mlsanityData to 14 Oct 2026

Variance Reduced Stochastic Gradient Descent with Neighbors

arXiv 1506.03662 ↗First posted 11 Jun 2015cs.LG math.OC stat.MLcited by 39

Not on the map. Why?

Abstract (arXiv)

Stochastic Gradient Descent (SGD) is a workhorse in machine learning, yet its slow convergence can be a computational bottleneck. Variance reduction techniques such as SAG, SVRG and SAGA have been proposed to overcome this weakness, achieving linear convergence. However, these methods are either based on computations of full gradients at pivot points, or on keeping per data point corrections in memory. Therefore speed-ups relative to SGD may need a minimal number of epochs in order to materialize. This paper investigates algorithms that can exploit neighborhood structure in the training data to share and re-use information about past stochastic gradients across data points, which offers advantages in the transient optimization phase. As a side-product we provide a unified convergence analysis for a family of variance reduction algorithms, which we call memorization algorithms. We provide experimental results supporting our theory.

Key facts. Cited by 39 papers in the map (data through 14 Oct 2026). First posted on arXiv 11 Jun 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 14; 2023: 7; 2024: 5; 2025: 1; 2026: 1.

39 papers.

Sort:

  1. 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learningcited by 64
  2. 2022Adaptive Second Order Coresets for Data-efficient Machine Learningcited by 60
  3. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 47
  4. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  5. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  6. 2021SHAQ: Incorporating Shapley Value Theory into Multi-Agent Q-Learningcited by 26
  7. 2022Can 5th Generation Local Training Methods Support Client Sampling? Yes!cited by 22
  8. 2021Stochastic Polyak Stepsize with a Moving Targetcited by 19
  9. 2022MariusGNN: Resource-Efficient Out-of-Core Training of Graph Neural Networkscited by 19
  10. 2021Distributed Learning Systems with First-order Methodscited by 17
  11. 2022Green, Quantized Federated Learning over Wireless Networks: An Energy-Efficient Designcited by 15
  12. 2021MURANA: A Generic Framework for Stochastic Variance-Reduced Optimizationcited by 14
27 more
  1. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
  2. 2023Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusionscited by 11
  3. 2021Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizescited by 10
  4. 2022Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topologycited by 10
  5. 2021Stochastic Reweighted Gradient Descentcited by 7
  6. 2022Stochastic Optimization for Spectral Risk Measurescited by 7
  7. 2023Data-Efficient Training of CNNs and Transformers with Coresets: A Stability Perspectivecited by 6
  8. 2022Stochastic Gradient Methods with Preconditioned Updatescited by 5
  9. 2022Distributed Methods with Absolute Compression and Error Compensationcited by 4
  10. 2024A Unified Theory of Stochastic Proximal Point Methods without Smoothnesscited by 4
  11. 2021Randomized Stochastic Gradient Descent Ascentcited by 3
  12. 2022Decentralized Stochastic Variance Reduced Extragradient Methodcited by 3
  13. 2023Byzantine-Robust Loopless Stochastic Variance-Reduced Gradientcited by 3
  14. 2023AdaSelection: Accelerating Deep Learning Training through Data Subsamplingcited by 3
  15. 2023Variance reduction techniques for stochastic proximal point algorithmscited by 3
  16. 2024Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradientscited by 3
  17. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 2
  18. 2025GC-Fed: Gradient Centralized Federated Learning with Partial Client Participationcited by 2
  19. 2026JacQuant: STE-Free Quantization-Aware Training via Learned Jacobian Surrogatescited by 2
  20. 2021Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programmingcited by 1
  21. 2022Statistical and Computational Guarantees for Influence Diagnosticscited by 1
  22. 2024Analysis of regularized federated learningcited by 1
  23. 2021Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimizationcited by 0
  24. 2022BALPA: A Balanced Primal-Dual Algorithm for Nonsmooth Optimization with Application to Distributed Optimizationcited by 0
  25. 2023Unified analysis of SGD-type methodscited by 0
  26. 2023Ordering for Non-Replacement SGDcited by 0
  27. 2024SOREL: A Stochastic Algorithm for Spectral Risks Minimizationcited by 0