Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy
Authors: Anastasia Koloskova
Ryan McKenna
Zachary Charles
J Keith Rush
Hugh Brendan McMahan
Venue: NeurIPS 2023 poster (2023)
Keywords: optimization
machine learning
differential privacy
TL;DR: We study the convergence of gradient descent with linearly correlated noise, and use our insights to design improved methods for differentially private optimization.

Abstract: We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise *linearly correlated* over iterations. We propose a simplified setting that distills key facets of these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multiple important special cases exactly (including anticorrelated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically.

Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy
Anastasia Koloskova' EPFL, Switzerland
Ryan McKenna Google Research
Zachary Charles Google Research
Keith Rush Google Research
Brendan McMahan
Google Research
Abstract
We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such DP-FTRL, which achieve strong performance in settings where privacy amplifica- tion techniques are infcasible (such in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise linearly correlated over iterations. We propose simplified setting that distills key facets these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multi- ple important special cases exactly (including anti-correlated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically.
Introduction
Differential privacy (DP) is critical framework for designing algorithms with provable statistical privacy guarantees. DP stochastic gradient descent (DP-SGD, Abadi et al. ( is particularly important for enabling private empirical risk minimization (ERM) of machine learning models. Many works have analyzed the convergence behavior of DP ERM methods, including DP-SGD (5]
16 48 8).
However, obtaining good privacy/utility trade-off's with DP-SGD can require excessively large batch
sizes or privacy amplification techniques such as subsampling 4 S 55 and shuffling [15 16 In some applications, including cross-devics federated learning, limited and device-controlled client availability can make sampling or shuffling infeasible [21] Even outside of such applications, many implementations DP-SGD do not properly use the Poisson subsampling scheme analyzed by Abadi
et al. I for amplification, and instead use single fixed permutation of the dataset 77)
Kairouz et al. (20) propose alternative method, DP-FTRI, which attain good privacy/utility trade-offss without amplification. Their key insight is that for SGD-style algorithms, the variance on prefix sums go
gi, {L....,27 . of gradients g, more important than the variance on individual gradients. By adding carefully tailored noise that is linearly correlated over iterations to the gradients, one can reduce the error on the prefix sums, at the cost of increased error on the individual gradients, for fixed privacy budget. The DP-FTRL mechanism is competitive with or better than SGD,GD, even without relying on privacy amplification, and enabled McMahan and Thakurta [3] to train the first differentially private machine learning model on user data in a production setting.
Work performed while doing internship at Google Research. Correspondence to: Anastasia Koloskova aunasassia.oloskovee @ @eptl.eh>..........e Ryan McKenna <mekennar @ google.com>.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Input: T workload matrix A, factorization objective obj
Input: model X, gradients G, IID Gaussian noise
C
minimize obj
A
B
first-order optimization steps additive, linearly correlated noise
Offline, one-lime
Data- and loss-dependent empirical risk minimization
matrix factorization
Figure 1: Two-stage MF-DP-FTRI. workflow proposed by Denisov et al. 10] The user selects workload matrix representing desired first-order optimization method. Offline, the user finds factorization BC A, using objective that balances ERM performance (as function of B) and privacy (as a function of C). The user applies to a downstream ERM task, but with linearly correlated additive noise governed by B.
Denisov et al. 10 Choquette- Choo et al. 7 develop refinement of DP-FTRL, MF-DP-FTRL. by formulating and solving an offline matrix factorization problem to find the "optimal" correlated noise structure under DP constraints. That is, for fixed privacy level, they aim to find correlated noise structures that lead to improved optimization. in Fig. [ However, (as we detail in Section 2 their offline factorization objective is based online convergence bound that is loose. This raises questions about whether there are factorization objectives that better capture convergence behavior of gradient descent algorithms with correlated noise.
simplified diagram of their workflow given
In this paper we study this class of mechanisms more closely and provide a detailed analysis of linearly correlated noise from an optimization point of view. Our main contributions are as follows:
We propose novel stochastic optimization problem that extracts key facets of methods like (MF-)DP-FTRLL, and which isolates the effects of linearly correlated noise on optimization.
We derive convergence rates for gradient descent on smooth convex and non-convex func- tions in such settings that showcase the effect of linearly correlated noise and recover tight convergence rates in notable special cases. We use a novel proof technique that may be of independent interest.
We use this theory to design new objective for the offline matrix factorization workflow in Fig. I We show that solving this objective leads to MF-DP-FTRL mechanisms with improved convergence properties. We validate the mechanism empirically on variety of datasets and tasks, matching or outperforming prior methods.
1.1 Related Work
Matrix mechanisms for differential privacy. Our work is closely related to differentially private optimization using matrix mechanisms (26). Historically, such mechanisms were applied to linear statistical queries 23 29 14 [8]. Denisov et al. [10] and Choquette- Chho et al. 7 extended these mechanisms to the adaptive streaming setting, allowing their application to optimization with DP. Denisov et al. [10] show that this framework (MF-DP-FTRL) subsumes and improves the DP-FTRL algorithm (20]- Both DP-FTRL and MF-DP-FTRL. improve privacy guarantees relative to DP- SGD I without amplification, and be combined with techniques such as momentum for improved utility [46]. The aforementioned work focuses on methods for computing factorizations, privacy properties, and empirics. Our work studies the analytic relationship between the correlated noise induced by the MF-DP-FTRL. framework and the downstream effect on optimization performance.
SGD with correlated noise. Stochastic noise in optimization arises in a variety of ways, including mini-batching 99 and explicit noise injection [1] noise independent across iterates, some work considers correlated noise. For example, shuffle SGD involves correlated noise due to sampling without replacement
54 19 While most analyses of SGD assume this
33 53
Lucchi et al. [27

---

use correlated Brownian motion to improve SGD's ability to explore the loss landscape. Recently, Orvieto et al. 37 investigated anti-correlated noise as way to impose regularization and improve generalization. We consider linearly correlated noise model, and analyze its impact on SGD's convergence to critical points.
SGD with biased noise. Many algorithms can be viewed as SGD with structured but potentially biased noise, including SGD with (biased) compression 44 delayed SGD 28 local
SGD [2], federated learning methods [22 52 (3, (36], decentralized optimization methods [50] (23
and many others. Convergence analyses for such methods often use techniques like perturbed iterate
analysis (28). Correlated gradient noise also biases the gradient updates. However, as we show
in Section directly applying such techniques to linearly correlated noise does not lead to tight
convergence guarantees.
2 Background
In this work, we focus on an empirical risk minimization (ERM) problem of the form
f(x) = ! Σ 1(x, Ex)
min XER
where ((x, {.) is the loss of model on a data point ε,, and n is the training set size. We would like to solve (I) while guaranteeing some form of privacy for the training set. We focus on differential privacy (DP, [33), a widely-used standard for anonymous data release. DP guarantees statistical difficulty in distinguishing whether or not particular unit's data served as an input to given algorithm, based on the algorithm's 's output. This protected unit may represent single training example or semantically higher-level unit like the entirety of a user's s data.
While there many methods for solving ①. will follow Denisov et al. 10], Choquette-Chov et al. 7 and restrict to first-order algorithms 2 that linearly combine (stochastic) gradients. Each algorithm A 2 is parameterized by learning rate 7 > number of steps T 0, and scalars {arg hershssssss Given a starting point Xg, A produces iterates X2 E R2d given by
X++1 = Xg - AA.g
Σラ 0zj8,
where ge is a batni) gradient of computed at x,. This class encompasses a variety of first- order algorithms, including SGD [40]. SGD with momentum (35), and delayed SGD [2). This class also captures algorithms that use learning rate scheduling, so long as the schedule is independent of the gradient values. We re-write the output of A in matrix notation by defining:
X = Xx....
XT]
E
Txx
Xo = [Xo........................ Xo]
E IR Txd
G g .
gTl
T
E Txd
A [ashsisr E TXT
Here A is the workload matrix representing A. At iteration I, A can only use the current and previous gradients, so atj = for j (ie. A lower-trianuular. In this notation, the iterates of A satisfy
X= X. - AAG
(2)
Example 2.1 (SGD). Define the prefix-sum matrix S E RTxT as the all-ones lower-triangular matrix. If A S, then (2) is simply SGD with learning rate y. As discussed by Denisov et al. [10] Section 4]. we also recover SGD with momentum using an appropriate transformation S' of
2.1 Matrix Factorization and Privacy Mechanisms
In order to make the output of (2) differentially private, we typically need to clip the gradients and add noise. Let G denote the matrix whose rows (gradients) have been clipped to some & threshold a. Let Z Txx be matrix with entries drawn independently from (0, 5²/4). The well-known DP-SGD algorithm [ adds this noise to each clipped gradient, so that
X X, A(G Z))
For consistency, we consider (2) to be the special case of (3) where and a = co. The variance 2 depends on the clipping threshold and desired (s, 8) privacy we aim achieve [l]
3

---

To derive algorithms with improved DP guarantees. Denisov et al. [TO] add the noise Z to factorized version of A. For factorization BC with B, C R TxT, we add noise the iterates via:
X = X - B (CG sens (C) Xn Y (AG sens(C))B)
Here, sens( C) is number representing the sensitivity of the mapping G + CG to "adjacent" input changes. We note that the sensitivity changes depending on the notion of adjacency. In single-epoch settings, two input matrices are adjacent if they differ by single row [10]. so the sensitivity function sens C) = m [Cr,ill2z i.e. the maximum f2-squared column norm of C. For details and extensions to multiple epochs, see [7].
If the variance of entries of Z is fixed to some value <2/d, then for all the possible factorizations A = BC in 44) have exactly same privacy guarantees, depending only on Ç. It will also be convenient define
sens( sens(C)( the "effective" variance Z after re-scaling by the sensitivity. Note that for a fixed o, the privacy guarantees of might be different depending on the sensitivity.
The factorization B A, C I recovers DP-SGD (3), but factorizations with better privacy-utility trade-offs may exist. The formulation of Eq. 4 transfers the linear optimization algorithm 2 into the setting of the matrix mechanism [26]. well-studied family of mechanisms in differential privacy. Denisov et al. [0O], Choquette- Proquette-Choo et al. [7] show that the mechanism in Eq. 44) provides DP guarantee equivalent to single application of the Gaussian mechanism, which can be computed
tightly using numerical accounting techniques 49 24
Finding good factorizations. Intuitively, a factorization A BC is good if sens(C) is small and the added noise BZ does not significantly degrade the convergence of (4). In order to quantify the effect of this added correlated noise on optimization, Denisov et al. [1O] derive an online regret bound for 4 in the convex case against adaptive adversary. Translating this via online-to-bard convergence the stochastic setting, the iterates x; satisfy
T Σ T+1 1=0
No
11 I
sens C) |BI
- f1 -1
+ +yI² + I
(5)
VT
where ī. is the Lipshitz constant of f. Denisov al. [10] therefore sens (C) |B| proxy for the impact of the factorized noise scheme on convergence. To find factorizations with good convergence properties, Denisov et al. (10), Choquette-Choo et al. 7 minimize sens(C) | subject to the constraint A = BC, which is equivalent to the following objective:
Problem 2.2 (Minimal-None define OPT ( = (B, C), where B, C E gx'T solve the following optimization problem.
Matrix Factorization). Given lower triangular matrix A T
min
B p B.C
such that BC A, sens C)= 1.
(6)
Eq. 6 is well-studied in the privacy literature and can be solved with a variety of numerical optimization algorithms [51 30 10 7. We also note that Denisov al. [T0 show that without loss of generality, we can assume and C are lower triangular.
Finding improved f'actorizations. We argue that (5) is pessimistic in stochastic settings. For SGD (when B A), the last term in (5) is O(7 sens C)CLVT), which diverges with T for constant stepsize. However, under the same assumptions as in [0]. SGD with constant stepsize actually achieves a faster rate of sensssesss) C) (see (41).
In this paper, turn our attention to the smooth functioos in order to focus non-convex functions. We show in Appendix A there are matrices B,, B, such that sens( [ | p = scns( (C2) [By rs but Eq. (4) diverges with B, and converges with Bg, therefore showing that Frobenius norm is not the right measure in the smooth case as well.
This begs the question of whether there are objectives that better capture the impact of the noise injected (4) on convergence. To answer this, we derive bound that can exhibit better dependence on B to design better factorizations for differentially private optimization.

---

3 Problem Formulation
To study the effect of the noise BZ on optimization, we analyze a slightly simplified objective that omits parts of 44 not directly related to linear noise correlation. We do this as follows:
(I) We assume that each g is the gradient the point X,, i.e. g: Vx())).
(II) We omit gradient clipping from our analysis. Alternatively, we can view this as setting the clipping threshold a do so that G = G in 4
(III) We restrict the class A to SGD-type algorithms where S, as in Example 2.1
We impose (I) for simplicity of presentation. Our results can be extended to stochastic gradients in direct fashion. Restriction (II) is also for simplicity. First, clipping not directly applied the noise BZ. Second, for bounded domains or Lipschitz f. our analysis still holds with clipping. Last, practical DP methods often use adaptive clipping [45] instead of fixed clipping. We are not aware of convergence analyses for such schemes. We impose (III) in order to limit the class of algorithms A to a wellstundrstood subclass. The convergence properties of (2) for general matrices A are not well-understood even when there is no noise (Z 0). As we discuss in Section even with these simplifications, the effect of BZ is not well-understood.
Due to (III), we study factorizations BC of the matrix A S, as in Example 2.1 Then, becomes
X X (SG + sens C))Z).
In vector notation, for by 0 and [b.....by! brl".
X X fxxx) (b++1 b,) bz)
where for simplicity of presentation, re-scaled the noise Z by the sensitivity, o² sens" (C) now discuss several noteworthy special cases (8).
Example 3.1 (PGD). If S (see Example 2.1 recover SGD with uncorrelated additive noise, also known as perturbed gradient descent (PGD), where
X++1 =
fx, + z+11l.
The convergence rate of SGD (and therefore PGD) is well-understood in the optimization literature (e.g. see Bubeck (6. Section 6)).
Example 3.2 (Anti-PGD). By setting B I, get algorithm that at every iteration adds an independent noise vector zi+1 and subtracts the previously added noise z,:
X (xx)), + Z++1 - -zz], = 0
(10)
Intuitively, this removes factor) the anti-correlated perturbed gradient descent (Anti-PGD) method proposed by Orvieto et al. (37, who study its generalization properties. Anti-PGD is also equivalent to SGD with randomized-smoothing [1I] The equivalence follows from defining X, = Xt + 72, and rewriting (10)
of the noise added in the prior round. This is (up learning rate
ă x, >V/(x - yzz))
While randomized smoothing algorithm is popular for non-smooth optimization, Vardhan and Stich 47 analyze its convergence properties in the smooth non-convex setting.
Example 3.3 (Tree Aggregation DP-FTRL). For l 2 and = 2 define HІ E (22=-1)x recursively as follows:
H 0
0
H =1),,, Het1
where 1 above represents an all-ones row of appropriate width. For T'
H2 and B SC where C/. denotes carefully chosen right pseudo-inverse of C, then we recover same noise matrix B as in the DP-FTRL algorithm with either the online or full Honaker estimator (depending on the choice of Cf) as in 20 10). Note that B, C are not square. This can be remedied by appropriately projecting onto T See Choquette-Choo et al. [7] Appendix D.3] for details.
5

---

Deriving Tighter Convergence Rates
We would like convergence rates for 7 that apply to any factorization and yield tight convergence rates for notable special cases. We pay special attention to PGD (Example and Anti-PGD (Exam- ple 3.2 as they represent extremes in the space of factorizations (S SI and IS, respectively). As we will show, it is possible to use existing theoretical tools to derive tight convergence rates for both, but not simulhaneously.
Below, we discuss ways to derive tight rates for PGD and Anti-PGD, and how these rates involve incompatible analyses. We then develop novel analytic framework involving restart iterates that allows us to analyze both methods simultaneously, as well as (7) for general factorizations. We start by formally stating our assumptions. For simplicity of presentation, we re-scale the noise Z by the sensitivity of C, i.c. o² = sens" " (C){?; we will suppress the C dependence of a.
Assumption 4.1 (Noise). The rows : 2r of the noise matrix Z are independent random vectors such that Vt, Elz]] and || 0².
We do not assume L-Lipshitzness in our results, but we do assume L-smoothness. This a relatively standard assumption in optimization literature [6].
Assumption 4.2 (L-smoothness). The function f R - is differentiable, and there exists > 0 such that for all 2, y IRd, ||V [xx)
S /
||x y/|.
For some the results we will assume convexity.
Assumption 4.3 (Convexity). The function f IR + convex, i.e. Vx, E (84,((x) - -f(y)= s (x)()), yy- When assuming convexity, also assume the infimum of f is achieved in Rd.
4.1 Convergence Rates for PGD and Anti-PGD
In this section we discuss the (distinct) convergence analyses of PGD and Anti-PGD,, and the suboptimal results derived by trying to apply the proof technique for one to the other. We focus on the convex setting for brevity, though these analyses can be directly extended to the non-convex setting.
PGD.
The convergence of PGD (Example 3.1 is well-understood since it is a special case of SGD. One can show the following.
Proposition 4.4 (Adapted from Dekel et al. 9 Theorem 1]). Under Assumptions 4.1 and 4.3
B and 7 < 1/2L, then the output of satisfies
Σ
E f*] T+1
so
[xo
x+12 TT
y022
(11)
The proof follows from combining the update (9) standard facts about convex functions, and the fact that 7 < 1/2L, get the inequality
E, | x=1 < |xx - x=1 - - +
is left to average over iterations 0 STST.
Anti-PGD. For Anti-PGD (Example
3.2 one show the following.
Proposition 4.5. Under Assumptions 4.1 satisfies
4.2
and 4.3 B = I and y < 1/21, then the output of 7
E [x)( Σ
f*1 O
||xo
x
LY20²
(12)
T+1
TT
Since Try < 3/2, the RHS of 12 is strictly smaller than the RHS of [T.. While this result may be known, were unable to find reference, provide complete proof in Appendix D The proof utilizes perturbed iterate analysis (28). We define a virtual sequence {x: as follows:
x x+1 X vx(x).
X0 = X0
(13)

---

The X2 are the iterates of 7 when Z = 0. We can then prove the following descent inequality:
| - x < [ x'
(f(x.) f*) + 2 | - x, ||
Because of the anti-correlation in (T) the virtual iterates x are close to the real iterates Xt, as X₁ & = 724 Averaging over 1, we recover
See Appendix D for details.
Tightness. The noise terms (those terms involving o²) in Appendix E on the objective f(x) = (4/2) ||x]
12 are both tight. We show this in
Difficulties in unified analysis. The proof techniques for PGD and Anti-PGD above are notably different, and as we explain Appendix F do not lead to favorable results when trying to use one of the strategies to analyze both.
4.2 Main Results and Analytic Techniques
To unify the proof techniques above, we use modified virtual sequence with restart iterations. For parameter т = (1/(n)) (throughout, Ö and é hide poly-logari factors), we define
x++1 x; fx,)))
if t + + mod т if t ++1= = 0 mod T.
(14)
x++ = X;+1
Similar to the virtual sequence in [33 X, incorporates only deterministic gradients V fx,).. However, every T iterations we reset &; to the real iterate x,. This allows us to control the divergence between the virtual sequence and the real sequence (enabling a tight analysis of PGD), while still capturing the convergence benefits of anti-correlated noise (enabling a tight analysis of Anti-PGD).
The parameter is independent of B, and depends only on the geometry of and the stepsize Using this machinery, we can prove convergence rates of (7) for any factorization $ BC. These rates involve & distances between the rows b, of the matrix B (where by 0 for convenience).
Theorem 4.6 (non-convex). Suppose Assumptions 4. and 4.2 hold, y S 1/4L, and 1/72. Then I1 is upper bounded by
produces iterates whose average error (T +
E
V (xx)))
1=
(f (f(x)) T
σ² X
||b, - -b--rl? 1): IKST t= mod
T I
1
b, - 11
b
+ Σ
TT
Theorem 4.7 (convex), Under Assumptions 4.1
4.2 and 4.3
if S 1/4. and r = @(1/Tt.. then (7)
produces iterates with average error (T + 1)-
21= E [xxx) - [ upper bounded by
[x00 7T
x
O² TLT
|b.
||b, b. ||
+1
+ Σ
IEST mod
We give complete proof's in Appendix C These convergence rates consist of two terms: The first term states how fast the function would converge in the absence of the noise. The second term, the noise term, is the focus of our paper, as it shows how the correlated noise BZ affects convergence.
These rates involve only differences of rows of B that are at most iterations apart. Intuitively, is coarse indicator of whether an iterate x; is still sensitive to the noise injected at an iteration t' < t. If t t' + 7. then changes the noise added at step are effectively uncorrelated iteration t'. As we
detail in Appendix, applying Theorem 4.7 to the special cases in Examples 3.1 3.2 recovers their tight convergence rates in
correspondingly.
5 Finding Better Factorizations
We now draw on our results in Section to develop better mechanisms for the MF-DP-FTRL framework. We modify the objective underlying the offline matrix factorization problem during the first stage of the ME-DP-FTRL workflow (Fig. []. Specifically, observe that the noise term in can be rewritten in matrix notation (up to multiplicative constants)
Theorems 4.6
and
|
Σ
|
Σ
1SST t= mod
bb, b, by-111 +
I8ET (20 mod
VF b,
b
b(+)r)
(15)
7

---

Average gradient norm
Last gradient norm
Convergence curve
squared norm
10a
DP- DP-P
squatd norm
10*
DP4P
DP-I
squared norm
101
DP MF
DP-MF-, tau 50
101
10
101
10>
20
102
10
2000
learning
learning
Iteration
(a) Average gradient norm for (h) Last gradient norm for vary-(c) Gradient norm over time for varying learning rates.
ing learning rates.
10
Figure 2: Comparison of the average and last gradient norms for DP-MF and DP-MF+ on random non-strongly convex quadratic function with = 10.
where A, = .T] E RTxT, and we set the rows X appropriately to select corresponding
row differences of B with either coefficient 1 or 1/VF depending on the index t. We give precise definition of A, and an explicit example when T 12,
in Appendix B
Recall that [0] minimize the Frobenius norm objective (6) based on their derived convergence bounds in (5). Since our derived convergence bounds are strictly tighter, propose using Eq. (15) the new objective function in (6). Intuitively, since A 12 is a better proxy for learning performance than [BB| minimizing this quantity in the offline factorization problem should lead to ERM methods with better privacy-utility trade-offs.
We can solve our new offline matrix factorization problem in straightforward manner. We can show that for A S, we can solve this modified problem by first computing the solution B, C using OPT (A, A). The solution to modified objective is then C C, B AC-1 This implies we can use existing open-source solvers designed for 6
Experiments
In this section, we evaluate the ERM performance of MF-DP-FTRL. under different offline factoriza- tion objectives. We focus on the Frobenius norm objective (6) which we refer to as DP-MF [0 and our modified objective 15 which we refer to DP-MF++
6.1 Validating Theoretical Results
We first validate theoretical results above by comparing the convergence of DP-MF and DP-MF+ on a random quadratic function that satisfies the assumptions of Theorem 4.7 Notably, we ensure the quadratic is not strongly convex. We treat in (15) as hyperparameter and tune over fixed grid. For complete details, please refer to Appendix H We present the results in Fig.
In Fig. 2(a) we plot + Et=o [VI(xx))1 as this quantity is proportional to the LHS of Theorem 4.7 For all learning rates, DP-MF+ either matches or outperforms DP-MF. Moreover, the advantage of the learning rate increases. This corresponds to our theory in Theorem 4.7 Indeed, the larger the stepsize 7, the smaller the optimal (as r O (1/z)), and the more often restarts are used in the analysis of Theorem 4.7
DP-MF+ increases
Fig. 2(b) further depicts the last-iterate behaviours of DP-MF and DP-MF+, which is often more practically relevant. Interestingly, the last iterate behaviour is improved even in the cases where the average behaviour does not improve. Finally, in Fig. 2(c) we pick = 10-2, r = 50 as the parameters for which both the average and the last-iterate behaviours convergence curve over iterations. DP-MF+ has regular oscillating behaviour, allowing it to achieve a good final-iterate performance. The period of these oscillations is exactly equal to T.
improved and plot the
6.2 Practical DP Training Experiments
We now compare DP-MF, DP-MF+, and DP-SGD with privacy amplification T on the MNIST, CIFAR-10 10, and Stack Overflow datascts. We omit from comparison DP-FTRL 20 and DP-Fourier

---

Nit Pi Baanir
0.25
020
021
07
Spaioo
10
100
-37
0.1
Epeice
160
Epadon
(a) MNIST. 1 epoch
(b) MNIST, 16 epochs
(c) CIFAR-10, 20 epochs
Figure 3: Test set accuracy of various mechanisms the MNIST and CIFAR- 10 datasets.
7 as these methods are strictly dominated by DP-MF. Unlike our theoretical analysis, we include clipping derive formal (e, 5) privacy guarantees. To facilitate fair comparison, we set 5 10-6 in all the settings, and compare against varying e. We give complete experimental details in Appendix
MNIST, logistic regression. We train for T 2048 iterations and either 16 epochs depending on the batch size, corresponding to a batch size of 29 and 469 respectively 2 We fix the clipping threshold at 1.0 and the learning rate 0.5. We vary in (55) over {2, 8, 32, 128, 512, 2048). The results are in Figs. (aa) and 3(b) DP-MF+ improves monotonically with т, performing best when 2048- T. For such r, DP-MF+ consistently out-performs DP-MF across all settings. Recall from 15 that this corresponds to the offline objective A where As = 1/VT for all i < T and Arr I. This objective strongly penalizes errors on the final iterate, which is the model used to compute test accuracy.
We also that DP-MF+ expands the number of settings in which we can beat DP-SGD. DP-MF only outperforms DP-SGD for sufficiently large E (E 2 0.31 for 1 epoch and 2 31 for 16 epochs). By contrast, DP-MF+ outperforms DP-SGD in every setting except when ε 0.01 and epoch. None of the mechanisms reached the accuracy levels obtained by the non-private baseline, even at 100. We suspect this is due to the fact that are using a fixed but aggressive clipping threshold of 1.0 across all experiments, which helps in the moderate privacy regime but hurts in very low privacy regime. Even though DP-MF* does not use privacy amplification, it outperforms DP-SGD, which uses privacy amplification. This is due to the efficient noise anti-correlations in DP-MF+. If amplification were not possible, performance of DP-SGD would degrade even further.
CIFAR-10, CNN. We follow the experimental setup from [7]- Specifically, we train all mechanisms for 20 epochs and 7 2000 iterations, which corresponds to batch size of 500 [ We tune the learning rate over a fixed grid. We fix r = T = 2000 in DP-MF+ as we found that worked best in the MNIST experiments. The results are given in Fig. 3(c) We see that DP-MF+ (T 2000) offers consistent improvement over DP-MF across all choices of considered. Both DP-MF and D beat DP- for & > 4. This observation is consistent with prior work on DP-FTRL and DP-ME, where DP-SGD performs relatively better with smaller while DP-MF performs better with larger E.
Stack Overflow, LSTM. In Appendix H we compare DP-MF and DP-MF* on a federated learning task with user-level differential privacy. We do not compare DP-SGD on this task, as amplification techniques such as shuffling and subsampling are not possible in practical federated learning settings [20] In this task, we train an LSTM network to do next-word prediction on the Stack Overflow dataset. To be consistent with the prior work [10 and test if our proposed factorizations are compatible with the other types of workloads A from Eq. ( we use momentum and learning rate decay. Our results are given Table 2 We see that two methods perform comparably, verifying competitiveness of our method. Note that this task uses federated averaging (32] instead of gradient
II practice, one often trains amall-scale models for many epochs, perhaps even using full- bull-batch gradients. improve the privacy/utility trade-off (at the cost of increased computation). We are interested in the relative performance lixed computation budget, so we train for a small number of epochs. 'While Choquette- Choquette-Choo et al. ? use momentum and learning rate decay, we omit the use of such techniques they are orthogonal to our theoretical results.

---

descent. Developing offline factorization objectives specifically for federated learning remains an open problem.
7 Conclusion
In this work, we developed analytic techniques to study the convergence of gradient descent under linearly correlated noise that motivated from a class of DP mechanisms. We derived tighter bounds than currently exist in the literature, and we our novel theoretical understanding to design privacy mechanisms with improved convergence. Perhaps more importantly. our work highlights the wealth of stochastic optimization questions arising from recent advances in differentially private model training. As such, we distill and formalize various optimization problems arising from recent work on matrix mechanisms for DP. Our work raises host of questions and open problems, including extending our analysis to include things such as clipping, shuffling, and momentum. Another key extension is to derive last-iterate convergence rates rather than average-iteren -iterat convergence rates, as in some settings it is only the final "released" model that needs formal privacy guarantees. Given the improved generalization properties of Anti-PGD [37] one could also investigate how design more general linearly correlated noise mechanisms which improve both privacy and generalization.
8 Acknowledgments
The authors would like thank Francesco D' Angelo, Nina Mainusch and Linara Adylova for their comments on the manuscript. The authors would also like to thank the reviewers for their helpful suggestions improving the clarity of the writing.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Oct 2016. doi: 10. 00.144/2976749.297833
[2] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q Weinberger, edi- tors, Advances in Neural Information Processing Systems, volume 24. Curran As- sociates, Inc., 2011. URL https: hww.rooeeiingssuuursss..pppppppp fo66222/77766111777777a55555555.
[3] The TensorFiow Federated Authors. TensorFlow Federated Stack Overflow dataset, 2019. URL (ataaete//tacckovrrrroo//oooo
[4] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464-473, IEEE, 2014.
[5] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances neural information processing systems, 32, 2019.
[6] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3 4):231133135 nov 2015. ISSN 1935-8237. doi: 10.1556/22000000500 URL https://doi.org. wtt./////...1112200000000000
[7] Christopher A. Choquette-Choo, H. Brendan McMahan, Keith Rush, and Abhradeep Thakurta.
Multi-epoch matrix factorization mechanisms for private machine learning, 2022. URL httpps
//arxiv.org/ab/ /ttp://///aab///..553..333
[8] Rudrajit Das, Satyen Kale, Zheng Xu, Tong Zhang, and Sujay Sanghavi. Beyond uniform Lipschitz condition in differentially private optimization. arXiv preprint 107113,.06..0133. 2022.
10

---

[9] Ofer Dekel, Ran prediction using mini-batches. Mach. Learn. Res., (3(mull):165-200 jan 2012. ISSN 1532-4435.
Ohad Shamir, and Lin Xiao. Optimal distributed online
[10] Sergey Denisov, Brendan McMahan, Keith Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In Neural Information Processing Systems, 2022.
[11] John C Duchi, Peter L Bartlett, and Martin Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
[12] Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients can win the race: Error-runtime trade-offs in distributed sgd. In International conference on artificial intelligence and statistics, pages 803-812. PMLR, 2018
[13] Cynthia Dwork, Frank McSherry Kobbi Nissim, and Adam Smith. Calibrating noise to sensitiv- ity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978- 978-3-540-32732-5.
[14] Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 425-438, 2020.
[15] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468 2479. SIAM, 2019.
[16] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954-964 IEEE, 2022.
[17] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly con- verging error compensated sgd. Advances in Neural Information Processing Systems, 33: 20889-20900, 2020.
[18) Monika Henzinger and Jalaj Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation using completely bounded norms. Cryptol- ogy ePrint Archive, Paper 2022/225, 2022.
[19] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-29, 2021.
[20] Peter Kairouz, Brendan Memahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 5213-5225. PMLR, 18-25 Jul 2021. URL
[21] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, (4(1-2): 1-00,, 2021.
[22] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[23] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich. A unified theory of decentralized SGD with changing topology and local updates. Proceedings of the 37th International Conference on Machine Learning, 20. JMLR.org, 2020.
11

---

[24] Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using FFT. In International Conference on Artificial Intelligence and Statistics, pages 3358-3366. PMLR, 2021.
[25] Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the twenly-ninth ACM SIGMOD-SIGACTT-IIGA symposium on Principles of database systems, pages 123-134, 2010.
[26] Chao Li, Gerome Miklau, Michael Hay, Andrew Megregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24:757-781, 2015.
[27] Aurelien Lucchi, Frank Proske, Antonio Orvieto, Francis Bach, and Hans Kersting. On the theoretical properties of noise correlation in stochastic optimization. Neural Information Processing Systems, 2022.
[28] Horia Mania, Xinghao Pan. Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal Optimization, 27(4):2202 2229, 2017. doi: 10. (0.1137/16M10050000. URL https:://ooi
[29] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimiz- ing error of high-dimensional statistical queries under differential privacy. arXiv preprint arXiv: 035377 2018.
[30] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajhhala Hdmm: Opti- mizing error of high-dimennnn dinesdimensional statistical queries under differential privacy. arXiv preprint arXiv:2106.11 12118, 2021.
[31] Brendan McMahan and Abhradeep Thakurta. Federated learning with formal differential privacy guarantees. Google Al Blog, 2022.
[32] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. caapuuniiaatio-fffffiieeee learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273- PMLR, 2017.
[33] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33: 17309-17320 17320, 2020.
[34] Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34:14606-14619, 2021.
[35] Yurii Nesterov. A method for solving the convex programming problem with convergence rate )./k2). Proceedings of the USSR Academy of Sciences, 269:543-555 547, 1983.
[36] John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statistics, pages 3581-3607. PMLR, 2022.
[37] Antonio Orvieto, Hans Kersting, Frank Proske, Francis Bach, and Aurelien Lucchi. Anticorre- lated noise injection for improved generalization. arXiv preprint arXiv:2202.02831, 2022.
[38] Antonio Orvieto, Anant Raj, Hans Kersting, and Francis Bach. Explicit regularization in overparametrized models via noise injection. arXiv preprint 33Xiv:2206.04613, 2022.
[39] B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Muthemutica and Mathematical Physics, 4(5):1-17, 1964. ISSN 0041-5553. doi: https///ao.oogg///00000004444141
URL http://///ww..eeeeeeeeeee..e....
12

---

[40] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathemaatical Statistics, 22(3):400 407, 1951. doi: 10.214/aom//117779956 URL https
//doi.org/ 0tt.111/4/ammm11777/755155/
[41] Shai Shalev-Shwarte Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In Anmual Conference Computational Learning Theory, 2009.
[42] Sebastian U. Stich. Local SGD converges fast and communicates little. International
Conference on Learning Representations, 2019. URL http://///ppprrreeeee/eettrrrrte
S1g2JnRcFX
[43] Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. J. Mach. Learn. Res., 21(1), jun 2022. ISSN 1532-4435.
[44] Sebastian U Stich, lean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. Advances Neural Information Processing Systems, 31, 2018.
[45] Om Thakkar, Galen Andrew, and H. B. McMahan. Differentially private learning with adaptive clipping. In Advances in Neural Information Processing Systems, 2021.
[46] Hoang Tran and Ashok Cutkosky. Momentum aggregation for private non-convex erm, 2022.
[47] Harsh Vardhan and Sebastian U. Stich. Tackling benign nonconvexity with smoothing and stochastic gradients, 2022. URL
[48] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
[49] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. In The 22nd International Conference Artificial Intelligncce and Statistics, pages 1226-1235. PMLR, 2019.
[50] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 7184-7193. PMLR, 2019.
[51] Ganzhao Yuan, Yin Yang, Zhenjie Zhang, and Zhifeng Hao. Convex optimization for linear query processing under approximate differential privacy, 2016. URL httpps://axxi...ott abs/1602.04302
[52] Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in Neural Information Processing Systems, 33:5332-5344, 2020.
[53] Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. In International Conference Learning Representations, 2022. httpsstpss:// http::////pe/eeeeeeeeee wtt.:e/eeeoooooondddddaaaaaaao
[54] Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning, pages 7594-7602. PMLR, 2019.
[55] Yuqing Zhu and Yu-X fu-Xiang Wang. Poission subsampled Rényi differential privacy. In Interna- tional Conference on Machine Learning, pages 7634-7642, PMLR, 2019.
13


Reviews:
[{"review_id": "Q5BvAAww3o", "reviewer": "Reviewer_dQeP", "summary": "This paper studies variants of noisy gradient descent, focusing on when the noise added at different time steps may be dependent. The motivation of this is differentially private optimization: while the standard DP-(S)GD adds independent noise at each time step, the recent DP-FTRL mechanism [1] adds carefully correlated noise. Even more recent work [2,3] extends this approach via the matrix mechanism. This paper builds heavily on the latter two works. It begins by identifying how the prior analysis is pessimistic and settings where one might hope to improve upon it.\n\nWe then analyze in detail \"perturbed gradient descent,\" PGD, ie gradient descent with independent Gaussian noise, and \"anti-PGD,\" which after each gradient step we add a new noise term and *subtract* the noise term from the previous time step. This latter method is closely related to randomized smoothing. \n\nThe authors establish the main theorems (for general \"noisy SGD-type\" algorithms without clipping) via a novel analysis, analyzing virtual iterates that periodically revert to the actual sequence.\n\nThe authors perform experiments, first on synthetic data without gradient clipping (to validate their theorems) and then with clipping on benchmark data sets. They show that, in some settings, their approach matches or exceed DP-SGD.\n\n[1] Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., & Xu, Z. (2021, July). Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning (pp. 5213-5225). PMLR.\n\n[2] Denisov, S., McMahan, H. B., Rush, J., Smith, A., & Guha Thakurta, A. (2022). Improved differential privacy for sgd via optimal private linear operators on adaptive streams. Advances in Neural Information Processing Systems, 35, 5910-5924.\n\n[3] Choquette-Choo, C. A., McMahan, H. B., Rush, K., & Thakurta, A. (2022). Multi-epoch matrix factorization mechanisms for private machine learning. arXiv preprint arXiv:2211.06530.", "questions": "What is the DP-SGD you're comparing against? How were the hyperparameters selected?\n\nCan you elaborate on what kinds of factorizations your approach favors? Do you have an intuition for how they differ from those of Denisov et al.?\n\nThe main theorems specify a value of $\\tau$, but the experimental performance seems to improve monotonically with $\\tau$. Maybe I missed it, but do you have an idea for why that is?", "limitations": "I feel the authors are clear about the limitations of their work. As I see it, the main limitations are (i) the narrow scope and (ii) the experiments, which I feel are more \"illustrative\" rather than comparing to the state of the art.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper investigates a topic of clear theoretical and practical importance; there is substantial food for thought. In particular, the authors convince me that there is more to be done in this direction. They analyze simplified cases but lay out many directions for further analysis. I agree that the paper \"highlights the wealth of stochastic optimization questions arising from recent advances in differentially private model training.\"\n\nIn addition, the paper makes clear progress beyond prior work, bringing a new set of tools to bear.\n\nI thought the analysis for the main theorems was very cool. It seems plausible that this type of analysis might be extended or applied elsewhere.\n\nI feel the authors do a good job placing their work within the broader literature.", "weaknesses": "The paper has limited scope and there were fewer conclusions after the main theorems than I had hoped. For instance, in line 253 we read \"Intuitively, since $\\lVert \\Lambda_{\\tau} \\mathbf{B}\\rVert_{F}^{2}$ is a better proxy for learning performance than $\\lVert \\mathbf{B}\\rVert_{F}^2$, minimizing this quantity... should lead to... better privacy-utility tradeoffs.\" The \"intuition\" just repeats the paper's setup, that of finding better factorization. I would like a discussion of *why* this proxy is better, beyond the theorem statement.\n\nI feel that future work may supercede this approach without building on it. It is not clear how much this paper would contribute beyond pointing out that there is more work to be done. Indeed, perhaps algorithms from from Choquette-Choo et al. already outperform this approach? While the contribution is clear, I feel there is a ceiling on its impact.\n\nI feel the paper spends too little time on background. This is on purpose, since the setup is similar to that of Denisov et al. and Choquette-Choo et al. However, I would like to see a more self-contained discussion. Two examples in particular stand out to me: first, the expression sens(C) is never defined. Second, as far as I can tell there is no detail on how DP-SGD was run as an experimental baseline.\n\nAlthough the motivation and experiments deal with privacy, the main theoretical results are for nonprivate algorithms. I was confused by this at first, especially in the transition from Section 2 to 3: the paper says \"we derive a tighter bound... to design better factorization mechanisms for differentially private optimization,\" and then almost immediately says \"we omit gradient clipping from our analysis.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their detailed review and positive assessment of our paper ! Below we address the raised questions:\n\n## Weaknesses:\n\n1. We write that $‖\\Lambda_{\\tau}  B‖^2_F$  is a better proxy for learning performance because it captures convergence of the algorithm more tightly that the $‖B ‖^2_F$. Indeed, it holds that $|| \\Lambda_{\\tau} B||^2_F \\leq 4 ||B||^2_F$, making our rates in Theorem 4.7. strictly tighter than that in (5). Moreover, our derived convergence rate in Theorems 4.6. and 4.7. is tight for some notable special cases such as PGD, Anti-PGD and Chess-PGD (discussed in Appendix A.2), while the prior convergence rate based on $||B||^2_F$ cannot be tight for these cases (see discussion in lines 130-137, as well as in Appendix A). Therefore, we believe that minimizing a tighter bound based on $||\\Lambda_{\\tau} B||^2_F$ (under the fixed privacy) should directly transfer to the better optimization properties than minimizing objective based on a loose bound $||B||^2_F$. We will add this discussion to the next version.\n\n\n2. Our work analyzes the dynamics of a general matrix mechanism applied to model training with gradient descent, and is therefore applicable to any of the matrix-based mechanisms recently designed for improved scalability. To the best of our knowledge, none of the related work has moved beyond the Frobenius-norm formulation of error including (Choquette-Choo et al.), which we show to fail to be predictive of optimization performance in a variety of cases. This is to say: our work inherits the applicability, algorithmic and scalability improvements pursued in the rest of the literature, but addresses a fundamentally orthogonal problem. For this reason, we expect the domain of application of the analysis presented here to continue to grow in the near future.\n\n    In particular, algorithms from (Choquette-Choo et al.) provide an orthogonal contribution to our work. In (Choquette-Choo et al.) the major contribution lies in extending computation of sensitivity of $C$ from having only one pass over the data (Denisov et al.) to the multi-epoch algorithms, and proposing an efficient way to solve the resulting matrix factorization optimization problem. However, their algorithms are still based on minimizing the objective $||B||$ (see equation (4) in Choquette-Choo et al. ). In our experiments in section 6 we already combined multi-epoch matrix mechanisms from (Choquette-Choo et al.) with our new proposed objective $|| \\Lambda_{\\tau} B||$, as we do multiple passes over the data in all the settings.\n\n\n3. Limited by space we decided to skip some of the details that are not crucial to understanding our main contributions. Upon your suggestion, we will add more details in the appendix in the next version or in the main text if space permits.\n\n4. By choosing a set of assumptions and relaxations in Section 3, we wanted to find the simplest model for which it would be meaningful to study the effect of the correlated noise. By choosing a simpler model we are able to study tightly the effect of the correlated noise structures. Moreover, if the function is Lipshitz, its gradients do not require clipping.\nIn experiments we illustrate that our approach can lead to practical improvements even with the simplifications made.\n\n## Questions:\n\n1. For MNIST experiments we fixed the clipping threshold at 1.0 and the learning rate at 0.5. For the CIFAR-10 experiments we fixed the clipping threshold at 1.0 and we tuned the learning rate over a grid of {2^k for k=-4, -3, …, 3, 4} independently for each of the methods.\n\n2. We plot the two factorizations (MF and MF+) in the attached PDF. \nBecause of the repetitive pattern in $\\Lambda_{\\tau}$, our proposed factorization MF+ consists of exactly the same blocks of size $\\tau$, with noise being correlated only within these small blocks, and not correlated otherwise. We will further polish and add it to the next version. \n\n3. We believe that this is in part because of differences between the last-iterate, and the averaged iterate performances, as we illustrated in our experiments on a random quadratic function (Fig. 2). Specifically, but setting $\\tau = T, \\Lambda_{\\tau}$ is a diagonal matrix where all entries are equal, except for the last which is much larger.  This influences the objective by putting much more weight on the error of the last-iterate model.  In our experiments (section 6.1) we evaluate the final trained model at the last trained model (last-iterate), while the theory gives guarantees for the averaged iterate performance. Studying last-iterate behavior theoretically is an interesting direction for future work.\n"}, {"review_id": "DAHqlRD2pw", "reviewer": "Reviewer_ptMd", "summary": "This paper develops many techniques to analyze gradient descent convergence with linearly correlated noise, a setting motivated by many DP algorithms. The work derives tighter bounds, and use the resulting insights to motivate DP-MF and DP-MF+.", "questions": "1. How can this method be scaled to large $T$?", "limitations": "Limitations are adequately discussed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is structured well, and is very notationally precise for the most part. \n- The theoretical results are very involved, and I particularly appreciate the authors including several noteworthy special cases.", "weaknesses": "Clarity:\n- This work is not very self contained, and it seems like the authors expect the reader to be very familiar with Denisov et al. and Choquette-Choo et al. This makes the work a bit difficult to follow at times. I would advise the authors to include more details about these works in the supplementary or even the main paper if possible.\n- Related to the previous point, details about Example 3.3 in Section 3 are not provided at all. \n- This is a minor suggestion, but using $x$ to denote the weights is unconventional in the machine learning community as it typically is used to denote the dataset. This may be a source of confusion to some readers.\n\nPracticality:\n- The problem setting seems impractical, as factorizing $\\mathbf{A} \\in \\mathbb{R}^{T x T}$ is intractable in realistic settings. In the experimental settings considered in this work, T is reasonable. However, in practice $T$ can be on the order of millions and even a one-time matrix factorization is not tractable.\n- Is Assumption 4.2 a realistic assumption for deep learning? The loss landscapes for neural networks are typically extremely sharp, rendering some of the convergence rate results vacuous. I understand that this is a common assumption in the optimization community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Clarity\n1. Due to the page limitations we unfortunately were unable to fit all the background information. Upon your suggestion, we will add more details in the appendix in the next version or in the main text if space permits. In particular we will include details of how to compute sensitivity of C, and will elaborate on Example 3.3.\n\n## Practicality\n1. The reviewer is correct to point out that the class of methods we consider are not currently applicable to the T >= 1M setting.  It is an interesting and important open problem to scale up the matrix factorization mechanism to these settings, but this is a problem that is orthogonal to what we study in this work.\n\n2. The reviewer correctly points out that assumption 4.2 is a simplifying assumption that is not applicable to deep learning loss functions.  Nevertheless it is an assumption that is commonly used in the optimization literature that allows us to get a theoretical handle on the problem.  While our theory does not cover deep learning loss functions, our experiments on CIFAR-10 and StackOverflow do, and our method works well empirically in both of those settings.\n"}, {"review_id": "hUbB5VYCFv", "reviewer": "Reviewer_WD4o", "summary": "This paper studies (stochastic) gradient descent with linearly correlated noise. The paper builds upon recent results on (MF-)DP-FTRL. It highlights the limitations of this methods, proposes a restarting trick to improve it, and derive the corresponding analysis. Interestingly, the proposed analysis gives a unified analysis of PGD and Anti-PGD, that are difficult to analyze together otherwise. Theoretical results are confirmed by numerical experiments.\n", "questions": "1. The restarting trick essentially states that not all iterates should have correlated noise. Do you think this is a fundamental property of the method or simply a caveat of the analysis?\n2. How does the restarting trick affect numerical performances in terms of time of execution? It seems that solving $OPT_F(\\Lambda_\\tau A)$ could be easier due to the structure of $\\Lambda_\\tau$: is it the case?\n", "limitations": "Yes, authors pointed that their analysis does not encompass clipping, and only works for averaged iterate. Some other research directions/limitations have also been mentioned in the conclusion.\n", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Overall, I think this paper is a nice paper, that perfectly fits the conference.\n1. The proposed method identifies the limitations of an (important) existing method and proposes a clever trick to overcome them.\n2. Corresponding theory is derived in multiple settings (convex and non-convex), and is confirmed by numerical experiments.\n3. Overall, the paper is very pleasant to read (even the appendix), with a clear introduction and clear motivations, and the math seems to be correct.\n", "weaknesses": "In my opinion, this paper does not have major weaknesses. I only have a few minor remarks.\n1. The method is claimed to work for DP-SGD, but the theory is only derived with full-batch gradients. This is a bit unfortunate since DP-FTRL-like methods aim at providing stochastic DP algorithms that do not rely on amplification.\n2. The proposed method seems a bit \"handmade\": it seems there is something deeper behind it.\n3. Example 3.3 is a bit crude and could benefit from a little more details (on the choice of the pseudo-inverse and the fact that B and C are not square).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their time and their positive assessment of our paper.\n\n## Weaknesses: \n1. In this work we aimed to find a simple theoretical model for which it would be interesting to study the effect of linearly correlated noise on the optimization dynamics. Since the stochasticity in the gradients is not directly linked to the linearly correlated noise, for clarity we decided to omit it from the theoretical analysis. Our model serves as a proxy to the real experimental setup. We verified the effectiveness of our proposed method experimentally, justifying the simplifications made.\n\n3. Thanks for your comment. We excluded the details due to space limitations. Upon your suggestion, we will add more explanations of Example 3.3. in the next version in the appendix or in the main text if space permits.\n\n## Questions: \nThanks for your interesting questions!\n\n1. We believe that there is something deeper going on. Our analysis was motivated by the intuition that not all the iterates should have correlated noise: intuitively, if the noise was added large number $T_0$ iterations ago, the iterate $x_t$ should move sufficiently far from $x_{t - T_0}$ making the old noise added at iteration $t - T_0$ to become effectively uncorrelated. However, this is only an intuitive explanation, and more investigation is needed to understand this question in detail.\n\n2. Thanks for your question. Because of the repetitive pattern of matrix $\\Lambda_{\\tau}$ (See Appendix B), we need to perform optimization only for the block of $\\tau \\times \\tau$ instead of $T \\times T$ matrix $A$, repeating the found correlation pattern $B_{\\tau \\times \\tau}$ $T / \\tau$ times. See also our attached PDF to the reviewer dQeP for illustration of the repetitive pattern in $B$. We will include these details in the next version.\n"}, {"review_id": "QGsnFatXLn", "reviewer": "Reviewer_2HBd", "summary": "This paper conducted a theoretical study of gradient descent with linearly correlated noise, with strong motivation from the theory and applications of differential privacy (in particular, the popular DP-SGD algorithm).\n\nThe main contribution is a new convergence analysis based on the idea of \"restart iterations\". The paper argues that it unifies two previous  \"incompatible\" analyses for two different noisy gradient descent algorithms, namely perturbed gradient descent (PGD) and anti-PGD.\n\nInspired by the new analysis, this paper proposes a new matrix factorization method for noisy SGD. The matrix factorization coordinates noises across different iterations of gradient descent. The new factorization refines a previous method. Experiments show that it compares favorably to prior works.\n", "questions": "* If possible, it would be nice to discuss why the two analyses for PGD and anti-PGD are incompatible. Also, I am curious if the two different proofs directly inspire your analysis.\n\n* Your paper shows that the \"restart\" in analysis and algorithm design does help. However, could you provide some intuition on why \"restart\" is beneficial in both theory and applications? Do you have evidence that this method yields tight analysis?\n\n* Are there good heuristics to find an appropriate \"tau\" in practice? Is there a way to come up with an algorithm that is equally good, but does not require the knowledge of the hyperparameter?", "limitations": "The limitations and future directions are discussed in the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is very well-written and looks both educational and professional.\n* It tackles an important and popular question of optimization and private learning. The \"restart iteration\" analysis looks nice. However, I don't work on this area myself, it is hard for me to evaluate the novelty of the new analysis.", "weaknesses": "* I am slightly dissatisfied with the hyper-parameter \"\\tau\" required in your new algorithm and analysis (more on this in the question section).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Questions\n\n1. Thanks for your question. Due to the space limitations, we discussed why the two analyses for PGD and anti-PGD are incompatible in the appendix F, where we showed that\n- using the real iterate sequence $x_t$ we cannot prove the tight convergence bound of Anti-PGD (12).\n- using the virtual iterate sequence $\\tilde x_t$, we cannot prove the tight convergence bound of PGD. We also show in Appendix E.3. that for the PGD algorithm the virtual sequence $\\tilde x_t$ is provably converging slower than the real iterate sequence $x_t$, making it fundamentally impossible to get tight rates of PGD through $\\tilde x_t$.\n\n    While we do not see any fundamental limitations of analyzing Anti-PGD using the real sequence $x_t$ we are unaware of how to prove a tight rate (12) using the real sequence $x_t$.\n\n    The two different proofs directly inspired our analysis: our approach combines virtual and real iterates through the restart trick. Every tau iterations the virtual iterate $\\tilde x_t$ is restarted to the real iterate $x_t$, allowing for the tight analysis of both algorithms simultaneously.\n\n2. Our analysis is tighter than the prior rate in (5). Indeed, it holds that $|| \\Lambda_{\\tau} B||^2_F \\leq 4 ||B||^2_F$, making our rates in Theorem 4.7. strictly tighter than that in (5). Moreover, our derived convergence rate in Theorems 4.6. and 4.7. is tight for some notable special cases of matrix B such as PGD, Anti-PGD and Chess-PGD (discussed in Appendix A.2), while the prior convergence rate based on $||B||^2_F$ cannot be tight for these cases (see discussion in lines 130-137, as well as in Appendix A). Therefore, minimizing a tighter bound based on $||\\Lambda_{\\tau} B||^2_F$ (under the fixed privacy) should directly transfer to the better optimization properties than minimizing a bound based on a loose bound $||B||^2_F$.\n\n3. While in our experiments we found that setting $\\tau = T$ gave the best results in practice, our experiments are relatively small-scale. We envision that for the larger scale experiments, one should set $\\tau$ as large so that computing factorization of matrix $\\tau \\times \\tau$ is still computationally feasible.\n\n    On the other hand, our experiments in Figure 2 revealed a mismatch between the average and the last iterate behavior. We believe that analyzing our method for the last-iterate behavior can help to understand which $\\tau$ we should pick to achieve the best performance in practice. This question is out of scope of our work, where we focused on understanding the convergence properties for the average iterate.\n"}, {"review_id": "4OWthgAis5", "reviewer": "Reviewer_xFGx", "summary": "The authors propose a new analysis method that unifies the analysis of noisy gradient descent-based algorithms, where the noise is added to the matrix factorization, which provides a tight analysis of both the algorithms simultaneously, and hence would give the analysis for convergences for a general class of such matrix-factorization based gradient descent algorithms. Based on this new analysis, the authors also propose a new matrix factorization objective to further tighten the upper bound and empirically show it.", "questions": "- Can the authors elaborate on what they exactly want to denote using Figure 1 and maybe provide a more clear diagram for it so that the process can be understood better?", "limitations": "Authors have mentioned most of the limitations in their future work and additional points have been discussed above in the weakness section (novely and final iterate analysis).", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The method of analysis is based on a very simple yet essential idea and it opens the possibilities of a unified method of analysis for a good class of algorithms which are based on gradient descent algorithms based on matrix factorization.\n- The transition from proposing a tighter bound to a new matrix factorization objective shows powerful empirical applications of this class of algorithms to private optimization.\n- The paper is theoretically very sound.\n- Evaluation done on the paper is simple and easy to understand and evaluation has been done not only with respect to utility but also to visualize the trend that the gradients follow across training.", "weaknesses": "- The novelty and the reach of this problem are limited to a very specific class of algorithms on a practical scale.\n- Although the authors have already addressed this in their future work, it is still important to note that the average case analysis for differentially private algorithms might not be a correct metric to judge the performance of the model since the final iterate of the algorithm is returned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and positive review! Below we address the raised points.\n\n## Weaknesses \n\n1. While our analysis is restricted to the specific class of algorithms, this class of algorithms capture significant advances in differentially private optimization which were recently shown to strictly generalize (and dominate) the major methods of differentially private optimization, practically improving over a popular and widely-used DP-SGD algorithm [1].\n\n    Our work analyzes the dynamics of a general matrix mechanism applied to model training with gradient descent, and is therefore applicable to any of the matrix-based mechanisms recently designed for improved scalability. To the best of our knowledge, none of the related work has moved beyond the Frobenius-norm formulation of error which we show to fail to be predictive of optimization performance in a variety of cases. This is to say: our work inherits the applicability, algorithmic and scalability improvements pursued in the rest of the literature, but addresses a fundamentally orthogonal problem. For this reason, we expect the domain of application of the analysis presented here to continue to grow in the near future.\n\n[1] Choquette-Choo et al,  (Amplified) Banded Matrix Factorization: A unified approach to private training.\n\n## Questions \n\n1. In Figure 1 we aimed to illustrate the workflow of MF-DP-FTRL algorithms. There are two underlying optimization problems: a one-time matrix factorization problem (left) that is performed to obtain a noise correlation pattern B, depending on the workload matrix A, and a factorization objective; and (left) an ERM minimization that is data and loss-dependent, performed using the found noise correlation pattern B. Our work focuses on understanding the (right) part of this diagram: specifically, we aim to understand which factorization objective one should use for a one-time offline matrix factorization problem.\nWe will make our diagram more clear in the next version. In particular we will explain the connection of our diagram to the MF-DP-FTRL algorithm in (4).\n"}]

Author rebuttal:
We would like to thank all of the reviewers for their time spent to review our paper, their useful comments that will allow to improve our paper, and for their positive assessment of our work. Below we address comments from each of the reviewers separately. We will try to clarify most of these points in the next version of the paper as well. 

Upon the question of the reviewer dQeP, in the attached PDF we illustrate noise patterns $B$ found by minimizing the previous factorization objective in Problem 2.2. $\text{OPT}(A)$ (Fig. a) and our proposed objective in Section 5 $\text{OPT}(\Lambda_{\tau} A)$ (Fig. b). We see that $B_{\text{MF}}$ cancels gradually the noise added at the previous iterations throughout all of the iterations, while for $B_{\text{MF}^+}$ the noise cancels only within the last $\tau$ iterations. Moreover, $B_{\text{MF}^+}$ consists of exactly the same blocks of size $\tau$, making it more computationally efficient to solve $\text{OPT}(\Lambda_\tau A)$ when $\tau < T$. 


Meta-review: This paper studies variants of differentially private gradient descent with noise added at different time steps may be dependent. It gives a new analysis for the smooth case that is, in certain cases, tighter than the one known for the non-smooth case. The analysis relies on a new combination of existing analyses and small scale experiments show a benefit of the resulting algorithm.
Decision: Accept (poster)