# Accelerating Variance-Reduced Stochastic Gradient Methods

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2019.

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

- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024)
- [Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems](https://mlsanity.com/paper/2406.02413/) (2024)
- [Gradient Descent-Type Methods: Background and Simple Unified Convergence Analysis](https://mlsanity.com/paper/2212.09413/) (2022)
- [A New Framework for Variance-Reduced Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.04613/) (2021)
- [Stochastic Optimisation Framework using the Core Imaging Library and Synergistic Image Reconstruction Framework for PET Reconstruction](https://mlsanity.com/paper/2406.15159/) (2024)
- [Normalized Iterative Hard Thresholding for Tensor Recovery](https://mlsanity.com/paper/2507.04228/) (2025)
- [Stochastic Gradient Descent with Strategic Querying](https://mlsanity.com/paper/2508.17144/) (2025)
- [Stochastic Dimension Zeroth-Order Estimator: Stable and Memory-Efficient Training of PINNs](https://mlsanity.com/paper/2603.24002/) (2026)

## Abstract (arXiv)

Variance reduction is a crucial tool for improving the slow convergence of stochastic gradient descent. Only a few variance-reduced methods, however, have yet been shown to directly benefit from Nesterov's acceleration techniques to match the convergence rates of accelerated gradient methods. Such approaches rely on "negative momentum", a technique for further variance reduction that is generally specific to the SVRG gradient estimator. In this work, we show that negative momentum is unnecessary for acceleration and develop a universal acceleration framework that allows all popular variance-reduced methods to achieve accelerated convergence rates. The constants appearing in these rates, including their dependence on the number of functions n, scale with the mean-squared-error and bias of the gradient estimator. In a series of numerical experiments, we demonstrate that versions of SAGA, SVRG, SARAH, and SARGE using our framework significantly outperform non-accelerated versions and compare favourably with algorithms using negative momentum.