# Asynchronous Coordinate Descent under More Realistic Assumptions

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

## Key facts

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

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

- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Stability and Generalization for Randomized Coordinate Descent](https://mlsanity.com/paper/2108.07414/) (2021)
- [Asynchronous speedup in decentralized optimization](https://mlsanity.com/paper/2106.03585/) (2021)
- [TensAIR: Real-Time Training of Neural Networks from Data-streams](https://mlsanity.com/paper/2211.10280/) (2022)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)
- [A Machine Learning Framework for Distributed Functional Compression over Wireless Channels in IoT](https://mlsanity.com/paper/2201.09483/) (2022)
- [Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent](https://mlsanity.com/paper/2308.09430/) (2023)
- [Distributed Dual Coordinate Ascent with Imbalanced Data on a General Tree Network](https://mlsanity.com/paper/2308.14783/) (2023)
- [On the Convergence Theory of Pipeline Gradient-based Analog In-memory Training](https://mlsanity.com/paper/2410.15155/) (2024)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)

## Abstract (arXiv)

Asynchronous-parallel algorithms have the potential to vastly speed up algorithms by eliminating costly synchronization. However, our understanding to these algorithms is limited because the current convergence of asynchronous (block) coordinate descent algorithms are based on somewhat unrealistic assumptions. In particular, the age of the shared optimization variables being used to update a block is assumed to be independent of the block being updated. Also, it is assumed that the updates are applied to randomly chosen blocks. In this paper, we argue that these assumptions either fail to hold or will imply less efficient implementations. We then prove the convergence of asynchronous-parallel block coordinate descent under more realistic assumptions, in particular, always without the independence assumption. The analysis permits both the deterministic (essentially) cyclic and random rules for block choices. Because a bound on the asynchronous delays may or may not be available, we establish convergence for both bounded delays and unbounded delays. The analysis also covers nonconvex, weakly convex, and strongly convex functions. We construct Lyapunov functions that directly model both objective progress and delays, so delays are not treated errors or noise. A continuous-time ODE is provided to explain the construction at a high level.