Differentially Private Adaptive Optimization with Delayed Preconditioners
Authors: Tian Li
Manzil Zaheer
Ken Liu
Sashank J. Reddi
Hugh Brendan McMahan
Virginia Smith
Venue: ICLR 2023 poster (2023)
Keywords: adaptive optimization
differential privacy

Abstract: Privacy costs may negate the benefits of using adaptive optimizers in differentially private model training. Prior works typically address this issue by using auxiliary information (e.g., public data) to boost the effectiveness of adaptive optimization. In this work, we explore techniques to estimate and efficiently adapt to gradient geometry in private adaptive optimization without auxiliary data. Motivated by the observation that adaptive methods can tolerate stale preconditioners, we propose differentially private adaptive training with delayed preconditioners (DP^2), a simple method that constructs delayed but less noisy preconditioners to better realize the benefits of adaptivity. Theoretically, we provide convergence guarantees for our method for both convex and non-convex problems, and analyze trade-offs between delay and privacy noise reduction. Empirically, we explore DP^2 across several real-world datasets, demonstrating that it can improve convergence speed by as much as 4× relative to non-adaptive baselines and match the performance of state-of-the-art optimization methods that require auxiliary data.

Published as a conference paper at ICLR 2023
DIFFERENTIALLY PRIVATE ADAPTIVE OPTIMIZATION WITH DELAYED PRECONDITIONERS
Tian Li MMnzil Zaheer Ziyu Liu Sashank Reddi Brendan McMahan 9 Virginia Smith Carnegie Mellon University, Google DeepMind, Google Research (litian, ziyuliu, smithv]@cs cmu cmu. edu, (manzilzaheer. sashank, mwm.maanyyooggle....ooo
ABSTRACT
Privacy noise may negate the benefits of using adaptive optimizers in differentially private model training. Prior works typically address this issue by using auxiliary information (e-g.. public data) to boost the effectiveness of adaptive optimization. In this work, we explore techniques to estimate and efficiently adapt to gradient geometry in private adaptive optimization without auxiliary data. Motivated by the observation that adaptive methods can tolerate stale preconditioners, we propose differentially private adaptive training with delayed preconditioners (DP?), a simple method that constructs delayed but less noisy preconditioners to better realize the benefits of adaptivity. Theoretically, we provide convergence guarantees for our method for both convex and non-convex problems, and analyze trade-offs between delay and privacy noise reduction. Empirically, we explore DP² across several real- world datasets, demonstrating that it can improve convergence speed by much 4x relative to non-adaptive baselines and match the performance of state-of-the-art optimization methods that require auxiliary data.
INTRODUCTION
Adaptive optimizers such as AdaGrad (Duchi et al., 2011; McMahan & Streeter, 2010) and RM- SProp (Hinton et al., 2012) are commonly used to improve convergence speed in machine learning training. However, in privacy-sensiteee of noise added to the preconditioners to guarantee differential privacy (Li et al., 2022). Prior works typically address this issue by using non-sensitive auxiliary data to approximate the underlying struc- tures of private gradients (Asi et al., 2021; Kairouz et al., 2021a; Li et al., 2022). While this can boost performance, assuming access to informative public data may be unrealistic many privacy-sensitive applications. In this work, we instead ask: Can we improve privacy/utility trade-off's in private adaptive optimization without accessing auxiliary data?
applications, the benefits of adaptivity may degrade as a result
A key insight have in addressing this question is that for many machine learning problems, the gradient geometry may not change drastically during successive steps of optimization (e.g., see Figure 1, which plots successive distributions of pre- conditioner values). This presents an opportunity estimate the preconditioners used by adaptive optimizers with smaller noise, by averaging across previous iterates. To this end, we propose DP?, a differentially private adaptive method that uses historical gradients to construct delayed preconditioners with reduced noise. Despite the simplicity of this approach, we find that it can signifi- cantly improve performance in to non-adaptive baselines, all without the need to access auxiliary data. To better understand these performance gains, we theoretically and empirically analyze the method to study the effect of using delayed preconditioners, including trade-offs that emerge between the noise reduction and staleness.
epoch 10
egoch 25
epoch 40
Figure 1: Preconditioner values do not change drastically during optimization (IMDB dataset).
convergence speed by as much as 4x relative
Contributions. We propose 2P² as a method for differentially private adaptive optimization with delayed preconditioners. Unlike prior work, 2p² does not rely on auxiliary data to improve pri- vacy/utility trade-offs in private training. We provide convergence guarantees for DP² in both convex and non-convex settings, and analyze the trade-off's between delay and privacy noise. We conduct

---

Published as a conference paper at ICLR 2023
extensive experiments to showcase the effectiveness of DP?, which can significantly improve model utility for a given privacy budget across text and recommendation benchmarks.
2 BACKGROUND AND RELATED WORK
In this section discuss closely related works and set up some preliminaries. We start by dis- cussing prior work in differentially private optimization, considering the classic framework of (e, difffeeeitti privacy (DP) (Dwork al., 2006), defined as follows.
Definition 1 (Differential privacy (Dwork et al., 2006)). A randomized algorithm M is (e, 5) differentially private if for all neighboring datasets D, D' differing by one element, and every possible subset of outputs O,
Pr (r(M(D) E O) e Pr(M(D)) E +
Differentially Private SGD. Informally, DP in machine learning offers protection by masking the influence of individual examples (example-level DP, e-g. (Abadi al., 2016; Bassily al., 2014; Song et al., 2013)) or all of the examples from one user (user-level e.g. (Kairouz et al., 2021b; McMahan et al., 2018)) on the trained model. In this work, we consider example-level DP using the popular subsampled Gaussian mechanism (Dwork et al., 2014; Mironov et al., 2019) to perturb gradients ensure DP. Unless much larger batch sizes and possibly larger datasets are used, DP mechanisms often lead to significant utility drop. Extensive research has thus been devoted to investigating improved
trade-offs for DP-SGD, including various training techniques (e.g., data augmentation and large-batch training) (De et al., 2022), leveraging public data (Amid et al., 2022; Zhou et al., 2021), 1), and releasing gradient statistics via tree aggregation to reduce the amount of noise (Chan et al., 2011; Denisov et al., 2022; Kairouz et al., 2021b). These prior works are orthogonal to and could be applied in conjunction with our proposed method, which focuses specifically on privacy in the context of adaptive optimization.
Differentially Private Adaptive Optimization. To reduce privacy cost in iterative DP algorithms, natural to consider applying adaptive optimizers (e.g., AdaGrad (Duchi et al., 2011; McMahan & Streeter, 2010), RMSProp (Hinton et al., 2012), AMSGrad (Reddi et al., 2018). and Yogi (Zaheer al., ))) speed up convergence. A straightforward approach is to first privatize mini-batch gradients and then plug in noisy gradients to any adaptive updating rules (Zhou et al., 2020). However, estimating gradient moments in this way may yield preconditioners with too much noise, resulting in adaptive methods that may not have meaningful improvements over DP-SGD (Li et al., 2022). As we discuss Section 1, more recent works suggest the use of non-sensitive public information to estimate the preconditioners (or other gradient structures) (Asi et al., 2021; Kairouz et al., 2021a; a; Li et al., 2022), which may not always be available practice. Section 5.2, we empirically benchmark two baselines along this line of work and demonstrate that DP2 can perform comparably to these Mate-offthe--a methods, even though does not require access to auxiliary data. Finally, we note that previous works have explored the high-level direction of delayed preconditioners, but mainly as a compromise for computational considerations in non- non-private training (Gupta et al., 2018). In this work, instead show that staleness be leveraged to improve privacy/utility trade-offs in private adaptive optimization, and propose and analyze a novel method for delaying preconditioner computation in the context of private training.
Notation. In this work, we consider using adaptive optimization methods to solve the classic empirical risk minimization objective, i.e., ming F(w) _, - (xff;w), where E IRd and (f(a": (f(x::)))er )e(p are individual loss functions on training sample i E [n). For vectors u, E Rd we use - v for foordinate-wist addition, and u for coordinate wise division. For any vector By denotes the j-th coordinate of For example, 93 refers to the j-th coordinate of gradient gdt Finally, |o|| E Rdd denotes taking coordinate-vue wise absolute values, and || Ilas denotes the matrix norm defined as || || == Vi, M-) for symmetric and positive definite matrix M E dRdxd or a diagonal matrix with non-negative diagonal entries populated by vector M E Rd.
3 2 DELAYED PRECONDITIONERS FOR DIFFERENTIALLY PRIVATE ADAPTIVE OPTIMIZATION
We now introduce our 2 framework. While we discuss 2 in the context of a particular adaptive method (RMSProp), we note that the approach is method-agnostic in that it can generally be applied
2

---

Published as a conference paper at ICLR 2023
to any private adaptive optimization method where preconditioners calculated each iteration. As an initial step towards understanding the algorithm, we first investigate the effects of delayed preconditioness in non- non-private training in Section 3.1. We then explain how to apply this idea to construct less noisy preconditioners from prior gradients in private training in Section 3.2.
3.1 DELAYED PRECONDITIONERS IN NON-PRIVATE SETTINGS
Adaptive methods preconditioners to adapt to gradient geometry, effectively resulting in coordinate-wing learning rates. This can be advantageous for many applications, especially those with sparse gradients non-uniform stochastic noise (e.g., Hinton al., 2012; McMahan & Streeter, 2010; Reddi et al., 2021; Zhang et al., 2020). One of the key design choices of DP² is to update preconditioners less frequently and use the average of past gradients reduce noise. Our observation is that a wide range of learning problems are tolerant to the staleness of preconditioners. In this subsection, validate this empirically on the benchmark datasets considered throughout this paper.
There are potentially many ways that one could instantiate the idea of delayed preconditioner computation in adaptive optimization. Here we consider a specific algorithm, which the exact non-private version of our proposed DP² framework (Algorithm 1) introduced in later sections. The basic idea is alternate between 8 steps of SGD and s steps of an adaptive method (for simplicity we assume RMSProp as the adaptive algorithm), where s is constant larger than 1. Each time we switch from SGD to RMSProp, we average 8 past SGD gradients and use the average to update the preconditioner. The preconditioner will be used in subsequent RMSProp updates (thus being stale). As motivation for DP², we empirically show that RMSProp with delayed preconditioners achieves almost the same optimization performance RMSProp (Figure 2).
IMDB
StackOverllow
MovieLens
SGD
1.0
training l05s
RMSProp
Ioaining loss
0.6
Delayed Precond.
training
0.6
spochs
# epoccs
<pochs
Figure 2: In non- con--pivate training, RMSProp with delayed preconditioners achieves similar training loss standard RMSProp across all datasets. Final test accuracies are presented in Section 5.1. This observation provides motivation for our proposed DP2 framework for private training (Section 3.2).
As discussed in Section 2, we note that the idea of delayed preconditioning has been briefly discussed in prior work (Gupta et al., 2018) for the purpose of speeding up the computation of adaptive optimization in non-private training. Unlike this prior work, we focus on the goal of reducing noise in private training, propose an alternative method for using stale preconditioners that is more amenable to differential privacy, and analyze our method both convex and non-convex settings.
3.2 CONSTRUCTING DELAYED PRECONDITIONERS WITH REDUCED NOISE
Without access to public data or other side information, prior works typically update preconditioners based on noisy gradients at each iteration (Zhou al., 2020). For instance, a natural way to privatize RMSProp is to update the preconditioner E Rd as <- 30 + (1 ()) where / E (0, 1) moving average constant, and ğ E Rd the noisy gradient output by some standard privacy mechanism (e.g., the Gaussian mechanism). However, a drawback to this is that the noise gets accumulated at each iteration, making adaptive methods significantly less effective (Li et al., 2022).
Inspired by the observation that problems can be tolerant to the staleness of preconditioners (Figure 2), we propose to update the preconditioners less frequently to reduce noise. For instance, we update every steps using some aggregate function of recent private gradients from DP-SGD. During iterations where U is not updated, we simply apply the most recent (stale) o to precondition the gradients. In order to mitigate the noise, we average over these gradients to form pseudo-gradient g. which can be plugged into arbitrary adaptive optimization algorithms. Note that the privacy noise variance will be reduced times if average Gaussian random variables (i.e., the DP noise).
We consider the practical diagonal (as opposed to matrix) form of adantive methods throughout the paper.
3

---

Published as a conference paper at ICLR 2023
Algorithm 1: DE* Delayed Preconditioners for Differentially Private RMSprop
Input: T, batch size b, noise multiplier o, clipping thresholds C, initial model w" E Rd constant E R learning rate schedule a', moving average parameter 3, SGD cumulative aggregation step $1, RMSProp cumulative step $2
for (= 0........
do
if mod (81 + 82) then
Reset accumulator G +
i mod (81 + 82) = 81 then
Update moment estimates as u + Bu + (1 (s1)
Reset accumulator G - 0
Uniformly randomly sample mini-batch B with size from private training data
Get individual gradients for sample E B: g+ + VV(x"; w²)
Privatize the (preconditioned) gradients using the Gaussian mechanism:
giv D (N(00,00))
g
+
Σ clip WEB
if mod (s1 + 82) < 81
where
D
Vu+
otherwise.
Accumulate the private gradients gr G + G +"' Update model parameters wt
10
11
w+ t- w² - aa'
12 return T
DP2 is summarized in Algorithm 1. For simplicity of presentation, we assume RMSProp as the adaptive method (denoted as DP²-RMSProp) throughout this section. However, our framework can be generally applied to other common adaptive methods (see Appendices C.3 and D). The high-level idea alternate between 8 steps of private SGD and 82 private RMSProp steps, and use averages of $1 SGD gradients (i.e., average of the accumulator G E R to update the preconditioner v. Next, we discuss some key components of our algorithm.
Order of privatization and preconditioning. Given private preconditioner there are generally two choices to perform adaptive optimization over the raw gradients "ge generated from mini-batch B at the 1-th iteration.
1. First privatize gradients with clipping threshold C1, then precondition noisy gradients with /o + where is small constant:
Σ
clip (gt,))) +N (0, (Vo+te)
b
VEB
2. First precondition gradients with V e, then privatize the output with clipping threshold Cz:
g" - b
clip (9 (Vu C2) + +N Σ VE
The difference is that the privacy noise in the first choice may be scaled in an undesired direction, <((0 with less noisy estimated V (perfect estimation removing all privacy noise in the Vote
extreme case) would amplify the noise (00, o2, o²C²) on informative coordinates (i.c., coordinates with smaller preconditioner values), which consistent with the argument made in Li et al. (2022). We empirically compare the two options and show that the latter gives better performance (Section 5.3).
is critical to average noisy gradients to construct a cleaner estimate of the preconditioner (Line and 10 in Algorithm 1) and apply it for adaptive optimization (Line 9). As these two steps access raw gradients twice, we need to privatize them separately. Unfortunately. the privacy budget would accumulate with each query the raw training data. Hence, we the private SGD gradients for both
4

---

Published as a conference paper at ICLR 2023
the model update and the preconditioner estimation. This results in hybrid method that alternates between private SGD and private adaptive optimization steps. Note that to get an unbiased estimate of the true delayed preconditioners, we can correct the bias in (G* /s1) (Line 5) by subtracting the s²c² privacy noise variance term 5,67 out of (G*/s1 (s)),, But this value is usually very small and negligible in practice. While in principle, non-adaptive and adaptive updates can take different numbers of consecutive iterations, in our empirical evaluation, we simply set $1 82, and find that this works reasonably well across all datasets (Section 5).
Privacy guarantees. From Algorithm 1, we see that at each iteration, we access raw data and pass them through the privacy barrier once (Line 9) to generate private gradients 5f with the same noise multiplier a and batch size b, and the preconditioner only accumulates already differentially private gradients. Since the final model is composition of these private releases (noisy gradients), Algorithm (or DP² in general) achieves the same privacy guarantces as standard DP-SGD training under the same training settings. For completeness, formally state the privacy guarantee below.
Theorem (Privacy guarantee of Algorithm (Abadi al., 2016)). There exist constants e1 and C2 such that for any & < c/bTT/n², Algorithm / is (c, -)differeenl private for any 8 >> 0 if (11
In practice, we use Rényi differential privacy (RDP) for the subsampled Gaussian mechanism accountant (Mironov et al., 2019) to compute the actual e's reported in the experiments (Section 5).
CONVERGENCE ANALYSIS
In this section, we analyze Algorithm for both convex and non-convex problems. We aim study the convergence properties of DP² and investigate the trade-offs between delay and privacy noise. In doing so, key challenges are introduced by alternating between adaptive and non-adaptive updating and through the staleness of preconditioners.
4.1 CONVEX CASES
For convex functions, we define the optimal model w" as w" E arg min, F(w). First we state some assumptions (apart from convexity) that are used in the analysis.
Assumption 1. There exists a constant Rt such that I| - w S R for any iteration t.
Assumption 2 (Bounded stochastic gradient norm). There exists constant C such that || for any i E [n)] and iteration I.
S
Assumption 1 (bounded domain across all iterations) commonly used in adaptive optimization literature (Asi et al., 2021; Levy et al., 2018 8; Li et al., 2022; Reddi et al., 2018). Assumption 2 aims to bound the L2 norm of the stochastic gradient, thus helping bound the L2 sensitivity of the operation of calculating and averaging individual gradients from mini-batch. Assuming bounded stochastic gradient norm is standard in prior works on convex and non-convex private optimization (e.g., Kairouz et al., 2021a Li et al., 2022; Zhou et al., 2020). Under this assumption, suppose the clipping does not happen, we have g" + gf + + o² c²C² /²bb),, where g" := ExE g² Without loss of generality, let $1 in Algorithm Our main convergence result is follows (assuming t starts from 1).
Theorem 2 (Convergence of Algorithm for convex problems). Let Assumptions I and 2 hold.
Assume F is a convex function. Let the learning rate a be set as a² +- +
After
Vi
running Algorithm! for iterations with s = vT for a small constant U E (0, 11, we obtain
min E - FFW")) <ETT
-F((")))F((') + VT
EEIID'
1 T
Vi
TET.
where To denotes the iteration indices where we switch from private RMSProp steps to private SGD steps plus the last iteration, with cardinality [T,, + N 02 /²/1²), and
K 2 max { a²'C² <vi 11-3 min { VM +
Ch(s)
1
C2
where M == C² +
sb2
5

---

Published as a conference paper at ICLR 2023
We defer all proofs Appendix A and state simplified convergence results in Corollary 1. As can see, the above upper bound relies on a critical metric h(s)) which is related to temporal gradient similarity and the amount of staleness s, formally defined as:
E E1lg
11g 11
(s) 2
max TE
max LE[T]
E
de
E
+ de
where the expectation is taken with respect to all randomness in the algorithm, and GL IR refers the latest accumulator that is used to update v (Line in Algorithm 1). A smaller h(s)) indicates better convergence. We see that the denominator of h(s) can be decomposed into the average of past raw gradients and the average of random Gaus- sian noise. Intuitively, h(s) tends to smaller as gradients across the s
0.12
0.10
0.08
0.08
iterations in G are more similar with the current gradient g in terms of the gradient norms. In Appendix A.2, we show that an upper bound of (s) can be expressed as 01 C28 where C1, C2 are constants. We also visualize the value of h(s) on the IMDB dataset in Figure 3, and show that (1) the values of (s) are consistently small across all delays, and (2) h(s) increases as the gets larger, which is consistent with the expression of s.
0.04
25
50
100
delay 5 (x300
Figure 3: Visualization of h(s) versus IMDB.
Trade-offs between delay and noise. Here we discuss how affects convergence based our analysis. Intuitively. larger s (larger delay) results in staler preconditioners, but introduces less noise due private gradient averaging.
our convergence bound, there are several terms that depend on (or v). Although this makes it difficult to derive a closed-form characterization of an optimal 8, we can analyze the effects of s in simplified settings. particular, examine the first term of (where с3 C4 are two constants),
the RHS of the convergence bound, let a
VM+r
V Ves+ S
and assume
L+ 20
1+
2+1
Combined with h(s), the dependence on v in a]ة
20
20
R2
can be expressed as (cr + cgv)
(v
+ This suggests that there exists
an optimal v that achieves the minimal value. In Section 5.1, we empirically study the effects of s across real-world datasets, and demonstrate that there exist specific ranges of that provide favorable trade-offs between delay and noise (Figure 6).
Corollary 1. Let Assumptions and 2 hold. Assume F is a convex function. Ignoring the constants, the convergence rate under learning rate a' O
Vt.
simplifies to
min E[F((())] So 1E[T]
( max TET,
[ID*)la) +0
T J [IN [IMM
where T. denotes the iteration indices where we switch from private RMSProp steps to private SGD steps plus the last iteration (thus having constant cardinality) and No. N(0,, C22/b²)
At high level, the first term is due to adaptive optimization using RMSProp, and the second term corresponds to the added privacy noise. Our O rate is the same as previous results for SGD (or DP-SGD) in convex cases with delaying learning rates (Bassily al., 2014; Nemirovski et al., 2009). Compared with DP-SGD, the added privacy noise would reduced from # Σ 1 BII to + V N* when the gradients are sparse (so that | < in adaptive iterations). Hence, this theorem suggests constant improvements relative to DP-SGD when switch for constant number of times.
4.2 NON-CONVEX CASES
We make the following additional common assumptions in non-convex convergence analyses. Assumption 3 (Smoothness). Each f(z;;w) w) (i [n]) is L-smooth with respect Rdd.
Assumption 4, Stochastic gradient variance is bounded, i.e., Blllgi B|g**1113] - 2 for all i,t.

---

Published as a conference paper at ICLR 2023
Theorem 3 (Convergence of Algorithm 1 for non-convex problems.). Let Assumptions 1-4 hold. Define constant M as M := C + ab? Under any delay parameter s, after running Algorithm I with constant learning rates a' = a such that La S 1, we have
a²c²
2(VM + 1)F(wtt + 2aI(VM+1) Σ RII ([
x²
do²Caa
oT
2c
2b
The proof is deferred to Appendix B. Compared with Theorem 2, here we do not have constraints on Note that guarantee (E, 5)-PP by running T iterations, can set o² 0
6 (og(1/))
arrive at convergence bound O our rate (with and without noise) is the same as previous results on DP-SGD and (DP) adaptive methods for non-convex problems (Li al., 2022; Zaheer et al., 2018). We note that our non-convex analysis does not directly highlight the benefits of adaptivity or trade-offs around 8; hence the optimal choice according to this result is = T, to maximize the goal of reducing privacy noise. However, the practical performance can be better than the upper bound derived here, as shown in our experiments (Section 5). Most of the previous works studying stochastic non-convex adaptive optimization does not prove improvements relative to SGD (e.g., Alacaoglu et al., 2020; De et al., 2018; Ward et al., 2020; Zaheer al., 2018). 8). It is still an open problem to rigorously characterize the benefits of adaptivity for non-convex problems, which we leave for future work.
- (+a) and T O [og(1/5)
vd
Under any
TE
dob
EMPIRICAL EVALUATION
In this section we report empirical results on a range of learning tasks. In Section 5. we compare DP² with the baselines of DP-SGD and vanilla DP adaptive methods across various privacy budgets, and investigate the effects of delay on all datasets. We additionally compare DP² with recent more advanced private adaptive methods in Section 5.2, and conduct ablation studies to validate the effectiveness of different 2 components in Section 5.3.
In all experiments, we use Rényi differential privacy (RDP) accountant for the subsampled Gaussian mechanism (Mironov et al., 2019) for privacy accounting. We focus on the RMSProp optimizer (Hin- et al., 2012) and provide results relating other adaptive methods such AdaGrad (Duchi et al., 2011; Streeter & McMahan, 2010) in Appendix C. Our experiments are implemented in JAX (Bradbury et al., 2018) with Haiku (Hennigan et al., 2020) auto-vectorize over the per- example operations (e.g. per-example clipping) for substantial speedups (Subramani et al., 2021). Unless explicitly stated, we report results with the best grid-searcher hyperparameters. Note that for DP" we tune the learning rates and clipping thresholds separately for private SGD iterations and private adaptive (RMSProp) iterations. See Appendix C.2 for hyperparameter details. Our code is publicly available at gi rithub..... com/ htte//eeziiiig weteniiyullumne
Tuning s. all experiments, we tune the delay parameter (s) via grid search. For convex tasks, we choose from {0.025, 0.5, 0.1, 0.5, 2, epochs. For the non-convex model, we choose from 30,5,3, 10, }5 epochs. We explore the sensitivity of D22 to in Section 5.2, and show that there exist wide range of parameters that result in superior performance compared with baseline methods.
Datasets and Tasks. We pick datasets and tasks where adaptivity is crucial (e.g., those involving sparse gradients). For such tasks, adaptive methods have major benefits relative to SGD in non- non-private training, and we expect Dp2 to retain the benefits in private training. See Appendix C. 1 for a detailed description. For all datasets, we explore the effects of several noise multiplier (a) values, and set
6 = 10 where k is the smallest integer that satisfies 10 t0-k < 1/n for the training dataset size n.
5.1
DP2 COMPARED WITH DP-SGD AND VANILLA DP ADAPTIVE METHOOSS
We consider two popular baselines: DP-SGD (Abadi et al., 2016) and vanilla DP-RMSProp (Zhou et al., 2020). In vanilla DP adaptive methods, private gradients are plugged into adaptive updating rules to approximate the preconditioners each iteration. Figure 4 compares DP DP2-RMSPrro with DP-SGD and DM-RMSProp. We observe that across all datasets, DP² consistently and substantially outperforms the baselines in terms of both convergence and absolute performance.
Privacy/utiliity trade-offs. Figure 4 reports learning curves under specific privacy budgets determined by the batch size and the number of epochs. Here, we additionally explore privacy/utility trade-offs
7

---

Published as a conference paper at ICLR 2023
IMDB (2 3.04,6 10-2)
S Overllow [E 0.87.6 = 10-1
MovieLens [e 9.33.6 10
DR-5GD
0.8
DR-RMSPrap
0.55
DMP-RM (oun)
MSE
1.7
0.30
125t
CP SG3
DP SGD
DP PM00
0.20
DP PrMP
0.3
IDP #MM5 Lours
DP PPM [ours]
100
10
20
30
40
50
10
15
20
25 30
apochs
spachs
Figure 4: Test performance of DP2 compared to DP-SGD and DP-RMPProp on IMDB (left),
StackOverflow (middle), and MovieLens-1000 (right) for fixed privacy budget. For all datasets, calculate the privacy loss (e) under fixed 8's, noise multipliers { {1.0, 1.0, 0.5), and batch size 64. All runs are repeated over 5 random seeds. Dotted lines correspond to training metries.
IMDB
StackOverllow
MovieL.nns
0.80
0.425
3.0
DP DF-1M45P65
DR ScD
RMS5
0.400
test MSE
0.75
2.5
test
0.3775
DR SGD De RMMSPree DeP.IS
0,350
DF-SGD RMd5P gP
2.0
0.65
0.325
10
12
14
15
36
15
privary budget
privary budget&
privacy budget
Figure 5: Privacy/utility trade-off's of DP2 (Algorithm 1) compared with DP-SGD and DP-RMSProp for a range of privacy budgets. We see that DD*-RMSProp consistently achieves more favorable privacy/utility trade-offs than the baseline methods.
across a range of privacy parameters, where E ranges are consistent with prior works (c.g., Kairouz al., 2021b). Results shown in Figure 5. We observe that similar the results in Figure 4, DP² significantly outperforms DP-SGD and DP-RMSProp under each privacy budget. For reference, the non-private RMSProp method achieves 87% accuracy, 62% accuracy, and 0.88 mean square error (MSE) on IMDB, StackOverflow, and MovieLens, respectively. Indeed, with weaker privacy (larger E). we expect smaller utility gaps between private and non- non-private optimization. In Appendix C.4, we additionally explore how increasing the computational budget may affect the privacy-utility trade-off.
IMDB
StackOverflow
MovieLens
StackOverflow
0.825
0.800
0.38
3.0
0.730
0.775
DP-SG'
RMBF
test a5c
11.85
DP-SGD
DP.PMSPxup
test MSE
best are
0.3
20 20-00
DPP.AMSProp
0.726
0,700
0.34
2.6
DP-PMMPPepp RRMSPop
SP-SCD
0.2
7.5
delay in terms of #epochs
delay terms of epochs
delay in terms of #epochs
# epochs
Figure 6: Effect of the delay parameter s. We show trade-off's between delay and noise in the first three subplots. The rightmost subfigure showcases convergence curves under different delays (s=10000 corresponds to delaying for epochs) where dD achieves 4x convergence speedup than DP-SGD. Privacy settings follow those of Figure 4. Although a specific value of s achieves the greatest improvements, we observe that nearly all instantiations of DP² improve upon the baselines.
Effects of s. Finally, we empirically study the effect of the delay parameter s. Intuitively, there exists a trade-off between the amount of delay and the privacy noise in the preconditioner: averaging over more historical gradients (larger s) could yield less noisy preconditioners, while introducing more staleness. In Figure 6, we report test performance versus the delay across all datasets on the first three subplots. In the last subplot, we additionally show the convergence behavior under different values of These results suggest that there is "sweet spot" for to yield good performance- small delays are gradually improving over DP-RA RMSProp: moderate delays perform best in terms of convergence and absolute performance; and large delays may slow down convergence (although it is
8

---

Published as a conference paper at ICLR 2023
possible to reach similar performance with sufficient training). These empirical results are consistent with the implications of our convergence analysis discussed in Section 4.1.
5.2 DP² COMPARED WITH RECENT METHODS FOR PRIVATE OPTIMIZATION
As discussed in Section 2, beyond DP-SGD and vanilla DP adaptive methods, another line of work uses auxiliary, public data to improve private (adaptive) optimization. While not directly comparable to DP2 since DP" does not require any side/public information, we compare DP" to two ot the-art methods along this direction": (1) AdadPS (Li et al., 2022) which uses public data or their statistics to estimate gradient geometry, and (2) PDA-DPMD (Amid et al., 2022), which uses the loss on public data as a mirror map to learn the underlying gradient geometry. Results are reported in Table I, which show that DP² has comparable performance to of-ee-oftthearr baselines, but without the need to access auxiliary data. See Appendix C.6 for full details and convergence curves.
AdaDPS (w/ RMSProp)
Dataset
DP-SGD
DP-RMSProp
PDA-DPMD
DP RM--Prprop
IMDB f StackOverflow t
.687 = .018
.713 + .005
.703 = .005
.826 + .003
.815 = .011
.330 + .002
.328 + .002
.353 + .001
.406 + .027
.391 = .001
MovieL.nns +
3.02 + .068
2.96 + .062
3.74 + .053
2.86 + .042
2.78 .054
Table I: DP compared with other private (adaptive) methods that use public data (Amid et al., 2022;
Li et al., 2022). Even though DP" does not require auxiliary information, we find that it achieves comparable performance with these state-of-the-att approaches that require additional public data. Corresponding convergence plots are presented in Figure 11 in Appendix C.6.
5.3 ABLATION STUDIES
Finally, we also study the effectiveness of different compo- nents of DP2. Recall that in Algorithm 1, we use noisy gra- dients from DP-SGD iterations to update both the model parameters and the preconditioner such that the total pri- vacy cost is identical to that of DP-SGD. The first variant considers accumulating DP-SGD gradients in the same way, but it runs private adaptive methods using delayed preconditioner in almost all iterations. This requires us to add independent noise twice at most iterations (when accumulating the preconditioner and when noising the preconditioned update), thus increasing the total privacy budget. The second variant is identical to DP2 except that it applies the delayed preconditioner after noising the clean gradient; this is to study the order of preconditioning as discussed in Section 3. As illustrated in Figure 7, both variants indeed significantly underperform our proposed method on the IMDB dataset, thus validating the design choices of DP We defer complete results to Figure 10 and Table 4 in Appendix C.5. See also Appendix D for the exact algorithms of both variants.
IMDB (s 3.04 6 = 10-5)
0.8
0.7
0.6
DP-RMPPhop
quer)
Va (soise hirt)
0.5
RepPip (sum)
20
40
60
80
100
# epochs
Figure 7: Different ablation variants of DP² on IMDB. The dotted lines corre- spond to training accuracy.
6 CONCLUSION AND FUTURE WORK
In this work, we proposed DP2, a private adaptive optimization framework that uses historical gradients to construct delayed but less noisy preconditioners, yielding improved privacy/utility trade- offs without the need to access auxiliary data. We demonstrated the effectiveness of DP" both theoretically and empirically. In the future, it would be interesting extend the techniques developed herein to other -eevaayyeensitvve applications such as federated learning (McMahan et al., 2017; Reddi et al., 1021). It is also worth exploring interplays between 2P? and private online optimization with tree aggregation, which similarly releases cumulative statistics with reduced noise (Chan et al., 2011).
"e not directly compare with the prior work of Asi et al. (2021) as the code is not publicly available work of Amid et al.
and implementation details are missing in the paper; however, the more recent (2022) we compare with suggests superior performance to Asi et al. (2021). We also implement the diagonal variant of the method proposed in the ceoreticalll-focueee work of Kairouz et al. (202 la), but observe that accuracy improves only marginally beyond random guessing (see Figure 12 in Appendix C.6).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The work of TL, ZL, and VS was supported in part by the National Science Foundation Grant IIS AS1888017, a Google Faculty Award, Meta Faculty Award, the Private Al Collaborative Research Institute, and the CONIX Research Center. Any opinions, findings, and conclusions or recommenda- tions expressed in this material are those of the author(s) and do not necessarily reflect the National Science Foundation or any other funding agency.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Conference on Computer and Communications Security, 2016.
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. A new regret analysis for adam-type algorithms. International Conference on Machine Learning, 2020.
Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith Suriyakumar, Om Thakkar, and Abhradeep Thakurta. Public data-assisted mirror descent for private model training. In International Conference on Machine Learning, 2022.
Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference Machine Learning. 2021.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In IEEE Symposium Foundations of Computer Science, 2014.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http:/ htt///gittuu github...b..ggg/gg com/ coom/gooll////oooooooooooooee jax.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security, 2011.
Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison nesterov acceleration. arXiv preprint arXiv:1807.06666. 2018.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint 1rXiv:2204.13660, 2022.
Sergey Denisov, Brendan McMahan, Keith Rush, Adam Smith, and Abhradeep Thakurta. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. In Advances in Neural Information Processing Systems, 2022.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 2011.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations differential privacy. Foundations and Trends@ in Theoretical Computer Science, 2014.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. In International Conference on Machine Learning, 2018.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Transactions Interactive Intelligent Systems, 2015.
10

---

Published as a conference paper at ICLR 2023
Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. Haiku: Sonnet for JAX, 2020. URL http::/ /ttp:://gthub com/ deepmind/ he/pminn///// dm- haiku.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Rmsprop: Divide the gradient by a running average of its recent magnitude. Neural Networks for Machine Learning, Coursera Lecture 6e, 2012.
Kaggle.
Stack Overflow Data on Kaggle. 2022.
htttp::/www.kagggtgt httpps//ww...gggleccmaaaattttss cotde//.ssccaaaattttttaeaaaase
Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces. In Conference on Learning Theory, 2021a.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, 2021b.
Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion, Advances in Neural Information Processing Systems, 2018.
Tian Li, Manzil Zaheer, Sashank Reddi, and Virginia Smith. Private adaptive optimization with side information. In International Conference on Machine Learning. 2022.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Anmual Meeting of the Association for Computational Linguistics: Human Language Technologies, 201 1.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics. 2017.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In Conference Learning Theory, 2010.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv:1908. 10530, 2019.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal Optimization, 2009.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný. Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2021.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018
Shuang Song, Kamalika Chaudhuri, and Anand Sarwate. Stochastic gradient descent with dif- ferentially private updates. In IEEE Global Conference Signal and Information Processing, 2013.
Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint 10Xiv:1002.4862. 2010.
Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private sgd via just-in-time compilation and vectorization. In Advances in Neural Information Processing Systems, 2021.
TensorFlow Federated.
TensorFlow aapppiiiapppppppaaaaeeeepei docs
Federated Stack Overflow Dataset.
https:
/ dataaetss//ttccoorrr////////// data, 2022.

---

Published as a conference paper at ICLR 2023
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence nonconvex landscapes. Journal of Machine Learning Research, 2020.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, 2018.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems, 2020.
Yingxue Zhou, Xiangyi Chen, Mingyi Hong. Zhiwei Steven Wu, and Arindam Banerjee. Private stochastic non-convex optimization: Adaptive algorithms and tighter generalization bounds. arXiv preprint (..xi::20061330000 2020.
Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. In International Conference on Learning Representations 2021.
12

---

Published as a conference paper at ICLR 2023
A PROOFS
Lemma 1. Under Assumption 2, let 81 = 82 = 8 in Algorithm 1, we have for any j E [d].
Bluy] S C² + sba
c²c²
Proof. Recall that C' is the gradient norm bound (Assumption 2). Let the clipping threshold be C as
well. We have for j [d].
27 =
1
+ +... + N2.1) ) (Nz)
2
E
G
E
9 5 + + 9ÿ.) +
(I)
E
(0) + ... + 93 )
2
+ E
1
(Ng) + + N7712
(2)
82
82
0²C²
S S
(3)
sbb
where (i,,..., } denotes the indices of noisy gradients used obtain Gj. and {NV) NN
random zero-mean Gaussian variables with variance d²C² under noise multiplier a, clipping threshold C, and mini-batch size b. Hence for any j E [d] and E [T].
12
(
2
o²C² stp
E
C
M,
(4)
B|u²] S M,
(5)
E [ & / S VM
(6)
E [DJ]] S max {
M V +
A. PROOF OF THEOREM 2
Based on the updating rule, we have
++ w" D
(8)
2 a r gº
2
D
-
No N' w0
(9)
Dr
a gt
+ a'v 2
||w²t w D +
2w - a''g'' + o'g''''
(10)
De
D
||w w0 11b 20 (g', - ww) + (at)2 g': g'
Dri
20 (10 w,, D' D'N + (1 2(a (2(())/('))) (g',N"
(11)
Rearranging terms gives
(g' - w²)- = 1|'0 - w' | w0 11
a²
g'
g
20
2
Dt
(w- w", D'N' + at
a a''g',
(12)
2
Taking the expectation on both sides conditioned on w²,
(V w² -w") Eg [||w* w² ||3r|]
Eg Eell w 11:u
2a
a² E,
g¹ D¹
)
+ a
E2 [1|
(13)
2
De
2
13

---

Published as a conference paper at ICLR 2023
where we have used the fact that N is zero-mean Gaussian variable independent of g', w/. Taking the expectation on both sides and using the convexity of F()):
[[F(w")] - F(w") Blll"* w" [1ad|
18 1lllw
w"
[e
at +
g
}
+ a'
B (14)
E
g
20
2
D³
2
Applying telescope sum, we have
T
[B(F(w)) F(w"))
11
E
1106
w0
E
[lle**
2011
20
20
g
a²
g
11::)
(15)
D
2
Hence, we need to bound the RHS:
|
w0
T
E
I|
w= 11
E
Illwt
w=1
w01 1
2a²
2at
2a²-1
1=2
Ti
T
+
a
E
g
+
a
E
[|N'
1
(16)
2
D
2
t=1
t=1
T2
where the vector D E Rdd satisfies that 1 when running private SGD steps, and D when running private RMSProp steps.
v +
Let the delay parameter to scheduled as
8 (T<
(17)
and the learning rate a' be
a'
(18)
Vl
where min {e, VM+c' 1.. and M is the upper bound of E [by] for j E [d]. as defined and proved in Lemma 1.
next consider the term. There are four cases.
1. DP-SGD at the - 1-th iteration, and DP-SGD at the 1-th iteration: As D = D there is not much requirement other that the learning rates need to satisfy a S r-1 which holds for our choice.
Private RMSProp at the t 1-th iteration, and private RMSProp at the 1-th iteration: Similar previous case, the learning rates need to satisfy a' a which holds for our choice.
DP-SGD the 1-th iteration, and private RMSProp at the i-th iteration: We require
a <
1
(19)
a²
But in this we must have /. % 0. So this is satisfied by our choice long S
4. Private RMSProp at the i 1-th iteration, and DP-SGD at the (-th iteration
14

---

Published as a conference paper at ICLR 2023
The first three cases form an updating pattern of DP-SGD .... ... DP-SGD DP- PM--RPP + -MPoMPp where every pattern takes 2s iterations, except for the first pattern, because the telescope sum starts from 2. For the first pattern, we have
w w"
IP |
[1
n= 11 1
(20)
2
2ar
2a
t=2
|u
w²
2x
11:00 20=11
(21)
2a
2=2
2x
(1I D [1]
[[1D'
Rº
D3
+
R2
E
[1]
(22)
2a
2
2a
2a
2m
where D v cc
For 2 1, we have
2sk+22
E 111""
w0 Il
E 1|w2"
w
Σ
20
20¹-1
(=2sh+1
E
[[|w22k++1
20
w=
11:
D200+1
E
[||
[
2a
w0
DRaK
2sk++2
Σ
E
|
w01l
w0
Dt 20
DC1
2sk-+2
2ce
E
2x
wº
12
D2
2ah++
w 1I=1
+ R²
B1ll 220k
1E
[11]
2
2a
2ak
2a
E
2ah+1
w=
D2ck+1
R²
B [Bil 22
[E[1 120k+211111 [|1]
2
2a 2sk++2a
2a 2sh
R²
22
(23)
2sk
where D2sk+20
v + belong to DP-RMSProp updates.
We look at the second T3 term, and prove by induction that there exists a constant k such that
Σ
g
g"
b>
K S a
(24)
2
D
-=1
When T' 1 (a' and D = 1), Blll 2 |13|
nd holds if 2 a²c² At each step t, the goal is
to get
a' E
Ko:
> D'
g6
K a [| |1]
[|]]
(25)
1. DP-SGD at the - 1-th iteration, and DP-SGD at the t-th iteration: We require
Rd a' _ which would hold for choice of a' as gradients are bounded and k 2 a²C².
[|ا|||
Rd axe
(26)
2. Private RMSProp at the t 1-th iteration, and private RMSProp at the t-th iteration:
We need
KE
V
+ E||2
a
g
Vi +
+e|l
(27)
a--l
Vut
+c
a²
t
{
(g'
g²
_
||||
Vo-
+el
(28)
Let
15

---

Published as a conference paper at ICLR 2023
E 11 11
h(s)
max tE(T]
(29)
E
GL : 1 c
Based on our updating rule,
EF ||| Vet Vot+
+c|11
2 v1- 3 BE
1 GLaL +e
(30)
Note that
at
g¹
||
a'C
a'C
[I] -
(31)
2
Vol-1
c
2
2c
where we have used the assumption that ||gs|| || S C. Combining the above two,
a'C
a'C
h(s)E
1
Gl
+
(32)
2E
2e
a'C
M(s)
[|]]
s 2e
E3
V
(33)
vI
1
||| V
+cl]]
< k
E
(34)
a--1
This implies the condition holds as long as x satisfies
Ch(s)
K CVT-B
(35)
3. DP-SGD at the / - 1-th iteration, and private RMSProp at the (-th iteration. We want to prove
Rd
a²
g'
>
E
g'
s a
B [[|
(36)
a 1
2
De
As |g S C, it holds that
at
g
g²
>
S
a'
|13
a'C
Blllg11
|||
a'C
Blllg [b).
(37)
V
2c
2e
2x
Therefore,
a²
E
g
g
Ch(s)
a
E
o0
+
cl]]
c
(38)
2
Vv
+
20V1
Based on our learning rate set in Eq. (18),
Vta' = Vt ---
(39)
a²
<
< at a
(40)
2 at at-lc
a'
Hence,
Ch(ss
'E
V
+c [|]]
evI E |[| ||
Ch(s)
1
d
(41)
2e 2 1
a
Ell Dil
< k
(42)
at
at-1)
where we require
Ch(s)
K <> c/I-B
(43)
16

---

Published as a conference paper at ICLR 2023
4. Private R.SProp at the t 1-th iteration, and DP-SGD at the t-th iteration. We need
a E Vot + e-
a' E [lle [|l
kd
(44)
a
Plug in E [IVel= S ddvM M (Lemma 1) and
||g || S C2, we have
a' - E
a¹
[ + elli
(dVM + d)
(45)
2
=2
Based on our learning rate set in Eq. (18), for some constant 7
a'
?
(46)
vt
VMlMM +1)
a
VM +1
a S d
dv M d
(47)
a
at
a
Therefore
a'
d
d a--l
C S
K
(48)
2
a
holds as long as K 2 a²C². To sum up, the requirement on k is
2 max { (o'c2 Ch(s)
(49)
'EvI- 3
Final convergence results:
min E [F(w') }] F(w")
(50)
[E[T]
+
1
1
T
a
20T
1B=,]
(51)
T
Vi
Q
TET.
where TT denotes the iteration indices where we switch from private RMSProp steps to private SGD) steps plus the last iteration, and its cardinality is [T,]
2
and 2 max c²2
Ch(s)
evI-B s
min { VAl+e
A.2 A CLOSER LOOK AT h(s) We closely examine h(s), defined as
E [1lg'11 111
h(s)= 2 max BE|T E
(52)
+
G1
Let assume mini-batch gradients on consecutive time steps are not very different, i.e. llgs gا1 S M. This means each gradient norm cannot be too far away from each other, which can be used to show the dependence of hss) on the delay parameter Denote the gap between the current iteration and the iteration where e gets updated as k, i.e., k := t { s. Hence,
1
(53)
k- + + k-* + (Nt-R-1 + + N k- + de
lgg 1 (g¹ k- + ..... + 9 k-) + 1 (g) k- + ... + 9 ----)) ||,
(54)
|_ (g k-1 :.............. x- + a
(N
+ N ||| + de
((g" g" k-1 + .... + (g' g" o)) + (g- + +... + g¹ x 11
(55)
(g) + ... + - k (Ni k- + + N /
+ dc
| (g' kg
+ [ +... M)
-g-
+ g k- ka
k- N(- d
de
(56)
17

---

Published as a conference paper at ICLR 2023
Denote : (Nt-k-1 + ..... ......... .......-... N and b 1/2 - t...
gk Then
1
de + sM
h(s) -
(57)
Bllla + b|1 |
de
sM
(58)
a E|
de
de
B[[|b[]]]
In the special case where gradients are sparse, i.e. [|]|[|]] < B|[|a[I], we have
sM
h(s) S
(59)
de B
is easy to see that the RHS is O (s), and increases as s. We can informally express it as ej s + c2.
where ej and 02 two constants.
B PROOF THEOREM 3
First we introduce result that will be used in this section. Under the bounded stochastic gradient variance assumption (Assumption 4), we have that conditioned on w²,
E, [1l
+ [VF(w')11
(60)
where b refers to the mini-batch size to obtain gradient g', ie., g + E gh This lemma is proved in Zaheer et al. (2018). The per-coordinate version this result is that for j E [d].
E, [(,})*]
b + (V,E(w'))
(61)
and EjELd T3- = +
As assume Fww is L-smooth, at each iteration t
L 11 w²1
F(w & F(w") + (VF(w'), w w²) +
(62)
2
Based the updating rule of Algorithm have
T.
F(w(+1) & F(w²) + (VF(w"), w r+ -w')= +
|| w011
(63)
2
=((w²) - a' VF(w"), o
De + No) +N² (at)²L
ge
+
No
(64)
2
Dr
where E Idd and N, ~ N (0, 2²0² with noise multiplier a and clipping threshold C, and D satisfies that
if mod 2s S 8, Vo+e otherwise.
D
(65)
Take expectation with respect to samples at the t-th iteration and N
E, [F( +1]] < F(w*) a" (VE(W)),
VF(w")
(at)²L
ge 27
d(at)2L
E2
+ 21
220
D
(V (V)F(1')22
(a
E,
[(g))
2
= = a'
c22
(Dj)²
252
JE(d]
JE|d
(66)
where we have used the fact that No a zero-mean random variable independent of w and D is independent of samples at time f.. We need consider cases.
18

---

Published as a conference paper at ICLR 2023
1. DP-SGD at the 1-th iteration
In this case, D 1. Hence plugging in
E, [(o))]]
I 1 + (V,F(()'))
(67)
b
we have
E, [F( s F(w")) - -a'- (a))2L)
72
o²C²d
VF(w"))
26 +
(68)
2
26
Under constant learning rate, let a' =a s +.
(22 o0Odd
Eg [F(w & F(w*) a [VF(w()]++
2b +
(69)
2
262
Taking expectation on both sides gives
: E [IVFF(w))) s -
(2
+ o2C2d
(a
(70)
2b
26
2. Private RMSProp at the t-th iteration
We have
VFF( (a')²
+ d(a")2Lo'C
FF + []] F(w")) a²
v of te
2c
V0 +
2b²
%E|d
jEld|
(71)
Plugging in B, [[o}]]]
s -/2
2 (V))(w'))
results in
E [[[
(72)
Σ [VF(w')13 (a))2
of (o+++e)
< F(w²) aa¹
+
Σ
oo te
2c
Seld
jeld
(a
dla
(73)
2e
Vos+e
+e
262
SEld]
=F(w²) - (a'
(a
[V
+ (a
T3
2
+
De
Voj te
2e
(Voz + +e)
262
jc(d]
jEId]
(74)
S <F(w')- - - (at)2L
[V
72
do
+ +
(75)
2E
Vus +
262b
212
JE(d]
Taking expectation on both sides yields
B[F(w'+)) < B[F(w')] - (a'
(at)²
V VF(W)))3
72
do²C²
E
+ (a2))2
20
Vog +
262b
212
jE(d]
(76)
[V
We need to lower bound Ejete E
We know from Holder's inequality that
Vuj+e
Bl, w)} < ][||]]]]][[|] Now note that
/VF(2)))
(VF(w)))
E 20 ||3 =
, .D.)
<
[II
(77)
D
Dt
(VF(w))
< E
(VM+ +c).
(78)
D
19

---

Published as a conference paper at ICLR 2023
Hence
F (2²)))
VF
E
(79)
DJ
M -
JE
and
([F(w((1)) +1) S [F[((1))] -0'² (a')2
E ( 121
72
do²
+ (a
+
2c
M +
22
20
(80)
Let a² = S i. we obtain
7²
d
((F(w [[](w"))]
[IVF(w')]
(81)
2(VM +
2626
262
Combining the two cases, for any t, we have
B[I[F(("() 2( 2(VM+ +1
(82)
72
do
- (E(P(w')
+ +2L((M+1))
(83)
222b
21
Taking a telescope sum results
T
2(vM + 1)F(w*) |[]'F(('))
72
do²
+ +2aolVM M +1)
+
(84)
aT
2
212
1=1
where M = C +
d²C² ab
20

---

Published as a conference paper at ICLR 2023
C EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
C.I DATASETS
IMDB (Maas et al., 2011) is binary classification dataset on sentiment analysis for movie reviews that includes 25,000025,000 ,000 training/test samples. Each sample is review under a vocabulary size of 10,000. We train logistic regression model with 10,001 parameters.
StackOverflow (Kaggle, 2022; TensorFlow Federated, 2022) is large-scale text dataset containing questions and answers from Stack Overflow. We focus on the task of classifying the tag(s) of a given sentence described in TensorFlow Federated (2022), though we focus on the usual centralized training setting instead of federated setting. We randomly sample 246,092 sentences for training and 61,719 for testing, where each sentence is described by 10,000 features. We format the task 500-class classification problem, and the resulting model has roughly 5 million parameters.
PevieLens-1008 (Harper & Konstan, 2015) 5) is movie review dataset commonly used for recommen- dation systems. It contains 100,000 movie ratings from 943 users on 1,682 items (== 6% non-zero entries). We study (non-convex) matrix factorization task with embedding size 100, thus totaling 262,500 parameters. We treat each non-zero entry as a 'record' for differential privacy, and randomly partition them for training and evaluation.
C.2 HYPERPARAMETERS
Unless otherwise stated, we fix the following hyperparameters in our experiments: for IMDB, StackOverflow, and Moviel respectively, we train for 100/50/50 epochs with batch size 64 and privacy 10 5010 6/10- 6, We then perform grid search other hyperparameters:
Learning rates: We grid search over {0.03, 0.1, 0.3, 1, 3, 5} for SGD AdaGrad update rules and from {0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1, 3J for the RMSProp update rule.
Per-example clipping thresholds: We grid search example clipping on clean gradients without preconditioning (e.g. for DP-SGD updates), and over (0.1, 0.25, 0.5, 1, 2, 3, 5) when clipping preconditioned clean gradients (e.g. for DP² updates in adaptive iterations). The rationale is that, in general, the preconditioned gradient norms are usually larger than those without preconditioning (recall from Section 3.2 that we apply preconditioning before privatization in DP²). For AdaDPS and DP2-RMPrrop. we also tried few values of even larger clip thresholds (z 10) though we did not perform full sweep for other hyperparameters at those values due to computational constraints.
{0.1, 0.25, 0.5, 1} when performing per-
Delay parameter For all datasets, (i.e., the number of optimization steps) is chosen heuristically as function of the number steps in an epoch. When reporting the best results (e.g. Figure 4, Figure 5), we search (390 steps/epoch); & E {100, 300, 1000, 3000} for StackOverflow (3845 steps/epoch); and E (1250, 15625, 31250, 50000) for MovieLens (1250 steps/epoch).
s (195, 390, 780) (roughly 0.5, 2 epochs respectively) for IMDB
Adaptivity e: our settings, the adaptivity parameter e for RMSProp//AdaGrad (in the denominator D' = V + 6) would affect the amount of adaptivity well as the norms of preconditioned gradients, which may in turn influence the privacy-utility trade-off under per-example clipping. We tune over small grid of (10-2 10 10-3,030000 10 10-5, 10-
All reported results use the best hyperparameter configurations, which are selected using training set metrics (as overfitting generally does not occur under DP noise). To facilitate reproducibility, summarize the tuned hyperparameters for the main experiments and the ablation studies in Table and Table below respectively.
21

---

Published as a conference paper at ICLR 2023
AdaDPS (w/ RMSProp)
Dataset
DP-SGD
DP-RMSProp
PDA-DPMD
DPM-RMSPro
IMDB
(5, 0.5)
(0.3, 0.1, 10-)
0.5)
(1, 10
(0.1, 3, 0.5, 5, 107, 195)
StackOverflow
(3, 0.25)
(0.03, 0.1, 10
(3, 0.25)
(0.4, 10-))
(0.3, 0.3, 0.25, 10.5, 1000)
MovieLens
(0.1, I)
(0.001, 0.5, 10")
(0.1, 1)
(0.01, 10, 103)
(0.1, 0.03, 1, 5, 103.31250)
Table 2: Tuned hyperparameters for different methods across three datasets. For DP-SGD and PDA-DPMD, the values refer to (LR, clip); for DP-RMSProp and AdaDPS, the values refer to (LR, clip, adaptivity <); and for DP², the values refer to (LR for SGD iters, LR for RMSProp iters, clip for SGD iters, clip for RMSProp iters, adaptivity e, delay 8). Bold values were experimented on the edges of the hyperparameter grids.
Dataset
Ablation Variant1
Ablation Variant 2
IMDB
(3.0, 0.1, 0.5, 2.0, 10², 780)
(0.3, 0.3, 0.25, 10 780) (0.3, 0.001, 0.25, 10 1000)
StackOverflow (1.0, 1.0, 1.0, 1.0, 10 1000)
Table 3: Tuned hyperparameters for ablation studies (Section 5.3) IMDB and StackOverflow: Both variants use the RMSProp update rule for the adaptive steps. Bold values were experimented on the edges of the hyperparameter grids. For Variant 1 and 2 respectively. the values refer to (LR for SGD iters, LR for RMSProp iters, clip for SGD iters, clip for RMSProp iters, adaptivity c, delay 8) and (LR for SGD iters, LR for RMSProp iters, clip for both SGD/RMSProp iters, adaptivity delay s). Note that for Variant 2 the clipping threshold do not need to be tuned separately for SGD/RMSProp iters as it applies to preconditioned gradients in both cases.
C.3 RESULTS FOR
The DP framework can be applied to a range of adaptive methods beyond RMSProp mostly discussed in the main text. We extend 2P to the AdaGrad update rule (with only one line of code change, see Section D), and benchmark its convergence and privacy-utility trade-offs. In Figure 8 and Figure 9, the results indicate that DP2-AdaGrad over the baselines in terms of both convergence and absolution performance, demonstrating the generality 2D to other adaptive optimizers.
like RMS-RMM can consistently and substantially improve
IMDB (5 = 3.04, 8 = 10
StackOverflow (5 = 0.87, 8 = 10-6)
0.40
0.8
0.35
acc
0.7
0.30
best
DP-SGD
DP-SGD
0.6
DP-RMSProp
0.25
DI-RMSPProp
DP-AdaGrad
DP-AcaGrad
DPI.RMSProp (ours)
0.20
DP4 RMSProp (ours)
0.5
Ada-AdaGrad (ours)
DP (ours)
0.15
60
80
100
10
20
30
40
# epochs
#
epochs
Figure 8: (Extension of Figure 4 to the AdaGrad update rule) Test accuracy of Dp² compared to DP-SGD, DP-RMSProp. and DP-AdaGrad on IMDB and StackOverflow. Dotted lines denote training performance.
C.4 EFFECTS OF INCREASING COMPUTATIONAL BUDGETS
When differential privacy introduces large utility gap between private and non-private training, one approach to improving the privacy-utility trade-off is to increase computational costs by using larger batch sizes under fixed numbers of steps. The noise multiplier needs to increase achieve the same privacy target, while the overall privacy noise may still be reduced due to the larger batch size. This technique may be adopted in practice when want prioritize the utility of private optimization
22

---

Published as a conference paper at ICLR 2023
under fixed privacy budgets. In Figure 9 (right), we explore the effect of such increased computation on StackOverflow. With 4x factor increase in computational cost (4x larger batch sizes with the same number of training iterations), observe that the privacy/utility trade-off of all methods can be substantially improved, narrowing the utility gap to non-private training. In particular, observe that the absolute performance improvement of Dp over the vanilla DP baselines remains similar.
IMDB
StackOverllov
StackOverflow
DP-SGD
DP-56D (4x)
0.6
RMSPPrp
DP RMSPPop
test acc
0.5
0.5
DP-RMSPmp (4x)
AcaGrod
DP AaGrad
0.7-
0.4
DP-AdaGrad (ex)
Dabyed RM5Phop
OP RMSProp
0.3
0.3
DP-RMMPmmp (4x)
Delsed Acafordd
DP AdaGrad
privacy budget
privacy budget
privacy budget
DPa-AdaGrad (4s)
Figure 9: (Extension of Figure 5 to the AdaGrad update rule and increased computational cost) Privacy/utilitty trade-offs of DP² compared to DP-SGD, DP-RMSProp, and DP-AdaGrad on IMDB and StackOverflow. "(4x)" denotes increasing the batch size and the number of epochs simultaneously by factor of 4 and picking the appropriate noise multiplier to arrive at similar privacy costs (z).
C.5 ADDITIONAL RESULTS FOR ABLATION STUDIES
Table 4 summarizes the results for ablation studies on IMDB, StackOverflow, and Moviel and Figure 10 reports test accuracies on IMDB and StackOverflow during optimization. The variants are discussed in Section 5.3 and complete algorithms are presented in Appendix D. We observe that DP² indeed consistently outperforms the two (weaker) variants on all datasets, thus verifying our design choices for DP In particular, note that the utility drop of variant 2 (adding noise before preconditioning) on StackOverflow is more significant compared to that on IMDB; we argue that this is due to StackOverflow being a high-dimensional learning task (roughly 5 million model parameters) and thus the detrimental effect of preconditioning per-coordinate noise is larger.
Dataset
Variant1
Variant 2
DP2-RMSProp
IMDB +
.799 + .006
.643 = .007
.855 + ,011
StackOverflow f
.382 .002
.265 + .004
.391 + .001
MovieLens 4
3.32 + .888
3.18 = .066
2.78 + .054
Table 4: Summary of ablation studies on all three datasets.
IMDB (s 3.01,
50015-10 = 10 10-5)
StackOverflow (s 0.87, 6 - 10
0.40
0.8
0.35
0.7
test acc
0.30
test
0.25
0.6
DP-SGD
DP-SGD
DP: RSPRMSPSgg
DP: RP-RMPPrpp
Voriant (extra query)
0.20
Voriant (extra query)
Variant (noise fisst)
Variant (noise first)
0.5
RRMPeep (oum)
0.15
De RM5Piop (ours)
20
100
10
40
# epochs
#
epochs
Figure 10: Test accuracies for ablation studies 2 Dotted lines correspond to training metrics.
23

---

Published as a conference paper at ICLR 2023
C.6 ADDITIONAL RESULTS FOR COMPARISON WITH PUBLIC ASSISTSDI METHODS
Figure 11 extends the results in Section 5.2 with convergence plots on IMDB and StackOverflow; On IMDB, observe that despite not using any auxiliary information, the convergence of Dp RMSProp is comparable with that of AdaDPS PMSPPpp (Li et al., 2022) which uses 1% of training data as the public data (250 examples) to approximate the preconditioner. On StackOverflow where the same public split of % corresponds to 2460 examples, we observe that AdaDPS- can outperform 2p
On the other hand, the extra public data do not help PDA-DPMD outperform DP?
IMDB (s 3.04, 5 = -0
StackOverflow (e 0.87, 10
0.40
0.8
0.35
0.7
test acc
0.30
test
0.6
DP-SGD
DP-SGD
DP RMSProp
RMSProp
AdaDPS RMSProp
0.20
AdaDPS-RMMProp
PDA-
0.5
DP PMop (ours)
DP*-RMPProp (nurs)
0.15
20
40
60
80
100
0
10
20
30
40
50
# epochs
# epochs
Figure 11: Test accuracies of Dp2 compared against recent private (adaptive) methods that leverage public data (Amid et al., 2022; Li al., 2022). Dotted lines correspond training metries.
IMDB (s - 3.04, 5 10-5)
UPP IP-SGD
0.8
Noisv AdaGrad (bases on (KRRT2IJ)
DP-RMSProp
DP--Bt/5PPm (oun)
acc
0.7
0.6
0.5
100
20
40
60
80
100
# epochs
Figure 12: Comparing 2 against noisy AdaGrad variant based on Kairouz et al. (2021a) where the gradients and the preconditioner are privatized separately.
In Figure 12, we additionally implement a private AdaGrad method proposed in Kairouz et al. (2021a) that also leverages public data. Specifically, in each iteration, the algorithm clips and adds independent noise to both the clean gradients and the preconditioner estimated using clean gradients; then uses public data estimate gradient subspace onto which to project the clipped/noised preconditioner in order to reduce the effect of noise; finally, it preconditions the noisy gradient with the noisy preconditioner and takes an update step. Our implementation differs from Kairouz et al. (2021a) in that use the diagonal form of the preconditioner instead of the full matrix form. To estimate the gradient subspace, we follow the approach described Zhou et al. (2021) where the projection matrix V E dx where is the number of parameters and & is the dimension of the subspace is obtained by taking the top-k eigenspace of M with
M
Σ
Ver (x':w") V (x';w")
puh
ExEx
where Xpuh is the set of public examples. Unfortunately, we have not obtained a satisfactory result for this noisy AdaGrad algorithm. We remark that since the method is extremely computationally
24

---

Published as a conference paper at ICLR 2023
expensive (involves computing the eigendecomposition of d x d matrix with d 10001 every iteration). further hyperparameter tuning may help improve the performance. However, our ablation studies (Section 5.3 and Appendix C.5) may shed light the current observations since this method privatizes gradients before preconditioning.
D ALGORITHMS
For completeness, we present all algorithms mentioned the main text detail.
Non-private version of DP only changing Line Algorithm
g
D
EEB
DP2 with the AdaGrad update rule (DD2- AdaGrad); only changing Line 5 in Algorithm to
v + (G* /s1)²
DD2 with Yogi's additive update rule (DP only changing Line 5 in Algorithm
(1 3)sign(G* v²) /s1)
Ablation variant (extra query) with delayed preconditioners: see Algorithm 2. Observe that the clean batch gradients {g*h heB get privatized twice in most iterations (when (t-1) mod A O), increasing the total privacy cost.
Ablation variant (noise before preconditioning) with delayed preconditioners: in Line 9 of Figure 1, privatize the batch gradients with the following replacement:
g' + b
Σ clip (g**, C) +N +N+NN000 (0,0009) /D' iEB
25

---

Published as a conference paper at ICLR 2023
Algorithm Ablation variant (extra query) using delayed preconditioners
Input: T. batch size b, noise multiplier o, clipping thresholds Ci. C2, initial model w Rd O, constant R4, learning rate schedule a', moving average parameters 3, delay steps $
Set accumulator GO 5- 0
for 1. 1. do
Uniformly randomly sample mini-batch B with size from private training data
Get individual gradients for sample B: gh V (x'"; w(11) Privatize the gradients using the Gaussian mechanism:
g' g'
- T H clip (g)
Eelip
Ci) (0,
NEB
Accumulate the private gradients g : +- Gt-1 +
if (t 1) mod = 0 then
Update moment estimates:
f0 + 3) (G* (s)
Reset accumulator: G + Set final gradient: ge + g
else
Privatize the clean, preconditioned gradients using the Gaussian mechanism:
11
Ø¹ - b
Σ
clip
Vo+c C2)
git
(0tt.c)++.00 +N (0. 00.03)))))
iEB
Set final gradient: g' <- g² Update model parameters wt
12
w' w a'g'
13 return T
26


Reviews:
[{"review_id": "XdJaWDY73c", "reviewer": "Reviewer_hof5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new private gradient adaptive descent algorithm for convex and non-convex optimization. The proposed algorithm does a delayed preconditioner update and leverages an average noisy gradient to reduce noise in the preconditioner. The experiments show the proposed algorithm outperforms previous private gradient-based optimization algorithms. ", "summary_of_the_review": "Overall, this paper is well written. It proposes an interesting algorithm and has a comprehensive empirical study. But the paper can be improved by clarifying the contribution, improving the theoretical bound presentation, and discussing the theoretical results. I recommend  6: marginally above the acceptance threshold. \n\n", "strength_and_weaknesses": "Strength:\n1. The proposed approach is well-motivated. It is reasonable to use a delayed preconditioner based on the empirical observation that the preconditioner value distribution is consistent between successive epochs.\n2. The experiment is comprehensive. This paper has experimented on multiple datasets, comparing the proposed algorithm with existing private optimizers and very recent private algorithms with public data. This paper also empirically studies privacy/utility trade-offs, and delay parameters.\n3. The writing is good. This paper is easy to follow. \n\n\nWeakness:\n1. The theoretical convergence bound for convex optimization is very hard to interpret. It is unclear to understand the rate of convergence in terms of dependence on iteration time 'T', delay parameter 's' or 'v', and dimension dependence 'd'. It will be good to clarify those dependencies in the bound and compare Theorem 2 with existing bounds which can make the contribution of this paper clear. \n2. There is inconsistency regarding the dependence on noise variance in Theorem 2 and Theorem 3. In the convex case (Theorem 2), the noise variance is scaled by the preconditioner, i.e., \\|N^t \\|^2_{D^t}, which shows the noise is projected by the preconditioner. But in the non-convex case (Theorem 3), the noise variance is d\\sigma^2 as appeared in most existing bounds. In the algorithm, the isotropic noise is added after applying the preconditioner to the gradient, which makes it more sense to have d\\sigma^2 in the bound. It will be great if the authors can add some discussions about this.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QSpzd6yrLi_", "reviewer": "Reviewer_vZ2E", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "Background: DP-SGD gives guarantees for the whole history of gradients. It very difficult to obtain guarantees that would hold only for the final model, so then it is natural to think, how could we use the history of gradients since due to post-processing that will not have any additional privacy cost.\n\nThe paper proposes a novel RMSprop type of preconditioner for DP-SGD. There are several key steps to reduce the effect of DP noise in the preconditioner. Commonly the preconditioners are plain non-DP SGD preconditioners applied to the noisy gradients, however this work tailors the RMSprop approach to DP-SGD. \n\nImportant steps include \n\n-average the preconditioner over noisy gradients. Preconditioner here means vector v with which the gradients are scaled element-wise before clipping. Averaging over the history of gradients reduces the effect of DP noise.\n-carry out the preconditioning before clipping, instead of afterwards (when e.g. using naively preconditioners to DP-SGD)\n-update the preconditioner only once in a while (for a short window of iterations update the accumulator with which the preconditioned is updated), then carry out preconditioning with the old one.", "summary_of_the_review": "All in all, I think the results (especially experimental) seem very convincing and the ideas natural, so I recommend acceptance.", "strength_and_weaknesses": "\nPros:\n\n- This seems like a novel idea and all these ideas seem like a natural thing to do for DP-SGD (averaging, using preconditioning before clipping)\n- Very strong experimental results for the proposed method\n- The paper is very well written and the convergence analysis seems convincing. For example, for convex problems, it shown that smaller amount of noise is added compared with DP-SGD which leads to faster convergence.\n\nCons:\n\n- Slight deficit of the convergence analysis: the analysis does not seem to improve over the state-of-the-art results for adaptive DP optimizers for non-convex problems, although the same asymptotics are obtained (as far as I see). This means that the strong experimental results are not reflected in the non-convex analysis.\n- I was expecting also some standard DP-SGD comparisons (MNIST, CIFAR10) etc. Could you comment, would the behaviour for this method be then similar?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BlOZs7UixzB", "reviewer": "Reviewer_P2DR", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provided a differential private adaptive training with delayed preconditioners to avoid using auxiliary data for private optimization. Some theoretical results and several numerical studies are explored to demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "This paper simply added delayed preconditioners in existing differential private algorithms. The contribution seems to be incremental.", "strength_and_weaknesses": "Strength:\nThis paper is easy to follow, and the target problem is interesting.\n\nWeakness:\n1. Assumption 1 is quite wired. For any iteration t, this should be proved theoretical rather than simply assuming it holds for all $w^{t}$.\n2. What is the definition of $\\|\\|\\cdot\\|\\|_{D^{t}}$?\n3. It has been discussed about the trade-offs between delay and noise, which suggest there exists an optimal $\\nu$. Could the authors investigate the trade-offs numerically?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2DM_30n_eU", "reviewer": "Reviewer_wuVW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes the idea of using delayed preconditioning by an average of gradients. The idea is motivated by the supposed empirical observation that the gradient geometry does not change significantly over a period of time. ", "summary_of_the_review": "Please see above. ", "strength_and_weaknesses": "The strength of the paper is the novel idea of using preconditioning in this smart way. I like that. \n\nThe main weakness of the paper is the lack of comparison with the prior work. Theorem 2 is almost impossible to interpret. Even the text following the theorem does not help the case. It would be better if the authors provide a corollary that instantiates the theorem with the parameter choice to better explain the result. \n\nAlso, the authors claim that the paper uses adaptive optimization. Does this help them improve the rate of convergence? What effect does it have on the utility guarantee? None of this is clearly spelled out. Of course, they cannot beat the lower bound due to BST14, so what is the best utility they achieve? A proper table comparing the result in this paper in context with previous works should be given. Also, what is the SCO rate? Does their algorithm also permits a nice generalization bound? Does the algorithm have to tune the staleness parameter and the temporal gradient similarity? None of these are clear in the paper.\n\nI haven't checked the proof thoroughly due to limited time. However, the proofs I tried to verify are written in a very difficult-to-parse manner. I will reserve my final score after the discussion with the authors and when I get to read the proofs in more details. \n\nI did not spend a lot of time going through the experiments. IMDB and StackOverflow are difficult to train datasets. The test accuracy for IMDB is really remarkable. I would really like to know more details here. It seems to be beating DP-SGD over all ranges of epsilon for all the datasets.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster