Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:03:07

Abstract: We consider the problem of computing tight privacy guarantees for the composition of subsampled differentially private mechanisms. Recent algorithms can numerically compute the privacy parameters to arbitrary precision but must be carefully applied.

Our main contribution is to address two common points of confusion. First, some privacy accountants assume that the privacy guarantees for the composition of a subsampled mechanism are determined by self-composing the worst-case datasets for the uncomposed mechanism. We show that this is not true in general. Second, Poisson subsampling is sometimes assumed to have similar privacy guarantees compared to sampling without replacement. We show that the privacy guarantees may in fact differ significantly between the two sampling schemes. In particular, we give an example of hyperparameters that result in $\varepsilon \approx 1$ for Poisson subsampling and $\varepsilon > 10$ for sampling without replacement. This occurs for some parameters that could realistically be chosen for DP-SGD.

Main paper: 
 introduction: 
 One of the fundamental properties of differential privacy is that composing multiple differentially private mechanisms to construct a new mechanism still satisfies differential privacy. This property allows us to design complicated mechanisms with strong formal privacy guarantees such as differentially private stochastic gradient descent (DP-SGD, Song et al. (2013) ; Bassily et al. (2014) ; Abadi et al. (2016) ).The privacy guarantees of a mechanism inevitably deteriorate with the number of compositions. Accurately quantifying the privacy parameters under composition is highly non-trivial and is an important area within the field of differential privacy. A common approach is to find the privacy parameters for each part of a mechanism and apply a composition theorem (Dwork et al., 2010; Kairouz et al., 2015) to find the privacy parameters of the full mechanism. In recent years, several alternatives to the traditional definition of differential privacy with cleaner results for composition have gained popularity (see, e.g., Dwork and Rothblum (2016) ; Bun and Steinke (2016) ; Mironov (2017) ; Dong et al. (2019) ).Another important concept is privacy amplification by subsampling (see, e.g., Balle et al. (2018) ; Steinke (2022) ). The general idea is to improve privacy guarantees by only using a randomly sampled subset of the full dataset as input to a mechanism. In this work we consider the problem of computing tight privacy parameters for subsampled mechanisms under composition.One of the primary motivations for studying privacy accounting of subsampled mechanisms is DP-SGD. DP-SGD achieves privacy by clipping gradients and adding appropriate Gaussian noise to each batch. As such, we can find the privacy parameters by analyzing the subsampled Gaussian mechanism under composition. One of the key contributions of Abadi et al. (2016) was the moments accountant which gives tighter bounds for the mechanism than the generic composition theorems. Later work improved the accountant by giving improved bounds on the Renyi Differential Privacy guarantees of the subsampled Gaussian mechanism under both Poisson subsampling and sampling without replacement (Mironov et al., 2019; Wang et al., 2020) .Even small constant factors in an (ε, δ)-DP budget are important. First, from the definition, such constant factors manifest exponentially in the privacy guarantee. Furthermore, when training a model privately with DP-SGD, it has been observed that they can lead to significant differences in the downstream utility, see, e.g., Figure 1 of De et al. (2022) . Consequently, "saving" such a factor in the value of ε through tighter analysis can be very valuable. This has motivated a recent line of work on numerically estimating the privacy parameters (Sommer et al., 2019; Koskela et al., 2020; 2021; Gopi et al., 2021; Zhu et al., 2022) .Most privacy accounting techniques for DP-SGD assume a version of the algorithm that employs amplification by Poisson subsampling. That is, the batch for each iteration is formed by including each point independently with sampling probability γ. Other privacy accountants consider a variant where random batches of a fixed size are selected for each step. Note that both of these are inconsistent with the standard method in the non-private setting, where batches are formed by randomly permuting and then partitioning the dataset. Indeed, the latter approach is much more efficient, and highly-optimized in most libraries. Consequently, many works in private ML implement a method with the conventional shuffle-and-partition method of batch formation, but employ privacy accountants that assume some other method of sampling batches. The hope is that small modifications of this sort would have negligible impact on the privacy analysis, thus justifying privacy accountants for a setting which is technically not matching.The central aim of our paper is to clarify some common problems with privacy accounting in order to facilitate more faithful comparisons between DP-SGD algorithms. We organize our paper as follows.• In Sections 4 and 5, we establish that the datasets used to compute the privacy guarantees of typical subsampled mechanism do not in general give the correct result when the mechanism is composed multiple times. Some popular privacy accountants assume otherwise, which is an error that can be corrected easily. • In Section 6, we show that rigorous privacy accounting is significantly affected by the method of sampling batches. This results in sizeable differences in the resulting privacy guarantees for settings which were previously treated as interchangeable by prior works. Consequently, we demonstrate the invalidity of the common practice of using one method of batch sampling and employing the privacy accountant for another. • Lastly, in Section 7, we discuss issues that arise in tight privacy accounting under the substitution relation. It is known for the add/remove relation that the privacy guarantees are determined by just one of two pairs of datasets. We show that this is unfortunately not the case in general under the substitution relation. 
preliminaries: 
 Differential privacy is a rigorous privacy framework introduced by Dwork et al. (2006) . Differential privacy is a restriction on how much the output distribution of a mechanism can change between any pair of datasets that differ only in a single individual. Such datasets are called neighboring, and we denote a pair of neighboring datasets as D ∼ D . We formally define neighboring datasets below. Definition 1 ((ε, δ)-Differential Privacy). A randomized mechanism M satisfies (ε, δ)-DP under neighboring relation ∼ if for all D ∼ D and all measurable sets of outputs Z we havePr[M(D) ∈ Z] ≤ e ε Pr[M(D ) ∈ Z] + δ.In this work, we consider datasets where each datapoint is a single-dimensional real value in the interval [-1, 1] . The mechanisms we consider apply more generally to multi-dimensional realvalued queries, and the pitfalls we highlight in this work are present for such input as well. We focus on single-dimensional inputs for simplicity of presentation. Likewise, any mechanism we define on [-1, 1] can be extended to all of R by clipping to the range [-1, 1]. After the appropriate rescaling, this is equivalent to the mechanisms used in practice for tasks including differentially private stochastic gradient descent.On the domain [-1, 1] * , we define the neighboring definitions of add, remove, and substitution (replacement). We typically want the neighboring relation to be symmetric, which is why add and remove are typically included in a single definition. + ε R , e ε A δ R + δ A )-DP under substitution because Pr[M(D) ∈ Z] ≤ e ε R Pr[M(D ) ∈ Z] + δ R ≤ e ε A +ε R Pr[M(D ) ∈ Z] + e ε A δ R + δ A .Definition 1 can be restated in terms of the hockey-stick divergence: Definition 3 (Hockey-stick Divergence). For any α ≥ 0 the hockey-stick divergence between distributions P and Q isH α (P ||Q) := E y∼Q dP dQ (y) -α + = P (S α ) -αQ(S α ),where dP dQ is the Radon-Nikodym derivative and S α = {y| dP dQ (y) ≥ α}.Specifically, a randomized mechanism M satisfies (ε, δ)-differential privacy if and only if The full range of privacy guarantees for a mechanism can be captured by the privacy curve. Definition 4 (Privacy Curves). The privacy curve of a randomized mechanism M under neighboring relation ∼ is the functionEQUATIONδ ∼ M : R → [0, 1] given by δ ∼ M (ε) := min{δ ∈ [0, 1] : M is (ε, δ)-DP}. If there is a single pair of neighboring datasets D ∼ D such that δ ∼ M (ε) = H e ε (M(D)||M(D )) for all ε ∈ R, we say that the privacy curve of M under ∼ is realized by the worst-case dataset pair (D, D ).Unfortunately, a worst-case dataset pair does not always exist. A broader tool that is now frequently used in the computation of privacy curves is the privacy loss distribution (PLD) formalism (Dwork and Rothblum, 2016; Sommer et al., 2019) . Definition 5 (Privacy Loss Distribution). Given a mechanism M and a pair of neighboring datasets D ∼ D , the privacy loss distribution of M with respect to (D, D ) isL M (D||D ) := ln(dM(D)/dM(D )) * M(D), i.e. ln( dM(D) dM(D ) (y)) ∼ L M (D||D ) when y ∼ M(D).An important caveat is that the privacy loss distribution is defined with respect to a specific pair of datasets, whereas the privacy curve implicitly involves taking a maximum over all neighboring pairs of datasets. Nonetheless, the PLD formalism can be used to recover the hockey-stick divergence viaH e ε (M(D)||M(D )) = E Y ∼L M (D||D ) [1 -e ε-Y ],from which we can reconstruct the privacy curve asδ ∼ M (ε) = max D∼D E Y ∼L M (D||D ) [1 -e ε-Y ].Lastly, we define the two subsampling procedures we consider in this work: sampling without replacement and Poisson sampling. Given a dataset D = (x 1 , . . . , x n ) and a set I ⊆ {1, . . . , n}, we denote byD| I := (x i1 , . . . , x i b ) the restriction of D to I = {i 1 , . . . , i b }. Definition 6 (Subsampling). Let M take datasets of size 1 b ≥ 1. The n b -subsampled mechanism M W OR is defined on datasets of size n ≥ b as M W OR (D) := M(D| I ),where I is a uniform random b-subset of {1, . . . , n}.On the other hand, given a mechanism M taking datasets of any size, the γ-subsampled mechanism M P oisson is defined on datasets of arbitrary size asM P oisson (D) := M(D| I ),where I includes each element of {1, . . . , |D|} independently with probability γ.D ∼ R D such that δ ∼ R M W OR is realized by (D, D ) and δ ∼ A M W OR is realized by (D , D).Our worst-case datasets can be found by reduction to one of the main results of Zhu et al. (2022) .Theorem 10 (Theorem 11 of Zhu et al. (2022) ). Let M be a randomized mechanism, let M P be the γ-subsampled version of the mechanism, and let M W OR be the n b -subsampled version of the mechanism on datasets of size n and n -1 with γ = b/n.1. If (P, Q) dominates M for add neighbors then (P, (1 -γ)P + Q) dominates M P oisson for add neighbors and ((1 -γ)P + Q, P ) dominates M P oisson for removal neighbors.2. If (P, Q) dominates M for substitute neighbors then (P, (1-γ)P +Q) dominates M W OR for add neighbors and ((1 -γ)P + Q, P ) dominates M W OR for removal neighbors.We sketch below the proof of Proposition 9. We also note that the proposition can also be proved for the Laplace mechanism by an identical argument where noise from the Laplace distribution replaces Gaussian noise.By symmetry, we will focus the proof sketch on the add neighboring relation. Now, from Theorem 10 we know that (N (0, σ 2 ), (1 -γ)N (0, σ 2 ) + γN (1, σ 2 )) dominates M P oisson and (N (0, σ 2 ), (1 -γ)N (0, σ 2 ) + γN (2, σ 2 )) dominates M W OR . We know that the dominating pair is tight if there exists a pair of neighboring datasets for which the hockey-stick divergence matches the dominating pair for all α. We can easily show that such inputs exist. Say that D i is the element in D that is not in D. The case of Poisson subsampling is simple. We set all elements in D to 0 and set D i = 1. Then M P oisson (D ) is centered around 1 if D i is included in the batch and 0 otherwise. That is, the distribution matches the dominating pair.The worst-case datasets are similar although slightly different for M W OR . We still set D i = 1 but now we set all elements of D to -1. For a batch of M W OR (D ) consisting of m = γn elements the output is either centered around -m or -m + 2 depending on whether of not D i is included in the batch whereas M W OR (D) = N (-m, σ 2 ). Shifting both distributions by m gives us the dominating pair from Theorem 10 and this does not affect the hockey-stick divergence.As such, there exists true worst-case datasets for both sampling schemes under the add and remove relations, respectively. Crucially, the distributions above show us that under the add and remove relations we must add noise with twice the magnitude when sampling without replacement compared to Poisson subsampling! The intuition for this difference is that the subroutine behaves similarly to the add/remove neighboring relation when using Poisson subsampling, whereas it resembles the substitution neighborhood when sampling without replacement. When D i is included in the batch another datapoint is 'pushed out' of the batch when sampling without replacement. Due to this parallel one might hope that the difference in privacy parameters between Poisson subsampling and sampling without replacement only differ by a small constant similar to the difference between the add/remove and substitution neighboring relations. That is indeed the case for many parameters, but as we show in Section 7 this assumption unfortunately does not always hold. 
related work: 
 After Dwork and Rothblum (2016) introduced privacy loss distributions, a number of works used the formalism to estimate the privacy curve to arbitrary precision, beginning with Sommer et al. (2019) . Koskela et al. (2020; 2021) develop an efficient accountant that efficiently computes the convolution of PLDs by leveraging the fast Fourier transform. Gopi et al. (2021) fine-tunes the application of FFT to speed up the accountant by several orders of magnitude.The most relevant related paper for our work is by Zhu et al. (2022) . They introduce the concept of a dominating pair of distributions. A typical approach to analyzing the privacy guarantees of a mechanism is to consider a pair of datasets that represents the worst-case for the privacy parameters. However, for some problems, determining what is a worst-case pair is not obvious: sometimes there is not a single pair of worst-case datasets. Their notion of a dominating pair of distributions helps formalize the idea of worst-case datasets. Definition 7 (Dominating Pair of Distributions (Zhu et al., 2022) ). The ordered pair of distributions(P, Q) dominates a mechanism M (under some neighboring relation ∼) if for all α ≥ 0 sup D∼D H α (M(D)||M(D )) ≤ H α (P ||Q).The hockey-stick divergence of the dominating pair P and Q gives an upper bound on the value δ for any ε. Note that the distributions P and Q do not need to correspond to distributions of running the mechanism on actual datasets. However, if there exists a pair of neighboring datasets such that P = M(D) and Q = M(D ) then we can find tight privacy parameters by analyzing the mechanisms with inputs D and D because H e ε (M(D)||M(D )) is also a lower bound on δ for any ε. The definition of dominating pairs of distributions is useful for analyzing the privacy guarantees of composed mechanisms. In this work, we focus on the special case where a mechanism consists of k self-compositions. This is, for example, the case in DP-SGD, in which we run several iterations of the subsampled Gaussian mechanism. The property we need for composition is presented in Theorem 8. Theorem 8 (Following Theorem 10 of Zhu et al. (2022) ).If (P, Q) dominates a mechanism M then (P k , Q k ) dominates k iterations of M.When studying differential privacy parameters in terms of the hockey-stick divergence, we usually focus on the case of α ≥ 1. Recall that the hockey-stick divergence of order α can be used to bound the value of δ for an (ε, δ)-DP mechanism where ε = ln(α). We typically do not care about the region of α < 1 because it corresponds to negative values of ε. However, it is crucial that definition of dominating pairs of distributions consider these values as well. This is because outputs with negative privacy loss are important for composition and Theorem 8 would not hold if the definition only considered α ≥ 1. In Sections 5 and 7 we consider distribution where the distributions that bound the hockey-stick divergence for α ≥ 1 without composition does not bound α ≥ 1 under composition. Zhu et al. (2022) studied general mechanisms in terms of dominating pairs of distributions under Poisson subsampling and sampling without replacement. Their work give upper bounds on the privacy parameters based on the dominating pair of distributions of the non-subsampled mechanism. We use some of their results which we introduce later throughout this paper. 
worst-case pair of datasets under add and remove relations: 
 In this section we give pairs of neighboring datasets with provable worst-case privacy parameters under the add and remove neighboring relations separately. We use these datasets as examples of the pitfalls to avoid in the subsequent section, where we discuss the combined add/remove neighboring relation. Proposition 9. Let M(x 1 , . . . , x n ) := n i=1 x i + N (0, σ 2 ) denote the Gaussian mechanism.1. There exists a dataset pair D ∼ R D such that δ ∼ R M P oisson is realized by (D, D ) and δ ∼ A M P oisson is realized by (D , D) (recall Definition 4). 
no worst-case pair of datasets under add/remove relation: 
 So far, we have considered privacy curves defined for all ε ∈ R, which is a necessary subtlety for PLD privacy accounting tools (e.g., Theorem 8). In this section, we relax the strong notion of worst- case dataset from Definition 4 to the more familiar setting where ε ≥ 0. Our main result is to give an example of a mechanism that admits a worst-case dataset under ∼ A/R and ε ≥ 0 when run for a single iteration, yet fails to admit a worst-case dataset (for ε ≥ 0) when run for multiple iterations. This violates an implicit assumption made by some privacy accountants. We can correct for this by computing the privacy curve under ∼ A and ∼ R separately and then taking the maximum.Proposition 11. Consider the Laplace mechanism M(x 1 , . . . , x n ) := n i=1 x i + Lap(0, s) and let M W OR be the n b -subsampled mechanism. Then, for some choice of k > 1 and b ≥ 1, there is no dataset-pairD ∼ A/R D such that δ ∼ A/R M k W OR (ε) = H e ε (M k W OR (D)||M k W OR (D ))for all ε ≥ 0.Note that this result can be extended easily to the γ-subsampled mechanism M P oisson as well. In any case, as we argued in Section 4, the privacy curves of M W OR under both add and remove neighbouring relations are realized by worst-case datasets. That is, we can find datasets D ∼ R D such that δ ∼ R M W OR is realized by (D, D ) and δ ∼ A M W OR is realized by (D , D). Moreover, it is generally the case that the privacy curve of a subsampled mechanism under ∼ R dominates the same privacy curve under ∼ A when ε ≥ 0 (see e.g. Proposition 30 of Zhu et al. (2022) or Theorem 5 of Mironov et al. (2019) ). In our case, the subsampled Laplace mechanism satisfies the symmetry conditions of Zhu et al. (2022) Proposition 30, we also have thatδ ∼ A/R M W OR (ε) = δ ∼ R M W OR (ε) ≥ δ ∼ A M W OR (ε) for ε ≥ 0. Now, noting that δ ∼ A/R M W OR (ε) = max{δ ∼ A M W OR (ε), δ ∼ R M W OR (ε)}, Proposition 11 can be proved by plot. Figure 1 shows several variations of the curves δ ∼ A M k W OR and δ ∼ R M k W OR, which have been computed numerically by Monte Carlo simulation (as in e.g. Wang et al. (2023) ). These curves are seen to cross in the region ε ≥ 0 when k = 2.Interestingly, the phenomenon emerges when k increases from 1 but disappears again for larger values of k. This is better understood by considering the privacy loss distributions L M W OR (D||D ) and L M W OR (D ||D), whose CDFs are shown in Figure 2 .The add relation PLD L M W OR (D ||D), which has a large mass at -ln(0.1+0.9/e), is more likely to take on positive values compared to the remove relation PLD L M W OR (D||D ), which tends to take on larger values due to its mass being slightly more spread out over [0, ∞). This effect is amplified by composition, which leads to the composed add PLD L M 2 W OR (D||D ) being much more likely to take on small positive values compared to L M 2 W OR (D ||D). This in turn causes the privacy curve for M 2 W OR to be larger under the add relation compared to the remove relation when ε is small. Under a larger number of compositions, however, it is known that both PLDs converge to a Gaussian distribution (Dong et al., 2019) . This explains why δ∼ R M k W OR and δ ∼ A M k W ORtend toward one another and the crossing behavior appears to vanish.  
privacy guarantee difference between sampling schemes: 
 In this section we explore settings where the privacy parameters between Poisson subsampling and sampling without replacement differ significantly. We focus on the subsampled Gaussian mechanism since this is the mechanism of choice for DP-SGD. One approach for choosing privacy-specific hyperparameters is to fix δ and the number of iterations to run DP-SGD. We can then compute the minimum value of the noise multiplier σ required to achieve (ε, δ)-DP for various sampling rates.We follow this approach for our example. We fix δ = 10 -6 and the number of iterations to 10, 000.We then vary the sampling rate between 10 -4 to 1 and use the PLD accountant implemented in the Opacus library (Yousefpour et al., 2021) In Figure 3 we plot the noise multiplier required to achieve (ε, δ)-DP with Poisson subsampling for ε ∈ {1, 2, 5, 10}. For comparison we plot the noise multiplier required to achieve (10, δ)-DP when sampling without replacement. From the previous section we know that this is twice the noise required for (10, δ)-DP with Poisson subsampling. The plot is clearly divided into two regions.When the sampling rate is high, the noise multiplier scales linearly in the sampling rate. However, for sufficiently low sampling rates the noise multiplier decreases much slower.This effect has been observed previously (see Ponomareva et al. (2023) ; Anil et al. (2022) for similar plots). Ideally, we want to choose parameters on the right side of this hinge as the benefits of privacy amplification wear off on the left side. For this reason some work has observed improved results when using large batch size (see, e.g., Dörmann et al. (2021) ).However, one might choose to select parameters close to the hinge. This can be problematic if the accountant assumes Poisson sampling but sampling without replacement is used. The hinge happens when σ is slightly less than 1 for Poisson sampling and therefore it happens when it is slightly less than 2 for sampling without replacement. The consequence can be seen for the curve for sampling without replacement in Figure 3 . For large sampling rates the noise requires roughly matches that for ε = 5 with Poisson subsampling. But for the small sampling rates we have to add more noise than for ε = 1 with Poisson subsampling. As such, if we use an accountant for Poisson subsampling with a target of ε = 1 but our implementation using sampling without replacement the actual value of ε could be above 10! We could hope that this increase would be offset if we allow for some slack in δ as well. However, as seen in the table of Figure 3 there can still be a big gap in ε even when we allow several orders of magnitude difference in δ. 
substitution: 
 In this section we consider the substitution neighboring relation. Unfortunately, finding tight bounds under the substitution relation can be challenging. We have already shown how the worst-case pair of datasets can differ depending on the value of ε under the add/remove relation. However, the solution to that problem is straightforward because we simply find the parameters under the add and remove relations separately and report the maximum value. Here we show that such a solution is not always possible under the substitution relation using a small concrete example for sampling without replacement.First, we restate another result from Zhu et al. (2022) which we use throughout the section. Similar to the case of add and remove, they show that without composition the worst-case datasets depend on whether or not α is above 1.Theorem 12 (Proposition 30 of Zhu et al. (2022) ). If (P, Q) dominates M under the substitution neighborhood relation for datasets of size γn then under the substitution neighborhood for datasets of size n we haveδ(α) ≤ H α ((1 -γ)P + γQ||P ) if α ≥ 1; H α (P ||(1 -γ)P + γQ) if 0 < α < 1,where δ(α) is the largest hockey-stick divergence of order α between running M W OR for a pair of neighboring datasets.Next we address a mistake made in related work. In their work on computing tight differential privacy guarantees Koskela et al. (2020) considered worst-case neighboring datasets for the subsampling Gaussian mechanism under multiple sampling techniques and neighboring relations. In the case of substitution they compute the hockey-stick divergence between the pair of distributions (1-γ)N (0, σ 2 )+γN (-1, σ 2 ) and (1-γ)N (0, σ 2 )+γN (1, σ 2 ). They consider the same distributions under both Poisson subsampling and sampling without replacement and as such make the claim that the privacy curve is identical between the two schemes under the substitution relation. Unfortunately, this is not true and it is also contradicted by our example from Section 6. If this claim was true the privacy curves for the two schemes would never differ significantly for add/remove either since the privacy guarantees of substitution never better than under add/remove for the mechanism.We see that their distributions do not follow the structure of Theorem 12. They compare the datasets D and D where D i = -1, D i = 1 and all other entries are 0. This is an understandable mistake as it seems the intuition behind this choice is that we do not want any additional randomness from other elements than the ith entry. For Poisson subsampling this requires the elements to have a value of 0, but when sampling without replacement this holds for any pairs of datasets where all other elements have the same value as we sample a fixed amount.Instead we can consider the datasets where D i = 1, D i = -1 and all other elements are -1.It follows from Theorem 12 that these are worst-case neighbouring datasets without composition. However, since this is not a dominating pairs of distributions it is more complicated when we consider composition. One might hope that we could simply compute the hockey-stick divergence of the self-composed distributions in both directions similar to the add/remove case. But sometimes that is not sufficient because we can combine the directions unlike with the add and remove cases.Next we give a minimal counterexample to showcase this challenge. Figure 4 shows the hockey-stick divergence as a function of ε for three pairs of neighboring datasets. We consider datasets of size 2 where we sample batches with a single element that is γ = 0.5. We apply the Laplace mechanism with a scale of 2. We compose the subsampled mechanism with itself only once, as in we run 2 queries. In all cases the neighboring datasets agree on index 1 and differ in index 2. For the first line D 1 = D 1 = -1, D 2 = 1, and D 2 = -1 for both queries. The second line switches D and D compared to the first line. So far this is very similar to the add and remove cases, the interesting case is the third line. We still have that D 1 = D 1 = -1 for both queries but now the second index differs across queries as we have D 2 = 1 and D 2 = -1 for the first query, but D 2 = -1 and D 2 = 1 for the second query. This pair of datasets matches the datasets from the first line in one query and the second line in the other. We can see from Figure 4 that the worst pair of datasets depends on the value of ε with all three pairs being the worst within one range.The above example is possible because the distributions for a query can match either the worst-case for add or remove. And since queries can be independent we can match the add case for one query and remove case for the other. This scales up with the number of compositions. For k compositions, we have to consider k + 1 ways of dividing up the queries between matching the add or the remove case. This significantly slows down the accountants in contrast to the 2 cases for add/remove. Worse still, we do not have a formal proof that one of k + 1 cases is the worst-case pair of datasets. 
discussion: 
 We have highlighted two issues that arise in the practice of privacy accounting.First, we have given a concrete example where the worst-case dataset (for ε ≥ 0) of a subsampled mechanism fails to be a worst-case dataset once that mechanism is composed. Care should therefore be taken to ensure that the privacy accountant computes privacy guarantees with respect to a true worst-case dataset for a given choice of ε.Secondly, we have shown that the privacy parameters for a subsampled and composed mechanism can differ significantly for different subsampling schemes. This can be problematic if the privacy accountant is assuming a different subsampling procedure from the one actually employed. We have shown this in the case of Poisson sampling and sampling without replacement but the phenomenon is likely to occur when comparing Poisson sampling to shuffling as well. Computing tight privacy guarantees for the shuffled Gaussian mechanism remains an important open problem. It is best practice to ensure that the implemented subsampling method matches the accounting method. When this is not practical, the discrepancy should be disclosed.We conclude with two recommendations for practitioners applying privacy accounting in the DP-SGD setting. We recommend disclosing the privacy accounting hyperparameters for the sake of reproducibility (see Section 5.3.3 of Ponomareva et al. (2023) for a list of suggestions). Finally, we also recommend that, when comparisons are made between DP-SGD mechanisms, the privacy accounting for both should be re-run for the sake of fairness.We treat the sample size and batch size as public knowledge in line with prior work.(Zhu et al.,2022) 
 
 Appendix:  


Decision: The submission identifies critical issues with differential privacy (DP) accounting methods, specifically highlighting discrepancies between Poisson subsampling and sampling without replacement and problems in worst-case dataset assumptions (e.g., the worst-case dataset shift for a single composition is not the worst-case under multiple compositions). Reviewers appreciated the relevance of these issues for DP practitioners. The message is clear: DP accounting must be done with care, and naive implementations may fail by considering wrong worst-case datasets and amplification via subsampling. However, reviewers DUtv and Tsvf noted that while the paper successfully points out these challenges, it falls short of offering concrete solutions. DUtv specifically mentioned that this paper would be more appropriate for a niche venue focused on DP, rather than NeurIPS, suggesting a workshop setting might be better suited for its contributions. Furthermore, DUtv highlighted that the comparison with Chua et al.'s work seemed misplaced, noting that the impact and scope of this paper do not quite match the broader significance of Chua et al.'s findings. Reviewer qk3S raised concerns about the corretness of Proposition 9. Other reviewers did not support the issue raised by reviewer qk3S, and this concern was downplayed in the discussion and in this meta-review. Reviewer NpBG did not engage with the rebuttal, so their review is given less weight. 

The main reason to reject this paper is its lack of actionable solutions for the identified privacy accounting issues (DUtv and Tsvf), making its contributions less compelling for a broad audience. While differential privacy is absolutely important and of significant interest to NeurIPS and the wider machine learning community, this paper does not provide the kind of applicable solutions needed to advance the field. As pointed out by several reviewers, identifying problems in accounting schemes is relevant for the DP community. However, going beyond raising issues and concretely developing possible solutions and clear recommendations would have been more meaningful for a broader ML audience. The reader is left wondering what are the concrete and actionable steps to accurately account for self-composition (especially when dominating pairs of PLRV are difficult to compute), and to identify the true DP guarantee from subsampling given that it is seemingly so easy to err. While some hints of solutions are dispersed throughout the paper, they are not presented in a clear and actionable way. The sentiment was shared by reviewers both during the review and the discussion phase.

I encourage the authors to continue working in this direction and, if resubmitting to an ML conference with a broad audience, consider developing actionable solutions to the important technical insights they outline in their work. The message that accounting should be done with care -- and implementations can easily be flawed -- is of interest to the DP community. However, for a broader audience, actual solutions would have been more impactful. How should we fix these issues? The two lasting recommendations in the paper, namely that practitioners must disclose privacy accounting hyperparameters for reproducibility and re-run privacy accounting when comparing different DP-SGD mechanisms, were found insufficient by the reviewers.

Reviews: review: paper_summary: paper_summary: This paper studies the notion sampling with replacement for differential privacy. Most of the literature on machine learning with differential privacy benefits from privacy amplification by poisson sampling in the privacy analysis. However, when implementing the mechanisms, engineers ofter use the sub-sampling with replacement as a substitude for poisson sampling, mainly due to efficiency issues. This paper studies the gap between these two settings. Their main contributions are as follows: 

 - Identifying the Problem with DP-SGD Implementations: The authors highlight a critical issue with implementations of (DP-SGD). They argue that many implementations incorrectly assume that Poisson sampling and batch-sampling yield similar privacy guarantees, which is not necessarily true.

- Gap between Batch-Sampling and Poisson Sampling: The paper demonstrates a significant privacy gap between these two sampling methods. They provide an example showing that for certain hyperparameters, Poisson subsampling can result in an ϵ≈1, whereas batch-sampling without replacement can result in an ϵ>10. This discrepancy is critical for privacy accounting in DP-SGD.  Authors compare the privacy guarantees of Poisson subsampling and batch-sampling. They show that the privacy guarantees can differ significantly depending on the sampling technique used. Their analysis reveals that the method of sampling batches (Poisson vs. fixed-size) significantly impacts the resulting privacy guarantees, cautioning against the interchangeable use of different sampling techniques in privacy analysis.
strength_weakness: strength_weakness: - I have some concerns about the correctness of the results.

- There is not much technical novelty.
questions: questions: - 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.

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

- 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 results of section 6, are you using the worst-case datasets of Proposition 9 to calculate the privacy curve?
limitations: limitations: Yes
paper_summary: paper_summary: The two main contributions of the paper is as follows:

the privacy guarantee of composition of subsampled mechanism may not be defined by worst-case dataset(s) for the underlying mechanism
Poisson subsampling and sampling without replacement may not have similar privacy guarantee.
strength_weakness: strength_weakness: There are some typos, and 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.
questions: questions: Is there a provable gap between the composition of WoR and Poisson subsampling?
limitations: limitations: Mostly seem like an empirical study of the composition result.
paper_summary: paper_summary: This paper examines the discrepancies between privacy accounting methods and their implementations, highlighting several cases where these mismatches lead to incorrect results. Specifically, it compares the noise requirements for achieving privacy guarantees under Poisson sampling versus sampling without replacement, and explores the limitations of worst-case dataset assumptions in subsampled mechanisms. Additionally, the authors address challenges in computing tight differential privacy (DP) bounds under the substitution relation of neighboring datasets.
strength_weakness: strength_weakness: - The different messages of the paper may be convoluted sometimes, which makes the paper hard to follow.

- No viable technical solutions are provided for the identified issues, which might be a difficult research problem.
questions: questions: - In the equation between lines 133 and 134 (and in the rest of the article), where did the maximum with $0$ go ? When I try to recover expression on the right-hand side, I obtain $E_Y \max(0, 1-e^{\epsilon - Y})$.
limitations: limitations: The authors discuss the limitations of their work.
paper_summary: paper_summary: The authors present two potential sources of error which can arise when composing sub-sampled DP mechanisms. On one hand, they discuss cases in which the composition of worst-case datasets does not yield the expected result, on the other hand, they disambiguate guarantees for mechanisms with Poisson sampling vs. sampling WOR.
strength_weakness: strength_weakness: There is nothing particularly wrong with the paper. The facts stated are valid, and they are interesting, especially since they point out potential sources of confusion. However, none of this is surprising or even particularly novel. Most of this information is implied by earlier work (Zhu et al. in particular), and some of the facts stated here would be better suited as GitHub issues on the relevant accountants, followed by a technical report at a venue like TPDP or Journal of Privacy and Confidentiality. That is to say: I am not against this paper in general, but this is not a NEURIPS paper to me. It is a highly specialised piece of technical writing with a very narrow scope, and is likely to be of interest only to a very small community. I would recommend the authors to submit it to a venue which is better suited to its content.
questions: questions: Some suggestions for improvement: 

- Definition 1: The "only if" does not hold here. For example, the mechanism also satisfies epsilon/delta-DP if it satisfies epsilon/delta probabilistic DP, i.e. the PLRV is bounded with probability at least 1-delta, but not the other way around.
- Definition 3: The hockey-stick divergence is asymmetric in general. A more appropriate terminology would be "of P from Q"
- There are some measure-theoretic constructs used, but there are no assumptions stated about absolute continuity (think (0, delta)-DP) or about whether densities exist (Definition 5), and the notation in Definition 5 is a bit uncommon. A nitpick: the "d" is a differential operator, and it's recommended to write it as $\mathrm{d}$
- There is a subtlety about Poisson sampling in Definition 6: Treating the **expected batch size** as public is fine, but the footnote just says "batch size". The **actual** batch size (the realised one), should still be kept secret right?
- 160: Referring to $D \sim D'$ as a dominating pair of datasets is a recipe for confusion in my opinion. The established terminology is to refer to dominating pairs of measures (or distributions). Perhaps state that the distributions under D, D' are dominating pairs, but not the databases themselves. After all, the whole point of even considering dominating pairs is (allegedly) to not have to think in terms of databases.
- Perhaps use "databases" consistently rather than mixed with "datasets"
- In 244: Your paper is aimed at an audience who are not DP theorists. I think just stating that "they converge to a Gaussian distribution" does not really inform this audience about why the crossing vanishes. You'd probably have to explain that the privacy profiles become pointwise equal because the PLDs now become symmetric about the expectations.
- 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?
- 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?
limitations: limitations: The discussion on limitations is a bit lacking in my opinion. The authors state (in the checklist) that the "main limitation is expressed in Conjecture 12". Not being able to find a counterexample for a proposition is not really what one understands under the term "limitation" of a work. 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. I would have much preferred an experimental section where the consequences of the pitfalls stated in the work are actually shown to affect the real-world use of DP-SGD or other mechanisms, and/or to see that specific privacy threats are practically enabled by overlooking these subtleties (e.g. through auditing).

Comments: title: Thank you for the rebuttal
Quick reminder to respond to the rebuttal
Quick reminder to respond to the rebuttal
Thank you and response to rebuttal
comment: Thank you for your detailed review and suggestions. 

We will consider all comments in future versions of the paper, here we address questions and recommendations. 

>- ... So, how do the authors suggest practitioners should handle the potential overestimation of privacy guarantees when using Poisson subsampling versus sampling without replacement? Are there specific guidelines or tools recommended to mitigate this risk? 
>- ... What specific steps should practitioners take to ensure that their privacy accounting method matches their implemented subsampling technique?  
>- 1 Include a section on strategies to protect proprietary data from miscalculated privacy guarantees. This could involve adopting more rigorous testing and validation procedures for privacy accountants, using differential privacy techniques like noise addition, and implementing robust encryption methods to safeguard data.  
>- 4 Discuss the ethical implications of using different sampling methods in detail. Propose guidelines for the ethical use of these methods, ensuring that the differences in privacy guarantees are fully understood and disclosed.

We conclude our paper with a short discussion including two concrete recommendations. We also refer to a more detailed list of best practices laid out in the paper "How to dp-fy ML: A practical guide to machine learning with differential privacy".

However, our suggestions primarily concern reproducibility and fair comparisons in the scientific community. We will expand our discussion with a focus on real-world deployments.

>- I have a question: What guidelines do the authors propose for the ethical use of publicly available datasets in privacy research?
>- 2 Develop comprehensive ethical guidelines for practitioners that outline permissible use cases, data protection measures, and the consequences of misuse.

We agree that these are important ethical considerations. However, we consider the development of such guidelines out-of-scope for our work. 
The community should address these concerns as a whole.
It is relevant for all ML practitioners and not just privacy researchers.

>- 3 Provide recommendations for enhancing the security of differential privacy models. This could involve incorporating adversarial training, which involves training the model with adversarial examples designed to simulate potential attacks. For instance, synthetic queries that mimic data extraction attempts could be used to train the model to recognize and mitigate real extraction attempts. Anomaly detection systems can also be implemented to monitor model queries in real-time and identify unusual patterns indicative of an ongoing attack.

These concerns are the focus of the adjacent line of research on "privacy auditing".
> 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).
I'm not sure if I understand the notion of dominating databases. What prevents you from choosing the neighboring datasets to be 

$$D=(0,...,0,0) ~~ {and} ~~ D'=(0,...,0,100)?$$ 

This clearly incurs higher hockey-stick divergence compared to $$D=(0,...,0,0) ~~ {and} ~~ D'=(0,...,0,1).$$ 

So I think the notion of dominating databases should be normalized by the sensitivity.

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. This is why you can show that you need double the noise! But this is meaningless. 

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.
Dear Reviewer NpBG,

As we approach the end of the discussion period with the authors, I would really like to hear your thoughts on their rebuttal. I would really appreciate it if you could engage with them before the close of discussions (Aug 13th, 11:59pm AoE).

Thanks,
AC
Dear Reviewer qk3S,

As we approach the end of the discussion period with the authors, I would really like to hear your thoughts on their rebuttal. I would really appreciate it if you could engage with them before the close of discussions (Aug 13th, 11:59pm AoE).

Thanks,
AC
Thank you for addressing the points raised in my review. As pointed out by the authors, correctly accounting privacy with algorithms such as DPSGD is a crucial research direction. Even though the authors do not provide technical solutions to the problems shown in the article, their identification is still meaningful. If the typo that I pointed out has no impact on the conclusion of the authors (i.e. if it didn't introduce errors later in the paper), I will improve my rating from 5 to 6.
Thank you for addressing the points raised in my review. I consider my suggestions for clarity etc., adequately addressed by the comments, and I'm confident that you have the technical expertise in DP to incorporate (or not) the other comments which I made and which were not specifically addressed point to point in your rebuttal. One final thought:

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

I agree with you that the discussion about scope and novelty has a strong subjective element, and I'm not going to hold this point against you. In fact, I'm willing to give you the benefit of the doubt and increase my score. However, I feel like I have to push back a bit against your argumentation using the Chua et al. paper. The paper (largely) does away with an age-old debate: "If we use the non-private SGD version of iterating through minibatches one by one, what happens to privacy guarantees?" Opacus, during its entire 0.XX release cycle had a note to the effect of "this type of minibatch sampling can be a good approximation of Poisson sampling" (I'm paraphrasing), and I'm fairly sure that many users and even people with some knowledge of DP came away with the notion that not using Poisson sampling is in some way OK. In other words: the Chua et al. paper takes big strides towards cleaning up a **major** misunderstanding, and I thus understand why it was awarded an oral at ICML. While indeed, thematically, your work is in a similar flavour, I am hard-pressed to view the issue you are tackling here as having the same impact or scope. I will increase my score as I recognise that the topic of your work also has importance (and because "in DP, details matter"), but I maintain that the impact and scope of your results, while interesting and valid, are not on par with some of the most important results in the field.