Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: 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.
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.

Despite these praises, I have some minor concerns that may, or not, be addressed in a rebuttal.
- 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.
- 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.
- 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?
- 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.

Note: 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.
limitations_and_societal_impact: Y.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

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

Su et al. (2016)  A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
                             Journal of Machine Learning Research, 17(153), 1–43, 2016.

Shi et al. (2021) Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
                             Mathematical Programming, Series A,  https://doi.org/10.1007/s10107-021-01681-8

this paper will become more attractive. 

If the author do more effort and deeper investigation, I would like to improve the my review result. 
limitations_and_societal_impact: The content  for the new concept uniform stability and comparison with initialization stability is not enough.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

2. The authors proved the uniform instability of full batch NAG. Many technical lemmas are proved.


Weakness: This paper needs many efforts to improve.

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

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

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

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 

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

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


Minor comments: 
- 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? 
- l.204: Did the authors mean O(log 1/\varespilon) ?
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_title: null

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)