Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent

Abstract

We present a coupled system of ODEs which, when discretized with a constant time step/learning rate, recovers Nesterov's accelerated gradient descent algorithm. The same ODEs, when discretized with a decreasing learning rate, leads to novel stochastic gradient descent (SGD) algorithms, one in the convex and a second in the strongly convex case. In the strongly convex case, we obtain an algorithm superficially similar to momentum SGD, but with additional terms. In the convex case, we obtain an algorithm with a novel order $k^{3/4}$ learning rate. We prove, extending the Lyapunov function approach from the full gradient case to the stochastic case, that the algorithms converge at the optimal rate for the last iterate of SGD, with rate constants which are better than previously available.

arXiv comment23 pages, 1 table, (minor revision), accepted to AISTATS 2020

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• A Lyapunov Analysis of Momentum Methods in Optimization
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• From Averaging to Acceleration, There is Only a Step-size
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings
• Stochastic Gradient Descent with Polyak's Learning Rate

Cited by in corpus (4)

• The long time behavior and the rate of convergence of symplectic convex algorithms obtained via splitting discretizations of inertial damping systems
• Accelerated differential inclusion for convex optimization
• Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum