# Variance-Reduced Methods for Machine Learning

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

## Key facts

- Cited by 79 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2020.

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

- [LLaDA 1.5: Variance-Reduced Preference Optimization for Large Language Diffusion Models](https://mlsanity.com/paper/2505.19223/) (2025)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization](https://mlsanity.com/paper/2102.07245/) (2021)
- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization](https://mlsanity.com/paper/2110.08084/) (2021)
- [MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization](https://mlsanity.com/paper/2106.03056/) (2021)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization](https://mlsanity.com/paper/2210.13277/) (2022)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Linear Convergence of Black-Box Variational Inference: Should We Stick the Landing?](https://mlsanity.com/paper/2307.14642/) (2023)
- [Exact Gauss-Newton Optimization for Training Deep Neural Networks](https://mlsanity.com/paper/2405.14402/) (2024)
- [IntSGD: Adaptive Floatless Compression of Stochastic Gradients](https://mlsanity.com/paper/2102.08374/) (2021)
- [EF21 with Bells & Whistles: Six Algorithmic Extensions of Modern Error Feedback](https://mlsanity.com/paper/2110.03294/) (2021)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methods](https://mlsanity.com/paper/2402.11215/) (2024)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [A2CiD2: Accelerating Asynchronous Communication in Decentralized Deep Learning](https://mlsanity.com/paper/2306.08289/) (2023)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [Balancing Act: Constraining Disparate Impact in Sparse Models](https://mlsanity.com/paper/2310.20673/) (2023)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Dataset Distillation via Knowledge Distillation: Towards Efficient Self-Supervised Pre-Training of Deep Networks](https://mlsanity.com/paper/2410.02116/) (2024)
- [Efficient Optimization Algorithms for Linear Adversarial Training](https://mlsanity.com/paper/2410.12677/) (2024)
- [Balance is Essence: Accelerating Sparse Training via Adaptive Gradient Correction](https://mlsanity.com/paper/2301.03573/) (2023)

## Abstract (arXiv)

Stochastic optimization lies at the heart of machine learning, and its cornerstone is stochastic gradient descent (SGD), a method introduced over 60 years ago. The last 8 years have seen an exciting new development: variance reduction (VR) for stochastic optimization methods. These VR methods excel in settings where more than one pass through the training data is allowed, achieving a faster convergence than SGD in theory as well as practice. These speedups underline the surge of interest in VR methods and the fast-growing body of work on this topic. This review covers the key principles and main developments behind VR methods for optimization with finite data sets and is aimed at non-expert readers. We focus mainly on the convex setting, and leave pointers to readers interested in extensions for minimizing non-convex functions.