mlsanityData to 7 Oct 2026

Algorithmic Instabilities of Accelerated Gradient Descent

arXiv 2102.02167 ↗First posted 3 Feb 2021cs.LG math.OC stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 16 of its 25 references that are in the map. First posted on arXiv 3 Feb 2021.

Builds on

16 of 25 references.

References · 16

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  2. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  3. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  4. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  5. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  6. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  7. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  8. 2019Sharper bounds for uniformly stable algorithmscited by 91
  9. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  10. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  11. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  12. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
4 more
  1. 2015A geometric alternative to Nesterov's accelerated gradient descentcited by 21
  2. 2017Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Proxcited by 12
  3. 2017Fast Rates for Empirical Risk Minimization of Strict Saddle Problemscited by 7
  4. 2020Stochastic Optimization with Laggard Data Pipelinescited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 1; 2024: 1; 2025: 1; 2026: 8.

16 papers.

Sort:

  1. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  2. 2022Reproducibility in Optimization: Theoretical Framework and Limitscited by 21
  3. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8
  4. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  5. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  6. 2026A Unified Lyapunov-IQC Framework for Uniform Stability of Smooth Quadratic First-Order Accelerated Optimizerscited by 1
  7. 2021Improved Learning Rates for Stochastic Optimizationcited by 0
  8. 2024On the stability of gradient descent with second order dynamics for time-varying cost functionscited by 0
  9. 2025Dynamically Weighted Momentum with Adaptive Step Sizes for Efficient Deep Network Trainingcited by 0
  10. 2026Momentum SVGD-EM for Accelerated Maximum Marginal Likelihood Estimationcited by 0
  11. 2026Stochastic Gradient Descent with Momentum is Algorithmically Stablecited by 0
  12. 2026Modeling Vehicle-Type-Specific Pedestrian Crash Avoidance Behavior in Safety-Critical Interactions Using Smooth-Mamba Deep Reinforcement Learningcited by 0
4 more
  1. 2026Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivitycited by 0
  2. 2026Dangerous Liaisons of Convex Learning and Non-Affine Aggregationcited by 0
  3. 2026Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustnesscited by 0
  4. 2026Generalization as a robust performance property of learning-enabled dynamical systemscited by 0