# On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2024.

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

- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Efficient AllReduce with Stragglers](https://mlsanity.com/paper/2505.23523/) (2025)
- [Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning](https://mlsanity.com/paper/2509.24305/) (2025)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction](https://mlsanity.com/paper/2506.23836/) (2025)
- [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)

We consider the decentralized stochastic asynchronous optimization setup, where many workers asynchronously calculate stochastic gradients and asynchronously communicate with each other using edges in a multigraph. For both homogeneous and heterogeneous setups, we prove new time complexity lower bounds under the assumption that computation and communication speeds are bounded. We develop a new nearly optimal method, Fragile SGD, and a new optimal method, Amelie SGD, that converge under arbitrary heterogeneous computation and communication speeds and match our lower bounds (up to a logarithmic factor in the homogeneous setting). Our time complexities are new, nearly optimal, and provably improve all previous asynchronous/synchronous stochastic methods in the decentralized setup.