# Momentum-Based Variance Reduction in Non-Convex SGD

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

## Key facts

- Cited by 306 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2019.

## Built on by (most cited first, 30 of 306)

- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [Flora: Low-Rank Adapters Are Secretly Gradient Compressors](https://mlsanity.com/paper/2402.03293/) (2024)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [A Novel Convergence Analysis for Algorithms of the Adam Family](https://mlsanity.com/paper/2112.03459/) (2021)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Faster Adaptive Federated Learning](https://mlsanity.com/paper/2212.00974/) (2022)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)

## Abstract (arXiv)

Variance reduction has emerged in recent years as a strong competitor to stochastic gradient descent in non-convex problems, providing the first algorithms to improve upon the converge rate of stochastic gradient descent for finding first-order critical points. However, variance reduction techniques typically require carefully tuned learning rates and willingness to use excessively large "mega-batches" in order to achieve their improved results. We present a new algorithm, STORM, that does not require any batches and makes use of adaptive learning rates, enabling simpler implementation and less hyperparameter tuning. Our technique for removing the batches uses a variant of momentum to achieve variance reduction in non-convex optimization. On smooth losses F, STORM finds a point boldsymbolx with mathbbE[|nabla F(boldsymbolx)|]≤ O(1/√T+σ1/3/T1/3) in T iterations with σ2 variance in the gradients, matching the optimal rate but without requiring knowledge of σ.