Analytical Composition of Differential Privacy via the Edgeworth Accountant
Authors: Hua Wang
Sheng Gao
Huanyu Zhang
Milan Shen
Weijie J Su
Venue: Submitted to ICLR 2023 (2023)
Keywords: Differential Privacy
f-Differential Privacy
Edgeworth Expansion
PLLR
Edgeworth Accountant

Abstract: Many modern machine learning algorithms are composed of simple private algorithms; thus, an increasingly important problem is to efficiently compute the overall privacy loss under composition. In this study, we introduce the Edgeworth Accountant, an analytical approach to composing differential privacy guarantees of private algorithms. The Edgeworth Accountant starts by losslessly tracking the privacy loss under composition using the $f$-differential privacy framework, which allows us to express the privacy guarantees using privacy-loss log-likelihood ratios (PLLRs). As the name suggests, this accountant next uses the Edgeworth expansion to the upper and lower bounds the probability distribution of the sum of the PLLRs. Moreover, by relying on a technique for approximating complex distributions using simple ones, we demonstrate that the Edgeworth Accountant can be applied to the composition of any noise-addition mechanism. Owing to certain appealing features of the Edgeworth expansion, the $(\epsilon, \delta)$-differential privacy bounds offered by this accountant are non-asymptotic, with essentially no extra computational cost, as opposed to the prior approaches, wherein the running times increase with the number of compositions. Finally, we demonstrate that our upper and lower $(\epsilon, \delta)$-differential privacy bounds are tight in federated analytics and certain regimes of training private deep learning models.

Under review as a conference paper at ICLR 2023
ANALYTICAL COMPOSITION OF DIFFERENTIAL PRI- VACY VIA THE EDGEWORTH ACCOUNTANT
Anonymous authors Paper under double-blind review
ABSTRACT
Many modern machine learning algorithms are in the form of composition of simple private algorithms; thus, an increasingly important problem is to efficiently compute the overall privacy loss under composition. In this paper, we introduce the Edgeworth Accountant, an analytical approach to composing differential privacy guarantees of private algorithms. The Edgeworth Accountant starts by losslessly tracking the privacy loss under composition using the f f-differential privacy frame- work (Dong al., 2022), which allows us to express the privacy guarantees using privacy-loss log-likelihood ratios (PLLRs). As the name suggests, this accoun- tant next uses the Edgeworth expansion (Hall 2013) to upper and lower bound the probability distribution of the sum of the PLLRs. Moreover, by relying a technique for approximating complex distributions by simple ones, we demonstrate that the Edgeworth Accountant can be applied to composition of any mechanism. Owing to certain appealing features of the Edgeworth expansion, the (e, 6) -)ddifferettial privacy bounds offered by this accountant are non-asymptotic, with essentially no extra computational cost, as opposed to the prior approaches in Koskela et al.] (2020); Gooi al.] (202I). in which the running times are in- creasing with the number of compositions. Finally, we show our upper and lower (e, 3)-differential privacy bounds are tight in certain regimes of training private deep learning models and federated analytics.
INTRODUCTION
Differential privacy (DP) provides a mathematically rigorous framework for analyzing and developing private algorithms working on datasets containing sensitive information about individuals (Dwork et This framework, however, is often faced with challenges when comes to analyzing the privacy loss of complex algorithms such privacy-preservigg deep learning and federated analytics (Ramage & Mazzocchi] 2020) Wang et al. 2021), which are composed of simple private building blocks. Therefore, central question in this active area is understand how the overall privacy guarantees degrade from the repetition of simple algorithms applied to the same dataset.
Continued efforts to address this question have led to the development relaxations of differential privacy and privacy analysis techniques (Dwork et al. 2010 Dwork& & Rothblum 2016 Bun et al. 2018 Bun & Steinke 2016). recent flurry of activity this line of research was triggered by Abadi et al. (216)), which proposed a technique called moments accountant for providing upper bounds on the overall privacy loss training private deep learning models over iterations. A shortcoming of moments accountant is that the privacy bounds are generally not tight, albeit computationally efficient. This is because this technique is enabled by Rényi DP in [Mironov (2017) and its following works (Balle al. 2018 Wang et al. 2019), whose privacy loss profile can be lossy for many mechanisms. Alternatively, y, another line of works directly compose (s. 5) guarantees via numerical methods such the fast Fourier transform (Koskela et al. 2020 Gopi al. 2021).
This approach can be computationally expensive, as the number of algorithms under composition is huge, which unfortunately is often the case for training deep neural networks.
Instead, this paper aims to develop computationally efficient lower and upper privacy bounds for the composition of private algorithms with finite-sample guarantees by relying on new privacy defini-
Herr, "sample" refers to the number of compositions of DP algorithms. From now on we use the term "finite-sample" mean that the bound is non-asymptotic in the number of compositions.

---

Under review as a conference paper at ICLR 2023
lossy approximation via CL.T
duality (ÉCLT, dCL
f-DP
approximate GDP
PLLI
(e, -DP
( >-PP
kinite-sampl bound via Edgeworth approximation
Figure 1: The comparison between the GDP approximation in Dong et al. (2022), and our Edge- worth Accountant. Both methods start from the exact composition using f-DP. Upper: Dong] let (2022) uses CLT type approximation to get GDP approximation to the f-DP guarantee, then converts it to (s, 6)-DP via duality (Fact D.. Lower: We losslessly convert the f-DP guarantee to an exact (e, 6(P))-DP guarantee. with 8()) defined with PLLRs in [31]. and then take the Edgeworth approximation to numerically compute the (),
tion called f-differential privacy (/-DP (Dong et al. 2022)). f-DP offers a complete characterization of DP guarantees via a hypothesis testing interpretation, which was first introduced Kairouz et al.) (2015), and enables a precise tracking of the privacy loss under composition using certain operation between the functional privacy parameters. Moreover, [Dng et al. (2022) developed an approximation tool for evaluating the overall privacy guarantees using central limit theorem (CLT), which can lead to approximate (E, 6)- guarantees using the duality between (s, 5DD and Gaussian Differential Privacy (GDP, special type of f-DP) (Dong et al. 2022). While the (s, 6)DD guarantees are asymptotically accurate, a usable snite-sample guarantee is lacking in the f-DP framework.
In this paper, we introduce the Edgeworth Accountant an analytically efficient approach to obtaining finite-sample (a, 6DP guarantees by leveraging the f-DP framework. In short, the Edgeworth Accountant makes of the Edgeworth approximation (Hall 2013), which is refinement to the CLT with better convergence rate, to approximate the distribution of the sum of certain random variables that we refer to privacy-loss log-likeliine ligeliill ratios (PLLRs). By leveraging Berry-Esseen type bound derived for the Edgeworth approximation, we obtain non-asymptotic upper and lower privacy bounds that are applicable to privacy-preserving deep learning and federated analytics. On a high level, we compare the approach of our Edgeworth Accountant to the Gaussian Differential Privacy approximation in Figure ! Additionally, we note that while the rate of the Edgeworth approximation is well conceived, the explicit finite-sample error bounds are highly non-trivial. To the best of our knowledge, the first time such a bound has been established in the statistics and differential privacy communities and it is also of interest on its own.
We have made available two versions of our Edgeworth Accountant to better fulfill practical needs: the approximate Edgeworth Accountant (AEA), and the exact Edgeworth Accountant interval (EEAI). The AEA can give an estimate with asymptotically accurate bound for any number of composition m. By using higher-order Edgeworth expansion, such estimate can be arbitrarily accurate, provided that the Edgeworth series converges, and therefore is useful in practice to quickly estimate privacy parameters. As for the FEAL, it provides accurate finite-sample bound for any It gives rigorous bound on the privacy parameters efficiently.
Our proposal is very important an efficiently computable ap-accoun. For the composition of m identical mechanisms, our algorithm runs in O(1) time to compute the privacy loss, and for the general case when we need compose m heterogeneous algorithms, the runtime becomes ((m). which is wnformation-thhoretiiee (Gopi al., (021)) provide accurate finite-sample bound, but can only achieve polynomial runtime for general composition of private algorithms. The suboptimal complcomyyyxtty of FFT-based methods leads to a large requirement of resources when m is large, and a large m is quite common in practice. For example, in deep learning and federated learning, m is the number of iterations (rounds) and can be potentially very large. To make things worse, in real-world applications, the same dataset is often adaptively used or shared among different tasks. To faithfully account for the privacy loss, the DP accountant system has to track the cost of each iteration across different tasks, further increasing the number of compositions. Our EEAI serves as the first DP accountant method that simultancously provides finite-sample guarantees, performs with optimal time complexity, and is very accurate (when m is large), which can be good supplement to the current toolbox.
optimal. In contrast, fast Fourier transform (FFT)-based algorithms
2

---

Under review as a conference paper at ICLR 2023
The paper is organized follows. We briefty summarize related work in privacy accounting of differentially private algorithms as well as our contributions in Section[] In Section 2 we introduce the concept of f-DP and its important properties. We then introduce the notion of privacy-loss log-likelihood ratios in Section 3 and establish how to use them for privacy accountant based on distribution function approximation. In Section we provide new method, Edgeworth Accountant, that can efficiently and almost accurately evaluate the privacy guarantees, while providing finite- sample error bounds. Simulation results and conclusions can be found in Sections 5 and 6 Proof' and technical details are deferred to the appendices.
1.1 MOTIVATING APPLICATIONS
We now discuss two motivating applications: the NoisySGI (Song et al.,
2013 Chaudhuri et al.
A et al. 2016 Bu et al. 2020) as well as the Federated Analytics and Federated Learning (Ramage & Mazzocchi 2020) Wang et al. (02T). The analysis DP guarantees of those applications important yet especially challenging due to the large number of compositions involved. Our goal is primarily to devise a general tool to analyze the DP guarantees for these applications.
NoisySGD. NoisySGD is one of the most popular algorithms for training differentially private neural networks. In contrast to the standard SGD, the NoisySGD has two additional steps in each iteration: clipping (to bound the sensitivity of the gradients) and noise addition (to guarantee the privacy of models). The details of the NoisySGD algorithm is described in Algorithm in Appendix B
Federated Analytics. Federated analytics is distributed analytical model, which performs statistical tasks through the interaction between a central server and local devices. To complete a global analytical task, in each iteration, the central server randomly selects subset of devices to earry out local analytics and then aggregates results for the statistical analysis. The total number of iterations is usually very large") in federated analytics, requiring a tight analysis of its DP guarantee.
1.2 RELATED WORK
In this section, we present the following comparison of several existing works in DP accountant in Table Specifically, we focus on their thcoretical guarantees and the runtime complexity when the number of composition is m. We present detailed survey of those DP accountants in Appendix A
Method
Finite- sample guarantee
Tightness of guarantee
Computational complexity
GDP/GDP-E
No
N/A
O(I), ((m)
MA
Only upper bound
Loose conversion to (E
O(1), O(m)
FFT
Yes
Yes
O(ym). O(m
EA
Yes
Yes
O(1), 0(m)
Table I: Comparison among different DP accountants. Each entry in the computation complex- ity contains two columns: (Left) the runtime for the composition of identical algorithms; (Right) the runtime for the composition of m general algorithms. GDP: the Gaussian differ- ential privacy accountant (Dong et al. (2022); GDP-E: the Edgeworth refinement to the GDP accountant (Zheng et al. 2020): MA: the moments accountant using Rényi-DP (Abadi et al. 2016); FFT: the fast Fourier transform accountant for privacy random variables (Gopi al. 2021 EA: the Edgeworth Accountant we propose, including both the AEA (Detinition
and the EEAI (Definition 4.2) *The guarantee of EA is tight when the order of the underlying Edgeworth expansion & is high, or when m is large for A 1.
1.3 OUR CONTRIBUTIONS
We now briefly summarize our three main contributions.
Improved time-complexity and estimation accuracy. We propose a new DP accountant method, termed Edgeworth Accountant, which gives finite-sample error bound in constant/linear time com- plexity for the composition of identical/general mechanisms. In practice, our method outperforms GDP and moments accountant, with almost the same runtime.
Thhe number of iterations can be small for single analytical task. However, in most practical cases, many statistical tasks performed on the same hase of users which leads a large number of total iterations.
3

---

Under review as a conference paper at ICLR 2023
A unified framework for efficient and computable evaluation of f-DP guarantee. Though the evaluation of f-DP guarantee is #P-hard, we provide a general framework to efficiently approximate it. Leveraging this framework, any approximation scheme to the CDFs of the sum of privacy-loss log-likelihood ratios (PLLRs) can directly transform to a new DP accountant.
Exact finite-sample Edgeworth bound analysis. We are, our best knowledge, the first to Edgeworth expansion with finite-sample bounds in the statistics and machine learning communities. The analysis of the finite-sample bound of Edgeworth expansion of its own interest, and has many potential applications. We further derive an explicit adaptive exponential decaying bound for the Edgeworth expansion of the PLLRs, which is the first such result for Edgeworth expansion.
PRELIMINARIES AND PROBLEM SETUP
In this section, we first define the notion of differential privacy and f-DP mathematically. We then set up the problem by revisiting our motivating applications.
A differentillly private algorithm promises that an adversary with perfect information about the entire private dataset in use - except for a single individual - would find it hard to distinguish between its presence or absence based on the output of the algorithm (Dwork et al. 2006), Formally, for s > 0. and 0 2 5 < 1, we consider a (randomized) algorithm M that takes as input a dataset. Definition 2.1. A randomized algorithm M is (e, 8D if for any neighboring dataset S, differing by an arbitrary sample, and for any event E, P (S) E E] & é P (M (S') E E +
In Dong et al. (2022), the authors propose to use the trade-off between the type-I error and type- error in place of a few privacy parameters in (s, DDDD. To formally define this new privacy notion, we denote by P and Q the distribution of (S) and (S"), and let & be (possibly randomized) rejection rule for a hypothesis testing, where Hn P vs. H1 Q. The trade-off function between P and Q is then defined as the mapping between type-I error type-Il error, that is, : Ep(o] & a}. This motivates the following definition.
f f= T(P, Q) a + inf {1 - (o[ø)
Definition 2.2. A (randomized) algorithm M is f f-differentially private if T (M( M (S')) > for all neighboring datasets S and S
The following facts about f-DP have been established in Bu et al. (0200) Dong al. 2022).
Fact 1 (Duality to (e, 8DP). A mechanism is f-DP if and only if it (s, 8(s)) for all E > 0, with 8(c) 1 (" Here ("())= = sup-occacco yr g(x:) is the convex conjugate of g.
Fact 2 (Composition). Letting M1 and M2 be two mechanisms, we define their composition al- gorithm M M(S) (S), M2 (S, Mi (S))). In general, the composition of more than two algorithms follows recursively. Given trade-off functions f = T(P, Q) and = T (P', Q'), let ff 7 g (P P',Q x Q²). Assume M, is fc-DP for 1,.... ... m. The composition theorem states that their m-fold composition algorithm is fi 8 ... & fm-DP, which is tight in general.
Fact 3 (Subsampling). Consider the following two most common subsampling schemes: (1) (Poisson subsampling) for each individual in the dataset S, includes its datum in the subsample independently with probability pt (2) (Uniform subsampling) draws a subsample of S that is chosen uniformly at
random among all s = |SS 1Sip-sized subsets of S. Denote Id(a) 1 - and suppose an algorithm M is fDP. The subsampling theorem for f-DP states that the Poisson subsampled and uniform subsampled algorithm are both min( 1 where fp pf + (1 p) Id.
Fact (Gaussian Differential Privacy (GDP).. To deal with the composition of f-DP guaran- tees, Dong et al. (2022) introduce the concept of μ-GDP, which is special case of f-DP with f f= Gj = T(N (0, A),A( (H, 1)). They prove that when all the f-D guarantees are close to the identity, their composition is asymptotically a GDGDP with some computable μ., which can then be converted to (e, 6DD via duality. However, it comes without a maite-sample bound.
With these facts, we can characterize the f-DP guarantee for motivating applications in Section I.I
NoisySGD. For a NoisySGD with m iterations, subsampling ratio of p. and noise multiplier o, it is m (Bu et al. 2020 Dong et al. 2022). with f = (pG1// + (1 p))d) Sm
Federated Analytics. Suppose there are m tasks, and each task is f.P with f. = T(P,, Q.). Then the overall DP guarantee is characterized by 8/ ft-DP.
4

---

Under review as a conference paper at ICLR 2023
It is easy to see that the f-DP guarantee of NoisySGD is special case of the f-DP guarantee of federated analytics with each trade-off function being ft = { f. } that is, with identical composition of subsampled Gaussian mechanisms. Therefore,
goal to efficiently and accurately
evaluate the privacy guarantee of the general X m i=1 f:-PP with an explicit finite-sample error bound.
3 PRIVACY-LOss LOG-LIKELIHOOD RATIOS (PLLRS)
We aim to compute the explicit DP guarantees for general composition of trade-off functions of the form f x0= ft. For the i-th composition, the trade-off function fi = T(P: Qi) is realized by the two hypotheses: Ho.: w; P. vs. m H : We ~ Qi where P.. Q; are two distributions. To evaluate the trade-off function f composite hypotheses Ho: w ~ Pi P2
fi. we are essentially distinguishing between the two x ... Pm vs. H1 : w ~ Q1 x Q2 x... x Qm. where w (wi,.... Wm) is the concatenation of all w; s. Motivated by the optimal test asserted by the Neyman- Lemma, we give the following definition.
The associated pair of privacy-loss log-likelihood ratios (PLLRs) is defined to be the logarithm of the Radon-Nikodym derivatives of two hypotheses under null and alternative hypothesis, respectively. Specifically, we can express PLLRs with respect Ho.: and Hi,i as
Definition 3.1.
X, log d..(t.))
dQ.(4)) where &, P. Qi- dQ:(6.) Y; log dP:(s.))
Note that the definition of PILRs only depends on the two hypotheses. allows us to convert the f-DP guarantee collection of (c, O)DP guarantees losslessly. The following proposition characterizes the relationship between e and 8 in terms of the distribution functions of PLLRs.
Proposition 3.2. Let XI,..., Xm and Y1.............. ......... Ymm be the PLLRs defined above. Let Fx.ms Fy. be the CDFs of X1 + +... + Xm and Y1 + ... + Ym. respectively. Then, the composed mechanism is f-DP (with f == f() if and only if is (s, O) for all with ö defined by
8 Fy,m(e) (e) e (x)m(E))-
(3.1)
Proposition 3.2 establishes a relationship between f-DP and a collection of (s, ((,)(D)) which reflects the primal-dual relationship between them. Note that some special forms of this general proposition have been proved previously terms of privacy loss random variables. See |Balle & Wang (2018); Zhu et al. ): Gopi et al. (202T) for details. The key contribution of our Proposition 3.2 is that we express the (c, dDD characterization of the #P-complete f-DP in terms of (3.1). which can be approximated directly. Of note, the above relationship is general in the sense that we make no assumption on the private mechanisms.
Definition 3.1 can be applied directly when dQ:(E:) is easy to compute, which corresponds to the 7P(5.) case without subsampling. To deal with the case with subsampling, one must take into account that the subsampled DP guarantee is the double conjugate of the minimum of two asymmetric trade-off functions (for example, recall the trade-off function of a single sub-sampled Gaussian mechanism is min where fo = (pG1/o - (1 p)))). In general, the composition of multiple subsampled mechanisms satisfies f-DP for f min 1 @ ) This general form makes the direct computation of the PLLRS through composite hypotheses infeasible, as it hard to write ff as trade-off function for some explicit pair of hypotheses Ho and H₁. Therefore, instead of using one single sequence of PLLRs directly corresponding to f. we shall use a family of sequences of PL.Rs. In general, suppose we have mechanism characterized by some f-DP guarantee, where (inf.ez ( for some index set I. That is. f is the tightest possible trade-off function satisfying all the -DP Suppose further that for each a, we can find a sequence of computable PLLRs corresponding to f(a), which allows us to obtain a collection of (e, 8(0z) (=))-DP guarantees.
Lemma 3.3. Suppose that for each a, functions f(a) and g(0) satisfy that mechanism f(a)-DP if and only if (c, gl0) (E) (DP for all E >> O. Then a mechanism and only if it is (s, (s,sup_ auppa60 (6(m) (+) {)) for all e > 0.
(infaer (f(a)))) -DP if
We defer the proof of this lemma to the appendices. The intuition is that both (infoez (f(a))) "*-DP "-DP
and (s, (o -DD correspond the tightest possible DP-guarantee for the entire collection.
For completeness, we explicitly require that all & and &a he independent.
5

---

Under review as a conference paper at ICLR 2023
Lemma 3.3 allows to characterize the subsampled Gaussian mechanism using two sequences of PLLRs. As mentioned above, it is f-DP with f = m S 1" where each fip (pG1/o + (1- p)]dd. For the first part, the PLLRs corresponding to 01
(pG21/o + (1 - p)ld) are given by x,") = log(1 + pe"S:- bx²), and y, = log(1 - p pellGi-24 24²), for 1 S S m, with & ~ ~N(0, 1), Ci ~ (0, 1) (1 pp) 1). And for the (LDG1// - -1 (1-p) 8om are given by + me $2²) ) and y,() log(1
second part, the PLLRs corresponding to @0 1 x(2) = --loo(1 & ~ 1), G ~ pV(0,, 1) + (1 p)W(,, Now substituting xx m and Fyar.. by any approximation (for example, using the CLT Edgeworth), we get computable relationship terms of the (c, (D))-D and similarly, we can get a relationship in terms of the (c, (E)) We conclude that the subsampled Gaussian mechanism is (E, max (oxx(d()) (E), (E)))
p= for sis m, with
3.1 TRANSFERRED ERROR BOUND BASED ON CDF APPROXIMATIONS
As discussed above, Lemma 3.3 allows us to characterize the double conjugate of the infimum of a collection of f(o)-DPs via analyzing each sequence of PLLRs separately. As result, our focus to compute the bounds of g(ax for each single trade-off function f(a) To fulfill the purpose, we seek an efficient algorithm for approximating distribution functions of the sum of PLLRs, namely, Fx Fx m Fycc)) This perspective provides general framework that naturally encompasses many existing methods, including fast Fourier transform (Gopi et al. (02T) and the characteristic function method (Zhu et al., 2021). They can be viewed as different methods for finding upper and lower bounds of I' ('xtt),m mm Ty(a), .m Specifically, we denote the upper and lower bounds of Fxto),m by F+. fx and F "xtm),m am? and similarly for Fyiu),, m These bounds can be easily converted the error bounds on privacy parameters of the form g(a)) (s) S (1a)(E) (E)), for all E >> 0, where
(E) = =1 - Frim m (E) - e Fxim) (E)). (0)+(()
(3.2)
(s) = Ft (ylm), (5) - E (1 (1- Fx (E)).
Thus, the DP guarantee of (infa f(a))'' -DP in the form of (e,8(=)) satisfies (o))( (s)] S
5(E) S supa (E)), for all æ >> 0. To convert the guarantee of the form (c, ((E)) for all E > 0
to the guarantee of the form (e(8), 5) for all
[0. 1), we can invert the above bounds on d(e) and
obtain the bounds of the form (6) < (0) S (0). Here (+)) is the largest root of equation
5 = sup (g(a))(())))))) (-)), and (8) is the smallest non-negative root of equation ò = sup, (g(()=(())) (.))
Remark 3.4. In practice, we often need to solve for those roots numerically, and we need to specify finite range in which we find all the roots. In Appendix B we exemplify how to find such range for NoisySGD, see Remark B.I in the appendices for details.
4 EDGEWORTH ACCOUNTANT WITH PINITE-SAMPLL GUARANTEE
In what follows, we present new approach, Edgeworth Accountant, based on the Edgeworth expansion to approximate the distribution functions of the sum of PLLRs. For simplicity, we demonstrate how to obtain the Edgeworth Accountant for any trade-off function f(a) based on a
single sequence of PLLRs {x("))m 1 { ( Henceforth, we drop the superscript a when it is clear from context. Specifically, we derive an approximate Edgeworth Accountant (AEA) and the
associated exact Edgeworth Accountant interval (EEAI) for with PLLRS [X:) (Y:), We define AEA and EEAI for general trade-off function of the form (infa f(a)) ** in Appendix
4.1 EDGEWORTH ACCOUNTANT
To approximate the CDF of a random variable X Σ. X₁. we introduce Edgeworth expansion
in its most general form, where X; 's are independent but not necessarily identical. Such generality allows account for composition of heterogeneous DP algorithms. Suppose E [X, 14
and Tp.i = E [(x, [t] < +00 for some p > 4. We define Bm := v DE E [[(,, pt)
and E 14 = Mn So, the standardized sum can be written as S. := (X Mm) Bm- We

---

Under review as a conference paper at ICLR 2023
denote km, (z) to be the k-th order Edgeworth approximation of Sm- Note that the central limit theorem (CLT) can be viewed as the 0-th order Edgeworth approximation. The first-order Edgeworth
approximation is given by adding one extra order (m) term to the CLT, that is, Em, x (z)
((z) Asm (2² 1) ((x)) Here, & and & are the CDF and PDF of a standard normal distribution, 6ym
and A is a constant to be defined in Lemma 4.3
It is known that (see for example, Hall (201))
the Edgeworth approximation of order p has an error rate of (( (2++1)/2), This desirable property motivates us to use the rescaled Edgeworth approximation Gm,,k (x) = Em.... ((xr - Mm) / Bm)
and Gm,,; (z) E ((x Mm)/ Bm.) to approximate Fx,m (z) and fy,m()), respectively, in
(.I]. This is what we term the approximate Edgeworth Accountant (AEA).
Definition 4.1 (AEA). The k-th order AEA that defines ō(E) for e > 0 is given by ō(E) = 1 Gm, (8) ef (1 - Gm,,,x(E)), for all > O.
Asymptotically, AEA is an exact accountant, due to the rate of convergence Edgeworth approximation admits. In practice, however, the finite-sample guarantee is still missing since the exact constant of such rate is unknown. To obtain a computable (e, (DD) bound via (3.1), we require the finite-sample bounds on the approximation error of the CDF for any finite number of iterations m. Suppose that we can provide finite-sample bound using Edgeworth approximation of the form [Fx,((x) -Gm.t.(xx)) S (x)), where A. (I) computable. Then we have
Ft.. (z)==C -Gm.k.((z) (z),,(()) and Fx, Gm,,k (z) - xmm...(x))) and similarly for my We now define the exact Edgeworth Accountant interval (EEAI). Definition 4.2 (EEAT), The k-th order EEAI associated with privacy parameter (() for > is given by _8+], where for all E > 0
(4.1)
where
5 (e) = 1 - Gm,,.Y (E) A
Gm, (e) + Am,xx(EE), ( X (+)).
(4.2)
8t (a) = - Km (E)
To bound the EEAL, it suffices to have a finite-sample bound on Am,x( and (
4.2 UNIFORM BOUND ON PLLRS
We now deal with the bound of the Edgeworth approximation on PLLRs in (4. Our starting point a uniform bound of the form A (ar) S 6m,6.x, for all x. The bound for Am,,, (a) follows identically. To achieve this goal, we follow the analysis on the samile-sampl bound in Derumigny ctt al. (02II) We state the bound of the first-order Edgeworth expansion.
Lemma 4.3. Define the average individual standard deviation Bm == Bm// V and the average standardized r-th cumulant as Ak. := 1 Ei= kr.// Ba, where kr. is the r-th centralized cumulant of the j-th sample. With bounded moments of order four, that is, Y4 < +o0 1 S i m, we have the (uniform) bound on Edgeworth expansion as
m
A,,1I S 0.1995Ks.m 0.031K3,m. s.m + 0.195K4.m 4.m + 0.054 (a Ks. + 3,m Vm
0.03882
T1,ma
m
where Kp.m := m- E E - 11111/ (Bm,),, which is the average standardized p-th absolute moment, and Ka,m= := Ka,m + 1. Em E E| r2. B Here 1i.m is remainder term of order O(1/m//4) that depends only on K3,m, K4,m and >a,m, and is defined in Equation (..I.
Note that this lemma deals with the first-order Edgeworth approximation which can be generalized to the higher-order Edgeworth approximations, We present the analysis of the second- and third-order in the appendices. The expression of fm.m only involves real integration with known constants which can be numerically evaluated in constant time.
Remark 4.4. The precision of the FEAT highly depends on the rate of the finite-sample bound of the Edgeworth expansion. Any better bounds for higher-order Edgeworth expansions can be directly applied to our EEAI by substituting Am,k,x(E), here we simply demonstrate when the first-order expansion. Observe that Lemma 4.3 gives a bound of order O(1/ /m) due to the reason that we want to deal with general independent but not necessarily identical random variables. We demonstrate how can obtain a O(1/m) rate in the i.i.d. case in Appendix H Our current first-order bound is primarily useful when m is large enough, but a bound for higher-order Edgeworth expansions can further improve the precision for all m.
leveraging
7

---

Under review as a conference paper at ICLR 2023
4.3 ADAPTIVE EXPONENTIAL DECAYING BOUND FOR NOISYSGD
One specific concern of the bound derived in the previous section is that it is uniform in e. Note that in (..1), there is amplification factor of error by ef in front of Fx,m. Therefore, as long as E grows in
m with order at least E (loo m), the error term in (3.I scales with order e m)) /O(m) ((1).
In this section, we study the compositions of subsampled Gaussian mechanism (including NoisySGD and many federated learning algorithms), where we are able improve the previous bound when e is large. Informally, omitting the dependence on m, we want to have bound of the form IFxm((e) xm,,,,xx = O(e-=)) to offset the effect of ef in front of Fx.m. To this end, we first prove that the tail bound of Fx,m (e) is of order O(e-=), with exact constant. Combining with the tail behavior of the Edgeworth expansion. we conclude that the difference has the desired convergence rate. Following the discussion in Section we need to calculate the bounds for two sequences of PLLRs separately. Here we focus on the sequence of PLLRs corresponding to (pG1/0 + (1 - p)ld) @m
These PLLRs are given by X; = log(1 - p + pett _=²), where & ~ N(, 1). The following theorem characterizes the tail behavior of Fx F..m. The tail bound of the sum of the other sequence of
PLLRS corresponding to ((pG1/a + (1 p) has the same rate, and can be proved similarly.
Theorem 1. There exist some positive constant a, and some associated constant nTa) >> O, such that the tail of .m can be bounded as - Fx,m (e) = ( X; 2 e) 2exp
[(etmmm] where -8m7'
(a - - 72 = max (log(1-ptpe"" pa- +ula" -a) -og((1)) 2², Tog [a]]
and a = día)
The proof of Theorem iis deferred to Appendix G along with its dependent technical lemmas. From the above theorem, we know that the tail of Fx.m (E) is O max(<"/m,m) /m.m)) = o(e-',, as long as E o(m). Note that in this case, the tail of the rescaled Edgeworth expansion is of the same order O max max(s_/m.m) /m.m)) = 5). Therefore, we can give finite-sample bound of the same rate for the difference between fx,m(() and its approximation G &.X at large Note that this finite-sample bound scales better than uniform bound Lemma 4.3 when mn and e are large.
4.4 EXTENSION TO OTHER MECHANISMS
Note that our analysis framework is applicable a wide range of common noise-adding mechanisms. Specifically, Lemma 4.3 only requires the distribution of PL.Rs to have bounded fourth moments. And for many common mechanisms, a counterpart of Theorem [ be proved similarly. We now demonstrate how to generalize our analysis to the Laplace Mechanism.
The Laplace Mechanism. It is straightforward to verify that the trade-off function for subsampled Laplace Mechanisms is given by min( + - -p)dd)ooo (idd)mm, ((TT. + (1 - p) where L [0, 1), Lap(u, 1)). The two associated sequences of PLLRS X₃ and Y, can be ex- y.")) = log (1 - + pel))- and xx()
pressed as: X x()) ()) = log (1 - p + pelf)
where & ~ Lap(O. 1). ~ pLap(u, 1) + (1 - Lap 1). Note that all the PLLRs are bounded and thus sub-Gaussian. This implies that we can apply Lemma 4.3 directly and also bound the tail similar to Theorem
- log (1 p + pel - (2 = - log (1 p + ((-
Proposition 4.5. Denote n = - max (E(X("), ((((()))(((()))) > O. The tail of the sum of both sequence of PLLRS under the Laplace Mechanism has the following inverse exponential be- havior, max (TP E x(1) 2 6) IP Em x(2) 2 26)} s exp _2(s+ma)²² ) where 72
(log(1 - p + pett) - log(1 - pe ?
5 NUMERICAL EXPERIMENTS
In this section, we illustrate the advantages of Edgeworth Accountant by presenting the plots of DP accountant curves under different settings. Specifically, we plot the privacy curve of against number of compositions and compare our methods (AEA and EEAD) with existing DP accountants. We provide the implementation of our Edgeworth Accountant in Appendix D
8

---

Under review as a conference paper at ICLR 2023
The AEA. We first demonstrate that proposed approximate Edgeworth Accountant (AEA) indeed very accurate, outperforming the existing Rényi DP and the CLT approximations in experiments. The first experiment has the same setting in Figure 1(b) in (oop et all (022I) where the authors report that both RDP and GDP are inaccurate, whereas the second setting corresponds to real federated learning task. The results settings in the caption. For each sub-figure, the dotted lines "FFT LOW" and "FFT UPP" denote the lower and upper bound computed by FFT (Gopi et al., 202T) which are used as the underlying ground truth. The "GDP" curve is computed by the CLT approximation (Bu et al.) (2020), the "RDP" curve computed by moments accountant using Rényi DP with subsampling amplification (Wang) er al. 2019), and the LEW_ESTT curve is computed by our (second-order) AEA. As is evident from the figures, our AEA outperforms the GDP and RDP.
shown in Figure 2 where describe the specific
0.7
2.5
0.30
UPP
0.6
CDP
2.0
RDP
0.25
0.5
MTLLOW
1.5
0.20
0.4
+1LUP
GDP
0.15
0.3
BW
1.0
RDF
0.10
0.2
0.5
0.05
0.1
0.0
500
1000
1500
2000
6
5000
10000 15000 20000
0
5000
10000 15000 20000
Figure 2: The privacy curve computed via several different accountants. Left: The setting in Figure 1(b) Gopi al. (202I). where p = 0.01. a 0.8. and 0.015. Middle and Right: The setting of real application task federated learning for 10 epochs, with p = 0.05, a = 1. and = 10 Here. "EW EST" is the estimate given by our approximate Edgeworth accountant. We omit the RDP curve in the middle subfigure for better comparisons with others.
The EEAL We now present the empirical performance of EEAI obtained in Section We still experiment with NoisySGD. Details of the experiments are in the caption of Figure 3 The two error bounds of EEAI are represented by "EW UPP" and "EW LOW". and all other curves are defined the same as in the previous setting, In addition to its optimal time complexity, our analytical finite-sample bounds also achieve better numerical stability for large m in many cases. See Appendix for details.
0.7
TFT LOW TFT UPF
0.7
ITT. Low
FFT. LOW
IFT UP
PFT LPP
1.2
TD
RDP
0.6
REP
EW EST
0.6
BW EST
EW UHP
BWLLOW
EA_LOW
0.5
BI UPP
EALLOW
0.5
0.4
0.3
0.3
0.6
0.2
0.2
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
166
1e6
1ec
Figure 3: We demonstrate the comparisons between our Edgeworth accountant (both AEA EEAI), the RDP accountant, and the FFT accountant (whose precision of e is set to be 0.1). The three settings are set so that the privacy guarantees does not change dramatically as increases. Specifically, in all three settings, we set 5 = 0.1, 0.8, and 0.4/ /m (left),
1/ v/v m log m (middle), and = 0.1v/oo log m/m (right). We omit the GDP curve here, because the performance is fairly close to the AEA ("EW EST curve) when is large.
CONCLUSION
In this paper, we provide novel way to efficiently evaluate the composition of f-DP, which serves as a general framework for constructing DP accountants based on approximations to PLLRs. Specifically, we introduced the Edgeworth Accountant, efficient approach to composing DP algorithms via Edgeworth approximation. In contrast, existing privacy accountant algorithms either fail to provide a finite-sample bound, or only achieve polynomial runtime for general compositions. Importantly, our approach is a complement to the existing literature when the number of compositions is large, which typical in applications such large-scale deep learning and federated analytics.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308 318, 2016.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning. pp. 394 403. PMLR, 2018.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances Neural Information Processing Systems, 31, 2018.
Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with Gaussian differential privacy. Harvard data science review, 2020(23), 2020.
Mark Bun and Thomas Steinke. Concentrated differrnntial privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016.
Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-86, 2018.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Alexis Derumigny, Lucas Girard, and Yannick Guyonvarch. Explicit non-asymptotic bounds for the distance the first-order edgeworth expansion. arXiv preprint arXiv:2101.05780 2021.
Jinshuo Dong, Aaron. Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology) (with discussion), 84(1):3-37, 2022.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint
16Xiv:1603.01 00./660300188 887,, 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and differential privacy. 2010 IEEE 51st Annual Symposium Foundations Computer Science, pp. 51-60. IEEE, 2010.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. arXiv preprint arXiv: 106.02848, 2021.
Peter Hall. The bootstrap and Edgeworth expansion. Springer Science Business Media, 2013.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pp. 1376-1385. PMLR, 2015.
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statisties, pp. 2560-2569.
PMLR, 2020.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEFE, 2017.
Hákan Prawitz. On the remainder in the central limit theorem: Part i. onedimensional independent variables with finite absolute moments of third order. Scandinavian Actuarial Journal, 1975(3): 145-156, 1975.
Daniel Ramage and Stefano Mazzocchi. Federated analytics: Collaborative data science without data collection. wttp:///..ooooooooooom////////ad
himl, 2020.
10

---

Under review as a conference paper at ICLR 2023
IG Shevtsova. Refinement of estimates for the rate of convergence in lyapunov's theorem. In Dokl. Akad. Nauk, volume 435, pp. 26-28, 2010.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differen- tially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248. IEEE, 2013.
Dan Wang, Siping Shi, Yifei Zhu, and Zhu Han. Federated analytics: Opportunities and challenges. IEEE Network, 2021.
Yu-Xi Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1226-1235. PMLR, 2019.
Qinqing Zheng, Jinshuo Dong, Qi Long, and Weijie J Su. Sharp composition bounds for gaussian differential privacy via edgeworth expansion. International Conference on Machine Learning. pp. 14420-14435, PMLR, 2020.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. arXiv preprint arXiv:2106.0888 08567 2021.


Reviews:
[{"review_id": "nbd9B4GgD9u", "reviewer": "Reviewer_Ri6D", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents Edgeworth Accountant (EA), an analytical approach to account the privacy loss of differentially private algorithms of multiple iterations (composition). The authors show that EA is more computationally efficient  than the Fast Fourier Transform approach and is more accurate than Renyi-DP accountant.", "summary_of_the_review": "This paper provides a new tool for the privacy analysis of iterative DP algorithms. The authors claim that their method is more accurate than existing ones, and the computational cost is affordable. The theoretical analysis seems to be sound. However, there are several main concerns about this paper that need to be addressed: \n\n(1) The trade-off of EA v.s. FFT and RDP are not clear\n\n(2) Experimental settings and results\n\n(3) How EA performs in its target applications is not clear", "strength_and_weaknesses": "Strength: Compared with existing approaches to account for DP guarantee, the proposed method provides a more accurate estimate while incurring lower computation cost. The theoretical analysis seems to be sound.\n\nWeakness: \n\nW1. The trade-off of EA vs. FFT and RDP are not clear. \n\n(1) Regarding the computation cost, how EA and FFT depend on the dimension of the noise is not covered. In particular, in table 1, only m (the number of compositions) is taken into account. \n\n(2) It is not clear why using RDP leads to a loose privacy accountant. Is it because of the conversion rule from RDP to (epsilon, delta)-DP, or some other limitations of RDP? It seems to me that RDP already gives a tight analysis for additive Gaussian noise, since there seems to be no slackness in the derivation in the original paper by Ilya Mironov. For the conversion from RDP to (epsilon, delta)-DP, Canone, Kamath, and Stenike propose an improved conversion rule in \"The Discrete Gaussian for Differential Privacy\" (see proposition 8); however, this improved rule is overlooked in the current paper. \n\n(3)  Does EA outperforms FFT and RDP when there is no subsampling? If subsampling is not the key factor, perhaps the author could move technicalities about subsampling to the appendix and focus more on EA itself.\n\n(4) Discussion on the effect of order for edgeworth approximation is also missing. How does the order influence the computation and accuracy of the estimate?\n\nW2. Unclear contributions. \n\nIt is not clear which propositions/lemmas/theorems in the draft are contributed by the author and which already exist in the literature. Maybe adding references could help.\n\nW3. Issues with experimental settings and results.\n\n(1) The author did not specify the size of the private dataset in their experiments at all. Delta=0.015 is too large for DP applications. \n\n(2) In Figure 3, why do we decrease the sampling probability p while increasing m?\n\n(3) It is unclear why the settings in Figures 2 and 3 are different? It seems that EEAI give the upper and lower bounds for AEA. It is better to put them in the same figures under the same settings.\n\n(4) What is the value of p (for Edgeworth approximation of order p) in the experiments? Is it the same as the subsampling rate p?\n\n(5) Please provide a figure for subsampling rate p=1 in the numerical experiments.\n\nW4. How EA performs in their target applications, noisy-SGD and Federated Analytics, is unclear.\n\n(1) No setting in the experiment section considers noisy-SGD. \n\n(2) The authors only show how their estimate for epsilon is more accurate, but do not provide any result on whether the more accurate estimate translates into better privacy-utility trade-off in the applications: noisy-SGD and Federated Analytics. \n\nW5. Overall, it is questionable if we should choose EA and f-DP to account for the privacy guarantee. As the authors have stated, GDP gives approximately the same result as EA, in the caption of Figure 3. In addition, FFT gives good enough upper and lower bounds for epsilon, as the gains in epsilon seem to be only marginal in Figures 2 and 3. How this more accurate estimate of privacy by EA translates into better privacy-utility trade-off is also not shown in the draft. In addition, the additional computation cost of FFT seems affordable since it is only a one time cost of O(sqrt(m)) and O(m^1.5). Should we choose EA over FFT?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "F9PNBDm3Vh", "reviewer": "Reviewer_iZYg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces the Edgeworth accountant, an accountant for composing DP mechanisms that obtains tighter guarantees and/or is faster to evaluate than existing accountants. The Edgeworth accountant of the paper is the first accountant to provide both finite-sample (i.e., non asymptotic in m) lower and upper bounds, with O(1) computational complexity for composing m iid mechanisms and O(m) for m non-iid mechanisms (here I believe the O() hides some dependences on the order of the Edgeworth approximation, though empirically the authors show a small order suffices). In contrast, the FFT accountant of Gopi et al. takes time O(sqrt(m)) and O(m^5/2) respectively, the moments accountant only gives upper bounds for non-asymptotic computations, and the Edgeworth refinement to the GDP accountant of Zheng et al. does not give a finite-sample guarantee.\n\nThe Edgeworth accountant (presented in the body of the paper for composing subsampled Gaussians, but which the authors show can be extended to other noise distributions common in the DP literature such as the Laplace mechanism) uses two ideas. First, it uses the fact that the optimal hypothesis test for which of two databases a DP output came from can be defined only in terms of the output's privacy-loss log-likelihood ratio (PLLR). In turn, the authors can show that composition of the f-DP guarantees given by the PLLR hypothesis tests, is equivalent to an (eps, delta)-DP guarantee written strictly in terms of the CDFs of the sum of the PLLRs. Second, these CDFs can be approximated using the Edgeworth expansion, a generalization of the central limit theorem which approximates the CDF of a distribution in terms of its cumulants. So, one can also approximate the (eps, delta)-DP guarantee given by the first idea, using the Edgeworth expansion. In order to obtain a strict upper/lower bound on the actual DP guarantees, one also needs a bound on the CDF approximation error given by the Edgeworth expansion, which the authors derive, and tighten for the special case of subsampled Gaussians. \n\nThe authors implement the (second-order) Edgeworth mechanism and show that in various settings, (i) the approximation given by their accountant is sandwiched between the upper and lower bounds given by the FFT accountant of Gopi et al, and much more accurate than RDP/CLT-based accountants, and (ii) the interval on epsilon given by their accountant is contained strictly within the interval given by the FFT accountant, and RDP is far outside both these intervals. ", "summary_of_the_review": "Overall I think the paper is above the acceptance threshold. As mentioned before, I think the paper is strong theoretically, contains some nice new ideas, and has a lot of potential for practical impact. That being said, it is not clear to me that the presentation of the paper, especially to practitioners who may lack some of the statistical background, is as accessible as it could be.", "strength_and_weaknesses": "The paper has two main strengths. First, it gives a very tight and efficient accounting scheme, that qualitative and quantitatively improves on past accounting schemes heavily. Accounting schemes are widespread in practice and there is good reason to believe the improvements on accounting will allow us to give stronger DP guarantees in practice (or equivalent, achieve much better accuracy for a target DP guarantee). The qualitative and improvements of the accountant are also good reason to hope it becomes widely used in practice. Second, the ideas leading up to the Edgeworth accountant are slick and feel \"natural in retrospect\", but the paper nonetheless is technically very novel, and the proofs are involved and several complex lemmas are needed to turn the ideas into an algorithm.\n\nThe main weakness of the paper is that a lot of technical background is assumed or quickly skipped over in the exposition. One would imagine the ideal reader for this paper is someone who e.g. maintains an actively used privacy accounting library and is interested in working on implementations of the Edgeworth accountant. It may be hard for such a person to read even through the body of the paper, since I don't believe the Edgeworth expansion is common knowledge among privacy researchers (while something like f-DP might be). Admittedly, this is probably at least somewhat true of most sufficiently technical papers given the page limit. But if it is possible to include even slightly more background on the Edgeworth expansion, it would make the paper much more approachable to the audience of interest. Of course, this may be difficult due to space constraints.\n\nNitpick: I think Proposition 3.2 or some part of its buildup should explicitly state/remind that f_i is the tradeoff given by thresholding the PLLRs, right now this needs to be inferred. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BaZpgOLdH9Y", "reviewer": "Reviewer_ESEo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper gives computationally efficient privacy bounds for the composition of DP algorithm with finite sample guarantees. The algorithm runs in constant time to compute the privacy loss for m identical DP mechanism, and in general case, the run time in $O(m)$ time. This improves on the previous results that use FFT. The proposed approach in this paper is Edgeworth accountancy. ", "summary_of_the_review": "Please see above.\n\nFor correctness below, I have not read the proofs so I cannot make a judgement on the correctness of the paper; however, none of the claims seems to be out of ordinary. Hence a rating of 3. Once I have verified the proofs, I will move it to 4. ", "strength_and_weaknesses": "The fact that they can compute the privacy cost for composition is constant for identical privacy mechanism and just linear in the general case. The paper also gives numerical experiments to substantiate their claim. \n\nI really did not see much of a weakness in the paper. I really liked reading the paper and if I am not missing something, this paper has definite improvement over previous work. The paper is well written. I have not yet verified the proof, and that is the only reason I am not giving full support in accepting the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "40oMKxYUxb", "reviewer": "Reviewer_kz4w", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The goal of the paper is to present algorithms computing tight non-asymptotic numerical estimates on the privacy parameters of $m$-fold compositions of differentially private algorithms. The paper uses the $f$-differential privacy formalism, which allows cleanly reducing the composition analysis to understanding the tail behavior of sums of independent privacy loss random variables. The original GDP paper of Dong, Roth, and Su used this idea to derive Berry-Esseen type bounds on the privacy loss parameters, as well as asymptotic limit theorems. This paper makes the natural next step (which was also explicitly suggested in the Dong, Roth, Su paper) of using the Edgeworth series approximation of the sum of independent random variables in order to get tighter error bounds.", "summary_of_the_review": "This may be a nice work, but the write-up leaves a lot unclear about its significance and novelty. ", "strength_and_weaknesses": "The problem studied by this paper - tight numeric bounds on the privacy parameters of differentially private algorithms - is an important one, and has received a lot of attention recently. The paper gives some evidence that Edgeworth series, applied to the f-differential privacy formalism, give some improvements in terms both of getting tighter bounds and of computational efficiency. \n\nThat said, I have the following concerns:\n* The paper claims computational complexity improvements, but leaves a lot unclear about this claim. \n    * Theoretically, what is the computational model in which the complexity of the algorithms is $O(m)$ for $m$-fold composition? Specifically, what assumptions are made with respect to how individual algorithms $M_i$ being composed are represented? The paper's supplement, when giving pseudocode for the algorithms, says things like \"Analytically encode all the corresponding PLLRs\". What does this mean? The authors should be precise about what kind of quantities/oracle access to $M_i$ is required, and how these assumptions correspond to the assumptions in prior work.\n    * No experimental evidence of better computational efficiency is presented, as far as I can tell. There is some evidence in the supplement of better numerical stability.\n\n* The experimental data presented leaves it unclear how significant the numerical improvements are. The experiments use some arbitrarily chosen (as far as I can tell) values of $\\delta$ and present bounds on $\\varepsilon$. The values of $\\delta$ chosen tend to be rather large: on the order 0.1 and 0.01 for 4 out of 6 plots. The two plots with lower value of $\\delta = 10^{-5}$ show that the improvement in the bounds on $\\varepsilon$ is rather small compared to the FFT based techniques. Even where the improvement is more significant in relative terms, it is still rather small in terms of the absolute value of $\\varepsilon$. \n\n* The paper is not always clear in terms of what is novel. See the next panel.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject