Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

I 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. 
clarity,_quality,_novelty_and_reproducibility: The paper is well written, quality is high. I did not verify the reproducibility of the paper.
summary_of_the_review: Please see above.

For 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

The 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. 

The 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. 
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.

The 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.

Nitpick: 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. 
clarity,_quality,_novelty_and_reproducibility: The quality, novelty, and reproducibility of the paper are all high. As mentioned before, the ideas in the paper are all "natural in retrospect" but at the same time a great deal of technical effort is needed for the main results in the paper. Also, the Edgeworth accountant obtains several novel guarantees both qualitatively and quantitatively improving over past work. 

As mentioned before, the authors do a good job explaining the concepts in the paper such that the main ideas are "natural in retrospect", so in that sense the paper is mostly clear. However, to someone without the appropriate background reading through the technical discussions that solidify these ideas may be difficult.
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
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. 

That said, I have the following concerns:
* The paper claims computational complexity improvements, but leaves a lot unclear about this claim. 
    * 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.
    * 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.

* 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$. 

* The paper is not always clear in terms of what is novel. See the next panel.
clarity,_quality,_novelty_and_reproducibility: As mentioned, the paper is unclear about how individual algorithms being composed need to be represented. I guess one can try to trace that from the various bounds and statements, but it would be much more convenient for the reader to provide this information up front.

In terms of novelty, I am not sure how novel two of the main results are: Proposition 3.2 and, especially, Lemma 4.3. 

* Proposition 3.2 is similar in spirit to the approach in the Dong, Roth, and Su GDP paper. Is there a new idea here that did not appear in their paper, or is Proposition 3.2 a nice, user-friendly restatement of their approach?

* Lemma 4.3, which is crucial for the "finite sample" bounds, appears identical to Theorem 2.1 in https://arxiv.org/abs/2101.05780. The paper says "we follow the analysis on the finite-sample bound in Derumigny et al. (2021)" which does not clarify whether they are just restating their result (in which case, why is a proof included in the appendix?) or whether they had to modify the Derumigny et al. analysis. If they had to modify it, then why and how?

summary_of_the_review: This may be a nice work, but the write-up leaves a lot unclear about its significance and novelty.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

Weakness: 

W1. The trade-off of EA vs. FFT and RDP are not clear. 

(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. 

(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. 

(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.

(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?

W2. Unclear contributions. 

It 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.

W3. Issues with experimental settings and results.

(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. 

(2) In Figure 3, why do we decrease the sampling probability p while increasing m?

(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.

(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?

(5) Please provide a figure for subsampling rate p=1 in the numerical experiments.

W4. How EA performs in their target applications, noisy-SGD and Federated Analytics, is unclear.

(1) No setting in the experiment section considers noisy-SGD. 

(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. 

W5. 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?
clarity,_quality,_novelty_and_reproducibility: 1. Clarity can be improved. The current draft is not self-contained, and is heavy in notation and lack of transition. There are also some concepts that require more detailed explanations, e.g., f-DP and edgeworth approximation. The settings for numerical experiments also need more details.

2. Quality regarding experiments can be improved. See details above

3. Novelty is unclear. Maybe better writing could clarify this issue. 

4. Reproducibility seems okay. But numerical stability for their implementation is not discussed.
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: 

(1) The trade-off of EA v.s. FFT and RDP are not clear

(2) Experimental settings and results

(3) How EA performs in its target applications is not clear
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a new accounting method for DP composition. Accurate composition accounting is central for DP analysis of ML training methods and this paper presents a more computationally efficient approach way to perform accounting. This is a promising work, but, as pointed out in the review of kz4w, the computational efficiency and underlying assumptions are not discussed with sufficient detail and clarity for the paper to be accepted at this stage.
justification_for_why_not_higher_score: Overall no enthusiasm and some serious concerns from an expert.
Decision: Reject