Edgeworth Accountant: An Analytical Approach to Differential Privacy Composition

Huanyu Zhang; Hua Wang; Jiayuan Wu; Milan Shen; Sheng Gao; Weijie J. Su

arxiv: 2206.04236 · v3 · submitted 2022-06-09 · 💻 cs.CR · cs.DS· cs.LG· stat.ML

Edgeworth Accountant: An Analytical Approach to Differential Privacy Composition

Hua Wang , Sheng Gao , Huanyu Zhang , Milan Shen , Weijie J. Su , Jiayuan Wu This is my paper

Pith reviewed 2026-05-24 11:03 UTC · model grok-4.3

classification 💻 cs.CR cs.DScs.LGstat.ML

keywords differential privacycompositionEdgeworth expansionprivacy lossf-differential privacyPLLRnoise addition

0 comments

The pith

The Edgeworth Accountant applies Edgeworth expansion to privacy-loss log-likelihood ratios to deliver closed-form (ε, δ) bounds for differential privacy composition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Edgeworth Accountant to compute the overall privacy loss when multiple private mechanisms are composed. It operates inside the f-differential privacy framework and uses the Edgeworth expansion to approximate the distribution of the sum of privacy-loss log-likelihood ratios. This produces non-asymptotic (ε, δ) bounds whose computational cost stays fixed even as the number of composed mechanisms grows. The approach works for arbitrary noise-addition mechanisms once their distributions are reduced to simpler forms. The resulting bounds are shown to be tight and accurate for tasks such as private deep learning and federated analytics.

Core claim

Leveraging the f-differential privacy framework, the Edgeworth Accountant accurately tracks privacy loss under composition, enabling a closed-form expression of privacy guarantees through privacy-loss log-likelihood ratios (PLLRs) by applying the Edgeworth expansion to estimate the probability distribution of their sum.

What carries the argument

Edgeworth expansion applied to the sum of privacy-loss log-likelihood ratios (PLLRs) to estimate their distribution under composition.

If this is right

Yields non-asymptotic (ε, δ) bounds whose running time does not grow with the number of composed mechanisms.
Supplies both upper and lower bounds on the privacy guarantee that remain tight for practical noise distributions.
Extends directly to any noise-addition mechanism once its privacy-loss distribution is simplified.
Supports accurate privacy accounting for deep-learning training and federated analytics pipelines.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The fixed-cost accounting could let practitioners run many more composition steps before privacy budgets are exhausted.
If the simplification step can be automated, the method would apply to mechanisms whose exact PLLR distributions are currently intractable.
Direct numerical comparison on small compositions would quickly reveal whether the Edgeworth truncation order needs to increase for high-accuracy regimes.

Load-bearing premise

A reduction technique exists that converts any noise-addition mechanism's distribution into a simpler form to which the Edgeworth expansion can be applied.

What would settle it

Compute the exact (ε, δ) privacy loss for a composition of many identical Gaussian mechanisms and compare it against the Edgeworth Accountant's predicted bounds to check for large deviation.

Figures

Figures reproduced from arXiv: 2206.04236 by Huanyu Zhang, Hua Wang, Jiayuan Wu, Milan Shen, Sheng Gao, Weijie J. Su.

**Figure 1.** Figure 1: The comparison between the GDP approximation in [9], and our Edgeworth Accountant. Both methods start from the exact composition using f-DP. Upper: [9] uses a CLT type approximation to get a GDP approximation to the f-DP guarantee, then converts it to (ε, δ)-DP via duality (Fact 1). Lower: We losslessly convert the f-DP guarantee to an exact (ε, δ(ε))-DP guarantee, with δ(ε) defined with PLLRs in (3.1), an… view at source ↗

**Figure 2.** Figure 2: The privacy curve computed via several different accountants. Left: The setting in [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

**Figure 3.** Figure 3: We demonstrate the comparisons between our Edgeworth Accountant (both AEA and EEAI), the RDP accountant, and the FFT accountant (whose precision of ε is set to be 0.1). The three settings are set so that the privacy guarantees does not change dramatically as m increases. Specifically, in all three settings, we set δ = 0.1, σ = 0.8, and p = 0.4/ √ m (left), p = 1/ √ m log m (middle), and p = 0.1 p log m/m (… view at source ↗

**Figure 4.** Figure 4: The value of (a +−a) 2 2 log(Φ(a+)−Φ(a)) when a > 0. Proof of Lemma E.2. Recall the definition in Equation (E.2), we can re-write Bi as a mixture random variable Bi = ( 0 w.p. P(ξi < a), ˜ξiµ − a +µ w.p. P(ξi ≥ a). where ˜ξi = ξi [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗

read the original abstract

In privacy-preserving data analysis, many procedures and algorithms are structured as compositions of multiple private building blocks. As such, an important question is how to efficiently compute the overall privacy loss under composition. This paper introduces the Edgeworth Accountant, an analytical approach to composing differential privacy guarantees for private algorithms. Leveraging the $f$-differential privacy framework, the Edgeworth Accountant accurately tracks privacy loss under composition, enabling a closed-form expression of privacy guarantees through privacy-loss log-likelihood ratios (PLLRs). As implied by its name, this method applies the Edgeworth expansion to estimate and define the probability distribution of the sum of the PLLRs. Furthermore, by using a technique that simplifies complex distributions into simpler ones, we demonstrate the Edgeworth Accountant's applicability to any noise-addition mechanism. Its main advantage is providing $(\epsilon, \delta)$-differential privacy bounds that are non-asymptotic and do not significantly increase computational cost. This feature sets it apart from previous approaches, in which the running time increases with the number of mechanisms under composition. We conclude by showing how our Edgeworth Accountant offers accurate estimates and tight upper and lower bounds on $(\epsilon, \delta)$-differential privacy guarantees, especially tailored for training private models in deep learning and federated analytics.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The Edgeworth Accountant applies the series to PLLR sums for analytical DP composition with fixed cost, but the non-asymptotic bound claim rests on an uncontrolled remainder.

read the letter

The paper's core move is to take the sum of privacy-loss log-likelihood ratios under the f-DP framework and approximate its distribution with an Edgeworth expansion, then convert that into closed-form (ε, δ) bounds. A second step simplifies the target distribution so the same accountant works for any additive noise mechanism. The practical payoff they advertise is that the cost stays constant no matter how many mechanisms you compose, unlike numerical accountants whose work grows with the number of steps. That is the actual novelty: the specific construction inside f-DP rather than another moments accountant or a pure numerical method. If the math closes, it would be a useful tool for people running hundreds of gradient steps in private deep learning. The abstract states that the resulting bounds are accurate and tight, and the simplification trick is presented as general. Those are the parts that could matter to practitioners who need something faster than exact or Monte-Carlo accounting. The main weakness is exactly the one the stress-test flags. Edgeworth is an asymptotic expansion whose truncation error is controlled only in the large-n limit and depends on the next cumulant; nothing in the abstract or the high-level description shows a uniform remainder bound that survives the simplification map and still delivers rigorous non-asymptotic (ε, δ) guarantees for finite composition counts. Without that control, or at least a clear numerical validation against exact composition on standard mechanisms, the central claim is not yet supported. The paper is written for the privacy-accounting subfield rather than the broader DP community. A reader who already works on accountants and is willing to do the error-term homework themselves could extract an idea worth testing. It is coherent enough on its own terms to deserve referee time; the question is whether the remainder can be handled or whether the method has to be sold as an approximation with empirical error bars. I would send it out for review so the derivation and any validation data can be checked directly.

Referee Report

2 major / 1 minor

Summary. The paper introduces the Edgeworth Accountant, an analytical approach to composing differential privacy guarantees. Leveraging the f-differential privacy framework, it applies the Edgeworth expansion to the sum of privacy-loss log-likelihood ratios (PLLRs) to obtain a closed-form expression for privacy guarantees. A distribution-simplification technique is used to extend the method to any noise-addition mechanism, yielding non-asymptotic (ε, δ) bounds whose computational cost does not grow with the number of compositions.

Significance. If the non-asymptotic bounds are placed on a rigorous footing, the work would supply an efficient analytical privacy accountant whose runtime is independent of composition count, which is directly useful for iterative training in deep learning and federated analytics. The attempt to derive closed-form expressions via Edgeworth expansion on PLLR sums is a concrete technical contribution worth evaluating on its own terms.

major comments (2)

[Abstract] Abstract: the claim that the Edgeworth Accountant supplies non-asymptotic (ε, δ) bounds is load-bearing for the central contribution, yet the Edgeworth series is asymptotic in powers of 1/√n; no uniform remainder bound (e.g., expressed via the next cumulant or an adapted Berry–Esseen inequality that survives the distribution-simplification map) is referenced or derived.
[Paragraph on applicability] Paragraph on applicability: the technique that simplifies complex distributions into simpler ones is asserted to make the accountant applicable to arbitrary noise-addition mechanisms, but the approximation error introduced by this simplification step is not quantified or propagated into the final (ε, δ) expressions.

minor comments (1)

The abstract states that the method 'offers accurate estimates and tight upper and lower bounds' but supplies no reference to numerical validation experiments or comparison tables against existing accountants.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive major comments. The observations on the asymptotic character of the Edgeworth expansion and the unquantified error from distribution simplification directly affect the strength of the central claims. We respond to each point below.

read point-by-point responses

Referee: [Abstract] Abstract: the claim that the Edgeworth Accountant supplies non-asymptotic (ε, δ) bounds is load-bearing for the central contribution, yet the Edgeworth series is asymptotic in powers of 1/√n; no uniform remainder bound (e.g., expressed via the next cumulant or an adapted Berry–Esseen inequality that survives the distribution-simplification map) is referenced or derived.

Authors: We agree that the Edgeworth series is asymptotic and that the manuscript does not supply a uniform remainder bound that would render the resulting (ε, δ) expressions rigorously non-asymptotic for every finite n. The term 'non-asymptotic' was used in the abstract to contrast the method with accountants whose cost grows with the number of compositions, rather than to assert a fully rigorous error-controlled bound. We will revise the abstract and the opening paragraphs to qualify the claim, replace 'non-asymptotic' with 'closed-form for finite compositions,' and insert a brief discussion of truncation error together with references to existing Edgeworth remainder results. A complete uniform bound under the distribution-simplification map would require further technical work beyond the scope of the present revision. revision: partial
Referee: [Paragraph on applicability] Paragraph on applicability: the technique that simplifies complex distributions into simpler ones is asserted to make the accountant applicable to arbitrary noise-addition mechanisms, but the approximation error introduced by this simplification step is not quantified or propagated into the final (ε, δ) expressions.

Authors: The distribution-simplification step is presented as a practical device that reduces arbitrary noise-addition mechanisms to a form amenable to the Edgeworth expansion, yet the manuscript indeed contains no explicit bound on the total-variation or privacy-loss distance introduced by the simplification, nor does it propagate that distance into the final (ε, δ) expressions. We will add a short subsection that (i) states the simplification map explicitly, (ii) derives a simple bound on the induced error in the privacy-loss random variable, and (iii) shows how this error can be absorbed into the final δ term. The revision will be incorporated in full. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation applies standard Edgeworth expansion to PLLR sums in established f-DP framework

full rationale

The paper claims to track privacy loss by applying the Edgeworth expansion (a classical asymptotic series) to the sum of PLLRs under the f-differential privacy framework, then using a distribution-simplification step to extend to arbitrary noise mechanisms. No quoted equation or step reduces the resulting non-asymptotic (ε,δ) bounds to a quantity defined in terms of itself, to a fitted parameter renamed as a prediction, or to a self-citation chain whose validity depends on the present work. The central claim therefore remains an independent analytical estimation procedure whose correctness can be checked against external benchmarks without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the validity of the Edgeworth expansion for sums of PLLRs and on the f-DP framework; no free parameters or invented entities are mentioned in the abstract.

axioms (2)

standard math The Edgeworth expansion supplies a usable approximation to the distribution of the sum of independent PLLRs.
Invoked when the paper states it applies the Edgeworth expansion to estimate the probability distribution of the sum of the PLLRs.
domain assumption The f-differential privacy framework correctly models the privacy loss of the mechanisms under consideration.
The abstract states the method leverages the f-DP framework.

pith-pipeline@v0.9.0 · 5773 in / 1437 out tokens · 40554 ms · 2026-05-24T11:03:16.976901+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Leveraging the f-differential privacy framework, the Edgeworth Accountant accurately tracks privacy loss under composition... applies the Edgeworth expansion to estimate... the sum of the PLLRs.
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We provide a finite-sample error bound... first time such a bound has been established in the statistical and differential privacy communities.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The 2020 US Decennial Census is more private than you (might) think
cs.CR 2024-10 unverdicted novelty 6.0

Using f-differential privacy to track losses across eight geographic levels, the 2020 Census provides stronger privacy than its nominal guarantees, enabling 15.08-24.82% noise variance reduction.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · cited by 1 Pith paper · 1 internal anchor

[1]

Abadi, A

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with diﬀerential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016

work page 2016
[2]

Balle, G

B. Balle, G. Barthe, and M. Gaboardi. Privacy ampliﬁcation by subsampling: Tight analyses via couplings and divergences.Advances in Neural Information Processing Systems, 31, 2018

work page 2018
[3]

Balle and Y.-X

B. Balle and Y.-X. Wang. Improving the gaussian mechanism for diﬀerential privacy: Analytical calibration and optimal denoising. InInternational Conference on Machine Learning, pages 394–403. PMLR, 2018

work page 2018
[4]

Z. Bu, J. Dong, Q. Long, and W. J. Su. Deep learning with Gaussian diﬀerential privacy. Harvard data science review, 2020(23), 2020

work page 2020
[5]

M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74–86, 2018

work page 2018
[6]

Bun and T

M. Bun and T. Steinke. Concentrated diﬀerential privacy: Simpliﬁcations, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635–658. Springer, 2016. 13

work page 2016
[7]

Chaudhuri, C

K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Diﬀerentially private empirical risk mini- mization. Journal of Machine Learning Research, 12(3), 2011

work page 2011
[8]

Derumigny, L

A. Derumigny, L. Girard, and Y. Guyonvarch. Explicit non-asymptotic bounds for the distance to the ﬁrst-order edgeworth expansion.arXiv preprint arXiv:2101.05780, 2021

work page arXiv 2021
[9]

J. Dong, A. Roth, and W. J. Su. Gaussian diﬀerential privacy.Journal of the Royal Statistical Society: Series B (Statistical Methodology) (with discussion), 84(1):3–37, 2022

work page 2022
[10]

Dwork, F

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. InTheory of cryptography conference, pages 265–284. Springer, 2006

work page 2006
[11]

Concentrated Differential Privacy

C. Dwork and G. N. Rothblum. Concentrated diﬀerential privacy. arXiv preprint arXiv:1603.01887, 2016

work page internal anchor Pith review Pith/arXiv arXiv 2016
[12]

Dwork, G

C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and diﬀerential privacy. In2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010

work page 2010
[13]

S. Gopi, Y. T. Lee, and L. Wutschitz. Numerical composition of diﬀerential privacy.arXiv preprint arXiv:2106.02848, 2021

work page arXiv 2021
[14]

Hall.The bootstrap and Edgeworth expansion

P. Hall.The bootstrap and Edgeworth expansion. Springer Science & Business Media, 2013

work page 2013
[15]

Kairouz, S

P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for diﬀerential privacy. In International conference on machine learning, pages 1376–1385. PMLR, 2015

work page 2015
[16]

Koskela, J

A. Koskela, J. Jälkö, and A. Honkela. Computing tight diﬀerential privacy guarantees using ﬀt. In International Conference on Artiﬁcial Intelligence and Statistics, pages 2560–2569. PMLR, 2020

work page 2020
[17]

I. Mironov. Rényi diﬀerential privacy. In2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017

work page 2017
[18]

H. Prawitz. On the remainder in the central limit theorem: Part i. onedimensional indepen- dent variables with ﬁnite absolute moments of third order.Scandinavian Actuarial Journal, 1975(3):145–156, 1975

work page 1975
[19]

Ramage and S

D. Ramage and S. Mazzocchi. Federated analytics: Collaborative data science without data collection. https://ai.googleblog.com/2020/05/federated-analytics-collaborative-data.html, 2020

work page 2020
[20]

Shevtsova

I. Shevtsova. Reﬁnement of estimates for the rate of convergence in lyapunov’s theorem. In Dokl. Akad. Nauk, volume 435, pages 26–28, 2010

work page 2010
[21]

S. Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with diﬀerentially private updates. In2013 IEEE Global Conference on Signal and Information Processing, pages 245–248. IEEE, 2013

work page 2013
[22]

D. Wang, S. Shi, Y. Zhu, and Z. Han. Federated analytics: Opportunities and challenges.IEEE Network, 2021. 14

work page 2021
[23]

Y.-X. Wang, B. Balle, and S. P. Kasiviswanathan. Subsampled rényi diﬀerential privacy and analytical moments accountant. InThe 22nd International Conference on Artiﬁcial Intelligence and Statistics, pages 1226–1235. PMLR, 2019

work page 2019
[24]

Zheng, J

Q. Zheng, J. Dong, Q. Long, and W. J. Su. Sharp composition bounds for gaussian diﬀerential privacy via edgeworth expansion. InInternational Conference on Machine Learning, pages 11420–11435. PMLR, 2020

work page 2020
[25]

W. Zhu, P. Kairouz, B. McMahan, H. Sun, and W. Li. Federated heavy hitters discovery with diﬀerential privacy. InInternational Conference on Artiﬁcial Intelligence and Statistics, pages 3837–3847. PMLR, 2020

work page 2020
[26]

Y. Zhu, J. Dong, and Y.-X. Wang. Optimal accounting of diﬀerential privacy via characteristic function. arXiv preprint arXiv:2106.08567, 2021. 15 Appendix A Analysis of NoisySGD We present the algorithms we considered in Section 1.1. To start with, suppose we have a neural networkh that is governed by weightsw, with samplesxi and labelsyi (i = 1,...,n ). ...

work page arXiv 2021
[27]

E(˜ξi) = φ(a) 1−Φ(a)

work page
[28]

Proof of Lemma E.4.This is based on several well-known truncated normal properties, and is easy to prove from the density function

P(˜ξi ≤t) = Φ(t)−Φ(a) 1−Φ(a) . Proof of Lemma E.4.This is based on several well-known truncated normal properties, and is easy to prove from the density function. Therefore we omit the proof here. F Details of Edgeworth approximation error The following discussion is largely adapted from [8] to be self-contained. For a distributionP, let fP denote its cha...

work page 1961

[1] [1]

Abadi, A

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with diﬀerential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016

work page 2016

[2] [2]

Balle, G

B. Balle, G. Barthe, and M. Gaboardi. Privacy ampliﬁcation by subsampling: Tight analyses via couplings and divergences.Advances in Neural Information Processing Systems, 31, 2018

work page 2018

[3] [3]

Balle and Y.-X

B. Balle and Y.-X. Wang. Improving the gaussian mechanism for diﬀerential privacy: Analytical calibration and optimal denoising. InInternational Conference on Machine Learning, pages 394–403. PMLR, 2018

work page 2018

[4] [4]

Z. Bu, J. Dong, Q. Long, and W. J. Su. Deep learning with Gaussian diﬀerential privacy. Harvard data science review, 2020(23), 2020

work page 2020

[5] [5]

M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74–86, 2018

work page 2018

[6] [6]

Bun and T

M. Bun and T. Steinke. Concentrated diﬀerential privacy: Simpliﬁcations, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635–658. Springer, 2016. 13

work page 2016

[7] [7]

Chaudhuri, C

K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Diﬀerentially private empirical risk mini- mization. Journal of Machine Learning Research, 12(3), 2011

work page 2011

[8] [8]

Derumigny, L

A. Derumigny, L. Girard, and Y. Guyonvarch. Explicit non-asymptotic bounds for the distance to the ﬁrst-order edgeworth expansion.arXiv preprint arXiv:2101.05780, 2021

work page arXiv 2021

[9] [9]

J. Dong, A. Roth, and W. J. Su. Gaussian diﬀerential privacy.Journal of the Royal Statistical Society: Series B (Statistical Methodology) (with discussion), 84(1):3–37, 2022

work page 2022

[10] [10]

Dwork, F

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. InTheory of cryptography conference, pages 265–284. Springer, 2006

work page 2006

[11] [11]

Concentrated Differential Privacy

C. Dwork and G. N. Rothblum. Concentrated diﬀerential privacy. arXiv preprint arXiv:1603.01887, 2016

work page internal anchor Pith review Pith/arXiv arXiv 2016

[12] [12]

Dwork, G

C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and diﬀerential privacy. In2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010

work page 2010

[13] [13]

S. Gopi, Y. T. Lee, and L. Wutschitz. Numerical composition of diﬀerential privacy.arXiv preprint arXiv:2106.02848, 2021

work page arXiv 2021

[14] [14]

Hall.The bootstrap and Edgeworth expansion

P. Hall.The bootstrap and Edgeworth expansion. Springer Science & Business Media, 2013

work page 2013

[15] [15]

Kairouz, S

P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for diﬀerential privacy. In International conference on machine learning, pages 1376–1385. PMLR, 2015

work page 2015

[16] [16]

Koskela, J

A. Koskela, J. Jälkö, and A. Honkela. Computing tight diﬀerential privacy guarantees using ﬀt. In International Conference on Artiﬁcial Intelligence and Statistics, pages 2560–2569. PMLR, 2020

work page 2020

[17] [17]

I. Mironov. Rényi diﬀerential privacy. In2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017

work page 2017

[18] [18]

H. Prawitz. On the remainder in the central limit theorem: Part i. onedimensional indepen- dent variables with ﬁnite absolute moments of third order.Scandinavian Actuarial Journal, 1975(3):145–156, 1975

work page 1975

[19] [19]

Ramage and S

D. Ramage and S. Mazzocchi. Federated analytics: Collaborative data science without data collection. https://ai.googleblog.com/2020/05/federated-analytics-collaborative-data.html, 2020

work page 2020

[20] [20]

Shevtsova

I. Shevtsova. Reﬁnement of estimates for the rate of convergence in lyapunov’s theorem. In Dokl. Akad. Nauk, volume 435, pages 26–28, 2010

work page 2010

[21] [21]

S. Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with diﬀerentially private updates. In2013 IEEE Global Conference on Signal and Information Processing, pages 245–248. IEEE, 2013

work page 2013

[22] [22]

D. Wang, S. Shi, Y. Zhu, and Z. Han. Federated analytics: Opportunities and challenges.IEEE Network, 2021. 14

work page 2021

[23] [23]

Y.-X. Wang, B. Balle, and S. P. Kasiviswanathan. Subsampled rényi diﬀerential privacy and analytical moments accountant. InThe 22nd International Conference on Artiﬁcial Intelligence and Statistics, pages 1226–1235. PMLR, 2019

work page 2019

[24] [24]

Zheng, J

Q. Zheng, J. Dong, Q. Long, and W. J. Su. Sharp composition bounds for gaussian diﬀerential privacy via edgeworth expansion. InInternational Conference on Machine Learning, pages 11420–11435. PMLR, 2020

work page 2020

[25] [25]

W. Zhu, P. Kairouz, B. McMahan, H. Sun, and W. Li. Federated heavy hitters discovery with diﬀerential privacy. InInternational Conference on Artiﬁcial Intelligence and Statistics, pages 3837–3847. PMLR, 2020

work page 2020

[26] [26]

Y. Zhu, J. Dong, and Y.-X. Wang. Optimal accounting of diﬀerential privacy via characteristic function. arXiv preprint arXiv:2106.08567, 2021. 15 Appendix A Analysis of NoisySGD We present the algorithms we considered in Section 1.1. To start with, suppose we have a neural networkh that is governed by weightsw, with samplesxi and labelsyi (i = 1,...,n ). ...

work page arXiv 2021

[27] [27]

E(˜ξi) = φ(a) 1−Φ(a)

work page

[28] [28]

Proof of Lemma E.4.This is based on several well-known truncated normal properties, and is easy to prove from the density function

P(˜ξi ≤t) = Φ(t)−Φ(a) 1−Φ(a) . Proof of Lemma E.4.This is based on several well-known truncated normal properties, and is easy to prove from the density function. Therefore we omit the proof here. F Details of Edgeworth approximation error The following discussion is largely adapted from [8] to be self-contained. For a distributionP, let fP denote its cha...

work page 1961