Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD
Authors: Nikita Kalinin
Ryan McKenna
Jalaj Upadhyay
Christoph H. Lampert
Venue: ICLR 2026 Poster (2026)
Keywords: Matrix Factorization
Differential Privacy
Machine Learning
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Matrix factorization mechanisms for differentially private training have emerged as a promising approach to improve model utility under privacy constraints. In practical settings, models are typically trained over multiple epochs, requiring matrix factorizations that account for repeated participation. Existing theoretical upper and lower bounds on multi-epoch factorization error leave a significant gap. In this work, we introduce a new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix. This factorization enables us to derive an explicit and tight characterization of the multi-epoch error. We further prove that BISR achieves asymptotically optimal error by matching the upper and lower bounds. Empirically, BISR performs on par with the state of the art factorization methods, while being simpler to implement, computationally efficient, and easier to analyze.

Published as a conference paper at ICLR 2026
BACK TO SQUARE RooTs: AN OPTIMAL BOUND ON THE MATRIX FACTORIZATION ERROR FOR MULTI- EPOCH DIFFERENTIALLY PRIVATE SGD
Nikita P. Kalinin
Ryan McKenna
Institute of Science and Technology (ISTA)
Google Research mckennar@google... com
Klosterneuburg, Austria
nikita lwkiniessliiiniist....e
Jalaj Upadhyay
Christoph H. Lampert
Rutgers University
Institute of Science and Technology (ISTA)
New Jersey. USA jalaj. www.hhyyyyruuugrr..coo edu
Klosterneuburg, Austria ch1 ihitist.o .c.at
ABSTRACT
Matrix factorization mechanisms for differentially private training have emerged promising approach improve model utility under privacy constraints. In practical settings, models are typically trained over multiple epochs, requiring matrix factorizations that account for repeated participation. Existing theoretical upper and lower bounds on multi-epoch factorization error leave a significant gap. In this work, we introduce new explicit factorization method, Banded Inverse Square Root (BISR), which imposes a banded structure on the inverse correlation matrix. This factorization enables us to derive an explicit and tight characterization of the multi-epoch error. We further prove that BISR achieves asymptotically optimal error by matching the upper and lower bounds. Empirically, BISR performs on par with sfte-offthhearr factorization methods, while being simpler to implement, computationally efficient, and easier to analyze.
1
INTRODUCTION
Private machine learning has become increasingly important as the use of sensitive data in model training continues to grow. Ensuring privacy while maintaining model accuracy presents critical challenge, particularly in fields like healthcare, finance, and personal data analysis. Differential Privacy (DP) has emerged fundamental framework for formalizing privacy guarantees in machine learning. It provides mathematically rigorous way to limit the influence of any individual data point the model's output, thereby preserving privacy. One effective approach achieving DP in iterative training is through the use of structured noise mechanisms that balance privacy guarantees with model utility.
In this work, we focus on the Matrix Factorization Mechanism (see Section 2.1 for a formal descrip- tion) for ensuring DP. Matrix factorization has been extensively studied in recent years in the broader machine learning application (Kairouz et al., 2021 Denisov et al. [022] Fichtenberger et al. 2023
Henzinger et al.) 20233 Choquette- Choo al. [2023b] Andersson Pagh| 2023
Henzinger et al.
2024 Kalinin & Lampert 2024 Henzinger & Upadhyay 2025 Pillutla et al.
2025
Henzinger et al.
2025b). has also been investigated private optimization (Koloskova et al.
2023 Choquette-Choe
ct all 2024a), federated learning (Zhang et al. 20255 Bienstock al.) (2025). and in the context of adaptive optimizers (Kalinin et al.) 2025 Ganesh et al. 2025). In particular, memory-efficient matrix
factorization has attracted significant attention in recent years (McMahan et al. 2024 Dvijotham
et al] 2024 Andersson & Pagh] 20255 Henzinger et al.) (2025)).
The approach has also been adopted in practice; for example, Google has reported its use for training
production on-device language models in their 2024 blog post "Advances in private training for
production on-device language models" (Xu & Zhang
2024). The core idea of the MF mechanism

---

Published as a conference paper at ICLR 2026
is to inject correlated noise into the gradients during training. The correlations are determined by the inverse of a matrix E Rux", referred to as the strategy matrix. While C' serves as a factor in the matrix factorization that defines the mechanism and used in calculation of the privacy level, its inverse C-1 functions as the correlation matrix, specifying how the injected noise is correlated across training steps. This structure allows the mechanism preserve model accuracy while still guaranteeing privacy.
Intuitively, the mechanism can be seen as follows: at each training step, fresh noise is generated and added, but part of the previous noise is stored in a buffer. In subsequent steps, portions of the stored noise are subtracted a controlled manner. This cancellation effect reduces the total amount of noise that accumulates in the model, thereby improving utility without weakening privacy guarantees.
When computing privacy, we must account for nulti-epoch participation, since in multi-epoch training the same datapoints are used multiple times. The notion of multi-epoch participation in the context of matrix factorization was first introduced by [Chquuette Chho et al. (2023a), where it was formulated as optimization problem over banded matrices. However, a key limitation of existing methods is the lack of precise theoretical guarantees on the factorization error in multi-epoch participation. While Kalinin & Lampert (2024) established general lower bound and provided an upper bound for Square Root Factorization, the error bounds for Banded Square Root Factorization, where the correlation matrix C' is p-banded, remained imprecise with respect to the bandwidth p.
In this work, we propose a novel approach to matrix factorization: rather than imposing a banded structure the correlation matrix C. we introduce banded inverse square root, enforcing the banded structure on C-1 This shiff" offers several key advantages. First, it allows for precise control over the resulting factorized matrices, enabling to derive explicit upper bounds on the factorization error with clear dependence on the bandwidth. Second, the method is computationally efficient, as it requires one just to convolve the previous noise with a quickly computable fixed sequence of coefficients, which can be done for instance via Fast Fourier Transform (FFT), making it suitable for large-scale machine learning tasks. Most importantly, we prove that our method achieves asymptotically optimal factorization error: we establish a new lower bound that matches our upper bound, closing a significant theoretical gap in the literature.
By refining the theoretical understanding of banded factorization in multi-epoch settings, our work provides both theoretical insights and practical benefits for privacy-preserving ML training. Our main contributions are:
1. We introduce a new factorization method, the Banded Inverse Square Root (BISR), which is scalable, efficient, and agnostic to the underlying training objective.
2. We prove that BISR is asymptotically optimal, by deriving tight upper and lower bounds on the multi-epoch factorization error, with explicit dependence on bandwidth and workload properties.
3. We conduct a thorough empirical evaluation, comparing BISR to existing techniques in multi participation trainingincluding Banded Square Root (BSR) (Kalinin & Lampert (022). Buffered Linear Toeplitz (BLT) (Dvijotham et al. 2024), and Banded Matrix Factorization (Band-MF) (McKenna 2025). showing that BISR achieves a higher or comparable accuracy for the large
matrix sizes.
4. In the low-memory regime, we propose an optimization method, BandInvMF, which directly optimizes the coefficients of the matrix C-1, This approach achieves error rates comparable to state-of of- offle-oo-theann the art factorization methods, while being easy and efficient to implement.
2 BACKGROUND
2.1 MATRIX FACTORIZATION (MF)
MF mechanisms provide a promising approach to the private matrix multiplication problem, which has applications in continual counting and Stochastic Gradient Descent for machine learning- Specifically, we aim to estimate the product of public matrix of coefficients A E R=xa and private matrix X E _ xd Instead of doing so directly, we adopt a factorization
BC, allowing us to estimate
'The inverse correlation matrix has heen receiving more attention recently. In the concurrent work McMahan Pilluta (2025), the authors consider the inverse correlation matrix of BLT..
2

---

Published as a conference paper at ICLR 2026
AX privately AX B(CX Z) C Here, Z ~ (0 s is appropriately scaled Gaussian noise, which ensures that CX + E RR is private; the multiplication by B preserves the privacy guarantees due DP's post-processing property.
The choice of factorization A = BC can significantly impact the quality of the private estimation. We quantify the approximation quality by the expected Frobenius error of the estimated product,
1
{B = E - I
71
where || ||r is the Frobenius norm. An elementary analysis (Li et 2015) shows that
_² n7
E(B,C)²= --1
and that the required noise strength, scales proportionally to the sensitivity of the matrix C. Let X ~ X' indicate that the update vector sequences differ only in the entries corresponding to single
data item. Then the sensitivity of the matrix C' is defined
sens(C) == sup ||CX - CX X~Xx
Private SGD. In this work, we consider the task of model training with SGD with (optional) weight decay and momentum. The corresponding update equations are 01+1 al; m,+1 and m++1 3m; + 2i, where oI....,hh 6n E Rº are the model parameters after each update step, .i....,24, the gradient vectors computed in each update step, 0 < a is the weight decay factor, and 0 - 3 < is the momentum strength
Following Kalinin & Lampert 2024), rewrite the dynamics in the matrix form θ A (0,,-.., vn) R and Aa, is the SGD) workload
with O (0,,... ,,,) R matrix defined as follows:
X
0
+
1
A =
E R
(4)
Σ a 1n-
Σ o gn---22-
2-
1
Note that, in contrast to the naive MF setting, in the SGD case any input data (gradient) depends on the previously computed model parameters, 0;-1, that is, we aim for adaptive privacy. However, Denisov et al. (022) shows that for Gaussian noise, adaptive privacy follows from the non-adaptive one, i.e., suffices for us to solve the case in which the X matrix is an arbitrary fixed data matrix.
Consequently, we estimate Aa, privately using the form A,,sX A + +C- This form corresponds to running SGD, but each individual gradient update perturbed by a correlated noise rely
vector. That has the advantage that do not need to store any previous gradients, and on any existing implementation of the SGD procedure.
In multi-epoch SGD, each data sample might contribute to more than gradient update vector. As a suitable notion of sensitivity, we adopt the setting of b-min-scparated repeated participation (two participations of any data point occur at least b update steps apart). The resulting sensitivity can be bounded as [Choquette-Chen et al. 2023a):
sens (C) S max
Σ ((CTC)) tUj
(5)
nElla
where I1g. denotes the collection of index sets drawn from {1, [I....,n n2 that contains at most elements and satisfy the condition that any two distinct indices are separated by at least b positions, so that no two indices the set lie closer than apart.
This bound becomes an equality in the case where all entries of C. C' are non-negative.
For simplicity of exposition, we implicit learning rate of 1. Because of the linearity of the operations, the general case be recovered by pre-scaling æ1 .1....,74 Tp accordingly.
3

---

Published as a conference paper at ICLR 2026
BISR noise correlation (p
Noise Z
= - Z
Clipped Aggregated Gradients
&
C =
Noise Buffer
C = =1//
?/2
X
C2 = -1/
Zz
&
Xg
2
:
Z
&
X
Figure 1: Illustration of noise correlation using the Banded Inverse Square Root (BISR) method with bandwidth 3. For example, at step 4, we form a new aggregate from a sampled batch of clipped gradients 24. We take the noise vectors 22 and 23 from the Noise Buffer and add them the gradient with coefficients c₁ add it directly obtain the private estimate 4.4. Finally, we remove 22 from the buffer and insert 24 in its place.
and C2 8 respectively. We then generate new noise vector 24 and
2.2 PRIVACY GUARANTEES
The privacy analysis of our mechanism relies on the well-established Gaussian mechanism, which allows achieving arbitrary (c, ddifffrrrntt privacy levels by calibrating the noise variance to the sensitivity of the underlying query. In particular, Theorem 2.1 Denisov et al. (2022) states that the guarantees proved for the nonadaptive continual release model extend to the fully adaptive setting under a suitable factorization of the query matrix. This ensures that the same differential privacy guarantees hold when the input stream chosen adaptively. A related multi-epoch variant was studied in Choquette-Choo et al. 2023a), which corresponds to a specific choice of the notion of neighboring streams.
Theorem 1. (Denisov et al. 2022 Theorem 2.1) 1) Let A E RaxR be a lower-triangular full-rank query matrix, and let BC be any factorization with the following property: for any two neighboring streams of vectors G, H1 E R. gu differing only in positions of participation of single user, we have ||C -H)H- S K. Let Z NO, x² 2 with a large enough so that
M(G) AG BZ B(CG 7))
satisfies (E, 8DP in the nonadaptive continual release model. Then M satisfies the same DP guarantee (with the same parameters) even when the rows of the imput are chosen adaptively.
Formally, the privacy guarantee of the Gaussian mechanism itself is characterized by the following analytic condition due to Balle& Wang (018)) which provides the exact relationship between the sensitivity, the privacy parameters, and the variance of the added Gaussian noise:
Theorem (Analytic Gaussian Mechanism (Balle Wang 2018)). Let : X Ed be function with global E, sensitivity A. For any E > U and ò E 10. 1l. the Gaussian output perturbation mechanism (xx (xx + Z with Z ~ NO0 oTT) is (D,6)-DP if and only if
4 2x
This condition enables tight calibration of the noise level a for any target privacy parameters (c, 5).
Optimal factorization. Better choices of factorization matrices achieve the same privacy levels with less added noise, potentially leading to higher utility. Therefore, various factorizations have been proposed and studied theoretically well empirically.
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 Differentially Private SGD with Banded Inverse Matrix Factorization
Input: Initialization On E IR&, dataset D, batch size B, clip norm Ç, learning rate v 0, weight decay 0 < a $ 1, momentum 0 S B < 1, loss E(O, d), noise multiplier e,, > O, coefficients of the banded inverse Toeplitz correlation matrix C-1: : (Co...., Cp-1)
1: Initialize me <- 0 E R
2: for = 1 to n do
3: Sample a minibatch S; (d1,...,dh, .d.. D
4: for j = 1 to do
5:
9j - V (0,,01, dj)
6:
9j - min (1, To: 9j
per-example clipping
7:
11 T4 + Σ}=1 Ø
aggregate clipped gradients
8:
Draw Z; ~ NV 00. TT.
9:
f + + Ei min(
Zi-t
> BISR noise injection momentum update
8
11:
a m;
> weight decay step
12:
return Pn
Choquette- Chooo et (2023a) defines the optimal factorization as the one that minimizes the expected approximation error (1). and proposed an optimization problem to (approximately) compute this factorization. A downside of this approach is that the optimization problem is computationally expensive and the numeric solution does not provide theoretical insights, such as the optimal (i.e. lowest) rate of growth of the approximation error.
On the other hand, a square root factorization introduced by Henzinger et al. (2024). is an explicit factorization, defined by A = C with positive main diagonal. Kalinin & Lampert (2024)
showed that the factorization error the square root factorization under multi-epoch participation is worse than that of the optimal factorization and they introduced banded square root (BSR) factorization, which is defined by making the matrix Ca.8 banded. A limitation of BSR that its guarantees are implicit in terms of the used bandwidth, which does not allow concluding how they relate to the optimal multi-epoch factorization at a theoretical level.
3 BANDED INVERSE SQUARE ROOT FACTORIZATION
In this section, we present our main theoretical results: we prove a new lower bound on the achievable approximation error (Theorem 3), we introduce the BISR factorization (Definition and we prove that BISR achieves this (therefore optimal) rate (Theorem 4
We first show improved version of the lower bounds of the approximation error for general factorizations from Kalinin & Lampert (2024).
Theorem 3 (General Multi- cattiiPaatiiiptiionn Lower Bound). Let A,, E RR be the SGD workload matrix ( with momentum 3 > 0 and weight decay O. In the natticpartiiiiaaioon setting with separation 1 < S and ls = [ for any factorization Ao, = BC, it holds
C(B.C) (R(vFlogn +k) (vk)
if a a= if a<
(6)
Proof Sketch. We use the probabilistic method in Lemma to obtain the bounds 9, (v for a < 1 and EBB C²) = 2 / V log n) for a 1. It remains to prove that for a = 1. we also have the lower bound EBB, B, C) ((k). For that, we prove general inequality: given a valid participation vector π
we have E EBB C) 2 A
As our second main contribution, we now introduce the BISR factorization for multi-epoch SGD. Definition 1 (Banded Inverse Square Root (BISR)). For given workload matrix A. let C be the matrix square root (i.e. C A) with positive values the diagonal. Let CP be the matrix obtained
5

---

Published as a conference paper at ICLR 2026
by: computing the inverse matrix C- -i imposing banded structure with p bands by setting all elements below the p-th diagonal to zero, iii inverting the resulting banded matrix back. Then, we denote by BISR the matrix factorization A = B"C", with 1
A(CC)
BISR can be seen as an alternative realization of the insights behind the BSR (Banded Square Root) factorization from Kalinin & Lamperi (024). There, the intuition was that making the matrix C' p- banded reduces its sensitivity without increasing the Frobenius norm of the subsequent postprocessing matrix too much, thereby resulting in overall reduction of the approximation error. The authors did not derive exact rates, though, because the dependence on is not explicit.
For BISR, instead make the matrix C-1 p-banded. This also leads reduction of the ap- proximation error compared to the non-banded case, but with two additional advantages. First, the resulting algorithm (see Algorithm and Figure for the illustration) time- and memory-efficient because the product of (C*)-1Z Z can be represented as convolution with p elements. Therefore, the computation can be performed efficiently: be stored at any time, while in an offline setting (which requires more storage), it can be accelerated further using the Fast Fourier Transform. Second, and mainly, it allows us to derive more explicit expressions of the approximation error with respect to the bandwidth p. In particular, we show the following.
streaming setting, only p rows of the matrix Z need to
Theorem 4 (BISR Approximation Error). For 1 S S and 1 S S is the following upper bound holds for the factorizaaooiiioioon error of the BISR Aa, B Ca g (as in Definition
J0x -10= Villogp+ +
nk 5
nk log
kplog 2 b
for a a=1,
E(B 0. Ca.s)
(7)
(o.0(VK)
for acl,
where Oa and Og indicate that the hidden constant may depend on and 3, respectively.
Proof sketch. To prove Theorem we use Lemma 11 to bound the Frobenius norm |Basell plp.. Then, Theorem 2 from Kalinin & Lampert (2024) (see Theorem (5). together with monotonicity of values C% from Lemma 8 provides explicit way to express the sensitivity sens,, conss,,(Co,sb (Co,s). To bound the sensitivity, we apply Lemma
12 to bound individual values. The product of the bounds on [
and senst, (Ca,8) yields the result. The full proof of Theorem can be found in the appendix. A
For comparison, Kalinin & Lampert (2024) proved a bound O nk logg + Op(Vk) the
approximation error of the BSR in the case a = 1, = O. While the first term also appears in (7). the second is non- con-informativ about the effect of the bandwidth, p. Therefore, it does not allow making statement about the optimality of the BSR.
In contrast, Theorem 4 is explicit about the role of p. Choosing its value to be Obblog b), such that the occurring terms in 7 are minimized, we obtain the following corollary.
Corollary 1 (Optimized BISR Approximation Error). Let Aa, D be the BISR factor-
ization defined of Definition 1 For 1 < b n let k [1]. Then. for pd Obb b), the matrix factorization error admits the following optimized upper bound:
SOs (Vilogn+ for = [
E(B
for < 1.
Comparing the upper bound in eq. (8) with the lower bound in eq. (6. we obtain that BISR is an asymptotically optimal factorization in the multi- participation setting.
To use the BISR factorization, we apply the following lemma, which provides analytic expressions for the elements of the inverse matrix C-1 0.

---

Published as a conference paper at ICLR 2026
BSR
230
ESR
ESR
BISR
140
BISR
BISR
R955E
28
044
82-
10.
107
107
201
Bandwidth (p)
Bandwidth (p)
Bendwidth (p)
a 1,
(b) a 1, 3 0.9
(c) c 0.999, B
Figure 2: RMSE comparison for Banded Square Root (BSR) and Banded Inverse Square Root (BISR) methods across varying bandwidths (p). The results are shown for a fixed matrix size of n = 16384
and participation number of it = 8. For BSR, the choice p = b is numerically optimal, while for BISR a smaller bandwidth suffices to achieve an optimal value.
Lemma 1 (Inverse Square Root of the Matrix Aa,ā). For k 2 O, ler = (-1) = =
(- kx)
The inverse square root of the matrix A_ defined in 4 for s casia
2k-1
8
1
0
k a..3 = -x=;= PisPrr-jaa Te-zak
Cany
where
(9)
j=0
8 Cn-1
3
n
The values of the matrix Cz,9 can then be computed efficiently via the Fast Fourier Transform (FFT) convolution of the sequences tya? and ,, where the sequence iU for 1, 1,... can be computed in linear time using the recursive expression i j-3/2 F--1-
Following the work of Andersson & Yehudayoff (2025), we show that the space complexity of the matrix (C%_s)=1 is equal p. meaning that exact multiplication with random real vector in streaming setting, performing continuous operations, requires storing p real values (not including the memory needed to store the matrix coefficients). This implies that, for memory-efficiett computation, small bandwidth p consider approximate multiplication. We formally state
must either the result in the following lemma:
Lemma 2.
The space complexity-defimed the minimum buffer size required by streaming algorithm to correctly process an input-for computing the product of the Toeplitz matrix (C% with an arbitrary vector z E for n 2p is exactly p. and least n-8 for Co,
4 EXPERIMENTS
In this section, we present numerical results from evaluating various factorization methods in the multi-participation regime.
We first study the effect of using different bandwidths for BSR and BISR, as shown in Figure We found that. in settings, the optimal bandwidth for BSR coincides with the separation parameter b, whereas for BISR smaller bandwidth suffices; therefore, in future comparisons with BISR, we propose optimizing the bandwidth determine the optimal y²
We compare BISR with several other methods, including Banded Square Root (BSR), Banded Matrix Factorization (BandMF), introduced by McKenna (2025), and Buffered Linear Toeplitz (BLT), introduced by Dvijotham et al. (2024) and adapted for multi- mulli-participation training by McMahan et al.) (2024). We use a buffer size of 4, as recommended, and observe that the error saturates quickly as the buffer size increases. We BandMF with bandwidth equal b, as did not observe any benefit from using a larger bandwidth. Moreover, we conjecture that optimal multi-epoch participation can always be achieved banded lower triangular matrix with bandwidth b.
7

---

Published as a conference paper at ICLR 2026
220
22
26
BLT
BSR mn
BISR (p=p")
BandNF (p 60
200
140
160
BSR lp
p')
(p- 5)
14.5
14.0
13.5
RisR 1n=p11
BandM
140
18
120
13.0
100
12.5
14.
80
12.0
11.5
15
10
10"
10
16"
10
10'
10
10
10"
10
10'
10'
30
10'
Iterations [n)
iterations
iterations
(a) 16,
1, 3
(b) 1: 16, 8
0.9
(c) 1:
16, a 0.999, 3
B5R (p -b
RISR (pm
70
RSR tp
(p-ppp
5.5
60
Bandh (p ti
5.0
AMSE
BLT
RMSE
40
jp-
20-
3.5
BISR to =p'
10-
(r-bi
10
10
10"
10.
10f
10r
102
10"
10" 36
16 102
10"
16*
16F
Iterations
iterations (n)
iterationn [n)
(d)
1, 0
(e) 1: 4, 1, 0.9
(1) 1: 4, 0.999, =
Figure 3: RMSE across varying matrix sizes for different factorization methods under multiple optimizer settings and participation levels. We showed that also in practice, BISR performs on par with, or even better than, BSR and BLT. However, methods based on numerical optimization, such as BandMF, may achieve superior performance in certain regimes.
We emphasize that BLT has only been described, analyzed, and implemented for prefix-sum matrices Therefore, we do not show BLT results for momentum and weight decay plots. For all methods except BISR, we use efficient implementations from the jax-privacy library (Balle et al. 2025).
Our experiments (Figure 3) show that banded inverse square root factorization consistently matches or exceeds BSR in quality across all regimes and outperforms it in scenarios with large number of participations. The improvement is particularly pronounced when the participation count is high (k 16). BISR achieves RMSE comparable to that of BLT, but has the ad advantage of easier implementation for both factorization and training, as it only requires convolving previous noise with fixed set of coefficientsan "embarrassingly parallel" operation (see McKKnna (2025)). While in practice, BandMF achieves slightly better RMSH at 16, requires solving a computationally expensive optimization problem, making it impractical for matrix sizes beyond 4096.
5 FROM BISR TO BANDINVMF
In the previous sections, we established that BISR has asymptotically optimal rate for large bandwidths p ~ blogh, b. However, practice, one might want to work with a smaller value of p to save memory and computational resources. In this section, we showcase modification to BISR with improved practical properties in this regime. We propose to keep the construction a banded inverse matrix with Toeplitz structure, but to set its values not by the closed form expressions (9) but by numeric optimization. Specifically, we optimize an upper bound on b-min separation participation, given by Equation 5
For the sake of numerical optimization, we assume that the optimum is achieved for indices of the form i + kb. This assumption can be justified, as observed that the resulting solution for matrix C is positive and decreasing, which guarantees optimality. If the sequence is not decreasing, it can be uniformly bounded by decreasing sequence. Specifically, if the values on the diagonals of C CJ.1. then they are upper bounded by maxe2, CI. which is decreasing sequence by construction. We use banded inverse square root factorization as an initialization for the coefficients. We provide an efficient JAX implementation in the Appendix (see Algorithm I as well as the convergence plots Figure
IIn concurrent work by Huang et al. 2025), BLT has been adapted to work with a momentum workload. "This is possible because even though we have shown that BISR provides asymptotically optimal factorization, that does imply that is superior to all other methods for finite problem sizes.
8

---

Published as a conference paper at ICLR 2026
60.
DSR
600
DSA
40-
65x
BISR
50
OCT
Band ruee
500
Band noler
Banddee
30
Bandfti
Band roll?
RMSE
-0
Banddhr
400
30
200
20
200
10.
10
12
14
16
10
12
14
10
12
14
16
Bandwidth
Bandwidth (p)
Bandwidth (p)
(a) 1:
4, Q 1, B
(b) l/
1, 3
0.9
(c) 1:
0.999, 3
120-
BSR
B5R
70-
85R
Risa
1000
60-
Bandindf
Bandltt
RMSS
80.
Bancki
RMSE
800-
50
60-
600-
400
20
15
Bandwidth (p)
Bandwidth (9)
Bandwidth (p)
(d) 16, a 8
(c) k 16, a 1. 0.9
(f) k: 16, a 0.999, B =
Figure 4: RMSE across different factorizations and optimization parameters o. 33 with small band- width. The plot shows that BandInvMF and BISR can significantly reduce RMSE for a small bandwidth regime, justifying the use of banded inverse methods instead of banded factorizations.
The numerical results are presented in Figure reffrreed to as Ban We observe that the error decreases drastically even with the addition of single band, compared trivial factorization. This observation is supported theoretically by the following lemma.
.......,) be lower triangular Toeplitz mafrix with 1 on the main diagonal and - on the subdlagonal. Then, for single participation and the prefix sum matrix A1,0, the following bound on the matrix factorizaiin error holds:
Lemma (Optimal Band Inversion Error). Let the matrix C = - -X,0....,
inf E(A100T), ,C,) =0))=((m)) Onn 1E(0,1)
(10)
Lemma 3 shows that the optimized inverse banded matrix factorization can achieve an asymptotically better bound than a trivial factorization A x II, which yields an error of O(vī). Moreover, from Theorem 4 for small p. the leading term for banded inverse square root factorization remains of order O(Vn). Therefore, we advocate for optimizing the coefficients when the bandwidth is small.
We compare Band- with other methods for training the 3-Block ConvNet model on CIFAR- 10 and the BERT-base model (~100M parameters) on IMDB (see Figure 5). both with and without amplification by subsampling. For a fairer comparison, we use a recently proposed bins-and-balls subsampling mechanism (Chua et al.) (025), which combines the accuracy benefits of Poisson subsampling with improved implementation efficiency. More importantly, it supports the matrix mechanism via the MCMC accountant (Choquette-Cher et al., 2024b c). even when the matrix C' is not banded. Our results indicate that in a low-memory regime, inverse correlation matrix methods BISR and Bnnd-Iny-MF achieve significantly higher accuracy than BSR and Band-MF, and consistently outperform DP-SGD, with and without amplification. Although Band-Im Leved-In--Na Inv-MF achieves lower RMSE than BISR, we did not observe corresponding gain in accuracy. This indicates that RMSE alone is not sufficient proxy for model performance in matrix factorization.
6 DISCUSSION
This work demonstrates that imposing a banded structure on the inverse correlation matrix, rather than the matrix itself, leads to both theoretical and practical benefits for differentially private training across multiple participations. Our Banded Inverse Square Root (BISR) method enables explicit factorization, supporting clean error analysis and efficient implementation.
We prove that BISR achieves asymptotically optimal factorization error by improving upon previously established lower bounds and showing that BISR matches the asymptotics precisely, thereby closing

---

Published as a conference paper at ICLR 2026
50-
50
Accuracy (%)
Accuracy
40
30
30
BSR (p m-1
BSR Ip m4
20
20
Band-Ine-WF (p-
Band-Iny-kf 1p-44
Band-MF
Band
2
6
10
10
Epochs
Epochs
(a) CIFAR-10 (Amplified)
(b) CIFAR-10 (Non-amplified)
90.0
87.5
Accuracy
80.0
77.5
BSR (p m
BSR (p
BISR (p 4)
75.0
BISR (p 4)
DASCD
DP-SGD
72.5
(a
72.5
70.0
Band-M (p
70.0
Band-MF (p 4)
10
10
Epochs
Epochs
(c) IMDB (Amplified)
(d) IMDB (Non-amplified)
Figure 5: Accuracy results for CIFAR-10 and IMDB in the small bandwidth (low-memory) regime. For CIFAR-10, both amplified (left) and non-amplified (right) results show that inverse factorization methods, BISR and Band-Inv-MF, achieve significantly higher accuracy compared to Band-MF. Both plots correspond to (9, 10 S-DP, with training performed using momentum / 0.9 and weight decay a = 0.9999, which we found to be optimal (see Tables [ and [] in the appendix). For IMDB, report accuracy from fine-tuning under the same ww-memmry regime, comparing amplified and non-amplified settings, with training performed using momentum / = 0.95 and weight decay 0.99999 (see Tables andd 4
fundamental gap the theory. An interesting direction for future work is to close the gap in constant dependence, as numerical optimization methods (e.g., BandMF, BLT), despite their computational cost, may outperform BISR.
In the low-memory regime, we find it beneficial to optimize directly over the coefficients of the inverse correlation matrix. Our Band-Inv-MF method achieves a lower matrix factorization error compared BISR. However, these improvements do not yet translate gains in model accuracy when training with the amplification by subsampling. Future research should focus on optimizing the matrix coefficients while explicitly accounting for amplification, in order bridge this gap.
ACKNOWLEDGMENTS
We thank Arun Ganesh for providing the code for the MCMC accountant. We thank Joel Andersson, Rasmus Pagh and Monika Henzinger for valuable comments the early version of the draft. We thank Christian Lebeda for fruitful discussion on the lower bound theorem.
Jalaj Upadhyays research was funded by the Rutgers Decanal Grant no. 302918, NSF CNS 2433628, Google Research Scholar Award, and Google Seed Fund Grant.
Nikita Kalinin's research was funded in part by the Austrian Science Fund (FWF) [10.55776/COE12]
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Joel Daniel Andersson and Rasmus Pagh. smooth binary mechanism for efficient private continual observation. In Conference Neural Information Processing Systems (NeurIPS), 2023.
Joel Daniel Andersson and Rasmus Pagh. Streaming private continual counting via binning. In IEEE Conference on Secure and Trustworty Machine Learning (SuTML), 2025.
Joel Daniel Andersson and Amir Yehudayoff. On the space complexity of online convolution, 2025.
arXiv preprint arXiv:2505.00181
Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy:
Analytical calibration and optimal denoising. In International Conference Machine Learing
(ICML), 2018.
Borja Balle, Leonard Berrada, Zachary Charles, Christopher A Choquette- Chhoo, Soham De, Vadym Doroshenko, Dj Dvijotham, Andrew Galen, Arun Ganesh, Sahra Ghalebikesabi, Jamie Hayes, Peter Kairouz, Ryan McKenna, Brendan McMahan, Aneesh Pappu, Natalia Ponomareva, Mikhail Pravilov, Keith Rush, Samuel L. Smith, and Robert Stanforth. JAX-Privacy: Algo- machine learning in JAX, 2025. URL http: httt:://githbl com/ foogle-deepmin// jax privacy
rithms for
Alexander Bienstock, Ujjwal Kumar, and Antigoni Polychroniadou. Dmm: Distributed matrix
mechanism for differentially-privve privvtt federated learning based on constant-overhead linear secret resharing. In International Conference on Machine Learing (ICML), 2025.
A. Böttcher and S. M. Grudsky. Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis. Springer, 2000.
C. A. Choquette-Choo, A. Ganesh, R. McKenna, H. B. McMahan, K. Rush, A. G. Thakurta, and X. Zheng. (Amplified) banded matrix factorization: A unified approach to private training. In Conference on Neural Information Processing Systems (NeurIPS), 2023a.
Christopher A Choquette-Choo, H Brendan McMahan, Keith Rush, and Abhradeep Thakurta. Multi- epoch matrix factorization mechanisms for private machine learning, In International Conference on Machine Learing (ICML), 2023b.
Christopher Choquette-Chern Krishnamurthy Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Correlated noise provably beats independent noise for dif- ferentially private learning. In International Conference on Learning Representations (ICLR), 2024a.
Christopher A Choquette-Chooe Arun Ganesh, Saminul Haque, Thomas Steinke, and Abhradeep Thakurta. Near exact privacy amplification for matrix mechanisms. In International Conference on Learning Representations (ICLR), 2024b.
Christopher A Choquette-Choo Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Privacy amplification for matrix mechanisms. In International Conference Learning Representations (ICLR), 2024c.
Lynn Chua, Badih Ghazi, Charlie Harrison, Ethan Leeman, Pritish Kamath, Ravi Kumar, Pasin Ma- nurangsi, Amer Sinha, and Chiyuan Zhang. Balls-and-Bine sampling for DP-SGD. In Conference on Uncertainty in Artificial Intelligence (AISTATS), 2025.
Denisov, H. McMahan, J. Rush, A. Smith, and G. A. Thakurta. Improved Differential Privacy for SGD via optimal private linear operators on adaptive streams. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
Krishnamurthy Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and ncar-optimal noise generation for streaming differential privacy. In Symposium on Foundations of Computer Science (FOCS), 2024.
H. Fichtenberger, M. Henzinger, and J. Upadhyay. Constant matters:
Fine-grainee complexity of differentially private continual observation using completely bounded norms. In International Conference Machine Learing (ICMI.,, 2023.
11

---

Published as a conference paper at ICLR 2026
Arun Ganesh, Brendan McMahan, and Abhradeep Thakurta. On design principles for private adaptive optimizers, 2025. arXiv preprint arXiv:2507.00 129.
M. Henzinger, J. Upadhyay, and S. Upadhyay. A unifying framework for differentially private sums under continual observation. In Symposium on Discrete Algorithms (SODA), 2024.
Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. In Symposium on Discrete Algorithms (SODA), 2025.
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight enror bounds differen- tially private continual counting. In Symposium on Discrete Algorithms (SODA), 2023.
Monika Henzinger, Nikita P. Kalinin, and Jalaj Upadhyay. Binned group algebra factorization for differentially private continual counting. 2025a. arXiv:2504.0439..
Monika Henzinger, Nikita P. Kalinin, and Jalaj Upadhyay. Normalized square root: Sharper ma- trix factorization bounds for differentially private continual counting, 2025b. arXiv preprint arXiv:2509.144 14334.
Yue Huang, Jiaojiao Zhang, and Qing Ling, Memory-efficient correlated noise for locally differentially private momentum in distributed learning. In International Workshop on Machine Learning for Signal Processing (MLSP). IEEE, 2025.
P. Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu. Practical and private (deep) learning without sampling shuffling. In International Conference on Machine Learing (ICML), 2021.
N. Kalinin and C. H. Lamperr. Banded square root matrix factorization for differentially private model training. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
Nikita P Kalinin, Jalaj Upadhyay, and Christoph H Lampert. Continual release moment estimation with differential privacy. In Conference Neural Information Processing Systems (NeurIPS), 2025.
Anastasiaa Koloskova, Ryan McKenna, Zachary Charles, John Rush, and H. Brendan McMahan. Gradient descent with linearly correlated noise: Theory and applications to differential privacy. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi. The matrix mechanism: Optimizing linear counting queries under Differential Privacy. International Conference on Very Large Data Bases (VLDB), 2015.
R. McKenna. Scaling up the banded matrix factorization mechanism for differentially private ML. In International Conference on Learning Representations (ICLR), 2025.
H. B. McMahan, Z. Xu, and Y. Zhang. A hassle-free algorithm for private learning in practice: Don't use tree aggregation, use BLTs. In Conference on Empirical Methods on Natural Language Processing (EMNLP), 2024.
H Brendan McMahan and Krishna Pillutla. An inversion theorem for Buffered Linear Toeplitz (BLT) matrices and applications to streaming differential privacy, 2025. arXiv preprint arXiv:250..21413.
Krishna Pillutla, Jalaj Upadhyay, Christopher A Choquette-Choo Krishnamurthy Dvijotham, Arun Ganesh, Monika Henzinger, Jonathan Katz, Ryan McKenna, H Brendan McMahan, Keith Rush, et al. Correlated noise mechanisms for differentially private learning, 2025. arXiv preprint arXiv:2506.08201
Gilbert Strang. A proposal for Toeplitz matrix calculations. Studies Applied Mathematics, 1986.
Zheng Xu and Yanxiang Zhang. Advances private training for production on-device language models, 2024. Goolge Research Blog.
Jiaojiao Zhang, Linglingzhi Zhu, Dominik Fay, and Mikael Johansson. Locally differentially private online federated learning with correlated noise. In IEEE Transactions on Signal Processing, 2025.
12

---

Published as a conference paper at ICLR 2026
KEY INEQUALITIES AND RELATIONSHIPS
This section compiles the fundamental inequalities and key relationships employed throughout this study. Each entry is presented with a concise explanation of its origin or the context in which it arises.
1/2 k
1
2k
Henzinger et al.
(024)
4
k
1
2.
STk S
Lemma 2.1 from Dvijotham et al.
2024)
TT( +1)
Tk
3.
Σ
P-1
Th 11+
VT Σ 1
1 p-1
11
2/D VT.
Integral inequality.
Vk
R=
p-1
4.
Σ
r < 1 + logp
Lemma
5.
0,
a g 3 TJTk-3
Theorem 1 from Kalinin & Lampert 20244
1=0
(1 - -3)
6.
18
1,0
1
for k 2 1.
Lemma 10
2k
h Σ
k
7.
1.9
pk-j
In the proof of Lemma
1=0
j=0
k Σ
k
8.
gh-1
Σ
9
3
In the proof of Lemma
1=0
1=0
1.0
(1 (k-
9.
Σ
C/
1,8
In the proof of Lemma
1- 3
1=0
10.
Ta(1 - 3) <
1.B
1.8 (1 B) S &6
Lemma
1=0
11.
log(k k + 1)
<
k-1
2.8222 <
1 log k
Lemma
4
(1 - 3)
j=0
a
12.
<
0.3
<
Lemma
2V +I
(1 - 3/a) +I
k-1
13. 15 Σ
100 5
(a - 3)2 log
1
Lemma
1 a
1=0
14. FR (-1)* 1122)
-1
2k Tk
Lemma
15. 20.8
% = Σ Po
Lemmal !
1=0
16. (x + +) < 2.. 0
Lemma
13

---

Published as a conference paper at ICLR 2026
A PROOFS
We start by stating some auxiliary results that will be extensively used throughout the proofs.
Lemma 4 (Theorem in Kalinin & Lampert (024) Square Root of the Matrix Aa, For l 2
let rk (- For s S the square root matrix Ca.9 A has the following
explicit form:
0
a
1
Ca.p
where
Σ o by j=0
(11)
Cn-1
Theorem 5 (Theorem 2 from Kalinin & Lampert (2024)). Let M be lower triangular Toeplitz
matrix with decreasing negative entries mo 2 m1 2 m2 Z ... mn-1 2 on the diagonals. Then the sensitivity of M in the setting of b-min- separnteearttionn is
k-1
sensk (MM) = Σ
M M,11+MM
(12)
where Mc-1+50) denotes the (1 (1+1b) jb)-thh column of M.
Lemma 5 (Lemma 7 from Kalinin & Lampert 2024)). For E (I....,m} it holds for ce 8.B as
defined in equation
log(k k: + 1)
k-1
1 1 log k
(c:
(13)
4
(1 - B)2
1=0
for a and otherwise
15
Σ
cc 1
(a 3)
1
log
a-
1
(14)
1=0
Lemma 2. The space complexity-definel as the minimum buffer size required by a streaming algorithm correctly process input-for computing the product of the Toeplitz matrix (C (Ca,g) with an arbitrary vector 2 E 1R",for n 2 2p 1, is exactly and at least n-5 2 for a,
Throughout this proof, we use only results from Andersson & Yehudayoff (0025) and thus any reference theorem or lemma should be understood as coming from that work. We use their Lemma 7, which lower-bounds the space complexity of a Toeplitz matrix using the rank of a corresponding Hankel matrix of its coefficients. The matrix C_, has a generating function
Proof of Lemma 2
f f= (1 - ax)) 3w). The proof of their Corollary 16 implies that the Hankel matrix H [f] has corank at most 3. Thus, Lemma 7 implies that C has space complexity least ~+1 3. For the matrix (C% a. -1 the generating function a rational function degree Pt therefore, for n 2 2p 1, their Theorem implies that the space complexity is exactly p. concluding the proof.
Theorem 3 (General Multi- PattipPartiiiiationn Lower Bound). Let Aa, Rexn be the SGD workload matrix (4), with momentum 3 > 0 and weight decay > 0. In the multi-particiiation setting with separation 1 < b and k [ f. any factorization A BC, holds
E(B.) = [1(Vklogn k) if a a= if a a<
(6)
(vk)
Proof of Theorem 3 We use the probabilistic method in Lemma to obtain the bounds (g((k) for a < 1 and E{B, = (VV/ log n) for a = It remains to prove that for a = 1, we also have the lower bound E(B, C) ((k).
We begin with the following observation: given a matrix C, we can compute an optimal participation scheme represented by vector with ones at positions corresponding participating columns,
14

---

Published as a conference paper at ICLR 2026
denoted by .c. As lower bound, consider specific participation vector Ti, with ones in columns indexed by + ib for i [0, 1], such that |T] = k. By construction, we have sensg,b(C) = || 2 || ll2. Therefore, the error can be bounded as follows:
E(B = vn
B 6 (C) z |||I||CTille 2
|1BCmlll=
= // A1, (15)
vn
As lower bound, consider 8 0 as | 1 2l 2 || 1 12. The elements of the matrix A1,0
are positive and non-increasing. Therefore, by Theorem |
the (k, -ssessittitt of A1,0 is exactly
|1, l/2. By Theorem from Kalinin & Lampert (2024), this sensitivity is at least kv in the lower bound:
resulting
v3
k [((k),
E(B, C) 2
(16)
v
which concludes the proof.
Lemma 6. Let Aa,3 E R=x* be the SGD workload matrix 4 In the multi cnulti-prticcipation setting
with separation 1 < b S n and k 1, for any factorization Aa, BC. it holds that
E(B 0) = [2(Vklog n),
a a=1
(17)
(((V)),
<<1
Proof. Here, we refine Theorem 8 from Kalinin & Lampert (0224) by removing the assumption that the scalar products between the columns of the matrix are non-negative, i.c., C 0. first prove that
1 47 II
sense (C)
(18)
To do so, we lower bound the b-min separation participation by the (k, b)-patticiipaiion, where we have a fixed b separation between vectors but are allowed to include only a subset of them. This splits the set of all column indices into disjoint subsets Sj for E [1, b] with |S,| S k. Then, the following inequality holds:
sensk, (C) (C)² Z sup
Σ iES
(19)
jE(L,6] scS,
where Cb.a denotes the i-th column of the matrix C. To prove a lower bound, we use the probabilistic method. Consider i.i.d. random variables ~ Bernoulli Then:
sup SCS,
C
C >
E
Σ SES
C
1
1
1 +
1 Σ
(Gra)
GRan)
2
:E
:ES
i
(20)
Σ
112 + -11>
Σ
C
2
Σ
2
EE
iES,
VES,
Thus,
sens (C)² max jE[L,6]
Σ 10,112
N 46
Σ
Cr.a
(21)
4
4b
1ES,
1=1
Therefore,
1 - |B|| s E(B. C)
1
1
>
|CIFF/CIP
[C
A
nb mb
n/nb
2/nb
(22)
The nuclear norm of the matrix Aa,9 has been lower bounded in Lemma 8 of Kalinin & Lampert (2024) by Ω(n logn) for a = 1, and by 2(n) for a < 1. Substituting proot.
concludes the
15

---

Published as a conference paper at ICLR 2026
Lemma 1 (Inverse Square Root of the Matrix Aa,z). For k 2 0, ler (-1) 2k-1
(
1/2)
The inverse square root of the matrix Ar, defined in for S $ <a 1,
2k-1
0
1
k where ox = - 7
(9)
a,
1=0
20,8
n-
Proof. The matrix for the momentum matrix is given by:
1
0
1
0
0
a
0
8
1
A = Aa, x Ap,0-
(23)
:
a=
n-2
gn-1
Bn-2
The inverse square root then takes the form:
C = 3,0-
(24)
since all lower triangular Toeplitz (LTT) matrices commute (see Strang (986) or Böttcher & Grudsky (2000)) Therefore, suffices to prove that the inverse square root the matrix Co, lower triangular Toeplitz matrix with elements 7ça², which would imply the stated formula for 20. since
the product of LTT matrices is given by the convolution of their elements.
The proof for the matrix Cad is based on the identities of the generating functions of the sequences re and fx. derived simultaneously using the binomial formula:
az) 1/2
1/2
(-1)+
(-1)
Σ rra x*
b:
k=0
k=0
(25)
1/2 (-1)%
(1 - az) 1/2_
)
Σ Fra
h:
k=
k==
Then the generating function of the product of the matrices C. and the proposed C=-1 1 is given by:
8
n
Σ
x rka F
az=az) (1 -x)aa/)) 1/2 1,
(26)
implying that Froe are indeed the coefficients of C_ which concludes the proof.
Lemma 7 (Bounds on diagonal entries of CT, The diagonal elements of the inverse square root of the momentum matrix CT defined in equation (9) with parameter S denoted as
(1, 1.8 .2 .....,,,....). satisfy the following inequality:
F1 B) < c S0, for k 2 1.
(27)
Proof. The values 2 are given by the convolution i and skrki
k -1+ +
k
2/.
(28)
1=0
Since Fy is negative for 2 1, the summation term is positive. Furthermore, 1 8h < 11 + B, and since f is negative, we obtain the lower bound:
-1.9 2 F1 + +
(29)
This bound is tight for l as 2/.3
148
16

---

Published as a conference paper at ICLR 2026
For the upper bound, first consider the special cases. When B = 0. have 21.0
řx 0. For
3 = 1, we formally obtain:
1,
k 0,
Σ Fytk-j
1,
h 1, 0,
(30)
otherwise.
This follows from the observation that CT x CT = AT which has the structure described in the equation.
Since the inequality holds for = 1, we now consider k 2 2, where oz =0. 0. We show the following, which establishes the upper bound:
2.8 be the diagonal elements of Proposition (Monotonicity of diagonal elements of CT Let 6K
C defined in equation ( Then 21.3 is increasing function of 3, varying from G& at B = 0 to 0 eg
at 3 11
Proof. To do so, differentiate 2 with respect B:
det.3 d3
k- T 1rkk-jo8-1- gh-1
k-1
kinB"-1
+
kF + Σ Tイ 35
(31)
To prove that this expression is positive, we analyze the term in brackets. As 3 + 0, the term tends positive infinity since Fyドk-j are positive and j k negative. Moreover, this term is decreasing
as B + 1, so it suffices to check its non-negativity at B = 1, i.e.
do
0
(32)
d3
3=1
Setting in equation (3T), we have
dē
1...
k-1 kFa
k
Σ
Fytu-jj-
(33)
d3
B=1
To show this, we use an auxiliary identity for the values ドzプ!
-1
r3
+
(34)
2j
2
2j
2
2
Using the identity
34
in equation
33 we obtain:
d d(22.))
1
1 h-1
Σ
Tk
+
r Tsūk-)
d3
2
8=1
==1
j=1
(35)
1
Σ
Σ
Tz 0.
2
Since both sums vanish for &: 2 2, this concludes the proof of Proposition 1
This completes the proof of the lemma.
Lemma 8 (Decresing values). The values (1, 2. ...., 1- ;
a.3 go.
6. of matrix C a.g as
defined in Lemma 12 are decreasing.
17

---

Published as a conference paper at ICLR 2026
Proof. The first values are decreasing, shown in Kalinin & Lampert 2024) values, we prove that
For the remaining
9pth
0.8 n gpth+1
Σ 20. 6-g
9. (optk-s 9pth+1-)) 2 0.
(36)
In Lemma 7 we prove that (-Cj 2 O, so each term in the summation is non-negative. Since
the differences (g. o. 0.Bl completing the proof.
9i+1) are also non-negative by the induction step, the inequality follows,
Lemma 9 (Bound on the matrix diagonal sum of CT.3). The diagonal elements of the inverse square root of the momentum matrix T defined in equation 4 with parameter 0 S B < 1, denoted as
(1, 2/.8 22 ..... ...... 21.8 satisfy the following inequality:
Tx - 3)
Σ
S
ck
2.9
(1-1),
for k 2 1.
(37)
j=0
Here 2 as defined by equation
9
Proof. We first state several properties of the sums of 21.8.
8gB0 rk-j:
b 1.8 gh
(2)
B Pk-j
(38)
1=
1=0
1. (1 gk-
(3)
1.9
1 1 8
1=0
which can be derived from equating the coefficients of the following generating function identities, respectively:
Br
(1) VI x /
Bx
VI
(2) [V- x 1 3x
x
v1
x
(39)
Br
fr
(3) V1 z Bx
x
Bx 1
V1 zV Br
Upper Bound. the terms 2l.8.
First, rewrite the expression as follows by multiplying and dividing by
1.8 (1 - gk- + (gh-++1
3.3 (1- - 3) (1 3) Σ
1.3 -3)
ck
ck
1-
==u
1=0
(40)
1.9 3
r3 Fk gh+
8
1=0
1=0
where the third equality follows from equation 38 (2). For O, the expression is identically 0. So. now consider when 3 > O. We want to show that
8
3
Tk-j
(41)
0=
18

---

Published as a conference paper at ICLR 2026
for all B E (0, 1].
As 3 increases from 0 to 1, the sum is clearly increasing, since the only positive term does not have 8 multiplier. For / 1, the equals zero, the sequences řy and ry have inverse generating functions. Therefore, the sum remains negative, concluding the proof of the upper bound.
Lower Bound. For the lower bound, using equation
38 and the recurrence relation of f, stated in
Lemma I we get
2 (x(1-8) 3) 3)=
rk-j ry8krkj
rx(1 - -3)=
83 rk-j j +
Brk
1=0
==
j=1
Tk Σ
rj
rk "k-33"
-30-1
B Tk 2
Tj
rk-
(42)
2j -
2j
j=1
j=1
2 Σ Ty
/=0
concluding the proof. In the above, the first inequality follows from the fact that 0 < B S 1. The fact trivially true for 3 0.
Lemma 10 (Bound on diagonal values of the matrix C1,a). The diagonal values of the matrix C1,8
(see equation (T)) with parameter 0 S 3 < 1, denoted as (1, c ,2 1,B
c2 satisfy the
inequality:
(1 - (1-3)
1.8 Ck
1,8 S
for k
(43)
k-1
2k
Proof. We first prove that
k k-1
ck 2 (rk-1 rx 3).
(44)
Using the expression of c
1.9
we have
k-1
k
k-1 c%
1.3 (rk-1 - (1)(1- - 3) = Σ
Tynk-1
Tyrk
Σ
TyTk-j (fk-1-Take TTx) 3)
1=0
)=0
k-1
B(rk-1
rk)
Ty (rk-jj1- ( r*.
j=1
k-1
3h
rk)
+
-kk--kk-ss)- -
Tk
==1
We note that F3 a decreasing sequence; therefore, the first two terms inside the brackets are positive, and the powers of 3 in front of them are non-positive. Therefore, as lower bound, we can substitute inside the sum:
1.9 ch ot (FR-1 - rx) B) gh
rk- Tk Σ
(Tk---1 Tk-)) - rk
(45)
j=1
= gh |---1 - 2rx + (1 Tk-1) - (1-2ra) =
Using this inequality, we obtain:
1.8
1,
1
%
c-1
(cp-1
Th-1 1
Tk
(1
1
1,3
1,8
ck
Ck-1
C-1
(46)
1 Th-1
1
g)2
<
1
2k
1.8
2k
C
concluding the proof.
19

---

Published as a conference paper at ICLR 2026
Lemma 11 (Bounds diagonals of Ba,.)) The matrix B in the factorzatooo is lower
triangular Toeplitz matrix. The values on us diagonals are
a.B 8 ..... 1 (1,9 a. 22 1-11
0.8
where O S a cp-1 for i2 p (47)
1,8/a
where 0/o for S sisp-- 1 is as defined in equation
Proof. The first values are identical to the square root factorization the inverse. The remaining values satisfy the following recurrence:
e, due to the uniqueness of
j+1 - -i-
1/B// 1 -i-
ga.3
a 1,1//
(48)
a a-
1 1- 3/0
1=0
1=0
Therefore, it suffices to prove that b.u I
1. pp
since we can then substitute ,3 with B/a.
p-1
gi-j+1
p-1
p-1 ge+1-p P
1.3 BP-j
6
1
2LB
1-3
B
j=0
j=0
1=
1
Σ
1.9
+ B(+1-p
p-1
213 (-p0-3p-)
+
(49)
1 3
1-3
1=0
1 gi+1pp
1.8 + cp- g
1,9
1 /=0
We now use Lemma 9 to first show that 6, 2 0, since the sum of 2) is non-negative and all other terms are positive. Second, we establish that:
8 - 1 - gitt
(1 3)c + 1.8 + gitt-p- = =C--1
2,3
(50)
1-3
which completes the proof.
Lemma 12 (Bounds diagonals of CP g. The matrix C in the BISR factorization is lower
triangular Toeplitz matrix. The values its diagonals are (1, 0.3 a.3
1p-1: gp.. ..... In-1).
0.,3
0.
....,
where C 2/2/a (for <isp 1) is defined in equation and
(1 (1-8/a)3 -1
0 S 9i < a' min (c) 1.3/a ,
1.3/0 (333 for Msja 1+
and i2p.
4p(1 3//)) 3/a))
(51)
Proof. The first values of Ch, are the same as those of Ca,B since the matrix is Lower Triangular Toeplitz (LTT). For the subsequent values, we first prove the following inequality by induction:
p M
p-1
9:
19
Σ
c. a 2.8/0
(52)
f=1
observe that for all sequences Eg 3 and gi 0,3 we can factor out a by replacing 3 with 3/o.
Therefore, it suffices to prove the inequality g. < c
c..8n' i-p after which we may substitute 3 with
3/o. For the subsequent values, we establish the stated bound g, < 2/. using Lemma 10
9ptk
p+t
1.8
1
(1 (1- 3)2 4p(1 + )
II
(1 (1- 8)2 1)2
11 (1- 3)2
$1. (53)
.3
1.8
2(p + 5)
4p(1 + 3)
Cp
13
Cp
/=1
20

---

Published as a conference paper at ICLR 2026
Since each term in the product is less than 1 for 2p + S 4p, the inequality holds. For the induction step, we show:
1 9 pp
p-1
(1 1+ (-
(1-5)² 3 4p + 3)
1,9
1.8
1,8
19
173
Cp B
Cp
TB
j=1
j=1
j=1
(54)
For convenience, we denote 63 for j S pp-1. 1:
(1-8)² 1+B
1. To proceed, we use the following auxiliary inequality
(1+
1+
03
3 jág S e
5j6b 16p
++
(55)
4p
since e0 S 1.25x for x S 1. Combining this inequality with Lemma 9 we obtain:
Optk
1,8
p-1
2 (1-
5j
5
$ 1 -
(1-11
)j.
(56)
Cp" 7B
I.B
16p
16p
j=1
==1
By Lemma 7 we can upper bound:
jrj
(- (- )j - (-rz)i(1 3)
S (1) 8).
(57)
2j 2j-17
Using the known bounds
Srz S Vzj"
we conclude:
Vx(++1)
1.f 9 9ptk
1- 3 VTp
5(1 3)3 p-1
1
1- B
5(1 - B)2
<
51
22/D
Cp' 73
1,
16pV π 1=1 Vj
/Tp
16p
(58)
1- B VTp
(1
<
8 (1 3) <1,
where for the second inequality we used the integral estimate Σ 1/2 S Sot x -1/2dx = 2VK.
Thus, we have shown that I 1 for all k, which completes the proof.
Theorem 4 (BISR Approximation Error). For 1 S S and 1 < k S & the following upper bound holds for the matrix factorizziio error of the BISR Aa, Bº Bap0oa Ca.p (as in Definition 7V:
Jos (Vilogp+
nk + VO
nk lngg
Eplogg b
for a a=
E(B C2.p)
(7)
(a,g(Vik)
for a<l,
where Ga,3 and Og indicate that the hidden constart may depend on and 3, respectively.
Proof. We begin with the case < 1. To analyze this, we first consider the Frobenius norm:
|B
IP
p-1
1
(c
+
Σ (6 06
0g + (cp-1
Σ a
2=0
i=0
(59)
2p
a 3)
log
I 1-
+
a²
(1,
where for the second inequality we used Lemma
11
and for the third inequality Lemma 7 from
Kalinin & Lampert (0244).
For the (k, b-seniiity of the matrix Co full matrix C. (see Lemma For Ca.3, we apply bound from Theorem 7 Kalinin & Lampert (2024), yielding sensk, (Cn,s, 0 (VE), which concludes the case 1.
the fact that it is clement-wiee bounded by the
21

---

Published as a conference paper at ICLR 2026
For 1, we use Lemma
to get:
n-1
(b. 2 Σ (c/10)0
+ Σ
1,8
1
2
2
n
(p-1))
(1- 3)2 ==U
(1- 8)2
p-1
==
i=0
i=p
i=p
n p
= Og logp + n $
$
1 1ogopp+ +
(1 8)2
pg
p
(60)
Next, we bound the sensitivity under k, participation. Using Theorem we obtain:
combined with Lemma
A- 1 k-1
sens & (CP,s)
Σ Σ
(o, (PPp):ss)))
(61)
1=0 1=0
We split the sum into the following four terms:
k-1k-1 min(ptab.nn)
min(p 1.m-1-jb)
Σ
1.9 1.9 ib-ib++
Σ
1.8 1.9
ib+t
O 9jb-ibtt ibtt
S2
k- k- I n- jb
R-1
min(p 1,n-1-ib)
n- 1-
9t
9
Ujb-tben
ibtt
(ce
(c2.833 +
Σ t=p
(gt 19:2
jæ
t=0
Sa
(62)
Step (S) Bound) We note that the case b < p < ni has not been considered Kalinin Lampert (2024) and is technically more challenging. Consider the half of the sum where j > i. The sum requires jb - ib S p 1; otherwise, the upper limit would be negative. We bound the sum as follows:
min(p ib,n) -
14
1.8 1.8
Tjb-ib
1
S
+
1
3
<1 - B)²
Vtib - ib +t)
p- 1+ib-jb
1
1 1
dr
(63)
(1 B)
π
x rriib - ib + x))
1
jb ib
jbb )
1+
f
(1 B)
π
p-
1
(V++1e v!)
where f(a) 2oog
We then use the following auxiliary inequality for the
function f(a):
| (-+1) + 2 log
(1+
1
s log ( (-+1)
f(a) = log
+ 2 log 2.
(64)
Va
This results in the following inequality:
min(p+ib,n (b. 1-jjb
Ct 1b-
1.8 1.8
1
14
2 2 2
log
1 1+1bb ib jb
1 1b-ib5p-1-
(1
3)2
jb ib
(65)
We can now upper bound the double sum:
k-
min(p+hh.))11-11
min(k -oonkkk1,,k 1,
Σ
ct C30-10+
1.9 1.3
2
Σ
3
log
1
(1 (1-3)²
2
jb ib
1=0
t=U
1=0
j=i+1
(66)
22

---

Published as a conference paper at ICLR 2026
The first term gives us:
R- 1 min(k- 1,
2
Σ j=H
5
3k 3)2
p
(67)
(1 3)
2
The second term is more involved. First, we upper bound the upper limit of the sum min - 1, + since the summands are positive, We can then upper bound the expression by:
ly by L
2-1+-12411 ΣΣ
p-1
(5)))
log
log II ==
= k log
(68)
j-i)
(L
(1:5
2=0
1=++1
Using the auxiliary inequality kt y we show that:
(
1
p
p
1
log
log
log
+
(1---))
b
b
(69)
p
p
p
p
log
+
<
b
b
b
b
Resulting in:
k- k- min(m---b.n)n--------
Σ 1=0
Ct
1.9 1.8
1b-
5
(1 B)2
1
3k
p
b
1
π
2 k
p
P-11
b
(70)
4k
p
Σ
(1 - 3)2
b
which concludes this part of the calculations. Step 2 (Bound S2). We can bound the inner sum as follows, assuming that jbb ib 2 p.
min(p- (p- 111-11111--- jbb)
p-1
p-1 2
Σ
4 9fb 9jb-ib++
1.8 1.8
S c
1,9 jb- 79
79
ibttb
c
12,3,,b 16 10
1p
4 7
1,9
t=0
p-1
Tp7 ib-
< 1.8 p
1/
1 10 p
4
1,9
- 3)²
1
(71)
1=0
1b- ib
37 3 bb-ib-p
r
Tp
2/p p
1
B)2
VT
(1 8)2
For our specific choice of 7/3 bound using the following auxiliary inequality:
1
de (1+
where dg
(1-8)² 1+B
We rewrite the
4p+
4p
333 P =
1
Pg
S
0//4
S 1/4
<
4
(72)
4p
This yields the upper bound for the whole sum:
k- min(p 1epippp-1nn11-1 1-n-1-
Ct 950-10+1
1.9 1.9
(1- -)2
8
jb-ib ib 18
(1 - (1
8 h
- 7%))
(73)
8= 3
1=0 j=i+1
We bound 7/ the following way:
7/3 = (1-
6g
b
bdg
bd
S
e
aptay
e
गान S 6 3
(74)
4p
08
23

---

Published as a conference paper at ICLR 2026
Thus,
k- --1k-1 ΣΣ jphi
1.n-1-88)
9 9 10--1+2-
1.8 1.8
5
8k
(1 13)2 (73 1)
(75)
8k
40kp(1 + 3)
bāg 3)2 50 1)
6(1 3)
(1
Step 3 (Bound Sz) We first bound the inner sum, assuming > i:
n-1-j0
1 1.8
(cp (r2.032
t-p jb to+
Dt 9jb-ib+z
3 13
1.8 22, 7
bb-t
(cp
(2 1b-1) (4p Qp)
209
(76)
(4p + 117 1b-ib
3 jb-
1/2
S
20 (1 - B32
20 (1 - B)2
5//3101 jb-ib
jb-bb (1+ 3)
79
S
2T - 3)2
(1-3)-
This yields the upper bound:
2(1 + 33
10kp(1 + B)²
ΣΣ Σ
It
1.9 1.9 1.9
9
(1 3)
Σ
2/3 Go-
6(1 11--9) 3)6
(77)
1=0
analogously to the previous step.
Step 4 (Bound S4) We bound the sum of squared column norms as follows:
min(p-13 1.1fpp-111111))
n-1-1b
(g)
3)2
k
2
(1 3)2
7B
[=0
t=0
(78)
k
5(1 + 3)
log
(1
3)2
2
B)
Step 5 (Combination) Combining all steps together, we bound the k, b sensitivity as follows:
k-1 k-1
senst, (1,33) =
((CT, (.p.,)) (CP,))
0= 1=
k
5(1 + B)
10 p(1 + 3) (
1+8
p p- 1
1 1+logp-
44
+4
(1 8)2
2n
6(1 B)2
(1 - B3}
k(1 8)3
logg + 54 p
(1 8)6
(79)
Thus,
E(BP (BB 22,) < k(1+ (1+ n P) n-P) (2 + logp 54
(80)
(1- 8)8
pa
And
[Vklopp+ +
nk
nk log
kp log p
E(BT CT,5) =0
+
(81)
p
24

---

Published as a conference paper at ICLR 2026
Lemma 3 (Optimal Band Inversion Error). Let the matrix C = LTT(1, -X,0....,0) be lower triangular Toeplitz matrix with 1 on the main diagonal and -À on the subdiagonal. Then, for a single participation and the prefix sum matrix A 1,0, the following bound on the matrix factorization error
holds:
inf 8(A1,0 CC)) -4(n!/4)
(10)
AE(0.1)
Proof. If the matrix T is given by LTT(1, -X,0, ........,0 0), then its inverse is Cx
L1 X, A The product A = LTT(1, 1 X, A...... 1 - A), which leads to the following error:
, 1 (1+(1- (1-11 (1-)))) 1))
n-1
12x (1+ (1 2)2 1)) 22m) (82)
Σ
n
n21 A2)
k=0
Therefore.
(2- b) 1- 1- (1- vn
1
2
inf E(A1,0 ,C,)
(83)
AE(0,1)
vn
vn'
when A = V1- Va
as
A
5 (1
= -.
v
The bound follows.
25

---

Published as a conference paper at ICLR 2026
testire 255
90
Eastone 5204
Feodumn 2000 20304
RANER
56
15
Staps
Stops
Steps
(8)
4, 0 1, 8 0
(b) 1:
4,
3 0.9
(c) k
4, CK 0.999, ==:
202-
fentior 15544
fertiore 55344
255
140
3924
14
2alalii 16304
178-
(d) k 16, 1,
(0) k
16, O
1, 0.9
(1) 1: 16, 0.999, B
Figure 6: Convergence Band-Iny-MF under different settings: for participation numbers 4, 16, with and without momentum (3) and weight decay (a). across various matrix sizes (iterations). In general, we observe that 20 steps are sufficient for the procedure to converge.
Table 1: Hyperparameters for CIFAR-10 Experiments. We train all methods with and without amplification to achieve (9, 10- ---f--iiifrrential privacy. Training uses a weight decay of 0.9999, momentum of 0.9, and batch size 512. Noise multipliers computed via an MCMC accountant for the amplified case, and as o.s x sensk,6()) for the non-amplified case, assuming 10 training epochs.
Method
Noise Multiplier
Learning Rate
bandwidth
Clip Norm
DP-SGD
1.2
0.1
1
10
BSR
2.3
0.3
4
Amplified
BISR
4.4
0.7
4
10
Band-MF
2.4
0.3
4
Band-Inv-NN
8.2
0.4
4
10
DP-SGD
1.8
0.1
1
10
BSR
3.3
0.2
4
10
Non-amplified
BISR
5.8
0.7
4
10
Band-MF
3.5
0.2
4
10
Band-Inv-Mi
9.1
0.5
4
B ADDITIONAL MATERIALS
Table 2: CIFAR-10 experiments with and without amplification, for = 9,, 8 = 10 accuracy (%) over epochs. Mean + standard error computed over runs.
showing test
Method
Epoch
Epoch
Epoch
Epoch 4
Epuch
Epech
Epuch
Epoch
Epech 9
Epoch
De-SCID
42.3
Amp.
BISK
42.7 1.1
47.5
579
085
685
Ranl-F
38.
43.1
468
500+
Band Im- MIF
34.6 1..
40.0
16
48.
1.0
506105
$3.108
562
57.4
DP-SCD
10.5
31.0
36. 02
372+04
17.
30
303+12
30++03
300+07
BSR
25.4+12
36.7 +2
403
416+20
43.6
436
4
25.000 09
444+11
45--18
4 85
Non-Amp
BISR
1.
41.7 122
454
13
51.1110 10
2.
538 100
540
385-08
S62
022
Band MF
25.9
36,7 0.09
41.1
13
428 1.4
022
25
45
46
453
02
Rand-In-MF
27.4+ 4.3
+6.0
395+ 24
43
467 167+00
47.0 2.0
497+13 1.7
535+05
544-15
579++0 04
26

---

Published as a conference paper at ICLR 2026
Table Hyperparameters for IMDB Sentiment Analysis Experiments with BERT-base. We train all methods with and without amplification to achieve (9, 10 (9,10-") -diffferrett privacy. Training uses weight decay of 0.99999, momentum of 0.95, and batch size 512. Noise multipliers are computed via MCMC accountant for the amplified case, and as o,, x SenSE,b(C) for the non-amplified case, assuming 10 training epochs.
Method
Noise Multiplier Learning Rate Bandwidth Clip Norm
DP-SGD
1.2
0.02
BSR
2.3
0.02
4
10
Amplified
BISR
4.4
0.15
4
10
Band-MF
2.4
0.02
4
10
Band-Inv-Ma
8.2
0.1
4
10
DP-SGD
1.8
0.02
1
10
BSR
3.3
0.02
4
Non-amplified
BISR
5.8
0.15
4
10
Band-MF
3.5
0.02
4
10
Band-Inv-MP
9.1
0.1
4
10
Table 4: IMDB sentiment analysis (BERT-base) with and without amplification, for 9, 10-5 showing test accuracy (%) over 10 epochs. Mean + standard error computed over 3 runs.
Riucc
Pirch
Epuch
Fpoch
Fporh
DP-SCD
71.23
0.29
$2.42
0.544
$4.45 a 0.21
55.57
0.1.9
$6.18
0.05
$6.54 0.03
36.95 a: 0.03
$5.59
0.14
87.26 0.35
$7.43 0.12
BSR
75
7.67
50.40
1:25
16.1
- 0.29
56.90
1:111
$7.40
1:13
$7.17 à 1.07
17.82 - 0.00
87:01
0.15
=1.10-0000 0.14
88.11 --066
Anp.
BISR
23.27 0.21
07.08 0.05
88.16 = 0.09
58.83 0.00
30.20 2: 0.6
89.21
: 0.00
39:49
0.03
89:4
1:111
2..00:00000
89.55 0
0.19
DP-SCD
62.04
78.21 1.3.6
$3.05 0.11
$..37
$5.01 0.06
85.40:20.33
8:.5
35.50:1..15
83.71 0:29
USR
70:74 00:74:11 1:11
1144
10 0.0
15.00-1111 0:33
50.90 1:36
16.91 mm
67.15
(7:00--011
87.19 0.09
0.11
87.1 0.10
Non-Ang
BISH
67
08.0 1:00
mm
89:00
0:07
89
89 -015
27

---

Published as a conference paper at ICLR 2026
import privacy
From jax privacy seeaacy.aatee maxtrix factorization import toeplitz import pax.numpy as jnp
import functcols
import numpy as np
def expected mean wrror n, k, workload_coes -> flost:
inv_cces = jnp. pad (0, inv_coef.size))
B_norm_squared toeplitz.mean error www.rriiiiinoooo--iiioooooomm n worzLoaLLcoof-ootLoodddooo ekip_chscke-Truc)
10
11
coef - tceplite. weeplltt..iveeee......m inveinneeeeeeeeee (inv_ccnco
12
min_sep // k assume divisible
14
sensitivity_squaatttt squared toeplitz. min_sep, sep, k, n, sxip_checks-Trug
return sensitivity_squared B_nore_squared
17
18
def
(x, n) -> np.ndarray:
19
= np. zp.zeros(n) (n)
y[o] = np. sp.ttrt (x[0))
for in range(1, n):
22
y[k] (xlk] -np. (y[1:k), (1::k] (2 y(o)) return y
23
24
def init (n, P. alpha 1.0, beta 0.0) -> jnp.ndarray: jrp.array([1, -alpha beta, alpha beta] + [0]*(n-3)
27
return jnp.array
(x, n) [:p]]
28
def Band Inv MF (n, b, k, alpha, beta, steps = 20)
compute workload matrix
31
jnp. (alpha (k + 1) beta (k 1)) (bets alpha) for k in range
32
initialize with BISR coefficients C_inv_init init (n, P, alpha, beta)
35
36
# optimize!
37
C inv__ppt
n=n,
39
bands=p,
40
strategy_coeff<cinn__i
41
loss_fn-functoolls partttt paltial (exnected_enneeror,, k-k, workload_coef-nt
max.opsimzer_ssepsstter
45
44
return C_inv_opt
Listing 1: Python code for Band-Iny-MF factorization. The function Leand_Inv_aee takes the matrix size (n), the minimum separation (b), the number of participations (k), the bandwidth (p), the weight decay (a), the momentum (5), and the number of optimization steps.
28


Reviews:
[{"review_id": "6oVXv8gIbB", "reviewer": "Reviewer_7NNd", "summary": "This paper introduces and analyzes a novel matrix factorization scheme, called BISR, which can be applie to DP-SGD and relies on (i) computing the inverse square root of the workload's matrix, (ii) imposing a band structure on it, and (iii) inverting the resulting matrix again.\nA novel lower bound on factorization error for SGD's workload matrix is derived, with matching upper bound for the BISR method, which relies on band structure of the inverse square root.\nNumerical experiments show that the resulting factorizations are consistently on par than the existing BSR mechanism, and strongly outperform it for some choices of bandwidth.", "questions": "1. Is it possible to derive theoretical convergence guarantees for DP-SGD in simple settings (e.g., strongly-convex functions)? In this setting, is there a chance to observe the true metrics on matrix factorization approximation that impact the final privacy-utility trade-off?\n2. Authors claim that the RMSE may not be a good proxy for approximation error. Are there other candidates for better proxies?\n3. Experiments showcase the low privacy regime: how would the result change in a high privacy regime? Would BISR still be better? Would the difference increase/decrease?\n4. What is the intuition why the inverse square root should be closer to a band structure than the square root itself?", "limitations": "", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The proposed method, relying on imposing structure on the inverse of SGD's workload matrix squared root, is original and very different from existing ideas.\n2. A refined theoretical lower bound on the factorization of SGD's workload matrix is provided.\n3. The BISR method is shown to match this upper bound.\n4. BISR is shown numerically to provide better factorization in many setting that existing methods, and this improved factorization precision results in improved accuracy over existing method in multiple private machine learning tasks.\n5. The paper is very well written and easy to read.", "weaknesses": "The paper is very interesting, and I mostly remark strengths about the contributions. Nonetheless, there are some minor weaknessses:\n1. No theoretical guarantees for DP-SGD under the BISR matrix factorization are provided.\n2. While the theoretical claims hint for a large improvement over the BSR method, this does not always show in practice; studying more precisely (i.e., non-asymptotically) the respective behaviour of the two methods may reveal more subtle compromises.\n3. The experiments on CIFAR-10 and IMDB are performed in the small bandwidth and low privacy regime: it is not clear whether the same conclusions would hold in high-privacy/large bandwidth regimes.", "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": "KopaipFk6e", "reviewer": "Reviewer_53th", "summary": "The paper investigates the matrix factorization mechanism for differentially private stochastic gradient descent (DP-SGD) under multi-epoch/multi-participation settings.\nThe matrix factorization mechanism is used to inject correlated noise into gradients during training by means of a correlation matrix.\nThe authors propose to enforce a banded structure on the _inverse_ of the correlation matrix, to derive explicit upper bounds on factorization errors and to prove asymptotic optimality.\nThe authors compare their approach with existing techniques, showing that their proposed approach achieves higher or comparable accuracy for large matrices.\nMoreover, the paper proposes an efficient, low-memory method which matches the performance of state-of-the-art approaches while being more efficient.", "questions": "* How practically (or theoretically) relevant is your approach for stricter privacy regimes, i.e., small values of $\\epsilon$?\n* What is the standard deviation/variability of the results reported in Figure 1/2? Are the results significantly different if you include error bands in the plots/results?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* **Theoretical contribution.**\nThe paper introduces and discusses a matrix factorization technique with provable optimality, and refines prior existing bound (Kalinin and Lampert, 2024).\nUnlike related work, you provide an explicit dependence on the bandwidth $p$ and on the participation $b$, which leads to more useful guarantees.\nThe idea to consider the inverse correlation matrix instead of the matrix itself is, as far as I can tell, novel and elegant.\nMoreover, the discussion on an efficient implementation reinforces the practical utility of your approach.\nThe problem discussed is very relevant and well placed within related literature.\n\n* **Empirical validation.**\nThe empirical validation you present is limited but consistent, and qualitatively supports your claims.\nIn particular in low-resource regimes, the presented approach performs better than existing ones.", "weaknesses": "* **Clarity and accessibility.** The paper has dense notation and long proofs: intuition could be introduced earlier.\nFor instance, the benefits of inverse banding are not intuitively clear, and visualizations could help here.\n\n* **Low privacy regime.**\nIn your empirical evaluation, you only present results in a arguably low privacy regime $\\epsilon=9$.\nWhile this specific value for the privacy budget seems to be common in related literature, it is generally understood to be at the edge of what is considered to be differentially private at all.\nIf my understanding is correct, the benefits of one specific factorization technique against another, is particularly important when the amount of noise added is small.\nWhile this justifies the chosen privacy regime, it may diminish the contribution for more strict, and therefore relevant from a privacy perspective, privacy regimes ($\\epsilon <= 1$) where DP constraints are more meaningful.\n\n* **Empirical relevance.**\nFollowing from my previous point, I am not convinced of the practical relevance of the approach.\nWhile I understand that your contribution is, first of all, theoretical, a comparison with more recent DP-SGD variants would further justify its practical relevance.\nThe plots do not show any measure of dispersion (e.g., error bars).\nThe empirical setup does not seem to reflect a real-world application with realistic privacy requirements, and no investigation of the effectiveness of the approach with different privacy budgets is performed.\nFrom the plots, the correspondence between RMSE and accuracy is difficult to grasp.\n\n### Other remarks\n\n* The nomenclature is at times confusing.\nBoth $C$ and $C^{-1}$ are referred to as \"correlation matrix\" throughout the introduction (e.g., compare lines 45 and 59/61).", "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": "lGxMLMSvZw", "reviewer": "Reviewer_2RDV", "summary": "This paper presents a new algorithm banded inverse square root (BISR), which is an extension to BSR from (Kalinin & Lampert 2024) by imposing a banded structure on the inverse matrix $C^{-1}$ rather than $C$ itself.\n\nBy making such modification, the authors are allowed to give a more explicit expression error with respect to the bandwidth $p$ and reduce the overall computational complexity. The authors also show a tight error bound on the approximation error with matching lower bounds.", "questions": "Questions are included in the \"Weaknesses\" section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find the idea of bounding the bandwidth of matrix on matrix $C$ to reduce computational complexity interesting and the optimal error bound a solid contribution. Also, I appreciate the authors' efforts make to make a comprehensive discussion and comparison with prior work.", "weaknesses": "1. The algorithmic modification are relatively minimal. The general structure of the algorithm directly follow that in (Kalinin & Lampert 2024) which slightly weaken the contribution of this work.\n2. More discussion is needed on the approximation error defined in equation (1) . In particular, how is this error related to the convergence error? Would achieving an optimal bound on this error also imply an optimal convergence rate? It would be great if the authors can provide explicit convergence rates for certain loss function classes (e.g., convex-Lipschitz loss) and make comparisons with existing DP algorithms like DP-SGD.\n3. The algorithm, claimed as computational efficient, may not be suitable for modern model training. To achieve optimal rate, $p$ needs to be set as $\\tilde{O}(b)$ where $b$, as far as I understand, can be approximated as the number of update steps per epoch. In large-scale training, this number can reach tens of thousands or even millions. Therefore, combining $p$ different $Z_i$'s in each update step could become prohibitively expensive in practice.", "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": "CLNPulQq0O", "reviewer": "Reviewer_xJi2", "summary": "This paper addresses the problem of adding correlated noise to elements in a data stream with a momentum structure in a differentially private manner under continuous observation, while maintaining low approximation error. The authors propose a novel factorization mechanism for injecting correlated noise at each iteration, providing formal differential privacy guarantees even against an adversary with access to all entries of the stream.\n\nTheir approach improves upon existing methods by factorizing the workload matrix, extending the square-root factorization framework studied in prior work. This refined factorization yields tighter approximation error bounds. Furthermore, the authors establish matching lower bounds on the achievable approximation error for general classes of stream structures, demonstrating the optimality of their approach.\n\nThe proposed mechanism has clear practical relevance, particularly for differentially private stochastic gradient descent (DP-SGD) with momentum. It enables more efficient and accurate private training of deep learning models, highlighting the work’s potential impact on privacy-preserving machine learning.", "questions": "Please see weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "This paper is very strong in terms of results:\n1. The paper presents rigorous theoretical results based on novel techniques that effectively close a significant gap in the existing literature on matrix factorization mechanisms within the context of streaming differential privacy covering a large variety of tasks.\n\n2. The paper synthesizes concepts from several related domains to develop a generalized formulation of DP-SGD with momentum, extending beyond existing approaches in the literature.\n\n3. The paper proposes a computationally efficient method to compute correlated noises. It provides a practical technique to implement these correlated noise techniques for settings which are not simple SGD and attempt to break into the practical scenario in existing optimization techniques used for differentially private deep learning.\n\n4. Practically the algorithm performs very well compared to existing matrix factorization methods for DP-SGD on classification datasets.", "weaknesses": "The main weakness of this paper lies in its presentation. While the technical results appear sound and potentially impactful, the exposition makes it difficult for readers to fully grasp the scope and implications of the work (especially from the lower bound perspective). Below are some specific comments and suggestions:\n1. *Dependence on Prior Work for Context*: The paper relies heavily on Kalinin & Lampert (2024) to set up the background for its lower bound results. For instance, the “multi-participation setting” introduced in Theorem 3 is not defined anywhere in the paper and an appropriate reference has not been given as well, which makes it hard to understand the exact conditions under which the stated bounds apply.\n\n*Suggestion*: It would be helpful if the authors could briefly explain or restate the definition of the multi-participation setting, even if it was introduced in prior work. A short contextual description would make the paper more self-contained and easier to follow.\n\n2. *Ambiguity in Notation*: Some notations are not clearly introduced. In particular, the terms $\\Omega_\\alpha$ and $\\Omega_{\\alpha, \\beta}$ in Theorem 3, along with their Big-O counterparts in Theorem 4 and Corollary 1, are not defined.\n\n*Suggestion*: Please clarify the meaning of these notations, either directly in the text or in a concise notation table.\n\nIncluding short background explanations—perhaps in an appendix if not in the main text—would greatly improve the paper’s readability. While it is understandable that some results depend on established frameworks, providing minimal context would help readers appreciate the contributions without needing to refer extensively to other works.", "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)