# Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2016.

## Built on by (most cited first, 18 of 18)

- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [APHQ-ViT: Post-Training Quantization with Average Perturbation Hessian Based Reconstruction for Vision Transformers](https://mlsanity.com/paper/2504.02508/) (2025)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method](https://mlsanity.com/paper/2103.11333/) (2021)
- [Provably Robust Federated Reinforcement Learning](https://mlsanity.com/paper/2502.08123/) (2025)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Sampling Through the Lens of Sequential Decision Making](https://mlsanity.com/paper/2208.08056/) (2022)
- [Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences](https://mlsanity.com/paper/2512.13123/) (2025)
- [A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization](https://mlsanity.com/paper/2102.09893/) (2021)
- [Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems](https://mlsanity.com/paper/2401.15890/) (2024)
- [Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks](https://mlsanity.com/paper/2112.10389/) (2021)
- [SADAM: Stochastic Adam, A Stochastic Operator for First-Order Gradient-based Optimizer](https://mlsanity.com/paper/2205.10247/) (2022)
- [Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds](https://mlsanity.com/paper/2610.03165/) (2026)
- [Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods](https://mlsanity.com/paper/2103.04413/) (2021)
- [Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization](https://mlsanity.com/paper/2407.16968/) (2024)
- [Convergence Analysis of alpha-SVRG under Strong Convexity](https://mlsanity.com/paper/2503.12454/) (2025)
- [Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Study](https://mlsanity.com/paper/2505.11752/) (2025)

## Abstract (arXiv)

We develop and analyze a procedure for gradient-based optimization that we refer to as stochastically controlled stochastic gradient (SCSG). As a member of the SVRG family of algorithms, SCSG makes use of gradient estimates at two scales, with the number of updates at the faster scale being governed by a geometric random variable. Unlike most existing algorithms in this family, both the computation cost and the communication cost of SCSG do not necessarily scale linearly with the sample size n; indeed, these costs are independent of n when the target accuracy is low. An experimental evaluation on real datasets confirms the effectiveness of SCSG.