Correlated Noise Provably Beats Independent Noise for Differentially Private Learning
Authors: Christopher A. Choquette-Choo
Krishnamurthy Dj Dvijotham
Krishna Pillutla
Arun Ganesh
Thomas Steinke
Abhradeep Guha Thakurta
Venue: ICLR 2024 poster (2024)
Keywords: differentially private optimization
stochastic gradient descent
linear regression theory
private deep learning
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We prove the benefits of correlated noise for DP optimization in linear regression. Using the theory, we derive an orders-of-magnitude more efficient correlated noise generation algorithm that nearly matches SOTA for private deep learning.

Abstract: Differentially private learning algorithms inject noise into the learning process. While the most common private learning algorithm, DP-SGD, adds independent Gaussian noise in each iteration, recent work on matrix factorization mechanisms has shown empirically that introducing correlations in the noise can greatly improve their utility. We characterize the asymptotic learning utility for any choice of the correlation function, giving precise analytical bounds for linear regression and as the solution to a convex program for general convex functions. We show, using these bounds, how correlated noise provably improves upon vanilla DP-SGD as a function of problem parameters such as the effective dimension and condition number. Moreover, our analytical expression for the near-optimal correlation function circumvents the cubic complexity of the semi-definite program used to optimize the noise correlation matrix in previous work. We validate these theoretical results with experiments on private deep learning. Our work matches or outperforms prior work while being efficient both in terms of computation and memory.

Published as a conference paper ICLR 2024
CORRELATED NOISE PROVABLY BEATS INDEPENDENT NOISE FOR DIFFERENTIALLY PRIVATE LEARNING
Christopher A. Choquette-Choo' Krishnamurthy (Dj) Dvijotham"
Krishna Pillutla'
Arun Ganesh Thomas Steinke Google
Abhradeep Guha Thakurta
ABSTRACT
Differentially private (DP) learning algorithms inject noise into the learning process, While the most common private learning algorithm, DP-SGD, adds independent Gaus- sian noise in each iteration, recent work on matrix factorization mechanisms has shown empirically that introducing correlations in the noise can greatly improve their utility. We characterize the asymptotic learning utility for any choice of the correlation function, giv- ing precise analytical bounds for linear regression and as the solution to a convex program for general convex functions. We show, using these bounds, how correlated noise provably improves upon vanilla DP-SGD as a function of problem parameters such as the effective dimension and condition number. Moreover, our analytical expression for the near-optimal correlation function circumvents the cubic complexity of the semi- cemi-definite program used to optimize the noise correlation matrix in previous work. We validate our theory with experiments on private deep learning. Our work matches or outperforms prior work while being efficient both in terms of compute and memory.
INTRODUCTION
The broad adoption of deep learning using sensitive data has led to the increasing popularity of rigorous frameworks for privacy preservation, such as differential privacy (Dwork et al., 2006). The workhorse of private learning, a differentially private variant of stochastic gradient descent called DP-SGD (Song al., 2013; Bassily et al., 2014; Abadi et al., 2016), clips per-example gradients to some & norm and adds in- dependent Gaussian noise. DP-SGD has been used in range of applications from learning with medical images (Adnan et al., 2022) to finetuning large language models with (100B)) parameters (He et al., 2023).
A recent line of work instead proposes to add correlated Gaussian noise each clipped gradient (Smith Thakurta, 2013; Kairouz et al., 202 la; Denisov et al., 2022; Choquette-Choo et al., 2023b). This class of algorithms called DP-FTRL, has been used for private federated learning industrial scale (Xu al., 2023). By solving an expensive semi-definite program to find the noise correlations, Choquette-Che Choo et al. (2023a) demonstrated empirically that DP-FTRL never worse and often much better than DP-SGD in its privacy-utility tradeoff across multiple modalities like images and text.
However, several questions remain open. Does DP-FTRL provably improve over DP-SGD in its expected utility? Further, can we design a more computationally efficient procedure to find the noise correlations for DP-FTRL without significantly worsening the privacy-utility tradeoff?
We answer both questions affirmatively by (1) providing sharp theoretical characterization of the noisy training dynamics of DP-FTRL, and (2) leveraging these analytical tools to circumvent the semi-definite program required in past work.
"Equal contribution; alphabetical ordering.

---

Published as conference paper ICLR 2024
Algorithm 1 The DR-FTRL/NOisy-FTRL algorithms with a noise correlation matrix B E R Tx
Input: B E RTXT initial iterate 0g R & clip norm G, noise multiplier dap. learning rate 7), datasct D 1: for 1 = O,...,
do
f Vr(0)
for Noisy-FTRI, for DP-FTRL
Obtain the next datapoint 2ι and compute g.
clip +) vr(())
3: Sample noise wh ~ (0, d G2 Ia) and calculate the correlated noise wb Er=o B w0.
4:
Update 0.+1 0. - T/g, for the noisy gradient g. gi + Wi
Return Or
1.1 PROBLEM SETUP AND BACKGROUND
Let D (.o...., =T J be dataset of T' datapoints, where each datapoint is sampled i..d. from an underlying distribution IP dataa- Our learning objective is to minimize:
F (0) EE cana (0: +r
(1)
where f(0; 2) is the loss incurred by model parameters O E R2 on datapoint z, and r(-) is data-independent regularization. We aim to minimize F while satisfying differential privacy with respect the dataset DD We assume that F has unique minimizer denoted 0..
We focus on variants of stochastic gradient descent with batch size of for data arriving in stream. The learning algorithms we study are presented in Algorithm I; we assume throughout that the dataset DD randomly shuffled before running the algorithm so that each datapoint 2; an i.i.d. sample from TP PPaaaa DP-FTRI. with noise coefficient matrix B E T (which is lower triangular) performs the updates!
0.+1 = =0; (clip (V (1) G) Vr(O.) Et= B,,-
(2)
for Gaussian noise w; NO0, G2) where clip (.. G)) denotes projection onto & ball of radius G. We define Noisy-FTRL to be DP-FTRL without clipping. Taking B = I as the identity matrix recovers DP- SGD (with clipping) and Noisy-SGD (without clipping), and other choices give rise to alternate algorithms.
We restate result from prior work showing that DP-FTRL is differentially private for any choice of B, provided the noise multiplier is scaled up appropriately.
Theorem 1.1 (Denisov et al. (2022); Bun & Steinke (2016)), DP-FTRL (Algorithmm I with the clipping enabled) satisfies p-zero concentrated differential privacy (zCDP) if the noise multiplier is taken as d (B) where "TT (B) = maxt<T (B= is the sensitivity of B-122
Remark 1.2. Although Noisy-FTRL is not differentially private, lets us analyze the noise dynamics of DP-FTRL without technicaliries associated with clipping. We sharply characterize the asymptotic utility of Noisy-FTRL for linear regression and show later that this analysis extends to DP-FTRL under appropriate assumptions. For mean estimation and learning with Lipschitz convex losses, directly analyze DP-FTRL.
1.2 MOTIVATION
This work is motivated by two open questions particular.
Matrices (c.g. B (B.r)c.r2)) and vectors (c.g. f = (So, .), are zero-indexed and bold-faced. We give DP guarantecs w.r.t. the "zero-out" notion of ncighborhood (Kairouz et al., 2021a); Appendix A for review. Further, a p-zCDP guarantee readily translated into (e, -DP (Bun & Steinke, 2016, Prop. 1.3).
2

---

Published as a conference paper at ICLR 2024
Provable separation between DP-SGD and DP-FTRL: The best-known separation between DP-SGD and DP-FTRL in the literature is due to Kairouz et al. (2021a). For G-Lipschitz convex losses, DP- FTRL at a privacy level of p-zCDP achieves a suboptimality of O(Gd"///Vo)) compared to DP-SGD's ( p2)). The only improvement here is in terms of the privacy parameter p. More recently, Koloskova et al. (2023) analyze Noisy-FTRL but without normalizing for the sensitivity (r(B) as in The- orem 1.I. Thus, the existing theory fails to reflect the large margin by which DP-FTRL empirically outper- forms DP-SGD across the board (Choquette-Choo et al., 2023a), and precise characterization is missing,
Computationally efficient DP-FTRL: Prior work on DP-FTRL utilizes the noise correlation matrix B that minimizes the squared error in the gradient prefix sums (Kairouz al., 2021a; Denisov et al., 2022):
(3) where 9: is the clipped gradient applied in iteration t and gt its noisy counterpart (cf. Algorithm 1). This was, in turn, obtained as an upper bound on the regret in an adversarial online learning setting (Kairouz al., 2021a, Thm. C.I). The most potent algorithm from the previous work gave B as the solution of a semidefinite program with matrix variables of size O(T²), requiring O(T$) time (Denisov et al., 2022, Eq. 4). This cost is prohibitive for large learning problems. Moreover, there mismatch between the objective (3) used to find the noise correlations and the final learning objective F(Or). In particular, there exist matrices Bi, B2 with equal squared error yp B1) = qo( B2) and equal sensitivities 7r (r( = (B,) such that DP-FTRL with B₁ diverges while DP-FTRL with B- converges (Koloskova et al., 2023).
(B = -. 0 - 9t
Our approach: We study the suboptimality in the final objective E[F F(O.)). We work in the asymptotic T + oc regime to allow the use of analytic tools, but also to derive results that apply regardless of the dataset size. Second, we restrict the search over B to Toeplitz matrices B 3 generated by a sequence 3 (Bo, .1....) of reals, but stronger motivation is that they are anytime, i.e., they do not be recomputed for each value of T and easily apply as T + co. Toeplitz were previously considered for their computational efficiency in learning (Choquette-Choo et al., 2023b) and their near-optimal rates in linear counting queries (Henzinger et al., 2024). Thus, our goal is to characterize the asymptotic suboptimality
Foo = lim [ (0r) -(0.)]
(4)
T-+00
for Or produced by Noisy-FTRL or DP-FTRL under noise correlation weights 33 where 0, = arg min is assumed unique. This limit turns out to be well-defined and finite for the settings we consider as long as || is finite. We analyze Foe in the frequency domain using the discrete-time Fourier transform
B(w)= = Ei cxp(iwt), with i the imaginary unit. Further, we define the limiting sensitivity associated with B the limiting value of yr, which, using standard Fourier analysis tools, equals
1/2
You (B) = lim Yr (B) =
L 25
J_
B [ww)
dw
(5)
T-
1.3 OUR CONTRIBUTIONS
The concrete contributions of this work are as follows.
Analytically optimal DP-FTRL for mean estimation: We give analytical expressions for the asymptotic suboptimality FoR for mean estimation and the noise correlations f that minimize Foo as a function of the learning rate 7 ($2.1). We find that the optimal noise is anti-correlated, so the algorithm subtracts out previously added noise. Inspired by the analytical expression for the optimal noise correlations 3. for mean estimation, we propose a single-paramete family of choices for B, which we call D-DP-FTRL. We show its favorable theoretical and empirical properties for a broader range of problems.
D-DP-FTRL:
"Note that the DP noise multiplier dep remains finite in the asymptotic T + regime consider the streaming setting: each example is processed once and the number of examples also grows to infinity.
3

---

Published as a conference paper ICLR 2024
for linear regression with Gaussian inputs æ ~ (0, H) and noise multiplier oap 7oo (2p) based on the limiting sensitivity (5), We give the bounds in terms of the learning rate 7) dimension d, the effective dimension der [ and the noise variance p representing the Since S den S d, Noisy-FTRL is better than Noisy-SGD at smaller 7 when der is small (e.g., when H is close to low rank).
Table 1:
Asymptotic suboptimality of Woisy-SGDDNNosyy--
Tr(H]
privacy level. We take G = 1 and Amax (H) 1 w.l.o.g. and only show the term depending
Algorithm
Asymptotic Suboptimality Ei
Ratio w/ Lower Bound
Remark
Lower Bound
2 da) (np d)
for all 33 with finite [|]]
Noixy-SGD
e()) denotes matching upper lower bounds Here, J Ausin (H)
2-Noisy-FTRL
(1 der log"
log"
weights from (7)
Strict separation for linear regression: We establish sharp bounds on Noisy-FTRL (i.e., DP-FTRL without gradient clipping) for linear regression. Summarized in Table and stated formally in $2.2, we show: (a) u-Noisy-FTRL, with analytical closed-form correlations, matches the lower bound up log factors. Both these bounds scale with the effective dimension der of the problem, which is no greater than the dimension d but can be much smaller when the data is approximately low rank.
(b) v-Noisy-FTRL is provably better than Noisy-SGD by factor that can be as large as d/ log d (when derr is a constant). This shows an exponential separation between Noisy-FTRL and Noisy-SGD.
Our bounds quantitatively show how the anti-correlations of p-Noisy-FTRR help prevent noise accumulation along eigen-directions of the Hessian with small eigenvalues. The gradients have weak signal along these directions and are unable to undo the effect of the previous noise and move the iterates back towards the minimizer; the anti-correlations are essential to obtain near-optimal asymptotic suboptimality. We also leverage these asymptotics to give bounds the utility of x-DP-FTRL and DP-SGD for finite T.
Numerical separation for general strongly convex functions: We bound the asymptotic suboptimality Foo for any noise correlation weights B as the optimal value of a convex program. We use this to show that DP-FTRL achieves a tighter bound particularly when the condition number is large (Figure 3 in $3).
Experiments with private deep learning: We show the proposed D-DP-FTRL outperforms other efficient differentially private algorithms on image and text classífication tasks. We also find that our approach competitive even with inefficient approaches that require ( computation and O(T²) memory.
2 ANALYSIS FOR QUADRATIC OBJECTIVES
For quadratic objectives, Algorithm 1 (with no clipping) corresponds to linear dynamical system (Gray Davisson, 2004), allowing use analytical tools. We give an exact analysis of DP-FTRL for mean estimation and Noisy-FTRL for linear regression. The analysis of Noisy-FTRL. also lets us derive guarantees for DP-FTRL for linear regression. We do not aim achieve the best possible rates in these stylized models. Rather, our goal is to understand the noise dynamics of DP-FTRI. and show separation with DP-SGD.
2.1 CONCEPTUAL OVERVIEW: PRIVATE MEAN ESTIMATION IN ONE DIMENSION
We begin with the simplest objective function, the squared error for mean estimation problem on the real line. This setting captures the core intuition and ideas used to derive further results.
Consider distribution Pdata with l [F]]]| S azgd and |z| S a.s. for z PPataa Our objective now is
F (()) Eg~Pam
2) with f f(:: 2) =² 28, and r r0) = 6²
(6)
We show strict separation between DP-FTRL and DP-SGD for this simple minimization problem.
4

---

Published as conference paper ICLR 2024
Ratio of DP FTRL to DP SGD
Suboptimality ratie for mean estimation
Optimal noise correlation (time domain)
Optimal noise correlation (frequency domain)
y ta 0.34
Correlation weight .i
Correlation [B
10
10-4
34.14
10-
16
10-
10
10-1
-//2
1/2
Learning Rate
Time
Frequency
Figure 1: Left: The ratio of the asymptotic suboptimalities of DP-FTRL to DP-SGD for mean estimation the learning rate 7. DP-FTRL is never worse but orders of magnitude better at 1 or n + Middle & Right: Time- and trequency-domaii descriptions of the optimal noise correlations for mean estimation (defined in Theorem 2.1).
Theorem 2.1. Consider the setting above with learning rate 1) S and clip norm G == 1nnndd o (B)
2p
Then, the asymptotic suboptimality of a p-zCDP sequence (0e)ī-o obtained via DP-SGD F (Gapsdd) O(pp- + ggg)- Further, the asymptotic suboptimality of any p-zCDP sequence (0:) from DP-FTRL
inl F (B) = (/*) =0 (17²p (1/n) + 170 10
The infimum above attained by = --1) 11)5, where (1/3) = I 1/2- t-b
Proof Sketch. Using tools from frequency-domain analysis of linear time-invariant systems (Oppenheim et al., 1997), show that the asymptotic variance is integral of (. The sensitivity (5) is integral of [B(w] so that Foo a product these integrals. Its minimizer can be analytically computed in the Fourier domain (Fig. 1, right), which yields the expression for 3 (Fig, 1, center). See $B for details. m
The optimal pー1 coefficient 2 log2 (1/1) is better than DP-SGD's Note that 3 < for / 1: the noise is anti-correlated and it helps by subtracting out the previously added noise. We also recover the correlations of (Fichtenberger al., 2023) as 17 + 0; these were shown to be near-optimal for linear counting queries.
Theorem 2.1 gives an analytical expression for the optimal noise correlation weights for DP-FTRL for this simplified setting. We parameterize it with parameter 0 < < to define
D.DD-FFRRLIo-Noisy-YYT
== (-1)
(7)
We analyze this choice theoretically for the setting of Noisy-FTRI. and demonstrate near-optimality for appropriate v. Later, for our experiments with DP-FTRL, we tune as a hyperparameter to tune. We call this approach (with clipping) D-DP-FTRL and (without clipping) y-Noisy-FTRL.
2.2 ASYMPTOTIC SUBOPTIMALITY FOR LINEAR REGRESSION
We now give a precise analysis of Foo for linear regression with v-Noisy-FTRI. We will use this to derive non-asymptotic privacy-utility bounds for DP-FTRL at the end of this section.
We consider (unregularized) linear regression with loss function, (0; (xx y)) 3/ (y (0, 2 that
F(0) = E(a.g)>Pan (y (0,z)) )²)
(8)
We assume d-dimensional Gaussian covariates æ N(O, H) and independent Gaussian residuals y
(0,, x)) .N(0,, o2 2gd)) where 0, arg min F. We make these assumptions for ease of presentation; state
5

---

Published as a conference paper ICLR 2024
Dimension Dependence
Effective Dimension Dependence
Learning, Rate Dependence
Asymptotic Subopt. F
D0
Dimension
Effective Dimension
dar
Learning Rate
SGD
SGD bound
Noisy-FRLL FTRL
Noizy-FTR FTRL bound
Figure 2: Linear regression simulations: We plot empirically observed asymptotic suboptimality of v--oisy- FTRL/Noisy-SCII and their theoretical bounds with d = 128 (varied in the left plot) where the Hessian H has eigenval- ues A = 1/k (varied as k for E [0.4, 1] in the middle plot), and learning rate 1 0.02 (varied in the right plot). The slope of the corresponding empirical and theoretical lines are nearly equal, showing the tightness of the theory. particular, we observe that Noisy-SGD has linear dependence on the dimension (slope 1.00) and is nearly constant w.r.t. the effective dimension (slope 0.18) while Noisy-FTRL has near-linear dependence on the effective dimension (slope 0.94). Noisy-FTRL (slope 2.03) also has a better dependence on the learning rate than Noisy-SGD (slope 1.27).
and prove our results under weaker assumptions in the supplement. Further, we assume that F is L-smooth and u-strongly convex (equivalently, μl = H = LI since the input covariance H is also the Hessian of F).
We express the bounds on F's in terms of the correlation weights and the problem parameters p, G which, for DP-F,RL, denote the target privacy level and the gradient clip norm respectively. See $C for proofs.
Theorem 2.2. Let c, C1, C2 denote universal constants. For S c/ Tr [H].
we have
(Noisy-SGD)
(B - (ndC2 + no Tr [H] Foo ( S C.
with (o0d (1, (1,)....),
(U-Noisy-FTRL)
log" + no sga) H
with v S TH1 and
(Lower bound)
Fx( 2 C2 Gn² + no Tr H
for all B with || < 0o.
This shows the near-optimality of u-Noisy-FTRL. and a provable gap between Noisy-FTRI. and Noisy-SGD.
Observe that our bounds separate the contributions arising from correlated noise (p~1 term) and those from the inherent noise in the linear model (o² term). We focus on the effect of correlation because the effect of the latter noise is the same across all choices of B. We plot the differences in Figure 2.
Exponential separation between Noisy-SGD and Noisy-FTRL: Noisy- stationary error depends on the ambient dimension d, while the lower bound depends on the effective dimension deff = Tr HH] H of the covariance H. We have, deff S with equality when all the eigenvalues of H are equal but der & ll when the eigenvalues of H decay rapidly or it is nearly low rank. This is true particularly for overparameter- ized models where the features may be highly correlated resulting in an approximately low-rank covariance. The effective dimension is closely related to the stable rank (Rudelson & Vershynin, 2007); cf. $C.6.
For instance, if the eigenvalues of H are (1, 1/,, 1/d), then deff S 2. Then, Noisy-FTRL's error of O log" (d/n)) is exponentially better than Noisy-SGD's (()--'d) The learning rate dependence of Soisy-SGD is also suboptimal, similar to 12 This result is also confirmed empirically in Figure 2 (right).
Assuming Amax (H) = I, the deff depeneeede comes from the contribution of cigen-direction j of H to the asymptotic suboptimality improving from (11) for Noisy-SGD to scale with the corresponding eigenvalue Thus, the coti-correlated noise particularly helps in the tail eigen-directions of H. We discuss this further in Remark C.16 of SC
X, of H for u-Noisy-FFi
6

---

Published as a conference paper at ICLR 2024
Comparison to prior work: We apply our theory to compute Fxx. for linear regression given choices of B used in prior work. Though certain choices of the noise correlation /3 may be optimal for finite lincar counting queries (Fichtenberger et al., 2023), results show that they have Fso 0G because the sensitivity diverges T 0c. v-Noisy-FTRL effectively offeciivy introduces an additional damping term (1-v)² " the correlations of (Fichtenberger al., 2023) to achieve near-optimality for lincar regression. Damping similarly helps for nnti-PGD (Orvicto et al., 2022), where the resulting error is the geometric mean of the lower bound and the bound of Noisy-SGD from Theorem 2.2.
Table 2:
Noise Correlation Weights 3
Sensitivity in T steps (3)
Asymptotic Suboptimality
Algorithm
F (9)
(Fichtenberger et al., 2023)
Eq. (7) with U
log T log (1/1)) 7
u-Noisy-FTRI. (Ours)
Eq. (7) with < S a/a
pp Tr [H] log (1/v)
Anti-PGD (Orvicto et al,, 2022)
(1, -,0....)
00 11 1//2 [dTr(H]
Anti-PGD + Damping
(1. (1 v)) O).....
1/v
2.3 FINITE-TIME PRIVACY-UTILITY BOUNDS FOR LINEAR REGRESSION
Noisy-FTRL, which we analyzed so far, is not differentially private. Differential privacy requires gradient clipping which significantly complicates the analysis. However, for finite time horizon T, we argue using concentration that V (0; =) is bounded with high probability, and clipping can be avoided. Formal statements and proofs for the finite-time analysis are given in $D.
Consider DP-FTRL with noise correlation 3" from (7) with v du and gradients clipped to any fn-nrrm G. As mentioned in $1.1, the outputs (0,. 0r) of DP-FTRL are p-zCDP. For an appropriate choice of 7. we give utility bounds in terms of the effective dimension deff and the condition number L/pc
(a) For 1) small enough, we have with probability at least 1 that
max Igell2 I cmax Tr [H] lo - e_ 21l. agd / H f polylog (T/p) =: G. t<T
(9)
Let & denote this event. If & holds, no gradients are clipped and DP-FTRL coincides with Noisy-FTRL.
(b) For T 2 den p). we have (omitting log factors and 021 terms and taking H 1):
deff
[dden 10--0, 0.
11
doig
+
for DP-SGD,
[[(F(O.) F(O.)) 1 (
oT
oT
nade 1 110 0.11 0T2
ad 2
redeff
for D-DP-FTRI.
0T
Thus, the dimension d in DP-SGD's bound effectively becomes kdemt /T for DP-FTRL, leading to better dimension dependence. While faster 1/(pT²) rates are known for DP-SGD-style algorithms for linear re- gression (Varshney al., 2022; Liu al., 2023), such algorithms require sophisticated adaptive clipping strategies. Our algorithms use a fixed clipping norm G and a fixed noise multiplier ddp independent of T; the bounds presented above are, to the best of our knowledge, the best known in the literature for DP-SGD in this setting. We leave the exploration of combining adaptive clipping with correlated noise for future work.
3 ASYMPTOTIC SUBOPTIMALITY FOR GENERAL STRONGLY CONVEX FUNCTIONS
We now generalize $2.2 to general strongly convex problems. Here, we bound the asymptotic suboptimality of DP-FTRL and DP-SGD by the value of a convex program.
Theorem 3.1. Suppose f(-;2) 2) is G-Lipschitz. and the stochastic gradients are uniformly bounded as of (0;z) Eg'nFon (Vof (0; 2 2 S azgd Then, if F is p-strongly convex and L-smooth, the asymp-
totic suboptimality Foo is bounded for any noise correlation B (w) in the frequency domain by:
inf
Ld
(C2p pc2p-'1 IB (w) Po (B)² + ogga) (Ww dw w I- n. T] - R., &. C (n,, (1) 1. (10)
7

---

Published as conference paper ICLR 2024
DP-FTRL Variant
Citation
Corr. matrix B
Anytime?
Computation Cost
Generation
Training (per step)
DP-SGD
(Abadi al., 2016)
Identity
0 (1)
(
Honaker/TreAgg
(Kairnuz al., 2021a)
Trianglri (LT)
(
(log T)
Optimal CC
(Fichtenherger et al., 2023)
Toeplitz & LT
(
O(T)
y-DP-FTRL
Ours
Toeplitz & LT
O(1)
O(T)
FFT
CCoquette-Chooe al., 2023b)
Teeplitz
0(1)
O (Tlgg T)
Full Honaker
(Honaker, 2015)
Arbitrary
O(T*) O(T")
Mulli-Cpoch (ME)
(Choquette-Chook al., 2023b)
Arbitrary
0 (T
0 (T
Table 3: Variants of DP-FTRL: the noise correlation matrix B and whether the correlation matrix B be ated/optimized agnostic the time horizon T (denoted as "Anytime"). and computation cost.
where Yoo (B) is the limiting sensitivity from Eq. (5), and C (1) μ, L) is convex set (details and proof in ŞE),
While technically an infinite-dimensional optimization problem over the function v we can approximate the solution by discretizing 1/ into k points uniformly over [-T, л|. Further, we discretize B similarly, we obtain second-order cone program with & conic constraints and ((k) decision variables. As k + oc, the solution approaches the so- lution to (10). Empirically, as & increases. We stop the computation when the change in bound as a function of k drops below a threshold - this gives k 1000.
Asymptotics for Strongly Convex Functions
Asymptotic Subopt. Fe
DP-SGD
DPDF-TLRL
12
Optimized
observe that the values stabilize quickly
22
Further, given the optimal v = 3b",, we can run an alternating minimiza- tion where minimize the objective of (10) with respect to 1 for fixed B and with respect to B for fixed v. This leads to an iteratively improving choice of B. We find empirically that this iterative procedure converges quickly and leads to provable theoretical gap between the upper bounds on Foo achievable by DP-SGD and DP-FTRL.
23
Condition Number L/u
Figure DP-FTRL attains a tighter bound on Fso with the growing condition number. Here, "Optimized" approximately mini- mizes (10). The plots hold for smooth and strongly convex func- tions (L = = G, aege 0).
We numerically compare the bound (10) for DP-SGD and y- y-DP-FTRL. Figure shows that the gap between DP-SGD and v-DP-FTRL mul- tiplicative: the absolute gap grows with the increasing condition number k T./p. The suboptimality of "Optimized" DP-FTRI. (optimized as described above) grows even more slowly with
Overall, v-DP-FTRL significantly improves upon DP-SGD and has only a single tunable parameter and no expensive computation to generate the noise correlations. We focus on 2-DP-FTRL for experiments in this paper but leave the possibility of improving results further based on Optimized DP-FTRL for future work.
4 EXPERIMENTS
We demonstrate the practical benefits of y-DP-FTRL for deep learning tasks. This approach has a single tunable parameter y that can easily be tuned based on minimizing the squared error (3) as in prior work.
Comparing Computation (Table 3): While optimized matrices (e.g. "ME" in Table 3) have the state-of- the hhr privacy-utility tradeoffs in private learning (without amplification), their computational cost scales
8

---

Published as a conference paper ICLR 2024
Nonprivate Baseline
Nonprivate Baseline
75
25
Test Accuracy
Test Accuracy
24
Mechanlam
23
Machaniam
Lo-ko3s-)) (Ours)
(+= ')-DP-FTRL
60-
Optinal CC 24
22
Optimal CC Online Honakerx10
Online horeeer xte
50-500 + Ammpliiation
21
DF-SGD Amplitication
UnserBeard
MElK-20) VosTBestiz
MElk-6)
4
10
12
14
16
2.5
5.0
7.5
10.0
12.5
15.0
17.5 20.0
Privacy Budget,
Privacy Budget,
(a) Example-level DP on CIFAR-10 (image classification). (b) User-level DP StackOverflow (language modeling).
Figure 4: The proposed v-DP-FTRL outperforms all other efficient and anytime mechanisms. It also nearly equal slightly outperform the thth-ot "ME" mechanism that requires significantly more compute (cf. Table 3). "The non- non-private baseline for StackOverflow uses per-user clipping as this improves performance by R 0.5% pp.
O(T For example, generating the correlation matrix B for T 10 takes around 24 hours (Choquette- Choo et al., 2023b). Moreover, it has ( cost per step. We find in this section that D-DP-FTRL achieves near state-of-the-art privacy-utility tradeoff's at a much smaller computational cost of O(T) per iteration.
We compare with other anytime approaches for which the matrices B can extended to any time horizon T. The practitioner then need not specify T in advance, but rather, can train for as long as necessary to achieve minimal model loss-it is common to, c.g., let algorithms run until certain conditions, like maximum difference on the train-test loss, are met (Morgan & Bourlard, 1989). Moreover, general matrices B become prohibitive in terms of compute/memorr models scale up (Kaplan al., 2020; Anil et 2023).
Experiment Setup: We use two standard benchmarks: example-level DP for image classification on the CIFAR-I0 dataset and user-level DP for language modeling on the StackOverflow dataset. We use the same setup as (Kairouz et al., 2021a). We also stamp/restart all baselines as suggested in (Choquette-Chnl 2023b). This gives the baselines the advantage of an additional tuning parameter (tuned to minimize the squared error (3)), but does not affect their per-step training cost. We denote this by the suffix "xS" for in the plot. We tune CIFAR- 10 hyperparameters with grid search, while we use hyperparameters reported from previous works for StackOverflow. Appendix G gives the full setup.
et al.,
Across both datasets, v-DP-FTRL outperforms all existing anytime mechanisms by a signif- icant margin (Figure 4a). We find an average 3pp improvement that grows becomes small. Indeed, the proposed D-DP-FTRL makes up 30-80% of the gap between previous efficient approaches and the state-of- the-art and computationally intense ME approach. For instance, nearly matches ME at 70.83%. In particular, y-DP-FTRL outperforms Optimal CC (Fichtenberger et al., 2023), which is equivalent to D-DP-FTRL with v 0: this shows the practical importance of the exponential decay parameter v in Eq. (7). For StackOverflow. we find that v-DP-FTRI outperforms the state-of fatte-of-the-ae ME across all (Figure 4b) by Rs 0.3%-points while requiring significantly less computation.
Main Results:
10, we have 1-DP-FTRL 69. 89.26%
As becomes small, DP-SGD can outperform DP-FTRI due to privacy amplification. We find that v- DP-FTRI. outperforms DP-SGD for ε 2 on CIFAR-10 (63.02% vs. 62.02%) and around Rs 2 for StackOverflow (23.6% versus 22.6%), showing its broad applicability. Finally, we observe that our mech- anism achieves near non-private baselines on StackOverflow, A model trained via v-DP-FTRL gets 25.3% validation accuracy at 8, mere 1%-ptit off from the non-private baseline.
"Note that in practice take T be the number of steps of minibatch gradient descent, effectively doing several epochs over the data which differs from the theoretical setting considered in previous sections.
9

---

Published as a conference paper ICLR 2024
ACKNOWLEDGEMENTS
The authors thank H. Brendan McMahan, Fabian Pedregosa, Ian R. Manchester, Keith Rush, and Rahul Kidambi for fruitful discussions and helpful comments.
REFERENCES
NIST Digital Library of Mathematical Functions. htt.ts:://dlll .nist. www.t.tto//.......... Release 1.1.10 of 2023- 06-15. URL https:/ /ts///ddi /dlmf... mist. gov/. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS' 16), pp. 308-318, 2016.
Mohammed Adnan, Shivam Kalra, Jesse C Cresswell, Graham W Taylor, and Hamid Tizhoosh. Federated learning and differential privacy for medical image analysis. Scientific reports, 12(1))1953, 2022.
Rafik Aguech, Eric Moulines, and Pierre Priouret. On a Perturbation Approach for the Analysis of Stochastic Tracking Algorithms. SIAM J. Control. Optim., 39(3):872-899 2000.
Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. Palm technical report. arXiv preprint 2.KV::3305.10403 2023.
Julyan Arbel, Olivier Marchal, and Hien D Nguyen. On strict sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables. ESAMM: Probability and Statistics, 24:39-55, 2020.
Francis R. Bach and Eric Moulines. Lon-Strongly-Coneee Smooth Stochastic Approximation with Conver- gence Rate (11/n.. In NeurlPS, pp. 773-781, 2013.
2013.
Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis Testing Interpreta- tions and Rényi Differential Privacy. In AISTATS, pp. 2496-2506, 2020.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algo- rithms and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 464-473, 2014.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, pp. 635-658. Springer, 2016.
Paul F Byrd and Morris D Friedman. Handbook of Elliptic Integrals for Engineers and Scientists, volume 67. Springer, 2013.
Andrea Caponnetto and Ernesto De Vito. Optimal Rates for the Regularized Least Least-Squares Algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19), pp. 267-284, 2019.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 2/), pp. 2633-2650, 2021.
10

---

Published as a conference paper ICLR 2024
Nicholas Carlini, Daphne Ippolito, Matthew Jagiclski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint arXiv:2202.07646, 2022.
Christopher A Choquette-Chon Arun Ganesh, Ryan McKenna, H Brendan McMahan, Keith Rush, Abhradeep Guha Thakkura, and Zheng Xu. (amplified) banded matrix factorization: A unified approach to private training. arXiv preprint (xXiv22306008/5. 2023a. URL https: h/tp:v//aaiiv....aa org/ abs/2306. 08153.
Christopher A. Choquette-Choo, Hugh Brendan McMahan, J Keith Rush, and Abhradeep Guha Thakurta. Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning. In ICML, volume 202, pp- 5924-5963, 23- 29 Jul 2023b.
Michael B. Cohen, Jelani Nelson, and David Woodruff. Optimal Approximate Matrix Product in Terms of Stable Rank. In ICALP, volume 55, pp. 11:1-11:14, 2016.
Alexandre Défossez and Francis R. Bach. Averaged Least-Mean-Squeee -quan-Su Bias-Variance Trade-off's and Optimal Sampling Distributions, In AISTATS, volume 38, 2015.
Sergey Denisov, H Brendan McMahan, John Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams. NeurlPS, 35: 5910-5924, 2022.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Proc. of the Third Conf. Theory of Cryptography (TCC), pp. 265-284, 2006. URL http: //xx doi. www/r0....... 1007 11 11611118111111111111111111111111 14.
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant Matters: Fine-grained Error
Bound on Differentially Private Continual Observation. In ICML,, 2023.
Robert M Gray and Lee D Davisson. An Introduction to Statistical Signal Processing. Cambridge University Press, 2004.
Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Neng- hai Yu, and Jiang Bian. Exploring the Limits of Differentially Private Deep Learning with Group-wist Clipping, In ICLR, 2023.
William Paul Heath and Adrian G Wills. Zames-Falb multipliers for quadratic programming. In Proceedings the 44th IEEE Conference on Decision and Control, pp. 963-968. IEEE, 2005.
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. A Unifying Framework for Differentially Private Sums under Continual Observation. In SODA. pp. 995-1018, 2024.
James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2015.
Daniel J. Hsu, Sham M. Kakade, and Tong Zhang. Dimension-free tail inequalities for sums of random matrices. ArXiv Preprint, 2011.
Daniel Hsu, Sham M. Kakade, and Tong Zhang. Random Design Analysis of Ridge Regression. Found. Comput. Math., 14(3):569-600, 2014.
Daphne Ippolito, Florian Tramèr, Milad Nasr, Chiyuan Zhang, Matthew Jagielski, Katherine Lee, Christo- pher A Choquette-Choo, and Nicholas Carlini. Preventing verbatim memorization in language models gives false sense of privacy. arXiv preprint a0X 2022.
11

---

Published as a conference paper at ICLR 2024
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The Price of Differential Privacy under Continual Observation. In ICML, pp. 14654-14678. PMLR, 2023.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. Markov Chain Theory Approach Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares). In FSTTCS, volume 93, pp. 2:1-2:10, 2017a.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Mis- specification, J. Mach. Learn. Res., 18:223:1 -223:42,, 2017b.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating Stochastic Gradient Descent for Least Squares Regression. COLT, volume 75, pp. 545-604, 2018.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Prac- tical and private (deep) learning without sampling or shuffling. In ICML, 2021a.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji,
Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' D'Oliveira, Salim EI Rouayheh, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Fari- naz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song. Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Ad- vances and Open Problems in Federated Learning. Foundations and Trends in Machine Learning, 14 (1-2):1-210, 2021b.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint Sit::20011083611 2020.
Anastasia Koloskova, Ryan McKenna, Zachary Charles, Keith Rush, and Brendan McMahan. Convergence of Gradient Descent with Linearly Correlated Noise and Applications to Differentially Private Learning. In NewrlPS, 2023.
Dan Kucerovsky, Kaveh Mousavand, and Aydin Sarraf. On some properties of Toeplitz matrices. Cogent Mathematics, 155475, 2016.
Sneha Kudugunta, Isaac Caswell, Biao Zhang, Xavier Gareia, Christopher Choquette CChot, Katherine Lee, Derrick Xin, Aditya Kusupati, Romi Stella, Ankur Bapna, et al. Madlad-400: A multilingual and document-level large audited dataset. arXiv preprint arXiv:2309.04666 2023.
Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal, 24:757-781, 2015.
Xiyang Liu, Prateck Jain, Weihao Kong, Sewoong Oh, and Arun Sai Suggala. Near Optimal Private and
Robust Linear Regression. arXiv preprint a:X1v:2301.1327,, 2023.
Per-Gunnar Martinsson and Joel A Tropp. Randomized Numerical Linear Algebra: Foundations and Algo- rithms. Acta Numerica, 29:403-572, 2020.
Brendan McMahan and Abhradeep Thakurta. Federated learning with formal differential privacy guarantees. Google Al Blog, 2022.
12

---

Published as conference paper ICLR 2024
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning Differentially Private Recur- rent Language Models. In ICLR, 2018.
Stanislav Minsker. On some extensions of Bernstein's 's inequality for self-adjoint operators. Statistics & Probability Letters, 127:111-119, 2017.
Nelson Morgan and Hervé Bourlard. Generalization and parameter estimation in feedforward nets: Some experiments. Advances in neural information processing systems, 2, 1989.
Kamyar Moshksar. On the Absolute Constant in Hanson-Wright Inequality, arXiv preprint, 2021.
Alan Oppenheim, Alan S Willsky, and Nawab. Signals and Systems, volume 2. 1997.
Antonio Orvieto, Hans Kersting, Frank Proske, Francis Bach, and Aurelien Lucchi. Anticorrelated Noise Injection for Improved Generalization. In ICML, pp. 17094-17116, 2022.
Krishna Pillutla, Yassine Laguel, Jérôme Malick, and Zaid Harchaoui. Federated learning with superquantile aggregation for heterogeneous data. Machine Learning, pp. 1-68, 2023.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMMaan Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy ML: A Practical Guide Machine Learning with Differential Privacy. Journal of Artificial Intelligence Research, 1201
2023.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H. Brendan McMahan. Adaptive federated optimization. CoRR, abs/2003.00295, 2020. URL https: arxiv. org/ abs 2003. 00295.
Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through geometric functional analysis. Journal of the ACM (JACM), 54(4):21-es, 2007.
Mark Rudelson and Roman Vershynin. Hanson Wright Inequality and Sub-Gaussian Concentration, 2013.
Adam Smith and Abhradeep Thakurta. (nearly) optimal algorithms for private online learning full- information and bandit settings. In Advances in Neural Information Processing Systems, pp. 2733-2741, 2013.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248.
IEEE, 2013.
Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. (Nearly) Optimal Private Linear Regression for Sub-Gaussian Data via Adaptive Clipping. In COLT, volume 178, pp. 1126-1166, 2022.
Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher A Choquette-Choo, Peter Kairouz, Brendan McMahan, Jesse Rosenstock, and Yuanbo Zhang. Federated Learning of Gboard Language Models with Differential Privacy. arXiv preprint a30iv:2305. 2344553 2023.
13

---

Published as conference paper ICLR 2024
Appendix
Table of Contents
A Further Background on DP-FTRL
A.1 DP-FTRL: The Matrix Mechanism for Private Learning
15
A.2 Differential Privacy in Adaptive Streams
16
B Asymptotics of DP-FTRI for Mean Estimation
16
C Asymptotics DP-FTRI. Linear Regression
C.I Setup, Assumptions, Notation
C.2 Proof of the Upper Bound the Asymptotic Suboptimality
(eoormmaiyyy....................
23
C.3 Proofs of Lower Bounds the Asymptotic Suboptimality
29
C.4 Asymptotics of v-Noisy-FTRL.
32
C.5 Asymptotics of Anti-PGD
34
C.6 Effective Dimension and the Stable Rank
34
C.7 Proofs Technical Lemmas
35
D Finite-Time Privacy-U Utility Tradeoff's for Linear Regression
D.I Setup, Assumptions, and Notation
................................
36
D.2 High-Prohability Bounds Noisy-FTRI.
38
D.3 Expected Bounds Noisy-FTRL.
45
D.4 Privacy-Utiliy Guarantees of DP-FTRL
48
E Proofs for General Strongly Convex Functions
E.1 Proof Theorem 3.1
F Technical Definitions and Lemmas
53
F11
Linear T'mee-Invaian (LTT) Systems
53
F2
Stationary Covariance of Stochastic Gradient Descent for Linear Regression
54
F3
Concentration of Measure
55
E4
Review of Elliptic Integrals
F55
Useful Integrals
F6
Other Helper Results
G Empirical Details
60
G.1 Image classification
60
G.2 Language modeling
60
14

---

Published as conference paper ICLR 2024
A FURTHER BACKGROUND ON DP-FTRL
In this appendix, we give detailed background of DP-FTRI,, and its exact notion of differential privacy.
A.1 DP-FTRL: THE MATRIX MECHANISM FOR PRIVATE LEARNING
The DP-FTRL algorithm (Kairouz al., 202 Denisov al., 2022) is obtained by adapting the matrix mechanism, originally designed for linear counting queries (Li et al., 2015), to optimization with a sequence
(go..... .......:50 :.....-9r-11 9r-1) of gradient vectors.
Algorithm gives a detailed description of DP-FTRL. We give an alternate description of DP-FTRL with invertible dower-triangee
noise coefficient matrix B E RTxT. Denoting C' B-1, the iterates of DP-FTRI. are generated by the update
01
00
gu
WO
BB
C
+
(11)
OT
OT-1
gT-1
WT
where 17 a learning rate and we ~ NN(0 I2 Ia) i.id. Gaussian noise with a noise multiplier ddp and G' the &g clip norm.
Following prior work, we also refer to B as the noise correlation matrix as the effective noise that is added the optimization is the i.i.d. noise (wo,.... wT-1) which are linearly correlated by the rows of the matrix B. It is also common in the literature to refer to C' as the encoder, while B is referred to as the decoder.
This privacy of (11) can be seen as a postprocessing of single application of the Gaussian mechanism. Let G. W E Rxxd denote the matrix where each row is the gradient Si (and respectively the noise w:). Then, (11) effectively the postprocessing of one run of Gaussian mechanism CG + W. Under a neighborhood model that can change one row of G. it can be seen that the maximum sensitivity of this operation max, I| (Denisov al., 2022). This sensitivity logic also holds for adaptively chosen gradients; postpone formal description to Appendix A.2.
Connection to the exposition in prior work: Prior work introduced DP-FTRL differently. Letting A E Rxx denote the lower triangular matrix of all ones, update (11) can also be written
0
0o
go
Wo
B
+
(12)
0r On
9T
WT-1
where B AB. The equivalence between (11) and (12) can seen by multiplying (11) by A, which
also equivalent taking the cumulative sum of the rows of matrix. In this notation, the objective from (3) used in previous work to find the matrix B can equivalently written as
( - 1 |
DP-FTRL with Toeplitz matrices: We focus on the class lower- trianttri and Toeplitz matrices B. That
is, [ B for all t 2 t' where B (3p. ... 3r-1) is the first column of B, In this case, (11)
'This implies that B 1 also lower-triangular and Toeplitz (Kucerovsky al., 2016, Prop. 2.2 & Rem. 2.3).
15

---

Published as conference paper ICLR 2024
reduces to this simple update:
t 3,
0(+1 = 17 9t +
(13)
r=0
This lets us study DP-FTRL as time-invariant stochastic process and characterize its stationary behavior.
A.2 DIFFERENTIAL PRIVACY ADAPTIVE STREAMS
We consider learning algorithms operating streams of gradients go- 91.-.. Rd_ We consider differential privacy (DP) under the "zero-out" notion of neighborhood (Kairouz et al., 2021a). Two streams G (go.-- -.00-----3300 9T- and G' (9h....- ...-. -r-1) of length 7 are said be neighbors if 9. 9² for all positions S T except possibly one position where one of 9: g is the zero vector.
Neighboring streams:
The zero-out neighborhood is standard in prior works on DP-FTRL (e.g. Kairouz et al., 2021a; Denisov al., 2022). For a further discussion of different notions of neighborhood, refer to (Ponomareva et al., 2023, Sec. 2. 2.1.1). This guide suggests that the semantics of the zero-out neighhorhood are roughly the same that of the usual add/remove notion of neighborhood.
DP with adaptive continual release: It is customary to formalize DP with adaptive streams as privacy game between mechanism M and a privacy adversary A. This is known the adaptive continual release setting (Jain et al., 2023). The game makes a binary choice b E {0. 1} ahead of time this remains fixed throughout and not revealed either M A. Each round consists of four steps:
.M sends the current model parameters 0g to the adversary A:
generates two gradient vectors 9t. g (e.g. as (0,;; 2,) for 2, Pdata or simply the zero vector);
. the game accepts these inputs if the partial streams (go.... .g......9)) 9t) and (go....,g)) .!) are neighbors; M receives 9t b else g'-
DP in this setting requires that the adversary cannot infer the value of b, i.e., the distribution of 0o.r lb 0 to be "close" to that of bb = (where the definition of "closeness" depends on the DP variant). For instance, (c, 6)-DP (Dwork al., 2006) requires for each E {0, 1] and any outcome set S that
Pr 6) exp(E) PO E S b) 8
Similarly, p-zCDP (Bun & Steinke, 2016) in this setting requires that the Rényi a-divergence between the distribution Po of 0o = 0 and the distribution Pi of 0o.r 1 are close:
(PoP S pa
for all a (0, oo). Following standard arguments (e.g. Balle et al., 2020), p-zCDP in this setting implies (Es, 6)-DP with
< inf a>l
pa
a-1 log
log(1 a -a-
ax
DP-FTRL satisfies zCDP guarantee described in Theorem 1.1 in $1. This guarantee is equivalent to the one obtained by interpreting (11) (1) as the postprocessing of one run of the Gaussian mechanism CG + W.
B ASYMPTOTICS OF DP-FTRL FOR MEAN ESTIMATION
We now prove Theorem 2.1 mean estimation.
16

---

Published as a conference paper ICLR 2024
Proof of Theorem 2.1. We rewrite the iterates of DP-FTRL as linear time-invariant (LTI) dynamical sys- tem, whose stationary variance can be analyzed in the Fourier domain directly.
Notation: Since [0) | S and G 2 there is no gradient clipping. We consider a mean-
adjusted version of the learning dynamics: let 6, = 0, [[ and uy = -x-B[el, This allows us to reason
dnd
about the deviation of the parameters from the true mean E[a]; indeed, it turns out that lim B[ö,] 0. The objective we optimize for can now be succinctly written as lim, E[6,]-
LTI System: Our next step is to write this LTI system (see Appendix F.I for review). Thus, the sequence (6 produced by (2) evolves as
8.41 = (1 -1-170 1) + nosd - do G Σ
3, W,- T=0
t= 0,1.....
(14)
This is an LTI system with input æ; = (wy: w²) E R2 and output y: = [oe] E R!. We can verify its asymptotic stability by examining the dynamics under zero inputs: U, 0 and w, 0 for all t. This gives 5: = (1 ') + as t + co. Thus, this system is asymptotically stable, Further, we can also get from taking expectations that E[ (1 7) 80 O. Thus, our objectíve Foo (B) lim B[ō is the limiting (stationary) variance of 5,-
To invoke results from the LTI literature, it convenient re-index time to start from -o so that the behavior at f = 0 describes the stationary behavior. Hence, the dynamics can be replaced by
8c+1 = (1- + 7/7 uy dp > W VtEW
(15)
where Z denotes the set of integers and the objective can taken to be (B) E[
Transfer function of the LTI system: The transfer function G(w) of the LTI system (15) is a complex matrix of shape 1 (see $F.1 for definitions), which can be written as
G(w)
1- 11-
17 B(w) 7 exp((x) (w)
(16)
The transfer function has the property that for any input sequences ur and we with DTFT (ww) and Z(w),
the output sequence satisfies Y (w) = G(w) (U(w)
Z(w)
Stationary variance of the LTI system: The stationary variance lim E[6 admits a nice closed form expression in the Fourier domain since its inputs are white noise. In particular, we is i.i.d. in each step and independent of the DP noise wa, so that the power spectral density of the sum of these two noise sources is simply the sum of the power spectral densities of the individual sources; the resulting expression is summarized in Theorem F.2.
We first calculate the input covariance is
Σ
E sr 30 ax
GZOZ
(17)
We can then use Theorem F.2 from $F.1 obtain an expression for the stationary variance F&e (B) [E(b]
(B) = 2T [" G(w) du = 2n f
[B (w) 22
2p Toc (B) + o dw.
|1 - 77 exp (iw) 12
17

---

Published as conference paper ICLR 2024
Note that above G(w)* denotes the conjugate transpose of the complex matrix G(w).
Optimizing for the correlation in frequency domain:
The dependence of Foo on B is via the first term:
112 B (w) 2 G2
2p 7o0
(5)
2p
(L,
|1 11-1- exp (iw) i dw ((,BB())))
B (w) 12
dw
(18)
2T
1 11-11 exp (w))
4x
The stationary variance's dependence on in (18) a product of a linear function of [B and B The former comes via the variance and the latter through the sensitivity You (B) via (5). The optimal value of B must balance these two considerations. By the Cauchy-Schwand inequality, the product is minimized when
B* (w) 2
B (w) Iv1 17 -exp (iw)),
(19)
- exp (iw) 1
[B)
and the minimum value is equal to
1 G d
(
dw
4m
exp (iw)
The proof of the error bound now follows by computing and bounding the integral I exl/ll-n-exp(xx)) This can be bounded via reductions to standard integrals whose asymptotics are known (see Lemma F.15 and Property F.10 from $F.4). Similarly, Corollary C.5 can be used to bound the o d term in (17).
Optimal correlation in time-domain: Next, we derive the time-domain description by taking (*(w)= = V -1 77) exp(- -w) (which amounts to fixing a phase (19) above). We use the Maclaurin series
expansion vI Ei=o (2(3)=² 2f of the square root function to get
(w(w)= = E
11)² exp(-iwl).
Comparing this to the definition the discrete-time Fourier transform (w) Ei 87 exp( sist gives the claimed expression for 3*.
Note also that the optimal correlations scale as | (t-
C ASYMPTOTICS OF DP-FTRL FOR LINEAR REGRESSION
The goal of this section is to prove Theorem 2.2. The proof relies heavily on the following matching upper and lower bounds on the stationary error of Noisy-FThe -FFy with any noise correlations 33 in the frequency domain using its discrete-time Fourier transform (DTFT) B as:
[ [B(w) dw dw))
Fx Fx = θ (10 Tr H
G
(20)
where the function h : |_ T| + depends on the eigenvalues Ai..... da the input covariance H:
Xy h(w)= exp (ww) - n/,1p²
(21)
The outline of the section is
18

---

Published as conference paper ICLR 2024
Table 4: Asymptotic suboptimality of Noisy-SGD and Noisy-FTRL for linear regression with Gaussian inputs based on the cigenvalues Å of the Hessian H. We give the bounds in terms of the learning rate dimension d, the effective dimension deff Tr [H] / ll. and the noise variance p representing the privacy level. We take G and || w.l.o.g. Noisy-FTRL is always better large dimension small learning rate r).
Eigenvalues of H
Effective dim. dat Noisy-SGD
Noisy-FTRL
Ratio of Noisy-FRRL Noisy
d =1
d
ndp
dp (og"(2))
17 1lg
d 1/VE
vd
ndpp1
/pp log log²( (
va lgg(()))
A = k (a <1
d'-a I-a
-dpp
(1 (1-a))+t)) 1/ d= o (d/w))
[1 (1 log
d 1/k
log d -dp
pp" (og
log
0 = 1/1²
constant
-dp
11"p~1oo"" log"(
log log
A k (a 1)
-dp-11
np log? n-T
a²
a² h-
y log?
Appendix C.I: Setup, including notation, and assumptions.
Appendix C.2: Proofs of the upper bound of (20), specifically Theorem C.15 (sce also Theo-
rem C.14 for the time-domain description).
Appendix C.3: Proofs of the lower bound of (20), specifically Theorem C.18.
Appendix C.4: Asymptotics of u-Noisy-FTRL.
Appendix C.5: Asymptotics of anti-PGD (see Table 2).
Appendix C.6: Effective Dimension and its Connection to the Stable Rank.
Appendix C.7: Proofs of intermediate technical results.
The separation between Noisy-SGD and D-Noisy-FTRL is further illustrated in Table 4. Following common practice (c.g. Caponnetto & De Vito, 2007), we compare the rates for various regimes of eigenvalue decays for H.
C.I
SETUP, ASSUMPTIONS, AND NOTATION
C.1.1 SETUP
Recall that wish minimize the objective
F(0) (x [(V- (0, 2))
(22)
Stochastic gradients: Given (x, y) ~ dataa- the vector
g = (x @ x) yz = (x x0 (0- 0.) - -xx
is a stochastic gradient of F at i.c., E [gg = (F))).
Noisy-FTRL Iterations: We specialize the Noisy-FTRL algorithm with Toeplitz noise correlations. Let T denote the number of iterations and 3.r (Bo...,, -r 1) denote the first column the Toeplitz matrix B (o)) RTx Starting from given O, E Rdd Noisy-FTRL samples fresh input-output
19

---

Published as conference paper ICLR 2024
pair (It, Mc) data and noise w,
D++ 0, - ((z, @ 2,)0; - y,ιz,) 1)
Br w
(23)
7=0
Recall that the sensitivity (g) equals to the maximum columns norm of B B-1 (Toeplitz(3))
TT
max L
B
(24)
where 6, = (I(j = = E R a standard basis vector. Note that the submatrix B
00m of the
first m rows and columns of B-1 equals Bialitt(BB...,,mm-111). Thus, the sensitivity (x( an increasing function of t always.
Infinite-time limit of Foisy-FTRL: We study the Noisy-FTRL error under the limit T - with infinite sequence 3 = (Bo, .... .) of weights.
It is also convenient to re-index time to start from -00 and consider the sequence (0) produced by analogue of Equation (23), which reads
θ 0++1 = 0, - 77 ((x, @ x, - y,,x,) 17
3r w
(25)
0=0
Note that this includes a summation over all previous DP noise (w=) For this sum have finite variance, we require Σx= 3 oo that 3 e e,, the space of all square-summabll infinite sequences. We will assume this holds throughout.
Sensitivity in the infinite limit: We define the sensitivity (() by considering the linear operator B Toeplitz(3) as the convolution operator [Bw]; = -r= 3, w, on input w = (w,), Let B-1 be the inverse operator to B, assuming exists. Note that the column norms B ---lezl), from (24) become equal for all T co. Thus, we get that the limiting sensitivity in the infinite time fimit equals
750 (3) = B -ell2
(26)
for = Toeplitx(3) and eq = (r= E E2, eo & Range (B) then we take 7 = oo.
Frequency-domain description: Our analysis relies on the frequency-domain representation
[- x| C of [3 obtained via discrete-tima Fourier transform (DTFT) and defined
B(w) Σ Be exp(iut).
(27)
The sequence B can be recovered from B(w) using the inverse Fourier transform. Note that 3 E L is equivalent to B E L2, the space of square- qquare-integrable functions, by Parseval's 's theorem. The sensitivity (26) can be defined in the Fourier domain follows.
Property C.I. Let B(w) denote the DTFT of C2, Then, we have
1
dw
2
( = 22 B = 2T
(28)
B2w)
Proof. Let z = B B be the solution of the linear system Bz co. Let ((w) denote the DTFT of z. Since the linear operator B is a convolution with the weights of 3, this system can be expressed the Fourier domain as
B(w)Z(w)= = (eol, exp(- (iTT) = 1.
T=0
Thus, Z(w) 1/B(w). We complete the proof with Parseval's theorem: ||21| + 1 [Z(W) dw.
20

---

Published as a conference paper ICLR 2024
C.1.2 ASSUMPTIONS
We prove the stationary error bounds under relaxation of the assumptions in $2.2. Assumption C.2. The data distribution Pata satisfies the following:
(A1) Input Mean and Covariance: The inputs have mean E[ar] and covariance Efar @ a| =: H.
Further, I. X1 2 ... 2 Xa =: Jr >> O are the eigenvalues of H.
(A2) Noise Mean and Variance: There exists a 0, E R such that y = (0., x)+ +E where & is independent
of x with Big] 0 and [B|{]] S o "g.
(A3) Input Kurtosis: There exists R² < oo such that E ||=|| (x 2 xx) = R H. More-
over, for every PSD P E $ that commutes with H (i.e., PH HP). we have E
[xx & x -1)))(1H2PP1)
1/2 1/211--1111 1/2-1/22200 x)] 3 Ckurt [P] H for some Ckurt <0.
These assumptions are fairly standard in the context of linear regression. Assumption (A1) implies that the Hessian matrix of objective F(0) is H > 0. Thus, F is T-smooth and y-strongly convex. Assump- tion (A2) implies that 0. is the unique global minimizer of F and that the linear model well-specified. The upper bounds we prove continue to hold in the case where the linear model is mis-specified (i.e. & is not independent of æ)) but we still have Eg (æ: @ x)]
sgd H.
Assumption (A3) is kurtosis (i.e. 4th moment) assumption the input distribution; will momentarily show that it follows with absolute constants when x ~ (0, H). More generally. by taking a trace, we get from Jensen's 's inequality that Tr [ S R2. The case of P of the second part of Assumption (A3) has a special significance in the literature (c.g. Hsu et al., 2014; Jain et al., 2018) as Ckurt Tr [4] = Okwrd is the number of samples that allows the spectral concentration of the empirical covariance to the population covariance H.
Property C.3. i N(O, H). we have that Assumption (A3) holds with R² < Tr [H] and Ckurt S
Proof. Let z H be element-wise independent and distributed as standard Gaussian. For the first part, denote M = 1 E|[[=| [x - 1/2 [2 Hz)= 2]. Elementary properties of the standard
Gaussian distribution give
3, if j
if = j and = j if l = j' and = j else
E 122,21231
1,
=f and B[a4
0,
0,
for # jr Thus, we have M 2H Tr (H) T. This gives
1|| &
H 1/2 M/ 1/2 = + +T 3Tr (Tr H.
For the second part, let H = UA and P UUU be the eigenvalue decomposition of H, P respec- tively (since they commute, they are simultaneously diagonalized in the same basis given by the columns of Since U z has the same distribution as by the spherical invariance of Gaussians, we have,
U).
H 1/2/
H 1/2 E [( 2) 8)) = UE 2) UT. (x 1 1/2 PH 1/2 (x x))
(29)
Each off- off-diagonal entry of E & E(> @ 2) is zero since it involves expected odd powers of Gaussians. Its jth diagonal entry equals (denoting = ززززز
E
= E|,1
ok E|E 20, Tr Tr
21

---

Published as conference paper ICLR 2024
This gives [= & 2) @ =]] = 2 [ 3Tr | since M 0. Plugging this back into (29)
and rearranging completes the proof.
C.1.3 NOTATION
We set up some notation, that we use throughout this section.
It convenient rewrite the Noisy-FTRL recursion in terms of the difference :- := 0: -0. We can rewrite the Noisy-FTRL recursion (25) as
0 (I aa & x;)) + n
Σ B-w:-7
(30)
We will analyze this recursion.
We describe the asymptotic suboptimality in terms of the self-adjoint linear operator T l² + l defined by
T3) =
B j=1
Σ 1--n,
(31)
This operator is positive semi definieii as we show in Lemma C.6 below. In the finite time setting, we could represent T by the matrix
d
(1-
Σ -== ndg) 25 171s))
Σ 1 (1 m/11))
T=
Σ وj=1 (1 m)
(1=1(1- m)g)
d
<//RR We only consider step-size 0 < < 1/R², which implies that 1 - n, E (0,1) for all j.
For j 1,.... d, define T3 62 - f2 as the linear operator
[T,3], = Σ 3,(1 -(g1)
(32)
Note that [T,S], < oo always since
211B11 112
Σ 81 - (--)
00;
since 0 < 17À < 1. Thus, we have that T d プド=
j=1 T, by the bounded convergence theorem.
Further, we show in the upcoming Lemma C.6 that each T3 is PSD.
Define E3, Pa Sd as
Eg diag (((3TT,3))==,, and UZ:U
(33)
where U is the eigen-basis of H = T By definition, P3 commutes with H since PaH HP3 UAAEg)UT Further, since each T, is PSD (Lemma C.6), we have that Eg and Pa are PSD as well. We also have
Tr [Pg Tr Egl (G. 13)
(34)
22

---

Published as conference paper ICLR 2024
Define the matrix M Cdxd as
M ((1 - (ll-exp(iw)) -HH
(35)
Throughout, we assume that Assumption C.2 holds.
Preliminary lemmas: This lemma helps move back and forth between the time-domain and frequency- domain representations. See Appendix C.7 for proof.
Lemma C.4. Consider 62 and its DTFT ((w). 1ʃ0 < n < 1/2g. we have
1 (3, I
1/1 T
2T [
[B(w)) dw
|1 nu exp(tw)] $ (3))
2
Setting B(w) and B = (..). gives the next corollary.
Corollary C.5. If0 < 1 < 1/) we have,
1
n1j
dw
nd exp(iw)) S 1.
2
2
Lemma C.6. The operators T3 defined in (32) and T defined in (31) are both positive semi-definite for 7) < 1/ maxjeld Az-
Proof. Consider any B e and its DTFT B(w). We have from Lemma C.4 that
BB(w) de 11 nd exp(tw))2
2x
0 5
(B, (B,T,B),
nd
or that (B,T,3) 2 O.
C.2 PROOF OF THE UPPER BOUND ON THE ASYMPTOTIC SUBOPTIMALITY
The key tool in the warm-up analysis mean estimation (Appendix B) the use of linear time-invariant (LTI) input-output systems to relate the output covariance to the input covariance using its transfer function (see Appendix F. I for a summary). The Noisy-FTRL recursion not trivial to characterize in this manner because the update (25) is not LTI. Instead, decompose it into infinite sequence of LTI systems and carefully analyze the error propagation.
This consists of the following steps:
Part 1: Decompose the Noisy-FTRL recursion into a sequence LTI systems.
Part 2: Compute the transfer function of each LTT system.
Part 3:
Compute the stationary covariance for each LTI system from the previous one.
Part 4:
Combine the stationary covariances get the stationary error of the original iterate.
C.2.1 PART 1: DECOMPOSITION INTO A SEQUENCE OF LTI SYSTEMS
A challenge in analyzing the stationary error of Equation (30) in the frequency domain is that it is not an LTT system. Replacing æ, & a, by H in Equation (30) results in an LTI update; this system is quite similar to fixed design linear regression. However, this leads recursion of the same form as (30). We can repeat the same technique replacing H, @ x by H and repeat this process indefinitely. This proof technique has been used in (Aguech al., 2000) to analyze stochastic tracking algorithms and (Bach& & Moulines, 2013) to analyze iterate-averaged SGD for linear regression. We adopt this technique to analyze the stationary covariance of DP mechanisms with correlated noise.
error in the general case, which satisfies
23

---

choose some sequences and solve for the Published as conference paper ICLR 2024
We define sequences (0 000
00 and (6)"))==- for r 2 0 as follows:
80
0 (I { +ntEta
w
(36)
1+1 (I rH) ny( H Dt X 3t 0
for 0,
It 2 xz ) (r) (I 1jlt @ x. 0 1p H 2+1
These recursions are assumed to start at t = -0 from 0 0 5/
O for 2 0 and 0 0 for
r >> These recursions are decomposition of (30) as we define below.
Property C.7. For each iteration t and any integer 2 0. have 0¹ = -r= o + 6fm)
Proof. We prove this by induction. The base case at t = -o holds by definition. Assume that this true for some integer t. Then, we have
m
0 0i+1 (I
712 &9 a:4)
Σ
(m))
+ n 1) Σ
8y -
aatt & 0 (I
nE
Σ
8r 8-10-- = 6/+1
-=0
The idea behind the proof is to show that E inequality to bound
6 (m)
@
|(m]]
-
0 as m - 00. Then, we can use the triangle
|0/11 <
r=0
where the stationary error of the right side can be obtained from analyzing the LTI systems defined in (36).
C.2.2 PART CHARACTERIZE THE TRANSFER FUNCTION EACH LTI SYSTEM
There are two LTT systems. First, r(r) for r > is an L.T system
1 (I H/ 1/24,
(37)
with input u. Rd and output 2, Rd Second, 0 (0) satisfies satisfies an LTI system
*+1 = (I - HH 1z Mu Σ B
(38)
T=U
with inputs (u,, wi) Rd x Rd and output 2, E Rd where the weights B l are assumed to be given.
We now characterize the transfer functions of these LTI systems; see Appendix F.I for a review.
Property C.8. The LTI system (37) is G(w) M E Cdxd, where My is defined Equation (35). Moreover, this system is asymptotically slable long 0 < 1H < I.
Proof. Let (w) E 3d and (ww) E Cd be the Fourier transforms of u, and z, respectively. The transfer function must hold for any input-output sequences,
24

---

Published as a conference paper ICLR 2024
transfer functions. is convenient consider the delta spike on standard basis (up to scaling), i.e., U = ey, where & is the Dirac delta at w, and ej is the 5th standard basis vector in R This gives Z = 2ngzdw where g-)-) is the 5th column of G(.).
To move back the time domain, we take an inverse Fourier transform get un exp(iut)e, and 2; exp(twt). Plugging this into the update (37) gives and solving for gj (w) gives (w) en. Stacking these into matrix gives the expression.
If u. 0 for all t, then || < I| - nH 112 1zi112 < || ll2 since |
-n 1| < 1. Hence, | + 0.
giving the asymptotic stability of the system.
Property C.9. The transfer function of the LTI system (38)
G((w) (G(w) G' G'(w) Cdxad
where G(w)= - and G'(w) (B((w) Mu with ((w) as the DTFT of B. Moreover, this system asymptotically stable long as 0 - 1/H - I.
Proof. The expression for (ww) is the same as in Property C.8. To find G", we set the Fourier transforms
0, W = 2, so that Z = 2T6 where g-) is the j column of G"().
An inverse Fourier transform gives the time domain versions wt exp(iwl), u, 0, 2, = exp(iwl)g] (w). Plugging these into (38) and plugging in the definition of ((w) gives the expression for the transfer function. Its asymptotic stability holds similar to Property C.8.
C.2.3 PART 3: COMPUTE THE STATIONARY COVARIANCE OF EACH LTI SYSTEM
The stationary covariance of LTI system driven by white noise can be concisely described in the frequency domain. A sequence (u:) is said to be white noise process if it is mean zero and E/u,u,] = 0 for t * т.
This is true for both 0!0) as well ((()) for r > Since we care about the stationary distribution and we start at f = -o, we have reached the steady state at = 0. So, we compute E B(0 0(7).
Stationary covariance the base recursion: We first start with 0!!)
Proposition C.10. We have that E
0
(0) is equal for all > -o and is bounded as
0
2 0 (0)
1 nogga I + no² 1/2 PgH 1/2
where Pa is defined in Equation (33) and we denote 0² G2 (2p).
Proof. The input (E,0,,, w.) forms white noise sequence, since for of T, have E[g,x
3l [, = 0 (since E, for each f is i.i.d) and E[w,,(- = 0. The covariance of the input is
E B(Caaaa
El(Gi wx) 6 (E.m,, w::) =
= (E((E=TT, w:) & (E- w-)]
El 69 mn)]
for all t, 5. This further bounded by Assumption (A1) as
((E w:) @ (E,,,, wx)] 1 ago H 0
0
o²1
25

---

Published as conference paper ICLR 2024
The output covariance of the asymptotically stable LTI system (38) can be given in terms of the trans- fer function G(w) = [G(w) (ww)] characterized in Property C.9 using Theorem F.2 This gives that
0 ( equal for each & -o and is bounded as
1 2TT
E
(n M HM n My) dus
(39)
With the eigenvalue decomposition H UAUT, get M U(1 exp(iw)) UT. This gives
M U diag
1 )=1 UT. (15/111 exp((w) n7,
We invoke Corollary C.5 to say
[ M. U diag
(("" dw - exp(lw) -n,1 m3)pp) d
U
j=1
(2Tt/n) U 2 I.
x U diag
(40)
17
Similarly, invoke Lemma C.4 to compute
5 B(w)) M Midw U diag (("", dw d B(w)) (epp111eep(())) - n12pp) -12,1 d
UT
i=1
1 U diag
(TT(,,T,3//n/// j=1)
U
2TT UA 1/2 Σزイ
2m H - 1/2 1/11 1/2
1
(41)
where Eg and Ps are defined in (33). Plugging (40) and (40) into (39) completes the proof of the upper bound.
Stationary covariance of the higher-order recursion: Next, we turn to ((r)
Proposition C.11. For any 2 1, we have
E
)r) n (ntt²) ( aagd +
Ckun
R (B, (,,TT))
Proof. Follows from combining Proposition C.10 with the more general Lemma C.12 below.
Lemma C.12. For some 2 1, suppose that 0 (((-1)
.!-
)! equal for each t and bounded as
E 0 ( 0 1 al + bH 1/2 P3H 1/2 for some scalars a, 2 0. Then, we have the following.
w. xe) r (a) We have that c(()) = (H-
1) is white-noise process with
r = (aR² + bO (B,T H.
E
(b) We have that IE ( x
(r)
is equal for each t and is bounded as
(r) s m 1 n (aR2 + bOkunt (8,T3) I.
26

---

Published as conference paper ICLR 2024
( @ (r) = 0 for & of T since æt is independent of æ, and le|,, @ æi
Proof. Note that IE
H. Since
x; is independent of 0 " ! we get from the tower rule of expectations that
E (r) @ (r) = E H 2 xz:) 10!--11
0. 0!" (H - Iz @ xx)
E (H & xx) E 0g & o 0 (H @ vz)
that ) is white noise process. Its covariance can further be bounded
E S
H xy @ xz))
[aI bH 1 (H - 21 @ xx1)
1 a x (x @ ax.)
+ bE (xe @ x. x 1/2 P -1/2 @0 2it)
1 aR H + kCutt Tr [Pg) H.
where the last inequality followed from Assumption (A3). Further, note that Tr [Pa] = (3, T23 from (34).
The output covariance of the asymptotically stable LTI system (37) can be given in terms of the transfer function G(ww) Mn using Theorem F.2 as
E 0 & )
2 (aR² bCkurt (3, T3))
(40) M.HM, dw I n (aR2 + bC (0, I.
2x
Remainder Term: It remains to show that the remainder term 6, can be neglected by taking m + co.
Proposition C.13. We have lim E o (m)
x (m)
0.
Proof. Let St noise process with
(m++)) = (H- xc 2 xx) (T))
By Lemma C.12 and Proposition C.11, we have Č is a white-
(m+1)
s9 çl c(
(n
(o2
Cuur R² (8.T3) H -
as m -> Do since 7 < 1/R². Note that the update for 5!m² exactly matches that of SGD (without added DP noise), and the noise covariance is O. The statement of this result is equivalent to showing that the stationary covariance of SGD with zero residuals is zero. This observation formalized in Lemma of (Jain et al., 2017a) (see also Theorem F.3 of Appendix F). which gives for any that
Chun R22 (B.T9) )] I
E 8
mm)
1
1
(nR9ym++
[0 +
1 - nR
as m - DC.
C.2.4 PART 4: COMBINING THE ERRORS
Time-domain description: We now state and prove a time-domain description of the upper bound of Equa- tion (20).
27

---

Published as conference paper ICLR 2024
Theorem C.14. Suppose Assumption C.2 holds. Consider the sequence (0:) produced by the Noisy-FThh FTRL update Equation (25) with some given weights B E e and noise variance wt NO 2 (2)) If the learning rate satisfies < R/R we have
(x) < 1 (1-V1It)
vnlee
-2
ng
1 Ckurt (1- 1/
9 (3) (8,T3)
2p
-222.119 (1)) First, note that 7 1/R² also implies that nd, 1 for each eigenvalue X, of H. The right side is well-defined since Lemma F.17 gives
Proof. We use shorthand x²
d
2
13 <
B, (1 - $
3|
2
<000
(42)
1=1
for B E e2, Next, using Proposition C.10, Tr H - RR, and Tr [P3] = (3, 13,, we get
E
=
Tr HE o
]
< nR + +no (3,T3)
(43)
Similarly, using Proposition C.II, get for r 2 1 that
E 0/ 2 и S (n
2kure
(3, (3.T3))
sgd
R²
We can ignore the remainder term since
8
[(m)]]"
0 as m + oc, from Proposition C.13. Thus, we get
H
using Property C.7 and the triangle inequality the norm
B(u, Hu) of random vector to get
2
H
To complete the proof, we plug in Equations (42) and (43) and sum up the infinite series. We simplify the 2 result using ||æe + yll < 2| + y and use F(0)- F(O.) (1/2)ll0 0, 12
Frequency-domain description: We now state and prove the frequency domain description of the upper bound (20).
Theorem C.15. Consider the setting of Theorem C.14. If E L2, i.e. 1_, BB(w) dw < co, we have
(B) 1 (1 11/22)
-2
R dgg
Ckurt (1- 1-VVRR)
-2
1/ 12
B(w)) h(w) du.
2mp
0² G2,2 (9) 2p
Proof. We again use the shorthand
First note that
d
A
Tr H
M(w) S 1 (1 n1 - 2(1 n)y
22
n
3
28

---

Published as conference paper ICLR 2024
Thus, the right side is well-defined since
Tr [
[(w) h(w)dw -
[B(w) dw < 00
1/2
by assumption. We use Lemma C.4 to get
d
7 I 1 exp(ixs (w) -1111² π
[B()) 1d
(3,T3) E (3,T,3)
[B(w]] h(w) dw.
Remark C.16 (Contribution per eigendirection). The expression of Theorem C.15 contains sum over the eigenvalues xi.... Ad of the Hessian matrix H through the function h(w), defined in Eq. (21). Thus, the contribution of eigenvalue >3 to the error proportional to (ignoring problem dependent constants)
Err, := 1 X3 [B(w)] dw
(44)
exp (w) n
For Noisy-SGD, we have that B(w) 1, and the error Err, = @(1) evaluates to an absolute constant (details in Corollary C.5). In other words, each eigendirection contributes a constant amount the error, leading to a (d) dimension dependence in the asymptolic error.
On the other hand, as we discuss further in Remark C.23 (Appendix C.4), we have Err; S Ö(xg) for v- Noisy-FTRL. Thus, the contribution of an eigendirection reduces proportional the eigenvalues, leading to effective dimension dependence for v-Noisy-FTRI.
These quantitative results can be connected intuitively to the signal in the gradients. Let X Ad be the eigenvalues of H with X = 1. The negative gradient at each step pushes the iterates back towards the minimizer, thus mitigating the effect of the past noise. However, the signal in the gradient along tail eigen- directions is small, making it ineffective in such directions. This leads to Err, +(1) for Noisy-SGD, which can be much larger than Xj. On the other hand, the anti-correlations of V-DP-FTRL "subtract our" the previous noise, leading to Err; x >g for v-Noisy-F FTRL, i.e., improved effective dimension dependence.
C.3 PROOFS OF LOWER BOUNDS ON THE ASYMPTOTIC SUBOPTIMALITY
We now state and prove the lower bound part of (20) on the asymptotic suboptimality. Assumption C.17. In addition Assumption C.2, the data distribution Pdata satisfies the following:
(A2') Worst-Case Residuals: For (x, y) Paataa the residual & : y- x)) has variance BBga]
o² sgd'
Note that the variance of 5² holds with equality under Assumption C.17. Theorem C.18. Suppose Assumption C717 holds. Consider the sequence (0.) produced by the Noisy-
FTRL update in Equation (25) with some given weights B E e. If the learning rate satisfies 1J < R?, we have
FOo (3)
no? sgd
Tr
H
G2222
[B(W)) h(w) dw 2
17
sgd
Tr [
(B. TB)
4mp
4p
where h(w) is defined in (21) and T defined in (31). Farthermore, the minimal stationary error over all choices of B is bounded as
11"
inf
(B) 2 4
2010
sgd +
Tr [H]
3
2p
where the infimum is attained by B. whose DTFT B, verifies
( 8 1/ //Ww(
29

---

Published as a conference paper ICLR 2024
Note that we assume B E e i.c., || which we assumed for the upper bounds.
Er |3+| oo for technical reasons. This implies that , E 82
The key idea behind the proof is that the variance of 0 is no smaller than that of an LTI system with 2; @ 2 replaced by its expectation H. We can quantify this latter covariance with equality under Assumption C.17. We set up some notation and develop some preliminary results before proving this theorem.
Formally, consider the sequences (0, > and (6, )== as defined in (36) (cf. Appendix C.2.1). They
start at = -o from 000 0; and 8.") O. By Property C.7, we these satisfy 0 = 0!!) + 8
We use a technical result that 0 and ò: are uncorrelated. It is proved at the end of this section. Proposition C.19. Consider the setting of Theorem C8 We have for all that
0 (0)
8 8 (0)
We now give the proof of Theorem C.18.
Proof of Theorem C.18. We use shorthand 0²
(2222(08 2p
(8)
Since 02 = =0(0) + +5!00
we have
1 0 = E 0
2 E
00)
(45)
where the cross terms disappear from Proposition C.19 for the first equality. We can get expression for this term by following the proof of Proposition C.10: under Assumption C.17, we have that Equation (39) holds with equality. Thus, get for all t -oo that
Foo (B) Tr H
00 20 0J] =
Tr
HE
0
& [
/ (1803e)) Tr
H H dw. 1/2 + B() H
2x
(46)
We invoke Corollary C.5 to obtain
dw
Tr
dw
Σ X3
exp((w) n/2y1
/=1
d
xdj
Tr
H
n
==1
Similarly, we invoke Lemma C.4 to compute
[ [(w))2Tr H 12 MM 1/2 dw =
A
B(w)
exp(lw) n72111 dw
B(w) ((W)))(()w)ll dw 2 T = 13)
This establishes the lower bound for specific choices of (3.
30

---

Published as conference paper ICLR 2024
Now, we turn the universal lower bound. Using the expression for 7so from Property C.I, get that the lower bound from the theorem statement is
no? sgd
GP 1 ST
1B(W)2 (F110())P))
dw
( (B(W)) Ph(l))
Fx (x)
H
(47)
2
The Schwarz inequality gives us that
(L dw
(BW) Ph(w) 2 Vh(wdd
with equality attained for [B()] 1//h(w). This gives the universal lower bound on (47) over all possible choices of B (or equivalently, all possible choices of B). To further lower bound this, we use cos(w) 2 get
h(W)=
Σ 1=1
> 1+ - 1 - 2(1 - cos(w)
Tr H
1)11}
j=1
Thus, we get that (47) can be further lower bounded as
10
2
GP2
(f"
Tr
1100 sgd
G²
(B N
sgd
Tr
[
+
dw
Tr
[
+
Tr
H
2
2
2
2
8p
Missing technical proofs in the lower bound: We now give the proof of Proposition C.19, which first relies on the following intermediate result. Proposition C.20. Consider the setting of Theorem C.18. We have all t, T that
[00) 0. w,
E
Proof. For this proof, start the sequences at 0 rather than f -o. We drop the superscript to write (0)) as ò,. Define shorthand Q = mae, @ æ, and R. = H W. 8 æc. We expand out the recursion to
get
8, = Q.-1ô:-11 + 1) 10
QQ R2 20 + R
(0)
QQ-1Q:-2 Q0o +
R 0 ( + Q.
Q.-1 ..-1--1110 2,0 00..0-QQ.RR8800
The first term is zero because d0 0 at initialization. Since R2 is mean zero and independent of 0 and R2 for & > T, we have
F 6 w
E
0 69 w-
77
+ EEQ
E R2 2|
0 (00) 2 wT +
E ... E[R]BB 00 & wr
0,
giving the desired result.
31

---

Published as conference paper ICLR 2024
Proof of Proposition C.19. We drop the superseript write 0 as 6,. We prove the claim by induction. At initialization, we have 0o so the hypothesis holds. Now assume that it holds at time i.e.
E
0 2 8 0.
Next, we expand out E 0 @ 0(+1 using their respective recursions. Note that w; H -2 (e and & are each zero mean and independent all quantities appearing up to iteration (formally, they are independent of the o-algebra generated by (0!)) and 6,). This gives
Σ Br wt - 6.0) (I (1-n
(0) e+1 d-+1 =(I ,HH 0 o (I HH F
E
(48)
The first term is zero by the induction hypothesis. For the second term, we can interchange the expectation and the infinite sum by the Fubini- Fubini-Tonelli theorem since
Σ 18 E
(w-r, 0600)\
S |811 max -.....
E (wir, <00
since B1 E el and E (wrr: )
< because
E W/ (w:-r, 0! Tr E W @ 60.01
by Proposition C.20. By Proposition C.20 again, we thus get
Br Wi-r 2 0000) = Σe B, E
w 2 ] 0.
E
==0
C.4 ASYMPTOTICS OF V-NOISY-FTRL
We now state and prove the upper bound for v-Noisy-FTRR Note that z-Noisy-FTRL can be described in the frequency domain as 18 (2) | exp(iw)).
For the proof, we define : (0, 1)2 > R as the integral
exp(iw) - exp [w) dw.
I(a,
(49)
The crux of the proof relies on a precise characterization of this integral, as we will shortly see below. Lemma C.21. Consider the integral I from (49). It satisfies the following properties:
(i) For all E 10, have
I(a,a) < 5lg((8/a).
(ii For all a S b < 1/4, we have
128
I(a, <
log log(8/a)(++0(a))
49
32

---

Published as a conference paper ICLR 2024
Proof. The strategy is to reduce this integral the standard elliptic integrals and leverage their properties to get the result. We start with the first part I(a, a). We use Lemma F.15 to rewrite in terms of the elliptic
integral of the first kind ((k): / dw/ v h2 (w)) (denoted (a)). Then, we use Property F.10 which says that (k) O log v1 k²) (denoted as (b)). This gives,
( 4
vI 1 - a/2
2 log 12 - a) S 5 log O
5
I(a, ④)
(50)
2 a
Similarly, we can express I(a, b) for a * b in terms of the elliptic integral of the third kind 11(a², k), whose definition given in (96). From Lemma F.16, we have for a, b (0, 1) that
2a²
a² 63 - (1-
I(a, b) = (1 a/2)
IIaa, k) where
12 a/2)2
and k = vI- a a+) to get
- -1-2). We invoke Property F.ll to bound the behavior of 11(a2,, k) as k + +1 (i.e.
2a²
1
I(a, b) s b²(1 - a/2) V1 - a² log
(1+)(a))
-1 12
2(1 a/2)
(1 -1-b//2 b/2)² log (2 (2 - a) (1+0(a))
128 log(8/a) Ol))
49
where the last inequality holds for a S <bs 1/4.
We are now ready to prove the bounds for u-Noisy-FTRL. Proposition C.22. Consider the setting of Theorem 15 with a2 sgd = 0. Then, v-Noisy- with S qp satisfies
log² ()) p
Foo ( S C m1x (1, Ckurt) 1/
for universal constant C > O, and Ō()) suppresses polylogarithmic terms in the problem parameters.
Proof. We use C to denote universal constant that can change from line to line. We can express the bound of Theorem C.15 with our specific choice of (ww) as
d
Fxo (B²) < C' max (1, Ckur I(v, v) Σ AyI(u,))))
(51)
j=1
For the T(u, v) term, we plug in Lemma C.21 We plug and nA into Lemma C.21 get (note that its conditions are satisfied)
I(v, S log -
8 (1 + +0v))
(52)
The last term is O(v) - O(m)). Plugging in (50) and (52) into (51) and using Tr H = Σj A <
R
completes the proof.
Remark C.23 (Contribution per eigendirection). We continue the discussion of Remark 1. The proof of Proposition C.22 shows that the contribution of the j eigendirection to the asymptotic suboptimality is proportional to
Err; = XyI(V,, ndz). As long as V S Tps we get from Lemma C.21 that Err; S (A, log(1/v)). Thus, the error contributed drops proportional X3, leading to effective dimension dependence for v-Noisy-FTRL.
33

---

m2 n) Published as a conference paper ICLR 2024
C.5 ASYMPTOTICS OF ANTI-PGD
As we discussed in Table 2, anti-PGD (Orvieto et al., 2022) is special case of Noisy-FTRI. with B (1, 11,-1,0, ...... Then, we have that (Toeplitz({))) the lower triangular matrix of all ones, so we have (3) = T, or that its limiting sensitivity is infinite.
We can cireumvent the infinity by damping 3 = (1, - (1-))111, v)..,...) for some 0 < < to be decided later. In this case, have (ww) 1 - (1 14) exp(-iw). that [B(w]] = exp((xx ?? which is the analogue of E--Noisy-FTRL with a square.
Proposition C.24. Consider the setting of Theorem C.15 with aggd 0 and (1, (1,-(1- n12), 0, .)....)oor for
some À (0, 1/n]. Then, we have,
(B) = = (nG2pp (nt (nd+ Tr H ))
Further, the learning rate satisfies 17 c/ [H] and we take = (1, vI/d)....). we get
(B) 2 ((2)2 1/3 )/) 22 /dTr(H))
Proof. Let 0² ====G² G From Theorems C.15 and C.18, we get that
(1100 12'0 (
dw
(1)) dw )
FB) =
(53)
(x
1 n1 exp(
Using Lemma F.12, we have
dw
2x
(
exp (
v(2 (2) v)
For the second integral, we expand out the numerator and invoke Lemma F.12 again to get
1
1 v exp(iw)] dw
1+ (1 v)2
m74y 2(1 v) n) - n)2,)
2 F nd exp(iw)]²
12
+
where we use < 2 v S and the same for Xy instead of Plugging the two integrals back into (53)
completes the proof.
C.6 EFFECTIVE DIMENSION AND THE STABLE RANK
The stable/numerical rank srank(A) A) of a matrix defined as
||
srank(A)
0 max (A)²
i.e. the squared ratio of the Frobenius norm of matrix to its largest singular value (Rudelson & Vershynin, 2007). By comparing this to our definition of the effective dimension, we find that des H) srank 1/2)) Note that the effective dimension is also called the "intrinsic dimension" by Martinsson & Tropp (2020).
The stable rank a matrix is a continuous function while the true rank is discontinuous. Thus, is highly desirable for the error of numerical algorithm to scale with the stable rank of its matrix input rather than the
34

---

Published as conference paper ICLR 2024
true rank (Rudelson & Vershynin, 2007: Martinsson Tropp. 2020). The stable rank is thus a fundamental quantity appearing in various fields such as randomized linear algebra (Cohen et al., 2016; Martinsson & Tropp, 2020) and matrix concentration (Hsu et al., 2011; Minsker, 2017).
Our results show that D-DP-FTRL's 's eтrоr has the desirable property of scaling with the stable rank (i.e. effective dimension) of the Hessian H rather than its true rank (i.e. the problem's dimension).
C.7 PROOFS OF TECHNICAL LEMMAS
We now prove Lemma C.4.
Proof of Lemma C.4. Denote
B(w) dw
I
-1 1 - 111, - exp((ix) }2
The denominator is simply
11 exp((i n/yp =1 + (1 n2,y² 2(1 n)2,) cosw.
(54)
We expand the numerator
= [B(w)
8,
3,3, (exp(ex(((---- - 7)) + exp( -io(T - 1)))
1=0
1=0 7=0
67
Σ>>>>
3e3, cos(w(t - 7))
t=0
t=0
00
Σ
3,3, cos(w(t - T))
(55)
t= r=0
This is bounded since the Cauchy-Schwarz inequality gives
[B(w) < || <0.
Thus, we can apply Fubini's 's theorem to exchange the sum and integral to give
cos(w(t - T))
3
1 (1 n,1)²² 2211 114;) cos(w)
(=0
T=0
2T
n1,)2 - 11,))1-=1 2n
(1
17 (2 -11,)
(=0
0=
where we evaluated the integral using Lemma F.12. We 5 nn S 2 to complete the proof.
D FINITE-TIME PRIVACY-UTILIE TRADEOFFS FOR LINEAR REGRESSION
The goal of this section is establish the finite time convergence of DP-FTRL. The key idea of the proof is to establish high probability bounds on the & norm of the iterates of Noisy-FTRL and use that to deduce a clip norm that does not clip any gradients with high probability.
The outline of this section is as follows:
Appendix D.1: Preliminaries, including setup, notation and assumptions.
35

---

Published as conference paper ICLR 2024
Appendix D.2: High probability bounds the iterates of Noisy-FTRL.
Appendix D.3: Expected bounds on the iterates of Noisy-FTRL.
Appendix D.4: Connecting DP-FTRL Noisy-FTRL for the final bound privacy-utility bounds (Corollary D.14 for DP-SGD and Corollary D.15 for DP-FTRL).
D.1 SETUP, ASSUMPTIONS, AND NOTATION
In this section, we fix the precise notation and assumptions. We also give some preliminary results.
D.1.1 ASSUMPTIONS
We make the following assumptions throughout this section.
Assumption D.1. The data distribution Paata satisfies the following:
(BI) Input Distribution: The inputs have mean E E[æc] = and covariance E| @ æ] =: H. We have μI 3 H 3 LI for p, L > O. Further, H -1/22x is element-wise independent and sub-Gaussie Gaussian with variance proxy e.g. H 1/2 NO, I).
(B2) Noise Distribution: There exists a 0, E IR such that y (0., x) + +E, where & is independent of æ and gero-meat sub- Gaussinn with variance proxy agd e.g. & NO, ggd)
These assumptions are a strengthening of Assumption C.2 which are necessitated by concentration argu- ments to follow below.
D.1.2 NOTATION
As in Assumption C.2, denote R as the smallest number such that the fourth moment of is bounded as
E | 1 2 a 3 H
(56)
Under Assumption (B1), we have = O(Tr H)) always. While Tr [H] S R2 directly follows
from (56) using Jensen's 's inequality. we show that R² < 3Tr HH) in Property C.3 in Appendix C.I. It convenient rewrite the Noisy-FTRL recursion (23) in terms of the difference 0 := 0, 0-
as
0/01 = (I (I-n( E xz)) 02 + n
Br W:--
(57)
We will show in the upcoming Property D.2 that 0 0 5ad + where O, captures the effect of the initial iterate, sgd captures the effect of the SGD noise, and do captures the effect of the additive DP noise. We will define these quantities now and state and prove Property D.2 later. Note that these recursions are defined for the same sequences of input realizations (mo, ..,...) drawn from Pdata. linear model noise realizations (Co, (i.,......,, and DP noise realizations (#o, wi....).
We define the crise-free version of the DP-FTRL recursion Ô 0/ and
θ = (I - 1)( & Oz
(58)
The effect of the SGD noise the Noisy-FTRI. process can be quantified by creating a process starting from 0 with no DP noise (i.e. w, = 0):
0 sgd (I 1)(3,, xx.) 0 17 E
(59)
36

---

Published as conference paper ICLR 2024
The effect of the DP noise in the Noisy-FTRL process can be quantified by creating a process starting from 0h with no SGD noise (i.e., & = 0):
- = (I - 1) X xze) 0.
Br -
(60)
For an input æ, drawn from Pdata We define the matrix
Q I Tjlt 0t.
(61)
Note that []] = nH.
Define the linear operator P $ + $ that operates on the cone PSD matrices given by
PM E n & x - na @ x)]
(62)
where is an imput drawn from Pdata- By definition, we have E|Q, PM and by inde- pendence,
-QQ PP
(63)
This extends higher powers of as well. Finally, we will heavily use the fact that Tr [PM]]
S
(1 TT [M] for PSD matrices M (see Lemma F.18 for proof).
For each iteration t, we define the PSD matrix Σ
It-1 & x + Qc-1(a1-2 @ x Q ... + Qi-1 ... Q1 @ xo)Q1
Qi-1,
(64)
For each iteration t, we define the PSD matrix 2/ as
Σ Ver ViT
where
0=0
(65)
V1, 13,1 1 ....t.....0000 ... ... Qi-T, i B
=
D.1.3 PRELIMINARY RESULTS
The first result is a decomposition of the Noisy-FTRL process into three processes: (a) gradient descent without additive noise, (b) noise process with only noise from the linear model, and (c) noise process with only the DP noise.
Property D.2. For the sequences 0 0. 0. 0.00 defined in Equations (57) (60), have the following:
0: = 0. + 0,50 add
+ 0
(66)
0. Q Q00
(67)
0 sgd = =n (ITEt + Q1 + + Qu .. -.Q1vEE))
(68)
0h
Σ
Br WT + Q. Σ
3, wi
Q: Q (Sowe)
7=0
1=0
= -1000001-11
+ (3
9 w
+ (B, + 8 2 .- + +... P- -.- Q1)
(69)
37

---

Published as conference paper ICLR 2024
Proof. The expressions follow from unrolling their respective updates. By unrolling the DP-FTRL update (57), we get,
0 #+1 + n By W
T=U
0 1) (x15: Q10r- -1
Σ 3, --rrr + Q₁
_
By Wi-1
7=0
Q..... Q00% (x1Et -
10000)
7 Σ
Br W + Qi
Σ B, W1-1-
Q: Q Q1 (86200)
Unrolling Equations (58) (60) respectively gives Equations (67) to (69), and comparing them with the expression above gives Equation (66).
D.2 HIGH--PROBABIITTY BOUNDS ON NOISY-FTRL
The goal of this subsection is to prove high probability bound norms of the iterates of Noisy-FTRL. We require a technical convergence condition on the weights B3.
Definition D.3. sequence
(5o, .... is said satisfy Half- Exfpo Decay with parameter (0, 1)
if for all nonnegative integers T, we huve
1Bl (1 - -2 12 + 13,1(1 1) 11/2 + 13+ S (1-1))=22
(70)
for universal constant C >
Theorem D.4. Fix a constant p < and suppose the Assumption D.1 holds. Consider the sequence (0 of iterates and the sequence (g:) )r= of gradients when running Noisy-FTRL for T iterations with noise coefficients B
Bro.....B11.. DP noise w, ~ NO, o² I) of given variance" o², a learning rate n S (eR2 log(T//)) for universal constant 1. Further, suppose that B satisfies Half-Expo Decay with parameter v for some v S mu. Then, with probability at least p. we have
|00 = (1106111
nR
o2 sga
0² ||
T
log
and
|10%)12
nRR02 ogd
o² agd
17
1g:11 1/ < CR
log
R2
for a universal constant C.
We prove this theorem over a sequence of intermediate results.
D.2.1 PROOF SETUP: DEFINITION OF EVENTS
The proof strategy relies on defining some events (that hold with high probability from concentration of measure) and proving the required boundedness under those events. Consider 0 < 1 and universal constant C' from statement of Theorem D.4. We define the following events.
IIn the context of this paper, have a² G2)( /(2p).
38

---

Published as conference paper ICLR 2024
Define the event where the inputs are bounded norm as:
T-1
& :
CR log
(71)
Define event where the noise in the linear model is bounded as:
T-1
&g = n
& 2 S 20 log
27
(72)
Define the event where the of 0 agd defined in (59) is bounded
T p
Eaed
o I
C sgd Tr
sgd
log
(73)
where we define the random matrix Eddd 2z-1 X x1-1 + Q1-1 @ Q + +
Q1-1- (ar @ an) QQ ... Q--1 (see also (64)). When this event holds, we have that 0 Q: for O,..., long as v S 1/ (CR2 log(T /p)) Indeed, in this case, we have
nar & Tz = 2 I 0.
(74)
The components of the sum defining 2oed are the PSD matrices W Wt,,, defined for T St- 1 as
QQ 1Q.-1---0 (++ @ x7) Qt-1, if < t 1, W [I1-1 @ x1-1,
(75)
if
Define the event where these are bounded in trace as
cagd T-1t-1
T (1
Tr W
(--mu)=---
(76)
p
t=
Define the event where the norm of 0 do defined in (60) is bounded as
E
T-1
0
dp 2 S SCn2
0 Tr
dp
log
7
(77)
t=
where 2d is defined (65).
Define the event where the matrix V,, defined in (65) is bounded in trace:
T-1
Tdd
Σ 13x((1 (p))(T-))//) }
o = n Tr VL, V S
(78)
We show that all these events hold with high probability. Proposition D.5. Consider the setting of Theorem D.4. We have,
P (E, (Ein negd g n n n ne 2 1-6pp 6p.
Proof. We will show that each of the events holds with probability at least 1 - p and a union bound gives the desired result.
39

---

Published as conference paper ICLR 2024
Event E₁: Since 2t И 11/22 clement-wise independent and I-sub-Gausiann, have from the -hiihh inequality (Lemma F.6) that
p(1101112 > CTr H (og(1/p)) = (() Hz,) > CTr [ log(1/p)) S p- gives that (P(E) 2 - p.
Taking a union bound over / = 0, ,,..., T
Event Eg: Since & is sub-Gaussian with mean zero and variance proxy o we have,
g²
P([@) > 8) S 2 exx
2 sgd
Setting the right side equal to p/T and taking union bound over 0, ........TT gives P(8)) 2 p.
Event e From the expression for 0, from (68), we can say that 0,yd conditioned on .o...., 2t-1 mean zero and satisfies
E
0 pae = 1) F4 Q4-134-1
(Q--1 .......0 Q 20)
:M,
Eo
Using the assumption that each & is independent and sub-Gaussian with variance proxy ózd get from the Hanson- Wright inequality (Lemma F.6) again that
P
Cip Tr [M.M,
log(1/p)) TP ((E., M,G,,,M,,A.. E..) Cr Tr [M.M, log(1/D)) s p.
Next, we confirm that
Tr [,M,]] = ||xx11 112 111--1011111 .....+++Q:- ....++1-Q-.....1111111. .QQ100011 =Tr 1 Finally, union bound over t = 0, 1,11 1,...,T gives that P(ε 2 p.
Event e5ed, Markov's inequality gives
(Tr [ s) (Wirl .r -
11-pp)----- R2
8
where the calculations for the expected bound are deferred to Lemma D.9. Taking a union bound over all T(T + 1)/2 <. 2 choices of (t, T) gives IP 2 1
Event :: From the expression for 0, from (69), we deduce that
0 dp Lo. 1z-1 NO, 1/00
Invoking the Hanson- Wright inequality (Lemma F.6) and union bounding t 0,...,T T 1 gives P(E))) 1-p.
Hanson-Wright
Event edp: Markov's 's inequality gives
Σ 1Bx1(1 - m)))( 12/2
P (Tr V1,
8)
V
<
where defer the technical calculations involved in bounding the expectation above to Lemma D.10. Taking union bound over all T(T 1)/2 < 2 choices of (t, gives P(EdF) p.
40

---

Published as conference paper ICLR 2024
D.2.2 HIGH PROBABILITY BOUNDS ON COMPONENT RECURSIONS
Bound on the noise-less iterates: We start with O, from (58).
Proposition D.6. Under event EL and if S log(T/) -1 we have that 10.11 - 110/1l2
Proof. Using the fact that 0 3 Q: under & (cf. Equation (74)), we get
0
11Q Quoil12 2 - 11Q--1ll""" "IQll l2 0oll2 S 10/1l22
Bound on 0:50; We turn to 0,50 from (59).
Proposition D.7. Under events E,, Epg Eggu. and 17 S (CR2 log (T/p))
have
0 sod
C
nR²
log
3
T
Proof. Under ETed, we have
o sgd 2 S Cr)202 agd
sggd
T
Tr
log
(79)
p
We bound [E Σ r=0 Tr W
r,) for W, defined in (75). We have two bounds for Tr (W
(a) Using 0 = Q. I under E (ef. Equation (74)), we bound
Tr [ + ||Q.-1 Q Q++10711
1 14-11 1Q++1|/a==11 CR log(TTp))
(b) Under event Egdd we have the bound
T Tr Wer] <
(1 m/1) 1
p
Using the first bound for the last S iterations and the second bound for the rest, we get
T R
ygd
1 (CC
p
2 R²
t---1
(1 - -1))²
Σ
(1 - 1 <
k=0
2 R2 exp( (1p(-1
1 < - + log((Tp)))
Choosing 5 min {t 1, log
(ploR(TTp)
as per Lemma F.20 gives
Tr
sdd
CR2 log (Tg(T/p)
1 1ogo log
T
C'R²
(T/p)
plog(T/pp)
qp
a/i
for some absolute constants C, C". Plugging this back into (79) completes the proof.
41

---

Published as conference paper ICLR 2024
Bound on 0 We turn 0 from (60).
Proposition D.8. Consider the setting of Theorem D.4. (CR² log(T/p)) we have
Under events E, E2 and yf S
R P
0 S SC
log
Proof. Based on the bound on 0, from ETP, we bound Tr 2.
=E Tr [Vrr V. We bound
2
each trace on the right side in two ways:
(a) We have Tr V,r V..ll < d from Lemma D.10.
(b) Under EdP and the assumption (*) of Half-Expo Decay of /3 with parameter S 7/4, also have
T
Tr V. V. <
18 - m/)(t=k)/22
2
T2d
18 - ()(T-2)/2
CT d (1 v)
P
Using the first bound for the first 7 iterations and the second bound for the rest, we get
+ Σ CT
Tr
S (1131Rd)
(1-1
k=
CT³d (1 1)- Σ
2
S (1881())
(1- 17>1111)1-1)
p
k=
CT ce2dexp(-Vr
ST (11Bipa)
(T (T>+-1)
pv
CT2 (TT//1l.(1)))) /p118111)] Choosing 5 S {t - & log(CT2
as per Lemma F.20, we get,
Tr [x00] |
CT
|| log
T
1 log
C"
p|lB|?
where we used || 2 1301 and C, C' are some universal constants. Combining this with the bound on 0.40 asserted by Edع completes the proof.
D.2.3 COMPLETING THE PROOF OF THE HIGH PROBABILITY BOUNDS
We are now ready to prove Theorem D.4.
Proof of Theorem D.4. Under events ε,, 55gd egd respectively from Propositions D.6 to D.8. We combine them with the triangle inequality and Equation (66) of Property D.2 to the claimed bound on ||0|||2-
C2 edp _dp have bounds the norms of 0,, 0,55d 0
42

---

Published as conference paper ICLR 2024
Next, for the gradients, we use the triangle and Cauchy-Schwarz incqualities on the definition gr Zt (2,, 0() xtςe to get
|| l12 S 2 | |001111100112 2 2/ 1 c.
Plugging in the bounds on ||æe||2 and [E): from E and &g respectively gives the claimed bound on |19:11
Finally, all the events above hold with probability least 6p from Proposition D.5. Substituting p/6 for p and adjusting the constants completes the proof.
D.2.4 HELPER LEMMAS
Lemma D.9. Consider the setting of Theorem D.4 and consider the PSD matrices Wt,,, define S t-1
W [Q--1... ... Qr+1 & xz x Qc-1,
i <t-,,
21-- @ x1-1.
if
We have that T a S R²( m1))
Proof. For = we have E (iWt-ll H S R². For < tt- 1, we have by independence of each
It that
Tr [ = Tr | Q HQT+1 ... Qt-1]] = Tr [QQ Q. ... Qi-1Il
= Tr [pt-1-11]
Recursively bounding Tr (PT H) Tr (P H) < - (1- [pr-1H] H from Lemma F,18 completes the proof.
Lemma D.10. Consider Vt, as defined in (65). We have that
Tr V1. Ve.il S Σ - k)/2
Further, if the event & = ni- (Q: 2 0} holds, then we also have
2
Tr [V Vi,1
Σ 13
Proof. Since I. is fixed throughout, simply write Ver V..
We define sequence of matrices
Ao...., A, as An = I and
As+1 Bx+1 I + Qi-++K A
for k O.....T 1. We first prove the expected bound followed by the absolute bound.
Expected bound: Then, we successively deduce the following.
(a) We have A 3 + Bk 1: +... + 90Q 1 Qi- by simply unrolling the
recursions.
(b) We immediately recognize that V, A..
(c) By independence of each Q,, taking an expectation of the expression in (a) gives
k B: -
A
Σ
1=0
43

---

Published as conference paper ICLR 2024
(d) We establish recursion
ETr A & dB + 2d|
Σ
[3i1(1 nu) ( + +(1 (1- (1--)1p mT)ETrr [A
I=0
Indeed, by expanding out the square of the recursion and using the independence the æ; 's, we get
ETr [A++1 A = 1 [r( + 28x+1 Tr ((T H)
(H)EEAA Tr [P(E] A
&
S d + 2|
| Tr - ( + (1 - TTDEE [
where plugged in the expression for E [[A]] from item (c) and used Lemma F.18 bound the last term. Using 0 3 I - n (1- 7/4) gives the claimed expression.
(e) Using induction and the recursion from part (d), we prove that
2
ETr [A S
Σ
181(11 m11) 13/2
Together with part (b), this gives the desired result. Indeed, the base case holds because ETr A, = Sdd. Supposing the induction hypothesis holds for some T 1, use the recursion of item (d) to get
1,s:(1 mnll) عمية 2
ETr [A+11 Atal S Bb+1 + 2|,3++1
B311(1 mp1 8-
Σ
d
k
m/un : 2
S 1 + +|13k+1|
|3:1(1 mp1) v 411 +
1 (
k++
2
|8:1(1 7/44) ح
1=0
where the second inequality used - mp S 1.
Absolute bound: Next, we prove the absolute bound, assuming that & holds. Again, we successively deduce:
(a) We starting with A = B I + 1 + + + Qut
(b) Then, we get
Tr [Ax] < 13x + 13 [T: [r(
180l
T.. Qi-T]] S Σ
|8t.,
1=0 where we bound each of the traces by d using Lemma F.19 (since we have Qs = I under E).
(c) By a similar logic, we get
Tr [Q [Q. A A Qu-T++]
2| Tr QQ: + 2|,81 Tr [Qi-++ Q1-rth-1) + 2|36 Tr (Qr-+k ... Q.-r]
k
2d
>
//|.
1=0
44

---

Published as conference paper ICLR 2024
(d) We prove by induction that Tr [A, A d Ei= |3|1
The base case holds since Tr A d. Supposing the induction hypothesis holds for some integer
- h t
the recursion of A to calculate
Tr [ A k+1 = d. + Bk+1 Tr [Qt-++k
A
A Qt
rRk] + Tr
+r[
Qe-
1++1
2
- d + 2d|3k+1
Tr Ed
130
1=0
1=0
Finally, item (d) together with A, Vi,r completes the proof.
D.3 EXPECTED BOUNDS ON NOISY-FTRI.
Our goal this section is to prove the following finite-time convergence guarantee of Noisy-FTRL in terms of the asymptotic suboptimality.
Theorem D.11. Consider problem (22) and suppose Assumption C.2 holds. For a given starting iterate 0g Rdd weights C2, learning rate 1/R², consider the sequence (0, ) produced by the iteration (23) where we NN, o² with 0² = G (3) (2)). Then, for any t 2 0, we have,
E [F()))) F(O.) (V L exp(-nud) (F(O0) F..)) + V (3)
We start with some preliminary lemmas. The first lemma about the covariance of the noise process and a generalization of (Jain et al., 2017a, Lemma 3) to linearly correlated additive noise.
Lemma D.12. Consider the sequence (0,) generated by Noisy-FTRL starting from 0 = 0, with noise correlations B E l and learning rate 1/Rº. Under Assumption C.2, have that its covariance
S. : E (o. - 0.) (0.
0.) (0)-0))
satisfies: (a) S, 3 S.41 for all 2 0, and (b) the sequence (St) converges element-wise as Co.
Proof. Recall the notation Q: = I - 1----00aa e x; and PM E[Q, use the shorthand 0 = 0, O..
We first prove that the covariance is increasing in PSD sense and argue that its limit exists.
Part Non-decreasing noise: By unrolling the update equation and using 0 O, we get
0' 17 (11-11--11 1
Q.-1- Q10056)
-1/ 10000- 1 + Bo 10) + (Br-1I B 1.0.:++............ +B0Q.-1 -Q))
(80)
By independence, all the cross terms cancel out, so it suffices to write out the second moment of each of the terms above. For the SGD noise terms that contain Er,r, we get for т = O..... that
Next, we calculate E
0 @ 0
E (Q Qu- 12 ( (Qu-1 Q PT (E(E xx))) Tr (81)
45

---

Published as conference paper ICLR 2024
Since it is second-moment term, we have T, = For the DP noise terms, denote x 00 x x 22
Then, we have for т = 0 to t - 1 that
x² E -- 1000: ... Q 82
=B + 8
- Q!-7)
8 + 23,
Σ
3x(I H)
3x E
Q 11- Q--1)
k=0
=8,1+ + 23,
Σ
Bx(I 1H T- +2
3r31 E Q1-1-.. Q: - Q1-T+ ... Qi-1
km0
km 2m0
8 I + 23,
Σ 3x(1
H 7- +
BuBt pr-k ((I- (H) =:
(82)
By this being a second moment, we have that T = 0. Plugging in (81) and (82) into the second moment of (80), we get,
E 0 41 @
04+1
17 Σ (Tx + o²)))
E
= E 6 0
This shows that the noise non-decreasing in a PSD sense.
Part 2: Convergence of the covariance: Next, we show that the noise sequence converges. From the update equation 0'+1 = Q,0% + narks - 7) Et 3, we get
S PS, + 1 x 2 x + 17 02 Σ
B7
TI(1 - hH
3
w
- Σ
3,E
wi-r 00] (1- nH).
==0
For 0, the term E,O @ W and its transpose are both 0. For 7 > 0, we have from (80) that
w nE 1 1 + 37-2Q1-11 + + BpQt-1 Qe-r+il Elw,-r @ w,-rl
110 (B--1 + 3-- 11H) + ........ + 30 -H)---1--
Plugging this back in gives
S PS, + 7f + 02 Σ
32 + 2n 02
3r 7H)
7=0
r=1
=PS + 0000
BT (1-
(83)
7=0 k=
46

---

Published as a conference paper ICLR 2024
Next, we take trace of (83). For the first term, we get
Tr [PS.] = Tr [St] - 2r [.S.] + Tr S ac 11 @ m.)
< Tr [S,] - 11 Tr [HS.] (2 11122)
1 (1 (1-1)) Tr [S:]
where we use (a)
@ xz.
= R H. (b) 1j S 1/R2, and (c) H = pI. By assumption, we also get
that Tr [8(2> x @ ai|
I
Tr H
I 2aga R². Finally, we have using Lemma F.17 that
sgd
d
(2-
2 ndy
211
2| Tr H
ΣΣ 3
Σ
(1
-
, || = 11311
<
11Ay
j=1
Thus, we get
Tr [1+11] S (1 (1- np) [S + 2nj0 111111 Tr [
n7² R ogdd
By unrolling this out, we get uniform bound for all t:
Tr [ - j
(20² |1 Tr H + n sgd
< 00
since B E l2, For any fixed vector (v, S.v) thus has limit from the monotone convergence theorem. From this, it follows that every diagonal entry of S, converges (take u as a standard basis vector) and then every dif-diagonal entry of S, also converges (take as the sum of two standard basis vectors). This shows that S, converges element-wise.
We are now ready prove Theorem D.11.
Proof of Theorem I. Define F (3) as the asymptotic suboptimality of a process that starts from 0g- O.. We will prove the desired result with Fx ((3) in the place of (G). Finally, we will show that Foo (3) is independent of its starting iterate so Foo (B) F (33..
We first separate the effects of the noise and the initial iterate using Property D.2. We invoke Lemma D. 12 for the former and directly bound the latter. Lastly, combine them both with triangle inequality. Recall that use the shorthand 02-- := 02 0, and Qe == I -72 @ Zt.
Effect of the initialization: We first calculate
E [[ = I 2n + 2 || 21 @ x. 1 I 2mH + R I
where the first inequality follows from (56), the second since 17 S 1/
R², 1/R2,
and the third since H 2 J.
Letting F, denote the sigma algebra generated by xo, I1 we get
0 - |[] [ @0, E(Q s (1 (11-n))pp @0: | exp( (x)((nn)) | |
E
Taking an unconditional expectation and unrolling this and using μuI H LII (Assumption (B1)) gives
E
0:
S S = s exp(-nut) 106112 - μ
L exp(- 0611 ft-
(84)
Effect of the noise: Define 0, و. + T We get from Lemma D.12 that there exists PSD matrix Sxc
such that
0 0
E
0 0 < 0 0 -...
= lim E
@ 0 =: S
+000
47

---

Published as conference paper ICLR 2024
Multiplying by H and taking trace, we get,
0 f B @6
- 01 ... - lim E
Tr -H(
(85)
Thus, 0, 0% + 0- is process that starts from 0g 0, and satisfies the conditions of Lemma D.12. This in turn gives
0 s E F(Oo) F(O.)) F(O.)) S (E(F(01) ((()))F(OO)) F(O.)]
.... lim E [(O.)) - -F(O.) Tr [S
1000
(86)
which equals Fx (3) by definition.
Combining both processes: From the triangle inequality of the norm v / Blluul H. get
E
0
S
E 0
+
0 H
Plugging in (84) and (85) gives
L
(B(F((,) F(..)] S
V
exp( (nnnttnn)))))))))
0
+
Tr [H
2p
H
L exp(- (F((s) F(O.)) + Fx (B)
where the last equality followed from (86). This establishes the required statement with Fx in place F Taking
OC, that
(B) lim F(()))
1000
for any fixed y or that Foo = F irrespective of 0g-
D.4 PRIVACY-UTILITY GUARANTEES OF DP-FTRL
We now a general privacy-utility bound for DP-FTRL in terms of the asymptotics of Noisy-FTRL, with the same parameters.
Theorem D.13. Fix constant 0 < < < and suppose the Assumption D.I holds. Fix noise coefficients B T μ.. Consider the sequence (0 of iterates and the sequence (g:)T=) T-1 of gradi-
,T.... that satisfy Half-Expo Decay with parameter ni for
ents when running DP-FTRL for T iterations with noise coefficients B. gradient clip norm G =
cR max [100 02112, / VnRPoz P asgd/ log" 5/2 (r) and a learning rate p
Vp
n M min
8C2 (0) log (T/p)
and DP noise we N(0, 00,003,00 G2I) with squared noise multiplier o²p (((3)//(p)) Then, we have the following:
(a) (0,)T is p-2CDP.
48

---

Published as conference paper ICLR 2024
(b) Let & denote the event where no gradients are clipped, i.e, & -roglll S G). We have, IP(E) 2 1 p. (c) We have,
2L.
E [(F(O() F(O.)) 18)] - exp(-nut) (F((b) F(0.)) 2 (g),
μ
where (B) is the asymptotic suboptimality of Noisy-FTRL run with the same parameters.
Proof. Part (a) follows from Theorem 1.1. For part (b), we bound the gradient norms from Theorem D.4 as
RR oodd
n0
1glll2 S CR
106112
Jgd
+
GV
log
5/2
R
1
I CR
110/1l2 + V
R
aga
Jsgd R
log
5/2
T
+
G
4
(1oolles
max
CR² max
116112s
nRR20
sgd
agd
log
5/2
T
G
SG
R
where the second inequality follows from the condition on the learning rate and we take c = 4C in the definition of G for the last inequality. Thus, & holds whenever the bound of Theorem D.4 holds, we have P(E) 2 -
For part (c), consider the sequence To produced by running Noisy-FTRL with Φo 0g and the same realizations (æt, &,, w:) of random inputs, linear model noise, and DP noise. On E, we have that Φi 0, for all Thus, have,
[(F(OO.) F(O.)) (8) [ [(((())) - F(0.)) 1 (E) S (F(())) - F(O.))
since (E) < 1. This can now be bounded using Theorem D.11 to complete the proof.
We can instantiate these rates for DP-SGD and DP-FTRL. Recall that we have k. = L//p, dett = Tr (H) (H/I. /L. and R22 (TT [H]..
Corollary D.14. Consider the setting of Theorem D.13 with T large enough that T/ Toloog(T/p) > cK2 dendp. p. The final suboptimality of SGD an appropriate choice of the learning rate (ignor- ing absolute constants),
I. (F(Oe)) - F(0.)) (1)] exp (-
pT cn2 off log (T/p)
dTr H 0 0.
1
+ k deff
agd
polylog (T)
pT
pT
T
Proof. We plug in the asymptotic suboptimality bound of Noisy-SGD into the bound of Theorem D.13. We get two terms depending on the learning rate ny: the first exp(-1jcl) term and the second (n)) term coming from the asymptotic suboptimality. We balance both the terms subject the maximum bound n using
49

---

Published as conference paper ICLR 2024
Lemma F.21 get
1 - exp (- E -
pp
cRtdlog"
(T/p) (T/pp)
polylog (T')
dR. 100 - -0.11
R² do sgd
+ o ggd
μT
Rearranging the constants completes the proof.
Corollary D.15. Consider the setting of Theorem D.13 with T large enough that T/ log' (T/p)
ox dind log dand ). For v-DP-FTRL with appropriate choice of the parameter and learning rate 7). we have (ignoring absolute constants).
P
E ( - (E) & cxp (-
L
pT cRR (Ten2 dlog' (T/p) log(n? d/d)
Kdell Tr [H] @u 0, 1
odono sgd
o2
agd
Kdefff
+
polylog (T)
pl
p
T
We plug in the asymptotic error for u-Noisy-FTRL from Proposition C.22 into Theorem D.13 to get that
Proof.
L E - F(())) (E)] < exp(-pr(l)) + no 122 + 1) R²G
1
log T/
(87)
where G² as given in the statement of Theorem D.13. For our choice of 3, have ||3|| S 4 always and (3)² < 5 1og(1/mp) from Equation (50) (from the proof of Proposition C.22). Thus, the largest learning rate permitted must satisfy
1
1) log² n/
(Tddlog(T/p))
From Lemma F.22, we can ensure with a more stringent condition
pp
cRt (T/p) log (cRt' (/p)/
Finally, this is implied by imposing the requirement
7max
cRAdlog (T/p) log
R&d p
We now tune 7) minimize the bound (87) subject
Mmax using Lemma R.21. Thus gives,
pn
[[[F(OT)- -(.))))F(FF))-00 F(0.))
exp
/
cRA (T)p) log
Rid pp
polylog (T)
R | 0.11
Rt o
o² oge Ri2 P
pul
Rewriting the constants completes the proof.
50

---

Published as conference paper ICLR 2024
E PROOFS FOR GENERAL STRONGLY CONVEX FUNCTIONS
We prove the results from Theorem 3.1. Under the assumptions of the theorem, clipping does not occur in DP-FTRL so the updates can be written as
0++1 0: - ((Bu), + (g: + rix))
(88)
where
gt (0)) 8, (0,; (,) EgwPenn [f(;))))
and Wi is a random variable that, conditioned on 0,, is bounded by sggd with probability 1. Below, Ia denotes the d x d identity matrix.
Theorem E.1. À = -o be such that X 2 0 E
80
A 2
and let A denote the Discrete-time Fourier transform (DTFT) of X Let
MA (w) = A (w)) MA (w) A (w)
(89a)
A (ww) ((1 -xxp
IIa exp (kw)
Ia -nIa)
(89b)
MA (w) = (HL (A (w) + A (w))) Ia
DA (A Ia I LA (w) Ia
(89c)
|AA (w) La + LA (w) Ia
(A (w))) Id
Then, for any non-negative valued function [- π
R4 such that
-17 La
0
Ma (w) =
Vu E [-
(90)
3 (w) Ia
We have that
ΣT= 1==
00 T
1-
2012 [ (B (B) ozea) (w) dw
2d
lim I-000
E
where Segd is the power spectral density of w. In particular, if the density of 0, converges to stationary distribution, the expected value of
lim E [10. 12
under the stationary distribution is bounded as above.
Proof. We assume without loss of generality that F (0) = so that the origin is the global optimum of (else we can translate the origin to achieve this). Since g V F (0) satisfies
g L.O, μ0 g) 2 40,g-
Then, (.... -o: 91 (2....) and (..., Gy 01, 02....) in terms of their Fourier transforms θ (w) ; G (w) (Heath & Wills (2005) Eq. 27-29):
write down the following family of integral quadratic constraints relating
(
(A()) La (+ (((W))) (A + Ia
0 (w) G (w)
dw 2 0. (91)
(A" (w)
51

---

Published as conference paper ICLR 2024
Noting that from (88), we have that
-(-
(1~0sp((u)) cxp(
1 - exp (bw)
θ (w) (exp (iw) 1) - (w)) + Z (w)) G (w)
+ (w) Z (w)
where Z denotes the DTFT of Ç = Bw + w. Plugging this into the above quadratic constraint and multi- plying by 1/², we obtain
[
+ Z (ww)
( (w)) 2 (w:) dw 0.
Mx (w)
(92)
I1
0 + (w) La)
Since MA (w) 3
we obtain that
0
f
(ww))
+ (w)) Z (w)
(w))
(
(-npla
1
0
+ (w)
E
5 9
(2)
dw 20
S1
a (w))
7 (w)
10 (w) (w)
Σ 110.11
4o0
+1
S 172
\eKcK! 21+1
1im E
where v[(2] denotes the LTT operator with transfer function V (w) applied to the signal Ç.
The denominator of the final line above is the power spectral density of vx([[] (since /x([] is wide-sense stationary stochastic process). By the Cauchy-Schward inequality for random variables, this is bounded above by
2d (IB (w) Pppppp--
'22 (B) + 2aed) v (w)
where the first term in brackets is the power spectral density of Gaussian random process Bw and the second term is upper bound the power spectral density of w. Hence, by Theorem F.2, we have the desired result.
E.1 PROOF OF THEOREM 3.1
Given the above theorem and smooth convexity parameter L, we know that the asymptotic suboptimality Fxo is bounded above by
2Ld [" 2
(B)
G² G² oaed) vp (w) dw.
Now, the constraint (90) be rewritten as
(-0²
? 0
vb (w))
+T 0 )))
(A (w) + (w)")) HA* (w) LA (w)
Dd (A) + -(A(0)+A()))) (1- (pp) (iw) - z 0
1 -xp (iw)
(93)
since all the matrices involved are Hadamard products of the 2 2 matrices above and the identity matrix.
52

---

Published as conference paper ICLR 2024
Thus, for each w, vi (w) must satisfy 2 2 PSD constraint which can be rewritten as Second Order Cone Program (SOCP) constraint. Furthermore, the constraint on from theorem E. is linear constraint, Since the projection
convex set 1b, v is convex, & belongs to a convex set. Furthermore, if we take À such that \ = 0 for [T] > T maxx for some T max > 0, the constraint on can be written as
Tmax
2AO 2
Further, if we discretize to uniform grid on [-T,, n., the constraints (93) can be written as a finite collection of SOCP constraints linking vb (w) and X.
F TECHNICAL DEFINITIONS AND LEMMAS
We review several relevant technical definitions and lemmas here:
Appendix F.1: Fourier Analysis Linear Invarinva Systems.
Appendix F.2: Stationary covariance of SGID.
Appendix F.3: Concentration of Measure.
Appendix F.4: Review of definitions and useful properties of elliptic integrals.
F.1 LINEAR TIME- INVARIAN (LTI) SYSTEMS
We first review the definition and some useful properties of discrete-time Linear Time-Invariant (LTT) sys- tems. We refer to the textbook (Oppenheim et al., 1997) for more detailed description.
(x)) in some input space and an output sequence (o in an output space y is said to be LTI if satisfies two properties:
Definition F.1. An input-output system y: AA(x)) with an input sequence
Linearity: For any X X-valued sequences (1),, xx)). and scalars a1, 02,,... we have
A
Σ
Σ
AajA()ol))
Time-Invariance: For any to E E, the sequence x' defined as x/j == 2t-to satisfies Ac(x') At-ta (z).
Throughout this paper, we consider LTI systems in the Euclidean space X' = Rdd
LTI systems can viewed as linear operators defined on the Hilbert space of signals in Rd:
(xx) (wi)
RR and
|
0o
VI E
We the notation z (x:) E Le to denote entire sequence. The Hilbert space Cg is endowed with the inner product
-to- F, y:
Asymptotic stability: An LTI system is said to be asymptotically stable if its output decays to zero for any input sequence that is bounded, i.e., for which there exists T > -oo such that æ; Vt T.
LTI systems in ID: We highlight some key properties of LTT systems = dimension, i.e. X' RR. This conveys the key ideas before deseribe the extension in higher dimensions. LTT systems be described
53

---

Published as conference paper ICLR 2024
in linear algebraic notation by the action of an infinite Toeplitz matrix H Toeplitz(h) (i.c., the first column of H is h) on an element E! lze:
H
D1
H (h t)₁ 11 Z
where denotes the convolution operator. This property is represented more elegantly in the Fourier domain. Consider the discrete-tine time Fourier transform (DTFT) X - - C of x defined by
((w) = Σ It exp(-iwl)
Similarly, let (w:) denote the DTFT of 7) and G(w)) denote the DTFT of h. Then, we have Y(w) (W)). Here, known as the impulse response and G(w) is known as the transfer function.
Multivariate LTI systems: The previous concepts can be directly extended to higher dimensions and mul- tivariate LTI systems admit clean representation in the Fourier domain.
Let Dy E Rd be the input and E TRP be the output of an LTI system. The DIFT X(w) = E 3i exp(-iwt) E Cd outputs d-dimensional complex vector, and Y(w) CP similarly.
The transfer function G(w)) in this case can represented as a complex matrix in Cpxd Similar to the scalar case, the Fourier domain description of this LTI system is given as Y (w) G ((W), where the latter product is the standard matrix-vector product over complex numbers.
Variance of LTI systems driven by white noise: The Fourier-domain analysis of an LTI system (particu- larly its transfer function) helps us characterize the covariance of the output y/ as a function of the covariance of the input æt. The following theorem presents the result for multivariate LTI systems driven by white noise. Theorem F.2. Consider asymptotically stable LTI system with -a-uue inputs (xx)r= and I=- valued outputs (y,) and transfer function G(w)) Cxxd. Suppose that x, stationary white noise sequence with covariance matrix Σ E Rdddd i.e., E[x,] 0 and E[x, xx] = Σ ift and Oaxd otherwise for all t, r. Then, we have for all t >> -oo that
1
Eig yel
G(w) EG(w) dw.
2T
F.2 STATIONARY COVARIANCE OF STOCHASTIC GRADIENT DESCENT FOR LINEAR REGRESSION
We now give result characterizing the stationary covariance of SGD for linear regression (Bach & Moulines, 2013; Défossez & Bach, 2015; Jain et al., 2017b;a).
Theorem F.3 (Lemma 5 of (Jain et al., 2017a)). Consider the recursion ö, = 0 and
8
Tjzt 8 ax)) 8, + +[
for all t 2 0 where
Di are i.i.d. with mean O, covariance H. and
C. are i..dd with mean O, covariance TE(e, 6 Gt] - a² H.
Further, TE
| (a), 2 m.) = R2 H and 1 < 1/R2, then we have for all & 2 0.
n1² I
E 2 8,1 1
nR
Thhe transfer function G(w) here is not be confused with the clip norm G used in the rest of the manuscript; this section is self-contained technical reference.
54

---

Published as conference paper ICLR 2024
F.3 CONCENTRATION MEASURE
We recall the definition of sub-Gaussian random variables and list some useful concentration inequalities. Definition F4. A real-valued random variable X is said to be sub-Gaussian with variance proxy o² if for all we have
Elexp(A(X - -w)] S exppX200 o² /2)),
where = [[X] If in addition, the variance of X exactly equals o², it is said to be strictly sub-Gaussian.
The cumulants of strict sub-Gaussian random variables are closely related those of Gaussian (Arbel et al., 2020, Prop. 3.2).
Property F.5. If X is strictly sub-Gaussin with mean zero and variance o², we have E[X 0 and [| 3 = 4] Y ~ ~N(00,²))
Next, we state the Hanson-Wright inequality for the concentration of quadratic forms; see e.g. (Rudelson Vershynin, 2013).
Lemma F... Let & (Ei,...,Ea) be such that each E₁ independent and sub- Gaussian with mean zero and variance proxy 0². Then, we have for any matrix A Raddd
ofIAI| d2l| ))
12
P((E, AC) (E AEM 1) S exp
-emin
for universal constant Consequently, for any p 1/3 and symmetric PSD matrix A, we have with probability 1 that
Tr [Tr[A]] V log + +1 log !) S ['ooTTr[A]] [A] log p
(E, Ag) S Co2
for universal constants C, C".
The second part follows from the first one under the simplifications || S ||lle I Tr[A] and EE Ag) S T [A] for A PSD.
Remark F.7. Explicit values for the constant in Lemma F.6 (and thus for C. C') are known for the case when E N0,, c a 0.1457 2 1/8, C' < 8, C' < 16 (Moshksar, 2021).
F.4 REVIEW OF ELLIPTIC INTEGRALS
We recall some definitions and useful properties of elliptic integrals. We refer to (NIS, $19) and (Byrd & Friedman, 2013) for details.
The three canonical elliptic integral forms are:
i The complete elliptic integral of the first kind K : (0, 1) - [0, 00)
is
1/2
dw
K(k)
(94)
V 12 sin?
ii The complete elliptic integral of the second kind E (0, 1) [0, xc) is
E(k) = [ x2
v 122 sin (w) de
(95)
55

---

Published as conference paper ICLR 2024
(ii) The complete elliptic integral of the third kind 11: (R\(11)) x (0,
1)
R denoted conventionally
as [aa", k) where a² is allowed to take negative values. It is defined as
II(a k) = %00 /2
dw
(96)
(1 - a sin (w)) 122 sin
The corresponding integrals where - 122 sin sin (w) is replaced with + k.2 sin ain?(w) (w) also be expressed using the elliptic integrals (NIS, Eq. (19.7.2), (19.7.5)).
Property F.8. For any m E (0, 1), we have
x//
dw
K
(VI+
m
(97)
msin?
VI+
Property F9. For any m E (0, 1) and any a² E R {+1} such that a² + m of 0, we have
dw
a2 a² sin (w))
m (w)
(98)
m
(Vi
m11
a²
+ a² 1 m
K
m (Vi+m)
+
(m + a
(m a m
+ m
The next few properties are about the asymptotics of the elliptic integrals; see e.g. (NIS, Eq. (19.9.1)) for (-) and (NIS, Eq. (19.12.4) for IT.
Property F.10. For all ls (0,1), 1), we have
4
12 1-k
log V1
$ ((k)= - 1
log
S log
k2
4
v1 122
v1 k22
Property F.1. For all k; a² (0, 1), we have
(1+0 (1+0(V1122)
T(a2,k) S 1 1 V1- - kz
log
F.5
USEFUL INTEGRALS
We list several useful definite integrals in this section.
Direct Evaluation: The first one is a cosine integral divided by quadratic form."
Lemma F.12. For reals < |b| < a and an integer I, we have
clw(ww)dw
2x
[4]
a + 62
2ab cos
a²
62
The next lemma is also about rational cosine functions."
"See https::////.. wtw.:ehssstaaceeccanec.coom a/ten///11ee0 6253.
"See aattps://matee wtw.:aatt.tttaeeecaaneeeeeom com a/ 1/1255309.
56

---

Published as conference paper ICLR 2024
Lemma F.13. For scalar a, we have
[
du
2x
iflal < 1,
I-
cos(w)
100,
if [a|
The next one is similar to the previous one. Lemma F.14. We have that
dw
cos(ww +00.
Proof. We successively deduce
dw
1
dw
1=/2 dw
=2v/
400,
cos(ww) V2.
sin w 22
sin(w)
where we used that f dw/ sin(w) log csc(w) + cot(w)] + +
Reductions to Elliptic Integrals: We now list several cosine integrals that can be reduced elliptic inte- grals (see Appendix F.4 for their definitions).
Lemma F.15. For any a E (0, 1), we have
[
dw
4
v11 (v1-0
K
(1-a/2
(99)
a exp(iw)
2 2
a/2
where K()) is the complete elliptic integral of the first kind, cf. (94).
Proof. Using cos(w)
2sin (2) and the substitution w' w/2, we successively deduce
dw
di
11 a exx((iw]
V1 (1 a) 2(1 a) cos(w)
= {
dw
v a² + 4(1 - a) sin (w/2)
4 x/2
dw'
a 1 + 4 (ياي) sin (w")
Applying Property F.8 to reduce this to the standard elliptic integral completes the proof.
The next lemma handles more general case. Note that it recovers Lemma F.15 when b since 11 k)) (k) by definition.
Lemma F.16. For any a, b E (0, 1), we have
[
1 - exp(iw)) dw ex
2a²
132 0) a²(1 b)
v1- a
I1
(100)
82(1
a/2)
17(1 a/2)
1- a/2
where II is the complete elliptic integral of the third kind, cf. (96).
57

---

Published as a conference paper ICLR 2024
Proof. We assume that * b to begin and handle the case of by continuity. Denote h(a,w) w) v + a)² 2(1 a) cos(w)
á 1 exp ([w)] dw
[| a exp(iw)) exp(iw))² dw cos(w)
1 b exp(iw))
a)²
h(a, w) h(b, 2(1 a) h(a,w) w) h(b,w)²
We next add and subtract terms to make the numerator of the second term read h(b, w) to give
T 1 a exp( dw
1 + (1-a)² (11 b)3)
1 1 a
dw
dw +
(101)
1 )
h(a,w) h(b,w)2
1 b h(a,w)
From Lemma F.15, the second term above can be written as
1
dw 4(1 - a) 1- x h(a,w)
K [11 a
(102)
(1 - (2 - a)
1- a/2
The first term of (101) can similarly be reduced to the elliptic integral form with cos(w) - 2 sin (w/2) and the substitution w' w/2 as
[ h(b,w)
dw
2 abb
dw
jo
V 1 + الراال sin sini (w) (1 للدياوة sin 3 (w/
T/2
dw
ab
اييي sin (w²) (1 + الاااك sin (wا²)
This can be written in terms of elliptic integrals using Property F.9 as
/2
dw
1(1-a) a²
sin
1 (1+ swn)(w²)
1(1-b) sin sin)(w'))
b
(103)
2 a
b² aa)
K(k)
(1-b)
IIaa?,A) k),
62(1 a) a²(1 b)
a2 a) a²(1 - b))
with k VI a/(1 - a/2) and
a (2 a) a2
80 a/2)2
Plugging in (102) and (103) into (101), we find that the K(-) term cancels out, completing the proof.
F.6 OTHER HELPER RESULTS
We list several other miscellaneous useful results.
Lemma F.17. For a sequence 3 = (Bo, BI....) E la and a constant 0 S c < 1, we have
3r Be 1t <
1 1 c
|| 2
2
1=0 0=0
58

---

Published as conference paper ICLR 2024
Proof. We break the sum into powers of and use the Cauchy-Schweer inequality (+) to get
20
8, 1 = -113111 +
Σ
3r
1=0 r=0
k=1
(+)
|1 +
c* ||
Summing up the geometric series with multiplier S << completes the proof.
Lemma F.18. Consider a random vector a that satisfies E|æx] = 0, E x 2 x] = H ž μI for some
and
E
x x
@
x 3 1t2 H. Then, we have for all S 1/ Rt² and all PSD matrices M that
Tr [(T TJØ 2 x M fje 2 a)) < (1 - nn) Tr
Proof.
The left side above (call "LHS") is bounded by
LHS = Tr M [MM] + 17 Tr
| | @ x M
< Tr M 221/T [ + R
$ Tr M TTTr [HM]
$ (1 Tr [M]
where we used (a)
||0||| x
R (b) 11 S 1/12, and (c) H > pI.
Lemma F.19. For PSD matrices 0 A A
I of shape d x d, we have Tr [A, ... A..A]]] S d.
Proof. Recall the inner product (A, B) = Tr AB on the space of real matrices. Using Hölder's
inequality the Schatten p-norms, get
Tr [A Ax] ((,,, A A2)l ||Alls, | A2lls..
Here, the Schatten I-norm ||-lls, is the l norm of the singular values (i.c. the nuclear norm); this is just the trace for PSD matrix. Thus,
| Tr [Ai]] < Tr 1.
The ||. is the loo norm the singular values, i.c. the operator norm ||-112. We get,
A Azll2 ||Axl2 ... 1| S 1.
Lemma F.20. For some fixed integer 2 and constants a >> p E (0, 1), define the function
S(7) + pa
exp( exp(-ar)
For min(t 1, -1 (pp)), we have,
ʃ(f) min ( ( 1, 11 (1 + log log (100) < _ log(1/))).
59

---

Published as a conference paper ICLR 2024
Proof. The convex function ++ T+ 1 exp(-ar) is minimized T, a log(L/p) > 0 with minimum
pn
value of a (1+Hog(1/p)). Ift-1 S f.. we take f = t- 1 and f(f) = t- S f S a (L+oo((//))) O
The next lemma is from (Pillutla et al., 2023, Lemma 13). Lemma F.21. Consider a function yp [0, M[nax] RR given by
((n) = A expp(- TTTT) + By + C1 log?
mp
given some constants T/max A, A, C A,B,C>& O. IfT 2 (UTTmax)
then we have
3B
AuT
3C
Ap²T2y
((n))) S (aexp(-urmaa T)
1 log
1 VVlog
log?
pT
B
H2T2
C
for some 1), S 7max depending on A, B, H. Lemma F.22. For c 1/4, we have,
0 (9/c()))
x (1/x( S
G EMPIRICAL DETAILS
We train image-classfiictton models using the CIFARIO dataset and language models using the Stack Over- flow Next Word Prediction (SONWP) dataset available on tensorf flwoorrlloooddo low-dwtasets..
G.1 IMAGE CLASSIFICATION
Image classification has long been studied in DP ML. For example, the original DP-SGD work of Abadi al. (2016) focused on this task. We use CIFAR10 which has 50,000 training and 10,000 test examples. We evaluate and compute test accuracies on the entire test set, following the open-sourced code of Kairouz al. (2021a). We reuse the network architecture, dataset processing, and initialization strategies presented in Kairouz et al. (2021 la); in particular, the architecture we use can be found in their Table 2 (b).
Setup and Tuning: We train all mechanisms for 2000 steps using batch size of 500 and clip norm of 1. This leads to MI. training dynamics of 20 epochs and 100 steps per epoch. We performed some initial small grid searches which showed nearly ubiquitously that momentum of 0.95 (searched over the grid 0, 0.85, 0.9, 0.95) and a linear learning rate cooldown 0.05 the initial learning rate over the last 500 steps of training improved model utility for all privacy levels. Thus, we fix these settings for all mechanisms except DP-SGD, for which no momentum performed best. For each mechanism, we then run tuning grid search for the learning rate on coefficients in {1, 2, 5} on powers in [-2, 3], selecting the best mechanism for each privacy level from this interval. Final experiments are repeated 12 times in each setting and show 95% bootstrapped confidence intervals.
Some mechanisms include additional hyperparameters that specify the exact mechanism's 's structure. For example, ME is specified by both the number of steps n and the max number of participations k: We include such parameters in the mechanism name. For all mechanisms, n 2000.
G.2 LANGUAGE MODELING
Language modeling has been prominently studied in user-level DP contexts, usually in conjunction with fed- erated learning (e.g. McMahan al., 2018). DP training is important for real-world applications of language
60

---

Published as conference paper ICLR 2024
models trained on user data as these models can memorize their training data if appropriate mitigations are not applied (Carlini et al., 2019; 2021; 2022; Ippolito et al., 2022; Anil et al., 2023; Kudugunta et al.. 2023). Indeed, DP already plays an important role in this application, as evidenced by Google's 's use of DP for train- ing on-device language models (McMahan & Thakurta, 2022: Xu et al., 2023), StackOverflow Next Word Prediction contains over 10 examples contributed non-identically from 342,477 users. The goal of this task is to predict the next word given sequence of words. We use the same setup as Croqueete-CCho et al. (2023b).
We consider version of DP-FTRL that works with "generalized gradients", i.e., the client update resulting from multiple local gradient steps on client's 's data; this is a common strategy to "lift" learning algorithms to the federated learning setting (Kairouz et al., 2021b). We refer to (Reddi al., 2020) for details. All mechanisms use an & clip norm I, server momentum of 0.95, and a client learning rate of server learning rate cool-down over the last 25% rounds. Initial tuning showed that these
Setup and Tuning:
1.0. They also were favorable parameter settings. We train all mechanisms for 2052 steps and report the final evaluation held-out set of 10, 000 examples. We zero large updates whose
accuracy of the model as reported foo norm exceeds 100. We use the tuned server learning rates from Choquette-Chor et al. (2023b) for all existing mechanisms. For the proposed v-DP-FTRL mechanisms, we do not perform extensive tuning due to computational costs and instead tune the parameter to minimize the bg eπтоr (3) of the total noise added due to B (ef. Choquette- Chot et al., 2023a, Figure 11).
61


Reviews:
[{"review_id": "i3vgMZDunX", "reviewer": "Reviewer_baaJ", "summary": "This paper studies DP-SGD with correlated noise, which is called DP-FTRL. Under the assumptions of i.i.d. data samples, Toeplitz correlation matrix, and unique minimizer, the authors characterized the asymptotic suboptimality of DP-FTRL. This considers mean estimation and linear regression and provides analytical expressions for the asymptotic suboptimality in a function of learning rate and effective dimension. Throughout experiments, the authors show the effectiveness of the proposed methods in various way.", "questions": "1) Is it possible to extend the analysis to general correlation matrices $B$ instead of Toeplitz?\n2) What is the motivation to study mean estimation? Can Theorem 2.1. be extended to other problems?\n3) What is $\\mathcal{E}$ inside the expectation on page 7?\n4) How to choose $\\nu$ in general?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and pleasing to read. The motivation for this investigation is very clear. \nThe analysis done in the paper is important in private ML, and the approaches to derive the results are interesting. I found that the closed-form expression for the optimal $\\beta$ in mean estimation is interesting. It is quite surprising that the analysis of DP-FTRL on the simple mean estimation results in a better trade-off of DP-FTRL in experiments.", "weaknesses": "Most of the results are for Noisy-SGD and Noisy-FTRL, which are not DP as written in the paper. \nThis paper uses lots of assumptions, and it seems difficult to adopt the results in practice.\nI understand it is a theory paper, but it would be useful to add more experimental results as they show the practical applicability.", "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": "CL5cnzejzU", "reviewer": "Reviewer_NgBE", "summary": "This paper investigates DP linear regression and strongly convex problems. The goal is to minimize $F(\\theta) = \\mathbb{E}\\_z [f(\\theta, z)] + r(\\theta)$ while providing a DP guarantee. The authors introduce a new version of DP-FTRL named $\\nu$-DP-FTRL. Instead of independent noises, $\\nu$-DP-FTRL uses a correlated noise $\\tilde w_t = \\sum_{\\tau=0}^t \\boldsymbol{B}\\_{t,\\tau} w_\\tau$, where each $w_\\tau$ is an i.i.d. Gaussian and $\\boldsymbol{B}$ is a Toeplitz lower-triangle matrix. The parameter is then privately updated as $\\theta_{t+1} = \\theta_t - \\eta(g_t + \\tilde w_t)$, with $g_t$ representing the non-private stochastic gradient (which may or may not be clipped).\n\nThe paper sets $\\nu$-DP-FTRL against DP-SGD, comparing their theoretical guarantees and empirical performances. Theoretically, the authors provide upper bounds for the suboptimality gap $\\mathbb{E}[F(\\theta_T)] - \\inf F(\\theta)$ for both algorithms. Notably, $\\nu$-DP-FTRL attains an asymptotic suboptimality gap of $\\tilde O(d_\\text{eff}\\eta^2/\\rho)$, where $d_\\text{eff} \\le d$ is the effective dimension. This matches the existing lower bound up to a logarithmic factor and improves upon the $O(d\\eta/\\rho)$ rate of DP-SGD. Empirically, $\\nu$-DP-FTRL also demonstrates better experiment performance compared to DP-SGD.", "questions": "I'm curious about the role of $\\nu$ in $\\hat \\beta_t^\\nu$. Since $\\binom{1/2}{t}$ in $\\hat \\beta_t^\\nu$ already decreases rapidly (roughly $1/t$ if I'm correct), is it necessary to add an additional damping term $(1-\\nu)^t$? Also, $\\nu$ is currently set to some small value in the experiments, so $(1-\\nu)^t$ decays significantly slower than $\\binom{1/2}{t}$. Thus, I wonder if $\\nu$ can be dropped to save some tuning effort. How would removing $\\nu$ (or setting $\\nu=0$) affect the theoretical bound and the empirical performance?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper provides a very detailed theoretical proof supporting the empirical observation that DP learning with correlated noise surpasses that with independent noise.\n- The introduced algorithm, $\\nu$-DP-FTRL, offers a notable improvement in the theoretical utility upper bound when compared to the leading bound of DP-SGD. Notably, this improved bound is dependent on the effective dimension $d\\_\\text{eff}$, which is often tighter than the vacuous dimension $d$ and thus adapts better to the problem difficulty. Furthermore, the bound demonstrates an improved dependence on the learning rate, improving from $O(\\eta)$ to $O(\\eta^2)$, which aligns with the existing lower bound.\n- The authors utilize the Fourier transform as an instrumental analysis tool for bounding the suboptimality gap. This analytical approach is beyond my expertise, but it suggests an new perspective for analyzing the asymptotic behavior of optimization problems.", "weaknesses": "My main concern is about the privacy guarantee. The authors use a high probability bound to argue that most of the time, the stochastic gradients won't exceed the clipping norm. Consequently, $\\nu$-DP-FTRL doesn't need any gradient clipping. But I'm not sure if this meets the standard DP definition, as sensitivity might be prohibitively high in rare cases. To me, the link between the high probability result and the standard definition isn't clear. Once this is addressed, this paper has very solid results.", "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": "DapifmHNzK", "reviewer": "Reviewer_rSjm", "summary": "This paper studies optimization (e.g., SGD) under differential privacy where the noise added to gradients correlates.", "questions": "Before Eq (3) the text says that B is a Toeplitz matrix.  How shall we read B(\\omega) after Eq (3)?  B is not a function, and the righthandside of B(\\omega)=... evaluates to a complex number rather than a real-valued matrix.\n\nDoes the series \\beta_t need to satisfy any property to make the sums and limits converge?\n\nHow is \\gamma_T defined?  The text says that one can infer Eq (4) from this definition.  In Eq 4, how shall we read the superscript 2?  Does it square \\gamma_T(B) or does it square its argument B?  (In the former case, many people would write (\\gamma_T(B))^2 or \\gamma_T^2(B), in the latter case, most people would write \\gamma_T(B^2))", "limitations": "", "rating": 1, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "It is plausible that correlated noise can help in some way.\nResearching this seems a valuable contribution.\n\nIf the text (or at least the appendix) would be clear and self-contained, and if the text would make the claims fully explicit, then this may become an interesting contribution discussing several interesting issues.", "weaknesses": "Parts of the text are very hard to follow.  E.g.,\n* The text introduces the limit with T going to \\infty, without explaining how this can make sense for a bounded privacy budget (i.e., for a finite privacy budget and an infinite (large) number of iterations, an infinite (large) amount of noise should be added in every step to the gradient, making it hard to converge.\n* While Eq (1) defines f(\\theta, z) as objective function, Eq (6) seems to treat f as the derivative of the objective function.\n* The proof of theorem 2.1 cites Fourrier analysis, but doesn't make explicit what is the derivation the authors have in mind.  There is even no proof that the asymptotic optimality defined by Eq (4) exists (i.e., the limit converges), which is non-trivial as the more iterations are performed, the higher the amount of noise per iteration needs to be.\n\nThe text also is insufficiently explicit leading the reader to incorrect assumptions on what is meant.  For example, while most of the text just uses \"differential privacy\", Appendix A.2 suddenly says that instead of \"neighboring datasets\" as most machine learning literature considers, the current paper considers zero-out neighborhood, where two sequences of gradients are adjacent if they only differ in one gradient.  This is clearly not the case if we are performing an optimization and are comparing the algorithm being run on neighboring datasets, in which case (almost) every gradient will be different.  As a result, Appendix B seems to be not really proving theorem 2.1 but a variant where \"neighboring datasets\" is replaced by \"zero-out neighbors\", which changes the meaning of the theorem.\n\nThe paper is not self-contained, and a lot of terms are not even explained in the appendix.", "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)