mlsanityData to 7 Oct 2026

Stochastic Reweighted Gradient Descent

arXiv 2103.12293 ↗First posted 23 Mar 2021math.OC cs.LG stat.MLcited by 7

Not on the map. Why?

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.

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

Builds on

37 of 59 references.

References · 37

  1. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  2. 2015Prioritized Experience Replaycited by 1,070
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  4. 2018Not All Samples Are Created Equal: Deep Learning with Importance Samplingcited by 323
  5. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  6. 2019SGD: General Analysis and Improved Ratescited by 206
  7. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  8. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  9. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  10. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  11. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  12. 2015Online Batch Selection for Faster Training of Neural Networkscited by 121
25 more
  1. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  2. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  3. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 94
  4. 2014Stochastic Optimization with Importance Samplingcited by 91
  5. 2015Variance Reduction in SGD by Distributed Importance Samplingcited by 79
  6. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  7. 2018On the Ineffectiveness of Variance Reduced Optimization for Deep Learningcited by 48
  8. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  9. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  10. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  11. 2016Importance Sampling for Minibatchescited by 36
  12. 2015An optimal randomized incremental gradient methodcited by 32
  13. 2019A unified variance-reduced accelerated gradient method for convex optimizationcited by 23
  14. 2017Safe Adaptive Importance Samplingcited by 19
  15. 2016A Simple Practical Accelerated Method for Finite Sumscited by 18
  16. 2020Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimizationcited by 18
  17. 2014A Lower Bound for the Optimization of Finite Sumscited by 13
  18. 2019Estimating Convergence of Markov chains with L-Lag Couplingscited by 13
  19. 2020On Convergence-Diagnostic based Step Sizes for Stochastic Gradient Descentcited by 11
  20. 2018Online Variance Reduction for Stochastic Optimizationcited by 10
  21. 2015Online Learning to Samplecited by 9
  22. 2017Stochastic Optimization with Bandit Samplingcited by 8
  23. 2019Online Variance Reduction with Mixturescited by 7
  24. 2015Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fieldscited by 6
  25. 2017Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimizationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 1; 2025: 2; 2026: 1.

7 papers.

  1. 2022Importance Tempering: Group Robustness for Overparameterized Modelscited by 6
  2. 2023Stochastic Re-weighted Gradient Descent via Distributionally Robust Optimizationcited by 6
  3. 2024Changing the Training Data Distribution to Reduce Simplicity Bias Improves In-distribution Generalizationcited by 3
  4. 2023Online Importance Sampling for Stochastic Gradient Optimizationcited by 1
  5. 2026DPRM: A Plug-in Doob h transform-induced Token-Ordering Module for Discrete Diffusion Modelscited by 1
  6. 2025Stochastic Gradient Descent with Strategic Queryingcited by 0
  7. 2025Data-Efficient Training by Evolved Samplingcited by 0