Research map / Optimization / Nonconvex and smooth optimization
Nesterov acceleration despite very noisy gradients
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes AGNES, a two-parameter-step generalization of Nesterov's accelerated gradient that retains O(1/n^2) convergence (convex) and linear acceleration (strongly convex) under multiplicative gradient noise of any size, with experiments on synthetic functions, MLP regression, and CIFAR-10 CNNs.
Problem
Accelerated gradient methods lose their acceleration guarantees, and can diverge, when stochastic gradient estimates have noise comparable to or larger than the gradient, as occurs in overparametrized learning where noise scales with gradient magnitude.
Approach
Decouple Nesterov's single learning rate into two parameters: a gradient step size eta and a separate momentum-lookahead step size alpha (with alpha chosen smaller than eta, scaled by 1+sigma^2), so acceleration holds for any multiplicative noise level sigma.
Key results
- AGNES with default parameters (alpha=1e-3, eta=1e-2, rho=0.99) reliably outperforms SGD and NAG in training loss and test accuracy on ResNet-34/ResNet-50 CIFAR-10 experiments, per the paper's claims.
- Theory: AGNES attains O(1/n^2) rate in the convex case and linear rate (1 - sqrt(mu*eta/(1+sigma^2)))^n in the strongly convex case for any noise intensity sigma, whereas NAG's analysis requires sigma < 1.
- In a convex 1D experiment with sigma=50, NAG diverges while AGNES, CNM and ACDM converge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AGNES instead of SGD with momentum | Neural network regression · Training and test sets, batch sizes 100, 50, and 10 | MSE loss | Helped |
| Use AGNES instead of NAG | Neural network regression · Training and test sets, batch sizes 100, 50, and 10 | MSE loss | Helped |
| Use AGNES instead of SGD with momentum | CIFAR-10 image classification · ResNet-34 and ResNet-50; batch sizes 10 and 50 | test accuracy | Helped |
| Use AGNES instead of NAG | CIFAR-10 image classification · ResNet-34 and ResNet-50; batch sizes 10 and 50 | test accuracy | Helped |
| Use AGNES instead of NAG | Convex synthetic optimization · f_d, dimensions d=4 and d=16, noise σ=10 and 50 | objective value | Mixed |
| Use AGNES instead of SGD | Strongly convex quadratic optimization · f_{μ,L}, μ=1, L=500 and L=10^4; multiple noise levels | objective value | Helped |
| Use a separate correction step size η rather than tying it to α | AGNES · CIFAR-10, ResNet-34, batch size 50 | test accuracy | Helped |
| Change α while holding η values fixed (ablation) | AGNES on LeNet-5 · MNIST, batch size 60, six epochs | training loss | Mixed |
| Increase η among the tested values while holding α fixed (ablation) | AGNES on LeNet-5 · MNIST, batch size 60, six epochs | training loss | Helped |
| Use a smaller α with the other AGNES hyperparameters unchanged (ablation) | AGNES on ResNet-34 · CIFAR-10, batch size 50, 40 epochs | training loss | No clear effect |
Surprising findings
- NAG diverges for large multiplicative noise even though gradient descent with a small step size still converges.
- The primary learning rate is alpha (the momentum-lookahead step), while eta can be orders of magnitude larger, which is the reverse of the intuition that the gradient step size dominates.
Limitations
- Multiplicative noise assumption is motivated for global minimizers in overparametrized settings but not at generic critical points.
- Experiments are limited; the authors acknowledge they did not test theory across a broad set of benchmarks.
- Requires tuning of three hyperparameters in the strongly convex case, versus one for SGD.
Experimental setup
Datasets: CIFAR-10 MNIST synthetic regression dataset (100,000 12-dimensional random vectors labeled by a random MLP)
Benchmarks: CIFAR-10 MNIST synthetic convex 1D functions f_d synthetic neural network regression
Metrics: training loss test accuracy test loss expected objective value
Baselines: SGD SGD with momentum NAG Adam ACDM CNM MaSS
Builds on: Nesterov accelerated gradient descent MaSS accelerated coordinate descent with multiplicative noise continuized Nesterov method
Closest papers by meaning
- Nesterov acceleration in benignly non-convex landscapes (ICLR 2025 · similarity 0.92)
- On Acceleration with Noise-Corrupted Gradients (ICML 2018 · similarity 0.90)
- On the Convergence of Nesterov’s Accelerated Gradient Method in Stochastic Settings (ICML 2020 · similarity 0.90)
- Gradient correlation is a key ingredient to accelerate SGD with momentum (ICLR 2025 · similarity 0.88)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.88)
- EMA-Nesterov: Stabilizing Nesterov's Lookahead for Accelerated Deep Learning Optimization (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.