# SVRG Meets AdaGrad: Painless Variance Reduction

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 59 references that are in the map.
- First posted on arXiv 18 Feb 2021.

## Builds on (most cited first, 30 of 40)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Fluctuation-dissipation relations for stochastic gradient descent](https://mlsanity.com/paper/1810.00004/) (2018)
- [On the Ineffectiveness of Variance Reduced Optimization for Deep Learning](https://mlsanity.com/paper/1812.04529/) (2018)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation](https://mlsanity.com/paper/1910.04920/) (2019)
- [Adam^+: A Stochastic Method with Adaptive Variance Reduction](https://mlsanity.com/paper/2011.11985/) (2020)
- [The Implicit Bias of AdaGrad on Separable Data](https://mlsanity.com/paper/1906.03559/) (2019)

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

- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Divergence Results and Convergence of a Variance Reduced Version of ADAM](https://mlsanity.com/paper/2210.05607/) (2022)
- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [An Adaptive Incremental Gradient Method With Support for Non-Euclidean Norms](https://mlsanity.com/paper/2205.02273/) (2022)
- [Adaptive Step-Size Methods for Compressed SGD](https://mlsanity.com/paper/2207.10046/) (2022)
- [Efficient Continual Finite-Sum Minimization](https://mlsanity.com/paper/2406.04731/) (2024)
- [Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Study](https://mlsanity.com/paper/2505.11752/) (2025)
- [SVRG and Beyond via Posterior Correction](https://mlsanity.com/paper/2512.01930/) (2025)
- [Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size](https://mlsanity.com/paper/2608.12009/) (2026)

## Abstract (arXiv)

Variance reduction (VR) methods for finite-sum minimization typically require the knowledge of problem-dependent constants that are often unknown and difficult to estimate. To address this, we use ideas from adaptive gradient methods to propose AdaSVRG, which is a more robust variant of SVRG, a common VR method. AdaSVRG uses AdaGrad in the inner loop of SVRG, making it robust to the choice of step-size. When minimizing a sum of n smooth convex functions, we prove that a variant of AdaSVRG requires tildeO(n + 1/ε) gradient evaluations to achieve an O(ε)-suboptimality, matching the typical rate, but without needing to know problem-dependent constants. Next, we leverage the properties of AdaGrad to propose a heuristic that adaptively determines the length of each inner-loop in AdaSVRG. Via experiments on synthetic and real-world datasets, we validate the robustness and effectiveness of AdaSVRG, demonstrating its superior performance over standard and other "tune-free" VR methods.