# Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 83 references that are in the map.
- First posted on arXiv 9 Sep 2021.

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

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1805.09965/) (2018)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [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)
- [An optimal randomized incremental gradient method](https://mlsanity.com/paper/1507.02000/) (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)
- [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties](https://mlsanity.com/paper/1403.3862/) (2014)
- [On the Convergence Rate of Incremental Aggregated Gradient Algorithms](https://mlsanity.com/paper/1506.02081/) (2015)
- [ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates](https://mlsanity.com/paper/1506.02396/) (2015)
- [Asynchronous stochastic convex optimization](https://mlsanity.com/paper/1508.00882/) (2015)
- [ASAGA: Asynchronous Parallel SAGA](https://mlsanity.com/paper/1606.04809/) (2016)
- [Asynchronous Coordinate Descent under More Realistic Assumptions](https://mlsanity.com/paper/1705.08494/) (2017)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)
- [Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods](https://mlsanity.com/paper/1608.01713/) (2016)
- [Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server](https://mlsanity.com/paper/1610.05507/) (2016)
- [More Iterations per Second, Same Quality -- Why Asynchronous Algorithms may Drastically Outperform Traditional Ones](https://mlsanity.com/paper/1708.05136/) (2017)
- [General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Scheme](https://mlsanity.com/paper/1910.05093/) (2019)

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

- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Asynchronous SGD on Graphs: a Unified Framework for Asynchronous Decentralized and Federated Optimization](https://mlsanity.com/paper/2311.00465/) (2023)
- [ACCO: Accumulate While You Communicate for Communication-Overlapped Sharded LLM Training](https://mlsanity.com/paper/2406.02613/) (2024)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Clustered Federated Learning based on Nonconvex Pairwise Fusion](https://mlsanity.com/paper/2211.04218/) (2022)
- [Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delays](https://mlsanity.com/paper/2405.10123/) (2024)
- [Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity](https://mlsanity.com/paper/2605.13434/) (2026)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)
- [Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching](https://mlsanity.com/paper/2408.07503/) (2024)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip](https://mlsanity.com/paper/2504.09792/) (2025)
- [Scalable Asynchronous Federated Modeling for Spatial Data](https://mlsanity.com/paper/2510.01771/) (2025)
- [Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum](https://mlsanity.com/paper/2605.02043/) (2026)
- [Stochastic convergence of parallel asynchronous adaptive first-order methods](https://mlsanity.com/paper/2606.01787/) (2026)
- [Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers](https://mlsanity.com/paper/2606.13287/) (2026)

## Abstract (arXiv)

We introduce novel convergence results for asynchronous iterations that appear in the analysis of parallel and distributed optimization algorithms. The results are simple to apply and give explicit estimates for how the degree of asynchrony impacts the convergence rates of the iterates. Our results shorten, streamline and strengthen existing convergence proofs for several asynchronous optimization methods and allow us to establish convergence guarantees for popular algorithms that were thus far lacking a complete theoretical understanding. Specifically, we use our results to derive better iteration complexity bounds for proximal incremental aggregated gradient methods, to obtain tighter guarantees depending on the average rather than maximum delay for the asynchronous stochastic gradient descent method, to provide less conservative analyses of the speedup conditions for asynchronous block-coordinate implementations of Krasnoselskii-Mann iterations, and to quantify the convergence rates for totally asynchronous iterations under various assumptions on communication delays and update rates.