# Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2014.

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

- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [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)
- [Joint Optimization of Communications and Federated Learning Over the Air](https://mlsanity.com/paper/2104.03490/) (2021)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Optimizing the Performative Risk under Weak Convexity Assumptions](https://mlsanity.com/paper/2209.00771/) (2022)
- [Asynchronous Gradient Play in Zero-Sum Multi-agent Games](https://mlsanity.com/paper/2211.08980/) (2022)
- [Distributed stochastic optimization with large delays](https://mlsanity.com/paper/2107.02919/) (2021)
- [A dual approach for federated learning](https://mlsanity.com/paper/2201.11183/) (2022)
- [On the Convergence of FedProx with Extrapolation and Inexact Prox](https://mlsanity.com/paper/2410.01410/) (2024)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03263/) (2022)
- [Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization](https://mlsanity.com/paper/2206.14981/) (2022)
- [Useful Compact Representations for Data-Fitting](https://mlsanity.com/paper/2403.12206/) (2024)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Asynchronous Message-Passing and Zeroth-Order Optimization Based Distributed Learning with a Use-Case in Resource Allocation in Communication Networks](https://mlsanity.com/paper/2311.04604/) (2023)
- [Accelerated Markov Chain Monte Carlo Using Adaptive Weighting Scheme](https://mlsanity.com/paper/2408.12888/) (2024)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)
- [Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings](https://mlsanity.com/paper/2506.08428/) (2025)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Scalable Asynchronous Federated Modeling for Spatial Data](https://mlsanity.com/paper/2510.01771/) (2025)

## Abstract (arXiv)

We describe an asynchronous parallel stochastic proximal coordinate descent algorithm for minimizing a composite objective function, which consists of a smooth convex function plus a separable convex function. In contrast to previous analyses, our model of asynchronous computation accounts for the fact that components of the unknown vector may be written by some cores simultaneously with being read by others. Despite the complications arising from this possibility, the method achieves a linear convergence rate on functions that satisfy an optimal strong convexity property and a sublinear rate (1/k) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is O(n1/4). We describe results from implementation on ten cores of a multicore processor.