# Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 39 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Builds on (most cited first, 27 of 27)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [ZeRO: Memory Optimizations Toward Training Trillion Parameter Models](https://mlsanity.com/paper/1910.02054/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Horovod: fast and easy distributed deep learning in TensorFlow](https://mlsanity.com/paper/1802.05799/) (2018)
- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [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)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (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)
- [Asynchrony begets Momentum, with an Application to Deep Learning](https://mlsanity.com/paper/1605.09774/) (2016)
- [Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model](https://mlsanity.com/paper/2305.12387/) (2023)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [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)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Birch SGD: A Tree Graph Framework for Local and Asynchronous SGD Methods](https://mlsanity.com/paper/2505.09218/) (2025)
- [Optimal sub-Gaussian variance proxy for truncated Gaussian and exponential random variables](https://mlsanity.com/paper/2403.08628/) (2024)

## Abstract (arXiv)

Modern distributed optimization methods mostly rely on traditional synchronous approaches, despite substantial recent progress in asynchronous optimization. We revisit Synchronous SGD and its robust variant, called m-Synchronous SGD, and theoretically show that they are nearly optimal in many heterogeneous computation scenarios, which is somewhat unexpected. We analyze the synchronous methods under random computation times and adversarial partial participation of workers, and prove that their time complexities are optimal in many practical regimes, up to logarithmic factors. While synchronous methods are not universal solutions and there exist tasks where asynchronous methods may be necessary, we show that they are sufficient for many modern heterogeneous computation scenarios.