# Stochastic Nested Variance Reduction for Nonconvex Optimization

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2018.

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

- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [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)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [On the Convergence of Muon and Beyond](https://mlsanity.com/paper/2509.15816/) (2025)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction](https://mlsanity.com/paper/2103.08280/) (2021)
- [Variance-reduced Clipping for Non-convex Optimization](https://mlsanity.com/paper/2303.00883/) (2023)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Random Scaling and Momentum for Non-smooth Non-convex Optimization](https://mlsanity.com/paper/2405.09742/) (2024)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [MuonEq: Balancing Before Orthogonalization with Lightweight Equilibration](https://mlsanity.com/paper/2603.28254/) (2026)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Better SGD using Second-order Momentum](https://mlsanity.com/paper/2103.03265/) (2021)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling](https://mlsanity.com/paper/2206.02275/) (2022)
- [Momentum Aggregation for Private Non-convex ERM](https://mlsanity.com/paper/2210.06328/) (2022)

## Abstract (arXiv)

We study finite-sum nonconvex optimization problems, where the objective function is an average of n nonconvex functions. We propose a new stochastic gradient descent algorithm based on nested variance reduction. Compared with conventional stochastic variance reduced gradient (SVRG) algorithm that uses two reference points to construct a semi-stochastic gradient with diminishing variance in each iteration, our algorithm uses K+1 nested reference points to build a semi-stochastic gradient to further reduce its variance in each iteration. For smooth nonconvex functions, the proposed algorithm converges to an ε-approximate first-order stationary point (i.e., |nabla F(x)|2≤ ε) within tilde O(nland ε-2+ε-3land n1/2ε-2) number of stochastic gradient evaluations. This improves the best known gradient complexity of SVRG O(n+n2/3ε-2) and that of SCSG O(nland ε-2+ε-10/3land n2/3ε-2). For gradient dominated functions, our algorithm also achieves better gradient complexity than the state-of-the-art algorithms. Thorough experimental results on different nonconvex optimization problems back up our theory.