# Stochastic Reweighted Gradient Descent

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 59 references that are in the map.
- First posted on arXiv 23 Mar 2021.

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

- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [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)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Online Batch Selection for Faster Training of Neural Networks](https://mlsanity.com/paper/1511.06343/) (2015)
- [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Variance Reduction in SGD by Distributed Importance Sampling](https://mlsanity.com/paper/1511.06481/) (2015)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [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)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Importance Sampling for Minibatches](https://mlsanity.com/paper/1602.02283/) (2016)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (2015)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Safe Adaptive Importance Sampling](https://mlsanity.com/paper/1711.02637/) (2017)
- [Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization](https://mlsanity.com/paper/2006.10281/) (2020)
- [A Simple Practical Accelerated Method for Finite Sums](https://mlsanity.com/paper/1602.02442/) (2016)
- [A Lower Bound for the Optimization of Finite Sums](https://mlsanity.com/paper/1410.0723/) (2014)
- [Estimating Convergence of Markov chains with L-Lag Couplings](https://mlsanity.com/paper/1905.09971/) (2019)

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

- [Importance Tempering: Group Robustness for Overparameterized Models](https://mlsanity.com/paper/2209.08745/) (2022)
- [Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimization](https://mlsanity.com/paper/2306.09222/) (2023)
- [Changing the Training Data Distribution to Reduce Simplicity Bias Improves In-distribution Generalization](https://mlsanity.com/paper/2404.17768/) (2024)
- [DPRM: A Plug-in Doob h transform-induced Token-Ordering Module for Discrete Diffusion Models](https://mlsanity.com/paper/2604.24357/) (2026)
- [Online Importance Sampling for Stochastic Gradient Optimization](https://mlsanity.com/paper/2311.14468/) (2023)
- [Stochastic Gradient Descent with Strategic Querying](https://mlsanity.com/paper/2508.17144/) (2025)
- [Data-Efficient Training by Evolved Sampling](https://mlsanity.com/paper/2509.23461/) (2025)

## Abstract (arXiv)

Despite the strong theoretical guarantees that variance-reduced finite-sum optimization algorithms enjoy, their applicability remains limited to cases where the memory overhead they introduce (SAG/SAGA), or the periodic full gradient computation they require (SVRG/SARAH) are manageable. A promising approach to achieving variance reduction while avoiding these drawbacks is the use of importance sampling instead of control variates. While many such methods have been proposed in the literature, directly proving that they improve the convergence of the resulting optimization algorithm has remained elusive. In this work, we propose an importance-sampling-based algorithm we call SRG (stochastic reweighted gradient). We analyze the convergence of SRG in the strongly-convex case and show that, while it does not recover the linear rate of control variates methods, it provably outperforms SGD. We pay particular attention to the time and memory overhead of our proposed method, and design a specialized red-black tree allowing its efficient implementation. Finally, we present empirical results to support our findings.