mlsanityData to 14 Oct 2026

Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays

arXiv 2206.07638 ↗First posted 15 Jun 2022math.OC cs.DC cs.LGcited by 63

Not on the map. Why?

Abstract (arXiv)

The existing analysis of asynchronous stochastic gradient descent (SGD) degrades dramatically when any delay is large, giving the impression that performance depends primarily on the delay. On the contrary, we prove much better guarantees for the same asynchronous SGD algorithm regardless of the delays in the gradients, depending instead just on the number of parallel devices used to implement the algorithm. Our guarantees are strictly better than the existing analyses, and we also argue that asynchronous SGD outperforms synchronous minibatch SGD in the settings we consider. For our analysis, we introduce a novel recursion based on "virtual iterates" and delay-adaptive stepsizes, which allow us to derive state-of-the-art guarantees for both convex and non-convex objectives.

Key facts. Cited by 63 papers in the map (data through 14 Oct 2026). Builds on 34 of its 56 references that are in the map. First posted on arXiv 15 Jun 2022.

Builds on

34 of 56 references.

References · 34

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,492
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  6. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  7. 2014Convex Optimization: Algorithms and Complexitycited by 575
  8. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  9. 2017Ray: A Distributed Framework for Emerging AI Applicationscited by 527
  10. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
  11. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  12. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
22 more
  1. 2019SGD: General Analysis and Improved Ratescited by 207
  2. 2021FjORD: Fair and Accurate Federated Learning under heterogeneous targets with Ordered Dropoutcited by 192
  3. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 190
  4. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  5. 2018Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysiscited by 156
  6. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  7. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  8. 2017Revisiting Distributed Synchronous SGDcited by 142
  9. 2017Lower Bounds for Finding Stationary Points Icited by 126
  10. 2015Asynchronous Parallel Stochastic Gradient for Nonconvex Optimizationcited by 116
  11. 2016Asynchronous Stochastic Gradient Descent with Delay Compensationcited by 99
  12. 2015Massively Parallel Methods for Deep Reinforcement Learningcited by 82
  13. 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
  14. 2020FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tierscited by 64
  15. 2018A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updatescited by 47
  16. 2020Advances in Asynchronous Parallel and Distributed Optimizationcited by 40
  17. 2019Asynchronous Decentralized SGD with Quantized and Local Updatescited by 36
  18. 2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
  19. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  20. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  21. 2018Improved asynchronous parallel optimization analysis for stochastic incremental methodscited by 30
  22. 2022Delay-adaptive step-sizes for asynchronous learningcited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 5; 2023: 8; 2024: 22; 2025: 12; 2026: 16.

63 papers.

Sort:

By area:

  1. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  2. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 38
  3. 2022SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communicationcited by 21
  4. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  5. 2023FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUscited by 20
  6. 2025Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexitycited by 18
  7. 2024CO2: Efficient Distributed Training with Full Communication-Computation Overlapcited by 17
  8. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  9. 2022Unbounded Gradients in Federated Learning with Buffered Asynchronous Aggregationcited by 12
  10. 2023Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimizationcited by 11
  11. 2024Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Surveycited by 10
  12. 2024FADAS: Towards Federated Adaptive Asynchronous Optimizationcited by 10
38 more
  1. 2022Communication-Efficient Federated Learning With Data and Client Heterogeneitycited by 9
  2. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 9
  3. 2024Noiseless Privacy-Preserving Decentralized Learningcited by 9
  4. 2024Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailabilitycited by 9
  5. 2025FedMuon: Federated Learning with Bias-corrected LMO-based Optimizationcited by 8
  6. 2024Queuing dynamics of asynchronous Federated Learningcited by 6
  7. 2024ACCO: Accumulate While You Communicate for Communication-Overlapped Sharded LLM Trainingcited by 6
  8. 2024MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Timescited by 6
  9. 2025Nesterov Method for Asynchronous Pipeline Parallel Optimizationcited by 6
  10. 2022PersA-FL: Personalized Asynchronous Federated Learningcited by 5
  11. 2024Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computationscited by 5
  12. 2024Towards Faster Decentralized Stochastic Optimization with Communication Compressioncited by 5
  13. 2024Ordered Momentum for Asynchronous SGDcited by 5
  14. 2025Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEscited by 5
  15. 2025Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneitycited by 5
  16. 2024Asynchronous Heterogeneous Linear Quadratic Regulator Designcited by 4
  17. 2024Communication-Efficient Adaptive Batch Size Strategies for Distributed Local Gradient Methodscited by 4
  18. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  19. 2026AsyncMesh: Fully Asynchronous Optimization for Data and Pipeline Parallelismcited by 3
  20. 2023Convergence Analysis of Decentralized ASGDcited by 2
  21. 2024Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delayscited by 2
  22. 2025Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous MLcited by 2
  23. 2025Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequencycited by 2
  24. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2
  25. 2026Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneitycited by 2
  26. 2026Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Methodcited by 2
  27. 2026Staleness-Learning Rate Scaling Laws for Asynchronous RLHFcited by 2
  28. 2023FAVANO: Federated AVeraging with Asynchronous NOdescited by 1
  29. 2024Learning from straggler clients in federated learningcited by 1
  30. 2024Dual-Delayed Asynchronous SGD for Arbitrarily Heterogeneous Datacited by 1
  31. 2024Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Frameworkcited by 1
  32. 2024Asynchronous Parallel Policy Gradient Methods for the Linear Quadratic Regulatorcited by 1
  33. 2024Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batchingcited by 1
  34. 2025Orthogonal Calibration for Asynchronous Federated Learningcited by 1
  35. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  36. 2026LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averagingcited by 1
  37. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  38. 2024Cyclic Data Parallelism for Efficient Parallelism of Deep Neural Networkscited by 0

50 most cited of 63 All 63 (JSON)