mlsanityData to 14 Oct 2026

Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity

arXiv 2501.16168 ↗First posted 27 Jan 2025cs.LG cs.DC math.OCcited by 18

Not on the map. Why?

Abstract (arXiv)

Asynchronous Stochastic Gradient Descent (Asynchronous SGD) is a cornerstone method for parallelizing learning in distributed machine learning. However, its performance suffers under arbitrarily heterogeneous computation times across workers, leading to suboptimal time complexity and inefficiency as the number of workers scales. While several Asynchronous SGD variants have been proposed, recent findings by Tyurin & Richt'arik (NeurIPS 2023) reveal that none achieve optimal time complexity, leaving a significant gap in the literature. In this paper, we propose Ringmaster ASGD, a novel Asynchronous SGD method designed to address these limitations and tame the inherent challenges of Asynchronous SGD. We establish, through rigorous theoretical analysis, that Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous and dynamically fluctuating worker computation times. This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 24 of its 35 references that are in the map. First posted on arXiv 27 Jan 2025.

Builds on

24 of 35 references.

References · 24

  1. 2019Advances and Open Problems in Federated Learningcited by 3,046
  2. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  5. 2017Asynchronous Decentralized Parallel Stochastic Gradient Descentcited by 159
  6. 2017Revisiting Distributed Synchronous SGDcited by 142
  7. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 95
  8. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  9. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  10. 2018Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGDcited by 68
  11. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
  12. 2020Optimal Complexity in Decentralized Trainingcited by 60
12 more
  1. 2018A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updatescited by 47
  2. 2015An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimizationcited by 38
  3. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  4. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  5. 2023Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Modelcited by 24
  6. 2021Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guaranteescited by 17
  7. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  8. 2024Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneitycited by 13
  9. 2024Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamicscited by 9
  10. 2024On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimizationcited by 8
  11. 2024MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Timescited by 6
  12. 2024Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computationscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 13.

18 papers.

Sort:

By area:

  1. 2025ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learningcited by 5
  2. 2025Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneitycited by 5
  3. 2025Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequencycited by 2
  4. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2
  5. 2026Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneitycited by 2
  6. 2026Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Methodcited by 2
  7. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  8. 2026LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averagingcited by 1
  9. 2025BurTorch: Revisiting Training from First Principles by Coupling Autodiff, Math Optimization, and Systemscited by 0
  10. 2026Ordered Local Momentum for Asynchronous Distributed Learning under Arbitrary Delayscited by 0
  11. 2026Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methodscited by 0
  12. 2026Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approachcited by 0
6 more
  1. 2026Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentumcited by 0
  2. 2026Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reductioncited by 0
  3. 2026Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglerscited by 0
  4. 2026One-Step Gradient Delay is Not a Barrier for Large-Scale Asynchronous Pipeline Parallel LLM Pretrainingcited by 0
  5. 2026Robustifying Asynchronous SGD via Soft Throttlingcited by 0
  6. 2026Asynchronous LLM Post-Training: Group-Mass Capping and Convergence Analysiscited by 0