# Variance Reduced Stochastic Gradient Descent with Neighbors

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

## Key facts

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

## Built on by (most cited first, 30 of 39)

- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Adaptive Second Order Coresets for Data-efficient Machine Learning](https://mlsanity.com/paper/2207.13887/) (2022)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [SHAQ: Incorporating Shapley Value Theory into Multi-Agent Q-Learning](https://mlsanity.com/paper/2105.15013/) (2021)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [MariusGNN: Resource-Efficient Out-of-Core Training of Graph Neural Networks](https://mlsanity.com/paper/2202.02365/) (2022)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Green, Quantized Federated Learning over Wireless Networks: An Energy-Efficient Design](https://mlsanity.com/paper/2207.09387/) (2022)
- [MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization](https://mlsanity.com/paper/2106.03056/) (2021)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions](https://mlsanity.com/paper/2310.02987/) (2023)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology](https://mlsanity.com/paper/2207.03730/) (2022)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Stochastic Optimization for Spectral Risk Measures](https://mlsanity.com/paper/2212.05149/) (2022)
- [Data-Efficient Training of CNNs and Transformers with Coresets: A Stability Perspective](https://mlsanity.com/paper/2303.02095/) (2023)
- [Stochastic Gradient Methods with Preconditioned Updates](https://mlsanity.com/paper/2206.00285/) (2022)
- [Distributed Methods with Absolute Compression and Error Compensation](https://mlsanity.com/paper/2203.02383/) (2022)
- [A Unified Theory of Stochastic Proximal Point Methods without Smoothness](https://mlsanity.com/paper/2405.15941/) (2024)
- [Randomized Stochastic Gradient Descent Ascent](https://mlsanity.com/paper/2111.13162/) (2021)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [Byzantine-Robust Loopless Stochastic Variance-Reduced Gradient](https://mlsanity.com/paper/2303.04560/) (2023)
- [AdaSelection: Accelerating Deep Learning Training through Data Subsampling](https://mlsanity.com/paper/2306.10728/) (2023)
- [Variance reduction techniques for stochastic proximal point algorithms](https://mlsanity.com/paper/2308.09310/) (2023)
- [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [GC-Fed: Gradient Centralized Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2503.13180/) (2025)

## 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.