# More Iterations per Second, Same Quality -- Why Asynchronous Algorithms may Drastically Outperform Traditional Ones

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2017.

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

- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data](https://mlsanity.com/paper/2203.01214/) (2022)
- [Accelerating Parallel Stochastic Gradient Descent via Non-blocking Mini-batches](https://mlsanity.com/paper/2211.00889/) (2022)
- [Utilizing Redundancy in Cost Functions for Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2110.10858/) (2021)
- [Impact of Redundancy on Resilience in Distributed Optimization and Learning](https://mlsanity.com/paper/2211.08622/) (2022)
- [Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach](https://mlsanity.com/paper/2603.26231/) (2026)

## Abstract (arXiv)

In this paper, we consider the convergence of a very general asynchronous-parallel algorithm called ARock, that takes many well-known asynchronous algorithms as special cases (gradient descent, proximal gradient, Douglas Rachford, ADMM, etc.). In asynchronous-parallel algorithms, the computing nodes simply use the most recent information that they have access to, instead of waiting for a full update from all nodes in the system. This means that nodes do not have to waste time waiting for information, which can be a major bottleneck, especially in distributed systems. When the system has p nodes, asynchronous algorithms may complete Theta(ln(p)) more iterations than synchronous algorithms in a given time period ("more iterations per second"). Although asynchronous algorithms may compute more iterations per second, there is error associated with using outdated information. How many more iterations in total are needed to compensate for this error is still an open question. The main results of this paper aim to answer this question. We prove, loosely, that as the size of the problem becomes large, the number of additional iterations that asynchronous algorithms need becomes negligible compared to the total number ("same quality" of the iterations). Taking these facts together, our results provide solid evidence of the potential of asynchronous algorithms to vastly speed up certain distributed computations.