Near-Exact Privacy Amplification for Matrix Mechanisms
Authors: Christopher A. Choquette-Choo
Arun Ganesh
Saminul Haque
Thomas Steinke
Abhradeep Guha Thakurta
Venue: ICLR 2025 Poster (2025)
Keywords: differential privacy
privacy amplification
privacy accounting
DP-FTRL
correlated noise
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We use Monte Carlo sampling to get near-exact privacy analysis for DP-SGD with random batching and correlated noise, while allowing arbitary correlation matrices.

Abstract: We study the problem of computing the privacy parameters for DP machine learning when using privacy amplification via random batching and noise correlated across rounds via a correlation matrix $\textbf{C}$ (i.e., the matrix mechanism). Past work on this problem either only applied to banded $\textbf{C}$, or gave loose privacy parameters. In this work, we give a framework for computing near-exact privacy parameters for any lower-triangular, non-negative $\textbf{C}$. Our framework allows us to optimize the correlation matrix $\textbf{C}$ while accounting for amplification, whereas past work could not. Empirically, we show this lets us achieve smaller RMSE on prefix sums than the previous state-of-the-art (SOTA). We also show that we can improve on the SOTA performance on deep learning tasks. Our two main technical tools are (i) using Monte Carlo accounting to bypass composition, which was the main technical challenge for past work, and (ii) a ``balls-in-bins'' batching scheme that enables easy privacy analysis and is closer to practical random batching than Poisson sampling.

Published as a conference paper ICLR 2025
NEAR EXACT PRIVACY AMPLIFICATION FOR MATRIX MECHANISMS
Christopher A. Choquette-Choo, Thomas Steinke, & Abhradeep Thakurta Google DeepMind
Mountain View, CA, 94043, USA
(cchoquette, steinke, Sthakurta)@yoogle.com
Arun Ganesh
Saminul Haque
Google Research
Department of Computer Science
Seattle, WA, 98103, USA
Stanford University Stanford, CA, 94305, USA
arunganesh@@ooogle..o com
samimulh@stannordd edu
ABSTRACT
We study the problem of computing the privacy parameters for DP machine learning when using privacy amplification via random batching and noise correlated across rounds via a correlation matrix C (i.e., the matrix mechanism). Past work this problem either only applied to banded C, or gave loose privacy parameters. In this work, we give framework for computing near-exact privacy parameters for any graerttraangular, non-nege non-negative C. Our framework allows us to optimize the correlation matrix C while accounting for am- plification, whereas past work could not. Empirically, we show this lets us achieve smaller RMSE on prefix sums than the previous state-of-the-art (SOTA). We also show that we can improve on the SOTA performance on deep learning tasks. Our two main technical tools are (i) using Monte Carlo accounting bypass composition, which was the main batching scheme that enables easy privacy analysis and implementation-i siiiee is closer to shuffling (widely considered practical random batching method) than Poisson sampling.
technical challenge for past work, and (ii) a "balls-in-bing
1 INTRODUCTION
Many recent works have improved the privacy-utility tradeoff of differentially private machine learning via improvements either privacy amplification or how noise correlated across rounds. Privacy amplification
(Kasiviswanathan et al. 2008 Balle & Wang 2018 Erlingsson al. 2019a Balle et al. (020) uses random-
ness in data processing to improve the existing privacy guarantees. Correlated noise (Kairouz et al., 202T]]
Denisov et al. 2022 Choquette-Choo et al. 2022), DP-FTRL, uses the matrix mechanism to add noise in DP training such that the noise added in one round is cancelled out in subsequent rounds. Specifically, if z is i.i.d. Gaussian matrix, independent noise approaches, i.e., differentially private stochastic gradient descent (DP-SGD) clip gradients and add noise z :] in the ith round of DP training; instead, DP-FTRL (C-)))[i;:) as the noise the ith round, where C is carefully chosen "correlation matrix".
Choquette- Choo et al. (024a) showed that one could simultancously obtain the benefits of privacy amplifi- cation and noise correlation, leading class of "banded" C correlation matrices that Pareto dominated
'A square lower-triangular matrix is b-banded, if at most b of the principal diagonals non-zero.

---

Published as a conference paper at ICLR 2025
either alone. However, their amplification analysis only applied to these specific banded matrices, whereas we may want to work with non-banded C due to urility or efficiency concerns (Dvijotham et al., 2024 McMahan al.) 2024). Choquette- Choo et al. (224b) gives an amplification analysis that works with gen- eral (i.e., non- banded) C and is tight in the limit as + O, but for larger values used commonly in DP machine learning, their analysis inherently introduces slack, and can greatly overestimate the true privacy parameter. Both of these works' limitations are due to a reliance on composition theorems. We propose an approach which bypasses composition and in turn avoids both of these limitations simultancously:
In this work, we use Monte Carlo accounting to enable nearly-exact privacy analysis and optimization of these amplified correlated noise mechanisms without any constraint on the structure of the correlation matrices. In turn, we are able to achieve smaller error for prefix sums than past work in various settings, and improve the -tate-of-the--e utility on deep learning tasks, even while using seeoor--eficiien correlation matrices.
This allows to obtain significant amplification benefits for generic C matrices, which were shown to be better than constrained versions in both utility (Choquette- et al. 2022) and memory (Dvijotham et al.) 2024) but cannot yet be combined with privacy amplification in the practical regimes of interest for in DP machine learning. In particular, we first consider the standard objective for correlated noise mechanisms, RMSE of prefix sums (as defined in e.g.. Kairouz et al. (202I); Denisov al. (2022); see Section 1.2). and find that our techniques lead to C' with significant reduction in RMSE over the prior SOTA around 10%. When used train models on the standard CIFAR- 10 benchmark?, the RMSE improvements translate to up to 1 1% absolute accuracy improvements compared to the prior SOTA (Choquette Siequette-Choo et al.) (024a).
1.1 OUR CONTRIBUTIONS
1.1.1 ALGORITHMIC CONTRIBUTIONS
Balls-in-hins minibatching: We propose a more practical sampling scheme that (i) does not require random access to the entire dataset, (ii) achieves much better privacy amplification than the next-best alternative, shuffling, and (iii) enables efficient amplification analysis via Monte Carlo sampling which would otherwise be NP-hard to compute. We are able to implement a practical variant of this sampling scheme that enforces fixed batch sizes (which are required for compatability with modern ML techniques like XLA compilation) for our deep learning experiments.
Near-exact analysis via Monte Carlo: We recognize a common issue with prior amplification analysis of
correlated noise mechanisms, which is their reliance on composition which led to slack for various reasons (see Section 1.2p. We thus show how to use Monte Carlo accounting (Wang et al., 2023) which instead observes that approximate DP guarantees can be written as the expected value of some function of the privacy loss and = (see Section for more details). Because it is easy to do Monte Carlo accounting for the whole matrix Cx + z, we can bypass the need for composition. In turn, we able to obtain near-exact privacy analysis (only paying for the sampling error of Monte Carlo approximation, which can be made arbitrarily small) while supporting general C, improving upon the weaknesses of both the past works.
Optimizing C under amplification: We, for the first time, show how to optimize C to minimize the RMSE under privacy amplification. This remediates a significant issue with prior work which required an expensive grid-search to check the amplified RMSE under all possible configurations (as this required post- hoc analysis after optimization of C, where the optimization did not account for amplification). A crucial
IIt is worth mentioning that accuracy of training on the CIFAR- 10 benchmark with correlated noise has boen highly optimized for over long series of papers (c.g. (Choquette- Choo al. 2022 2024ab). So, any tangible and unconditional improvement is significant.
2

---

Published as a conference paper ICLR 2025
aspect of Monte Carlo accounting that it allows one calibrate the quality of the privacy guarantee based on the computation available, i.e., one can obtain a quick (and less rigorous) parameter by using a small number of MC samples, which can be made rigorous (with appropriate failure probability 5) by increasing the number of samples. So, while optimizing for the C matrices we use fewer MC samples, and when providing the final privacy guarantee with the optimized C matrix, we run it with large number of samples to achieve appropriate convergence of the sampler.
1.1.2 EMPIRICAL EVALUATION
RMSE analysis: We first look at the standard objective for evaluating correlated noise mechanisms, RMSE on prefix sums (formally defined in Section 1.2). We compare the RMSE achieved by matrices amplified using our analysis, and by the previous SOTA of banded matrices and Poisson sampling of ofChoquuette-hhne ct al. (2024a). We demonstrate that because we can directly optimize the correlation matrix for the RMSE under amplification, we can achieve up 10% reduction in RMSE compared to the SOTA.
Empirical evaluation on CIFAR-10: We next use correlation matrices and a computed using our privacy analysis to train a VGG model on CIFAR-IO. We again compare the SOTA of Choquette- Choo et al. (2024)). We show that despite using a weaker sampling assumption, matrices amplified by balls-in-bins batching Pareto dominate the approach of (Choquette- Choo et al. (024a), getting equal accuracy at smaller 8 and giving up to 1 1% absolute accuracy improvements at larger e.
1.2 BACKGROUND AND PRIOR WORK
Here, we summarize prior work and highlight why our contributions above are significant.
There are several forms of privacy amplification, but the two most popular are sampling and shuffling. Poisson sampling forms batches by independently including each example with some probability. Exact analyses for DP-SGD with Poisson sampling are well-known, but Poisson sampling is generally considered impractical (Ponomareva et al. 2023). DP-SGD with shuffling uses multiple passes over a shuffled dataset with fixed batch size. Shuffling is considered more practical, but tight analyses of DP-SGD with shuffling remain clusive because of the dependence between examples.
Privacy amplification:
Correlated noise: DP-SGD uses independent noise, i.c., if the gradients are the rows of matrix x, the gradients used in DP-SGD are the rows of x + z, where is i.i.d. Gaussian noise the same shape x. DP-FTRL instead uses the correlated noise, i.e., uses rows of x + C-1z as gradients, where is a "correlation matrix." By post-processing this has the same privacy guarantees as the matrix mechanism Cx + z. Usually C is chosen to minimize some objective, the most common being the RMSE of prefix sums, given by AC- -I a where A is the lrian-lrra all-ones matrix and the noise multiplier needed for privacy. We give more background on privacy amplification and DP-FTRL in Appendix B
The main hurdle is that privacy amplification analysis usually relies heavily on composition: instead of analyzing the entire training run directly, we compute a privacy guarantee for each round of training separately, and then combine these in a straightforward way to analyze the entire run. However, composition requires that both sampling and noise randomness be independent across rounds and of course noise correlations violates this. Thus, the only two prior works Schoquette-Choo et al.) 2024a b) combining privacy amplification and noise correlation leveraged reductions which significantly reduce the privacy amplification benefits.
Challenges of combining privacy amplification and correlated noise:
Amplified banded matrix factorization only the first b diagonals of C' are non-zero. For b-banded C, they observe that rows i and j of Cx + z are independent if jí jl 2 b. If each example is assigned an index k E {0, 1....b b 1} and then can only
Sroouuette-Choo al., 2024a): The matrix C is b-banded if
3

---

Published as a conference paper ICLR 2025
be sampled in rounds where i (mod b) = k, the resulting privacy guarantee can be reduced standard DP-SGD but for ny'b rounds and batch size scaled up by b. However, there are two key limitations: (i) it constrains C limiting its expressivity, and (ii) its analysis does not exploit the fact that the assignment of batches to indices can be randomized. This latter issue becomes apparent when b is sufficiently large, where the result collapses to one without any amplification despite this randomness.
Conditional composition (Choquette- Choo et al. 2024b): They instead show that these mechanisms have privacy guarantees upper bounded by different independent noise mechanism, allowing the use of compo- sition. Specifically, consider Poisson sampling with probability p. Effectively what they show is that we can compute a separate privacy guarantee for each row of Cx + using an inflated sampling probability p > p and compose these guarantees as if they were independent. This approach is more general than (Choquette- Choo et al., 2024a) because it applies to generic C. However, p introduces slack in the analysis that gets worse as the noise multiplier decreases, such that the e computed in low-privacy regimes can be much worse than even the unamplified e. This manifests practically in DP machine learning: most mechanisms obtain no benefits.
1.3 FUTURE DIRECTIONS
There are several interesting directions for extending the practicality of our work. One reason for our choice of balls-in-bins sampling is that it is more amenable Monte Carlo accounting than Poisson sampling. Poisson sampling provides much stronger amplification than shuffling in most settings (Chua et al.] (024). ignoring the practicality of Poisson sampling, enabling Monte Carlo accounting for correlated noise with Poisson sampling could thus enable even higher utility for private training. However, the fact that the corresponding mixture of Gaussians has 2n modes is challenging technical barrier to such result.
The number of samples we need to verify a DP guarantee using Monte Carlo accounting and e.g. Bernstein's inequality scales as 1/6. which may be prohibitive for small d. an interesting but challenging question to determine if a more careful sampler and concentration analysis can give substantially improved sample complexity for analyzing correlated noise mechanisms. Due to space constraints, we discuss other future directions in Appendix
2 PRIVACY Loss DISTRIBUTIONS AND MONTE CARLO ACCOUNTING
We can define (s, 8)DP in terms of the hockey-stick divergence. For any two distributions P, Q. their a-hockey stick divergence for 2 0 is given by Ha (P S. P(x) aQ(=),0). A mecha- nism M is (s, 6)D if for any adjacent databases D D' (under the add-remove adjacency), we have Her (D))) S Suppose P. are a dominating pair (Zhu et al. 2022) for M of interest; that for any D ~ D' > 0 we have Ha (MD), M(D')) I (P,Q). Then, by sampling X ~ P and computing Y = log P(X)/Q(X), we then say that the privacy-loss distribution (PLD) (Balle et al. 2018)
of P and Q is the law of Y.
Now to prove (c, DDP for M, it suffices to show Her (P.Q. Q) < 8. The main observation in Monte Carlo accounting is that if exactly computing H. (P, Q) is hard but sampling Y is easy, we can estimate 5 for some & by taking the average of sufficiently many samples of max(1 e 0). Namely, let be the estimated 5 value, i.e. the average over some samples of max e ,0.. As a starting point, we can already claim (e, 8DP an informal privacy statement. To make it formal, we can use the Estimate- Estimate-Veriff- Verify-Relesse framework of (Wang et al. 2023) (Algorithm 1 we fix a target (s, 8DP privacy guarantee ahead of time, and use Monte Carlo accounting to verify that M satisfies with (c, 8)P and only run M if the verification succeeds.
write Ha expectation over Y. Ha(P, Q) Ey [max/1 ac see-YY00 .O]]. Then,
The below theorem shows that Algorithm can be made to incur only a constant blowup in 8:
4

---

Published as conference paper ICLR 2025
Algorithm 1 Estimate- Seaiitt--errfyy--eeeeeee Releff- of (Wang et al., 2023)
Inputs: Mechanism M, dataset D, estimated privacy parameters E,
1: Determine dominating pair P, Q of M, get ö, an estimate of He- (P.QQ)..
2: if' < å then
3:
return M(D)
4: else
5: return 1
6: end
d
dg
d
d_
d
d_
d
d_
d,
dg
d,
d
4
d
B,
B2
B
B,
B
B
B,
B,
B
B,
Bg
B
6.
d
4
4.
d.
4
4
d
d
d,
d
4
d
d.
4,
d.
d
d.
d,
d.
d,
B,
B
B
B
B
B
B
B
B
B,
Bg
B
No amplification
Shuffling
Balls-in-bins
Poisson sampling
Figure 1: A comparison of the how different amplification methods might form batches. Here, n = 6 rounds, and form b = batches per epoch for E 2 epochs (visually represented as one row for fixed batch sizes, and all methods but Poisson sampling use the same
each epoch). Note that shuffling batching across epochs and enforce exactly one participation per example per epoch.
Theorem 2.1 (Theorem 9 of Wang et al. (2023). Suppose in Algorithm 7 that for any P, such that (2(, Q) > rô, 8 > 8 wap. at least 7ô. Then Algorithm is (e, -DP.
The following theorem (proven in Appendix E can be used to derive the tail bound required for Theorem 2.1 Theorem 2.2. Suppose we use samples in computing in Algorithm
1 Then for any P, Q such that
H2(P,Q) 2 T8, 1, we have Pr[s < 6] S exp
s(r-1)86 87/3-2/3
3 BALLS-IN-BIN BATCHING
As we will see the next section, applying Monte Carlo accounting to correlated noise mechanisms requires time linear in the number of possible participation patterns. For re-ound DP-SGD with Poisson sampling, this is 2". Shuffling reduces the number of possible participation patterns, and is generally considered a more practical variant, but is hard do privacy analysis for because the participations of different examples are not independent like in Poisson sampling.
To alleviate the issues with both Poisson sampling and shuffling, we propose balls-in-bins batching. Infor- mally, balls-in- bins batching forms batches using the Balls-in-bins process, where examples are balls and batches are bins:
Definition 3.1. In balls-in-hins batching, we form batches follows. Let b be the number of batches per epoch we wish to use and let E be the number of epochs that we train. Also denote by n = the total number of training iterations. For each example d, independently include it in exactly one of B1, B2..... B, uniformly at random. We then iterate through the batches in round robin fashion, i.e. in iteration of our learning algorithm use batch B; (mod b) (abusing notation to let e.g. 2b (mod
b).
Figure give a visualization of dalls-in--inn batching and other standard methods for forming batches. The following lemma (proven in Appendix C shows that the following pair of distributions is dominating
5

---

Published as a conference paper ICLR 2025
pair for the correlated noise mechanism x + C-1z 6-1z with balls-in-bins batching:
E 1
P= (m.,,22), where m.
Σ
C
Q = 0
j=0
where |C| is the matrix whose entries are the absolute values of corresponding entry in C.
Lemma 3.2 (Dimension-reduccion for balls-in-bing bins batching). Suppose C E Rux= is a lower-triangular matrix with non-negative entries. Then P. Q (resp. Q, as defined above dominating pair for the correlated noise mechanism with balls-it in in-bins batching under the add (resp. remove) adjacency.
For simplicity of presentation, we will focus on the add adjacency in the rest of the paper. It is easy to extend results to the remove adjacency, and for the add-and-remen the two adjacencies' privacy guarantees (paying a factor of 2 in the failure probability of Theorem (2. by a union bound). We also remark that Lemma 3.2 (and any results in our paper for the add/remove adjacency) can be readily extended to the replace adjacency using recent results of Schuchardt et al. (2024).
adjacency we simply take the worse of
Advantages of balls-in-bing batching: In addition to being more amenable for Monte Carlo analysis than shuffling or Poisson sampling, we believe balls-in-bins batching may be more practical than Poisson sam- pling for various reasons. First, one way to implement balls-in-bins batching to form b batches is as follows: from the multinomial random variable with | trials and b equally likely out- comes. We shuffle the dataset once, and then we operate in multiple streaming passes over the shuffled dataset. In iteration i, we take the next O; (mod b) examples from the dataset stream.
We sample (C1, ......, (b)
Hence, up to the choice of variable batch size (which we will discuss how make practical in Section !. balls-in-bins batching is no harder to implement than shuffling, which is generally considered to be prac- tical batch sampling method. As a function of requiring little overhead compared to shuffling, balls-in-bins batching avoids some of the practical issues with Poisson sampling. For example, shuffling and balls-in-bins are both memory-efficient if implemented in an offline manner as the shuffled dataset is the same size as the original dataset. In contrast, if we implement Poisson sampling in an offline manner, to store all batches formed by Poisson sampling we need to write each example Bn/|D) times in expectation, which can be much larger than 1.
4 MONTE CARLO ACCOUNTING FOR CORRELATED NOISE MECHANISMS
4.1 CALIBRATING
Now, suppose we are given a lower triangular matrix C E Raxn with non-negative entries and we aim to find the minimum noise-multiplier a so that the balls-in-bins mechanism is (c, dDD.. This 8' will be slightly smaller than ó so that Algorithm|| is (e, BDP and outputs 1 with very small probability. We approach this by drawing sample of the dominating PLD and employing a bisection root-finding algorithm on a.
To do this, we first recall the dominating distributions,
Pc.rr N(m,, I²1), where m;
Climpjtt
Qx -OON000021,
Hence we can sample PLD(Pc Qa) by first sampling X Pc.a and computing Y Pc. (x)). Note that computing Y efficient since Pc,, has only b modes. To make the sam-
log Q
pling independent of a, instead sample i Uni(b) and Z NO, I) then for any compute
6

---

Published as conference paper ICLR 2025
==
foi (m + a (.). This process is summarized in Algorithm which uses the function to Q.
estimate the d at fixed σ. The inner computation of å is easily parallelizable, as it is simple average over a given sample size. On top of this, a bisection algorithm is run, which can converge" to within A additive error in only (log((/A)) many iterations because a is scalar.
Algorithm 2 Finding
Inputs: Target (e, 6)-DP guarantee, sample size m, matrix C.
1: ii ... im rid (n](
2: Zi...., 2m NO0, I)
3: Define (a( == log Pc. (mi, to. 2,))
4: Define the function 8 as 8(0; C,E, 11mm Z1.m)
- E exp(E Y)(o)))
m
5: a* solution 8(;; C, 8, him, Zi.)) 5 obtained by some 1-d bisection algorithm
6: return 0²
4.2 OPTIMIZING OVER MATRICES
In the previous section, outlined the procedure Algorithm 2 for estimating the noise multiplier for given matrix C. We now show that we can optimize C for a given utility metric that is a function of C, a. We will choose the utility metric be the RMSE (root mean squared error) of prefix sums of achieved by + C z. which was also the metric optimized by (Choquette-Cie Chho et al. 2022 2024a). The RMSE is given by ||A ClI. where |I-I| is the Frobenius norm and A is the all-ones lower-triangular matrix. While we focus on RMSE in this paper, our optimization framework is easily extended to any differentiable function of C and
Algorithm22 2 computes a (as function of C) using bisection, hence we cannot e.g. apply automatic differ- entiation to find partial derivatives of a. However, via implicit differentiation we can still obtain gradients of the RMSE with respect to C using only quantities computable via automatic differentiation (see Ap- pendix D for details). We then simply plug these gradients into an optimization algorithm; for simplicity, use gradient descent. Finally, for efficiency, choose restrict to Toeplitz C to optimize over lower dimensional space.
5 EXPERIMENTS
We implement Algorithm 2 for calibrating noise multiplier for given mechanism under balls-in-bins batching. In this section, we look at both the problem of minimizing RMSE and a deep learning setting, and compare results enabled by our accounting and optimization routines past work. For all results we fix 5 = 10-5, and for balls-in-bing batching we use Theorem 2.2 in conjunction with Theorem 2.1 to get a formal (s, 10 DD guarantee after choosing and σ. See Appendix for details.
"To show bisection search converges, Jmas is the a achieving the target DP guarantee without amplification (which we easily can compute using existing accounting libraries), 5(0; = and 6(amazi...) < 8 (whp). turn, 8(a; for some [0, maa) and bisection converges this point by continuity of 8
7

---

Published as conference paper ICLR 2025
RMSE improvement on BandMF-num, bands 64
RMSE improvement DPSGD
-5
Improvement in RMSE
% Improvement in RMSE
30
25
Unamplified
20
Unamplified
Ballsinnbins
40
Balls-in-bins
Poisson
15
Poisson
20
2
2
2
2
20
21
22
(b) Improvement RMSE over unamplified
(a) Improvement RMSE unamplified DP-SGD
banded matrix factorization due to different amplifi- cation schemes.
due different amplification schemes.
Figure 2: Comparisons using fixed C.
5.1 RMSE RESULTS
5.1.1 ANALYSIS OF THE AMPLIFICATION SCHEMES
We first focus the RMSE metric |CI We compare balls-in-bins batching analysis, Poisson sampling (using the analysis of (Choquette-Chie Choo et al.) 2024a) for b-banded matrices where 1, and standard PLD accounting for DP-SGD), and no amplification (i.e., do multiple passes using fixed batch size over a dataset). To simplify presentation in this section we will restrict to the setting with 2048 total iterations and 16 epochs, i.e. 128 iterations per epoch or B D2/128. In Appendix F we provide results for other settings of the number of epochs and number of iterations per epoch; while the exact numbers differ in other settings, the high-level conclusions hold in all settings tested.
we plot the percentage improvement in RMSE due to balls-in-bins and Poisson sampling over the unamplified RMSE of DP-SGD, i.e. = I. We observe that the improvement from the two sampling schemes is similar for smaller and Poisson performs substantially better than balls- in-bins for larger s. Since balls-in-bins resembles shuffling, this mirrors the results of Chuaaa et al. (0024).
Amplification of DP-SGD: In Fig. 2a
Amplification of banded matrix factorization: We next consider non-identity choices of C. In particular, we look at b-banded matrices where b > 1. Recall that a weakness of the sampling scheme of Choquette- Choo et al. (2024a) is that the amount of randomness in the sampling scheme, i.e. the degree of benefit from amplification. decreases as the number of bands b in the matrix increases. In contrast, the randomness in independent of the matrix structure. We then may expect that balls-in-bins et al. (024a). We verify this in Fig. 2bb
sampling from balls-in-bins amplification outperforms the amplification of (hhoohett- We again plot the percentage reduction in RMSE due to amplification but for 64-banded matrix instead of C I. As predicted, due to using higher-randomness sampling scheme, balls-in-bing consistently outperforms Poisson sampling until 16.
While the previous experiment shows that balls-in-bins is preferable when using fixed large number of bands, better strategy to choose the number bands minimize the RMSE rather than fix b advance. In Fig, 3al we reproduce Figure 22 instead of fixing the number of bands b in advance, b E 2, 4, 8, 16, 32, 64, 128, 256} and for balls-in-bins batching pick the value of b which minimizes the RMSE. For banded matrices and Poisson sampling, where Choquette- -Chee et al. (2024a)'s 's result gives a non-zero amount amplification. For the unamplified baseline, there is no benefit reducing the number of bands b pick b = 256.
sweep
do the same but restrict to b S 64, i.e. the regime
8

---

Published as conference paper ICLR 2025
RMSE improvement on BandMF through amplification
over best unamplifed Bandler
RMSE improvement Best BandMF
Improveeennn rnprovvmment in RMSE
10
Optanized lbsppitz
20
improvement in RMSE
Optimtzed BLT-3
--- Best BandMF unamplified RMSE
Best BandMF
Best Bandke IMSE wi balls-in-bins
6
241
2
24
(a) Improvement RMSE over unamplified b-banded matrix factorization due to different amplification (b) Improvement from optimizing using objective schemes. All curves optimize the choice of b each accounting for amplification.
point. Best choices b are plotted in Appendix
Figure 3: Comparisons for variable C.
For S. 4, the best RMSE under Poisson sampling slightly outperforms balls-in-bins batching and for E 2 deterioration in the RMSE improvements from Poisson. At 16, see that is better to forgo amplification and use the unamplified baseline. In contrast, because the distinguishing problem for balls-in-bins for fixed C always strictly harder than the unamplified baseline, the best C combined with balls-in-bing batching always strictly improves over the unamplified baseline.
5.1.2 IMPROVEMENTS TO OPTIMIZATION
We now look at the benefits of using our optimization procedure to choose C. We compare two variants of our optimization scheme, one which optimizes over general Toeplitz matrices, and another which optimizes over the BLT matrix family defined by Dvijotham et al. (0024). We use the 3-buffer variant of BLTs, i.e. they can specified using parameters and only require a memory overhead of 3 times the model size. In Figure we plot the improvement in RMSE for both these variants relative to the best b-banded C amplified using the sampling scheme and analysis of [Choquette-Chhee Choo et al. (2024a).
We observe that for most values, optimization procedure for C can give reduction in RMSE compared to the previous stte-of-theeart of [Choquette- Choo et al. (2024a). For extreme values of e, the banded baseline still outperforms our optimized matrices. We note that despite BLT matrices being subset of Toeplitz matrices, our optimized BLTs matrices sometimes outperform our optimized Toeplitz matrices. We believe this is because BLTs lie in lower-dimensional space which may make it casier to optimize over them, i.e. the suboptimality of our solution to the optimization problem over BLT's may be smaller than the suboptimality of solution to the problem over Toeplitz matrices.
We also conducted experiments to understand the scalability of our optimization procedure. Due to space constraints, defer these Appendix G
5.2 CIFAR RESULTS
We next compare different choices of the correlation matrix C and amplification schemes in deep learn- ing setting. We replicate the CIFARIO image recognition setting considered by (Choquette- 2024a): we also the same VGG model, 20 epochs of 100 iterations with batch size 500, and mo- mentum 0.95 and a learning rate cooldown from to n/20 across iterations 500 to 2000. We vary E E (0.5, 1.0, 2.0, 4.0, 8.0). We fix the clip norm to 1.0 and tune the learning rate separately for each com-
et al.)
9

---

Published as a conference paper ICLR 2025
CIFAR Accuracy
Test acc. minus test acc. of Band MF + Poisson
1
Band MF Poisson (baseline)
Optimized + Ralls-in-Bins
Optimized Toeplitz + Balls-in-Bins
0
MF Balls-In-Bins
0.5
1.0
2.0
4.0
8.0
6
10-5
Figure 4: Comparison of accuracy on CIFAR of different correlated noise strategies and amplification meth- ods, relative to the baseline of banded C + Poisson sampling, with 95% confidence intervals over 100 trials. We give a non-normalized plot in Appendix
bination of e and correlation matrix/amplification method, and then report the average of 100 training runs for each combination. The different correlation matrix choices and amplification methods we consider are:
Our baseline the SOTA of banded matrices of Choquette-Choo al. (2024a) using their Pois- son sampling-based amplification scheme. We also consider banded matrices and balls-in-bins batching. Following [hoquette-CCa Chho
(2024a), for each choice of the number of bands b, we
optimize C without accounting for amplification. Then for each amplification method, we use the choice of b in each setting of that gives the lowest RMSE under amplification.
We do not separately consider multi-epoch MEMF of [Choquette Caooqueette-hooo et al. (0022 or DP-
SGD with Poisson sampling as they are subsumed by this approach.
BLT matrices Dvijotham et al. (2024). We restrict 4 buffers and use our optimization frame-
work to optimize C for the RMSE under balls-in-bins batching for each value E.
General Toeplitz lower-triangul matrices. Again
optimization framework to optimize C for the RMSE under balls-in bins batching for each value of
For all methods, in the implementation shuffle the dataset and noise multiplier assuming the corresponding amplification method was properly implemented. This is a standard practice for simplifying implementations in the literature (e.g.. Choquette- Appendix|! []] we discuss the pitfalls of this practice, and do a training run where we actually implement a practical variant of balls-in-bins batching that also uses fixed batch sizes for gradient computations.
fixed batch size, but calculate the
et al.) (2024a)). In
In Fig. we plot the test accuracy achieved by each combination of correlation matrix and amplification
analysis. We conclude the following:
Banded matrix factorization + balls-in-bins always at least as good as the baseline, and sometimes gives up 1% accuracy improvements. As argued earlier, the baseline assumes Poisson sampling which is a stronger/less practical assumption.
Our ability to optimize BLT matrices makes them also always at least as good as the baseline, but with smaller improvements than the previous bullet. The baseline uses up to 16 bands depending on s, so BLTs are also up to 4x more memory efficient than the baseline.
Optimized Toeplitz matrices are incomparable to the baseline; we believe their weak performance relative to the other methods is due to the difficulty of the optimization problem.
10

---

Published as conference paper ICLR 2025
REFERENCES
Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, lya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS' 16), pp- 308-318, 2016.
Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pp. 394-403, 2018.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 0280-6290. 2018. URL http: /ttp:://ppprrs.a/e//ee nips cc/paper/
7865 prwvacyy amp compliifiattioo ion by subs amp ing t tight analyses - via coaa-coupliie Lings and divergenn
Borja Balle, Peter Kairouz, H Brendan McMahan, Om Thakkar, and Abhradeep Thakurta. Privacy amplifi- cation via random check-ins. In NeurIPS, 2020.
Christopher Choquette-Choo, Brendan McMahan, Keith Rush, and Abhradeep Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. arXiv preprint vrXiv:2211.06530 2022.
Christopher A Choquette-Choo, Krishnamurthy Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Correlated noise provably beats independent noise for differentially private learning. arXiv preprint arXiv:2310.06771, 2023.
Christopher A Choquette-Choo, Arun Ganesh, Ryan McKenna, H Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. (Amplified) banded matrix factorization: A unified approach private training. Advances in Neural Information Processing Systems, 36, 2024a.
Christopher A. Choquette-Choo, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Pri- vacy amplification for matrix mechanisms. In The Twelfth International Conference on Learning Representations, 2024b. URL http::::///pppeeveeeeee net
How private is DP-SGD? arXiv preprint http:////opppeeeeeeeeee/ooooaaaa 1ot
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. 2024.
Sergey Denisov, H Brendan McMahan, John Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. Advances in Neural Information Processing Systems, 35:5910-5924, 2022.
DP Team. Google's differential privacy libraries., 2022. httpp::/gtttbb..co/gggg/ differential-privae
Krishnamurthy Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy, 2024. URL
16706
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proc. of the Forty-Second ACM Symp. on Theory of Computing (STOC' 10), pp. 715-724, 2010.

---

Published as a conference paper ICLR 2025
Ülfar Erlingsson, Vitaly Feldman, Πlya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Timo- thy M. Chan (ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA. January 6-9, 2019, pp.
SIAM, 2019a. doi: 011137/1.97811119999 151. URL https:://dooooo org/ 10. 1137/1 978161197548888 151
Ülfar Erlingsson, Ilya Mironov, Ananth Raghunathan, and Shuang Song. That which call private, 2019b.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 954-964, 2022. doi: 10.1 109/FCC552999 211.9.222111.00 1.0096.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Prac- tical and private (deep) learning without sampling or shuffling. In ICMI,, 2021.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? In 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 531-540, 2008
Antti Koskela, Joonas Jalko, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete- valued mechanisms and for the subsampled gaussian mechanism using FFT. In A Banerjee and K Fuku- mizu (eds.). 24th International Conference on Artificial Intelligence and Statistics (AISTATS), Proceed- ings of Machine Learning Research, United States, 2021. Microtome Publishing. 24th International Con- ference on Artificial Intelligence and Statistics (AISTATS): Conference date: 13-04-2021 Through 15- 04-2021.
H. Brendan McMahan, Zheng Xu, and Yanxiang Zhang. A algoriitt for private learning in prac- tice: Don't use tree aggregation, use blts, 2024. URL htttt::/aaxxxi org.//iiiorroooooooo wwwggg/....... abs/ 24002220.22. 08868
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMaaan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How DP-fy ML: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 17:1113-1201, URL http::tt///// doi wtw.o/oooo.00000.11111113
July 2023. ISSN 1076-9757. doi: 10.1613/jair. 1.16449...144
1.1649
Jan Schuchardt, Mihail Stoian, Arthur Kosmala, and Stephan Günnemann. Unified mechanism-speciffc amplification by subsampling and group privacy amplification, 2024. URL https://arxiv.oog:
Jaachen T. Wang, Saeed Mahloujifar, Tong Wu, Ruoxi Jia, and Prateck Mittal. A randomized approach to tight privacy accounting. Advances in Neural Information Processing Systems, 36. 2023. ISSN 1049- 5258. Publisher Copyright: c 2023 Neural information processing systems foundation. All rights re- served.; 37th Conference on Neural Information Processing Systems, NeurIPS 2023; ; Conference date:
10-12-2023 Through 16-12-2023.
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, abs/2109.12298, 2021. URL
http://b///00000 12299
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In Gustau Camps-Vare Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Prooeedings of Machine Learning Research, pp. 4782-4817. PMLR, 28-30 Mar 2022. URL https: //proceedingss ngs. ml wwwpppersss.saaaa.pep
12

---

Published as a conference paper ICLR 2025
A MORE FUTURE DIRECTIONS
To be able to use Monte Carlo sampling to analyze the privacy amplification of the balls-in-bins sampling scheme, we needed to first provide PLD-dominating pair of distributions. In Lemma [.2] we obtain this pair by taking the modes of to be sums of certain columns of |C|. This is potentially too loose, and we may hope to instead use sums of columns of C, thereby reducing the norm of each mode. In the unamplified setting, this loosening of the assumption is possible whenever C(:, i] C(:..]] for any pair of rounds i, a user can participate in. However, amplification through sampling complicates this, and standard techniques for reducing dimensionality and adaptivity don't work anymore, see Appendix Oopeedix[forr an example.
While we were able to implement practical variant of balls-in-bins batching that was compatible with XLA compilation, we only used our variant to train a small-scale model. We leave it to future work to implement balls-in-bing batching at larger scales, and in particular compare the scalability of balls-in-bol bins to that of unamplified training and Poisson sampling.
B MORE BACKGROUND ON PRIVACY AMPLIFICATION AND CORRELATED NOISE
Privacy amplification: Though randomness in data processing reduces the variance of noise required, the main challenge with privacy amplification is giving tight privacy analysis of the amplified mechanism, which for DP-SGD usually requires computing divergence between two mixtures of Gaussians. There are several
forms of privacy amplification. but the two most popular are sampling (Abadi et al. 2016 Balle et al.) 2018)
and shuffling (Balle & Wang 2018: Erlingsson et al. 2019h Feldman et al. 2022).
Privacy amplification by (Poisson) sampling assumes the batches are formed by including each element in- dependently with some probability p. Because the sampling randomness is independent across rounds, tight privacy analyses of DP training with independent noise (DP-SGD) are well-known (Koskela et al. (021). and supported by open-source libraries (DP Team 2022). However, Poisson sampling is often impractical implement, especially when working with larger datasets (Ponomareva al. 2023).
Privacy amplification by shuffling in the context of DP-SGD usually assumes the batches are formed by shuffling the dataset (a single time) and then forming fixed-size batches using the shuffled order. In some limited settings its privacy analysis is well-understood (Feldman et al. (022). but in the setting of DP-SGD, for example, tight privacy analyses remain elusive. Technically, the difficulty is that the participations of different examples are dependent, unlike with Poisson sampling. In addition to being challenging to analyze, Chua et al. (2024) demonstrated that shufiling often gives much smaller improvements in privacy compared to sampling. Despite these difficulties, as Chua et al.] (2024) note, shuffling is used much more widely in practice since can be implemented, e-g., single pre-eeesesing pass over the dataset, whereas sampling requires random access to potentially very large datasets which is often infeasible.
Kairouz et al. 1222 proposed FTRL,,,, the first DP training algorithm with correlated noise, where the update at each step are the rows of x + Ztree where Ztree is sampled using the binary tree mechanism of (Dwork et al., 2010). Denisoy et al. (2022) showed this was special case of the updates being rows of x C-tz, z, giving more expressive definition for C-1 called the "correlation matrix". They showed these matrices could be optimized via a convex optimization program to maximize noise cancellation (i.c.. minimize total noise variance). [ChqquetteChhin alization, leading to the first correlated noise DP training algorithm to (substantially) outperform DP-SGD with practical e's. Shoqueete-Chooo et al. (2024a) showed that correlated noise algorithms Pareto-dominated DP-SGD in privicy-utility tradeoffs; [Choquette-Chor et al. (2023) showed that these algorithms provably outperformed SGD.
Correlated noise:
al. (2022) proposed "multi-participatee
gener-
13

---

Published as conference paper ICLR 2025
For simplicity, these works assume C is non-negative and lower-triangular The privacy guarantee of cor- related noise is the same as that of the matrix mechanism Cx + z by post-processing. hence based on how batches are formed we can usually give privacy guarantees terms of an appropriate norm of C. To op- timize the matrix C, the convex program usually minimizes the cott-mea--suuare--erro (RMSE) of the prefix sums x, given by ||, a where A the lower-triangular all-ones matrix and a is the noise multiplier needed for Cx + satisty the target privacy guarantee.
C PROOF OF LEMMA 3.2
We use Lemma 4.5 of (Choquette-Choo et al. 2024b), restated here for convenience:
Lemma C.I. Let : E RR Let ,y....,,c og RR be such that ||ci[i, :lll2 S c((i) all i,j. Then letting
P 0 o (nxp)x(xx))) DiiN(c, o ((xx))((xx))) P'= NNO, o Inxn).
for all a we have (P,QQ) < H.(PP, (IP',Q) Q'). Furthermore, this holds even if the jth row of each is chosen as a function of the first j - 1 rows of P.Q. (subject to [e,li S c,()) while di remain fixed.
Proof. We give the proof for the add adjacency. Proving P,Q is dominating pair for the add adjacency implies Q, P is dominating pair for the remove adjacency by Lemma 29 of (Zhu et al. (022)..
Because each is assigned their batch independently, contributions from all users other than the differing user are always O. In more detail, by post-processing, we can assume that release the contributions to the input matrix of all examples except the differing user's. Let x be these contributions, and x' be x plus the contribution of the differing user. Then distinguishing Cx z and Cx' is equivalent to distinguishing z and C(x' xx + z, exactly the setting where all users except the differing user only contribute 0.
assume without loss of generality that
Now, for the input matrix x maxp, the rows have at most unit norm the entries where the differing user participates and O everywhere else. If the differing user is assigned to the ith batch, it is immediate by triangle inequality that || (Cxx),, < Σド= [Ck..b-+t-- Because every
participates in each batch with probability J. we can apply Lemma 4.5 of Choquette- Choo et al. (024b) to exactly get that the correlated noise mechanism with watls-with-bins batching is domiattd by the parr P. Q.
D FINDING THE DERIVATIVE OF RMSE
By chain rule:
0(o [|A-')) = 0
-C
do aC
+ ||| -cll
aC
aC
Let å denote the function defined in Algorithm 2 i.e. the function that takes given e, a, C and set of
Monte Carlo samples, and outputs the corresponding estimated 8 value. Given set Monte Carlo samples, we want to take a gradient step while preserving 8 = Taking derivative of both sides of this constraint with respect to C:
14

---

Published as conference paper ICLR 2025
ab
dô
do
do
08
+
0
ac
do
ac
aC
ac
do
So to optimize the RMSE w.r.t. C we can now use Algorithm gradient descent using the gradient
to find for given C, and then apply
a |
P|AA-'0 aC
a8
dd
||A-c||
cll
OC
ac
do
Since 8 is computed using only differentiable functions of C and (i.e., not via bisection), all partial deriva- tives in the above expression can be evaluated the given C, pair using automatic differentiation.
CONFIDENCE INTERVALS FOR MONTE CARLO ACCOUNTING
this section we prove Theorem 2.2 which allows one to derive the required tail bounds on the error of å
in Theorem 2.1
Proof of Theorem 2.2 If H((, > 78, then we can express 8 = Ei= 8, where each 8, an i.d.
random variable in the range [0, 1] with mean 2 -ō. By the Bhatia-Davis inequality, we have Var (6:) <
(1 - μ) So B[
E| + Var 8,
n²² Var ( S
Now we can apply Bernstein's inequality to get that:
st2/2 /2/22
st2/2
Pr[s < exp
exp
I exp
[[88]] + t/3
1/3
Setting / = 5:
s(p s(p 6)2 A4//3 8/3
Pr(β <8 exp
Since / 2 78 > 6, we have:
d s(p - 55//22 (e(p-5)(2p)) 8) 0,
dp 4u/3 6/3
(4p - 36)
i.e. the bound Pr(s < 8) is decreasing in p, it is minimized by setting μ 76. Plugging this value of f in gives as desired:
s(7 -
Prps < 8) S exp
8T/3 3- 2/3
15

---

Published as conference paper ICLR 2025
For our empirical results, use 8 8- 10- - 1.25, 10 For this set of values, Theorem 2.2 gives
a failure probability less than 7.2 10-9 We use Algorithm to verify the DP guarantee for both the add
and remove adjacencies, but by a union bound the failure probability increases at most 1.5 10 once
accounting for both adjacencies, much smaller than 70 = 10-5, So, we can apply Theorem 2.1 to show (e, 9-DP for our empirical results.
F RMSE PLOTS FOR OTHER SETTINGS
F.1 VARYING SAMPLING PROBABILITY
Figure 5 we compare Poisson sampling and balls-in-bins batching. We fix 128 rounds of training, and fix target DP guarantee of (1, 10-9)-DP We vary the sampling probability and compare the RMSE achieved by the best banded matrix with either balls-in-bins sampling + our amplification analysis or the sampling scheme and analysis of Chhqueetee Chho al. (2024a). For balls-in-bins, we treat 1/b where b is the iterations per epoch as the sampling probability for the purpose of plotting, i.e. at each point on the x-axis both algorithms have the same expected batch size.
% Reduction in RMSE vs Sampling Probability
% Reduction in RMSE VS Best Unamplified
0.8
Poisson
Balls in bins
0.6
0.4
0.2
0.0
1
2
4
8
16
32
64
128
1 Sampling Probability
Figure 5: Comparison of improvement due to function of sampling probability.
F.2 GRID OF EPOCHS AND ITERATIONS
Here we plot the RMSE improvements through amplification and optimization for number epochs in {8, 16, 32) and iterations per epoch in (32, 64, 128).
16

---

Published as conference paper ICLR 2025
F.3
NUMBER OF EPOCHS AND ITERATIONS PER EPOCH 32
RMSE improvement BandMF through amplification
improvement in RMSE unampiffed BandMM
Best BandMF unamplitedd RMSE (baseline)
Best BandMF RMSE w/ Polsson
20
Figure 6: Improvement in RMSE over unamplified b-banded matrix factorization due to different amplifica- tion schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
10.0
Best BandMF (baseline) Optimized
% improvement in RMSE over Best BandMF
Optimized BLT3
-25
-50
-73
-100
Figure 7: Improvement from optimizing C using objective accounting for amplification.
17

---

Published as conference paper ICLR 2025
F.4
NUMBER OF EPOCHS AND ITERATIONS PER EPOCH 64
RMSE improvement BandMF through amplification
improvement in RMSE unamplffed BandMM
Best BandMF unamplitied RMSE (baseline)
Best BandMF RMSE w/ Polsson
20
Figure 8: Improvement in RMSE over unamplified b-banded matrix factorization due to different amplifica- tion schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
Best BandMF (baseline)
10.0
Optimized
% improvement in RMSE over Best BandMF-
Optimized BLT3
7.5
-25
-5.0
-7.5
Figure 9: Improvement from optimizing C using objective accounting for amplification.
18

---

Published as conference paper ICLR 2025
F.5
NUMBER OF EPOCHS AND ITERATIONS PER EPOCH 128
RMSE improvement BandMF through amplification
improvement in RMSE over best unampiified BandMM
40
Best BandMF unamplitedd RMSE (baseline)
Best BandMF RMSE w/ Polsson
20
10
Figure 10: Improvement in RMSE over unamplified b-banded matrix factorization due different amplifi- cation schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
12.5
Best BandMF (baseline)
Optimized
% improvement in RMSE over Best BandMFF
Optimized BLT3
10.0
7.
5.0
-2.
-5.0
Figure 11: Improvement from optimizing C using objective accounting for amplification.
19

---

Published as conference paper ICLR 2025
F.6
NUMBER OF EPOCHS 16 ITERATIONS PER EPOCH 32
RMSE improvement BandMF through amplification
improvement in RMSE unamplifedd BandMr
Best BandMF unamplitied RMSE (baseline)
Best BandMF RMSE w/ Polsson
15-
Figure 12: Improvement in RMSE over unamplified b-banded matrix factorization due different amplifi- cation schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
Best BandMF (baseline)
Optimized
improvement RMSE BandME
Optimized BLT3
Figure 13: Improvement from optimizing C using objective accounting for amplification.
20

---

Published as conference paper ICLR 2025
F.7
NUMBER OF EPOCHS 16 ITERATIONS PER EPOCH 64
RMSE improvement BandMF through amplification
improvement in RMSE unampifhed BandMM
Best BandMF unamplitied RMSE (baseline)
Best BandMF RMSE w/ Polsson
Figure 14: Improvement in RMSE over unamplified b-banded matrix factorization due different amplifi- cation schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
Best BandMF (baseline)
Optimized
improvement RMSE BandME
Optimized BLT3
Figure 15: Improvement from optimizing C using objective accounting for amplification.
21

---

Published as conference paper ICLR 2025
F.8
NUMBER OF EPOCHS 16 ITERATIONS PER EPOCH 128
RMSE improvement BandMF through amplification
RMSE unampiifed BandMM
Best BandMF unamplitied RMSE (baseline)
Best BandMF RMSE w/ Polsson
20
10
Figure 16: Improvement in RMSE over unamplified b-banded matrix factorization due different amplifi- cation schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
Best BandMF (baseline)
Optimized
improvement RMSE BandME
Optimized BLT3
Figure 17: Improvement from optimizing C using objective accounting for amplification.
22

---

Published as conference paper ICLR 2025
F.9
NUMBER OF EPOCHS 32 ITERATIONS PER EPOCH 32
RMSE improvement BandMF through amplification
% improvement in RMSSE over best unamplifeed BandMe
12.5
10.0
0.0
-25
Best BandMF unamplified RMSE (baseline)
balls-in-bins
Best BandMF RMSE w/ Poisson
Figure 18: Improvement in RMSE over unamplified b-banded matrix factorization due different amplifi- cation schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
Best BandMF (baseline)
Optimized
improvement RMSE over BandME
Optimized BLT3
Figure 19: Improvement from optimizing C using objective accounting for amplification.
23

---

Published as conference paper ICLR 2025
F.10
NUMBER EPOCHS 32 AND ITERATIONS PER EPOCH 64
RMSE improvement BandMF through amplification
in RMSE best unampifhed BandMr
Best BandMF unamplitied RMSE (baseline)
Best BandMF RMSE w/ Polsson
Figure 20: Improvement in RMSE over unamplified b-banded matrix factorization due different amplifi- cation schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
Best BandMF (baseline)
Optimized
improvement RMSE over BandME
Optimized BLT3
Figure 21: Improvement from optimizing C using objective accounting for amplification.
24

---

Published as conference paper ICLR 2025
F.11
NUMBER EPOCHS 32 AND ITERATIONS PER EPOCH 128
RMSE improvement BandMF through amplification
improvement in RMSE over best unamplified BandMM
20
Best BandMF unamplified RMSE (baseline)
Best BandMI RMSE w/ balls in binins
BandMF RMSE
Figure 22: Improvement in RMSE over unamplified b-banded matrix factorization due different amplifi- cation schemes. All curves optimize the choice of b at each point.
RMSE improvement Best BandMF
10
Best BandMF (baseline)
Optimized
improvement RMSE BandME
Optimized BLT3
Figure 23: Improvement from optimizing C using objective accounting for amplification.
25

---

Published as conference paper ICLR 2025
Number of Samples 131072
Number of Epochs
16
32
64
32
376.88
384.44
311.35
Iterations
64
383.19
323.56
658.95
per epoch
128
389.37
770.18
3594.55
Number of Samples 1048576
Number of Epochs
16
32
64
32
374.33
394.50
468.45 .488
Iterations
64
525.25
664.23
804.56
per epoch
128
1060.45
1435.47
Out memory
Figure 24: Time (in seconds) to optimize C for different values of Monte Carlo samples used per gradient descent iteration, number of epochs, and iterations per epoch.
G
SCALABILITY OF OUR OPTIMIZATION PROCEDURE
G.1 TIMING ANALYSIS
In this section, to understand the scalability of our optimization procedure, analyze how long it takes to optimize for the matrix C as well and how it depends on the various parameters.
In Figure 24
we give the time, in seconds, for completing 300 iterations of gradient descent while varying the number of epochs, iterations per epoch, and number samples per gradient descent iteration. We use v100 GPU to perform the gradient steps. Here fix 10-5 and e 1. We make the following observations:
Increasing the number of samples multiplicatively by 8 does not cause the runtime to increase by the same amount.
On average, the runtime seems have a sublinear dependence in the number of epochs. In contrast, in most settings for a large enough number of iterations per epoch the runtime seems to grow linearly or worse in the iterations per epoch.
For the largest number of samples, epochs, and iterations per epoch we ran into memory issues. In the next section, we show that using very small number of samples in the optimization loop still yields good RMSE, i.e. these memory issues can generally be avoided. Combined with these observations, we believe this is evidence the optimization procedure is scalable the number of epochs, although it may be infeasible run the procedure for a large number of iterations per epoch.
G.2 EFFECT OF THE NUMBER OF SAMPLES
When optimizing over the matrix C, we use Monte Carlo sampler to estimate However, for privacy purposes we only need the estimate of a to be accurate for the final C output by the optimization procedure, since that is the only correlation matrix will actually use during model training. For intermediate values of C in the gradient descent procedure, it is not privacy violation to compute inaccurate values for these matrices.
turn, to make the optimization procedure more efficient, we can use a smaller number of samples per iteration. A natural question is then if the number of samples needed for the Monte Carlo estimator to
26

---

Published as conference paper ICLR 2025
number samples
70
0.5
ep5110
2p0
worse RMSE than using samples
60
4p04.0
Number of samples
Figure 25: Percentage increase in RMSE due using smaller number of samples per iteration in the optimization procedure, when compared to the RMSE achieved by using 220 samples per iteration.
concentrate comparable to the number of samples needed for the optimization achieve reasonable RMSE.
We run our optimization procedure for varying number of samples per iteration, and Fig. 25 for each of these numbers we plot the suboptimality of the final C value in terms of RMSE achieved compared to using the maximum number of samples. We vary & and fix least 1/5 x 2 samples needed for the Monte Carlo estimator of á to guarantec erro smaller than 8 with, say, constant probability, However, in Figure 25 we see that for = 0.5, 1,2 using e.g. x 2 samples per iteration suffices for achieving similar RMSE 20 samples per iteration, and at 4 this number of samples only leads to a s 10% increase in RMSE. In other words, our optimization procedure can use a much smaller number of samples (compared to the final verification of C and Ø) at little to cost in utility.
10-5 For this choice ó, we need
27

---

Published as conference paper ICLR 2025
H
ADDITIONAL FIGURES FOR SECTION S
27
balls-in-bins
poisson
2
Best number of bands
2
24
23
2
21
20
2-4
2-3
2
2-1
2 eps
2
22
23
24
Figure 26: For each of the amplification methods in Figure 3a
the best choice of at each value of e.
CIFAR Accuracy
65
Test acc.
Band MF Poisson (baseline)
Optim izd BLT + Bins
60
Optim zed Toeplitz Balls-in-Biin Bn-Bims
Band MF Balls-In-Blns
55
50
0.5
1.0
2.0
4.0
8.0
@
15
Figure 27: Comparison of accuracy on CIFAR1O of different correlated noise strategies and amplification methods, with 95% confidence intervals over 100 trials.
28

---

Published as conference paper ICLR 2025
Method E
0.5
1.0
2.0
4.0
8.0
BandMF + Poisson
1.018
0.778
0.606
0.481
0.388
MandMF Balls-in- Bins
2.829
2.071
1.455
0.802
0.470
Optimized BLT + Balls-in-Bins
2.609
1.598
1.079
0.694
0.448
Optimized Toeplitz + Balls-in-Bins
2.003
1.182
0.864
0.639
0.445
Figure 28: Noise multiplier a used in the CIFARIO experiments for different correlated noise strategies and amplification methods. Note that different strategies which have higher noise cancellation require higher o, lower noise multiplier alone does not imply better learning performance.
Method e
0.5
1.0
2.0
4.0
8.0
BandMF + Poisson
32
BandMF
16
32
64
64
64
Figure 29: Number of bands used the CIFARIO experiments for BandMF combined with different ampli- fication methods.
I PRACTICAL IMPLEMENTATION OF BALLS-IN-BINS BATCHING
In Section 5.2. and in most empirical research on DP model training, an amplification method like Poisson sampling is assumed when computing the noise multiplier, but for convenience a simpler sampling scheme is actually implemented. The most common case of this is assuming Poisson sampling when instead doing shuffling, even though shuffling can produce much larger e values than sampling (Chua et al., 2024). notable exception is research built on Opacus (Yousefpour et al. (021) which implements Poisson sampling.
The main issue with implementing such sampling schemes properly that they usually lead to unequal batch sizes (as schemes like shuffling which enforce equal batch sizes usually hard to analyze tightly), which can lead to several inefficiencies:
Modern model training pipelines optimized for fixed batch size. For example. XLA, which is used to e.g. compile gradient computations implemented in libraries like TensorFlow and JAX, requires static input shape. To variable batch sizes, one would naively need forgo the of XLA which could heavily slow down training in large-scale settings.
For example, consider Opacus which correctly implements Poisson sampling and supports variable batch sizes. the benchmarking experiments of (Yousefpour et al., (021). Opa- cus was shown to have runtime competitive with JAX for small-scale DP training, However, they observed that e.g. JAX pays large up-front cost for compilation but after compilation achieves better runtime per iteration than Opacus. We expect that for larger scale the training the time spent on compilation is smaller fraction of training time, hence variable batch size training with Opacus would be less scalable than XLA-based training using fixed batch sizes. Sampling slightly larger batch can lead to disproportionately longer gradient computation times. As an extreme case, suppose we use an expected batch size of B, and we have accelerators that can each process single gradient in parallel in time T. Hence computing batch gradient B examples takes time T. However, if we have B + 1 samples instead, we will need time 2T instead. Sampling smaller batch leads to wasted computational resources. For example, in the above setting, we sampled 9B BB/10 examples, then we would have B/10 accelerators being unused, which may be undesirable.
29

---

Published as a conference paper ICLR 2025
CIFAR Accuracy
70
Test accuracy
MEMF amplification) [Choquette Choo 2022]
60
Optimized + Implemented Balls-in-Bil Bins
Optimized Unimplemented Balls-in-Biis
50
0.5
1.0
2.0
4.0
8.0
Epsilon
delta
1e-5
Figure 30: Comparison of implementing balls-in-bins batching to shuffling and assuming balls-in-bins in the analysis, and the unamplified baseline.
To this end we propose and implement the following practical variant of balls-in-bins batching: We do balls-in-bing batching, but:
If batch has size less than we pad it with some examples that have gradient its batch size becomes B.
If batch has size greater than B, we truncate have size exactly B. We compute the average gradient over the padded/truncated batch (i.e. our normalization in the average always 1/B).
Recall that balls-in-bins (without padding and truncating) can be implemented by shuffling the dataset, sam- pling batch size schedule, and then taking batches according to this schedule. Hence even with padding and truncating balls-in- ins--inniiii bins requires minimal overhead top of shuffling, and indeed we were easily able to implement it in our CIFAR training code using only single shuffle on the dataset and numpy's 's multi- nomial sampler and pad operations, and use XIA compile gradient computations in the resulting code. Furthermore, none these changes affects the privacy analysis. This is because (i) the fixed normalization is compatible with the privacy analysis which is implicitly analyzing the sum rather than the average, (ii) truncating a batch is equivalent to some of the examples in that batch having gradient O, and DP-SGD's privacy analysis allows arbitrary clipped gradient.
We next demonstrate that the loss in utility due to truncating examples or not saturating the batch size in every iteration acceptable. We rerun the training procedure from the previous section using BLT matrices (we focus on BLT matrices as they are the most scalable choice of correlated noise (McMahan et al. 2024)), but implement our practical variant of balls-in-bins batching. We pad/truncate to the same batch size of 500, i.e. in terms of gradient computations our practical variant of balls-in-bins is no more costly than shuffling the dataset and using fixed batch sizes instead.
In Figure 30 we compare this implementation to (i) the same implementation but using shuffling instead of balls-in-bins batching, and (ii) the state-of-the-art unamplified baseline of MEME. We see that the im- provements from amplification over the unamplified baseline are far larger than the loss in utility due the suboptimal batching introduced by the sampling scheme. To the best of our knowledge, this is the first DP model training result that simultaneously (i) implements the sampling scheme assumed when computing the noise multiplier, (ii) does so at a negligible cost in efficiency and in a manner compatible with modern machine learning frameworks, and (iii) still demonstrates improvements over the unamplified baseline.
30

---

Published as conference paper ICLR 2025
J DIMENSIONALITY REDUCTION AND ADAPTIVITY
To find dominating pair for matrix C, we typically wish to argue that the worst case PLD is generated by a user that only ever inputs the same entry every iteration. This simultaneously handles dimension reduction and adaptivity and is the strategy for unamplified privacy analyses (see, e.g.. Choquette- the MEMF case, for to be the case that the worst-case PLD is achieved by a user always outputting the same vector, it suffices to require C. C.j for all indices i. j for which in. However, this no longer the case for balls-in-bing sampling, even in a very simple case. Consider the matrix
et al. (2022), ).
can simultaneously appear
C= (-113 9)
with epoch. Then, the user only participates in exactly one of the first column the second. Say the user's inputs are (a, b), where a, b f [-1,1], 1}, which means that the MoG representing it
(() _ (((,b),,
Then, maximizing the inner product between (a. -a) and (0. will dominate the PLD w.r.t N(0, o2). This is then maximized at -a, rather than a. Thus, for balls-in-bins sampling, the inner products across columns that user cannot simultaneously participate in matters. Noting that this example hinged on the inner product between the two columns being negative, it is possible that C C 0 entry-wise sufficient to show that user may well only input the same vector.
31


Reviews:
[{"review_id": "6iQisobYLN", "reviewer": "Reviewer_9yen", "summary": "This paper investigates the computation of privacy parameters for differentially private (DP) machine learning, specifically when using privacy amplification through random batching and noise correlated across rounds via a correlation matrix C. Previous work either restricted C to banded matrices or provided loose privacy parameters. The authors introduce a framework for computing near-exact privacy parameters for any lower-triangular, non-negative C, optimizing C while considering amplification. They show empirical improvements over the state-of-the-art in root mean squared error (RMSE) for prefix sums and performance on deep learning tasks. The key techniques include Monte Carlo accounting to avoid composition and a balls-in-bins batching scheme for practical random batching.", "questions": "- Could the authors interpret \"near-exact\" privacy analysis by:\n  - Provide a more precise definition or explanation of what it means by \"near-exact\".\n  - Discuss the potential impact of the looseness in $P$ on the overall privacy guarantees, given that the construction of $P$ in the dominating pair is potentially too loose.\n\n- In lines 358-364, the authors discuss the choice of $b$ in experiments, which is chosen from the set {$ 1, 2, 4, 8, 16, 32, 64, 128, 256 $}. How does the (sub)optimal choice of $b$ vary with the other key parameters (e.g., $\\varepsilon$)? Could the authors briefly discuss the intuition behind these variations, or include an ablation study showing the impact of suboptimal b choices on performance? \n\n- The authors note that the \"balls-in-bins” batching scheme enables easy privacy analysis. However, will the practical variant of balls-in-bins batching in Appendix H complicate the privacy analysis? Would it encounter the same difficulties in privacy analysis as Poisson sampling?\n\n- In line 280, the authors mention that the bisection requires $O(\\log(1/\\delta))$ iterations, where $\\delta$ is supposed to be the privacy parameter in $(\\varepsilon, \\delta)$-DP. However, should it be $O(\\log(1/\\text{err}))$, where $\\text{err}$ is the error tolerance of $\\sigma^*$?\n\nMinor:\n- Figure 1 explains the amplification methods quite well. However, I would suggest additional notes indicating that the first row corresponds to the batches in the first epoch (e.g., $E = 1$), and that the second row is the second epoch (e.g., $E = 2$).\n\n- In the introduction, the authors mention that one of the limitations of previous work is the banded $C$ issue. Could the authors provide the key intuition as to why the banded $C$ may restrict utility and efficiency, or discuss any specific scenarios or applications where non-banded C matrices are particularly beneficial?\n\n- In Appendix H, for the practical variant of balls-in-bins batching, the authors pad the small batch with some zero-gradient examples to avoid wasted computational resources. Could the authors further explain why wasted computational resources would be a problem?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Propose a more practical minibatch sampling method, the Balls-in-Bins, that achieves better privacy amplification.\n\n- Use Monte Carlo accounting to bypass composition. The limitations of the current work are well-discussed, especially the limitation of the construction of P.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "zrK9cD9cX9", "reviewer": "Reviewer_7a3D", "summary": "In this paper, the authors propose a ``balls-and-bins'' batching scheme, for which the privacy analysis is quite straightforward (by analyzing hockey-stick divergence of the `dominating pairs'). Based on their novel batching scheme, the authors use Monte Carlo accounting to estimate the privacy parameter and avoid the estimation errors introduced by DP composition theorems. The experimental results indicate that their scheme performs better than existing works.", "questions": "- What is the ``practical random batching'', and why is the balls-and-bins scheme approximates it better than Poisson sampling?\n- Can the authors provide a proof for the monotonicity between $\\sigma$ and $\\delta$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, and the theoretical results seem to be correct (I didn't check the full proof carefully, but I believe it makes sense at a high level).", "weaknesses": "- In the abstract, the authors claim that the ``ball-and-bins'' scheme is closer to practical random batching than Poisson sampling. But there is no theoretical explanation in the paper. Not sure if I miss anything here.\n- The Algorithm 2 applies bisection method to compute the $\\sigma$. But the proof of monotonicity is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "VdDL2XWQn2", "reviewer": "Reviewer_6FLQ", "summary": "The paper provides a differential privacy accountant for the \"ball-in-bins batching\", where the disjoint mini-batches for DP-SGD are formed via multinomial sampling. A particularly nice property of the accounting method is that it can be combined with so-called matrix mechanisms, where correlated noise is added to the DP-SGD iterations. The accounting is based on the randomized differential privacy accounting framework provided by [Wang et al., 2023](https://proceedings.neurips.cc/paper_files/paper/2023/file/6ae7df1f40f5faeda474b36b61197822-Paper-Conference.pdf), where Monte Carle sampling of the hockey-stick integral (when expressed using the privacy loss distribution) is carried out. This is enabled by Lemma 3.2 which gives a dominating pair of distributions $(P,Q)$, where $P$ can be sampled efficiently and $Q$ has a tractable density function. This way, the PLD can be sampled and the hockey-stick integral estimated.", "questions": "- In Lemma 3.2: What exactly guarantees that $(P,Q)$ dominates the pair $(Q,P)$ (for those stated $P$ and $Q$) ? I think the proof of Lemma 3.2 could be elaborated to make it more readable. Perhaps you could add the required results from the reference paper (Choquette-Choo et al., 2024b) to the appendix instead of shortly referring to the lemmas and theorems (example: \"see e.g. the first part of proof of Theorem 4.8\").\n\n- What would be required to for providing convergence guarantees for the estimates? Could you use the results by Wang et al. for that?\n\n- As I said I assume the analysis is for the add/remove neighborhood relation of datasets. In addition to adding it somewhere (e.g., Section 2), you could briefly discuss in Section 3 how the results might change (or not) for the substitution neighborhood relation.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a novel and practical mini-batch sampling scheme applicable to matrix mechanisms. \n\n- Seems like a novel way for using the randomized accounting framework proposed by Wang et al. (2023). To the best of my knowledge, this is the most \"non-trivial\" use of that framework and sets an example that the Monte Carlo sampling is viable tool for differential privacy accounting and designing DP mechanisms.\n\n- Although the convergence analysis is missing, and there are many future questions (e.g., the tightness of the dominating pair and the efficiency of the sampling), the paper gives convincing experimental results indicating this is a viable way of carrying out privacy accounting for the proposed mini-batch sampling scheme.", "weaknesses": "- The theory is a weak side of the paper. There are really no theoretical guarantees given for the accuracy of the estimates. Theorem 2.1 is stated (Theorem 9 by Wang et al., 2023) however there are no results that would materialize this result. Also, I think it would be good to elaborate on that result, especially since it is stated so differently than Theorem 9 by Wang et al.\n\n- The paper is not fully polished: I don't see the neighborhood relation of datasets stated anywhere. Due to the form of the dominating pair $(P,Q)$ given in Section 3, I assume you consider the add/remove relation. Perhaps the definition you use could be added somewhere in Section 2?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "bFlHoKz5vb", "reviewer": "Reviewer_kfPY", "summary": "This paper presents an algorithm for calculating privacy parameters in differentially private SGD when using privacy amplification through random batching and noise correlated across rounds via a correlation matrix, known as the matrix mechanism.", "questions": "1. How to derive high-confidence bound for the monte-carlo simulation results?\n\n2. Can the authors provide the noise parameter or the noise variance in Figure 4 to help readers understand the amplification? The accuracy itself does not tell too much meaningful information as the performance of SGD may be influenced by many other factors. \n\n3. Can the authors comment more on why in large eps, the proposed method performs much worse compared to subsampling amplification?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper studies a very important problem, balls-in-bins batching with correlated noise, an alternative privacy amplification method in DP-SGD different from the classic subsampling amplification. Existing methods for analyzing privacy in this setting have drawbacks, especially with specific types of correlation matrices (banded matrices). The simulation method proposed shows an interesting and simple way to estimate the security parameter for arbitrary correlation matrix, which can be further used to optimize the noise form.", "weaknesses": "1. A significant limitation of the results is that, while a concrete simulation algorithm is presented, the paper lacks formal high-probability or confidence bounds for the computed DP security parameter. This absence leaves ambiguity about the paper's contribution: whether it offers merely a heuristic estimation or an approach with provable guarantees. My evaluation could improve if high-confidence bounds were provided.\n\n2. The paper does not provide a closed-form or asymptotic bound for the amplification rate produced by the methods, or, equivalently, an indication of the amount of noise required or potentially saved. This lack of theoretical clarity makes it difficult to determine the extent of improvement the method could yield beyond empirical optimization of the noise form.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)