# On the Convergence of SGD with Biased Gradients

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

## Key facts

- Cited by 83 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2020.

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

- [Fine-tuning Language Models over Slow Networks using Activation Compression with Guarantees](https://mlsanity.com/paper/2206.01299/) (2022)
- [GPT-FL: Generative Pre-trained Model-Assisted Federated Learning](https://mlsanity.com/paper/2306.02210/) (2023)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation](https://mlsanity.com/paper/2204.13170/) (2022)
- [FIARSE: Model-Heterogeneous Federated Learning via Importance-Aware Submodel Extraction](https://mlsanity.com/paper/2407.19389/) (2024)
- [Verification of Machine Unlearning is Fragile](https://mlsanity.com/paper/2408.00929/) (2024)
- [The Behavior and Convergence of Local Bayesian Optimization](https://mlsanity.com/paper/2305.15572/) (2023)
- [Masked Training of Neural Networks with Partial Gradients](https://mlsanity.com/paper/2106.08895/) (2021)
- [Softened Symbol Grounding for Neuro-symbolic Systems](https://mlsanity.com/paper/2403.00323/) (2024)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Optimization with Access to Auxiliary Information](https://mlsanity.com/paper/2206.00395/) (2022)
- [Linear Speedup in Personalized Collaborative Learning](https://mlsanity.com/paper/2111.05968/) (2021)
- [When Do Curricula Work in Federated Learning?](https://mlsanity.com/paper/2212.12712/) (2022)
- [On Convergence of Incremental Gradient for Non-Convex Smooth Functions](https://mlsanity.com/paper/2305.19259/) (2023)
- [Error Mitigation-Aided Optimization of Parameterized Quantum Circuits: Convergence Analysis](https://mlsanity.com/paper/2209.11514/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Entropy-MCMC: Sampling from Flat Basins with Ease](https://mlsanity.com/paper/2310.05401/) (2023)
- [LoCo: Low-Bit Communication Adaptor for Large-scale Model Training](https://mlsanity.com/paper/2407.04480/) (2024)
- [Direct Quantized Training of Language Models with Stochastic Rounding](https://mlsanity.com/paper/2412.04787/) (2024)
- [Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining](https://mlsanity.com/paper/2303.15311/) (2023)
- [Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences](https://mlsanity.com/paper/2311.14127/) (2023)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers](https://mlsanity.com/paper/2402.02951/) (2024)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [On the Convergence of Continual Federated Learning Using Incrementally Aggregated Gradients](https://mlsanity.com/paper/2411.07959/) (2024)
- [Discrete State Diffusion Models: A Sample Complexity Perspective](https://mlsanity.com/paper/2510.10854/) (2025)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Variational Inference with Locally Enhanced Bounds for Hierarchical Models](https://mlsanity.com/paper/2203.04432/) (2022)
- [Scaling Automatic Research Agents via World Models](https://mlsanity.com/paper/2608.12564/) (2026)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)

## Abstract (arXiv)

We analyze the complexity of biased stochastic gradient methods (SGD), where individual updates are corrupted by deterministic, i.e. biased error terms. We derive convergence results for smooth (non-convex) functions and give improved rates under the Polyak-Lojasiewicz condition. We quantify how the magnitude of the bias impacts the attainable accuracy and the convergence rates (sometimes leading to divergence). Our framework covers many applications where either only biased gradient updates are available, or preferred, over unbiased ones for performance reasons. For instance, in the domain of distributed learning, biased gradient compression techniques such as top-k compression have been proposed as a tool to alleviate the communication bottleneck and in derivative-free optimization, only biased gradient estimators can be queried. We discuss a few guiding examples that show the broad applicability of our analysis.