Scalable DP-SGD: Shuffling vs. Poisson Subsampling
Authors: Lynn Chua
Badih Ghazi
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Amer Sinha
Chiyuan Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: DPSGD
Differential Privacy
Shuffling
Poisson subsampling
Primary area: privacy
TL;DR: Establishes new lower bounds on privacy analysis of DP-SGD with shuffling and provides a first comparative study of DP-SGD with Shuffling vs Poisson Subsampling in the light of the gaps in privacy analysis between the two approaches.

Abstract: We provide new lower bounds on the privacy guarantee of _multi-epoch_ Adaptive Batch Linear Queries (ABLQ) mechanism with _shuffled batch sampling_, demonstrating substantial gaps when compared to _Poisson subsampling_; prior analysis was limited to a single epoch.
Since the privacy analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) is obtained by analyzing the ABLQ mechanism, this brings into serious question the common practice of implementing Shuffling based DP-SGD, but reporting privacy parameters as if Poisson subsampling was used.
To understand the impact of this gap on the utility of trained machine learning models, we introduce a novel practical approach to implement Poisson subsampling _at scale_ using massively parallel computation, and efficiently train models with the same.
We provide a comparison between the utility of models trained with Poisson subsampling based DP-SGD, and the optimistic estimates of utility when using shuffling, via our new lower bounds on the privacy guarantee of ABLQ with shuffling.

Scalable DP-SGD: Shuffling vs. Poisson Subsampling
Lynn Chua Google Research chuallyn@googge..om
Badih Ghazi
Pritish Kamath Google Research pri pritishk@google.coo com
Google Research badihghazi @araiiig@aall.... com
Ravi Kumar Google Research
Pasin Manurangsi Google Research pasinggoogle.c com
Amer Sinha Google Research
ravi wwwkkk530mmm...mmmmm com
amersinha@google.cmm com
Chiyuan Zhang Google Research chiyuan@google..om com
Abstract
We provide new lower bounds on the privacy guarantee of the multi-epoch Adaptive Batch Linear Queries (ABLQ) mechanism with shuffled batch sampling, demon- strating substantial gaps when compared Poisson subsampling; prior analysis was limited to single epoch. Since the privacy analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) obtained by analyzing the ABLQ mech- anism, this brings into serious question the common practice of implementing shuffling-based DP-SGD, but reporting privacy parameters if Poisson subsam- pling was used. To understand the impact of this gap on the utility of trained machine learning models, we introduce practical approach implement Poisson subsampling at scale using massively parallel computation, and efficiently train models with the same. We compare the utility of models trained with Poisson- bubsampling-based DP-SGD, and the optimistic estimates of utility when using shuffling, via our new lower bounds on the privacy guarantee of ABLQ with shuffling.
Introduction
common approach for private training of differentiable models, such neural networks, is apply first-order methods with noisy gradients. This general framework is known as DP-SGD (Differentially Private Stochastic Gradient Descent) [Abadi al., 2016]; the framework itself is compatible with any optimization sub-routine. Multiple open source implementations exist for applying DP-SGD in practice, namely, Tensorflow Privacy, JAX Privacy [Balle et al., 2022] and PyTorch Opacus [Yousefpour et al., 2021]; and DP-SGD has been applied widely in various machine learning domains [e.g., Tramer and Boneh, 2020, De al., 2022, Bu et al., 2022, Chen et al., 2020, Dockhorn et al., 2023, Anil et al., 2022, He et al., 2022, Igamberdiev et al., 2024, Tang et al., 2024].
DP-SGD (Algorithm 1) processes the training data in sequence of steps, where each step, noisy estimate of the average gradient over a mini-batch is computed and used to perform a first-order update over the differentiable model. To obtain the noisy (average) gradient, the gradient g for each example in the mini-batch is clipped to have norm at most C' (a pre-determined fixed bound), by setting [g]c := g min(1, C/llglla), and computing the sum over the batch; then independent zero-mean noise drawn from the Gaussian distribution of scale aC' is added to each coordinate of the summed gradient. This could then be scaled by the "target" mini-batch size obtain noisy
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algorithm 1 DP-SGD: Differentially Private Stochastic Gradient Descent [Abadi et al., 2016] Params: Batch sampler B (samples T batches, with "target" batch size b), differentiable loss L:Rd x X' + R initial model state wp, clipping norm C, noise scale a. (Z1,....,2up F.))
Input: Dataset
Output: Final model state wT E R
(SI...., Sr) < -B(n)
fort = 1, T do
9t < 5 (N c²CCTa) + Exes, Fwl(w:;)) Could also be some other optimization method.
we W ne9t
return Wrr
average gradient.' The privacy guarantee of the mechanism depends on the following parameters: the noise scale o, the number of examples in the training dataset, the size of mini-batches, the number of training steps, and the mini-batch generation process.
In practice, almost all deep learning systems generate mini-batches of fixed-size by sequentially going over the dataset, possibly applying global shuffling of all the examples in the dataset for each training epoch; each epoch corresponds the examples may be kept the same or resampled between different epochs. However, performing the privacy analysis for such mechanism has appeared to be technically difficult due to correlation between the different mini-batches. Abadi et al. [2016] instead consider a different mini-batch generation process of Poisson subsampling. wherein each mini-batch is generated independently by including each example with fixed probability. This mini-batch generation process is however rarely implemented in practice, and consequently it has become common practice to use some form of shuffling in applications, but to report privacy parameters if Poisson subsampling was used (see, e.g., the survey by Ponomareva et al. [2023, Section 4.3 A notable exception is the Py PoTocc Opacus library [Yousefpour et al., 2021] that supports the option of Poisson subsampling; however, this implementation only works well for datasets that allow efficient random access (for instance by loading it entirely into memory). To the best of knowledge, Poisson subsampling has not been used for training with DP-SGD on massive datasets.
single pass over the dataset, and the ordering of
The privacy analysis of DP-SGD is usually performed by viewing it as a post-processing of an Adaptive Batch Linear Queries (ABLQ) mechanism that releases the estimates of a sequence of adaptively chosen linear queries the mini-batches (formal definitions in Section 2.1). Chua et al. [2024] showed that the privacy loss of ABLQ with shuffling can be significantly higher than that with Poisson subsampling for small values of a. Even though their analysis only applied to single epoch mechanism, this has put under serious question the aforementioned common practice of implementing DP-SGD with some form of shuffling while reporting privacy parameters assuming Poisson subsampling. The motivating question for our work is:
Which batch sampler provides the best utility for models trained with DP-SGD, when applied with the correct corresponding privacy accounting?
1.1 Contributions
Our contributions are summarized as follows.
Privacy Analysis of Multi-Epoch ABLQ with Shuffling. We provide lower bounds on the privacy guarantees of shuffling- based ABLQ to handle multiple epochs. We consider the cases of both (i) Persistent Shuffling, wherein the examples are globally shuffled once and the order is kept the same between epochs, and (ii) Dynamic Shuffling, wherein the examples are globally shuffled independently for each epoch. Since our technique provides a lower bound on the privacy guarantee, the utility of the models obtained via shuffling- based DP-SGD with this privacy accounting is an optimistic estimate of the utility under the correct accounting.
Scalable Implementation of DP-SGD with Poisson Subsampling via Truncation. Variable batches are typically inconvenient handle in deep learning systems. For example, upon a change in the input shape, jax. jit triggers a recompilation of the computation graph, and tf function will
As explained later, for Poisson batch sampler. the mini-batch size is not constant, but the scaling has to be done with the "target" mini mati- size, and not the realized mini-batch size.

---

differentially private (DP) mechanism M X - Ao can be viewed as a mapping from input datasets to distributions over an output space, namely, input dataset (II...., F.) where each example x; E X, M(x) ) is a probability measure over the output space O; for ease of notation, we retrace the computation graph. Additionally, Google TPUs require all operations to have fixed input and output shapes. We introduce truncated Poisson subsampling to circumvent variable batch sizes. In particular, we choose an upper bound on the maximum batch size B that our training can handle, and given any variable size batch b, if b 2 B, we randomly sub-select B examples to retain in the batch, and if b < B, we pad the batch with B b dummy examples with zero weight. This deviates slightly from the standard Poisson subsampling process since our batch sizes can never exceed B. We choose B to be sufficiently larger than the expected batch size, that the probability that the sampled batch size b exceeds the maximum allowed batch size is small. We provide a modification to the analysis of ABLQ with Poisson subsampling in order to handle this difference.
Generating these truncated Poisson subsampled batches can be difficult when the dataset is too large to fit in memory. We provide a scalable approach to the generation of batches with truncated Poisson subsampling using massively parallel computation [Dean and Ghemawat, 2004]. This can be easily specified using frameworks like beam [Apache Beam] and implemented on distributed platforms such as Apache Flink, Apache Spark, or Google Cloud Dataflow.
Our detailed experimental results are presented in Section 4, and summarized below:
DP-SGD with Shuffle batch samplers performs similarly to Poisson subsampling for the same a. However, DP-SGD with Shuffle batch samplers, with our optimistic privacy accounting, perform worse than Poisson subsampling in high privacy regimes (small values of =).
Thus, our results suggest that Poisson subsampling is a viable option for implementing DP-SGD at scale, with almost no loss in utility compared to the traditional approach that uses shuffling with (incorrect) accounting assuming Poisson subsampling.
1.2
Related Work
Chua et al. [2024] demonstrated gaps in the privacy analysis of ABLQ using shuffling and Poisson subsampling, by providing a lower bound on the privacy guarantee of ABLQ with shuffling; their technique, however, was specialized for one epoch. We extend their technique to the multi- eeeli- version of ABLQ with shuffling and provide lower bounds for both persistent and dynamic batching.
Lebeda et al. [2024] also point out gaps in the privacy analysis of ABLQ with Poisson subsampling and with sampling batches of fixed size independently, showing that the latter has worse privacy guarantees than Poisson subsampling. We do not cover this sampling in our experimental study, since sampling independent batches of fixed size not commonly implemented practice, and DP-SGD using this sampling is only expected to be worse as compared to Poisson subsampling.
Yousefpour al. [2021] report the model utility (and computational cost overhead) under training with DP-SGD with Poisson subsampling. However, to the best of our knowledge, there is no prior work that has compared the model utility of DP- under Poisson subsampling with that under shuffling, let alone compared it against DP-SGD under (Dynamic/Persistenn) shuffling or studied the gaps between the privacy accounting of the two approaches.
One possible gap between the privacy analysis of DP-SGD and ABLQ is that the former only releases the final iterate, whereas the latter releases the responses to all the queries. An interesting result by Annamalai [2024] shows that in general the privacy analysis of the last-iterate of DP-SGD cannot be improved over that of ABLQ, when using Poisson subsampling. This suggests that at least without any further assumptions, e.g., on the loss function, it is not possible to improve the privacy analysis of DP-SGD beyond that provided by ABLQ; this is in contrast the techniques of privacy amplification by iteration for convex loss functions [e.g. Feldman et al., 2018, Altschuler and Talwar, 2022].
2 Preliminaries
often refer to the corresponding random variable also M(x). Two datasets and x' are said to be adjacent, denoted x ~ x', if they "differ in one example"; in particular, we use the "zeroing-out" adjacency defined shortly.
3

---

Algorithm 2 ABLQg: Adaptive Batch Linear Queries (as formalized in Chua et al. [2024])
Params: Batch sampler B (samples T batches), noise scale and (adaptive) query method A
(IR")" X X' + Bd
Input: Dataset
(#1,...,,.1)
Output: Query estimates 91, ................................ 9r Rd
(Si....,Spp < (n)
fort= ,..., do
(x(+) == A(g
9t < Gt + Lies, (15) for e o(0,
return (91, (91....191)
Algorithm 3 (n #): Permutation Batch Sampler
Algorithm 4 Pb,B,T: Truncated Poisson Batch Sampler
Params: Batch size b, numher of batches T.
Params: Target batch size 6, max batch size B, number
Input: Number of examples n s.t. E := 6T/n an integer (number of epochs), S := n/b is an integer (number of steps per epoch); list No...... T8-1,
batches
Input: Number of examples n.
Output: Sey. ST S [m]] of butches, with |St] S B. for f 1...., , do
where each Tee is permutation of [n.. Output: Seq. S1,.... ST S [n] batches.
St for I,..., do
for = .....,
........ E do
for s ..... do
8, (t)
with prob. b/n with prob. b/n
t= 5 5 + + (sb
S:
S.
(sb
if [ > B then
return Si..... Sr
S arhitrary subset of St of size B
return , Sr
Definition 2.1 (DP). For 8 2 0, mechanism M satisfies (s, 8)-DP if for all "adjacent" datasets
x ~ x', and for any (measurable) event I' it holds that Pr[M(()) E e s e Pr[M(x') E E +1]+6
For any mechanism M, we use &m Rgo [0, 1] to denote its privacy loss curve, namely (c) is the smallest such that M satisfies (c, (DDP: EM [0, 1] + R2o defined similarly.
2.1 Adaptive Batch Linear Queries Mechanism
Following the notation in Chua et al. [2024], we study the adaptive batch linear queries mechanism ABLQg (Algorithm 2) using batch sampler B and adaptive query method A, defined. The batch sampler B can be any algorithm that randomly samples sequence Si,..., Sr of batches. ABLQ operates by processing the batches in sequential order, and produces a sequence (g1...., .r). where the response 9r E Rd is produced the sum of (z)) over the batch S, with added zero-mean Gaussian noise of scale a to all coordinates, where the query t/e X Bd (for Bd = {u E R : ||ui|e < 11) is produced by the adaptive query method A, based on the previous responses 91....: 1t-1- DP-SGD can be viewed as post-processing of an adaptive query method that maps examples to the clipped gradient at the last iterate, namely the (1r) == (V.(((;-1,,)) (we treat the clipping norm C = 1 for simplicity, as it just scaling term).
Si....,,T
In this work, we consider the following mulli-epoch batch samplers: Deterministic Dr,7, Persistent Shuffle Si,r, and Dynamic Shuffle S batch sampler defined as instantiations of Algorithm in Figure and truncated Poisson PB,B.r (Algorithm 4); we drop the subscripts of each sampler whenever it is clear from context. Note that, while Po,B,T has restriction the value of n, the samplers Di,T, Sir and S require that the number of examples is such that E := bT/n and S == n/b are integers, where E' corresponds to the number of epochs and S corresponds to the number of steps per epoch. We call the tuple (n, b. T) as "valid" if that holds, and we will often implicitly assume that this holds. Also note that PB.B.T corresponds to the standard Poisson subsampling without truncation when B = oc. We use ôg(E) to denote the privacy loss curve of ABLQu for any B E , where other parameters such as a, T, etc. are implicit. Namely, for all 8 > 0, let òz(E) be the smallest 8 > 0 such that ABLQ satisfies (e. 8)-DP for all choices of the underlying adaptive query method A. We define (5) similarly. Finally, we define a (e, 6) as the smallest such that ABLQg satisfies (E,8)-DP, with other parameters being implicit in B.

---

Deterministic Batch Sampler Db,r(1) (n)) Realized as (n; Id, Id. ld....) where Id is the iden- tity permutation, i.e., the data is not permuted.
Persistent Shuffle Batch Sampler Sh. Realized as (m; m, ..... .). where a is random permutation over [n], i.e., the data is shuffled once and the order is persistent across epochs.
Dynamic Shuffle Batch Sampler S Realized as [,; To, TI,...), where Te 's are i.i.d. random permutations over [n]. i.e., the data is reshuffled in each epoch.
Figure 1: Various natural instantiations of the permutation batch sampler.
Adjacency notion. The common notion of Add-Remove adjacency is not applicable for mechanisms such ABLQD, ABLQss, ABLQgo because these methods require that bT /n and n/b are integers, and changing n by 1 does not respect this requirement. And while the other common notion of Substitution is applicable for all the mechanisms we consider, the standard analysis for A is done w.r.t Add-Remove adjacency [Abadi et al., 2016, Mironov, 2017]. Therefore, we use the "Zeroing-out" adjacency introduced by Kairouz et al. [2021], namely we consider the augmented input space X1 == X' U { where any adaptive query method A is extended as A(g1..... 9t: L) := 0 for all 91.
St E IR Datasets æ, x' XT are said to be zero-out adjacent if there exists such that a- -'= j. and exactly one of (æi, 2. is in X' and the other is L. We use æ - x' to specifically denote adjacent datasets with 24 E X' and x = L. Thus ~ x' if either x - x' or x' + x.
2.2 Dominating Pairs
For two probability density functions P and Q and a, E R2o. we use aP + BQ to denote the weighted sum of the density functions. We use P 53 Q to denote the product distribution sampled as (wr, wa) for w1 ~ P. w2 ~ Q, and, p8T to denote the T-fold product distribution P 69 .... 60 P. For all E E R. the ef -hockckyy stick divergence between P and Q is Dæ= (PIIQ) supr P(T) e QTT).
Thus, by definition mechanism M satisfies () iff for all adjacent æ x', holds that De (M(x)||((²') S 6.
Definition 2.2 (Dominating Pair [Zhu et al., 2022]). The pair (P.Q) dominates the pair (4, B)
(denoted (P, Q) > (A, B)) if De (PIIQ) 2 De (A holds for all E E TR. We say that (P, dominates mechanism M (denoted (P. Q) > -M) if (P. Q) (((z), for all adjacent x + x'.
If (P.Q) > .M, then for all 2 0, it holds that 8M(() S max/D (PII). Dec (QIP)), and conversely, if there exists adjacent datasets x th x' such that (M(z),M(z))) > (P.Q), then 5M(E) 2 max (PIIQ), D== (Q]) When both of these hold, say that (P, tightly dominates the mechanism M (denoted (P, = =M) and in this case it holds that d)((e) max Der (PIIQ), De- (Q). Thus, tightly dominating pairs completely characterize the privacy loss of a mechanism (although they are not guaranteed to exist for all mechanisms). Dominating pairs behave nicely under mechanism compositions: if (Pi, Q1) > M1 and (P2, Q2) > M2, then
(P1 @ Ps, Q1 & Q2) > Mi o M2, where Mi o M2 denotes the (adaptively) composed mechanism.
3 Privacy analysis of multi-epoch ABLQB
We discuss the privacy analysis of ABLQB for B E &D,,,S",,' via dominating pairs.
Privacy analysis for ABLQ A single epoch of the ABLQ mechanism corresponds to a Gaus- sian mechanism with noise scale a. And thus, F = bT/n epochs of the ABLQp mechanism corresponds an F-fold composition of the Gaussian mechanism, which is privacy-wise equiva- lent Gaussian mechanism with noise scale a/ o/VE [Dong et al., 2019, Corollary 3.3]. Thus, closed-form expression for ÔE( exists via the dominating pair (PD = =1, 4) QD (O Z)). Theorem 3.1 (Balle and Wang [2018, Theorem 8)). For all a > 0, E 2 O, and valid n, b, T, it holds that
(e( & (-o'e + + e (-o's- 10
where a'
VE*
and (c)) is the cumulative density function (CDF) of the standard normal random variable (0, 1).
5

---

Privacy analysis of ABLOp. First, let us consider the case of Poisson subsampling without truncation, namely B co. Zhu et al. [2022] showed that the tightly dominating pair for single step of A a Poisson sub-sampled Gaussian mechanism, is given by the pair (U = (1 - (),((, 2 + 9V(1 V = NN( )))).))))))))))))). where q is the sub-sampling probability of each example, namely q b/n. Since ABLQp is a T-fold composition of this Poisson subsampled Gaussian mechanism, it follows that (P'p == U Qp == v = A
A finite value of B however changes the mechanism slightly. In order to handle this, we use the following proposition, where drv (P. P') denotes the statistical distance between P and P'.
Proposition 3.2. For distributions P,P', Q, such that (P, (Q, Q') I n. and Des (P'II))))) I 6, then Dæ (PI[Q) - 6 + + (1+
Proof. For any event I we have that
@ P(T)& S P'(T) S +Q(())+++) (
(i)
S (Q(T) + +8+ e (Q(T) + 8 + ef),
where (i) follows from dPv P*) 17, (ii) follows from D (P'II'') < 5 and (iii) follows from dTv Q') S 17. Thus, we get that D (Pll)) S ā mf1+
The batch size |Sp] before truncation in Po. is distributed as the binomial distribution Bin(n, b/n). and thus, by a union bound over the events that the sampled batch size |S > B at any step, it follows that for any input dataset x,
PIBLQP.A. Pu BT (z), ABLQ P (z)) S T (n, B), drv (AvLA
where (n, b, B) == Pr Pin,. > BJ. Applying Proposition 3.2 we get Theorem 3.3. For all 0, E 2 O. and integers n 2 b. B 2 b, T, holds that àp(e) S max (Po (Qp), (Qp Pp)] T (1 + e (V b, B)-
While the hockey stick divergences Der (P)l(P) and (e-(Qpl|Pp) do not have closed expressions, upper bounds on these can be obtained using privacy accountants based on the methods of Rényi DP (RDP) [Mironov, 2017] and privacy loss distributions (PLD) [Meiser and Mohammadi, 2018, Sommer et al., 2019]; the latter admits numerically accurate algorithms [Koskela et al., 2020, Gopi et al., 2021, Ghazi et al., 2022, Doroshenko et al., 2022]. with multiple open-source implementations [Prediger and Koskela, 2020, Google's s DP Library., 2020, Microsoft., 2021].
Note that (n, 6, B) can be made arbitrarily small by increasing B, which affects the computation cost. In particular, given target privacy parameter (s, we can, for example, work backwards to first choose B such that (n, 6, - (1+ S 10-3- 6, and then choose the noise scale a such S (1-10- -8, using aforementioned privacy accounting libraries. Notice that our use of Proposition 3.2 likely not the optimal approach to account for the batch truncation. We do not optimize this further because we find that this approach already provides very minimal degradation to the choice of a for modest value of B relative to b. A more careful analysis could at best result in a slightly smaller B, which we do not consider as significant; see Figures 3 and 4 for more details.
that max (Py p(p). (2p
Privacy analysis of ABLQ Obtaining the exact privacy guarantee for ABLQq has been an open problem in the literature. Our starting point is the approach introduced by Chua et al. [2024] to prove a lower bound in the single epoch setting. Let the input space be X = [-1, 1]. the (non-adaptive) query method A that produces the query (5 = x, and consider the adjacent datasets:
(z1 -1, -I,,..,,n In-1 = In 1) and x' = (.1 = -1, -....., In- - 1, In = =1.
Recall that the number of epochs is F = bT/n and the number of steps per epoch is S = n/b. By considering the same setting, it is easy to see that the distributions U ABLQs (x) and
V = ABLQ.s (x') are given as:
U E. W((6 1 1+ 1
and V Σ 1/4 -V(-b 1 fe,
Also implicit in prior work [Koskela al., 2020].

---

where fo E R² is the sum of basis vectors ΣE-1 CEs+e, and 1 denotes the all-1's vector in IR". Basically, fa is the indicator vector encoding the batches that the differing example gets assigned to; in persistent shuffling. an example gets assigned to the sth batch within each epoch for a random s E (1,...,S) S). Shifting the distributions by b and projecting to the span of (fa : E [S]) does not change the hockey stick divergence De= (U [V), hence we might as well consider the pair
U² E.=1 N((2EE,, Is)s and : Exn NN(VEE, I²)))
By scaling down the distributions by v on all coordinates we arrive at the following pair:
Ps+ Σ. (2e,, T and Qs- E. Ne 1
(1)
The pair (Pso, Qs:) is essentially same as the pair obtained by Chua et al. [2024], with replaced by a/ a/VE, and we get the following:
Proposition 3.4. For all a > 2 0 and all valid n. T, it holds that
(E) 2 max(De (Ps 112=> De (Qs (P=))}
Following Chua et al. [2024], can obtain lower bound as 6g (E) Ps (T) c Qgo (T) for any I, and in particular, we consider events of the form I'c == {w E R mmx, W/ > C} for various values of C. Pso (Tc) and Qs- (Ic) are efficient to compute
and Thus, using Proposition 3.4, get that
Pso (Tc) 1 1
C-2 l/vVE)
8-1
= = 1-
C-1
$ (0=0 c S-1
a/VEE
a//VE)
(/VEE
Theorem 3.5. For all 0, O, and all valid b, T. it holds that
os (E) 2 sup Pso (Tc) Qs (Tc).
CER
Privacy analysis of ABLQ Our starting point for providing a lower bound on ōgo (E) is the pair (Ps, Qs) as defined below that provides a lower bound in the case of a single epoch.
Ps = و NN(e,,, o2) and Qs -S B -N(e,,
ABLQso is an E-fold composition of the single-epoch mechanism. Hence by composition of dominat- ing pairs, it follows that (g) 2 max( (Pso [[ D& (Qsa (Pso) }}, where Pst = PS and Qso = Q However, it is tricky to directly identify an event for which the lower bound Pso (T) e Qso (T) is non-trivial and Pso (T), Qso (T) are easy compute. So in order to lower bound Der (Pso l1Qso), below we construct pair (Ps, Qs) of discrete distributions such that (Ps, Qs) (Ps. Qs) and thus (Pso, Qsc)= (P F)
For probability measures P and Q over measurable space Ω, and finite partition' & (GI...., GTn) ) of Ω. we can consider the discrete distributions pe and Q defined over (1....,m}
such that pd (i) = P(G,) and Q (i) Q(G.). The
property of DP implies:
Proposition 3.6 (DP Post- Post-processing [Dwork and Roth, 2014]). For all partitions & of Qt it holds that (P.Q) >
We construct the pair (Ps. Qs) by instantiating Proposition 3.6 with the set G = (Go, GI...., Da....,,G+4l. parameterized by a sequence C₁ .... < Om of values defined as follows: Go = {w E R max, W, S C1), 3. G3 == {w E IR ; C. < max, w. < C.+1 } for S i < m and Em+1 = {w E T S, Cm < max, W. in other words, Go = R x Tc, G. Tc. Tem., for 1 < m and Gm+1= T
Theorem 3.7. For all a > 0, 2 O, all valid n, b, T, and any finite sequence C1, Om of values used to define Ps. Qs as above, it holds that
(E) Dex Dec (P 100 Dec (Q | }} G 's pairwise disjoint and G =Ω.
7

---

Map Add weight and sample batich incioes
Reduce
Map Truncatle
Group
Batch
Batch
% Wetul
Random subset of two examples sampled.
Sertu
Batch
Batch
Ng wiwl
Randlom
%
exampples
%
whol
%
Batch
Batch
Training Examples
Dummyy exeemple with weight O lsaaieed
Figure 2: Visualization of the massively parallel computation approach for Poisson subsampling at scale. Consider 6 records 21..... sub-sampled into batches with a maximum batch size of B The Map operation adds "weight" parameter of all examples, and samples indices of batches to which each example will belong. The Reduce operation groups by the batch indices. The final Map operation truncates batches with more than examples (e.g., batches 1 and 3 above), and pads dummy examples with weight O in batches with fewer than B examples (e.g., batch 4 above).
We use the ap_accounting library [Google's DP Library,, 2020] to numerically compute lower bound on the quantity above, using PLD. In particular, we choose Cj and Cm such that Ps(Go) and (G(Gm+1) are sufficiently small and choose other C,'s to get a sufficiently fine discretization of the interval between C1 and Cm.
An illustration of these accounting methods is presented in Figure which demonstrates the signifi- cant gap where the optimal a for dynamic/persistent shuffliigg is significantly larger than compared to Poisson subsampling, even when using an optimistic estimate for shuffling as above. We provide the implementation of our privacy accounting methods described above in an iPython notebook hosted on Google Colab, executable using the freely available Python CPU runtime.
4 Experiments
We compare DP-SGD using the following batch sampling algorithms corresponding noise scales:
Deterministic batches (using nearly exact value of (E, 6) via Theorem 3.1),
Truncated Poisson subsampled batches (using upper bound
(e, 6) via Theorem 3.3), Persistent shuffled batches (using lower bound on o (c, 8) via Theorem 3.5), and
Dynamic shuffled batches (using lower bound go (e, via Theorem 3.7).
As a comparison, we also evaluate DP-SGD with dynamic shuffled batches, but using noise that an upper bound pe, 8) (with no truncation, i.e. B = oc), to capture the incorrect, but commonly employed approach in practice. Finally, in order to understand the impact of using different batch sampling to model training in isolation, compare models trained with SGD under truncated Poisson subsampling, and dynamic and persistent shuffling without any clipping or noise. We use massively parallel computation Rap-Reduce operations [Dean and Ghemawat, 2004]) generate batches with truncated Poisson subsampling in scalable manner as visualized in Figure 2; the details, with beam pipeline implementation, is provided in Appendix A.
'In our evaluation, we choose C1 and C., to ensure Ps(Go) be equally spaced in between Ci and C... with a gap of A o where A is the desired discretization of the PLD. This heuristic choice is guided by intuition that privacy loss is approximately linear max: zz/o², and thus the chosen gap means that this approximate privacy loss varies by A between huckets.
We chose other C,'s to
attpe::/ //colab. research eeeearch.goggle.. con/drive/ hiteeeeeevvaaaaa http:///wwccoooeeeeooooooooooao.

---

5.16
0.827
5.700
14
0.892
2.75
03323
5.700
seccontinng
03333
0
0.797
5" accourting!
[UBI
03
0.350
0,10
02222
3.4
00387
2
Batch
0.19
122
1356
1.00
PIUZI
2200
175
0.16
5" (P accoouniinng
1002
(UB)
1.00
1101
[-Faaett)
0.00
215
21
251
21
Batcn size
Batch
Figure 3: AUC (left) and bounds ds values (middle) for = 5, = 2.7 2.7.100 1 and using 1 epoch (top) and epochs (bottom) of training on a linear-log scale; AUC (right) is with non-private training.
We run experiments the Criteo Display Ads pCTR Dataset BaattnBtttttte Tien, 2014], which contains around 46 million examples from a week Criteo ads traffic. Each example has 13 integer features and 26 categorical features, and the objective is to predict the probability of clicking on an ad given these features. We use the labeled training set from the dataset, split chronologically into a 80% 10%%/%%%10%% partition of train/validation/test sets. We use the binary cross entropy loss and report the AUC on the labeled test split, averaged over three runs with different random seeds. These plotted with error bars indicating a single standard deviation. We include more details about the model architectures and training in Appendix B.
We experiments varying the (expected) batch size from 024 to 262 144, for both private training with (a = 5, 8 = 2.7
and non non-private training and with 1 or epochs. We plot the results in Figure 3. As mostly expected, observe that the model utility generally improves with smaller σ. Truncated Poisson subsampling performs similarly to dynamic shuffling for the same value of a. although it performs worse for non-private training. The latter could be attributed to the fact that when using truncated Poisson subsampling, a substantial fraction of examples are never seen in the training with high probability. However, this does appear significantly affect the private training model utility for the range of parameters that we consider, since we observe that truncated Poisson subsampling behaves similarly dynamic shuffling with noise scale of (e, d) (the values of a for "p" and "SO (P accounting)" visually overlap in Figure 3; the values for P are only negligibly larger, since it accounts for truncation). Truncated Poisson subsampling performs better when compared to shuffling when the latter using our lower bound on so (e, 6), which suggests that shuffling with correct accounting (that is, with potentially even larger σ)) would only perform worse.
We also run experiments with a fixed batch size 65 536 and varying E from to 256, fixing ó = 2.7 10-8, 8. We plot the results and the corresponding values in Figure 4. We again observe that shuffling (with our lower bound accounting) performs worse than truncated Poisson subsampling in the high privacy (low e) regime, but performs slightly better in the low privacy (high e) regime (this is because at large e the noise required under Poisson subsampling is in fact larger than that under shuffling). Moreover, we observe that shuffling performs similarly to truncated Poisson subsampling when we use similar value of a, consistent with our observations from Figure 3.
Finally, as comparison, we compute the upper bounds on ss 8) via the privacy amplification by shuffling bounds by Feldman et al. [2021]. We find that these bounds tend to be vacuous in many regime of parameters, namely they no better than O),, which is clearly upper bound on (E. Details are provided in Appendix C.
'The expected number of examples that approaches e in the limit as b/n 0, for tixed number of epochs E' 6I Ul/n.
used even once during training is at least (1 L)T, which

---

PIUB)
3
S accounting)
5" (LB)
3730
10
D (-Exact)
PUB)
8.70
5" accounting)
S" (LB)
10"1
3.700
(-Exact)
15
64
120
255
20
54
125
259
10
P(UB)
S (P (Pacountinn)
0.79
(LB)
S" (LB)
(UB)
0.77
accounting
8" (LB)
17 (-Exact)
0.75
Figure 4: AUC (left) and values (right) with varying fixing d = 2.7 10 and using (top) 1 epoch and (bottom) 5 epochs of training. a is in log scale to highlight the differences at high E.
Conclusion
We provide new lower bounds on the privacy analysis of Adaptive Batch Linear Query mechanisms, under persistent and dynamic shuffling batch samplers, extending the prior work of Chua et al. [2024] that analyzed the single epoch case. Our lower bound method continues to identify separations in the multi-epoch setting, showing that the amplification guarantees due to even dynamic shuffling can be significantly limited compared to the amplification due to Poisson subsampling regimes of practical interest.
We also provide evaluation of DP-SGD with various batch samplers with the corresponding privacy accounting, and propose an approach for implementing Poisson subsampling at scale using massively parallel computation. Our findings suggest that with provable privacy guarantees on model training, Poisson-subsampling based DP-SGD has better privacy-utility trade-off than shuffling- based DP- SGD in many practical parameter regimes of interest, and in fact, essentially match the utility of suuffling-bsed DP-SGD at the same noise level. Thus, we consider Poisson-subsampling based DP-SGD as viable approach for implementing DP-SGD at scale, given the lower bound on privacy analysis when using shuffling.
Several interesting directions remain be investigated. Firstly, our technique only provides lower bound on the privacy guarantee when using persistent / dynamic shuffled batches. While some privacy amplification results known [Feldman et al., 2021, 2023], providing tight inon-vacuous upper bound on the privacy guarantee in these settings remains an open challenge. This can be important in regimes where shuffling does provide better privacy guarantees than Poisson subsampling.
Another important point to note that persistent and dynamic shuffling are not the only forms of shuffling used in practice. For example, methods such tf. data. Datasstt shuffl le or torchdata. datapipes....... wtw.ai.......eleeeee.....e provide a uniformly random shuffle, only when the size of its "buffer" is larger than the dataset. Otherwise, for buffer size b, returns random record among the first records, and immediately replaces it with the next record ((b + 1)th in this case), and repeats this process, which leads an asymmetric form shuffling. Such batch samplers merit more careful privacy analysis.
Acknowledgements
We would like to thank Charlie Harrison and Ethan Leeman for valuable discussions, well as anonymous reviewers for their thoughtful feedback that helped improve the quality of the paper.
10

---

References
Martín Abadi, Andy Chu, lan J. Goodfellow, H. Brendan McMahan, Πly Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In CCS, pages 308-318, 2016.
Jason M. Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. In NeurIPS, 2022.
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differen- tially private BERT. In EMNLP (Findings), pages 6481-6491 2022.
Meenatchi Sundaram Muthu Selva Annamalai. It's our loss: No privacy amplification for hidden state DP-SGD with non-convex loss. CoRR, fbss/2007.06494 2024.
Apache Beam. BtRth:tss://baa hatpp///aaaaaaaaaaaaaea.aa
Apache Flink. URL https://flinkk.cecm/// awwche..ccccpppaoooao
Apache Spark. URL https://spark:: https://spark.apache apache..cccccceco
Borja Balle and Yu-Xiang Wang- Improving the gaussian mechanism for differential privacy:
Analytical calibration and optimal denoising. In ICML, pages 403-412, 2018.
Borja Balle, Leonard Berrada, Soham De, Sahra Ghalebikesabi, Jamie Hayes, Aneesh Pappu, Samuel L Smith, and Robert Stanforth. JAX-Privacy: Algorithms for preaecypreserring ma- chine learning in JAX, 2022. URL http: /ttp::///iiie gighhb...... com/ www.:/ooogeeddemmnineeee
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. In NeurlPS, pages 38305-38318 2022.
Dingfan Chen, Tribhuvanesh Orekondy, and Mario Fritz. GS-WGAN: A gradient-sanitized approach for learning differentially private generators. NeurlPS, pages 2673-12684, 2020.
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. How Private is DP-SGD? In ICML, 2024.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L. Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. CoRR, 1aw/2204.13650 2022.
Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI, pages 137-150, 2004.
Tim Dockhorn, Tianshi Cao, Arash Vahdat, and Karsten Kreis. Differentially private diffusion models. TMLR, 2023.
Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. CoRR, Tttps/905.02233 2019.
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. PoPETS, 2022(4):552-570, 2022.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor: Comput. Sci., 9(3-4):211-40) 2014.
Vitaly Feldman, 1lya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In FOCS, pages 521-532, 2018.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In FOCS, pages 954,964, 2021.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. In SODA, pages 4966 4981, 2023.
Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Faster privacy accounting via evolving discretization. In ICML, pages 7470-7483, 2022.

---

Google Cloud Dataflow. URL htttttt:://coot google..oogo.ooooooooooo..oo.... dam/datallow.
Google Colab. URL https://colalt resaerrrc
Google's DP Library. DP Accounting Library. https://githin htwpttthu..oomeeeeeeeeeeeeeeee google/ conm/oogle//
differential
sesffrettiall-ppvvvccrrreree privacy/treeeeeeeeeeeepeee http://ttewemaaaptttttooo//////t httpr/hoo/dpacccounningg 2020.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In
NeurlPS, pages 1631-116423 2021.
Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. Exploring the limits of differentially private deep learning with group-wise clipping. arXiv preprint arXiv:2212.01539, 2022.
Timour Igamberdiev, Doan Nam Long Vu, Felix Künnecke, Zhuo Yu, Jannik Holmer, and Ivan Haber- nal. DP-NMT: Scalable differentially-priiee machine translation. In EACL (Demonstrations)) pages 94-105,20 2024.
Olivier Chapelle Jean- Baptiste Tien, joycenv. Display advertising challenge, 2014. URL https:
//kaggle. cwm/ http://ei....oerrrrieodddipp///e challenge.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. ICML, pages 5213-5225, 2021.
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. In AISTATS, pages 2560-2569, 2020.
Christian Janos Lebeda, Matthew Regehr, and Gautam Kamath. Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition. CoRR, abs/2405.20769, 2024.
Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? Tight bounds for r-fold approximate differential privacy. In CCS, pages 247-264, 2018.
Microsoft. A fast algorithm optimally compose privacy guarantees of differentially private (DP) mechanisms to arbitrary accuracy. https : : //github. com/mi http:/mmicooooo///poooocooo wtwpro/ssottppaccccotttaaaeeeeee accountant, 2021.
Ilya Mironov. Rényi differential privacy. In CSF, pages 263-275, 2017. 2017.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ML: A practical guide to machine learning with differential privacy. JAIR, 77:1113-1211, 2023.
Lukas Prediger and Antt Koskela. Code for computing tight guarantees for differential privacy. Btt.au....o/DPPaae/PP/LLLI
Acc.D--cccuttant 2020.
David M. Sommer, Sehastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. PoPATS, 2019(2):245-66) 2019.
Xinyu Tang, Ashwinee Panda, Milad Nasr, Saeed Mahloujifar, and Prateek Mittal. Private fine-tuning of large language models with zeroth-order optimization. CoRR, abs/2401.04343, 2024.
Tensorflow Privacy. URL poocs/pythonmtt_prvaaaee
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). CoRR, abs/201 1. 1660, 2020.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. CoRR, 122999 2021.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In A/STATS, pages 4782-4817 2022.
12

---

A Massively Parallel Implementation of Truncated Poisson Subsampling
We massively parallel computation generate batches with truncated Poisson subsampling in scalable manner. Given the imput parameters b. B, T, and we first compute the maximum batch size B such that (n, b, B) T (1 E²) I 10 10- 8. For each example in the input dataset, we generate a list of batches that the example would be in when sampled using Poisson subsampling. While a naive implementation would sample T Bernoulli random variables with parameter b/n, this can be made efficient by sampling the indices of the batches containing the examples directly, since the difference between two consecutive such indices distributed as geometric random variable with parameter b/n. We then group the examples by the batches, and subsample each batch uniformly, without replacement, to obtain batch size most B. For batches with size smaller than B, we pad the batch with examples such that every batch has size B. In order to differentiate the padding examples from the non-padding examples, we add weight to all the examples, where non-padding examples have weight and the padding examples have weight O. During the training, we use weighted loss function using these weights, such that the padding examples do not have any effect on the training loss.
We include a code snippet for implementing truncated Poisson subsampling using massively par- allel computation. This is written using Apache beam [Apache Beam] in Python, which can be implemented on distributed platforms such as Apache Flink, Apache Spark, Google Cloud Dataflow.
import apache beam beam import numpy as np import tensorflow as
class PoissonSubsample (beam. PTransform):
n""Generate batches of ewamp les using possson subsampling.
A Attributes:
batch_sizes Namimun batch size.
num, batches: Number of batches.
subsampline hiappl..o...bsssty..... Probability of sampling each example in each batch.
sample pople_stee size: Number of samples to sample le at a time.
ded init__
self, max baacbaaaaeeeeeeesseesassaaaaasee int, num_batches: int, subsampling..robbbbiigg float, sample_size: int, ):
self. self._max, max__atthh_siieeeeeeee__eettt___ max_batch_eize
_elft__mm_batches
batches
self self._subsee .ts.saaamlliigg.roobllltt
subsamplingg.rrobbbllity
self welf._sample_stte self self._rng np. row.ra. default_rng()
sample_size
def get_batchh_ateeeeeeeeeeeeeee baatch__ndiceessse11))
"*"Betrrns the indices of the batches that an ezanple le is en.
Assuming that enample is samples in each batch using poisson subsampling return the list of indices the batches that the enample is nen
bargest_batchl index =
batch_indices np. array ([])
if self self._ batch_indice
=- 0.0:
while Jargest_batch_ing
selff_num_bat batches:
Sample batches using geometric distrébution
geometric_samples = self geometric(
p=self.. sheelf__ubbaane www.eeeanlnggg.rrbbbbbbae size=self._sande sample_mampeepppeeeeee
13

---

batch_indices concatenatee(
ibatch_ bargest_batch_indee index mpp.cumeumueeemmttttrceeee.a
largest_ ceatt__btch___aee index batch indices[-1]
return (ttchh.iniieeebbacch..h. indices self half.__mm_bbatchee batches]
def _add__ padd_naddin batch):
"*"Returns batch padded to man, batch_ size with padding enamples.
Pads smput batch size man, batch_ size by adding padding cxamples. The padding ezamples lea are specified by addsng a weight to the ezamples, where padding ezaeples have weight and non-padding enamples have weight 1.
Args:
batch: A tuple of (batch, id, 1sst of ezanples)
batch_id, examples batch
examples = list
(ex(exallee) self. maaf___aa_bbachhaat size:
madding_exampaa
train t.a.i.. Example()
baddinggexample.coppp
padding_extn example. features .eature. feature ('weight '] 'I ifloat_list value[:] [o.0]
examples. extend(
[padding_exaplle (self batch size len(exapplea)
return (batch_id, examples)
def expand pcoll):
def snberate_batch_tte (cmortt
Convert to paárs consisting of (batch id, ezample)
for batch_id in self. self. half.get_batch_ite indices))
yield (int (batch_id), example)
def add__eights (example):
Add weight with value to indicate non-padding ezamples
veighted_ CopyFrom(example weighted_exane weighted_ example caammle.featte return veighted_exanple
tf tr.itriin.FF (xample))))
feature ('veight') 'I float_ list. value[] [1.0]
Croup elements into batches keyed by the batch id grouped_pcoll
pcoll
'Add weights' beam
'Key by batch id' >> beam. FlatMap (generate_ hatmmrrat_bbath_eieee batch_ids)
'Sample max_batch_eize elements per batch'
bean. combiners. Sample. Saample.Fixedeee FixedSizePerKey baneel.._mx_bbaccheeeeee
Add padding' beam. Map(eel.. settseeffd_ddddeeeeeeeeeeeed _adddiddding))
return grouped_pcoll
B Training details
We use a neural network with five layers and ~-8M parameters as the model. The first layer consists of feature transforms for each of the categorical and integer features. Categorical features mapped into dense feature vectors using an embedding layer, where the embedding dimensions are fixed at 48. We apply log transform for the remaining integer features, and concatenate all the features together. The next three layers are fully connected layers with 598 hidden units each and a ReLU activation function. The last layer consists of fully connected layer which gives scalar logit prediction.
We use the Adam or Adagrad optimizer with base learning rate {0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1), which is scaled with cosine decay, and tune the norm bound
14

---

C' E {1,5, 10.100000 50}. For the experiments with varying batch sizes, we use batch sizes that are powers of between 1 1024 and 262 144. with corresponding maximum batch sizes B in (1 3288, 2 469, 4 681, 9 9007, 17 520, 34 355, 67 754, 134 172, 266 475475). For the experiments with varying e, we vary 8 as powers of 2 between and 256, with batch size 65 536 and corresponding maximum batch sizes B in {67 642, 67 667, 725, 67 841, 68 059, 68 449, 69 106, 70 156, 71 760). With these choices the maximum batch sizes, the values for truncated Poisson subsampling are observe from the nearly overlapping curves in
only slightly larger than without truncation, Figure and Figure 4. The training is done using NVIDIA Tesla PI00 GPUs, where each epoch of training takes 1-2 hours single GPU.
C Privacy Amplification by Shuffling
We evaluate the upper bounds on as(e, 6) via privacy amplification by shuffling results of Feldman al. [2021], as applied in the context of our experiments in Figure 3. In particular, their Proposition 5.3 states that if the unamplified (Gaussian) mechanism satisfies (eo, 6 )-D. then ABLQs with T steps (in single epoch setting) will satisfy (5, O(e dD for any 17 E [0. 1] and
E = ca-aae (Ver (Veroog(//)) log(1/1) vT
They also obtain tighter numerical bound with implementation provided in GitHub repository.?
We evaluate their bounds in an optimistic manner. Namely, for given value of ō, we compute an optimistic estimate on ε compared to the bound above by setting 6 = 6/n and setting en (do), and set = 5 (note that this is optimistic because the above proposition requires setting = 7 + dg)))))) which is larger than the we are claiming). We use the numerical analysis method provided in the library by Feldman et al. [2021] to compute as (via binary search top of their method to compute an upper bound on ES), and plot in Figure 5, along with the lower bound øs obtained by Chua et al. [2024], well dpp We find that the bounds by Feldman et al. [2021] are vacuous for batch sizes 048 and above, in that they are even larger than the bounds without any amplification.
1.3
1.2-
5
1.1
1.0
0.9
(Feldman at.)
(-Exact)
0.8
210
211
212
2
21
2
2
2
2
Batch size
Figure 5: Comparison of an optimistic estimate of the upper bound on from Feldman et al. [2021] against the lower bound as in Theorem 3.5 and op.
D a with varying epochs
We include a comparison of the values for varying numbers of epochs, to show how the same trends hold beyond the and epoch regimes.
'bttss//gituub..om/app//ee shuftling- amplification -haiiaaiiittiiinnaaaiiicccooooon
15

---

P(UB)
(P accounting) s" (LB)
(-Exact)
10
10
35
20
Number epochs
Figure 6: ag values with varying numbers of epochs, fixing 5, = 2.7 10-8, and batch size 65 536.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims in the abstract are summarized under "Our Contributions" (Sec- tion 1.1) and described in detail in the rest of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
We discuss limitations and future directions of this paper in Section 5.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to vi- olations these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence performance the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
16

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might used by review- ers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proofs all statements are included either the main body, or the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the thcorems, formulas, and proof's in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
All experimental details are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless whether the code and data are provided or not.
If the contribution a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending the contribution, reproducibility
be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might specific model and empirical evaluation, may be necessary
suffice, or if the contribution to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
17

---

(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e-g., large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The source code for privacy accounting is provided in a Google Colab and beam pipelines for implementing Poisson subsampling at scale are provided in Appendix A.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https ptttpa://nips cttppblic/cpp//c////cccc guides Satps//ooeeSuuSissteeeeee wwwsssssssslieeeeeeoeeoeesssesee for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wwwssssoiooiyyyy for more details.
//nips. wwtpcc/pppppcppeeceeeeceoe http//uuudee//eeeuiieeeeeeeeee
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details are provided in Section 4 and Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report eиror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
The training experiments have been repeated independently few times and error bars are provided. However, due to significant cost of the experiments, we limit ourselves to only small number of independent runs. These details are described in Section 4.
Justification:
18

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric eπrоr bars that would yield results that are out of range (c.g. negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification:
The details on the compute resources are in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experi- mental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics bttps::/neurr/ cc/public/Ehhiiicideeeii.i
Question:
Answer: [Yes]
Justification: The paper conforms the NeurIPS Code Ethics as it only uses experiments on publicly available datasets, and does not use any crowdsoureing or human subjects.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [No]
19

---

The research work is about differentially private training of ML models. We do not see anticipate any specific positive or negative societal impacts of this research, beyond the impacts of differential privacy itself. So we do not feel the need to discuss this in the paper.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimesss considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make a best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or datasct.
The authors should state which version of the asset is used and, if possible, include a URL,
The name of the license (c.g.. CC-BY 4.0) should be included for each asset.
20

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi snperswithcode thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/ccode/modeel as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not rely on any crowdsourcing with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not rely on any crowdsourcing with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "8BYiMMGJPB", "reviewer": "Reviewer_vHjL", "summary": "This paper investigates the utility of models trained with DP-SGD based on previous findings on the gap in privacy guarantee between shuffled batch sampling (commonly used in practice) and Poisson subsampling (used in theoretical analysis) for private training. A scalable implementation of Posson subsampling is proposed via truncation and parallelization, provided with lower bounds of the privacy guarantee via multi-epoch ABLQ with shuffling.", "questions": "- The authors mentioned that the Opacus library supports Possion subsampling but might not be used for training on massive datasets. Have the authors tested the implementation from Opacus on the Criteo dataset? If so, how large is a batch it can support (from 1000 to 200,000)? Is this the major obstacle to be included as a reference for Fig.2 and 3?\n- Is the target batch size $b$ still used to average the summed noisy gradients for the truncated Poisson Batch sampler? Could the authors elaborate on how the size of truncated batches would affect the tracking of privacy loss, especially in Theorem 3.3?\n- Line 254 -255, could the authors provide more details on selecting $C_i$ in practice? And what is the computation complexity regarding this part?", "limitations": "See W2,3 and Q1", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- This paper studies the implementation of subsampling with associated privacy accounting in private training and extends the results of ABLQ for multiple epochs.\n- A scalable implementation of Possion subsampling is proposed, provided with lower bounds on its privacy guarantee.", "weaknesses": "- The techniques for extending ABLQ from multi-batch to multi-epoch are straightforward. \n- It is difficult to distinguish from the existing results of Chua et al. [2024], given much of the material in Sec. 2 and Sec. 3 overlaps and is sometimes verbatim.\n- Different types of batch sampling with different privacy accounting are evaluated. Still, all of them underestimate the privacy loss and cannot rigorously reflect the model utility under the claimed $(\\epsilon, \\delta)$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments.\n\n> techniques for extending to multi-epoch are straightforward. [Similar to Reviewer 1Uvo]\n\nWhile it may seem that our privacy analysis used some standard techniques (discretization, post-processing and PLD accounting), it was a priori unclear if such a simple method would be effective at providing strong lower bounds, let alone what such a method (e.g. the choice of discretization sets) would be. We would like to note that the prior work of [Chua et al](https://arxiv.org/abs/2403.17673) explicitly notes in Section 5, that _[their] approach is limited to a “single epoch” mechanism ... Extending [their] approach to multiple epochs will be interesting._ Moreover, while they are primarily focused on theoretical analysis, we also study practical implementations and evaluations on real world problems to verify the empirical feasibility of the proposed methods.\n\n> material overlap in Sec. 2 and 3.\n\nSection 2 consists mainly of definitions (some standard and some from [Chua et al](https://arxiv.org/abs/2403.17673)), resulting in the overlap; please note that we have cited them in all relevant places. Nevertheless, thank you for bringing this to our attention and we will keep this in mind as we revise the paper to highlight our contributions better.\n\n> Different types of batch sampling with different privacy accounting are evaluated ... all of them underestimate the privacy loss and cannot rigorously reflect the model utility under the claimed $(\\epsilon, \\delta)$.\n\nWe would like to clarify a possible misunderstanding here, that for Poisson subsampling based DP-SGD, we use the `dp_accounting` library that _overestimates_ the privacy loss, and for Shuffle based DP-SGD, our method _underestimates_ the privacy loss. So the way to interpret our results is that: whenever Poisson subsampling based DP-SGD out-performs Shuffle-based DP-SGD, this would hold even if we use the optimal accounting for each method.\n\n> Have the authors tested the implementation from Opacus on the Criteo dataset?\n\nUsing the implementation from Opacus requires efficient random access to all the data points (e.g. loading the entire dataset in memory), which is not always feasible depending on the machine and configuration, given that the Criteo dataset takes 49GB of storage. We believe such a comparison does not provide too much scientific value, because for small datasets that can fit in memory, the Opacus solution and our method would perform similarly because they are mathematically equivalent. But in contrast to our methods, to the best of our knowledge, it is not straightforward how to scale Opacus to larger datasets.\n\n>Is the target batch size b still used to average the summed noisy gradients for the truncated Poisson Batch sampler? Could the authors elaborate on how the size of truncated batches would affect the tracking of privacy loss, especially in Theorem 3.3?\n\nWe average the summed noisy gradients using the expected batch size; in any case, this is simply a scaling factor that can be assimilated in the learning rate, hence it is not important whether we normalize by the expected or maximum batch size. There is a privacy-vs-computation tradeoff in the choice of maximum batch size $B$ in the Poisson sampler: Taking $B$ to be large gets us closer to the privacy guarantee of the (untruncated) Poisson sampler, but increases the computation cost, since the batches are now larger (even if they contain dummy values with zero weight).\n\n> Line 254 -255, could the authors provide more details on selecting Ci in practice? And what is the computation complexity regarding this part?\n\nIndeed, while any choice of $C_i$’s are valid, there is an accuracy-vs-computation trade-off, in that, making $C_1$ smaller, $C_m$ larger and adding large number of intermediate $C_i$’s improves the accuracy of the lower bound at the cost of increased computational complexity.\n* As we note in the paper, we choose $C_1$ to be small enough, and $C_m$ to be large enough so that $P_{\\cal S}(G_0)$ and $P_{\\cal S}(G_{m+1})$ to be small enough. In particular, we chose the values to ensure $P_{\\cal S}(G_0) + P_{\\cal S}(G_{m+1}) \\le e^{-40}$.\n* We chose $C_i$’s to be equally spaced in between $C_1$ and $C_m$ with a gap of $\\Delta * \\sigma^2$, where $\\Delta$ is the desired discretization of the PLD. This is a heuristic choice guided by the intuition that we would like to discretize in buckets such that the privacy loss changes by $\\Delta$, and since the privacy loss is approximately given as $\\max_t x_t / \\sigma^2$, the chosen gap means that this approximate privacy loss varies by $\\Delta$ between buckets.\n\nThese details are present in the implementation provided in the Colab link in the paper. But we will highlight these details more prominently in a revision.\n\nPlease let us know if there are any further questions we can clarify, and if we have satisfactorily addressed the concerns of the reviewer, we kindly ask the reviewer to revisit the rating.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gOaU85Nlih", "reviewer": "Reviewer_1Uvo", "summary": "The paper focuses on practical implementations of DP training of ML models at scale in the multi-epoch setting. The contribution is two-fold: the paper gives a rigorous analysis for a practical version of Poisson subsampled DP-SGD where the batch size is upper bounded, and proposes lower $(\\varepsilon,\\delta)$-bounds for the shuffled Gaussian mechanism. Both of these contributions require a careful theoretical analysis which the paper succeeds in carrying out such that the bounds are sharp: there is no big slack in the approximative Poisson subsampling upper bound and the lower bounds is able to illustrate that the shuffling mechanism generally leads to a worse privacy-utility trade-off than the Poisson subsampled Gaussian mechanism. So the message becomes clear: although the shuffling + disjoint batch training is practical, the practical version the paper proposes will likely lead to a better privacy-utility trade-off. The paper builds upon the paper (Chua et al., ICML 2024) and borrows several results from it.", "questions": "- You mention that the analysis for the shuffled Gaussian mechanism is an open problem. Why do you think this is an important open problem if the lower bounds for the shuffled Gaussian mechanism already indicate that DP-SGD give much better privacy-utility trade-off? In which scenarios would the upper bounds be useful?\n\n- Why do you only consider the Poisson subsampling? Is there something particular in the subsampling without replacement that makes it less suitable to the large scale setting? In that case you would not need to have those approximations that you carry out to limit the batch size.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Clear message and a well-written paper on a timely topic. DP training of ML models is becoming more popular and these practical aspects need to be addressed.\n\n- Elegant theoretical analysis for the approximative Poisson mechanism and for the lower bounds of the shuffled Gaussian mechanism.", "weaknesses": "- The paper heavily builds upon the previous work by Chua et al. (ICML 2024), and the novelty is relatively thin, although the paper succeeds in delivering a clear message.\n\n- The privacy amplification by iteration analysis - type of analysis is not mentioned. Although the current analyses in that line of work are only applicable to convex problems, they give $(\\varepsilon,\\delta)$-DP bounds for e.g. noisy cyclic GD (Bok et al., ICML 2024) that lead to models whose privacy-utility trade-off is competitive with the DP-SGD trained models (see e.g. experiments by Bok et al.).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments.\n\n> novelty over prior work [Similar to Reviewer vHjL]\n\nWhile it may seem that our privacy analysis used some standard techniques (discretization, post-processing and PLD accounting), it was a priori unclear if such a simple method would be effective at providing strong lower bounds, let alone what such a method (e.g. the choice of discretization sets) would be. We would like to note that the prior work of [Chua et al](https://arxiv.org/abs/2403.17673) explicitly notes in Section 5, that _[their] approach is limited to a “single epoch” mechanism ... Extending [their] approach to multiple epochs will be interesting._ Moreover, while they are primarily focused on theoretical analysis, we also study practical implementations and evaluations on real world problems to verify the empirical feasibility of the proposed methods.\n\n> privacy amplification by iteration is not mentioned.\n\nUnderstanding when privacy amplification by iteration applies remains an interesting direction, but as of now there is no evidence that it can provide any improvements in the general (non-convex) setting. In fact, a recent [work](https://arxiv.org/abs/2407.06496) suggests that such an improvement might not be possible for general non-convex losses. We will include a discussion on the same in a revision.\n\n> Importance of upper bounds for the shuffled DP-SGD?\n\nThis would be relevant in a regime where Shuffle-DP-SGD performs better than Poisson subsampling. In this case, we would need an “upper-bound” accounting method to report a correct DP guarantee. But we agree that it is less relevant in regimes where Shuffle DP-SGD has worse model utility.\n\n> subsampling without replacement (Similar point raised by Reviewer k7t2)\n\nSampling without replacement (i.e., sampling fixed-sizes batches uniformly and independently at random) can also be implemented using a variant of the massively parallel computation approach we propose. We did not consider it in our evaluation however since the privacy guarantees of that are worse than that of Poisson subsampling. In particular, as noted in this recent work of [Lebeda et al.](https://arxiv.org/abs/2405.20769), the noise scale required for this method is twice that required for Poisson subsampling. We will revise the paper to include a discussion of this alternative approach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bUG9nQqc7X", "reviewer": "Reviewer_9tRV", "summary": "This paper provides theoretical and empirical analyses of three different DP-SGD minibatch sampling schemes, and also implement an efficient beam pipeline for using Poisson sampling in practice via a truncation-based approach.  Theoretically, they derive new lower bounds for the privacy accounting / noise calibration of shuffling-based DP-SGD, and truncated Poisson-sampling-based DP-SGD.  Empirically, they show (1) for the same noise multiplier, shuffling does better (in terms of AUC) than Poisson sampling and (2) for the same privacy budget, Poisson sampling does better, mainly due to the more favorable privacy accounting.  In one experiment (Fig 3 upper left) they show that shuffling can sometimes be better than Poisson sampling for small epsilon.", "questions": "1) In Fig 2, it seems like P corresponds to  truncated Poisson sampling, but green line corresponds to non-truncated Poisson accounting.  Why do these lines line up in the middle plots then?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* Addresses an important gap in many works on DP-SGD in a principled manner.\n* Clearly demonstrates the benefits of Poisson sampling over shuffling with correct / tight privacy accounting.\n* Shows how to implement Poisson sampling within the typical constraints of an ML pipeline via truncation + padding + offline beam job to order the examples.  This is crucial to get the best privacy / utility trade-offs and formal privacy guarantees in production DP applications.  The shuffling ~=~ sampling approximation may still make sense in research applications.  \n* Experiments compare the methods you'd expect to see (normalized by sigma and normalized by privacy budget).", "weaknesses": "There are a few missing pieces that I think would strengthen the paper and hopefully not require too much extra work:\n\n1) Thm 3.3 uses the bound from Prop 3.2, and may not be the tightest possible result.  Would be good to quantify the gap between Poisson sampling and Truncated Poisson sampling in terms of the noise multiplier you obtain for each, fixing p for Poisson sampling and B for the Truncated Poisson sampling so that the expected batch sizes of Poisson sampling matches the physical batch sizes of truncated Poisson.\n2) There is not enough discussion or analysis on how to configure the Truncated Poisson parameters.  For a fixed physical batch size, privacy budget, and other relevant parameters (number of iterations), can you give a simple procedure to find the best sampling probability to use in terms of the expected signal to noise ratio?\n3) Do the same findings hold up beyond the 1- and 5-epoch regimes? Would be nice to include a comparison where Epochs is varied on the x-axis and sigma is varied on the y-axis (no need to do new experiments on real data which might be very expensive).  \n\nMinor:\n\n4) In plots you should evenly space out the independent variables.  If plotting in log space, evenly space them in log space (e.g., Batch Size = 1024, 2048, 4096, ..., 262144 and epsilon = 1, 2, 4, 8, ..., 16).  Also the legend is a bit small, and shared across plots.  Consider making 1-row 5-column legend spanning or otherwise increasing the font size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments.\n\n> quantify the gap between Poisson sampling and Truncated Poisson sampling\n\nWhile it is likely that our analysis for truncated Poisson sampling is not optimal, it is reasonable enough in practice. The loss due to truncation is very minimal to the privacy accounting as we allocate only $0.1 \\delta$ for the truncation part, as seen by how the noise multiplier for Poisson subsampling with and without truncation are quite similar (seen in Fig. 2, 3). Note that the trade-off here is only between privacy and computation: larger maximum batch size means accounting is closer to (untruncated) Poisson subsampling, at the cost of increased computation during model training.\nThus, the optimal accounting for truncated Poisson subsampling would at best allow us to use a slightly smaller maximum batch size, which would only slightly reduce the computational cost of training. Since this was not central to our work, we did not optimize the analysis to the best possible. Thanks for raising this, and we will consider adding this to the discussion.\n\n> find the best sampling probability to use in terms of the expected signal to noise ratio\n\nWhile we do not optimize this theoretically, this was indeed our motivation for considering different batch sizes in Figure 2.\n\n>  include a comparison where Epochs is varied on the x-axis and sigma is varied on the y-axis\n\nWe provide $\\sigma$ values for different accounting methods in the table below, as well as in a plot in Figure 1 of the attached pdf. Note that the values for the $\\cal P$ sampler are upper bounds, whereas the values for $\\cal S$ samplers are lower bounds. Again observe that the values for $\\cal P$ (truncated Poisson subsampling) are very close to ${\\cal S}^{\\circlearrowright}$ ($\\cal P$ accounting), the latter corresponding to untruncated Poisson subsampling.\n\n| Epochs | $\\cal P$ | ${\\cal S}^\\circlearrowright$ ($\\cal P$ accounting) |  ${\\cal S}^\\circlearrowright$ | ${\\cal S}^{\\diamond}$ | $\\cal D$ | \n|---|---|---|---|---|---|\n| 1 | 0.608 | 0.606 | 1.053 | 1.053 | 1.106 |\n| 3 | 0.643 | 0.642 | 1.181 | 1.825 | 1.916 |\n| 5 | 0.665 | 0.663 | 1.227 | 2.356 | 2.474 |\n| 10 | 0.702 | 0.701 | 1.292 | 3.331 | 3.499 |\n| 15 | 0.730 | 0.729 | 1.334 | 4.080 | 4.285 |\n| 20 | 0.755 | 0.753 | 1.366 | 4.711 | 4.948 |\n\nObserve that the values of Poisson subsampling with truncation are slightly larger than that without truncation.\n\n> evenly space out the independent variables\n\nThanks for the suggestion. We will modify the plots accordingly.\n\n> Why do these lines line up in the middle plots\n\nAs argued above, the additional privacy loss due to truncation of the batch in Poisson subsampling is minimal even with our sub-optimal analysis, and so while the values with and without truncation are not exactly the same, the difference is negligible compared to the scale of the rest of the plot.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tBT1crP9Pr", "reviewer": "Reviewer_k7t2", "summary": "DP-SGD is one of the must common algorithms currently deployed for performing machine learning tasks while maintaining differential privacy. As the \"S\" in its name reminds us, the gradient is not computed over the full dataset at each turn, but instead over a subset sampled from it. The commonly used privacy analysis typically relies on Poisson sub-sampling, whereby each element is independently added to each batch with some constant probability. In contrast, due to technical challenges stemming from the fact the Poisson sub-sampled batch size is not constant, this is typically implemented by first shuffling the full dataset, then batching it into subsequent subsets.\n\nUnfortunately, there is a gap between existing upper bounds on the privacy loss of the shuffle version and those of the sub-sampling. Recently Lynn et al. [1] provided a lower bound on the privacy of the shuffled version, which shows a clear gap between the two settings in some parameter regimes (mainly low local privacy).\n\nThis paper continues and extends [1] work in two ways:\n1. It extends the analysis to multi-epoch setting\n2. It proposes a variant of Poisson sub-sampling with effective constant batch size, by paying a small price in the privacy failure probability $\\delta$\nThe authors also perform several empirical experiments to compare the privacy and accuracy of various versions of private training.\n\n[1] Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. How Private is DP-SGD? In International Conference on Machine Learning, ICML (to appear), 2024.", "questions": "Can the authors add a comparison of the the various privacy analyses to the upper bounds provided by existing literature on general shuffle model, such as the one provided by Feldman et al. [2]?\n\nAdditionally, to the best of my understanding, amplification by sub-sampling a constant size batches without replacement (per sampling)  is will understood, and enjoys privacy guarantees that are comparable to those of Poisson sub-sampling, up to a factor 2, depending on the exact neighboring notion. What is the advantage of the proposed method relative to the WOR sampling option?\n\n[2] Feldman, V., McMillan, A., and Talwar, K. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In FOCS, pp. 954–964, 2021", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "This paper is clearly written, and adds to our understanding of the toolkit one can use when attempting to learn privately. The proposed truncated sub-sampling might prove a useful alternative to the existing commonly used shuffle method.", "weaknesses": "While this work is clearly written and provides useful empirical and theoretical tools, its novelty is somewhat limited.\nAs mentioned, this is a follow-up work to the one by Lynn et al. The extension of their analysis to multi epochs is relatively straight forward, and so is the analysis of the truncated Poisson sub-sampling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful comments.\n\n> add a comparison of the the various privacy analyses to the upper bounds provided by existing literature on general shuffle model\n\nWhile the amplification bounds for shuffling such as by Feldman et al. provide upper bounds, we did not consider it because\n* our focus in this work was primarily to compare _lower bounds_ for Shuffle DP-SGD with _upper bounds_ for Poisson DP-SGD, and\n* in the regime of small noise multipliers, where we see that our lower bound on the noise multiplier of Shuffle DP-SGD is quite close to that of Deterministic (no amplification), these upper bounds on amplification by shuffling have to necessarily be near-vacuous (cannot be much better than deterministic).\n\nNevertheless, this is a valuable point, and we will include at least the noise multipliers obtained via these amplification upper bounds for comparison in a future revision.\n\n> sampling without replacement (Similar point raised by Reviewer 1Uvo)\n\nIndeed, sampling without replacement (i.e., sampling fixed-sizes batches uniformly and independently at random) can also be implemented using the massively parallel computation approach we propose. We did not however consider it in our evaluation however since the privacy guarantees of that are worse than that of Poisson subsampling. Similar to your point, as noted in this recent work of [Lebeda et al.](https://arxiv.org/abs/2405.20769), the noise scale required for this method is twice that required for Poisson subsampling. We will revise the paper to include a discussion of this alternative approach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their thoughtful comments. In the attached pdf, we plot the noise multiplier $\sigma$ values against the number of epochs for different accounting methods, to answer a comment from Reviewer 9tRV.

Meta-review: The main critiques of this paper were that the techniques may not be the most novel, and the contribution may be somewhat modest. Nonetheless reviewers agreed that this is an impactful advance on a very important problem, and thus worthy of acceptance.

In the discussion, Reviewers k7t2 and 9tRV brought up some points that they feel deserve mentioning in the final paper (highlighted in their reviews), and I anticipate the authors will take them into account.
Decision: Accept (poster)