mlsanityData to 7 Oct 2026

On the Convergence of SGD with Biased Gradients

arXiv 2008.00051 ↗First posted 31 Jul 2020cs.LG math.OC stat.MLcited by 79

Not on the map. Why?

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.

Key facts. Cited by 79 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 11; 2023: 19; 2024: 18; 2025: 8; 2026: 21.

79 papers.

Sort:

By area:

  1. 2022Fine-tuning Language Models over Slow Networks using Activation Compression with Guaranteescited by 29
  2. 2023GPT-FL: Generative Pre-trained Model-Assisted Federated Learningcited by 24
  3. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  4. 2022AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimationcited by 21
  5. 2024FIARSE: Model-Heterogeneous Federated Learning via Importance-Aware Submodel Extractioncited by 21
  6. 2024Verification of Machine Unlearning is Fragilecited by 20
  7. 2023The Behavior and Convergence of Local Bayesian Optimizationcited by 19
  8. 2024Softened Symbol Grounding for Neuro-symbolic Systemscited by 16
  9. 2021Masked Training of Neural Networks with Partial Gradientscited by 15
  10. 2023Federated Learning with Regularized Client Participationcited by 13
  11. 2022Optimization with Access to Auxiliary Informationcited by 12
  12. 2022When Do Curricula Work in Federated Learning?cited by 9
38 more
  1. 2021Linear Speedup in Personalized Collaborative Learningcited by 8
  2. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  3. 2022Error Mitigation-Aided Optimization of Parameterized Quantum Circuits: Convergence Analysiscited by 6
  4. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  5. 2023Entropy-MCMC: Sampling from Flat Basins with Easecited by 6
  6. 2023Improving Dual-Encoder Training through Dynamic Indexes for Negative Miningcited by 5
  7. 2023Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differencescited by 5
  8. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  9. 2024LoCo: Low-Bit Communication Adaptor for Large-scale Model Trainingcited by 5
  10. 2024On the Convergence of Continual Federated Learning Using Incrementally Aggregated Gradientscited by 5
  11. 2024Direct Quantized Training of Language Models with Stochastic Roundingcited by 5
  12. 2022Variational Inference with Locally Enhanced Bounds for Hierarchical Modelscited by 4
  13. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 4
  14. 2024Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oraclescited by 4
  15. 2025Discrete State Diffusion Models: A Sample Complexity Perspectivecited by 4
  16. 2026StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Modelscited by 4
  17. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  18. 2023Uncertainty-Aware Instance Reweighting for Off-Policy Learningcited by 3
  19. 2023Convergence Analysis of Stochastic Gradient Descent with MCMC Estimatorscited by 3
  20. 2023Fast Slate Policy Optimization: Going Beyond Plackett-Lucecited by 3
  21. 2023Domain Generalization without Excess Empirical Riskcited by 3
  22. 2023Enhancing Group Fairness in Online Settings Using Oblique Decision Forestscited by 3
  23. 2024Behind the Myth of Exploration in Policy Gradientscited by 3
  24. 2022Learning from time-dependent streaming data with online stochastic algorithmscited by 2
  25. 2023Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gapcited by 2
  26. 2023Controlling Federated Learning for Covertnesscited by 2
  27. 2024Parallel Momentum Methods Under Biased Gradient Estimationscited by 2
  28. 2024Regularization for Adversarial Robust Learningcited by 2
  29. 2022Fundamental Limits of Communication Efficiency for Model Aggregation in Distributed Learning: A Rate-Distortion Approachcited by 1
  30. 2022Adaptive Top-K in SGD for Communication-Efficient Distributed Learningcited by 1
  31. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 1
  32. 2024ε-Policy Gradient for Online Pricingcited by 1
  33. 2024Solving Hidden Monotone Variational Inequalities with Surrogate Lossescited by 1
  34. 2024Fed-ZOE: Communication-Efficient Over-the-Air Federated Learning via Zeroth-Order Estimationcited by 1
  35. 2025Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Ratescited by 1
  36. 2025Who to Trust? Aggregating Client Predictions in Federated Distillationcited by 1
  37. 2025Generative Modeling with Continuous Flows: Sample Complexity of Flow Matchingcited by 1
  38. 2026LatentFlow: A General Framework for Conditioning Stochastic Processescited by 1

50 most cited of 79 All 79 (JSON)