Scaling up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private ML
Authors: Ryan McKenna
Venue: ICLR 2025 Spotlight (2025)
Keywords: differential privacy
large models
DP-SGD
matrix factorization
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose new techniques to improve the scalability of the banded matrix factorization mechanism, which is the current state-of-the-art mechanism in the DP-MF family.

Abstract: Correlated noise mechanisms such as DP Matrix Factorization (DP-MF) have proven to be effective alternatives to DP-SGD in large-epsilon few-epoch training regimes.  Significant work has been done to find the best correlated noise strategies, and the current state-of-the-art approach is DP-BandMF , which optimally balances the benefits of privacy amplification and noise correlation.  Despite it's utility advantages, severe scalability limitations prevent this mechanism from handling large-scale training scenarios where the number of training iterations may be more than $10^4$ and the number of model parameters may exceed $10^7$.  In this work, we present techniques to scale up DP-BandMF along these two dimensions, significantly extending it's reach and enabling it to effectively handle settings with over $10^6$ training iterations and $10^9$ model parameters, with no utility degradation at smaller scales.

Published as a conference paper at ICLR 2025
SCALING UP THE BANDED MATRIX FACTORIZATION MECHANISM FOR DIFFERENTIALLY PRIVATE ML
Ryan McKenna"
ABSTRACT
Correlated noise mechanisms such as DP Matrix Factorization (DP-MF) have proven to be effective alternatives to DP-SGD in large-epsilon few-epoch training regimes. Significant work has been done to find the best correlated noise strategies, and the current state-of-the-ant approach is OP-BANDMF, which optimally bal- ances the benefits of privacy amplification and noise correlation. Despite it's utility advantages, severe scalability limitations prevent this mechanism from handling large-scale training scenarios where the number of training iterations may exceed 10s and the number of model parameters may exceed 10". In this work, we present techniques to scale up DP- OP-BANDMF along these two dimensions, significantly extending it's reach and enabling it handle settings with virtually any number of model parameters and training iterations, with negligible utility degradation.
INTRODUCTION
Modern machine learning is done at unprecedented scales; state-of-the-art large language models have billions of parameters and are trained on super computers with thousands of accelerators for hundreds of thousands of iterations (Kaplan et al., 2020; Chowdhery et al., 2023). Many applications would benefit from training these large-scale models on user data, but this raises a host of privacy concerns (Yao al., 2024). Differential privacy (DP) offers formal definition and algorithmic framework to train such models while protecting individual- used DP mechanism for machine learning is DP-SGD (Abadi et al., 2016), of which there are many variants. DP-SGD relies crucially on privacy amplification by subsampling, and generally benefits significantly from training with huge batch sizes for many epochs (Ponomareva et al., 2023), which can be difficult infeasible in large-scale compute-constrained settings. A promising alternative, the DP-FTRL algorithm (Kairouz et al., 2021b) instead relies on carefully correlated noise, and tends to work better than SGD when training with smaller batches and fewer epochs, especially in the low privacy regime (c R 10) that is common in real-world scenarios.
information. The most widely
There are many variants of the DP-FTRL algorithm that primarily differ in how they generate cor- related noise (Kairouz et al., 2021b; Denisov et al., 2022; Choquette- Choo et al., 2023b; 2024; McMahan et al., 2024a; Fichtenberger et al., 2023; Henzinger et al., 2023; Kalinin & Lampert, 2024; Choquette-Choi Chho et al., 2023a). The best variants of the DP-FTRL mechanism utilize numerical optimization to find the best noise correlation strategy, and are usually referred as matrix factor- ization mechanisms (DP-MF). The space of DP-MF mechanisms is rapidly evolving, with recent work focusing intensely on improving the constant factors (Denisov et al., 2022: Choquette-Chi Chho et al., 2023b; 2024). The variant with the best constant factors in this space is the Banded Matrix Factorization mechanism (OP-BANDMF), which utilizes banded correlation matrices and enjoys the benefits of both privacy amplification and noise correlation. By setting the number of bands to one, DP- BE-NDNMM reduces to DP-SGD, and by setting the number of bands equal to the number of training iterations, DP- BF-ANNDM reduces to un-amplified variants of DP-MF. By optimally choosing the number of bands, DP-B BP-BANDMF enjoys significantly better constant factors than both DP-SGD and other MF-stle mechanisms in many settings.
Despite its advantages, severe scalability limitations of DP- DP-BANDMF (and other DP-MF -tsylle mechanisms more broadly) has hindered its wider use, and prevented it from scaling effectively to large-scale training regimes where typical models have billions of parameters and are trained for tens
"Google Research, mckenna reckenna@@goggee com

---

Published as a conference paper at ICLR 2025
to hundreds of thousands of iterations. Existing DP-BANDMA implementations face computational bottlenecks stemming from two places: (1) an expensive optimization problem linked to the n x n strategy matrix C (where is the number of training iterations), requiring ((n²) time and O memory to evaluate the expected error, limiting its use to approximately 10* training iterations. (2) During training, 3P-BANDMF incurs ((b- d) memory overhead (where b is the number of bands in C. and d is model dimensionality),, which is bx more than DP-SGD but "/ox less than DENSE- DP-MF. In this work, we develop techniques to overcome DP-BANDMF's scalability limitations, without sacrificing on the constant factors that make it an appealing mechanism:
Efficient Strategy Optimization: We exploit the structure of banded strategies to reduce the per-iteration complexity of strategy optimization to 0b) time and ((n-)) bb) space, which allows DP-BANDMF to scale to approximately n 10 training iterations. For scenarios demanding even more iterations (up to and beyond n > 10'), ), we restrict attention to banded Toeplitz strategies, whose structure enables O(n- 6) time and (nx) space complexity during strategy optimization. Experiments show the approximation quality loss to be less than 2% in terms expected error.
Distributed Noise Generation: Prior implementations of DP-MF-style mechanisms add noise on a single machine, even when training is coordinated across 1000's of machines (Denisov et al., 2022; Choquette-Choo et al., 2023b). We show how to effectively distribute the noise generation process, allowing DP-BANDMF to effectively take advantage of multi-machine environments common in large scale training regimes, and scale to larger models and more bands than was previously possible. Experiments demonstrate negligible training-time overhead compared to DP-SGD, even with hundreds of bands.
State-of-the-art Performance:
We conduct comprehensive experiments on expected error, and show that our scalable 3P-BANDMF mechanism offers lower expected error than all other scalable MF-style mechanisms across all settings tested, including DP-SGD, and concurrent works that also improve scalability of DP-MF (McMahan et al., 2024a;b; Kalinin & Lampert, 2024).
BACKGROUND
We assume the reader has familiarity with differential privacy (Dwork, 2006; 2008). Below provide background on DP-BANDMF, which includes DP-SGD and DP-MF-style mechanisms as special cases. DP-BANDMF is completely characterized by b-banded lower triangular strategy matrix! C E Ruxx (i.e., Cip 0 i < or isjtt
2.1 TRAINING DYNAMICS
OP-BANDMF (Algorithm 2) is similar to the more well known DP-SGD algorithm (Abadi et al., 2016): minibatches are sampled randomly, gradients clipped and aggregated, and noise is added to preserve privacy. The key innovation of -.--BANDMF is in the noise addition step: while DP- SGD adds i.i.d. Gaussian noise in each iteration, DP OP-BANDMF adds noise from richer class. Specifically, the strategy matrix C is used to generate noise that is correlated across iterations, and the key subroutine for generating this correlated noise is shown in Algorithm
When instantiated with I (the identity matrix, = 1), Algorithm is identical to DP-SGD, as is easy to verify the output of Algorithm is simply the i.i.d. Gaussian noise vectors z, passed input. When instantiated with a dense lower triangular strategy matrix C (b n2), Algorithm 2 captures
sometimes simply referred the "strategy".
Algorithm Banded Inverse Multiplication (Choquette-Choo et al., 2024)
Input: lower triangular b- b-Banded matrix C pnxa stream of vectors Z Zi...., Zn E Rdd where Z is the matrix with rows z;- Output: Y C one for = 1,..., n do
time.
y; = (z, E Ciyy,)/Ca
yield y;
2

---

Published as a conference paper at ICLR 2025
Algorithm 2 Iterative Machine Learning with DP-BANDME
Input:
b-banded strategy C' RR**, noise multiplier o, loss function E, initial parameters wo. dataset D, expected participations k, clipping norm R
Output: Learned parameters w/.
Partition D into b (approximately) equal sized subsets Do.... arbitrarily
for y, Algorithm [(C,z; z, "i.dd N 1)d) do
Stream of correlated noise
Sample B S D; mod by Poisson sampling each example with probability M/nn.
g: Σxer clip( (V((W(11;=).
>> Clipped + aggregated gradient D Noisy (privatized) gradient
g. = g: + Roy;
wi Update w
Post-processing noisy gradient using any optimizer
return wn
DENSE-DP DP--- (Denisov et al., 2022). DP-SGD benefits from privacy amplification by sampling but uses uncorrelated noise while DENSE-DP-MF benefits from correlated noise, but does not enjoy any privacy amplification due to sampling. DP-SGD tends to work better in the small-epsilon, many-epoch regime, while DENSE-DP-MF tends to work better in the large-epsilon, few-epoch regime (Choquette-Chee et al., 2024). By using a b-banded strategy matrix, DP-BANDMF operates between these extremes and benefits from both privacy amplification by sampling and correlated noise. Specifically, the proposition below states that the privacy properties of DP-B OP-BANDMF relate very naturally the simpler DP-SGD mechanism whose privacy properties are well-understood.
Proposition 2.1 (Noise Calibration (Choquette- Choo al., 2024)). Let OSGD 6, k n) denote the noise nultipliier required for DP-SGD to achieve (e, (D when run for iterations with sampling probability 1/n. Given a b-banded strategy matrix C satisfying || I 1, Algorithm 2 satisfies (cP for F = a (c 8, k. 7/b).
The function OSGD is typically computed using numerical privacy accounting methods such as the PLD accountant (Sommer et al., 2018; Doroshenko al., 2022).
Remark 2.1 (Memory Overhead). Algorithm requires storing a state of size bxd (y:-l..... y i- 1). where b is the number of bands and d is the model dimensionaliry. This is bx larger than DP-SGD, but n/ex smaller than DENSE-DD -D-NF- For large models (d 10*) and many bands 100), this can require hundreds of Gigabytes of space.
2.2 STRATEGY OPTIMIZATION
In this section, we describe how DP- DP-BANDME optimally selects the number of bands b and the strategy matrix C. The matrix C and it's number of bands chosen by solving a numerical optimization problem minimize the expected total squared error added to the (clipped + aggregated) minibatch gradients during training.
Proposition 2.2 (Expected Error (Choquette-Choo et al., 2024)). The expected total squared error of DP-BANDMF given a b-banded strategy matrix C is equal to:
AC ||| = r. (E,
(E, 8, n) (CI
where [[]|,,2 is the maximum L2 column norm of C and is related to it's sensitivity, and A the workload, typically taken be the lower triangular matrix of ones (Kairouz et al., 2021b), and a BondME's F (E, 8, b, k. n) = (sCD(e,&) 5, n/b) is the noise multiplier required to run -P-BANDMF under the given privacy budget.
The optimization problem at the heart of DP- DP-BANDMF follows immediately from this expression and stated below. Note that smaller values of 6 give better privacy amplification (smaller a BandMF), but reduces the benefits of correlated noise (more restricted space of strategies). Since b is a discrete parameter, we solve the un-am un-amplified version of the problem for fixed b s [1,n] (not accounting for a F)n F), and choose the strategy matrix and number of bands that minimizes expected error accounting for a BandM F in a brute force manner.
Strategy Optimization (Choquette-Chie Choo et al., 2024)). Given a work- load matrix A, and the desired number of bands b, the optimization problem underlying DP- OP-BANDMF
Problem 2.1 (DP-BANDIN
3

---

Published as a conference paper at ICLR 2025
Algorithm 3 (Efficient) Expected Total Squared Error
Input: O E 62
Output: |AC())
bo 0
loss 0
for = ,,...,, n do
e, f row of the n identity matrix
Ei=1
>> Column normalization constant > thh row of C(e)-1
Yi (e: 2==1 O,.r,)/01:
b; b; +y;
jth row AC(@)-1
loss += b. b;
> partial squared Frobenius norm
return loss
can be formulated as:
minimize
|| 11 subject to Ciy =0 if or
(I)
Absent the bandedness constraint, this optimization problem has received considerable attention (Li al., 2015; Yuan et al., 2016; McKenna et al., 2023; Denisov et al., 2022), and the algorithm for solving it in the banded case is closely related (Choquette-Choo et al., 2024). Prior work (Choquette- Choo et al., 2024) solves Problem 2.1 by reformulating it in terms of the object X CTC. This reformulation is convex and unconstrained, meaning standard optimization tools like L-BFGS can efficiently find the best solution with access to an oracle that computes the loss and gradient with respect to X. We note that the problem as it is stated in Problem 2.1 is nol convex with respect to C (Li et al., 2015; Yuan et al., 2016; McKenna et al., 2023; 2018). The drawback of this solution approach is that it materializes several n matrices in each iteration, even though there are only roughly n free (non-zero) variables. As a result, it requires O ) time and (nz²) space to evaluate the objective once, and cannot be practically done beyond n. 10
3 SCALABLE STRATEGY OPTIMIZATION AND NOISE GENERATION
In this section, we propose two approaches to implicitly compute the objective function, bypassing the need to materialize x matrices explicitly. These innovations enable scalability up s 10 and n > 10" respectively. For simplicity, we specialize the presentation to the Prefix workload (lower triangular matrix of ones), banded strategies, and the expected total squared error objective (Proposition 2.2). In App. D, we show that the same core approach taken here easily translates to more general classes of workloads, strategies, and objective functions.
3.1 EFFICIENT STRATEGY OPTIMIZATION
The complexity of solving Problem 2.1 using L-BFGS is proportional to the complexity of evaluating the objective function and its corresponding gradient. Our first key idea to scale up DP-BANDMF is utilize Algorithm
efficiently evaluate the objective function. Specifically, one row of AC-1 at a time and compute the norm in an online fashion as shown in Algorithm 3.
will materialize
Let θ be b n matrix of parameters which will define our banded strategy matrix C(O). We define C(O) to be the column-normalized b-banded matrix satisfying: Cij @ /1as/// 9 By construction, we have || C(e) 1. Thus, to evaluate the objective function we simply need to compute (AC())- 11 and Algorithm gives an algorithm for doing that efficiently. The key idea is to generate rows of AC(@)-1 one at a time and compute the Frobenius norm a streaming manner.
Each iteration of Algorithm 3 requires O(n b) time, as the vectors e; and y, are size n, and there is a sum over b such vectors. Thus, the total time complexity of Algorithm 3 is O(n² 2..... .b). The algorithm
4

---

Published as a conference paper at ICLR 2025
must keep track of y : Yy in each iteration, and hence the space complexity is ( -b). This is a factor improvement in both the time and space complexity of OP-BANDMF, which can be substantial when the number of bands is small (which it often is, we demonstrate in Section 4). While Algorithm is specialized to the class of columm-normaliizdd banded strategies and the Prefix workload, the core approach is easy to generalize other parameterized classes of strategies and more general workloads, as we discuss in App. D.
Our L-BFGS algorithm also requires the gradient of the objective function run efficiently. We do not derive that here, but rather rely on Jax's 's reverse-mode auto-differentiation capabilities instead (Bradbury et al., 2018). Depending on how the gradients are computed, the gradient computation can be more time and memory intensive than the loss calculation. We discuss this more in depth in App. and provide some experiments on the scalability of this approach Section 4. Using these ideas, we can scale DP- MF-BANDMF up to roughly 10 under reasonable time and memory constraints, without sacrificing any solution quality over prior work (Choquette-Chel Chho et al., 2024).
3.2 OPTIMIZING BANDED TOEPLITZ STRATEGIES
We now explore another technique that is even more scalable, while only sacrificing a small amount in terms of expected error. Our key idea is to restrict attention to the special class of banded Toeplitz strategies. This design decision was inspired by manual inspection of the optimal dense strategies, observing that they exhibit near- Toeplito structure. By exploiting the special structure of this class of strategies, we can evaluate the objective function using only O(n b) time and O(n) space, and scale strategy optimization up to and beyond 10 we show below:
Proposition 3.1 (Banded Toeplitz Expected Total Squared Error). Let 0 e Rh be Toeplitz coefficients, such that C(0)ss = 0 0i-j+l, and let w = C(0)- 11. The expected total squared error is equal to:
-1.
|C(()) 1012
|AC( (n)m
Proof: The first expression states that the maximum L2 column norm of a lower triangular Toeplitz matrix is equal to the norm of it's first column 0. By direct inspection, the first n n- b columns
of C(O) all share the same non-zero entries of O, and the norms of these columns are thus ||0|p- The non-zero entries of the remaining b b-1 columns of C(0) correspond to subvector of 0, and hence these columns have norm [0]2- The second expression states that the Frobenius norm can be calculated without explicitly materializing any matrices. Note that both A and C(0) are lower triangular Toeplitz matrices, and if C(0) is invertible, then its inverse is also lower triangular Toeplitz. matrix (Lin, 2008, Lemma 5). Second note that multiplication is commutative within this class, and therefore (0) (O) A, and this product is itself a lower triangular Toeplitz matrix (Lin, 2008, Lemma 5). As such, it is completely defined by its first column w. Using the definition of matrix multiplication we can obtain w by multiplying C-1 by the first column of A, which is 1 (Lay, 2003, Page 97). The squared Frobenius norm of a Toeplitz matrix with parameters w can be calculated directly over this vector by observing that wi repeated along the e diagonal band of the Toeplitz matrix and hence appears (n i 1) times, leading to the expression stated above for the squared Frobenius norm of (G))
We note that this approach generalizes to any Toeplitz-structured workload, as we show in App. D. The complexity of evaluating the objective function is determined by the cost of solving the linear Toeplitz system w = -10 which can be done with Algorithm I in O(n 6) time and O(b) space. In App. we further reduce the time complexity to O(b²) by observing that the sequence w; rapidly converges to a fixed point, which allows scalability to virtually any n (as long as b is not too large).
Column Normalization In general the column norms of Toeplitz matrices are not all equal, a property that optimal strategies are known to have in the 2018; Yuan et al., 2016; McKenna et al., 2018) and property built-in to DP-BANDM (Choquette- Choo et al., 2024). When the number of bands is small, the loss in solution quality from not column normalizing is small, as the first b columns of a banded Toeplitz strategy already have equal norm. Moreover, we can always normalize the columns of the banded Toeplitz matrices as a post- post-processing step after strategy optimization, which recommend in practice.
setting (Zhang et al.,
5

---

Published as a conference paper at ICLR 2025
3.3 DISTRIBUTED NOISE GENERATION
At training time, DP-BANDMF incurs a b d memory overhead where is the number of bands and d is the number of model parameters. In large-scale settings d may exceed 10", and assuming b = 256 and 4-byte floats are used, this is a very significant one terabyte cost. In this section, we will argue that with careful implementation, this is not major issue in typical large-scale training regimes.
We make two key observations. First, in order to train large models with differential privacy, large batch sizes are typically needed, which requires combination of coordinated training across many accelerators and virtual batching (De et al., 2022; Anil et al,, 2022). For example, to train a 1 billion parameter model with DP, one might use 1024 machines and 16x virtual batching to attain a reasonable batch size of 16384 (assuming a per core batch size of 1). Second, we can effectively utilize multiple machines when generating noise by observing that Algorithm I can be translated an embarrassingly parallel algorithm since each coordinate of the noise vectors are treated identically.
In our implementation, each machine in charge of producing a different shard of the noise vectors y,, and they keep track of the state required to generate that noise locally." This state corresponds to the same shard of the
Yrast ...
Y-1
Y
y;
model size (d)
GPU 1
previous b 6-1 1 correlated noise vectors (y--1...... " Vs-b+)), and this sharding strategy is illustrated in the figure to the right. This benefit of this sharding strategy is that no communication is needed between machines until the noise is added to the clipped + aggregated gradient. Using the example above, this implementation would have very manageable overhead of one GB per machine (one TB split across 1024 machines).
GPU 2
GPU
GPU 4
# bands (b)
In Section 4.2 we demonstrate that in practice the number of bands needed is typically far less than 256, and that the overhead incurred by our distributed correlated noise generation algorithm is small compared to the cost of per-example gradient clipping, even when the number of bands large. To better understand the scalability limits of this distributed noise generation approach in different settings, it useful to look at a few more illustrative examples.
Example 3.1. Suppose want to train 4 million parameter model on a single GPU with memory limit of GB. We can afford to store roughly 64 copies of the model assuming each parameter is represented 4-byte float. This allows to use roughly 64 bands overall.
Example 3.2. Now suppose we want to train larger 128 million parameter model in parallel on 64 machines, which is usefullneeded to get the large batch sizes usually used with large models and DP training. By parallelizing the noise generation code across these 64 machines, 2 copies of the model per machine, allowing us to use roughly 128 bands overall.
afford to store
Example 3.3. Now suppose we want to finetune an billion parameter model on 64 machines, and use parameter-efficien fine-tuning method such as LoRA (Hu et al., 2021; Yu et al., 2021) Further, assume the number of learnable finetuning parameters is 4 million. Now, the cost of the forward/backward pass completely dwarfs any overhead of noise generation. We can store 64 copies of the model per machine, and parallelize computation across 64 machines, allowing us to run DP-BANDMF with up to 4096 bands.
EMPIRICAL RESULTS
In this section, we empirically evaluate our proposed strategy optimization algorithms in terms of solution quality and scalability. Then, conduct experiments and perform analysis to understand the optimal number of bands as a function of the relevant parameters. Our analysis reveals that in many scenarios of practical interest the optimal number of bands is small, and consequently the overhead of (RMSE),
DP-B BANDMF at training time is small. Our experiments focus on root-mean mean--quared-eee which we compute in closed form using Proposition 2.2, dividing by n and taking the square root. Strategy optimization is done on an NVIDIA V100 Tensor Core GPÚ for up to 10K iterations.
"this strategy for distributing noise generation is very different from distributed differential privacy (Kairouz al., 2021a), where each client/machine generates entire vector of noise with smaller variance.

---

Published as a conference paper at ICLR 2025
RMSE Suboptimali lit Ratio
Optimization
DP-SGD
Exploit Banded Structure [Ours]
Tree Aggregation
2.00
Banded Toeplitz [Oure]
Stamping
1.50
Banded Sert [Concureet]
125
DP-BLT T-MF
1.1
Unamplified BandMF
Amplified BandMF
1.02
1.00
10
10
10
10"
10
10P
10
Training Iterations (n)
Epsilon
(a) b = 16
(b) n. 16384, &
Figure (a-b) Ratio of RMSE of each strategy to the best strategy that scales to each setting. (a) Compares our scalable banded and banded toeplitz strategies with other banded strategies. (b)
Compares our scalable DP-BANDMF with non-banded strategies as a function of
4.1 COMPARISON PRIOR AND CONCURRENT WORK
We begin by evaluating the solution quality of our strategies compared to prior and concurrent work. We provide a thorough qualitative comparison between the mechanisms considered here App. G. In Figure la, fix b 16 while varying and compare our strategies obtained through implicit optimization to the strategies produced through explicit optimization as in prior work (Choquette- additional baseline, which was proposed
Choo al., 2024). We also include BANDED SQRT in concurrent work (Kalinin & Lampert, 2024), and avoids dense matrix representations through the same banded Toeplitz structure we consider. We plot on the y-axis the RMSE Suboptimality Ratio, which we define as the ratio of RMSE between given strategy and the best available strategy for that setting. Because all the strategies in this figure are 16-banded, they enjoy the same privacy properties (whether they are used in amplified or non-amplified setting), and therefore the RMSE Suboptimality Ratio's 's we report hold for all e. The highlights from this experiment are four-fold:
The prior work that represents the strategy using dense matrices scaled up to n < 10 while our implicitly optimized banded strategies scaled up to 105, and our banded Toeplitz strategies scaled well beyond > 10". We provide more detailed scalability results in Figure 4 of App. F.
Our implicit strategy optimization algorithm for general banded matrices converges to the same solution as prior work (Choquette-Choo et al., 2024) for all settings tested (where the latter successfully ran). This is encouraging in light of the fact that we directly optimize C (rather than X C C) and Problem 2.1 is not convex with respect C.
The BANDED SQRT baseline approach (Kalinin & Lampert, 2024) achieves worse expected error across all settings than both of our approaches. The suboptimality approaches up to 25% in the settings we tested, with larger suboptimality for larger
Toeplitz strategies are between 0-2% suboptimal. with suboptimality increasing with the number of bands and decreasing with the number of iterations. For large n 2 16384 and small & s 32, which is the regime of most interest, the suboptimality is s 0.25%, indicating arbitrary banded strategies do not provide much benefit over the more restrictive class.
Our coolumn-normaliza
In Figure 1b compare against several additional baseline mechanisms for 16384 iterations and k == epochs while varying e. We include results for DP-SGD (Abadi et al., 2016), Tree Aggregation (Kairouz al., 2021b), Stamping (Denisov et al., 2022), FHU (Fichtenberger al., 2023), Buffered Toeplitz, (McMahan et al., 2024a;b). and our Unamplified and Amplified scalable DP-BANDMF approach. We omit from comparison DENSE-DP-MF (Choquette-hool et al., 2023b) due to scalability limitations of that approach for n 16384.
Here, SGD and Amplified OP-BANDMF benefit from privacy amplification, while the other mechanisms do not. Our highlights from this experiment are two-fold:
Amplified DP-BANDMF is better than all other mechanism across all settings evaluated. The improvement over SP- grows with e, while the improvement over other mechanisms decreases with The best alternatives are either DP-SGD or Buffered Toeplitz, both of which have 2x
7

---

Published as a conference paper at ICLR 2025
0.0625
8
4
2
2
2
2
2
1024
RMSE Suboptimality Ratio
0.125
16
8
2
2
2
2
512
3.00
256
0.25
32
16
8
4
2
1
1
2.00
122
0.5
64
32
4
2
7
64
1.25
1.0
64
643210
8
1
32
1.12
Epochs (k)
2.0
64
16
8
4
2
166
1.06
4.0
64
32
16
4
2
1
1.03
8.0
64
32
8
1
1.02
16384
16.0
64321
16
8
4
2
10
16
10
16
32
64
128
256
512
1024
Bands (b)
Epochs
(a) Bands vs. RMSE
(b) Optimal Number Bands
Figure 2: (a) RMSE Suboptimality Ratio (relative to full-batch DP-SGD) of DP-BANDME
function of for various epochs, with fixed (c, 6) = (1, 10 and n 16384. (b) Optimal number of bands (within factor of 2) function of the privacy budget and the number of epochs, fixing n = 4096 and 1
worse RMSE for 1. Amplified DP-BANDMF still enjoy meaningful 19% better RMSE than the best competitor for e as large as
Unamplified DP-BANDD BANDMF is the best non-amplified mechanism that can scale to this setting, and enjoys 5% lower RMSE than Buffered Toeplitz strategies for all e. While our primary focus has been in centralized training regimes, this figure shows that DP-BANDMF is also state-of-the-art approach in federated scenarios where amplification is not feasible (Kairouz et al., 2021b).
While we focused single value of n and k in Figure 1b, general findings remain unchanged for other settings, although the magnitude of the improvements do change. For completeness, results for other values of and & shown in Figure 7 in App. F.
4.2 OPTIMAL NUMBER OF BANDS
We now perform ablation on DP-BANDMF to understand how to select the number of bands in practice, how the performance of DP-BANDMF changes as a function the number of epochs. Figure 2a plots the RMSE suboptimality ratio of DP-BANDMF relative the full-batch DP-SGD baseline for different values for epochs and bands fixing at 1. Figure 2b plots the optimal number of bands for different values of epochs and Our findings from these experiments three-fold:
With only 32 epochs, DP-SGD (b = 1) has nearly the same RMSE as full-batch DP-SGD (16384 epochs), but the RMSE degrades rapidly with fewer epochs. Unamplified DP-BANDMF (b = n/x) achieves worse RMSE than DP-SGD when the number of epochs is large (and utility is the best), but it degrades more gracefully than DP-SGD, offering better utility in the few-epoch regime. Amplified DP-BANDM (b b..) offers the best of both worlds: full-batch DP-SGD-level performance when the number of epochs sufficiently large, and even more graceful degradation of RMSE with respect to number of epochs than Unamplified DP-BANDME
The RMSE improves predictably with increasing epochs, but there are diminishing marginal returns. For example, the RMSE of Amplified DP- ----BANDMM is < 2x worse than the RMSE of full-batch DP-SGD with only two epochs, and < 18% worse with only eight epochs. We note that RMSE only accounts for the noise added due to privacy; increasing the number of epochs under fixed number of iterations increases the batch size, which also reduces the minibatch gradient variance.
The optimal number of bands drops predictably with increasing epochs and decreasing epsilon. Specifically, the dependence appears roughly linear both parameters, and a good rule of thumb is that b, </n/s should be near-optimal. In some parameter regimes. like == 16. b, may be too large to feasibly handle. However, Amplified OP-BANDMF with a suboptimal number of bands is still better than the alternative of DP-SGD.
8

---

Published as a conference paper at ICLR 2025
Cloped
Bond
Well Cbock (weca)
Bands
@bpesGGradeettg
Cross Entroge
Bands
Condlated
14
MPF-BLMMF))
12
12"
12th RASEE
Bands
(a) Noise Generation Time
(b) Adaptive Optimizer
(c) Non-Adaptive Optimizer
Figure 3: (a) Wall Clock Time for correlated noise generation and per-example gradient clipping for 100M parameter BertBass model when on 32 TPU v3 cores. (b-c) RMSE vs. Learning Performance (evaluation cross entropy) with an adaptive optimizer (b) and a non-adaptive optimizer (c). In both (b) and (c), 4M parameter BertTiny model is trained on the StackOverflow dataset for various noise multipliers.
The analysis above reveals what the optimal number bands is for different settings, but not whether it is feasible run the mechanism for that many bands. In Figure 3a plot the wall clock time to generate correlated noise as a function of the number of bands in a typical distributed training scenario with 100M parameter BertBas model trained on 32 accelerators. Our primary finding for this experiment is:
Using our distributed algorithm, correlated noise generation is not the primary bottleneck, even when the number of bands is fairly large (up to b 128, corresponding to 1.6 GB overhead per accelerator). The cost of per-example gradient clipping is one- to three- orders magnitude more expensive, depending on the batch size.
4.3 RMSE VS. LEARNING PERFORMANCE
Thus far we have primarily focused on RMSE on the prefix workload, but this is just a proxy for what really about: training-time learning performance. In Figure 3(b-c) we aim understand the relationship between RMSE and learning performance across range of DP-MF strategies. Our goal compare different mechanisms across a different privacy budgets, as this has been done in prior work (Choquette- et al., 2024; 2023a; Denisov et al., 2022), and our mechanism is just more scalable instantiation of the prior work.
We consider strategies with differing numbers of bands, and for each setting we optimize the strategy for the prefix workload. Note this different from early work on matrix factorization where the strategy is optimized for workload that encodes the optimizer parameters like momentum and learning rate cooldown (Denisov al., 2022). Recent work on DP-BANDMF suggest is fine to configure the strategy for the prefix workload even when using SGD with momentum in practice (Choquette- Choo et al., 2024, Section I).
For each strategy under consideration, we train BertTiny model with per-example clipping and correlated noise addition with range of noise multiplies spanning 3 orders of magnitude. We tune the learning rate for each setting and report results for the best value found. We each experiment, record the RMSE the strategy / noise multiplier along with the evaluation set cross entropy, and plot the results in Figures 3b and 3c. Our main findings from this experiment are:
For adaptive optimizer and the same RMSE, strategies with fewer bands provide better learning performance, indicating that RMSE is not the best proxy for learning performance across multiple strategies. These results suggest that should set bands more conservatively than suggested by RMSE alone to optimize learning performance if using DP-B -P-BANDMF with an adaptive optimizer.
For a non-adaptive optimizer, the lines for 1-, 8-, 64-, and 112-banded strategies all line up, indicating that RMSE is reasonable predictor of learning performance. However, there is still gap between DP- BANDMF and BLT-DP-ME (5000 bands), where fewer bands achieves better learning performance for the same RMSE.

---

Published as a conference paper at ICLR 2025
While this experiment focused RMSE, also tested the effectiveness of max proxy for learning performance in Figure 9 in App. F, with similar observations holding there as well.
RELATED WORK
More DP-MF Variants Koloskova et al. (2024); Choquette- Choo et al. (2023a) revisit the objec- tive underlying DP-MF and propose new variants based on their analysis. Like us, Henzinger et al. (2023) and Choquette-Choo et al. (2023a) use Toeplitz strategies, and bypass the O(n") runtime of strategy optimization. However, they consider "full" Toeplitz matrices and do not address the ((n.d) training-time memory overhead of the algorithm, preventing scalability in large-scale settings.
Scalable Approaches to the Matrix Mechanism The optimization problem we studied in this work dates back to the Matrix Mechanism (Li et al., 2010), and has been the subject of intense research for a different problem domain: answering workloads of linear counting queries over discrete databases (Li al., 2010; 2015; Yuan et al., 2016; McKenna al., 2018; 2023; Xiao et al., 2024; Nikolov et al., 2013; Edmonds et al., 2020; McKenna et al., 2020; Li & Miklau, 2013; Xiao al., 2024). McKenna al. (2023) and Xiao et al. (2024) restrict attention to special classes of strategies that enable efficient strategy optimization. By exploiting the special structure in these strategies, they scale well beyond n 10", but the specific strategies considered in those works do not directly apply in the context of iteratively training ML models.
Concurrently with our work. McMahan et (2024a) proposed BLT-DP-ME memory-efficien approximation of single-epoch DENSE-DP-MEF and extended to handle multiple epochs in follow-up work (McMahan et al., 2024b). Their method scales to an arbitrary number of training iterations, and reduces the training-time time memory complexity to Occ d) for small and configurable 3, while only sacrificing 5-7.5% in RMSE compared to Unamplified 1P-BANDMF.
LIMITATIONS
Here we discuss several limitations of this paper. First, the number of bands needed to maximize utility may differ from the number of bands that feasible to use under compute constraints. In Section 4.2 we provided an argument that in the regimes of most practical interest, the number of bands will be small. However, is conceivable for there to be situations when the optimal number of bands is larger than what can be supported under compute constraints.
Second DP-B MF-BANDMF relies on Poisson sampling to form minibatches, which can be tricky to integrate into modern ML infrastructure due variable batch sizes.
Third, this work and nearly all work on DP Matrix Factorization relies on the assumption that expected error on the prefix sums of gradients is good proxy for learning performance (Kairouz et al., 2022002bb. lb; Denisov et al., 2022; Choquette-Choo et al., 2023a; McMahan et al., 2024a; Kalinin & Lampert, 2024). As demonstrated in Section 4.3, this proxy not perfect, particularly when combined with adaptive optimizers. More research is needed to improve the objective function underlying DP-MF- ---lle mechanisms, and how to configure them with adaptive optimizers.
Finally, our distributed noise generation procedure relies on the assumption that the worker machines responsible for computing each shard of the noise are not compromised, otherwise the privacy guarantees could be at risk. In situations where noise must be generated on single machine, DP- BANDMF may not be able to scale to as many bands. However, as we showed throughout Section 4, DP-BANDMF tends to work best with small number of bands anyway.
7 CONCLUSION
This work motivated by the desire to train large-scale ML models with differential privacy. Our work is best characterized by its simplicity, scalability, and state-of-the-art performance. Our key ideas are straightforward to understand and implement. Our algorithms for strategy optimization scale effectively well beyond > 10", and our algorithm for distributed noise generation can handle large models with little overhead. Finally, our mechanism offers better expected error than any other -t-lle mechanism across wide variety of settings.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differen- tially private bert. In Findings of the Association for Computational Linguistics: EMNLP 2022, pp.
1491, 2022.
James Bradbury, Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http://
http://githuse gttphbb.ttttutt/gco com/ google/ jax.
Christopher A Choquette-Chon Chho,, Krishnamurthy Dj Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Correlated noise provably beats independent noise for differentially private learning. In The Twelfth International Conference Learning Representations, 2023a.
Christopher A Choquette- Choo, Hugh Brendan Mcmahan, J Keith Rush, and Abhradeep Guha Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Interna- fional Conference on Machine Learning, pp. 5924-5963. PMLR, 2023b.
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 Neural Information Processing Systems, 36, 2024.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint 1XXx:2204.13650. 2022.
Carson Denison, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash V Varadarajan, and Chiyuan Zhang. Private ad modeling with dp-sgd. arXiv preprint ar arXiv:2211.11800 2022.
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.
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings on Privacy Enhancing Technologies, 2022.
Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Cynthia Dwork. Differential privacy:
A survey of results. In International conference on theory and applications of models of computation, pp. 1-19. Springer, 2008
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mecha- nisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pp. 438. 2020.
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. pp. 10072-10092, 2023.
Monika Henzinger, Jalaj Upadhyay. and Sarvagya Upadhyay. Almost tight error bounds differen- tially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Al Algorithms (SODA), pp. 5003-5039. SIAM, 2023.
11

---

Published as a conference paper at ICLR 2025
Edward J Hu, Phillip Wallis, Zeyuan Alien-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2021.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference Machine Learning, pp. 5201-5212. PMLR, 2021a.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference Machine Learning, pp- 5213-5225. PMLR, 2021b.
Nikita Kalinin and Christoph Lampert. Banded square root matrix factorization for differentially private model training. arXiv preprint arXiv:2405. 13763, 2024.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001 008611, 2020.
Anastasiaa Koloskova, Ryan McKenna, Zachary Charles, John Rush, and H Brendan McMahan. Gradient descent with linearly correlated noise: Theory and applications to differential privacy, Advances in Neural Information Processing Systems, 36, 2024.
David C Lay. Linear algebra and its applications. Pearson Education India, 2003.
Chao Li and Gerome Miklau. Optimal error of query sets under the differentially privatt matrix mechanism. In Proceedings of the 16th International Conference on Database Theory, pp. 272-283, 2013.
Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the twenty-ninth ACM SIGMOD- SIGACT-SIGART symposium on Principles of database systems, pp. 123-134, 2010.
Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal, 24: 757-781, 2015.
Fu-Rong Lin. An explicit formula for the inverse of band triangular toeplitz matrix. Linear algebra and its applications, 428(2-3):520-553) 2008
Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajihala. Optimizing error of high-dimensional statistical queries under differential privacy. Proceedings of the VLDB Endowment, 11(10), 2018.
Ryan McKenna, Raj Kumar Maity, Arya Mazumdar, and Gerome Miklau. A workload-adaptive mechanism for linear queries under local differential privacy. Proceedings of the VLDB Endowment, 13(11), 2020.
Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavaijalla Optimizing error of high-dimensional statistical queries under differential privacy. Journal of Privucy and Confiden- fiality, 13()), 2023.
Brendan McMahan, Krishna Pillutla, Thomas Steinke, Abhradeep Thakurta, et al. Efficient and near-optimal noise generation for streaming differential privacy. arXiv preprint arXiv:2404.16706, 2024a.
H Brendan McMahan, Zheng Xu, and Yanxiang Zhang. A hassle-free algorithm for private learning in practice: Don't 't use tree aggregation, use blts. arXiv preprint arXiv:2408. 088868 2024b.
Aleksandar Nikolov, Kunal Talwar. and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 351-360. 2013.
12

---

Published as a conference paper at ICLR 2025
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. Journal of Artificial Intelligence Research, 1111113-1200 2023.
David Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Cryptology ePrint Archive, 2018.
Yingtai Xiao, Guanlin He, Danfeng Zhang, and Daniel Kifer. An optimal and scalable matrix mechanism for noisy marginals under convex loss functions. Advances in Neural Information Processing Systems, 36, 2024.
Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher Choquette-Chre Peter Kairouz, Bren- dan McMahan, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of gboard language models with differential privacy. arXiv preprint arXiv:230S. 18465, 2023.
Yifan Yao. Jinhao Duan. Kaidi Xu, Yuanfang Cai, Zhibo Sun, and Yue Zhang. A survey on large language model (IIm) security and privacy: The good, the bad, and the ugly. High-Confidence Computing, pp. 100211, 2024.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. International Conference on Learning Representations, 2021.
Ganzhao Yuan, Yin Yang, Zhenjie Zhang, and Zhifeng Hao. Convex optimization for linear query processing under approximate differential privacy. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 2005-200 2016.
Dan Zhang, Ryan McKenna, Ios Kotsogiannis, Michael Hay, Ashwin Machanavaijhala, and Gerome Miklau. Ektelo: A framework for defining differentially-privee computations. In Proceedings of the 2018 International Conference on Management of Data, pp. 115-130, 2018.
A NOTATION
Symbol
Domain
Meaning
Na
number of training iterations model dimensionality
d
N.
k
N.
number of epochs
q
(0, 1]
minibatch sampling probability number of bands
b
N.
R.
noise multiplier
A
R n=x
lower triangular ones matrix
Z
Rasd
Gaussian noise, Z:j (0, o²)
C
R
DP- OP-BANDMF strategy matrix Parameterized strategy matrix tth indicator vector
C(O)
Rax
R"
1.11,22
R.
maximum Lo column norm
asGD(c.ó.g.n)
R.
DP-SGD noise multiplier
Table 1: Table of Notation
B EXAMPLES
B. OPTIMAL 3-BANDED STRATEGY
Example B.1 (DP-BANDMF). The matrix below the optimal 3-banded strategy matrix C config- ured for 9 training iterations. (Informal ?) OP-BANDMF with minibatch sampling probability of
TDP-BANDMP requires special sampling different from the usual Poisson sampling of DP-SGD to achieve this guarantee, see Choquette-Choo al. (2024) for the details.
13

---

Published as a conference paper at ICLR 2025
q 1/s enjoys the same privacy guarantees as 3 iterations of DP-SGD with sampling probability 3q. The vectors Yy are added to the minibatch gradients during training, and can be computed efficiently in online fashion with O d) space using Algorithm 1, exemplified below:
00.740
0
0
0
Z2
Y1
0.500
0.822
0
0
0
0
0
Z2
Y2
0.450
0.492
0.876
0
0
0
Z3
Y3
0.286
0.395
0.821
0
0
0
0
Y4
0.278
0.462
0.855
25
Y5
0
0.335
0.442
0.882
0
0
Y6
0
0
0.272
0.403
0,892
0
Z7
Y7
0
0
0.243 0
0,409
0.936
0
Y8
0
0
0
0.194
0.353
1.000]
Zg
Yg.
Y1 #1/0.740
Y1
Y2 (R.-0.300y 0/o..22
Y3 = (4x-00.922--004500y
Y9 (2a (G.-0.553y-001994--))
C COMPUTING THE GRADIENT OF THE EXPECTED ERROR
We implemented functiins to compute the expected error of banded strategies (Algorithm 5) and banded Toeplitz strategies (Proposition 3.1) pure JAX. This allowed transformation to give function to compute its gradients, so we didn't 't have to manually derive them. In this section, we discuss the time and memory complexity of these gradient calculations.
use the jax. grad
For both banded strategies and banded Toeplitz strategies, computing the gradient of the objective function requires back- prokppppoaaaninn through Algorithm 1. In the banded case, this algorithm invoked with sequence of size vectors, while in the banded Toeplitz case, it is invoked with sequence of scalars. To compute the objective function, the intermediate values y; can be discarded on step i However, compute the gradient, by default jax. grad requires keeping around all values of in memory at once.
Banded Strategies Both the time and memory complexity of computing the gradient with this default implementation is Onnbb) in the banded case. By using the jax. checkpoint transformation, we trade-off memory for time during the backward pass by only storing some subset of intermediates. Specifically, given a parameter that roughly corresponds to the number of intermediates to keep around for the backwards, can compute the gradient using O(nbb)) time and ((nb//k) memory by re-materializing the inputs we need when we need them. We choose k so that the total memory consumed is less than equal 4GB.
Banded Toeplitz Strategies The time and memory complexity of computing the gradient with the default implementation Obbn) and O(n) respectively. We believe the memory complexity of he loss function could be reduced to (bb) with more careful implementation though. However, O(n) memory already small enough scale up all values of n we care about in practice, and no special tricks are needed to improve the memory footprint.
C.I TIMING EXPERIMENTS
Figure Figure 4 shows the wallclock time required to evaluate the loss function and it's gradient on both CPUs and GPUs, for various n at fixed 6 16. We evaluate the wall clock time for increasing n until the total time to compute both the loss and grad exceeds 60 seconds. Our findings from this experiment are:
We can compute both the loss and gradient of general banded strategies up to about n æ 10 under reasonable time limits when utilizing GPUs. As gets larger, the relative gap between the time to compute the loss and gradient grows, as expected due to our checkpointing strategy described above.
14

---

Published as a conference paper at ICLR 2025
CPU
50
Grad on CPU GPU
Time Per Ittrraion (
60
Grad on CPU
GPU
Grad on GPU
Grad GPU
Por
10
10
10
10
10
12
10
10
T3
(a) Banded Timing
(b) Toeplitz Timing
Figure Wallclock time required evaluate the total squared error objective function and it's gradient as function of n for b= 16. Does not include JIT-compile time, which is amortized over strategy optimization.
Algorithm Streaming Linear Operator for Prefix
Input: stream of vectors 21..... 2n Rd, where Z is the matrix with rows z, Output: Y AZ, one row at a time. for i 1, 1,...,... do
Y: y;-1 + Zi
yield y;
Figure 5: Algorithm for streaming matrix multiplication by a Prefix matrix. To simplify the presentation, we use the convention that out-of-bounds indexing into matrix or vector returns
We compute both the loss and gradient of banded Toeplitz strategies beyond 107 under reasonable time limits. These computations do not benefit from GPUs, and in fact an order of magnitude faster on CPUs. This is due the inherent sequential nature of Algorithm which is not type of computation that benefits from GPUs.
D GENERALIZATIONS TO OTHER STRATEGY AND WORKLOAD CLASSES
Our presentation in Section 3.1 focused on the Prefix workload and the class of (column-normalize) banded matrices and Toeplitz matrices. However, our core approach also applies to a broader set of strategies in workloads, as show in this section.
D.1 STREAMING LINEAR OPERATORS
We begin by providing a definition for a Streaming Linear Operator:
Definition D.1 (Streaming Linear Operator (SLO)). A Streaming Linear Operator is function that consumes a sequence of vectors Z 2i...., Zn as input one at a time, and produces a sequence of vectors time such that y; is linear function of 21.... 2,. We say SLO is b-buffered if only requires storing state of size at most b vectors.
Y1,-.-yYa yn
We note that there is one-to-one correspondence between SLOs and lower triangular matrices. The Prefix matrix can be represented as a 1-buffer SLO, shown in Figure 5. Banded lower triangular matrices and their inverses be represented b-buffer SLOs, as shown in Algorithm I. The heavyball momentum learning rate cooldown workload studied in prior work Denison al. (2022); Choquette-Choo et al. (2023b) can also be represented 2-buffer SL.O.
15

---

Published as a conference paper at ICLR 2025
Algorithm 5 Efficiently Evaluating the Per Query Error
Input: SLO for C(@)-1
(10)-1 SLO for Output: by b,, one entry at a time, where B AC(@)-
bo
for i = 1....,,. do
y: -SO00- (c:)
b; (y:)
yield b;
D.2 EFFICIENTLY OPTIMIZING PARAMETERIZED STRATEGIES VIA SLOS
Recall that computing the objective function efficiently is the core requirement for performing efficient strategy optimization over the space of strategies. As long as we can express this function in terms of Jax primitives, we can rely on auto-differentiation tools to compute the gradients and perform the optimization. Hence, our focus this section is on generalizing Algorithm 3 to handle any workload represented SLO, and any parameterized strategy whose inverse is SLO, and any differentiable aggregator of the per-query expected squared errors.
Algorithm is algorithm calculate the per-query expected error of any workload and parame- terized strategy represented as a pair of SLOs. The time and memory complexity of this algorithm depends only on the complexity of the underlying SLO implementations. In general, for a b1- buffer SLO for C-1 and bu-buffer SLO for A, the time and memory complexity of Algorithm is O(n" (b2 b2)) and (n((b, + b2)) respectively. We note that the per-query-error can be combined with any ssub)-differentabbe In this paper, our focus was on expected total squared error, which is simply a sum of the per-query squared errors. However, the max expected error is another natural choice that has been sometimes used prior work MeMahan et (2024a); Fichtenberger al. (2023). The "best" loss function to use, i... the one that best correlates with learning performance, is still an open question.
aggregator to get scalar-valuee valued loss function that can be optimized.
D.3 EFFICIENTLY OPTIMIZING BANDED TOEPLITZ STRATEGIES FOR TOEPLITZ WORKLOADS
In this section, we show that we can efficiently calculate the expected per-query squared error for banded Toeplitz strategy any Toeplitz workload with minor modification to Proposition 3.1. These generalizations do not affect the time or memory complexity of the algorithm.
Proposition D.1 (Banded Toeplitz Expected Per-Query Squared Error). Let X,0 E R be Toeplitz coefficients for A and C respectively. The expected square error (excluding sensitivity) the ith query can be evaluated Σ)=1 w² where -
E THEORETICAL GUARANTEES
In this section we provide theoretical guarantees on the expected error of our mechanism. To do so, it useful to state the theoretical guarantees of the BANDED SQRT mechanism. We restate their main theoretical guarantee below, specialized to the Prefix workload:
Proposition E.1 (Thm 6 Kalinin & Lampert (2024)). Let A denote the Prefxx workload let C(0) denote the strategy matrix for the Banded Square Root factorizaziiinn with b bands. Then
o(1
n
log
We will now argue that our Banded Toeplitz strategy inherits the theoretical guarantees of the BANDED SQRT strategy.
Proposition E.2. Let C(O,) denote the strategy for BANDED SORT and note that it is a banded Toeplitz matrix. Now let C(O.) denote the banded Toeplitz, matrix numerically optimized for the
16

---

Published as a conference paper at ICLR 2025
objective function specified in Proposition 3.1, using Bg the initialization. Then the expected error of C(+.) is never worse than the expected error of C(0)), that is:
[CC(0.) |
Proof. First note that the objective we optimize is identical to the one shown in the proposition above, and note that it is product of two continuous and differentiable functions of 0, and is therefore also continuous and differentiable. For simplicity, assume we optimize this objective with gradient descent. In each iteration, we compute the gradient which points in the direction of steepest descent. With sufficiently small step sizes, the sequence of iterates are guaranteed to non non-inceasing. Thus, the objective function of the final iterate is less than or equal to the objective function at the initial point.
Combining Proposition E.1 with Proposition E.2 shows that banded Toeplitz strategy inherits the theoretical guarantees of the BANDED SQRT mechanism Kalinin & Lampert (2024), For simplicity, presented these propositions for the Prefix workload, but Proposition E.1 can be generalized to handle any momentum-comm cooldownn workload Kalinin & Lampert (2024), and Proposition E.2 applies for any workload.
F ADDITIONAL EXPERIMENTS
F.1 AMPLIFICATION VS NOISE CORRELATION
In Figure we measure the benefit of privacy amplification and noise correlation respectively, by comparing the RMSE of Amplified DP-BANDMF with Unamplified DP-BANDMF and DP-SGD. Our main findings from this experiment are:
1. Amplification most beneficial when both e and epochs are small. However, even up to 8, there is meaningful improvement in RMSE of & 15%. Figure 6b shows that correlated noise is most beneficial when is large and epochs is small, and lines up very nicely with Figure 2b. In the most extreme setting, the RMSE of OP-BANDMF can be 9x lower than DP-SGD, With larger epochs or smaller e, the benefit of correlated noise decreases, confirming it most useful compute-constrained settings.
2. When the number of epochs is large (but still well less than n),, Amplified DP-SGD and Unamplified DP-B IP-BANDMF both achieve similar RMSE (as indicated by the dark blue region), despite being very different mechanisms. Moreover, the RMSE these settings nearly matches the RMSE attained by full-batch DP-SGD, even with many fewer epochs (512 instead of 16384).
F.2 COMPARISONS TO BASELINES
In Figure 1b of the main text, we compared our scalable amplified DP-BANDMF approach with other strategies as function of e. In this section, we compare against the same baselines, but vary the number of training iterations n and the number of epochs k.
In Figure 7a, we see that the OP-BANDME improves relative to baselines as n increases. At n 105 our mechanism enjoys 25% smaller RMSE than the next best competitor. In Figure 7b we see that DP-BANDMF enjoys the greatest relative improvement over competitors for small k, although the relationship not monotonic.
F.3 BANDS VS. EPOCHS VS. RMSE
In this section, we revisit Figure 2a but increase e from to Figure 8 shows how the number of bands effects the RMSE under different number numbers of epochs. With larger more epochs are needed for SGG to get near full-batch performance (in this case, 256 epochs). The optimal number of bands also tends to be somewhat higher in this regime, with 1 128 bands being optimal for
17

---

Published as a conference paper at ICLR 2025
9.00
0.0625
5.00
0.125
3.00
0.25
2.00
0.5
1..5
1.0
1.25
2.0
1.12
4.0
1.06
8.0
1.03
16.0
2
4
8
16
32
64
128
256
512
1024
1
2
4
8
16
32-
64
128-
256
512
1024
Epochs
Epochs
Amplification Benefit
(b) Correlation Benefit
Figure 6: (a) Ratio of RMSE between Unamplified DP-BANDMF (b = */44 and DP- DP-BANDME; which
measures the benefit of amplification in different settings. (b) Ratio of RMSE between Amplified DP-SGD (b 1) and DP- BP-BANDMF, which measures the benefit of correlated noise in different settings. Both plots show results for 16384.
Suboptimalty Rotto
3:30
Tree Aggrepation
DP-SED
Subopttmalltt Rotto
Tree Aggregation
DP AP-SED
Stunsing
Stamsing
FHU
FHU
1.20
Buffeee Tospiitz Dence MF Amolffd BandMF
1:20
Buffeoed Tosp
Denze MF
Amelfiidd BandMF
1:20
3100
2101
Itertiions
Epochs
(a) k 8
(b) 8192,
Figure 7: RMSE Suboptimality ratio of different strategies as a function (left) and & (right) for =.4. 4.
the 8 epoch setting. DP-BANDMF needs 16 epochs to get within a factor of the RMES of full-batch DP-SGD.
F.4 MAX ERROR vs. LEARNING PERFORMANCE
G QUALATATIVE COMPARISON TO PRIOR AND CONCURRENT WORK
There are three primary axes we can evaluate prior matrix factorization approaches on: (1) efficiency of strategy selection, (2) training-time overhead, and (3) utility. Table
The factorizations that are most efficient to calculate avoid numerical optimization Abadi et al. (2016); Kairouz al. (2021b); Kalinin Lampert (2024); Fichtenberger al. (2023), but do so the cost of utility. The factorizations that are most expensive to compute represent the noise correlation strategy using dense matrices, and are generally inefficient large n Denisov al. (2022); Choquette-Cie Choo et al. (2023b; 2024). Our proposed approach, well concurrent approach McMahan et al. (2024a;b) get the best of both worlds, by numerically optimizing over parameterized classes of strategies that avoid dense representations.
Different factorizations have different properties that can exploited for runtime efficiency. DP- SGD is the most efficient method, since it adds independent rather than correlated noise. The most general matrix factorizations require time linear to generate noise for single iteration, which be prohibitively expensive for large (even with distributed noise generation). Indeed, these
18

---

Published as a conference paper at ICLR 2025
2
Epochs (k)
1.8
04
BB
A16
32
64
128
256
* 163844
1.6
1.4
RMSE
1.2
1
0.8
0.6
10
10 Bands (b)
10a
Figure 8: RMSE of DP-BANDMF as function of for various epochs, with fixed (c, = (8,10 10 and n 16384. With b = DP-BANDMF equivalent to DP-SGD, and only benefits from amplication (not correlated noise). With b E. DP-BANDMF only benefits from correlated noise (not amplification) and closely resembles DENSE- BENSE-DD-MM DP-MF. The best RMSE is obtained somewhere in the middle, with the both the best RMSE and corresponding value of b decreasing with epochs. By using DP- PP-BANDMF instead DP-SGD, one can run for far fewer epochs without sacrificing nearly much utility.
3.95
DP-BandMF(b=11
DP-BandM((b=1)
DP-BandMF(b-8)
DP-BandMF(b-B)
Entropy
3.9-
DP-BandMF(b-64)
Cross Entropy
DP-BnnMMFbb6G6
2.08
DP (b-Bn)
6
DPBLT-MF
3.8
375
377
5-
10"
10
10
10 Max Error
10a
Max Error
Adaptive Optimizer
(b) Non-Adaptive Optimizer
Figure 9: Max Per-Quee Qurry Error vs. Learning Performance (evaluation cross entropy) with an adaptive optimizer (a) and non-adaptive optimizer (b). both (a) and (b), 4M parameter BertTiny model is trained on the StackOverflow dataset for various noise multipliers.
prior works focused on settings where n 5 2052 Denisov et al. (2022); Choquette-Chie Choo et al. (2023b). Our method bypasses this limitation via Algorithm 1, and enjoys only bx overhead.
Finally, different factorizations enjoy different utility. We say factorization optimal in at least one setting of (n 2 & n, 16) if it achieves the lowest RMSE among all methods that scale to that setting. While this characterization doesn't quantify how close to optimal different methods are, it clearly demonstrates the advantages of OP-BANDMF relative to other scalable approaches.
19

---

Published as a conference paper at ICLR 2025
Efficient Strategy Selection
Sub-linear Training Overhead
Optimal in at least one setting
Factorization
Identity (DP-SGD)
TREE AGGREGATION Kairouz et al. (2021b)
FHU Fichtenberger et al. (2023)
x
LTI Choquette-Chor et al. (2023a)
STAMPING Denisov et al. (2022)
X
x
MULTI-EPOCH MF Choquette-Choo et al. (2023b)
BLT-DP-M MMF McMahan et al. (2024a)
X
BANDED SQRT Kalinin & Lampert (2024)
X
DP-BANDMF [Ours]
Table 2: Summary of existing matrix factorizations and their performance characteristics.
H IMPROVING FRAGILITY TO MIN SEPARATION FOR FEDERATED TRAINING SCENARIOS
The primary focus of this paper has been on centralized training regimes, where DP-BANDMF benefits from privacy amplification by sampling. As observed in prior work (Choquette- Choo et al., 2024; McMahan al., 2024b) and in Figure l Unamplified OP-BANDMF still a sfate-of-the-ae mechanism in federated training regimes. There, (k, b) (k,b))-in-ssepe min-separattin participation pattern is used where each user contributes at most & times during training, and each contribution separated by at least b iterations. In centralized scenarios we know what these parameters are in advance based on properties the dataset and training setup. In federated scenarios, it is more difficult to control, and therefore the strategy is typically optimized based estimates of these quantities, while the privacy budget consumed during training is computed post-hoc (Xu et al., 2023). If the min separation is correctly estimated, DP-BANDMF is the best known mechanism currently available. However, if the true min separation differs from the one the strategy was optimized for significantly (e.g.. more than factor of 2x), BLT-DP-MF outperform DP-BANDMF.
Fundamentally, this phenomenon due to the fact that the Teeplitz coefficients in the BLT strategies decay more quickly than the ones in banded Toeplitz strategies. A simple heuristic can improve the robustness of banded Toeplitz strategies to miscalibration of min-sepaaattin, at the cost of increased expected error when the min-separation correctly calibrated.
Let by and denote the lower and upper bound on min separation we want to tailor the mechanism for.
Optimize 0 12 for expected error as in Proposition 3.1.
b- 0, for all by- Set 0; = b-bu
We take the setting considered McMahan et al. (2024b), where n 2000, 5, and min-sep is between by = 200 and = 400. In Figure 10a we plot the Toeplitz coefficients of three strategies: BLT, BandToop optimized for 400, and BandToep + Heuristic described above. In Figure 10b we plot the RMSE of each strategy as a function of the minimum separation. With our heuristic, we achieve lower RMSE than BLT strategies across all min separations considered, but sacrifice some RMSE over the baseline banded Toeplitz strategy when the minimum separation is very close to 400. Note the relative differences between all three mechanisms are pretty small in this setting. Finally, we will note that the heuristic can likely be replaced with something more principled, by e.g., optimizing for the expected error averaged over different min-separations. We leave this exploration for future work.
I SCALING BEYOND 107
Beyond 10", numerically optimizing banded Toeplitz strategies becomes expensive using the techniques we described in the main body. With a small observation, we can derive an approximate loss function whose time complexity is significantly reduced. Recall from Proposition 3.1 that to
20

---

Published as a conference paper at ICLR 2025
109
9.2
BLT
BLT
Toep
Tbeplitz Coefficlent
BandToep
BandToep + Heuristic
Band Heuristic
8.8
20
RMSE
8.6
10-2
8.0
10-4
100
200
300
400
500
200
225
250
2.75
350
375
400
Index
Min Separation
(a) Toeplitz Coefficients
(b) Min Sep Fragility
Figure 10: Comparison between Buffered Toeplitz strategies and Banded Toeplitz strategies when the min-separation is not known in advance (i.e., federated training scenarios).
compute the expected error of Toeplitz strategy we need to compute C(0) (if we are optimizing for the Prefix workload), Note that y; defined by simple linear recurrence of order shown in Algorithm 1. Rewriting that recurrence here, we have:
y/ = (1 Σ 9+)l- j-2
Now consider the setting where >> b. Now suppose for moment the sequence y/ converges to some fixed point x. that is lim V/ x. We can solve for this fixed point by substituting y; yt-j+1 æ, and solving for x. Doing so, we obtain:
1
I =
Σラ=1 0
It is natural to question whether the sequence converges. Since divergence would generally imply high expected error, we believe any reasonable iterative optimization procedure should produce well-behaved strategy parameters O. To compute approximate expected error, we can simply compute y, exactly up to some fixed index m, and then approximate y: Σ, 05 idea, we can easily approximate the expected mean squared error as:
for > m. Using this
Σ
1
Σ, 0g
i-
We evaluate this expression in 0(m) time using the closed form expression for Σ Ei i. We can similarly easily approximate the expected max squared error as:
m Σ 1=
Σ
(n m
Σg 0,
Empirically, the sequence converges quite quickly and recommend setting 62 (assuming n > b²), which gives an overall time complexity of O(b²) for evaluating the loss function. As concrete data point, optimizing the expected max squared error for 2 and b = 64 using b. m = 6² yields suboptimality ratios are 1.032 and 1.0 respectively. That is, setting m = b² gives no loss in solution quality.
21

---

Published as a conference paper at ICLR 2025
1.25
Training Iterations (n)
2
1.12
32
1.06
512
1.03
1.02
8192
1.01
2
32
512
Bands (b)
Figure 11: RMSE Suboptimaltiy Ratio of the optimal parameterized banded Toeplitz strategy of the form 02 1/1+ c, and the optimal unconstrained banded Toeplitz strategy, for various choices of n and b.
J NEAR-OPTIMAL BANDED TOEPLITZ STRATEGIES WITHOUT GRADIENTS
Through inspection of the optimal Toeplitz coefficients Figure 10a, one can attempt to a functional form the parameters. The expression 1/4 provides an excellent fit for the optimal banded Toeplitz coefficients when c is chosen appropriately. To find the best value of given the n and b, one can do simple sweep over range possible values, picking the best one. This avoids the need to compute gradients, and the evaluation of the loss function at different values of can be easily vectorized parallelized. This provides an excellent approximation of the optimal Toeplitz coefficients, particularly when n >> b, as demonstrated in Figure 11.
While we do not work out the details here, we believe that it may be possible to identify an efficient single-shot algorithm to find the optimal value of by deriving and analyzing the gradient, and identifying where it
K OPTIMIZING COLUMN-NORMALIZS BANDED TOEPLITZ STRATEGIES
In Section 3.2, we discuss the importance column normalization, and propose a simple heuristic of normalizing the columns of the optimized banded Toeplitz matrix. This heuristic improves the expected eиror over the corresponding un- nn-nommalized strategy, but is not in general optimal among the class of all -oommllnor banded Toeplitz strategies, (since for column normalization). In this section, we describe two approaches to optimize over the space of column normalized banded Toeplitz strategies. In general, galumi-normalized Toeplitz strategies, but we would have to forfeit the efficiency advantages that come along with the Toeplitz structure, and instead use the techniques banded matrices in Section 3.1. Alternatively, we can use the gradient-free approach described in App. which can be helpful because the gradient computation is the primary bottleneck for general banded optimization explained in App. C. However, the latter approach would only give an approximate minimum (although in practice the sub-optimality likely too small to matter).
optimized without accounting
optimize
the space of
described for general
22


Reviews:
[{"review_id": "4GuzVlAJS3", "reviewer": "Reviewer_HJgB", "summary": "The paper studies a mechanism (DP-BandMF) for private machine learning that has advantages over the standard private mechanism (DP-SGD) in some regimes due to its use of optimized correlated noise. The algorithm is characterized by a strategy matrix that determines the correlational structure of the noise.\n\nThis work identifies the optimization of the stategy matrix is a computational bottleneck limiting the applicability of DP-BandMF. Prior work gives an $O(n^3)$ time and $O(n^2)$ space algorithm, which is impractical for large values of $n$. This work improves the running time to $O(bn^2)$ and the space to $O(bn)$ where the band size $b$ characterizes the level of correlation allowed between noise vectors. The authors go on to give a further improved $O(bn)$ time $O(n)$ space algorithm for a restricted class of strategies.\n\nThe authors conclude with a series of experiments that assess the scalability and solution quality of their algorithm, the optimal band-size, as well as the suitability of the RMSE measure optimized by their algorithm as a proxy for utility loss.", "questions": "- Could context be provided for how a \"strategy\" should be interpreted? Around l85 in the background.\n- The \"workload\" $A$ is introduced around l150 but the context is also unclear to me here. What is the role of this object and why is it natural to view as a lower triangular matrix of ones?\n- Could the authors provide a definition of Toeplitz strategies? One was not provided.\n- Lastly, is there a typo on l85? $i \\leq j + b$ looks the wrong-way-around to me.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper investigates practical scalability issues of a useful DP-ML algorithm and makes substantial performance improvements that increase the range of high-dimensional learning tasks that may be solved by DP-BandML.\n\nThe purpose and conclusions of the experiments are well-explained.\n\nOverall, the paper is very clearly written and pleasant to read.", "weaknesses": "A small point not addressed in this work is efficient computation of the gradient of the RMSE objective. The authors defer to the Jax implementation. It is unclear whether there is an inherent limitation of this approach or if there is room for meaningful improvement in gradient computation efficiency.\n\nA more significant weakness of this work is somewhat limited technical novelty in the results. The primary technical contribution appears to be Algorithm 3, which leverages sparsity and computes the objective in a streaming fashion.\n\nThe authors do extend their results in Proposition 3.1 to a new setting involving Toeplitz strategies. This result is nice but I found the following motivation not fully convincing: \"This design decision was inspired by manual inspection of the optimal dense strategies, observing that they exhibit a near-Toeplitz structure.\" While this choice seems bolstered by by the result in Figure 1(a), a more careful theoretical justification would be welcome, if possible.", "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": "iKf8fnJfKL", "reviewer": "Reviewer_rykK", "summary": "The paper presents a improvement to the DP-BANDMF, a differentially private mechanism that adds correlated noise to DP-SGD, aiming to address its scalability limitations. Existing approach DP-BANDMF has struggled with computational and memory demands, especially in large-scale models. The authors introduce two methods  to optimize this mechanism for scenarios involving over 10^6 training iterations and up to 10^9 model parameters, making it feasible for use with modern, large-scale models. The empirical results demonstrate significant performance gains over existing mechanisms.", "questions": "1. Is there any insight on why adaptive estimator works worse than adaptive optimizer?\n\n2. In practice, how do we manage the privacy budget for selecting number of bands?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well written and clearly addresses the contributions.\n2. The empirical study is thorough with limitations sufficiently addressed.", "weaknesses": "The only concern here is that this paper does not discuss too much privacy utility trade-off, which is not the focus of this paper.", "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": "15bVVf40yf", "reviewer": "Reviewer_YuCq", "summary": "This paper proposes a differential privacy method that utilizes both random sampling and correlated noise via the use of b-banded strategy matrix. The number of bands b controls the proportion of privacy amplification from subsampling and correlated noise, which can be optimally selected with efficient computation cost using the banded Toeplitz strategy. Further distributed noise generation is used to save potential memory cost.", "questions": "I have no questions.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is well explained and motivated.\n2. Extensive theoretical and empirical analysis to support the proposed mechanism.\n3. The paper is well-written and easy to follow.", "weaknesses": "1. A discussion on the communication cost w.r.t the number of bands as a tradeoff in the distributed setting would be nice to have.", "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 (Spotlight)