# Variance Reduction for Faster Non-Convex Optimization

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

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2016.

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

- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [Variance-reduced Clipping for Non-convex Optimization](https://mlsanity.com/paper/2303.00883/) (2023)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Optimizing Large-Scale Hyperparameters via Automated Learning Algorithm](https://mlsanity.com/paper/2102.09026/) (2021)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2211.13668/) (2022)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [DiSK: Differentially Private Optimizer with Simplified Kalman Filter for Noise Reduction](https://mlsanity.com/paper/2410.03883/) (2024)
- [Efficient Semi-Implicit Variational Inference](https://mlsanity.com/paper/2101.06070/) (2021)
- [IntSGD: Adaptive Floatless Compression of Stochastic Gradients](https://mlsanity.com/paper/2102.08374/) (2021)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [DOPPLER: Differentially Private Optimizers with Low-pass Filter for Privacy Noise Reduction](https://mlsanity.com/paper/2408.13460/) (2024)
- [Stochastic Gradient Langevin Dynamics with Variance Reduction](https://mlsanity.com/paper/2102.06759/) (2021)
- [Stochastic Anderson Mixing for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2110.01543/) (2021)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [Federated Learning for Diffusion Models](https://mlsanity.com/paper/2503.06426/) (2025)
- [Smoothed functional-based gradient algorithms for off-policy reinforcement learning: A non-asymptotic viewpoint](https://mlsanity.com/paper/2101.02137/) (2021)

## Abstract (arXiv)

We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in O(1/varepsilon) iterations for smooth objectives, and stochastic gradient descent that converges in O(1/varepsilon2) iterations for objectives that are sum of smooth functions. We provide the first improvement in this line of research. Our result is based on the variance reduction trick recently introduced to convex optimization, as well as a brand new analysis of variance reduction that is suitable for non-convex optimization. For objectives that are sum of smooth functions, our first-order minibatch stochastic method converges with an O(1/varepsilon) rate, and is faster than full gradient descent by Omega(n1/3). We demonstrate the effectiveness of our methods on empirical risk minimizations with non-convex loss functions and training neural nets.