# Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity

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

## 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 (most cited first, 24 of 24)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization](https://mlsanity.com/paper/1805.10222/) (2018)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model](https://mlsanity.com/paper/2305.12387/) (2023)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity](https://mlsanity.com/paper/2402.04785/) (2024)
- [Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics](https://mlsanity.com/paper/2408.04929/) (2024)
- [On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization](https://mlsanity.com/paper/2405.16218/) (2024)
- [MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times](https://mlsanity.com/paper/2410.04285/) (2024)
- [Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations](https://mlsanity.com/paper/2405.15545/) (2024)

## Built on by (most cited first, 18 of 18)

- [ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning](https://mlsanity.com/paper/2502.00775/) (2025)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequency](https://mlsanity.com/paper/2502.08206/) (2025)
- [Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.19379/) (2026)
- [Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity](https://mlsanity.com/paper/2605.13434/) (2026)
- [Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method](https://mlsanity.com/paper/2605.18174/) (2026)
- [Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning](https://mlsanity.com/paper/2509.24305/) (2025)
- [LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging](https://mlsanity.com/paper/2605.20866/) (2026)
- [BurTorch: Revisiting Training from First Principles by Coupling Autodiff, Math Optimization, and Systems](https://mlsanity.com/paper/2503.13795/) (2025)
- [Ordered Local Momentum for Asynchronous Distributed Learning under Arbitrary Delays](https://mlsanity.com/paper/2601.12322/) (2026)
- [Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods](https://mlsanity.com/paper/2602.03802/) (2026)
- [Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach](https://mlsanity.com/paper/2603.26231/) (2026)
- [Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum](https://mlsanity.com/paper/2605.02043/) (2026)
- [Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction](https://mlsanity.com/paper/2605.08871/) (2026)
- [Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers](https://mlsanity.com/paper/2606.13287/) (2026)
- [One-Step Gradient Delay is Not a Barrier for Large-Scale Asynchronous Pipeline Parallel LLM Pretraining](https://mlsanity.com/paper/2606.30634/) (2026)
- [Robustifying Asynchronous SGD via Soft Throttling](https://mlsanity.com/paper/2609.39357/) (2026)
- [Asynchronous LLM Post-Training: Group-Mass Capping and Convergence Analysis](https://mlsanity.com/paper/2610.01896/) (2026)

## 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.