Algorithmic Instabilities of Accelerated Gradient Descent
Authors: Amit Attia
Tomer Koren
Venue: NeurIPS 2021 Poster (2021)
Keywords: Accelerated Gradient Descent
Nesterov Acceleration
Algorithmic Stability
Uniform Stability
Convex Optimization

Abstract: We study the algorithmic stability of Nesterov's accelerated gradient method. For convex quadratic objectives, Chen et al. (2018) proved that the uniform stability of the method grows quadratically with the number of optimization steps, and conjectured that the same is true for the general convex and smooth case. We disprove this conjecture and show, for two notions of algorithmic stability (including uniform stability), that the stability of Nesterov's accelerated method in fact deteriorates exponentially fast with the number of gradient steps. This stands in sharp contrast to the bounds in the quadratic case, but also to known results for non-accelerated gradient methods where stability typically grows linearly with the number of steps.

Algorithmic Instabilities of Accelerated Gradient Descent
Amit Attia
Tomer Koren
Blavatnik School of Computer Science Tel Aviv University tau. ac. il
Blavatnik School of Computer Science Tel Aviv University, and Google Research tkoren@tauex. tau. ac il
Abstract
We study the algorithmic stability of Nesterov's accelerated gradient method. For convex quadratic objectives, Chen et al. [10] proved that the uniform stability of the method grows quadratically with the number of optimization steps, and conjectured that the same is true for the general convex and smooth case. We disprove this conjecture and show, for two notions of algorithmic stability (including uniform stability), that the stability of Nesterov's 's accelerated method fact deteriorates exponentially fast with the number of gradient steps. This stands in sharp contrast to the bounds in the quadratic case, but also to known results for non-accelerated gradient methods where stability typically grows linearly with the number of steps.
Introduction
Algorithmic stability has emerged the last decades central tool for generalization analysis of learning algorithms. While the classical approach in generalization theory originating in the PAC learning framework appeal uniform convergence arguments, more recent progress stochastic convex optimization models, starting with the pioneering work of Bousquet and Elisseeff [6] and Shalev-Shwartz al. [24], has relied on stability analysis for deriving tight generalization results for convex risk minimizing algorithms.
Perhaps the most common form of algorithmic stability is the called uniform stability [6]. Roughly, the uniform stability of a learning algorithm is the worst-case change in its output model, in terms of its loss Bousquet and Elisseeff [6] initially used uniform stability to argue about the generalization of empirical risk minimization with strongly convex losses. studied the stability effect of regularization on the generalization of convex models. Their bounds were recently improved in a variety of ways [13, 14, 7] and their approach has been influential in variety of settings (e.g., 18, 16, 9). In fact, to this day, algorithmic stability is essentially the only general approach for obtaining tight (dimension free) generalization bounds for convex optimization algorithms applied to the empirical risk (see 24, 12).
arbitrary example, when replacing single sample in the data set used for training.
al. [24] revisited this concept and
Significant focus has been put recently studying the stability properties of iterative optimization algorithms. Hardt et al. [17] considered stochastic gradient descent (SGD) and gave the first bounds its uniform stability for convex and smooth loss function, that grow linearly with the number of
optimization steps. As observed by Feldman and Vondrak [13] and Chen et al. [10], their arguments also apply with minor modifications to full-batch gradient descent (GD). Bassily et al. [5] exhibited significant gap in stability between the smooth and non-smooth cases, showing that non-smooth GD and SGD are inherently less stable than their smooth counterparts. Even further, algorithmic stability has also been used as an analysis technique in stochastic mini-batched iterative optimization (e.g., 25, 1). and has been proved crucial to the design and analysis of differentially private optimization algorithms [26, 4, 15]. both of which focusing primarily on smooth optimization.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

Having identified smoothness as key to algorithmic stability of iterative optimization methods, the following fundamental question emerges: how stable are optimal methods for smooth convex optimization? In particular, what is the algorithmic stability of the celebrated Nesterov accelerated gradient (NAG) method [22]-a cornerstone of optimal methods in convex optimization? Besides being a basic and natural question in its own right, its resolution could have important implications to the design and analysis of optimization algorithms, as well as serve to deepen our understanding of the generalization properties of iterative gradient methods. Chen et al. [10] addressed this question in the case of convex quadratic objectives and derived bounds on the uniform stability of NAG that grow quadratically with the number of gradient steps (as opposed to the linear growth known for GD). They conjectured that similar bounds hold true more broadly, but fell short of proving this for general convex and smooth objectives. Our work is aimed at filling this gap.
1.1 Our Results
We establish tight algorithmic stability bounds for the Nesterov accelerated gradient method (NAG). We show that, somewhat surprisingly, the uniform stability of NAG grows exponentially fast with the number of steps in the general convex and smooth setting. Namely, the uniform stability of T T-steps NAG with respect to dataset of n examples in general exp((2(T)) and in particular, after merely T = (log n) steps the stability becomes the trivial F2( (). This result demonstrates a sharp contrast between the stability of NAG in the quadratic case and in the general convex, and disproves the conjecture of Chen et al. [10] that the uniform stability of NAG in the general convex setting is (TT)/n), as in the case of a quadratic objective.
Our results in fact apply to a simpler notion of stability that is arguably more fundamental the context of iterative optimization methods-which we term initialization stability. The initialization stability of an algorithm A (formally defined in Section 2 below) measures the sensitivity of A's output to an e-perturbation in its initialization point. For this notion, we demonstrate a construction of a smooth and convex objective function such that, for sufficiently small e, the stability of T-steps NAG is lower bounded by exp() Here again, we exhibit a dramatic gap between the quadratic and general convex cases: for quadratic objectives, we show that the initialization stability of NAG is upper bounded by OTTe).
For completeness, we also prove initialization stability upper bounds in a few relevant convex optimization settings: for GD, we analyze both the smooth and non-smooth cases; for NAG, give bounds for quadratic objectives as well as for general smooth ones. Table summarizes the stability bounds establish compared existing bounds in the literature. Note in particular the remarkable exponential gap between the stability bounds for GD and NAG in the general smooth case, with respect both stability definitions. Stability lower bounds for NAG are discussed in Sections 3 and 4; initialization stability upper bounds for the various settings and additional uniform stability bounds are detailed in the full version of the paper [3].
METHOD
SETTING
INIT. STABILITY
UNIE. STABILITY ((T/n)
REFERENCE
GD
convex, smooth convex, non-smooth
((e)
Hardt et al. [17]
GD
O (
@ nTT @ (n) exp()(T))/n
Bassily et al. [5]
NAG
convex, quadratic
(TT)) eXp(O(T))
Chen et al. [10]
NAG
convex, smooth
(this paper)
Table 1: Stability bounds introduced in this work (in bold) compared to existing bounds. For simplicity, all
bounds in the smooth case are for 1) = @(Ip)) The lower bounds for NAG are presented here a simplified form and the actual bounds exhibit a fluctuation in the increase of stability; see also Fig. 2 and the precise results in Sections 3 and 4.
Finally, we remark that our focus here is on the general convex (and smooth) case, and we do not provide formal results for the strongly convex case. However, we argue that stability analysis in the latter case is not as compelling as in the general case. Indeed, a strongly convex objective admits a unique minimum, and so NAG will converge to an e-neighborhood of this minimum in Olog (1/e)) steps from any initialization, at which point its stability becomes O(e); thus, with strong convexity perturbations in initialization get quickly washed away as the algorithm rapidly converges to the unique optimum. (A similar reasoning also applies to uniform stability with strongly convex losses.)

---

1.2 Overview of Main Ideas and Techniques
We provide intuition constructions and highlight some of the key ideas leading to our results. We start by revisiting the analysis of the quadratic case which is simpler and better understood.
Why NAG stable for quadratics: Consider a quadratic function f with Hessian matrix H z For analyzing the initialization stability of NAG, let consider two runs of the method initialized at Xo. respectively, and let (x,+Yr), (E,, F:) denote the corresponding NAG iterates at step Further, let us denote by A & X, - & the difference between the two sequences iterates. Using the update rule of NAG (see Eqs. (I) and (2) below) and the fact that for quadratic f. differences between gradients can expressed as Vf(x) - fx(') = H(x - x') for any x, E R Rdd is straightforward to show that the distance A evolves according to
1+ (1 - ())H) + Y,) - 1,-
This recursion can be naturally put in matrix form, leading to:
[1 (1+Y -Yx -001 (
where here A = = nH. Thus, for a quadratic f. bounding the divergence || between the two NAG sequences reduces controlling the operator norm of the matrix product above, namely
(1 (1+Y8)A
-YEA 10)
Remarkably, can be shown that this norm is O(1) for any 3 3 and any choice of -1 & YI....-Ye S 1. (This can be seen by writing the Schur decomposition of the involved matrices, as we show in the full version of the paper (3].t) As a consequence, the initialization stability of NAG for quadratic objective is shown grow only linearly with the number of steps
What breaks down in the general convex case: For a general convex (twice-differentiable and smooth) f. the Hessian matrix is of course no longer fixed across the execution. Assuming for simplicity the one-dimensional case, similar arguments show that the relevant operator norm is the form
(1 (x+
-YEAK 0
related to Hessians of taken at suitable points along the optimization trajectory. However, if Aę are allowed to vary arbitrarily between steps, the matrix product above might explode exponentially fast, even in the one-dimensional case! Indeed, fix yx 0.9 for all k, and set A = 0 whenever & mod 3 = O and A = otherwise; then using simple linear algebra the operator norm of interest be shown to satisfy
where 0 A1....,
[((
1.9 -0.9 (1.
1.9 (19
- 6/3
0 2.71 -1.71
1/3
0
1.15'.
How a hard function should look like: The exponential blowup we exhibited above hinged on worst-case sequence A1..... A, that varies significantly between consecutive steps. remains unclear, however, what does this imply for the actual optimization setup we care about, and whether such a convex and smooth function f. Our main results essentially
sequence can be realized by Hessians answer the latter question on the affirmative and build upon construction of such function f that directly imitates such bad sequence.
Concretely, we generate a hard function inductively based on a running execution of NAG, where in each step we amend the construction with "gadget" function having piecewise-constant Hessian (that equals either or the maximal f); see Fig. for an illustration of this construct. The interval pieces are carefully chosen based on the NAG iterates computed so far in way that slightly perturbed
Chen al. [10] give alternative argument based Chebyshev polynomials.

---

A f()) 4 f()) 8
Figure I: function (left) constructed of four instantiations of our "gadget" (right) at increasing sizes. During an interval with zero Hessian, the trajectory with the larger momentum gains distance. When reaching an interval with maximal Hessian (depicted here as iteration f), the "slow" trajectory experiences a larger gradient which gives it larger momentum and makes become the "faster" one.
execution would traverse through intervals with an appropriate pattern Hessians that induces behaviour similar to the one exhibited by the matrix products above, leading to exponential blowup the stability terms. Fig. shows a simulation of the divergence between the two trajectories of NAG construct, illustrating how the divergence fluctuates between positive
on the objective function absolute value growing exponentially with time. More technical details and negative values, with its on this construction can be found in Section 3.
10"
10a
10a
10F
107
10'
10a
-10
-367
-107
-10-
50
100
150
200
250
300
250
500
750
1000
1250
1500
1750
Boration
Eoration
(a) construction for 1) 1/(2;);;
(b) construction for 1/(10/))
Divergence between trajectories (in log-scale) along the optimization process for different values of At steps / = @(i/))) (i= 1,2,...) NAG experiences an exponential growth the divergence, as reaches an interval with maximal Hessian. The dashed lines depict our theoretical exponential lower bound.
Figure 2:
From initialization stability to uniform stability: Finally, we employ a simple reduction to translate results regarding initialization stability to relate uniform stability in the context of empirical risk optimization, where one uses bfull-batch) NAG to minimize the (convex, smooth) empirical risk induced by sample S of examples. Coneretely, we can arrive at a scenario where after one step of NAG on the original and modified samples the respective iterates risks simulate our bad function from before. Thus, we again end up with an exponential increase in the divergence between the executions, that leads similar increase the algorithmic (uniform) stability: the latter becomes as large as Q(1 after merely T = O (log n) steps of full-batch NAG. The formal details of this reduction can be found in Section 4.
show that by replacing single example in S,
((1 /nt) away from each other, whereas the remaining steps both empirical
1.3 Discussion and Additional Related Work
It interesting to contrast our results with what is known for the closely related heavy ball method [23]. Classic results show that while for convex quadratic objectives (properly tuned) heavy ball method attains the accelerated (1/T72 convergence rate, for general convex and smooth functions it might even fail to converge at all (see 20). More specifically, known that there exists objectives for which heavy ball assumes cyclic trajectory that never gets close to the optimum; it is then not hard

---

to turn such a construction to an instability result for heavy ball, as a slight perturbation in the cyclic pattern can be shown to make the method converge to optimum.
Also related to our work is Devolder et al. [11], that analyzed GD and NAG with inexact first-onder information, namely, in a setting where each gradient update is contaminated with bounded yet arbitrary perturbation. Interestingly, they showed that in contrast to GD, NAG suffers from an accumulation of errors-which appears analogous to the linear increase in initialization stability the latter experiences in the quadratic case. At the same time, in the general convex case their results might seem to be at odds with ours as we show that even a single perturbation at initialization suffices for extreme instabilities. However, note that they analyze the impact of perturbations on the convergence rate of NAG (in terms of objective value), whereas algorithmic stability is concerned with their effect on the actual iterates: specifically, initialization stability captures to what extent the iterates of the algorithm might stray away from their original positions as a result of small perturbation in the initialization point.
Various forms of stability are well-studied in the literature of dynamical systems, with the notion of Lyapunov stability being perhaps the most notable one. While related to our study, Lyapunov stability is concerned with stability of solution due perturbation near point of equilibrium of the system, and the solution is then said to be stable if the system remains in equilibrium despite this perturbation. In contrast, we are concerned with an arbitrary perturbation to the system (or algorithm) initialization point, which is the case of interest for initialization stability.
Our work leaves few intriguing open problems for future investigation. Most importantly, it remains unclear whether there exists a different accelerated method (one with the optimal (11772) rate for smooth and convex objectives) that is also poly(?) -ttable. Bubeck et al. [8] suggested geometric alternative to NAG that comes to mind, and it could be interesting to check whether this method or a variant thereof more stable than NAG. Another open question stability lower and upper bounds for NAG in the regime < // B: while our lower bounds have an exponential dependence on 17. the upper bounds do not. Finally, it could be interesting to determine whether the (TT)) initialization stability bound we have for NAG in the quadratic case is tight (the corresponding uniform stability result is actually tight even for linear losses. but this may not be the case for initialization stability).
resolve the gap between our
2 Preliminaries
In this work we are interested in optimization of convex and smooth functions over the d-dimensional Euclidean space Rd. A function ff said to be f-smooth (for B > 0) if its gradient is B-Lipschitz namely, if for all u, V E Rd it holds that (f) - (fvll s Bllu- -vl.
2.1 Nesterov Accelerated Gradient Method
The Nesterov Accelerated Gradient (NAG) method [22] we consider in this paper takes the following form. Starting with and yo Xo, it iterates for / = 1, ...:
x, = Yr-1-11 (vv/(r-)
(1)
y, x, + (x, - x;-1),
(2)
where y, /42 and 17 > 0 is step-size parameter. For a B-smooth convex objective and 0 < 7 S 1/8, B. this method cxhibits the convergence rate O(1/ ; for 17 = 1/B. this gives the optimal convergence rate for the class of f--mmooth convex functions (see [21]). We remark that while NAG appears in several other forms in the literature, many of these are in fact equivalent to the one given in Eqs. (1) and (2). For more details, see the full version of the paper [3].
Throughout, we use the notation NAG (f Xo,, f, .7) to refer to the iterates (x, yr) at step of NAG on f initialized at xo with step size n7. We sometimes drop the step size argument and use the shorter notation NAG(S. ff xx. 1) when 17 is clear from the context.
We will use the following definitions and relations throughout. We introduce the following notation for the momentum term of NAG, for all > O:
m, e (0xx-xx-1)
-
(3)
FFrr concreteness, we focus here on the most common choice of momentum parameters Yr. but our results can be adapted similar settings.
5

---

Using this notation, we have that
X yr-1 1/v(()))-)).
(4)
yr = X, m, = =1-1 -nV/((r-1)++
-
(5)
m,
(6)
Here, Eq. (6) follows from Eqs. (3) (5) via
my = Yr xx-1)
(Eq. (3))
= = - / - -x--1)
(Eq. (4))
(x + m1-1 n/ ())(() ( x1-1)
(Eq. (5))
- = -y:mm--1-V/(0)- -)V((r-)))
2.2 Algorithmic Stability
We consider two forms of algorithmic stability. The first is the well-known uniform stability [6], while second is initialization stability which we define here.
Uniform stability. Consider the following general setting of supervised learning. There is a sample space & of examples and unknown distribution 'D over Z. We receive training set = (2)...., 2n)
of n samples drawn i..dd from D. The goal is finding a model w with small population risk:
R(w) - E (w::)))
where ((w; z) is the loss of the model described by w on an example z. However, as we cannot evaluate the population risk directly, learning algorithms will be applied on the empirical risk with respect to the sample given by
(s(w) A Σ ((w 1=1
In this paper, our algorithm of interest in this context is full-batch NAG, namely, NAG applied to the empirical risk Rs. We use the following notion of uniform stability.
Definition (uniform stability). Algorithm A is c-uniformly stable if for all S' e z" such that S,5' differ in at most one example, the corresponding outputs A(S) and A(S') satisfy
sup (E(A(S); - ((A(S);; 2) s.
zeZ
We use A,f to denote the infimum over all c > 0 for which this inequality holds.
Initialization stability. A second notion of algorithmic stability that we define and discuss in this paper, natural in the context of iterative optimization methods, pertains to the stability of the optimization algorithm with respect to its initialization point. Initialization stability measures the sensitivity of the algorithm's output small perturbation in its initial point; formally.
Definition (initialization stability). Let A be an algorithm that when initialized at a point x e Rd. produces Axx) Rd as output. Then for the initialization stability of xo (Rd is given as ginit A
(xo. c) = ((5o) - Axxo)l io E Rd ||ã0 xoll s e).
Initialization Stability of NAG
In this section we prove first main result, regarding the initialization stability of NAG:
Theorem 3. Let e. G. > 0 and 0 < n S 1/8. Consider two initialization points xo 0, E. Then, there exists a convex, ß-smooth, G-Lipschita,funttin function f that attains a minimum over R. and universal constants c1. > O, such that the sequences (N,, Vr) ) = NAG(f.xo.1,n) and (x, NAG(f.āo. f8.0 1,7) satisfy
N (Xo, c) 2 [x, - R,1 Z min G
38. c2e
VIE (T [ (11+2)2) : 1,2.....
Furthermore, for all > 10 mp
(In
3G +3) holds that NAG, (xo, e) 2 37
2pc
"We give here definition suitable for deterministic algorithms, which suffices for the context of this paper. Similar definitions exist for randomized algorithms; see for example [17, 13J.

---

In words, the theorem establishes an exponential blowup in the distance between the two trajectories x, and &, during the initial O(1/e) steps, after which the (lower bound on the) distance reaches constant and stops increasing. Notice that in the blowup phase, an increase in distance happens roughly every np steps; indeed, the actual behaviour of NAG on the function we construct exhibit fluctuations in the difference X, x,, as illustrated in Fig. 2. We remark that a similar bound holds also for the yr sequence produced by NAG.
Construction. Throughout this section, we will assume without loss of generality that 0 < e < G/2p. (When 2 G/2B our result holds simply for constant function.) To lower bound the initialization stability and prove the theorem, we will rely on the following construction of functions fo. fi....: R - R. Let the parameters G. n.n.c 0 be given, and for all i 2 0 define - [10/np](i 2). The construction proceeds follows:
(i) Let fx(x) - -Gx;
(ii) For 2 1:
Let (Xm, Yn, = (f-1.. and (Eng Fn,) = NA n);
Define fi R - R as follows:
fi(x) - Gxx B S S 1 1/3 s.st & [ymnon +yy dzdy.
max
where ym min(yn, (Yn, Fng ym ma Jn
(iii) Let M = supli 0 max, fzj(x) < < v s
Note that the above recursion defines infinite sequence of functions fo- fi. f2..... IR R. Ultimately, we will be interested in the functions {fiigs which we will analyze in order to prove the instability result. Further, note that max, Vf((x) < G thus M itself is well-defined, possibly co. The functions constructed above are not bowerebounded (and thus do not admit a minimum). Below we define lower-bounded adaptation of fM (assuming 1 S M < co, which is proved in Lemma 7 later on). Our modified version of fM, termed f defined by a quadratic continuation of fMr right of p ynm up plateau. This construction defined formally as:
fM (x) (x)
x X p: P <<sEp- D [M(())) otherwise.
f(x) SM (P) + (fM p) f( pp) (M) VMM
Analysis. We start by stating few lemmas we will use in the proof of main theorem. Our focus is on the functions/ fi for 0 $ i S M, deferring the analysis of f to after we establish that M is finite. First, we show that the functions we constructed are indeed convex, smooth and Lipschitz. Lemma 4. For all i M, the function fi convex, B-smooth and G G-Lisschitz Proof. The second derivative of fi is
fixx B 1 3 S sist. 2 [yn min max E {0. B).
Ynn Thus, fi is convex and f-smooth. We lower bound the first derivative by
1[3 f i min max
v((x) --0
dz 2-G
and by the definition of M, (x) < -G/2. /2. Hence for all x E R we have (f((() E (-G,,-G/2)) is G-Lipschitz over R.
Next, analyze the iterations of NAG on fi for any given 0 i S M. Fix such index i and consider (X,, yr) = NAG 0, and (i, F,) = NAG(fi. e) for all S T for some T 2 ni+1. We introduce the following compact notation for differences between the NAG terms related to the two sequences:
A 2 x, - &r From the update rules of NAG (Eqs. (4) to (6)), have that
D A yr Rr.
Df f((x)) (f.)),
AT" 2 m, m.-
A A/-1 -7A/1 1-1
A/' A. ATT A. - -1A/ + A,"
(8)
A," = Y, ~
(9)
Our next lemma below describes the evolution of the differences A/ and A," in terms of A/.
7

---

Lemma 5. For all ST
p 4/
ifi fnzt
and A" Yr(4 nBaj-)) Y,A
ift E (nz 1)j= otherwise.
0
otherwise,
The following lemma summarise the evolution of the distance between the sequences yr and år at steps / [nj)isisi+] and for f > fi+l. The exponential growth is achieved by a balance between the difference in momentum terms and the difference between the sequences.
Lemma 6. For the difference terms A7, we have the following:
(i) For all
s it holds that EnBl S M1++ 51BAA
(ii) For all j s it holds that | ymax
>nys 2 3/e.
(iii) For all 1 n1+1, holds that |A71 2 |
Finally, we can show that f well-defined by proving that is finite the following lemma. The bound M also indicate that after (log )) steps the two trajectories yr. Fr reach a constant distance.
Lemma 7. It holds that s M In 3G (in particular, M is finite), and ymax
G 3P
Now we can return to our f. First, we show indeed posses the basic properties for Theorem Lemma 8. function f convex, B-smooth, G G-Lisschitz and attains a mmnnmmumx* E arg min, fx) s.f. [Xo - x²1 = O ([(G///B))) log(G/ for E (0,
The final lemma we require shows that the distance between the two trajectories is the same for f and fM. This holds true since the two functions coincide for S p, after which the iterates reach plateau which induces similar stability dynamics as the linear part of fM at >
Lemma 9. Let (x) NAG(f, O,t. and (K,, 51) NAG(f,c,t.) C,T.) be the iterations of NAG on from our initialization points. Similarly, for fM. let (&,, 51) NAG( fM 0. m) and (X, Fr) NAG EAG,,M.e.t.
e,t, .T). Then for all t, we have that x, -x, 8, N, and yr 5r 80 F1.
We defer the proofs of Lemmas 5 to 9 to the full version of the paper [3], and proceed to prove our main result.
Proof of Theorem Based on Lemma it suffices to show that the lower bound holds for the function fM. Let deal with is when i < M + 1. We already established with Lemma 6 that | 2 3i-1e. Since I n, (i 1) 2 nBt/11 2. Hence,
11 In(3),c2 c2 3 Let / = for some 2 1. The first case we will
5 |AX 3781/11-3e = JA 2 I cne
To relate to |x; - -xyl
|x, xrl |A%
|
|
(Eq. (8))
A
A M
Yi
(Lemma for f .N.........1.. +2)
|4%
|A M-1+1
(Since 1 2 1=00 + Yr S 1)
nB
|
5
5
|
2 eze Smprr E.
(n s })
Here, (-) follows from Lemma if i 1 and the case if 1 follows by combining Lemma
and A = 0 which implies that A = O. If > nM+1 (includes the case of M + and

---

3G r [10/np]
2pc + +3) from Lemma 7), since 1 1 2 MM+1+
1x - x, 1 n
(Eq. (7))
=1
(Lemma 5)
|
(Lemma 6)
And using Lemma we conclude that [x, - of Theorem beside attaining minimum, and using Lemmas and 9, f posses all the properties needed for Theorem 3.
@ Hence, with Lemma 4, fur holds all properties
38
4 Uniform Stability of NAG
In this section we present our second main result, regarding the uniform stability of (full-hatch) NAG. This is given formally in the following theorem.
Theorem 10. For any G. l.u y and n 2 4 such that 0 17 S f, there exists a loss function ((w; that convex, B-smooth and G-Lipschitz in w (for every z %) and universal constants c3, C4 such that the uniform stability of -teps full- NAG with step size is
gunif NAG, (n) 2 min
G 38
cSppT G²
VT (T
10 " nB n-3 (i i 112..2...
n
Furthermore, for all T
4 (In
Be + 3) holds that 6unif NAGy _ (n) 2
G 38
np
The comments following Theorem 3 regarding the exponential blowup and the fluctuating behaviour also apply here. Note also the perhaps surprising inverse dependence on & (ßr² is also O(1BB). The dependence can be explained by the fact that smooth optimization over highly non-smooth yet still G G-Lipschitz function must have small step size (with 17 s I/B) which improves stability.
Construction. We denote the given parameters for the theorem with G. p. f).n We will use the construction from Section 3 with the properties of Theorem in order create loss function and samples which will have the same optimization for f 2 1. For the construction we define the following setting of G, B, n:
3 f)
BIf n-3
G=
B=
Using these parameters, we obtain f from the construction of Section As we proved in the previous section, this is the function for which Theorem 3 holds. Note that for T < n1, the lower bounds already holds even for quadratics, as we show in the full version the paper [3]. We also define the following functions,
((w; 1) O,
(10)
((w;2) & -BnTW + f
" [ 1[2 E Go)dddy,,
(11)
and further let ((w:3) = -Gw, (w: = Gw, and (w::5) f(w). Note that all are convex, B-smooth and G-Lipschitz. Let function ((w;z) over R x %. Our samples of interest are S = (1. 3, 4, 5....... E 2" and S' 32, 2". Thus, the empirical risks Rs, Rs. corresponding S, given by
(1.2.3.4.3 5, be our sample space, consider the loss
3 f(w) n
Rs(w) (w(
f(w),
(12)
n n1 (s-(w) -w)
n
n
f(w).
(13)
n
n
Analysis. The key lemma below shows that we constructed scenario that reduces the problem of analyzing the uniform stability of full-batch NAG analyzing its initialization stability the function ff we constructed in Section 3.
Lemma 11. For all 1,2, ... we have that
NAG(F. (. NAG(Rs, f)), NAG(f.e,t.m) 0,

---

Using this key lemma. Theorem 10 follows immediately by setting c1/4 / and c4 c2/4, for the samples S, S' we defined and = 3. As ((w:3) -..,
( e(T;: = G
- 1,
and by using the definitions of G. P. e we get the two cases of Theorem 3 which lower bound |xy x as needed. The full proof of Lemma 11 and Theorem 10 can be found in the full version of the paper [3].
Acknowledgments and Disclosure of Funding
We thank Naman Agarwal, Yair Carmon and Roi Livni for valuable discussions. This work was partially supported by the Israeli Science Foundation (ISF) grant no. 2549/19, by the Len Blavatnik and the Blavatnik Family foundation, and by the Yandex Initiative in Machine Learning.
References
[1] N. Agarwal, R. Anil, T. Koren, K. Talwar, and C. Zhang. Stochastic optimization with laggard data pipelines. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, 2020.
[2] Z. Allen-Zhu and L. Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Pagstuul-Leeibniz-Zeee
fuer Informatik, 2017.
[3] A. Attia and T. Koren. Algorithmic instabilities of accelerated gradient descent. arXiv preprint wxXi:2202.02166 2021. Available at https://arxiv http:/aaaavoooggbabaraaaaaa org/abs/2102. 00111
[4] R. Bassily, V. Feldman, K. Talwar, and A. Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 2019.
[5] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
[6] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of machine learning research, 2Mar))499-522 2002.
[7] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pages 610-626. PMLR, 2020.
[8] S. Bubeck, Y. T. Lee, and M. Singh. A geometric alternative to nesterov's 's accelerated gradient descent. arXiv preprint
www.:1506.88877 2015.
[9] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 745-754. PMLR, 2018.
[10] Y. Chen, C. Jin, and B. Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint 1rXiv:1804.000 2018
[11] O. Devolder, F. Glineur, and Y. Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1-2):37 2014.
[12] V. Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. Advances Neural Information Processing Systems, 29:3576-3584, 2016.
[13] V. Feldman and J. Vondrak. Generalization bounds for uniformly stable algorithms. In Advances in Neural Information Processing Systems, pages 9747-9757, 2018.
[14] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279, 2019.
[15] V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439 439-449, 2020.
10

---

[16] A. Gonen and S. Shalev-Shwartz. Fast rates for empirical risk minimization of strict saddle problems. In Conference on Learning Theory, pages 1043-1063. PMLR, 2017.
[17] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning, pages 1225-1234, PMLR, 2016.
[18] T. Koren and K. Y. Levy. Fast rates for exp-concave empirical risk minimization. In Proceedings of the 28th International Conference on Neural Information Processing Systems- 1, pages 1477-1485, 2015.
[19] G. Lan. An optimal method for stochastic composite optimization. Mathematical Programmingg 133(1-2):355-37, 2012.
[20] L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
[21] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume Springer Science & Business Media, 2003.
[22] Y. E. Nesterov. A method for solving the convex programming problem with convergence rate (1/k") 2). In Dokl. akad. nauk Sssr, volume 269, pages 543-541 1983.
[23] B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physies, 4(5):1-17, 1964.
[24] Shalev-Shwarzz, O. Shamir, N. Srebro, and Sridharan. Stochastic convex optimization. In COLT, 2009.
[25] J. Wang, W. Wang, and N. Srebro. Memory and communication efficient distributed stochastic optimization with minibatch prox. Conference on Learning Theory, pages 1882-1919. PMLR, 2017.
[26] X. Wu, Li, A. Kumar, K. Chaudhuri, S. Jha, and J. Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Proceedings of the 2017 ACM International Conference Management of Data, pages 1307-1322, 2017.


Reviews:
[{"review_id": "gGAiNWM_XrJ", "reviewer": "Reviewer_tbGy", "summary": "This paper studies the stability of Nesterov accelerated gradient in the initialization and in the sense of uniform stability. The authors prove lower bounds on the stability parameters, that diverge exponentially in the number of iterations, by building clever one-dimensional adversarial examples. This proves that in the general convex smooth case, Nesterov accelerated gradient can be a lot more instable than in the quadratic case. ", "questions": "", "limitations": "", "rating": 7, "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": "The core of this paper is a technical construction of an adversarial example where Nesterov accelerated gradient is instable. I could not check all the details but I appreciated the good exposition and I believe the math to be clean. \n\nThe counter-example built by the authors does answer rigorously to the question of uniform stability as it is asked by the authors; however the example seems artificial and very adversarial. As explained in the introduction, the concept of uniform stability was originally used to study the generalization of empirical risk minimization; one could wonder whether the conclusions drawn in this paper transpose to more realistic learning settings. For instance, what happens when the functions in the finite sum are no longer adversarial but i.i.d. according to some law? This perspective might be far-reaching, but I would appreciate to have the opinion of the authors on the subject. \n\nThe counter-example of Section 3 is in dimension 1. Could there be a result in larger dimensions? I am asking because the authors use the mean-value theorem in page 14, applied to the gradient of the function. This mean-value theorem does not hold for multi-variate functions. \n\n\nMinor comments: \n- In Theorem 3, why do the authors study G-Lipschitz functions? Could we expect the result to hold without the requirement for the function to be Lipschitz, and without the minimum in the lower-bound? \n- l.204: Did the authors mean O(log 1/\\varespilon) ?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In general, the authors brought a clean answer to a restricted theoretical question, but I would like to see a discussion on the potential insights that could be gained from this. See the main review for suggestions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3,5"}, "extra_text": {}}, {"review_id": "U4cHRmhjaR", "reviewer": "Reviewer_TrR8", "summary": "This paper presents two kinds of Instabilities of Accelerated Gradient Descent. Although with many novel results at the first glance, almost of them  are confusing.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "Strengths: 1. This paper proposes the notion of initialization stability and proves that the NAG is initialization unstable. To this end,  the authors prove many technical lemmas.\n\n2. The authors proved the uniform instability of full batch NAG. Many technical lemmas are proved.\n\n\nWeakness: This paper needs many efforts to improve.\n\n1. The overclaim in the abstract and introduction.  They say they disprove this conjecture proposed in [ Chen et al. 2018]. However, in Sec. 4, they proved the full batch version!  No any stochasticity of the algorithm and the so-called uniform instability actually comes from the initialization stability proposed by the authors. They do not prove the real uniform instability.\n\n2. The initialization stability is similar to the notion of stability in dynamics and PDE. This is reasonable because we may not know whether the dynamic is convergent or not.  However,  in the optimization community,   NAG can be easily guaranteed to converge. And then, two points must get very closed after enough iterations. The initialization stability is useless for any convergent iterates.  The authors can prove the initialization instability because under the conditions given in Theorem 3 one sequence is convergent and the other one is divergent. \n\n3. The uniform stability is proposed by literature and widely used because it can be employed to generalization errors in training problems.  Nevertheless, the authors do not tell us why to introduce the initialization stability and how it is used. It seems the initialization stability is only used for the uniform instability of NAG.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "TzJV1ULsMu", "reviewer": "Reviewer_boQt", "summary": "It is very interesting and attractive to investigate the algorithmic instabilities for the famous Nesterov accelerated gradient descent method. This concepts  are very related to ordinary differential equation, such as initialization stability corresponding to continuous dependence of solution about initialization for long time. The uniform stability is for the objective function. The authors tries to use the so-called uniform stability to describe the NAG under noise cannot obtain the desired result. \n\nThe new concept --- uniform stability is a novel point.  ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "This paper introduce a new concept --- uniform stability to describe the algorithms' stability, which is an originality. But the quality and clarity is not enough. The authors have not shown the clear intuition for why the new concept --- uniform stability is important, just do the computation. Moreover, it looks very interesting that the authors do deeper investigation. If they can compare the stability concept with the approximating ODEs, \n\nSu et al. (2016)  A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights\n                             Journal of Machine Learning Research, 17(153), 1–43, 2016.\n\nShi et al. (2021) Understanding the Acceleration Phenomenon via High-Resolution Differential Equations\n                             Mathematical Programming, Series A,  https://doi.org/10.1007/s10107-021-01681-8\n\nthis paper will become more attractive. \n\nIf the author do more effort and deeper investigation, I would like to improve the my review result. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The content  for the new concept uniform stability and comparison with initialization stability is not enough. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "35"}, "extra_text": {}}, {"review_id": "0L3zj3d5uFe", "reviewer": "Reviewer_Vh9U", "summary": "This paper disproves Chen et al.'s conjecture that Nesterov accelerations leads a quadratic growth of the uniform stability, by showing for adequate notions of stability that NAG detoriates exponentially fast.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "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": "This is an excellent paper. The topic is important: stability of acceleration of the gradient descent. The presentation is really clear, in particular I found section 1.2 \"overview of main ideas and techniques\" insightful. It is rare to have a pedagogical presentation in the last iteration of NeurIPS.\n\nDespite these praises, I have some minor concerns that may, or not, be addressed in a rebuttal.\n- There is no citation associated to \"initialization stability\" that is a $\\ell_\\infty$ control that is quite common in sensitivity analysis. The authors apply it to algorithms in this paper, but at the end, it is the same concept.\n- Only NAG is studied here, but one may ask if the analysis is really linked to the specific value of $t-1/t-2$ or if more general momentum or inertial methods could be studied with the same analysis.\n- The paper can be seen as a worst case analysis, with the construction of \"gadgets\", I would like to know if we may recover Chen et al's results for a wider class of functions: what about polynomials? convex-semialgebraic functions?\n- There is a lot of interesting results in appendix D and E not discussed in the main text, I guess the authors could squeeze a bit some derivation to be able to present at least what is contained in them.\n\nNote: the paper has 31 pages of supplementary materials, mostly proofs of lemmas. The community should at some point recognize that no one is able to carefully check 7 theoretical papers of this length in the span of a month. I believe the proof strategy is correct -- I obviously, and unfortunately, didn't check the hundreds of equations included.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Y.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies uniform stability of Nesterov accelerated gradient descent for smooth convex optimization and proves that, unlike in the quadratic case and contrary to a conjecture by [Chen et al., 2018], the error can accumulate exponentially fast (as opposed to quadratically fast, which happens for quadratics). The crux of the approach is in introducing clever constructions of one-dimensional adversarial examples. Overall, the exposition of the paper is clear and the paper appears technically sound (as far as it was possible to verify by reviewers). The paper adds a solid contribution to understanding of stability of accelerated/momentum methods.
Decision: Accept (Poster)