mlsanityData to 7 Oct 2026

Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD

arXiv 1803.01113 ↗First posted 3 Mar 2018stat.ML cs.LGcited by 68

Not on the map. Why?

Abstract (arXiv)

Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers). Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence. In this work we present a novel theoretical characterization of the speed-up offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime (wallclock time). The novelty in our work is that our runtime analysis considers random straggler delays, which helps us design and compare distributed SGD algorithms that strike a balance between stragglers and staleness. We also present a new convergence analysis of asynchronous SGD variants without bounded or exponential delay assumptions, and a novel learning rate schedule to compensate for gradient staleness.

Key facts. Cited by 68 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

68 papers.

Sort:

By area:

  1. 2021A Field Guide to Federated Optimizationcited by 312
  2. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 188
  3. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  4. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 76
  5. 2020Towards Crowdsourced Training of Large Neural Networks using Decentralized Mixture-of-Expertscited by 43
  6. 2022Compute-Efficient Deep Learning: Algorithmic Trends and Opportunitiescited by 38
  7. 2021SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networkscited by 30
  8. 2022FLUTE: A Scalable, Extensible Framework for High-Performance Federated Learning Simulationscited by 27
  9. 2021Trade-offs of Local SGD at Scale: An Empirical Studycited by 19
  10. 2022AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregationcited by 19
  11. 2023Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacycited by 18
  12. 2024CO2: Efficient Distributed Training with Full Communication-Computation Overlapcited by 17
38 more
  1. 2025Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexitycited by 17
  2. 2022Asynchronous Decentralized Learning over Unreliable Wireless Networkscited by 13
  3. 2023The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Surveycited by 13
  4. 2023Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batchingcited by 12
  5. 2023DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updatescited by 12
  6. 2021Secure and Efficient Federated Learning Through Layering and Sharding Blockchaincited by 10
  7. 2022Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Datacited by 9
  8. 2021Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learningcited by 8
  9. 2024Achieving Linear Speedup in Asynchronous Federated Learning with Heterogeneous Clientscited by 7
  10. 2021Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delayscited by 6
  11. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 6
  12. 2021The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communicationcited by 5
  13. 2024Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computationscited by 5
  14. 2024Ordered Momentum for Asynchronous SGDcited by 5
  15. 2024MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Timescited by 5
  16. 2025ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learningcited by 5
  17. 2025Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneitycited by 5
  18. 2021Accelerating Neural Network Training with Distributed Asynchronous and Selective Optimization (DASO)cited by 4
  19. 2021Coding for Straggler Mitigation in Federated Learningcited by 4
  20. 2022CowClip: Reducing CTR Prediction Model Training Time from 12 hours to 10 minutes on 1 GPUcited by 4
  21. 2022GBA: A Tuning-free Approach to Switch between Synchronous and Asynchronous Training for Recommendation Modelcited by 4
  22. 2021Sync-Switch: Hybrid Parameter Synchronization for Distributed Deep Learningcited by 3
  23. 2024Momentum Approximation in Asynchronous Private Federated Learningcited by 3
  24. 2024FedAST: Federated Asynchronous Simultaneous Trainingcited by 3
  25. 2022Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learningcited by 2
  26. 2022STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronizationcited by 2
  27. 2022Accelerating Parallel Stochastic Gradient Descent via Non-blocking Mini-batchescited by 2
  28. 2024Ravnest: Decentralized Asynchronous Training on Heterogeneous Devicescited by 2
  29. 2024Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delayscited by 2
  30. 2025Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequencycited by 2
  31. 2025Asynchronous Federated Learning with non-convex client objective functions and heterogeneous datasetcited by 2
  32. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2
  33. 2026Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneitycited by 2
  34. 2026Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Methodcited by 2
  35. 2021Privacy-Preserving Serverless Edge Learning with Decentralized Small Datacited by 1
  36. 2022Lightweight Projective Derivative Codes for Compressed Asynchronous Gradient Descentcited by 1
  37. 2022BSAC-CoEx: Coexistence of URLLC and Distributed Learning Services via Device Selectioncited by 1
  38. 2024AntDT: A Self-Adaptive Distributed Training Framework for Leader and Straggler Nodescited by 1

50 most cited of 68 All 68 (JSON)