# Non-convex Finite-Sum Optimization Via SCSG Methods

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

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2017.

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

- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Variance-reduced Clipping for Non-convex Optimization](https://mlsanity.com/paper/2303.00883/) (2023)
- [FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.04755/) (2021)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2110.01165/) (2021)
- [Stochastic Differentially Private and Fair Learning](https://mlsanity.com/paper/2210.08781/) (2022)
- [Variance Reduced Training with Stratified Sampling for Forecasting Models](https://mlsanity.com/paper/2103.02062/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Optimization with Access to Auxiliary Information](https://mlsanity.com/paper/2206.00395/) (2022)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [Knowledge Distillation Performs Partial Variance Reduction](https://mlsanity.com/paper/2305.17581/) (2023)
- [Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise](https://mlsanity.com/paper/2506.11214/) (2025)
- [Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling](https://mlsanity.com/paper/2206.02275/) (2022)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [The Minimax Complexity of Distributed Optimization](https://mlsanity.com/paper/2109.00534/) (2021)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [On the Convergence of Continual Learning with Adaptive Methods](https://mlsanity.com/paper/2404.05555/) (2024)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Stochastic Gradient Methods with Preconditioned Updates](https://mlsanity.com/paper/2206.00285/) (2022)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)

## Abstract (arXiv)

We develop a class of algorithms, as variants of the stochastically controlled stochastic gradient (SCSG) methods (Lei and Jordan, 2016), for the smooth non-convex finite-sum optimization problem. Assuming the smoothness of each component, the complexity of SCSG to reach a stationary point with mathbbE |nabla f(x)|2≤ ε is Oleft (minε-5/3, ε-1n2/3right), which strictly outperforms the stochastic gradient descent. Moreover, SCSG is never worse than the state-of-the-art methods based on variance reduction and it significantly outperforms them when the target accuracy is low. A similar acceleration is also achieved when the functions satisfy the Polyak-Lojasiewicz condition. Empirical experiments demonstrate that SCSG outperforms stochastic gradient methods on training multi-layers neural networks in terms of both training and validation loss.