Momentum Aggregation for Private Non-convex ERM
Authors: Hoang Tran
Ashok Cutkosky
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
momentum
non-convex optimization
ERM
tree-aggregation

Abstract: We introduce new algorithms and convergence guarantees for privacy-preserving non-convex Empirical Risk Minimization (ERM) on smooth $d$-dimensional objectives. We develop an improved sensitivity analysis of stochastic gradient descent on smooth objectives that exploits the recurrence of examples in different epochs. By combining this new approach with recent analysis of momentum with private aggregation techniques, we provide an $(\epsilon,\delta)$-differential private algorithm that finds a gradient of norm $O\left(\frac{d^{1/3}}{(\epsilon N)^{2/3}}\right)$ in $O\left(\frac{N^{7/3}\epsilon^{4/3}}{d^{2/3}}\right)$ gradient evaluations, improving the previous best gradient bound of $\tilde O\left(\frac{d^{1/4}}{\sqrt{\epsilon N}}\right)$.

Momentum Aggregation for Private Non-convex ERM
Hoang Tran Boston University tranhpēbu. edu
Ashok Cutkosky Boston University ashok@cutkosky.. com
Abstract
We introduce algorithms and convergence guarantees for privacy- prreeccyie non-convex Empirical Risk Minimization (ERM) on smooth d-dimensional objec- tives. We develop improved sensitivity analysis of stochastic gradient descent on smooth objectives that exploits the recurrence of examples in different epochs. By combining this new approach with recent analysis of momentum with private ag- gregation techniques, we provide an (c, (5.5)-d dddifferent private algorithm that finds
a gradient of norm δ (eN)a73
44/3
in N7/3,4/a
gradient evaluations, improving
d2/3
d/4
the previous best gradient bound of
VEN
Introduction
In recent years, statistical machine learning models have been deployed many domains such as health care, education, criminal justice, social studies [Chen et al. 2021 He et al.) 2019 Jiang] jet al. 2017). However, the release of statistical estimates based on these sensitive data comes with the risk of leaking personal information of individuals in the original dataset. One naive solution for this problem is to remove all the identifying information such as names, races, or social security numbers. Unfortunately, this is usually not enough to preserve privacy. It has been shown in various works that an adversary can take advantages of structural properties of the rest of the dataset to reconstruct information about certain individuals [Backstrom et al. 2007 Dinur and Nissim 2003)). Thus, we would need a stronger sawaccy-rreeevingg mechanism. Over the past couple of decades, differential privacy (Dwork al. 2006 has emerged the dominant privacy notion for machine learning problems.
Definition (Differential Privacy Dwork and Roth 2014). randomized algorithm M: XN H Rd satisfies (c, () differential privacy ((c, D)-DP) for any two data sets D, D' E X differing by at most one element and any event E C Rd, it holds that:
P (MM(D) E S (xp(c)((M(D") E +
Roughly speaking, differential privacy guarantees that the outputs of two neighboring datasets (datasets that differ in at most one datapoint) are almost the same with high probability, thus preventing the adversary from identifying any individual's data.
In this paper, minimization (ERM) problems. In ERM problems, given N i.i.d samples æ1, FN E X' from some unknown distribution P. the goal is find Rdd such that minimizes the empirical loss defined as follows:
interested in designing (c, pprivate algorithms for non-convex empirical risk
F(w)
fw, xi:)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where f: x X I is the loss function associated with the learning problem. This is a setting that commonly arises in modemn machine learning problem. For example, in image classification problems, the data point x would be tuple of (image, label), w denotes the parameters of our model, and f(w, 2) represents composing the model predictions with some loss function such as cross-entropy. We are interested in finding a critical point, or a point such that the norm of the empirical gradient [VF(w)]] is as small as possible. Further, we want all the outputs W1, W2, ..., WT to be differentially private with respect to the N training samples.
Private ERM has been well studied in the convex settings. The approaches in this line of work can be classified into three main categories: output perturbation (Dwork et al. [2006] Chaudhuri al.) 2011, Zhang et al.) 2017 Wu et al., [2017]. objective perturbation [Chaudhuri et al. 2011
Kifer et al. 2012 Lyengar et al. [019]] Tal war et al. [014]) and gradient perturbation [Bassily et al.
2014 Wang et al. 2017 7 Jayaraman et al. [018]] Wang et al.)
2018]. All of these approaches have Vdd
been shown to achieve the asymptotically optimal bound O
for smooth convex loss (with
EN
output perturbation requiring strong convexity to get the optimal bound) in (near) linear time. On the other hand, the literature on private non-convex ERM is nowhere as comprehensive. The first theoretical bound in private non-convex ERM is from (Zhang et al. [017]. They propose an algorithm called Random Round Private Stochastic Gradient Descent (RRSGD) which inspired by the results from Bassily et al. 2014, Ghadimi and Lan 2013). RRSGD is able to guarantee the utility bound
of O (dloginn/o) (1511)
However, RRSGD takes O (N²dd) gradient computations to achieve this, which can be troublesome for high-dimensional problem. [Wang al. 2018) then improves upon this utility bound by factor of O (l)) They achieve this rate by using full-batch gradient descent which is not a common practice in non- non-private machine learning in which very large batch sizes actually require careful work to make training efficient. Recently, [Wang et al. 2019b] tackles both runtime and utility issues by introducing a private version of the Stochastic Recursive Momentum (DP-SRM) [Cutkosky and Orabona 2019]. By appealing variance reduction well as privacy amplification by subsampling [Balle et al.
VeN
2018 Abadi et al.] 2016), DP-SRM achieve
(d (110(11 in O VeN
(cN)
the bound O
gradient complexity. However, DR-SRM still
d3/4
v/
requires the batch size to be O
VeN 2074
for the analysis to work. Finally, although our focus in this
paper is the ERM problem, there are also various works on private stochastic non-coovex/convex optimization [Bassily et al.
2019 b021a Feldman et al., 2018 2020 Zhou et al. 2020 Asi et al..
2021 Wang et al. 2019a Kulkarni al. 2021].
Contributions. We first provide the analysis for the private version of Normalized SGD (DP-NSGD) [Cutkosky and Mchta 2020) for unconstrained non-convex ERM. By using the tree-aggregation technique [Chan et al. 2011 Dwork et al., 2010] to compute the momentum privately, we can ensure the privacy guarantee while adding noise of only Ô
JT
(where is the total number of
eVN
iterations). This allows us to achieve the same asymptotic bound Ô
d1/4
on the expectation of the VeN
gradient as (Zhang et al.] 2017 Wang et al. 2018 2019b) without appealing privacy amplification techniques which is usually required for private SGD to have a good utility guarantee [Abadi et al.. 2016). DP-NSGD also does not require large batch size as in [Wang et al. 2018 2019b/: it has utility guarantee for any batch size. This tree- agceagggegttion technique is morally similar to the approach in [Karrouz et al. 12021 Guha Thakurta and Smith 2013) for online learning. However, unlike in
Kairouz et al.J [221] Guha Thakurta and Smith 2013]. we do not restrict our loss function to be convex and we will also extend rggeagggeg technique to SGD with momentum. Further, provide a new variant of Normalized SGD that takes advantages of the fact that the gradients of the nearby iterates are close to each other due to smoothness. This new algorithm is able to guarantee an d3/3
error of δ known rate for private non-convex FRM.
in O
////3//33
gradient computations which, to our knowledge, is the best
(2N)273
d3/3
Organization. The rest of the paper is organized as follows. In section 2 we define our problem of interest and the assumptions that we make on the problem settings. We also provide some background on Differential Privacy as well as some high-level intuition on tree-aggregation technique. We then formally describe our first private variant of Normalized SGD in section 3 and discuss its privacy guarantee and theoretical utility bound. In section we introduce novel musitivitt-reducce analysis
2

---

for Normalized SGD that allows to improve upon the utility bound in section 3 Finally, we conclude with a discussion in section 5
2 Preliminaries
Assumptions. We define our loss function as [(w,,) x:): RR x X' + R where E X is some sample from the dataset. Throughout the paper, we make the following assumptions on f(w, 2). Define differentiable function f()) _2 R be G-Lipschitz iff fy)ll G for all y E R and be L-smooth iff V f(y) V f(z)) II I. L|| - where ||.]| is the standard 2-norm unless specified otherwise. We assume that fwu, x)) is differentiable, G-Lipschitz, and L-smooth with probability 1.
We also assume that provided the initial point w1 Rd there exists some upper bound R of F(wi)
or formally: SuPwERd F(wn) ) - F(w) < R.
Differential Privacy. Let D be dataset containing N datapoints. Then two datasets D, D' said to be neighbors if | - D'I11 = or in other words, the two datasets differ at exactly one entry. Now we have the definition for sensitivity:
Definition 2. (Lg-sensitivityy The Le-sensitivity of a function f(): X + Rd is defined as follows:
A()) sup - ((D')
D.D
In this work, we also make use of Renyi Differential Privacy (RDP) [Mironov] 2017). RDP is relaxation (e, 6) and can be used to improve the utility bound and do composition efficiently while still guarantecing privacy.
Definition 3. ((o, RD-RDP (Mironov 2017)) A randomized algorithm f X by TR. is said to have CDRDP of order for any neighboring datasets D, D' holds that:
D&(T(D)IL(D') Se
where (P(P( A a-I log BaI
P(z) Q(
9[1:8]
9[:44]
[[5:8]
91:22
9[3:4]
9[5:6]
((7:8)
g11:1
9(2:2]
913:3]
g[4:4]
[|s:5]
[|s:6]
M1::7
[
Figure 1: Visualization of the aggeeggggnn mechanism. Each node of the tree hold the appropriate
value U/::=] where 91y:z] m Dt.
Tree-aggregation. Consider the problem of releasing private partial sum $ly.=] E
Ei=y: 9: given stream of vectors 91..... 9t- Assuming ||g.1| s G Vi E [t], then the simplest solution for this problem add Gaussian noise with standard deviation Ô (1/e) to each gi so that each şi (e. -D. Then error from the noise added any partial sum will be bounded by O O(VT/c). However, this problem can be solved much more efficiently using ageeagggegttion [Chan et al. 2011 Dwork et al. 2010]. tree-aggregation, we consider complete binary tree where each of the leaf nodes is labeled with zi and each internal node in the tree is the sum of its children. The tree is illustrated in Fig It is clear from Fig I that each gi only affects ancestors, or at most [log /] + nodes. Thus, by adding Gaussian noise with standard deviation Oloo t/e) to every node, the complete tree will be (p

---

Furthermore, since we only need at most logt nodes to compute any partial sum [|raa] the noise added every yy.i would be bounded by (log' t/e), which lot less than the noise that would add using advanced composition.
To get general idea on how we can use this tree-aggregation technique to design private algorithms, let us analyse the update of SGD with initial point W1 = 0:
W++1 We r/ (we,, 2z,)
V f(Ws
where V[(w,, x4) is the gradient of the loss function evaluated on the current iterate w, and some sample Tt. Notice that every iterate W would be function of the sum of the gradients s, E ff(w,, xx) up to iteration t. Thus, if we can tree aggggggggtioon privately compute every partial sum *[y.=] = Dizy V [[(ws, m4), we can the use these partial sums to compute every iterate wt, and is also private by post-procent post-processing [Dwork and Roth 2014). Similarly, we can also use this aggregation technique for SGD with momentum where we replace ff(w,, with the momentum my. This method of computing momentum would be the main ingredient for our private algorithms. more detailed discussions are provided in section 3 and Tree-aggregated momentum has been briefly mentioned in the momentum variant of Differentially Private Follow-The
(DP-FTRL) in [Kairouz et al., 202T]. However, their algorithm does not directly compose momentum using the tree-aggregation and they also do not provide any formal guarantee for the algorithm.
3 Private Normalized SGD
Before go into the details of our private algorithm, first let us set up some notations that are frequently used in the rest of the paper. We define the set of subsets I as follows:
I {a22 + 1, + 1)2"Ila, E Z, [a2 + (a 1)22] c [I,...,T}}
Each interval in corresponds to a node in the tree described above (In Fig. the set 1 is {[1, [2, [2, 2], [1, }). Thus, the set of intervals / is essentially different way store the binary tree for tree-aggregation mechanism. Then, for every interval b). there exists (log T) disjoint subsets [V1, =1)....,, ..., [W, =n I such that [a, = U [ys =,] Daniely et al. (2055) We denote the set of such subsets as COMPOSE(a, (a, b). which can be computed using Algorithm Now can proceed to the analysis of the private Normalized SGD algorithm described in Algorithm
The main idea of Algorithm|] is based on two observations. The first observation wi a function of the momentum. Thus, similar to SGD, if we can compute the momentum privately, every iterate w1.....; WT would also be private by post-processing. The second observation is that m, is an exponentially weighted sum of the gradients and can be computed efficiently using tree-aggregation. To see this, notice that the momentum m, can be written as follows:
m = (1 - a)m--1 + aV f(wr, Fxy))
1 (W) I Fz
0
Σ
a1-
(1 a)) a=== Vf xz
(=J)CCOMPOS)(1.0
where denote x the sample drawn at iteration i N:N rs. Now, if set f(g.s]
Ei (((1-a==--r' VV= x ox then:
Σ
(1 - ((
m
(=

---

Thus, if we consider fly.= as the value of the node [y, 2] in the tree, can compute my using at most (log t) nodes from the tree, We will also accumulate the noise in the same way. Assuming S[y.=] as the noise we need to add to node [y, 2] to make [y..e] private, then the noisy my is:
m
E
(1-a)* [m.e]]
Σ
(1-a)* a1-a) [(u.a)
(L))ECCMPOOS((L)
Σ
(1 (1-a) aaa [[y.=]
which is essentially the update of Algorithm 1 Then, as long as fly.s] has low sensitivity, the noise
we need to add make my private would be small since there only at most O (log t) intervals in COMPOSE(L,)).
Algorithm Differentially private Normalized SGD with momentum (DP-NSGD)
Input: noise parameter momentum parameter 1 - B, dataset (I1, (Z1,...: TN), tree depth Rt Lipschitz constant G, loss function f(w,, x), noise map
mo mgg- <- O.
NOISE f
V < (min( R, [logz (NV)) + 1) + Σド= (N)+1 1.
for b 0, ..... R do
for .,... [T/2a] - do
Sample $[a2*+1.(0 +1(0++12))) Z[a2' + 1, (a + 1)2*1 + (1++12
N(O, 16a
end for end for
for q O, ..... T/N| do
Sample a permutation TH ...... N of {1....,N] uniformly at random. for i 1. ..... min ( T N do
I < qN +
Send interval [1, to Algorithm
3 to get the set S COMPOSE(110)
for every interval S; E $ do
NOISE + NOISE + (1 - a) a (1)) Z[Sa] S1[1] indicates the end index each interval S₁)
end for
m. a m a V +VV[(w,,
m, + m, + NOISE
my
1++1 wh 7) me
NOISE <-O end for end for return WT
Theorem 4. (Privacy guarantee) Suppose that f(w, x) is G Gippsschitz for all E Rdd, E X,
Algorithm 7 is (z, 2 Renyi-differentially private for all z. Consequentially; if exp( (op(-)) -), then with
2//08(1/6)
Algorithm is (e, d)-differentially private.
Proof sketch of Theorem define:
Denote N + rt for any iteration for T E [1, and ge 0. We
[p.z]] = a ar) =-(
V Vi(wr, M.u,,,aa x-4e)
M== y
Σ
(1 (1-a) t-= [
m4 =
[y. (c.O)E))
To compute the sensitivity of fy.=]. recall that the loss function f is G-Lipschitz. Further, any given datapoint z; contribute most [ly 21/N1 gradient terms in the summation defining fly.a). Thus
5

---

[[.3)] has sensitivity A = 2oG 11a--1/M1--- (1- -1 S 4aG for 2 N (Proposition 13 Next, 2==0
compute the maximum number of interval that contains any datapoint æ; for i E (I....:: N). Given two neighboring datasets and D', we use $ to indicate the index of the datapoint that is different between the two datasets. We then denote S(y.a] {l, N) the set that contains the indices of the datapoints that contribute node [y, (essentially which elements of the dataset are relevant to the value of node [y, 2)). For any E {l....,Ny NN, for any S [No]] there are I different a {0,.... [T/2*] - 1} such that $ E S1022 (a)+4))2 for I (logg(N)) at most N Further, for any
= (l...., N3 for all a. Therefore, for any [N)] à E S1a2 [log, (NV)+1 sets S; such that E S,- there at most V min( + (N)
The privacy guarantee then follows via the ordinary composition properties of Renyi differential privacy. The full proof is included in the appendix.
Before proving our utility bound, we need the following lemma.
Lemma 5. [Essentially Lemma 2 |Cutkosky and Mehta (020 Define:
é = VW(w:
Suppose W1,...WTT is a sequence of iterates defined by Wr+1 = W2 1) the sequence mm,,... M..... Pick in uniformly at random from wi,..., WT. Then:
TTm for some arbitrary
E [|] 3E 3E[(F(w1)
-F(wr+1)))
3Ln
+
Σ
T
Bll&&ll
2nT
4
Now are ready to prove the utility guarantee of Algorithm [
Theorem 6. (Utility guarantee) Assuming f(w, x) is G-Lipschitz, L-smooth for all Rd, X.
and F F(w1) is bounded by R. Then Algorithm 7 with
VNT' O Tlog, T /
oN T
O
T Tlog T (1) and in that pick uniformly random from wi w,...., WT
log, T (og(1//)) guarantees:
N
( RR 61. 61./1og2 T log(l////////// (1/5) + 12G /log log 1og(11)))//)9044
VeN
3L(dlog(1/0))4
Vlog
6G
6G lolo T d (og(1/))
+
4VEN3/2
VN
eN
1/4 VEN
1
VN
The analysis of Algorithm I pretty much follows the analysis of non-private Normalized SGD in Cutkosky and Mchtal [2220]. We first bound the error between the noisy momentum and the true empirical risk gradient El first term is bounded by the standard deviation of the added noise. The second term requires more delicate analysis due to the use of random reshuffling (RR) in our algorithm (which is more common practice than sampling in real-worth problems). This introduces bias to the gradient estimates. Or formally, if we define
VF(w))lll < E[[ m+ - m; ||] + Elllm, VF(w,))ll Il]- The
N and r = N for every iteration E [T), we have KI / (wr,, ..%. )] * FF(w:) Most the known analysis of RR done with regular SGD Mishchenko et al. [2020] Nguyen et al. [209 since the bias becomes an even bigger problem in SGD with momentum due to the accumulative nature of momentum. To circumvent this problem rewrite m,
(1-a)) f = )+O(n=V) and use the fact that E f ( : 2 _=%/2/
F((W..) where Wyg is the iterate at the beginning of the epoch and I²;, is datapoint that is sampled in that particular epoch (this is true because Wg.. is independent of any data sampled in the epoch). Then, by applying Jensen's inequality and the definition of empirical loss, we have the bound Bl]mm - VF(w))ll < Ō (Vo + nN
av/7 </N
Finally, we can apply Lemma 5 with
the appropriate hyperparameters to get the utility bound in Theorem

---

Algorithm 2 Sensitivity reduced normalized SGD
Input:
Initial Point w1, training set .1,...,, NN learning rates 7), momentum parameter 1- B,
cross-batch parameter y, Lipschitz constant G, smoothness constant L, noise variance o². Set VS2N 3 log2 N, V>2N NN (og)
Set Ôg = 4G, 82 = 8, = 2n/N.
for q 0,............. ..... LT/N] do
Sample a permutation कi ....... N of (1....,NN) uniformly at random. for O..... min(N 1,T NN} } do
f - qN ++ for k = 0, ..... [t) do
if mod 2 = then
if I < 2N then
Sample C NO0,680"
else
Sample c (0, 88
end if
Sample Ci ((, 8,00 22
PG
1t-2 24 - 1.1) = Σ Li
a) -aa' +
Fr
( (1-24 1.1] = -i= (V
- - Ci
if 2 +1> N then
Sample / ~ N0,882 [ )2N
FA [t-24+1,1] E 2 a) (V - 1)N (022)
+ C
end if
end if
end for
Compute mh using the reconstruction algorithm (Algorithm
mi Wr = 1 m
end for
end for
Return wi,..., WT
4 Sensitivity Reduced Normalized SGD
In this section, we will devise algorithm that has asymptotically tighter bound than δ which is the best known bound for (e, 8) non-convex ERM. One natural direction is to use better algorithm for non-convex optimization than SGD. It known that non-convex optimization operating on smooth losses, the optimal rate for SGD (11/N1/4) Arjevani et al. [2019] while
d//4
VEN
more advanced methods that use variance reduction Fang et al. 2018). Zhou et al. [018 Tran-Dinh al. 2019 or bessiann-vector product Arjevani et al. 2020 Tran and Cutkosky 2021 can achieve the rate (11/N//3). Thus, one could hope that these methods non-convex ERM. Unfortumately, this does not seem to be the case in reality. For example, Wang al. [2019b] proposes variant of the variance-reduction based stochastic recursive momentum (STORM) Cutkosky and Orabona [2019] called DP-SRM but their algorithm shows little asymptotic improvement compared to previous known bound. DP-SRM improves the error bound by a factor of log(n/8) but this seems to be the result of sampling Abadi et al. (0166) rather than variance reduction. We would like explore an alternative direction improve the error bound. Instead of using better non-convex optimization methods, we will reuse the Normalized SGD in section 3 but with tighter
improve the bound of private
privacy analysis that requires us to add less noise than Ô
The motivation for our methods comes from full-batch SGD. Consider the following full-batch
normalized gradient descent update: W++1 = w: - '7 2r " where g: = (Wt.). Notice that (for
<> 1) - + (F(w)) - VF(w,-1). Now, given -t-1, 1, the sensitivity of can be bounded by
the sensitivity of F FW which in turn only O(n/N) due to smoothness and the
fact that |w, Wt-1l 17. This is lot smaller than the naive bound of O(1/N) since n << 1. We
7

---

can iterate the above idea to write 9: VF(wi) + Ei= VF(w;)) VF( In this way, each 9r is a partial sum of terms with sensitivity Onn/N), which can be be privately estimated with an error of (n) using tree-aggregation. The main intuition here is that except for the first iterate, each iterate is close to the previous iterate due to smoothness that is, VF(w,)
VF(w,-1) has low sensitivity. In fact, we can further control the sensitivity of gt. by expressing gr = (1-7)(9--1 Fuw,) ()) + FV(() for some parameter y 1. Now, with appropriate value of % St. can potentially have even lower sensitivity compared to the case 7 = that we discuss above. Moving beyond the full-batch case, we would like to replace the full-batch gradients V)((w,) in this argument with momentum estimates my. Unfortunately, it is not the case that my m,-1 has low sensitivity. Instead, notice that the distance between two iterates evaluated consecutive epochs will be at most n < for appropriate 7) and we can show that the sensitivity of m, N scales by this same distance factor. Our method described in Algorithm follows this observation to compute low sensitivity momentum queries. To see this, let us rewrite the momentum my in Algorithm
the same sample two
m (1 -a)m--1 + VV/VV./ f (Wrr, Txa)
a) )=²² 'V f W/. xa
a a) Ww xx + Σ a) (V - V Vf(
In order to exploit this decomposition, we define G(a,b] = Etzal (1 a) N. ba (1 a) (VVf(ur,
F, and A (a.b))
Σ (1
a) h- (V ff =xae V ff( I)N, xxz)) )). Then, I states:
m, m==Gpp. + amppa
(2)
Considering = qN + r, we can further refine this expansion by observing (Lemma
9-1 (1 a) vi - 7) (1+1) --(-1))))) ( G|+LLc+
G[a.) = -1 (1-a)* +
i=0
7) - (1)10)00-1-3))) (1
GG--IN-L--
f=1
Thus, in Algorithm we will estimate Gja.bj. Ma,b] and A (a.0] for all intervals [u, b] using tree aggregation, and then recombine these estimates using (2) and 3 to estimate my, The critical observation is that each term of the sums for T[a.0] and Aja have sensitivity most On1 because the normalized update implies || | Wer Σ nN for all [t --='l E'| S N, while the O(1) sensitivity terms Gja.6] are scaled down by 7. However, notice that in the first two epochs, we don't have the extra parameter that helps control the noise added to the momentum. Thus, if we just naively add noise based on the maximum sensitivity (which is VS2N), the noise will blow up since scales with T/N. To remedy this, add two different types of noise to 2 (k E {0. {O..... logg [t) depends on whether t > 2N. By dividing the sensitivity into 2 cases, we can make the momentum of the first 2 epochs (e, DD by adding noise of ((1/)) and every other epochs 8) by adding noise of /Ve) Then, the whole procedure would be (O(c),
DP overall.
Morally speaking, we can think of the first two terms of the update of Algorithm (Fq. 3 as the first iterate the full-batch example with some exponentially weighted factors and the third term as the
(1 (VW,)( (W + FF(() part. Overall, if set 7 nN, the noise we need to
add to make m, private is Ô + TVTT + CnNyT which is smaller than the ò D(avT) noise that
"V/ we add Section 3 Formally, we have the following error bound for the momentum.
e/N
8

---

Lemma 7. Suppose 2 1 N and y S 1
using the update of Algorithm 2 we have:
2'
192Ga log, T /ddlog(1/0) + 128(G + +L) a / log(1/6) log,
Ellm - mill =
e
L6 log, T TT/331 N log()/6)
To prove Lemma] 7 we sum up the variance of the Gaussian noise needed to add to make every term in Eq and ft private. Then Elllm, mill I VdVAR where VAR is the total noise variance and d the dimension of the noise vector.
Theorem 8. (Privacy guarantee) Suppose 1/N and f is G-Lipschitz and L-smooth. Then
is (2.3z/20²) Renyi differentially private for all z. With 4v //oii1/8
Algorithm (c, DP
Algorithm is
The proof of Theorem 8 follows the proof of tree- -re-aggregated momentum with Renyi differential privacy as in section 3
We defer the proof to the appendix.
Now we have the utility bound for Algorithm
Theorem 9. (Utility guarantee) Assuming f(w,,) a)) is G-Lipschitz, T-smooth for all IRd X,
and F F(w)) ) is bounded by R. Then Algorithm with = v,,, VNT' a Na/4, NT/8,4/3
T3/A
6273
22/4 vá and to that is picked uniformly random from 10 -... WT guarantees: N5/4
R
(4K(G + 2L) + 12L)d
6G 36GK
9KLVd
V[]))(()
(cN)2/3
eN
eN
1//3
(EN)2/3
VN
where 16 16log, T (og()/)))
The analysis of Algorithm 2 is similar to the analysis of Algorithm
We still bound the error between m FF (w,))l s E [l]m my ll] is the same as in Theorem but now, the noise bound
1
the noisy momentum and the true empirical risk gradient
E. [l]m, Fwwlll E [[]m
((())) [I]
E [|] m.ll] is only Ô ( (av + avT anNydT instead Ô
av due to our sensitivity-
reduced analysis. Then we can apply Lemma get our final utility guarantee. The full proof is provided in the appendix.
Conclusions
In this paper, we present two new private algorithms for non-convex ERM. Both algorithms are variants of Normalized SGD with momentum and both utilizes tree-aggregation method to privately compute the momentum. Our first algorithm overcomes the large batch size and privacy amplification techniques requirements in previous works while still achieving the state-of-the-ard asymptotic bound
Our second algorithm uses the insight from full-batch SGD operating on smooth losses reduce the sensitivity of the momentum. This allows the algorithm achieve the utility bound d//3 which, to our knowledge, is the best known bound for private non-covex HRM.
VeN
(eNY=73
There are several limitations that one could further explore to improve the results of this paper. The most natural direction is to incorporate privacy amplification by shuffling into both algorithms. Based on the current analysis, it not obvious that we can apply privacy amplification immediately to aggggggge momentum. However, it is possible that there are some clever ways that one can come up to make the analysis work. It has been shown in previous work that
Limitations:
privacy amplification by shuffling does help achieve the Ô ///4
utility bound. Therefore, is our hope that by combining privacy amplification with our sensitivity reduced algorithm, we can achieve an even better utility bound than Ô 41/3 (eN)a78
VeN
Furthermore, even though our first

---

algorithm has comparable run time to previous works, the second algorithm has slightly less ideal run time. The current algorithm requires Ô NT/9 4//3 gradient evaluations but has the total run time dP/3
of O(N11/8 /d2/3) due to the extra run time from the compose and reconstruction algorithms. We would like to reduce this to quadratic run time. We will leave these for future research.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, 1lya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv: arXiv:1912.022: 1912.02.6., 2019.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Sccond-orde information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299, 2020.
Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods convex optimization. In International Conference on Machine Learning, pages 383-392. PMLR, 2021.
Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. Proceedings the 16th International Conference on World Wide Web, WWW '07, page 181-190, New York, NY, USA, 2007. Association for Computing Machinery, ISBN 9781595936547. doi: 0..144/1122257.1222555 1242598
URL http:///////...orr//000.0/11///1 1145111.1.11/1222777777
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
Racf Bassily, Adam Smith, and Abhradoep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium Foundations of Computer Science, pages 464-473. IEEE, 2014.
Racf Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Proceedingy of the 33rd International Conference on Neural Information Processing Systems, pages 11282-11291, 2019.
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic optimization: New results in convex and non-convex settings. Advances in Neural Information Processigg Systems, 34, 2021a.
Racf Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-cuclidcan diffcrentially private stochastic convex optimization. In Conference on Learning Theory, pages 474-499, PMLR, 2021b.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3)1124,, 2011.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimiza- tion. Journal of Machine Learning Research, 12(3), 2011.
Zhaoyi Chen, Xiong Liu, William Hogan, Elizabeth Shenkman, and Jiang Bian. Applications of artificial intelligence in drug development using real-world data. Drug discovery today, 2665):12561126,, 2021.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. International Conference on Machine Learning, 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex sgd. Advances in Neural Information Processing Systems, pages 15210- -12199, 2019.
Amit Daniely, Alon Gonen, and Shai Shalev-Shward, Strongly adaptive online learning. International Conference on Machine Learning, pages 1405-1411. PMLR, 2015.
Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the Twenty- Second ACM SIGMOD SIGMOD-SIGACTO SIGACT-SIGARY Symposium on Principles of Database Systems, PODS '03, page 202 210. New York, NY, USA, 2003, Association for Computing Machinery. ISBN 1581 158110 136706. doi: 10.1145/773 URL attps:///oss htt://tt..oor///// /00 1145/773153.
10

---

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4)2211 2014.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, TCC"06, page 265-284, Berlin, Heidelherg, 2006. Springer-Veriae ISBN 3540327312. doi: 10. 1681878_14 URL httttt wwopooorg/11..000000 1100110111111811111
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the sorty-second ACM symposium on Theory of computing, pages 715-724, 2010.
Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path- integrattt differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 521-532. IEEE, 2018.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Compuring, pages 439-449, 2020.
Saeed Ghadimi and Guanghui Lan, Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341- 234)22234--338, 2013.
Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full- information and bandit scttings. Advances in Neural Information Processing Systems, 26:2733-277 2741,, 2013,
Jianxing Hc, Sally Baxter, Jie Xu, Jiming Xu, Xingtao Zhou, and Kang Zhang. The practical implementation of ar- tificial intelligence tcchnologies in medicine. Nature Medicine, 25, 01 2019. doi: 10. 0011088/41591-01 5000-000000----.
Roger Iyengar, Joseph P. Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pages 299-316, 2019.
doi: 10.1109/SP.2019000000
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without dis- tress: Privacy-preserving empirical risk minimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grau- man, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018. URL htttp:://proceeeeiiie wwtp:/aa...p.p.pppee//eaaa... 72216688ccb000666511ffffffee -wwteebbddd-appe...e pdf
Fei Jiang, Yong Jiang, Hui Zhi, Yi Dong, Hao Li, Sufeng Ma. Yilong Wang, Qiang Dong, Haipeng Shen, and Yongjun Wang. Artificial intelligence healthcare: past, present and future. Stroke and Vascular Neurology, 2(4):230-2) 243, 2017, ISSN 2059-866 8688. doi: 10.1136/svp 10.113666m-2017-000000 2017-000101. (aatent/2/4/255
URL httl:ttttt:////t bmj com/
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling, arXiv preprint arXiv:2103.cm 000099 2021.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high- dimensional regression. Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 25.1 1 1..1-25,400 40, Edinburgh, Scotland, 25-27 Jun 2012. PMIR. URL. 1223/iferr22 html
mlr press/
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non- mon-hh empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103.15352 2021.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275.10 IEEE, 2017.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárík, Random reshuffling: Simple analysis with vast improvements. arXiv preprint 2xXiv:2006,05900 2020.
Phuong Ha Nguyen, Lam M Nguyen, and Marten van Dijk. Tight dimension independent lower bound on the expected convergence rate for diminishing step sizes in sgd. Advances in Neural Information Processing Systems, 32, 2019.
11

---

Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. arXiv preprint 1rX14:1411.5417, 2014.
Hoang Tran and Ashok Cutkosky. Better sgd using second-orde momentum. arXiv preprint arXiv:2003.03665 2021.
Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. A hybrid stochastic optimization framework for stochastic composite nonconvex optimization. arXiv preprint arXi:: 2019.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: faster and more general. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 2719-721222 2728, 2017.
Di Wang, Minwei Yc, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. arXiv preprint arXiv: 0188802025555 2018.
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pages 6526-6535. PMLR, 2019a.
Lingxiao Wang, Bargav Jayaraman, David Evans, and Quanquan Gu. Efficient privacy preservng stochastic nonconvex optimization. arXiv preprint arXiv:/910. 13659, 2019b.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Proceedings of the ACM International Conference on Management of Data, pages 1307-1322, 2017.
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 1922-39223 2017.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3925-3936, 2018.
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 2006v:2006.1350, 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes]
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you diseuss any potential negative societal impacts of your work? [No] this is theoretical paper. has no potential negative societal impacts
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL.)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "pJUa5WBQd3", "reviewer": "Reviewer_85uj", "summary": "The paper proposes a new privacy-preserving algorithm and proves convergence guarantees on the existing differentially private normalized SGD algorithm and the variant proposed in the paper. The new variant of sensitivity reduced normalized sgd achieves better convergence guarantees on smooth non-convex problems than previous algorithms. The improvement comes from using tree-aggregation technique that reduces the amount of noise needed to make partial sums differentially private.", "questions": "Lines 103-111: Since the noise is being added to each gradient to make each of them differentially private, and the gradients in an epoch come from different samples, even after summing the gradients in an epoch, I think the differential privacy for each sample will remain  $(\\epsilon/\\sqrt{t}, \\delta/t)$. I think the composition rule applies when the gradients are from the same sample, but here since a sample will not be seen until the next epoch, the differential privacy guarantee does not reduce. Is the paragraph explaining the case when gradients are coming from the same sample (that is, GD instead of SGD)? Can the authors clarify this?\n\n\nTypo in Algorithm 1: step size is missing in the statement $w_{t+1} ← w_t − m_t/\\|m_t\\|$", "limitations": ".", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper uses the tree-aggregation technique to propose a new technique that achieves better error guarantee on smooth, non-convex objectives than prior works (although the dependence on the dimension $d$ and $\\epsilon$ is worse).\n2. The paper presents a new analysis of differentially private normalized sgd which achieves same error rates as previous papers, without needing any privacy amplification techniches or needing full batch gradient descent which were needed in previous papers.\n\n\nWeaknesses:\n1. Although the error dependence of algorithm 2 on N is better, the dependence on d and $\\epsilon$ is worse for the new algorithm.\n2. The paper admits that runtime is worse for the new algorithm is proportional to $N^{11/3}/d^{2/3}$. Even in the regime when $N$ is proportional to $d$, this is $N^3$. Also, number of steps needed by algorithm 1 is proportional to $N^2$. Both of these numbers are large, but the $N^3$ runtime of the new algorithm is particularly problematic.\n3. The paper admits that it is not obvious that privacy amplification by shuffling can be directly applied to their tree-aggregation based method.\n4. The paper does not have any experiments showing the convergence properties of the new algorithm. I understand that this is a theoretical paper, but some small scale experiments would be nice to better gauge the algorithm.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_gLSYJUHpH_", "reviewer": "Reviewer_vQgL", "summary": "The paper proposed a few new algorithms for private ERM. The key idea of the new algorithms is using tree aggregation in momentum normalized SGD from Cutkosky and Mehta, 2020. The proposed algorithms can achieve better convergence rate than the existing method.", "questions": "The results looks quite solid to me. One question I have is why to use normalized SGD as the base algorithm, could the authors elaborate more on it?", "limitations": "Limitations are well-discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The idea of using tree aggregation for momentum seems to be quite novel in the field. \n2. The proposed algorithms can achieve better convergence rate.\n\nWeaknesses:\n1. The proposed algorithm seems to require a larger memory to store some tree aggregation nodes.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Wy0o5g_AkBx", "reviewer": "Reviewer_nfxU", "summary": "This paper proposes the use of momentum techniques in conjunction with the tree aggregation framework in differential privacy to obtain better rates for differentially private stationary points for the empirical loss. This problem has got recent attention in the literature, and all existing rates are slow ($O(d^{1/4}/\\sqrt{N\\epsilon})$) and require high running time. This paper focuses on both aspects, first providing algorithm with the above rate but with better running time, which is primarily based on noisy SGD with momentum (which crucially makes use of tree aggregation). And second, providing a sharper rate of $O((d/[N\\epsilon]^2)^{1/3})$ for this problem (gradient complexity of the method is $O(N^{7/3}\\epsilon^{4/3}/d^{2/3})$, but running time is actually at least cubic in the sample size). This is achieved by the use of a recursive gradient estimator, for which its terms have low sensitivity due to the small displacement of iterates, together with smoothness of the loss. ", "questions": "1. Line 120:  The notation of the samples in the dataset from $x$  to $z$ is confusing, as $x$ already been used for data points. Maybe they should avoid summing intervals $[x,y]$ and prefer denoting intervals as $[y,z]$. This applies to other parts of the paper where this notation is used. \n2. Page 4, line 143: an extra 'in' after m_t. \n3. Page 4, equations after line 143. I find confusing that the sum in the second equality goes from $x+1$ to $y$. Does this mean that e.g., when $x=y$ we get an empty sum? BTW, it would be highly beneficial that, before unraveling the formula for $m_t$, the recursion $m_t=(1-\\alpha)m_{t-1}+\\alpha \\nabla f(w)$ is introduced. Also there is a typo: w'_t should be w_{t'}. \n4. Algoritm 1, page 5. It is never said (only in the appendix) what $S_i[1]$ is. Besides, the '$b-(S_i[1])$' I think should be '$t-(S_i[1])$'. \n5. Algorithm 1, when generating the noise map $Z$, shouldn't it be $\\chi_{[a2^b + 1 : (a+1)2^b]} and Z[a2^b + 1 : (a+1)2^b]$? \n6. Page 5, line 157. $f_{[x,y)}$ should be $f_{[x,y]}$?\n7. Page 5, line 161: $q$ is used to indicate the data point that is different on the neighboring datasets, but $q$ is already been used to indicate the epochs in the algorithms. This is not a mistake, but please consider a different notation. Other repetitions of use in notation (e.g. for $R$) are present throughout, which make reading quite confusing.\n8. Page 7, Algorithm 2. $q_i$ is defined in the third line, but when it is actually used, it should be q_t instead of q_i, and indeed I think one could simply use '$q$' since It is defined by $t = qN + r$. \n9. Page 7, Algorithm 2. I couldn't follow why there are two types of noises, depending on whether $t\\leq 2N$ or larger. Is there a fundamental reason for this? I am also confused about the fact that the algorithm seems to rebuild all estimators from scratch every time they are needed, and then new noise is added to them. In this sense, it is not entirely clear to be that the privacy analysis here is accounting for all these repeated noise estimates. I would think it's easier and more natural to reuse the privatized terms from previous iterations, but possibly I am missing something here.\n10. Page 7, line 196: should be an N instead of T in the rate? \n11. Page 8, equation (2). Correct $G_{[1:t]}$ and $\\alpha_{[1:t]}$ by $G_{[1,t]}$ and $\\alpha_{[1,t]}$.\n12. Page 8, equation (3). What is $r$ here? There could be multiple choices for it. Also, the notation is confusing, because of the use of $r_{[a,b]}$. I think it would be easier to understand the decomposition if they explicitly say that they are considering $t = qN + r$. \n13. Equation (4) after line 551: Should Compose(t) be Compose[1,t] instead?\n14. Line 472: $F_i$ should be $G_i$? \n15. Line 492 and Appendix C in general: sometimes the bold notation of the functions $f_i$ is dropped.  Even in algorithm 5 f_1 is not written in bold but the rest iterations are. \n16. Proof of lemma 11 (below line 564), in the first inequality there is a term $(1-\\alpha)^t$ that should be $(1-\\alpha)^{t-i}$. However, it is correct it in the next inequality. \n\n\n\n\n", "limitations": "Yes. Limitations on running time and possible additional improvements are discussed. It is not discussed though how far from tight the obtained upper bound is, which I think it is an important consideration.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This is a definite improvement upon the state of the art.\n2. The problem is of key relevance in differential privacy and  machine learning.\n3. At the technical level, the algorithms do not require privacy amplification techniques, although they use multiple random shuffles of the data, which is somewhat baffling. Regarding this last point, I wonder whether the shuffling is necessary at all: I suspect this can be circumvented using analyses of incremental SGD, such as Nedic, Bertsekas (Incremental subgradient methods for nondifferentiable optimization, SIOPT 2001).\n\nWeaknesses:\n\n1. The improvements seem to be marginal, compared to existing literature.\n2. Regarding algorithmic performance it is arguably more interesting to understand the out of sample performance of the algorithm. \n3. The technique of recursive gradient estimation, used particularly in the second method, is already well known (see e.g., BGM'21 paper cited, and also Bassily, Guzman, Nandi 2021: \"Non-Euclidean Differentially Private Stochastic Optimization\"). The paper does not reflect this fact in its presentation. The main difference between the current submission and past work is that in the current paper this is analyzed for multiple passes on the data, which adds another layer of complexity into the analysis.\n4. The paper contains typos and some small inconsistencies which make reading difficult.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept