Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies an interesting problem --- obtaining arbitrary tight privacy guarantees of composed mechanisms efficiently. On the one hand, the known efficient RDP-based moments accountant (O(1) computational time) cannot achieve an arbitrary accuracy. On the other hand, the Fast Fourier Transform (FFT) based approach provides explicit error bounds, but the computational complexity is O( k^1.5), where k is the number of compositions. 
The paper provides an improved analysis for computing the privacy curve of the composition and saves a factor of k in the run time and memory. 

main_review: Weak points. 

The main results are quite limited delta with respect to previous work. Given that the paper's major contribution is to *speed up the privacy computation* for PLD-based accountants, I think this paper is marginally above the acceptance threshold despite its interesting viewpoint in the error analysis. 

Strong points.

1. Compared to the prior work [KJPH21], the proposed algorithm shifts the discretized random variables and improves the approximation procedue using the coupling approximation.

2. They provide a tighter tail bound of the privacy loss random variables, which improves the truncation procedure and enables a wide choice on the mesh size ($1/\sqrt(k)$) compared to ($1/k$) in [KJPH21]. 
 

Question:

Does the paper support heterogeneous composition as that in [KH21]?

Minor comments:
The authors can improve the clarity by removing words like *in an influential paper* and *in an important paper*. 

limitations_and_societal_impact: The potential negative societal impact is not applicable here.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper considers an important problem of computing the total privacy loss under composition. Since computing the exact (and optimal) privacy loss is computationally infeasible under complexity-theoretic assumptions, the paper computes an approximation. 
main_review: Except for spotting some typos (like trucation instead of truncation on page 19), I do not have any complaints about the paper. I only have positive feedback about the paper and I will note it down for the latter stages:
1. The paper studies a very important problem of computing an approximation to privacy loss under composition. 
2. The paper is very well written, the proof is elegant and easy to follow. 
3. The algorithm is very efficient (not just theoretically, but even practically). 
4. The current submission can be easily plugged in any large-scale deployment. I stressed tested the algorithm and it performed really well. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper studies numerical composition of DP from a computation complexity perspective. Previous FFT based algorithm is optimized in its selection of discretization grid and truncation threshold. The runtime is significantly improved from $k^{1.5}$ to $k^{0.5}$. It also show that the CLT approach can underreport $\varepsilon$ for very small $\delta$.
main_review: Although the algorithm is basically the same as the previous work, the improvement brought by the correct selection of discretization grid and truncation threshold is very remarkable. This shows the exciting potential of the FFT type accountant.

The concept of coupling approximation used in the analysis also seems interesting.

I'd like to point out something that complements the knowledge. In this paper, Definition 3.1 and the claim below gives a clear picture about what (pair of) densities can be PRVs, but since the so-called privacy curve is a more fundamental object (indeed, the whole paper is about computing an operation of this object), it would be great if there is a clear picture about the privacy curve. This appears in the following paper

> Zhu, Yuqing, Jinshuo Dong, and Yu-Xiang Wang. "Optimal Accounting of Differential Privacy via Characteristic Function."

In the same spirit, from the claim below Definition 3.1, it seems one of the two densities determines the other. This seems worth a serious statement, and I wonder if we can pick a simpler object to work on. It's also not clear to me what privacy curve guarantees density and what privacy curve guarantees discrete probability masses. Is there no privacy curve that we ever imagine to design that has non-discrete PRVs but also no density?

Regarding the writing, for the ease of the most general audience, I think including the runtime plot would be very helpful. Due to the page limit, Section 5 may have to be reduced. I understand how exciting it is to see theoretical ideas lead to practical improvements and the authors would like to tell us why, but I guess by human nature, a plot is more informative.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The proposes a refined numerical method for (eps,delta)-differential privacy accounting. The method is based on that of [KJPH21]: the discrete privacy random variable (PRV) is formed by using the CDF of the true PRV and then normalised. By then using concentration inequalities, the error analysis is simplified (compared to [KJPH21]) which also leads to tighter bounds that enable choosing smaller parameter values for the algorithm. This improved error analysis also leads to improvement of the theoretical complexity bound (this is also considerably lower than the one given by Murtagh and Vadhan (2016)).
main_review: All in all I think this is a very nice addition to this line of research, and I am leaning towards accepting the paper. I do have some comments and criticism, in more detail below. I am ready to reconsider my score based on authors' response.

Pros:

- The paper completes the previously proposed numerical method: The idea of normalising the truncated distributions and resorting to tail bounds in the error analysis (the way it is done) feels like the right way to do the error analysis. It is difficult to imagine major improvements to the discretisation procedure and to the overall complexity bounds. The complexity bound is considerably  better than the result given by Murtagh and Vadhan (2016).

- The paper seems well written and the presentation of the error analysis elegant.

Cons:

- The nature of the contribution is slightly incremental when considering the existing numerical method by [KJPH21]: the novelties lie mainly in the discretisation of the privacy loss random variable and in the error analysis of the resulting approximation. 

- The experiments: The 'competing method' is obviously that of [KJPH21]. However, the chosen experimental comparisons (e.g. Figure 1a, Figure 3) seem to be chosen such that the method of [KJPH21] is not yet converging properly, and therefore do not seem to tell the whole truth. The method of [KJPH21] in a sense already 'does the job' by giving accurate tight bounds in affordable runtimes (compute times orders of seconds). E.g. in Figure 3b, I would expect the method of [KJPH21] to give tighter bounds (quickly) when decreasing the discretisation parameter h from the reported $8 \cdot 10^{-4}$ to $1 \cdot 10^{-5}$. 


Questions and Remarks:

- Could you explain where does the assumption "$| Y_i - \widetilde{Y}_i | \leq_0 h$" in Lemma 5.3 come from? I would imagine there is always some gap due to the normalisation carried out for the truncated distribution so that for small enough $h$, $Y_i$ and $\widetilde{Y}_i$ would actually differ with a positive probability. Unless the discretisation interval contains the whole of $Y$, due to the normalisation $Y_i$ and $\widetilde{Y}_i$ would always differ.

- To make everything rigorous, should you not consider discretisation at the points $\{i \cdot h\}$, $-n \leq i < n$ instead of $-n \leq i \leq n$, due to the periodisation ?

- How is the PRV evaluated for the subsampled Gaussian mechanism exactly? Looking at the discretisation algorithm, you use the CDF at ih - h/2 and at ih + h/2 to obtain the point mass.  So you numerically integrate the CDFs in high precision using the analytic formula for the PRV? How do you ensure that the integration error stays very small e.g. for the PRV of the subsampled Gaussian mechanism?

- Can you get the FFT evaluations down to order of tens of milliseconds with reasonable accuracy? Unless that is the case, the gains from the computational speed up might be limited in practice.

- Remark about the runtime experiments: using those parameter values ($\sigma=0.8$, $p=4 \cdot 10^{-3}$, $\varepsilon=1.5$), the $\delta$ goes up to ~ $3 \cdot 10^{-5}$ for $k=2000$, and up to ~0.02 for $k=10^4$, so I would say that for up to $k=10^4$ it is less typical DP-SGD training (unless very small amount of data, $\delta$ should be less than $1/N$, $N$ number of samples).

limitations_and_societal_impact: Yes, relation to the other accounting methods is discussed. This is mostly a theory paper.
review_title: null

Meta-review: The reviewers felt that, although the algorithm in this paper is very similar to previous work, the modifications feel like the "right" way to solve the problem, and the improvements are significant for an important problem. The reviewers agreed that this paper should be accepted as a spotlight.
Decision: Accept (Spotlight)