# A Guide Through the Zoo of Biased SGD

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 77 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Deep Learning with Limited Numerical Precision](https://mlsanity.com/paper/1502.02551/) (2015)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression](https://mlsanity.com/paper/1905.05957/) (2019)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [Scaling Distributed Machine Learning with In-Network Aggregation](https://mlsanity.com/paper/1903.06701/) (2019)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions](https://mlsanity.com/paper/1902.00908/) (2019)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning](https://mlsanity.com/paper/1911.08250/) (2019)
- [Quantized Adam with Error Feedback](https://mlsanity.com/paper/2004.14180/) (2020)
- [3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation](https://mlsanity.com/paper/2202.00998/) (2022)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)

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

- [Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs)](https://mlsanity.com/paper/2505.13416/) (2025)
- [Functional Bilevel Optimization for Machine Learning](https://mlsanity.com/paper/2403.20233/) (2024)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [Bayesian Experimental Design via Contrastive Diffusions](https://mlsanity.com/paper/2410.11826/) (2024)
- [Towards Exact Gradient-based Training on Analog In-memory Computing](https://mlsanity.com/paper/2406.12774/) (2024)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [Poor Man's Training on MCUs: A Memory-Efficient Quantized Back-Propagation-Free Approach](https://mlsanity.com/paper/2411.05873/) (2024)
- [Improving the Straight-Through Estimator with Zeroth-Order Information](https://mlsanity.com/paper/2510.23926/) (2025)
- [A Unified Theory of Stochastic Proximal Point Methods without Smoothness](https://mlsanity.com/paper/2405.15941/) (2024)
- [Error Feedback under (L0,L1)-Smoothness: Normalization and Momentum](https://mlsanity.com/paper/2410.16871/) (2024)
- [Correlated Quantization for Faster Nonconvex Distributed Optimization](https://mlsanity.com/paper/2401.05518/) (2024)
- [Automatic AI Model Selection for Wireless Systems: Online Learning via Digital Twinning](https://mlsanity.com/paper/2406.15819/) (2024)
- [On the Convergence of FedProx with Extrapolation and Inexact Prox](https://mlsanity.com/paper/2410.01410/) (2024)
- [Learning Latent Variable Models via Jarzynski-adjusted Langevin Algorithm](https://mlsanity.com/paper/2505.18427/) (2025)
- [Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization](https://mlsanity.com/paper/2506.06606/) (2025)
- [Communication-Efficient Gluon in Federated Learning](https://mlsanity.com/paper/2604.10689/) (2026)
- [Parallel Momentum Methods Under Biased Gradient Estimations](https://mlsanity.com/paper/2403.00853/) (2024)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Bilevel Learning with Inexact Stochastic Gradients](https://mlsanity.com/paper/2412.12049/) (2024)
- [Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis](https://mlsanity.com/paper/2505.17965/) (2025)
- [Layer-Parallel Training for Transformers](https://mlsanity.com/paper/2601.09026/) (2026)
- [MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2412.17082/) (2024)
- [Analysis of On-policy Policy Gradient Methods under the Distribution Mismatch](https://mlsanity.com/paper/2503.22244/) (2025)
- [Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds](https://mlsanity.com/paper/2509.13628/) (2025)
- [Efficient Stochastic Optimisation via Sequential Monte Carlo](https://mlsanity.com/paper/2601.22003/) (2026)
- [Tracking the Median of Gradients with a Stochastic Proximal Point Method](https://mlsanity.com/paper/2402.12828/) (2024)
- [Graph Convolutional Network For Semi-supervised Node Classification With Subgraph Sketching](https://mlsanity.com/paper/2404.12724/) (2024)
- [Derivatives of Stochastic Gradient Descent in parametric optimization](https://mlsanity.com/paper/2405.15894/) (2024)
- [Stochastic Gradient Descent Revisited](https://mlsanity.com/paper/2412.06070/) (2024)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) is arguably the most important single algorithm in modern machine learning. Although SGD with unbiased gradient estimators has been studied extensively over at least half a century, SGD variants relying on biased estimators are rare. Nevertheless, there has been an increased interest in this topic in recent years. However, existing literature on SGD with biased estimators (BiasedSGD) lacks coherence since each new paper relies on a different set of assumptions, without any clear understanding of how they are connected, which may lead to confusion. We address this gap by establishing connections among the existing assumptions, and presenting a comprehensive map of the underlying relationships. Additionally, we introduce a new set of assumptions that is provably weaker than all previous assumptions, and use it to present a thorough analysis of BiasedSGD in both convex and non-convex settings, offering advantages over previous results. We also provide examples where biased estimators outperform their unbiased counterparts or where unbiased versions are simply not available. Finally, we demonstrate the effectiveness of our framework through experimental results that validate our theoretical findings.