Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition

Thank you for the reply.

Our example with the Laplace mechanism simply shows that even a simple mechanism that has a worst-case pair of datasets might not have a worst-case pair of datasets under subsampling and composition.

I still don't fully understand why would one want to find the worst-case pair of datasets. I think it is clear that one has to consider a bound that holds for all pairs of datasets.

You are correct that Zhu et al. give a construction of a dominating pair of distributions in Corollary 32. However, there is no implementation of this construction to the best of our knowledge.

Such a construction can also be found in "Doroshenko et al. (2022). Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions. Proceedings on Privacy Enhancing Technologies." and it is a fairly simple algorithm. But I agree this should be addressed more thoroughly.

Regarding implementations of accountants for the subsampled Gaussian mechanism: the “PRV accountant”/Opacus (and PLD Accountant) only computes the “remove” relation. The “autodp” and Google DP library correctly computes both the “add” and “remove” relations and takes the point-wise maximum, as in Theorem 11 of Zhu et al.

That is an interesting observation (and perhaps someone should tell the authors), but I don't think these findings make a sufficient contribution for a paper.

As mentioned in our response to Reviewer LTUo we conjecture that in the case of the Gaussian mechanism, it is sufficient to consider the “remove” datasets for subsampling without replacement under the substitution relation.

I think proving this (even if it holds only for the Gaussian mechanism) would strengthen the paper.

The privacy parameters are not assumed to be identical. However, the privacy parameters are sometimes assumed to be close as is the case between the add/remove and substitution neighboring relations. We base this claim on the fact that accountants for Poisson subsampling are often used when it is not the implemented sampling scheme.

It indeed seems to be the case that the accountants for Poisson subsampling (with remove/add neighbourhood relation) are often used when they shouldn't be. And I think the same often happens in case of RDP accountants. Anyhow, I think the differences between neighbourhood relations and sampling schemes are correctly reflected in the results of Zhu et al. (2022). I think it would be interesting to see what are (as tight as possible) dominating pairs (either numerical or analytical) in various cases.

The RDP accountant computes the RDP guarantees of a single iteration for a given order and then applies the RDP composition theorem.

As far as I understand, the RDP accountants commonly compute the RDP guarantees for several orders and then convert the RDP-epsilons of different orders to approximate DP-guarantees using some conversion rule.

Due to the privacy scaling under the RDP composition theorem, it is sufficient to find the worst-case datasets for only a single iteration when using the RDP accountant. One could use a similar approach for hockey-stick divergence by computing a single (ε, δ)-DP guarantee and applying the advanced composition theorem. However, (ε, δ)-DP guarantees do not compose as well as the RDP guarantee. Therefore, the problem of determining the worst-case datasets under composition only seems to arise for exact accountants.

I don't exactly follow here. If we want to have an accurate RDP accountant, we would need to have RDP bounds for several RDP orders (the conversion in the end).

All in all I think the topic is actual and the subtleties of hockey stick vs. Rényi divergence based accountants haven't been fully addressed, but this paper does not really propose any solutions and also I think the criticism is not sharp enough to make for a paper.

Thank you for your thorough review.

The point a) was addressed by the work of Zhu et al. (2022)...

The intent of our example was not to show that some mechanisms do not have worst-case datasets. As you point out there are many such mechanisms. Our example with the Laplace mechanism simply shows that even a simple mechanism that has a worst-case pair of datasets might not have a worst-case pair of datasets under subsampling and composition. We will make this point more explicit in the paper. As for whether or not this is still a pitfall for privacy accountants please see our response below.

The correct bound for hockey-stick divergence in the case of subsampling without replacement and substitute neighbourhood relation of datasets is given in Proposition 30 by Zhu et al. (2022). So, as far as I see, this problem is solved, and in the most well-known software libraries that use numerical accounting and dominating pairs of distributions, namely the "autodp" by Wang et al. and "PRV accountant" by Gopi et al., Opacus and Google DP library, correct formulas are used.

Proposition 30 gives the upper bound of the hockey-stick divergence for a single iteration. However, it is not a dominating pair of distributions since the order of the pair differs between alpha below or above 1. In Section 7 we show that the pair of datasets considered in Proposition 30 is not sufficient to give tight bounds under composition for general mechanisms. You are correct that Zhu et al. give a construction of a dominating pair of distributions in Corollary 32. However, there is no implementation of this construction to the best of our knowledge. Regarding implementations of accountants for the subsampled Gaussian mechanism: the “PRV accountant”/Opacus (and PLD Accountant) only computes the “remove” relation. The “autodp” and Google DP library correctly computes both the “add” and “remove” relations and takes the point-wise maximum, as in Theorem 11 of Zhu et al. As mentioned in our response to Reviewer LTUo we conjecture that in the case of the Gaussian mechanism, it is sufficient to consider the “remove” datasets for subsampling without replacement under the substitution relation. However, we are not aware of any proof and therefore we disagree with the claim that this problem is solved.

...the claim that "Poisson subsampling is sometimes assumed to have similar privacy guarantees compared to sampling without replacement" is not true…

We agree that this claim is too strong as is and should be rephrased. The privacy parameters are not assumed to be identical. However, the privacy parameters are sometimes assumed to be close as is the case between the add/remove and substitution neighboring relations. We base this claim on the fact that accountants for Poisson subsampling are often used when it is not the implemented sampling scheme.

What is special about the hockey stick divergence…?

The RDP accountant computes the RDP guarantees of a single iteration for a given order and then applies the RDP composition theorem. Due to the privacy scaling under the RDP composition theorem, it is sufficient to find the worst-case datasets for only a single iteration when using the RDP accountant. One could use a similar approach for hockey-stick divergence by computing a single (ε, δ)-DP guarantee and applying the advanced composition theorem. However, (ε, δ)-DP guarantees do not compose as well as the RDP guarantee. Therefore, the problem of determining the worst-case datasets under composition only seems to arise for exact accountants.

Still getting back to this:

Due to the privacy scaling under the RDP composition theorem, it is sufficient to find the worst-case datasets for only a single iteration when using the RDP accountant. One could use a similar approach for hockey-stick divergence by computing a single (ε, δ)-DP guarantee and applying the advanced composition theorem. However, (ε, δ)-DP guarantees do not compose as well as the RDP guarantee. Therefore, the problem of determining the worst-case datasets under composition only seems to arise for exact accountants.

I believe that different RDP orders could have different worst-case pairs of datasets, similarly as you might not have a worst-case pair for the hockey-stick divergence. To get the benefit out of RDP accounting, one should keep track of several RDP orders. Often the dominating pairs of distributions are obtained by some post-processing (consider e.g. additive Laplace or Gaussian noise), and the resulting pair is a dominating pair for both Rényi and HS divergence, and often this pair is even tight in sense that it exactly gives the divergence of the mechanism evaluated on different dataset pairs (e.g., Gaussian mechanism). If we don't have a worst-case pair of datasets (consider, e.g., the exponential mechanism) but want to find tight bounds for a given divergence, I think one encounters difficulties both with Rényi and HS divergence based accounting.

(By the way, I would rather use the term numerical accounting than exact accounting when talking about the HS divergence based approach.)

even a simple mechanism that has a worst-case pair of datasets might not have a worst-case pair of datasets under subsampling and composition.

Thinking about this, I believe that the same pair of datasets would be the worst-case pair for compositions as well as for a single call of the mechanism (at least for non-adaptive compositions, I don't think we can expect to find worst-case pairs of datasets for adaptive compositions in general). For subsampling, again, the possible difficulties when trying to find the worst-case dataset pairs would be shared by other accounting methods such as the RDP, I think.

I also share the criticism with reviewer dGjF in that Figure 1 should not be used as a proof (Proposition 11). I also think that the example with Laplace noise is a bit difficult to follow, some more formal derivation e.g. in the appendix would have helped (I suppose that could be even dealt analytically).

I think the paper has some interesting points, but still needs more work. Some constructive results would definitely strengthen the paper.

Ps. it seems that the worst-case data set in that Laplace example dominates for $\varepsilon \geq 0$ whereas there should be dominance for all $\varepsilon \in \mathbb{R}$ for using the composition result.

Thank you for the helpful feedback on writing and presentation. We will make several minor edits to address typos and unclear exposition, and we will improve the rigor based on your suggestions. For Proposition 9 we will include a reference for the dominating pair of the Gaussian mechanism (Balle and Wang, https://arxiv.org/pdf/1805.06530.pdf). For Proposition 11 we will include exact calculations for two points on the center plot which is sufficient for the proof of the counter-example. We will rephrase parts of Section 7 and redesign Figure 3 to improve presentation.

We thank the reviewers for their feedback.

While constructing the bad cases on lower dimensional datasets is sufficient to demonstrate the claims, it would be nice to include empirical results on more realistic datasets to show that these pitfalls can actually appear in practice.

We agree that understanding the privacy loss for actual datasets is an important problem. It would be interesting to e.g. examine how privacy auditing techniques for DP-SGD are affected by various sampling schemes using standard benchmark datasets. It is unlikely that the gradients resemble the worst-case datasets for sampling without replacement in all iterations. That is, all gradients have maximum length and the same direction. It is also unlikely that they resemble the worst-case datasets for Poisson subsampling where all but one datapoint is the zero vector. As such, it is not immediately clear how the sampling schemes compare empirically. However, we consider this a separate problem from tight privacy accounting.

The authors did not provide a viable technical solution for dealing with the worst-case dataset problem under replacement DP + For replacement DP, is there a good way to find a good approximation of privacy curves when the exact worst-case dataset is hard to obtain?

Determining the worst-case dataset under replacement is a difficult problem in general as we show in Section 7. The technique by Zhu et al. can be used to construct a dominating pair of distributions. See the review and response to Reviewer G1qb for more details. Under subsampling without replacement without composition, the privacy curve of the Gaussian and Laplace mechanisms is the same under the substitution neighborhood as under the remove relation for $\varepsilon \geq 0$. As we show in Sections 5 and 7, that is not the case under composition for the Laplace mechanism. We conjecture that the curve under the substitution and remove relations matches under composition for the Gaussian mechanism. Proving or disproving this is a direction for future work. Nonetheless, the goal of Section 7 is to highlight that accounting for worst-case datasets under substitution is unsolved and that care should be taken when using numerical accounting under the substitution neighboring relation.

Thank you for your review.

I am concerned that the paper presents somewhat of a straw-man (e.g. the two points of 'common' confusion in the abstract). It would be useful to provide evidence (even something anecdotal ) that these are common pitfalls in practice. This would make the overall contribution of the paper much more convincing.

When writing the paper, we made a deliberate decision to minimize drawing attention to existing errors, though we understand how this treatment can risk presenting a straw-man. There are multiple examples of papers that perform privacy accounting for Poisson subsampling when it does not match the implementation. Anecdotally, we can refer the reviewers to page 23 of (De et al., https://arxiv.org/pdf/2204.13650.pdf): “As a minor technical note, we remark that this accountant assumes that at each iteration mini-batches are sampled with replacement from the entire dataset by including every training example with probability 𝑞, while in practice we sample mini-batches using a random shuffling scheme, such that each example is sampled once per training epoch.” Poisson subsampling is computationally inefficient for large datasets and therefore the implementation might instead perform subsampling without replacement or shuffling. We do not want to call out otherwise good works like this in the main body of our paper. We focus on cautioning that such technicalities can in fact lead to large accounting errors. Regarding the pitfall about privacy accountants please see our response to Reviewer G1qb for more details and examples.

The two recommendations for practitioners in the discussion section are welcome but I believe spelling out the implications of this work for practitioners (who will not read through the theory in detail) merits an entire section of the paper, and would enhance its practical utility and potential impact.

We will expand on implications for practitioners as suggested.

It would be interesting to understand whether empirical privacy (e.g. measured via auditing/MIA) of Poisson subsampling and sampling with replacement differs as much as the theoretical analysis implies (e.g. epsilon =1 vs 10!). Do you have priors about this?

Please see our response to Reviewer LTUo.