Algorithmic Instabilities of Accelerated Gradient Descent
Year: 2022

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 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.

text: 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 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.

heading: 1 Introduction
text: Algorithmic stability has emerged over the last two decades as a central tool for generalization analysis of learning algorithms. While the classical approach in generalization theory originating in the PAC learning framework appeal to uniform convergence arguments, more recent progress on stochastic convex optimization models, starting with the pioneering work of Bousquet and Elisseeff [6] and Shalev-Shwartz et 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 so 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 on an arbitrary example, when replacing a single sample in the data set used for training. Bousquet and Elisseeff [6] initially used uniform stability to argue about the generalization of empirical risk minimization with strongly convex losses. Shalev-Shwartz et al. [24] revisited this concept and 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 a 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). Significant focus has been put recently on studying the stability properties of iterative optimization algorithms. Hardt et al. [17] considered stochastic gradient descent (SGD) and gave the first bounds on its uniform stability for a 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 a 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.

heading: 1.1 Our Results
text: 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 )-steps NAG with respect to a dataset of = examples is in general exp(Ω()))/=, and in particular, after merely ) = $ (log =) steps the stability becomes the trivial Ω(1). 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 $ ()2/=), as in the case of a quadratic objective. Our results in fact apply to a simpler notion of stability—one that is arguably more fundamental in the context of iterative optimization methods—which we term initialization stability. The initialization stability of an algorithm (formally defined in Section 2 below) measures the sensitivity of ’s output to an ²-perturbation in its initialization point. For this notion, we demonstrate a construction of a smooth and convex objective function such that, for sufficiently small ², the stability of )-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 $ ()²). 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, we give bounds for quadratic objectives as well as for general smooth ones. Table 1 summarizes the stability bounds we establish compared to 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 to 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] .
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 ²-neighborhood of this minimum in $ (log(1/²)) steps from any initialization, at which point its stability becomes $ (²); 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.)

heading: 1.2 Overview of Main Ideas and Techniques
text: We now provide some intuition to our 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 is stable for quadratics: Consider a quadratic function 5 with Hessian matrix 0. For analyzing the initialization stability of NAG, let us consider two runs of the method initialized at G0, G̃0 respectively, and let (GC , HC ), (G̃C , H̃C ) denote the corresponding NAG iterates at step C. Further, let us denote by ∆GC , GC − G̃C the difference between the two sequences of iterates. Using the update rule of NAG (see Eqs. (1) and (2) below) and the fact that for a quadratic 5 , differences between gradients can be expressed as ∇ 5 (G) − ∇ 5 (G ′) = (G − G ′) for any G, G ′ ∈ ℝ3 , it is straightforward to show that the distance ∆GC evolves according to
∆GC+1 = ( − η ) ( (1 + γC )∆GC − γC∆GC−1 ) .
This recursion can be naturally put in matrix form, leading to:( ∆G C+1 ∆GC ) = C∏ :=1 ( (1 + γ: ) −γ: 0 ) ( ∆G1 ∆G0 ) ,
where here = − η . Thus, for a quadratic 5 , bounding the divergence ‖∆GC ‖ between the two NAG sequences reduces to controlling the operator norm of the matrix product above, namely C∏
:=1
( (1 + γ: ) −γ:
0 ) . Remarkably, it can be shown that this norm is $ (C) for any 0 and any choice of −1 ≤ γ1, . . . , γC ≤ 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].1) As a consequence, the initialization stability of NAG for a quadratic objective 5 is shown to grow only linearly with the number of steps C. What breaks down in the general convex case: For a general convex (twice-differentiable and smooth) 5 , 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 of the form C∏
:=1
( (1 + γ: ) : −γ: :
0 ) , where 0 ≤ 1, . . . , C ≤ 1 are related to Hessians of 5 taken at suitable points along the optimization trajectory. However, if : are allowed to vary arbitrarily between steps, the matrix product above might explode exponentially fast, even in the one-dimensional case! Indeed, fix γ: = 0.9 for all : , and set : = 0 whenever : mod 3 = 0 and : = 1 otherwise; then using simple linear algebra the operator norm of interest can be shown to satisfy ((0 01 0) (1.9 −0.91 0 ) (1.9 −0.91 0 )) C/3 = ( 0 02.71 −1.71) C/3 ≥ 1.15C . How a hard function should look like: The exponential blowup we exhibited above hinged on a worst-case sequence 1, . . . , C that varies significantly between consecutive steps. It remains unclear, however, what does this imply for the actual optimization setup we care about, and whether such a sequence can be realized by Hessians of a convex and smooth function 5 . Our main results essentially answer the latter question on the affirmative and build upon a construction of such a function 5 that directly imitates such a 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 a “gadget” function having a piecewise-constant Hessian (that equals either 0 or the maximal β); see Fig. 1 for an illustration of this construct. The interval pieces are carefully chosen based on the NAG iterates computed so far in a way that a slightly perturbed
1Chen et al. [10] give an alternative argument based on Chebyshev polynomials.
execution would traverse through intervals with an appropriate pattern of Hessians that induces a behaviour similar to the one exhibited by the matrix products above, leading to an exponential blowup in the stability terms. Fig. 2 shows a simulation of the divergence between the two trajectories of NAG on the objective function we construct, illustrating how the divergence fluctuates between positive and negative values, with its absolute value growing exponentially with time. More technical details on this construction can be found in Section 3.
From initialization stability to uniform stability: Finally, we employ a simple reduction to translate our results regarding initialization stability to relate to uniform stability in the context of empirical risk optimization, where one uses (full-batch) NAG to minimize the (convex, smooth) empirical risk induced by a sample ( of = examples. Concretely, we show that by replacing a single example in (, we can arrive at a scenario where after one step of NAG on the original and modified samples the respective iterates are ² = Θ(1/=) away from each other, whereas in the remaining steps both empirical risks simulate our bad function from before. Thus, we again end up with an exponential increase in the divergence between the two executions, that leads to a similar increase in the algorithmic (uniform) stability: the latter becomes as large as Ω(1) after merely ) = $ (log =) steps of full-batch NAG. The formal details of this reduction can be found in Section 4.

heading: 1.3 Discussion and Additional Related Work
text: It is 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 the (properly tuned) heavy ball method attains the accelerated $ (1/)2) convergence rate, for general convex and smooth functions it might even fail to converge at all (see 20). More specifically, it is known that there exists objectives for which heavy ball assumes a 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-order information, namely, in a setting where each gradient update is contaminated with a 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 a 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 a solution due to a perturbation near a 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 a few intriguing open problems for future investigation. Most importantly, it remains unclear whether there exists a different accelerated method (one with the optimal $ (1/)2) rate for smooth and convex objectives) that is also poly())-stable. Bubeck et al. [8] suggested a geometric alternative to NAG that comes to mind, and it could be interesting to check whether this method or a variant thereof is more stable than NAG. Another open question is to resolve the gap between our stability lower and upper bounds for NAG in the regime η 1/β: while our lower bounds have an exponential dependence on η, the upper bounds do not. Finally, it could be interesting to determine whether the $ ()²) 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).

heading: 2 Preliminaries
text: In this work we are interested in optimization of convex and smooth functions over the 3-dimensional Euclidean space ℝ3 . A function 5 is said to be β-smooth (for β > 0) if its gradient is β-Lipschitz, namely, if for all D, E ∈ ℝ3 it holds that ‖∇ 5 (D) − ∇ 5 (E)‖ ≤ β‖D − E‖.

heading: 2.1 Nesterov Accelerated Gradient Method
text: The Nesterov Accelerated Gradient (NAG) method [22] we consider in this paper takes the following form. Starting with G0 and H0 = G0, it iterates for C = 1, 2, . . .:
GC = HC−1 − η∇ 5 (HC−1); (1) HC = GC + γC (GC − GC−1), (2)
where γC = C−1C+2 and η > 0 is a step-size parameter.2 For a β-smooth convex objective 5 and 0 < η ≤ 1/β, this method exhibits the convergence rate$ (1/η)2); for η = 1/β, this gives the optimal convergence rate for the class of β-smooth 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( 5 , G0, C, η) to refer to the iterates (GC , HC ) at step C of NAG on 5 initialized at G0 with step size η. We sometimes drop the step size argument and use the shorter notation NAG( 5 , G0, C) when η 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 C > 0:
<C , γC (GC − GC−1). (3)
2For concreteness, we focus here on the most common choice of momentum parameters γC , but our results can be adapted to similar settings.
Using this notation, we have that GC = HC−1 − η∇ 5 (HC−1), (4) HC = GC + <C = HC−1 − η∇ 5 (HC−1) + <C , (5) <C = γC (<C−1 − η∇ 5 (HC−1)). (6)
Here, Eq. (6) follows from Eqs. (3) to (5) via <C = γC (GC − GC−1) (Eq. (3))
= γC (HC−1 − η∇ 5 (HC−1) − GC−1) (Eq. (4)) = γC (GC−1 + <C−1 − η∇ 5 (HC−1) − GC−1) (Eq. (5)) = γC (<C−1 − η∇ 5 (HC−1)).

heading: 2.2 Algorithmic Stability
text: We consider two forms of algorithmic stability. The first is the well-known uniform stability [6], while the second is initialization stability which we define here. Uniform stability. Consider the following general setting of supervised learning. There is a sample spaceZ of examples and an unknown distributionD overZ. We receive a training set ( = (I1, . . . , I=) of = samples drawn i.i.d. from D. The goal is finding a model F with a small population risk:
'(F) , EI∼D [`(F; I)], where `(F; I) is the loss of the model described by F on an example I. 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
'( (F) , 1 = =∑ 8=1 `(F; I8).
In this paper, our algorithm of interest in this context is full-batch NAG, namely, NAG applied to the empirical risk '( . We use the following notion of uniform stability.3 Definition 1 (uniform stability). Algorithm is ²-uniformly stable if for all (, (′ ∈ Z= such that (, (′ differ in at most one example, the corresponding outputs (() and ((′) satisfy
sup I∈Z |`( ((); I) − `( ((′); I) | ≤ ².
We use δunif ,` (=) to denote the infimum over all ² > 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 to a small perturbation in its initial point; formally, Definition 2 (initialization stability). Let be an algorithm that when initialized at a point G ∈ ℝ3 , produces (G) ∈ ℝ3 as output. Then for ² > 0, the initialization stability of at G0 ∈ ℝ3 is given as
δinitA (G0, ²) = sup{‖ (G̃0) − (G0)‖ : G̃0 ∈ ℝ 3 , ‖G̃0 − G0‖ ≤ ²}.

heading: 3 Initialization Stability of NAG
text: In this section we prove our first main result, regarding the initialization stability of NAG: Theorem 3. Let ², ,β > 0 and 0 < η ≤ 1/β. Consider two initialization points G0 = 0, G̃0 = ². Then, there exists a convex, β-smooth, -Lipschitz function 5 that attains a minimum over ℝ, and universal constants 21, 22 > 0, such that the sequences (GC , HC ) = NAG( 5 , G0, C, η) and (G̃C , H̃C ) = NAG( 5 , G̃0, C, η) satisfy
δinitNAGC (G0, ²) ≥ |GC − G̃C | ≥ min { 3β , 224 21ηβC² } , ∀ C ∈ { d 10 ηβ e (8 + 2) : 8 = 1, 2, . . . } .
Furthermore, for all C > d 10 ηβ e ( ln 3 2β² + 3 ) it holds that δinitNAGC (G0, ²) ≥ 3β .
3We give here a definition suitable for deterministic algorithms, which suffices for the context of this paper. Similar definitions exist for randomized algorithms; see for example [17, 13].
In words, the theorem establishes an exponential blowup in the distance between the two trajectories GC and G̃C during the initial $ (1/²) steps, after which the (lower bound on the) distance reaches a constant and stops increasing. Notice that in the blowup phase, an increase in distance happens roughly every ηβ steps; indeed, the actual behaviour of NAG on the function we construct exhibit fluctuations in the difference GC − G̃C , as illustrated in Fig. 2. We remark that a similar bound holds also for the HC sequence produced by NAG. Construction. Throughout this section, we will assume without loss of generality that 0 < ² < /2β. (When ² ≥ /2β our result holds simply for a constant function.) To lower bound the initialization stability and prove the theorem, we will rely on the following construction of functions 50, 51, . . . : ℝ → ℝ. Let the parameters ,β, η, ² > 0 be given, and for all 8 ≥ 0 define =8 , d10/ηβe (8 + 2). The construction proceeds as follows:
(i) Let 50 (G) , − G; (ii) For 8 ≥ 1:
• Let (G=8 , H=8 ) = NAG( 58−1, 0, =8 , η) and (G̃=8 , H̃=8 ) = NAG( 58−1, ², =8 , η); • Define 58 : ℝ→ ℝ as follows: 58 (G) , − G + β ∫ G −∞ ∫ H −∞ 1 [ ∃ 9 ≤ 8 s.t. I ∈ [Hmin= 9 , H max = 9 ] ] 3I3H,
where Hmin=8 = min{H=8 , H̃=8 }, H max =8 = max{H=8 , H̃=8 }; (iii) Let " = sup { 8 ≥ 0 : maxG ∇ 5 9 (G) < − 12 , ∀ 0 ≤ 9 ≤ 8 } .
Note that the above recursion defines an infinite sequence of functions 50, 51, 52, . . . : ℝ → ℝ. Ultimately, we will be interested in the functions { 58}8≤" which we will analyze in order to prove the instability result. Further, note that maxG ∇ 50 (G) < − 12 , thus " itself is well-defined, possibly∞. The functions constructed above are not lower-bounded (and thus do not admit a minimum). Below we define a lower-bounded adaptation of 5" (assuming 1 ≤ " < ∞, which is proved in Lemma 7 later on). Our modified version of 5" , termed 5 is defined by a quadratic continuation of 5" right of ? , Hmax=" , up to a plateau. This construction is defined formally as:
5 (G) ,  5" (G) G ≤ ?; 5" (?) + ∇ 5" (?) (G − ?) + β2 (G − ?) 2 ? < G ≤ ? − 1 β ∇ 5" (?); 5" (?) − 12β∇ 5" (?) 2 otherwise.
Analysis. We start by stating a few lemmas we will use in the proof of our main theorem. Our focus is on the functions 58 for 0 ≤ 8 ≤ " , deferring the analysis of 5 to after we establish that " is finite. First, we show that the functions we constructed are indeed convex, smooth and Lipschitz. Lemma 4. For all 0 ≤ 8 ≤ " , the function 58 is convex, β-smooth and -Lipschitz. Proof. The second derivative of 58 is
∇2 58 (G) = β · 1 [ ∃ 9 ≤ 8 s.t. I ∈ [Hmin= 9 , H max = 9 ] ] ∈ {0,β}.
Thus, 58 is convex and β-smooth. We lower bound the first derivative by ∇ 58 (G) = − + β ∫ G −∞ 1 [ ∃ 9 ≤ 8 s.t. I ∈ [Hmin= 9 , H max = 9 ] ] 3I ≥ − , and by the definition of " , ∇ 58 (G) < − /2. Hence for all G ∈ ℝ we have ∇ 58 (G) ∈ [− ,− /2), so 58 is -Lipschitz over ℝ.
Next, we analyze the iterations of NAG on 58 for any given 0 ≤ 8 ≤ " . Fix such index 8 and consider (GC , HC ) = NAG( 58 , 0, C) and (G̃C , H̃C ) = NAG( 58 , ², C) for all C ≤ ) for some ) ≥ =8+1. We introduce the following compact notation for differences between the NAG terms related to the two sequences:
∆GC , GC − G̃C , ∆ H C , HC − H̃C , ∆ 5 C , ∇ 58 (GC ) − ∇ 58 (G̃C ), ∆<C , <C − <̃C .
From the update rules of NAG (Eqs. (4) to (6)), we have that ∆GC = ∆ H C−1 − η∆ 5 C−1, (7)
∆ H C = ∆ G C + ∆<C = ∆ H C−1 − η∆ 5 C−1 + ∆ < C , (8)
∆<C = γC (∆<C−1 − η∆ 5 C−1). (9) Our next lemma below describes the evolution of the differences ∆ 5C and ∆<C in terms of ∆ H C .
Lemma 5. For all C ≤ ) ,
∆ 5 C =
{ β∆
H C if C ∈ {= 9 }89=1;
0 otherwise, and ∆<C =
{ γC (∆<C−1 − ηβ∆ H C−1) if C ∈ {= 9 + 1} 8 9=1;
γC∆ < C−1 otherwise.
The following lemma summarise the evolution of the distance between the sequences HC and H̃C at steps C ∈ {= 9 }1≤ 9≤8+1 and for C > =8+1. 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 ∆HC , we have the following:
(i) For all 1 ≤ 9 ≤ 8, it holds that 23ηβ|∆ H = 9 | ≤ |∆<= 9+1 | ≤ 1 5ηβ|∆ H = 9+1 |.
(ii) For all 0 ≤ 9 ≤ 8, it holds that |∆H= 9+1 | = Hmax= 9+1 − H min = 9+1 ≥ 3 9². (iii) For all C > =8+1, it holds that |∆HC | ≥ |∆ H =8+1 |.
Finally, we can show that 5 is well-defined by proving that " is finite in the following lemma. The bound of " also indicate that after $ (log 1
² ) steps the two trajectories HC , H̃C reach a constant distance.
Lemma 7. It holds that 1 ≤ " ≤ ln 3 2β² (in particular, " is finite), and H max ="+1 − H min ="+1 ≥ 3β .
Now we can return to our 5 . First, we show it indeed posses the basic properties for Theorem 3. Lemma8. The function 5 is convex,β-smooth, -Lipschitz and attains aminimum G★ ∈ arg minG 5 (G) s.t. |G0 − G★ | = $ ( ( /ηβ2) log( /β²)2 ) for G0 ∈ {0, ²}.
The final lemma we require shows that the distance between the two trajectories is the same for 5 and 5" . This holds true since the two functions coincide for G ≤ ?, after which the iterates reach a plateau which induces similar stability dynamics as the linear part of 5" at G > ?. Lemma 9. Let (GC , HC ) = NAG( 5 , 0, C, η) and (G̃C , H̃C ) = NAG( 5 , ², C, η) be the iterations of NAG on 5 from our initialization points. Similarly, for 5" , let (ĜC , ĤC ) = NAG( 5" , 0, C, η) and (ḠC , H̄C ) = NAG( 5" , ², C, η). Then for all C, we have that GC − G̃C = ĜC − ḠC and HC − H̃C = ĤC − H̄C .
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 3. Based on Lemma 9, it suffices to show that the lower bound holds for the function 5" . Let 21 = 111 ln(3), 22 = 4 5 3 −3. Let C = =8 for some 8 ≥ 1. The first case we will deal with is when 8 ≤ " + 1. We already established with Lemma 6 that |∆H=8 | ≥ 38−1². Since C = =8 = (8 + 2) d10/ηβe, 8 ≥ ηβC/11 − 2. Hence,
|∆H=8 | ≥ 3 ηβC/11−3² =⇒ |∆H=8 | ≥ 5 4 224 21ηβ) ².
To relate to |GC − G̃C |,
|GC − G̃C | = |∆G=8 | ≥ |∆H=8 | − |∆ < =8 | (Eq. (8))
≥ |∆H=8 | − |∆ < =8−1+1 | =8∏ C==8−1+2 γC (Lemma 5 for C = =8 , . . . , =8−1 + 2)
≥ |∆H=8 | − |∆ < =8−1+1 | (Since C ≥ 1⇒ 0 ≤ γC ≤ 1)
(∗) ≥ |∆H=8 | ( 1 − ηβ
5 ) ≥ 4
5 |∆H=8 | ≥ 224 21ηβ) ². (η ≤ 1 β )
Here, (∗) follows from Lemma 6 if 8 > 1 and the case of 8 = 1 follows by combining Lemma 5 and ∆<1 = 0 which implies that ∆ < =0+1 = 0. If C > ="+1 (includes the case of 8 > " + 1 and
C > d10/ηβe ( ln 3 2β² + 3 ) from Lemma 7), since C − 1 ≥ ="+1,
|GC − G̃C | = |∆HC−1 − η∆ 5 C−1 | (Eq. (7)) = |∆H
C−1 | (Lemma 5) ≥ |∆H="+1 |. (Lemma 6)
And using Lemma 7 we conclude that |GC − G̃C | ≥ 3β . Hence, with Lemma 4, 5" holds all properties of Theorem 3 beside attaining a minimum, and using Lemmas 8 and 9, 5 posses all the properties needed for Theorem 3.

heading: 4 Uniform Stability of NAG
text: In this section we present our second main result, regarding the uniform stability of (full-batch) NAG. This is given formally in the following theorem. Theorem 10. For any ,β, η and = ≥ 4 such that 0 < η ≤ 1/β, there exists a loss function `(F; I) that is convex, β-smooth and -Lipschitz in F (for every I ∈ Z) and universal constants 23, 24 > 0, such that the uniform stability of )-steps full-batch NAG with step size η is
δunifNAG) ,` (=) ≥ min { 2 3β , 244 23ηβ) βη 2 2 = } , ∀ ) ∈ { d 10 ηβ = =−3 e (8 + 2) : 8 = 1, 2, . . . } ,
Furthermore, for all ) ≥ d 40 ηβ e ( ln 6 β² + 3 ) it holds that δunifNAG) ,` (=) ≥ 2 3β .
The comments following Theorem 3 regarding the exponential blowup and the fluctuating behaviour also apply here. Note also the perhaps surprising inverse dependence on β (βη2 is also $ (1/β)). The dependence can be explained by the fact that smooth optimization over a highly non-smooth yet still -Lipschitz function must have a small step size (with η ≤ 1/β) which improves stability.
Construction. We denote the given parameters for the theorem with ̂, β̂, η̂, =. We will use the construction from Section 3 with the properties of Theorem 3 in order to create a loss function and samples which will have the same optimization for C ≥ 1. For the construction we define the following setting of ,β, η, ²:
= ̂, β = β̂, η = = − 3 = η̂, ² = βη2 = − 3 .
Using these parameters, we obtain 5 from the construction of Section 3. As we proved in the previous section, this is the function for which Theorem 3 holds. Note that for ) < =1, the lower bounds already holds even for quadratics, as we show in the full version of the paper [3]. We also define the following functions,
`(F; 1) , 0, (10) `(F; 2) , −βη F + β ∫ F −∞ ∫ H −∞ 1[I ∈ [0, η ]]3I3H, (11)
and further let `(F; 3) = − F, `(F; 4) = F, and `(F; 5) = 5 (F). Note that all are convex, β-smooth and -Lipschitz. Let Z = {1, 2, 3, 4, 5} be our sample space, we consider the loss function `(F; I) over ℝ × Z. Our samples of interest are ( = (1, 3, 4, 5, . . . , 5) ∈ Z= and (′ = (2, 3, 4, 5, . . . , 5) ∈ Z=. Thus, the empirical risks '( , '(′ corresponding to (, (′ are given by
'( (F) = 1 = 61 (F) + = − 3 = 5 (F) = = − 3 = 5 (F), (12)
'(′ (F) = 1 = 62 (F) + = − 3 = 5 (F). (13)
Analysis. The key lemma below shows that we constructed a scenario that reduces the problem of analyzing the uniform stability of full-batch NAG to analyzing its initialization stability on the function 5 we constructed in Section 3. Lemma 11. For all C = 1, 2, . . ., we have that
NAG( 5 , 0, C, η) = NAG('( , 0, C, η̂), NAG( 5 , ², C, η) = NAG('(′ , 0, C, η̂).
Using this key lemma, Theorem 10 follows immediately by setting 23 = 21/4 and 24 = 22/4, for the samples (, (′ we defined and I = 3. As `(F; 3) = − F,
|`(G) ; 3) − `(G̃) ; 3) | = |G) − G̃) |, and by using the definitions of ,β, η, ² we get the two cases of Theorem 3 which lower bound |G) − G̃) | 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.

Review summaries:
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.   The new concept --- uniform stability is a novel point.  

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.