# On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2020.

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

- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Learning from Future: A Novel Self-Training Framework for Semantic Segmentation](https://mlsanity.com/paper/2209.06993/) (2022)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization](https://mlsanity.com/paper/2110.09057/) (2021)
- [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization](https://mlsanity.com/paper/2102.11537/) (2021)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [Hierarchical Federated Learning with Momentum Acceleration in Multi-Tier Networks](https://mlsanity.com/paper/2210.14560/) (2022)
- [Memory Augmented Optimizers for Deep Learning](https://mlsanity.com/paper/2106.10708/) (2021)
- [PnP-CM: Consistency Models as Plug-and-Play Priors for Inverse Problems](https://mlsanity.com/paper/2509.22736/) (2025)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [SHANG++: Robust Stochastic Acceleration under Multiplicative Noise](https://mlsanity.com/paper/2603.09355/) (2026)
- [Gradient Temporal Difference with Momentum: Stability and Convergence](https://mlsanity.com/paper/2111.11004/) (2021)
- [EMO: Episodic Memory Optimization for Few-Shot Meta-Learning](https://mlsanity.com/paper/2306.05189/) (2023)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [On the Generalization of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2102.13653/) (2021)
- [Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs](https://mlsanity.com/paper/2106.08775/) (2021)
- [Does Momentum Help? A Sample Complexity Analysis](https://mlsanity.com/paper/2110.15547/) (2021)
- [Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results](https://mlsanity.com/paper/2209.05372/) (2022)
- [A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques](https://mlsanity.com/paper/2403.11163/) (2024)
- [Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation](https://mlsanity.com/paper/2404.02378/) (2024)
- [Adaptive Gradient Regularization: A Faster and Generalizable Optimization Technique for Deep Neural Networks](https://mlsanity.com/paper/2407.16944/) (2024)
- [Convex Distillation: Efficient Compression of Deep Networks via Convex Optimization](https://mlsanity.com/paper/2410.06567/) (2024)
- [A Concise Lyapunov Analysis of Nesterov's Accelerated Gradient Method](https://mlsanity.com/paper/2502.17373/) (2025)
- [Why Federated Optimization Fails to Achieve Perfect Fitting? A Theoretical Perspective on Client-Side Optima](https://mlsanity.com/paper/2511.00469/) (2025)

## Abstract (arXiv)

We study Nesterov's accelerated gradient method with constant step-size and momentum parameters in the stochastic approximation setting (unbiased gradients with bounded variance) and the finite-sum setting (where randomness is due to sampling mini-batches). To build better insight into the behavior of Nesterov's method in stochastic settings, we focus throughout on objectives that are smooth, strongly-convex, and twice continuously differentiable. In the stochastic approximation setting, Nesterov's method converges to a neighborhood of the optimal point at the same accelerated rate as in the deterministic setting. Perhaps surprisingly, in the finite-sum setting, we prove that Nesterov's method may diverge with the usual choice of step-size and momentum, unless additional conditions on the problem related to conditioning and data coherence are satisfied. Our results shed light as to why Nesterov's method may fail to converge or achieve acceleration in the finite-sum setting.