Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition

We appreciate the reviewer agreeing that the findings are interesting. We respectfully disagree that the findings may be too niche or specialized, or too "narrow [in] scope" for highlighting at a conference like NeurIPS. As just one example, the concurrent work ``How Private are DP-SGD Implementations?'' by Chua et al. focuses precisely on issues related to discrepancies between DP-SGD implementations and accounting techniques. Their work could be similarly criticized as being narrow in scope or niche. However, this paper was not only accepted to ICML 2024, but awarded an oral presentation (only 6% of accepted papers), recognizing it as one of the papers most deserving of highlighting to the community. Our work is thematically quite similar in focus to theirs. And while the reviewer claims that the results are not surprising or novel, we again respectfully disagree. Indeed, similar to almost all work in the field, we build upon prior contributions. It appears that the reviewer may have substantial technical expertise with prior contributions, and thus some of the arguments we employ may seem more natural to them.

In summary, we believe the reviewer (at a minimum) agrees with us that the paper highlights and demonstrates interesting, important, and practically-relevant phenomena that are still a common pitfall for practitioners. Is this not sufficient for a NeurIPS paper? Below, we address and clarify on many of the interesting and insightful questions raised by the reviewer. It seems like the primary negativity in the reviewer's evaluation is based on whether this paper "feels" like a NeurIPS paper. We hope the reviewer reconsiders their feelings here, given the fact that NeurIPS is a "big tent" community and in light of the recognition for the thematically-similar paper of Chua et al.

Furthermore, thank you for your suggestions. We will make edits to improve clarity. Below we address a couple of specific points in more detail.

In Figure 2, just because the mechanisms satisfy the same delta and epsilon, this does not make them identical or even comparable in general (they are only "identical" if they have equal privacy curves or trade-off functions). The figure seems to rely in a sense on the mechanisms being otherwise identical. Is there a limitation which needs addressing here?

Table 1 does address this limitation in the sense that it demonstrates the same discrepancy even as $\delta$ is permitted to vary by several orders of magnitude.

The Gopi accountant is known to break for low delta. Did you encounter any problems for delta 1e-7? Is there any chance the results could be spurious for low delta values?

For Figure 2 we used the Opacus accountant, which to our knowledge does not have this issue. In any case, the reported issues for the Gopi accountant seem to emerge for much smaller values (e.g. $10^{-14}$). Still, the reviewer is correct that we cannot rule out the existence of a bug in the Opacus implementation. In our research we ran similar experiments with different accountants including implementations based on RDP and found a similar gap between Poisson and WOR. We will add a short note to the paper.

In particular, the supposed "limitation" is --by the authors' own admission-- easily resolved by just running the accountant on the two curves separately and taking the supremum.

It is true that the issue can be easily resolved in the context of the add/remove neighboring relation but the problem becomes significantly murkier under the substitution relation (as in Section 7). In that case, the number of worst-case datasets scales with the number of compositions. On the other hand, an accountant that "smooths over" worst-case datasets may be unnecessarily lossy (as in Section D). Therefore, there is an accuracy and computational motivation to settle the issue of worst-case datasets under the substitution relation. Resolving the conjecture for the add/remove relation will lead to a solution for the substitution relation. Our paper is unclear on this point and we will rephrase to emphasize it.

No viable technical solutions are provided for the identified issues, which might be a difficult research problem.

As the reviewer suggests, this is indeed a very difficult research direction, which we have invested substantial time and effort into. The main intention of our work is to draw theorist and practitioner attention to these issues, and clearly and crisply state reasonable technical conjectures for the community to coalesce around and attack. Traditionally, having clear and well-defined technical problems and conjectures has spurred mathematical advancements and progress. We consider these issues to be of great enough practical importance that we urge the community to work on these problems with us in parallel.

In the equation between lines 133 and 134 (and in the rest of the article), where did the maximum with 0 go?

This is a typo. Thank you for pointing it out!

There are some typos

If the reviewer could point out specific typos that they noticed that would be highly appreciated.

...the result for the gap is shown empirically. I have to state that I have not seen the Appendix so if the authors have a provable guarantee for this gap in the Appendix, please point me that. To me, the selling point of the paper is this result and it should be placed front and center. Most of the results that are given in the form of propositions and lemma are from previous works.

We show the result for the gap both empirically and theoretically. As a convention, we present results from previous work as theorems and our results as lemmas and propositions. We will make this convention explicit in the paper. The proofs of all propositions are in the Appendix. Proposition 9 shows that noise with twice the magnitude is required under WOR when compared to Poisson. The proof of Proposition 9 is in Appendix A.

Note that this gap does not follow from the result of Zhu et al. They give dominating pairs of distributions for upper bounding the privacy parameters. We show that the bounds are tight for both Poisson and WOR in the case of the subsampled Laplace/Gaussian. It is likely not very surprising to privacy accounting experts that the distributions are tight for DP-SGD, but it is not true for all mechanisms.

Is there a provable gap between the composition of WoR and Poisson subsampling?

Yes, please again refer to Appendix A for the details.

There are no issues with the correctness of the results questioned by the reviewer. We discuss the technical details of Proposition 9 below.

You introduce the notion of dominating pairs of distributions, but then you talk about dominating datasets. You need to clarify the relation. Specifically in Proposition 9, I don't understand what a dominating dataset means.

By dominating datasets we mean a pair of datasets that induce a dominating pair of distributions when the mechanism is applied to them. The distinction is important for our results. We have been unclear about this point so thank you for mentioning it. We will update the text to clarify.

Proposition 9 looks incorrect to me. In case of $b=n$ and $\lambda=1$, the dominating pairs should collide, but this proposition suggests otherwise.

We assume that $\lambda$ refers to the Poisson subsampling rate, which we call $\gamma$. The dominating pairs will not collide in this case due to the fact that sampling without replacement involves a fixed batch size and we are considering the add/remove relation. Therefore the sampling rate differs between neighboring datasets. Taking $n$ to be the size of the larger dataset, the largest value we can choose for $b$ is $n-1$, the size of the smaller dataset. Taking $b = n-1$ leads to a rate for sampling without replacement of $(n-1)/n$, so for a direct comparison we should consider $\gamma = (n-1)/n$ for Poisson as well instead of $\gamma = 1$.

Note that it is not an artifact of the choice that $n$ refers to the size of the larger dataset. If we refer to the size of the smaller dataset as $n$ such that $b = n$ is valid we see a similar difference. But the comparison is not as clean with this choice because we would use $2n/(n+1)$ times as much noise.

You say: "Crucially, Proposition 9 implies that under the add and remove relations, we must add noise with twice the magnitude when sampling without replacement compared to Poisson subsampling!". This doesn't sound correct. Again, if you set the sampling rate to 1, then the two mechanisms collide. Am I missing something?

For the settings of $b$ and $\gamma$ we just described, the dominating pair we obtain for Poisson subsampling is $\mathcal{N}(0, \sigma^2)$ vs. $\frac{1}{n}\mathcal{N}(0, \sigma^2) + \frac{n-1}{n}\mathcal{N}(1, \sigma^2)$. For sampling without replacement we get $\mathcal{N}(-b, \sigma^2)$ vs. $\frac{1}{n}\mathcal{N}(-b, \sigma^2) + \frac{n-1}{n}\mathcal{N}(-(b - 1) + 1, \sigma^2)$. Due to the translational properties of the normal distribution, this is equivalent to $\mathcal{N}(0, \sigma^2)$ vs. $\frac{1}{n}\mathcal{N}(0, \sigma^2) + \frac{n-1}{n}\mathcal{N}(2, \sigma^2)$. Thus we need twice as much noise under WOR.

For the results of section 6, are you using the worst-case datasets of Proposition 9 to calculate the privacy curve?

Yes.

What prevents you from choosing the neighboring datasets to be $D=(0,...,0,0) ~~ {and} ~~ D’=(0,...,0,100)$?

Please see the paragraph beginning at l.90. In our work we consider mechanisms over a bounded domain. We restrict to the domain [-1, 1], without loss of generality. Without a bounded domain (or, equivalently, some sort of clipping), as the instance the reviewer highlights exemplifies, the sensitivity may be arbitrarily large and no non-trivial results are at all possible for the Laplace or Gaussian Mechanism. Note, in particular, that the Subsampled Gaussian Mechanism, which forms the basis of DPSGD, employs clipping for precisely this reason.

Now I think you are actually making this mistake in your proposition 9. Your neighboring datasets for the case of poisson sampling has sensitivity of 1.0, while your neighboring dataset for the case of sampling with replacement has sensitivity 2.0

First, we maintain that Proposition 9 is correct. The proof (in Appendix A) is rather succinct (~half a page), and if the reviewer can identify any specific technical issue in the proof, we would be willing to reconsider our position.

That said, the reviewer has highlighted one of the most surprising and counterintuitive results in our work! Indeed, it certainly "feels" like the datasets D1 = (-1, ..., -1) and D1' = (-1, ..., -1, 1) ought to be "worse" than D2 = (0, ..., 0) and D2' = (0, ..., 0, 1). Indeed, this is correct for WOR: as the reviewer points out, including the 1 will make a bigger difference if it displaces a -1 (when the difference is 2) rather than if it displaces a 0 (when the difference is 1).

However, quite surprisingly, the same does not hold for Poisson! We give an informal argument of why that is here. In case 1 (with -1's), we could achieve a particular sum because the underlying dataset is D1 and a -1 is not sampled (which increases the sum by 1), or because the underlying dataset is D1' and the +1 is sampled (which increases the sum by 1). The same confusion can not occur for D2 and D2', since for D2 the sum is always fixed to be 0, and in D2' the sum is 1 with probability $\gamma$. That is, there is no event under D2 that "looks like" a 1 has been included, whereas there is for D1 (where a -1 is excluded).

Of course, the discussion above is not a precise argument. However, the rigorous technical details are present in Appendix A of our paper and appeal to Theorem 10.

The example I gave is actually a good way to see why your result isn’t meaningful. Even if we consider the sampling rate to be (n-1)/n (I don’t know why you are doing this but it’s ok), the two mechanisms will collide as n approaches to infinity.

We remind that we considered the sampling rate of (n-1)/n because this is the closest possible case to the $\gamma = 1$ case suggested by the reviewer (due to the discrepant size of the datasets). We also comment that the two mechanisms would in fact not collide, either with the same pair of datasets (though this can be shown directly via a sophisticated argument regarding the rather complex mixtures induced by the Poisson sampling on the -1's dataset, the easiest way to see it is by observing that it would contradict our proof which does not have any issues) or the pairs of datasets that we define in Proposition 9 (as demonstrated in our initial rebuttal, please refer to it above).