# Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 66 references that are in the map.
- First posted on arXiv 26 Sep 2025.

## Builds on (most cited first, 30 of 49)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [Towards Personalized Federated Learning](https://mlsanity.com/paper/2103.00710/) (2021)
- [Bayesian Nonparametric Federated Learning of Neural Networks](https://mlsanity.com/paper/1905.12022/) (2019)
- [Asynchronous Federated Optimization](https://mlsanity.com/paper/1903.03934/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Asynchronous Stochastic Gradient Descent with Delay Compensation](https://mlsanity.com/paper/1609.08326/) (2016)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [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)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Advances in Asynchronous Parallel and Distributed Optimization](https://mlsanity.com/paper/2006.13838/) (2020)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [Improved asynchronous parallel optimization analysis for stochastic incremental methods](https://mlsanity.com/paper/1801.03749/) (2018)

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

- [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)
- [LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging](https://mlsanity.com/paper/2605.20866/) (2026)
- [Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods](https://mlsanity.com/paper/2602.03802/) (2026)
- [Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction](https://mlsanity.com/paper/2605.08871/) (2026)

## Abstract (arXiv)

Asynchronous stochastic gradient methods are central to scalable distributed optimization, particularly when devices differ in computational capabilities. Such settings arise naturally in federated learning, where training takes place on smartphones and other heterogeneous edge devices. In addition to varying computation speeds, these devices often hold data from different distributions. However, existing asynchronous SGD methods struggle in such heterogeneous settings and face two key limitations. First, many rely on unrealistic assumptions of similarity across workers' data distributions. Second, methods that relax this assumption still fail to achieve theoretically optimal performance under heterogeneous computation times. We introduce Ringleader ASGD, the first asynchronous SGD algorithm that attains the theoretical lower bounds for parallel first-order stochastic methods in the smooth nonconvex regime, thereby achieving optimal time complexity under data heterogeneity and without restrictive similarity assumptions. Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary and even time-varying worker computation speeds, closing a fundamental gap in the theory of asynchronous optimization.