# Nesterov acceleration despite very noisy gradients

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

## Key facts

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

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

- [Nesterov acceleration in benignly non-convex landscapes](https://mlsanity.com/paper/2410.08395/) (2024)
- [Accelerated Distributed Optimization with Compression and Error Feedback](https://mlsanity.com/paper/2503.08427/) (2025)
- [A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces](https://mlsanity.com/paper/2310.17610/) (2023)
- [SHANG++: Robust Stochastic Acceleration under Multiplicative Noise](https://mlsanity.com/paper/2603.09355/) (2026)
- [Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods](https://mlsanity.com/paper/2606.19179/) (2026)
- [Adam-SHANG: A Convergent Adam-Type Method for Stochastic Smooth Convex Optimization](https://mlsanity.com/paper/2605.12878/) (2026)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)

## Abstract (arXiv)

We present a generalization of Nesterov's accelerated gradient descent algorithm. Our algorithm (AGNES) provably achieves acceleration for smooth convex and strongly convex minimization tasks with noisy gradient estimates if the noise intensity is proportional to the magnitude of the gradient at every point. Nesterov's method converges at an accelerated rate if the constant of proportionality is below 1, while AGNES accommodates any signal-to-noise ratio. The noise model is motivated by applications in overparametrized machine learning. AGNES requires only two parameters in convex and three in strongly convex minimization tasks, improving on existing methods. We further provide clear geometric interpretations and heuristics for the choice of parameters.