Algorithmic Instabilities of Accelerated Gradient Descent

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.

arXiv comment37 pages

References in corpus (7)

• A geometric alternative to Nesterov's accelerated gradient descent
• Private Stochastic Convex Optimization with Optimal Rates
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Generalization Bounds for Uniformly Stable Algorithms
• Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back