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

arXiv: https://arxiv.org/abs/1908.07861 · HTML: https://mlsanity.com/paper/1908.07861/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2019.

## Built on by (most cited first, 13 of 13)

- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Analyzing Human Models that Adapt Online](https://mlsanity.com/paper/2103.05746/) (2021)
- [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021)
- [Nesterov acceleration in benignly non-convex landscapes](https://mlsanity.com/paper/2410.08395/) (2024)
- [SHANG++: Robust Stochastic Acceleration under Multiplicative Noise](https://mlsanity.com/paper/2603.09355/) (2026)
- [NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer](https://mlsanity.com/paper/2209.14937/) (2022)
- [On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights](https://mlsanity.com/paper/2305.08658/) (2023)
- [A Variational Perspective on High-Resolution ODEs](https://mlsanity.com/paper/2311.02002/) (2023)
- [Mean-field underdamped Langevin dynamics and its spacetime discretization](https://mlsanity.com/paper/2312.16360/) (2023)
- [Accelerating Optimization via Differentiable Stopping Time](https://mlsanity.com/paper/2505.22509/) (2025)
- [Dynamic Low-rank Approximation of Full-Matrix Preconditioner for Training Generalized Linear Models](https://mlsanity.com/paper/2508.21106/) (2025)
- [On the Generalization of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2102.13653/) (2021)
- [Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural Networks](https://mlsanity.com/paper/2208.03941/) (2022)

## Abstract (arXiv)

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