# An Asynchronous Parallel Stochastic Coordinate Descent Algorithm

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2013.

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

- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [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)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [Efficient and Light-Weight Federated Learning via Asynchronous Distributed Dropout](https://mlsanity.com/paper/2210.16105/) (2022)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [On generalization bounds for deep networks based on loss surface implicit regularization](https://mlsanity.com/paper/2201.04545/) (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)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [A dual approach for federated learning](https://mlsanity.com/paper/2201.11183/) (2022)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [Adaptive Stochastic Gradient Descent for Fast and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2208.03134/) (2022)
- [Convex and Bilevel Optimization for Neuro-Symbolic Inference and Learning](https://mlsanity.com/paper/2401.09651/) (2024)
- [Learning Linear Models Using Distributed Iterative Hessian Sketching](https://mlsanity.com/paper/2112.04101/) (2021)
- [A Machine Learning Framework for Distributed Functional Compression over Wireless Channels in IoT](https://mlsanity.com/paper/2201.09483/) (2022)
- [FedDec: Peer-to-peer Aided Federated Learning](https://mlsanity.com/paper/2306.06715/) (2023)
- [Distributed Dual Coordinate Ascent with Imbalanced Data on a General Tree Network](https://mlsanity.com/paper/2308.14783/) (2023)
- [Accelerated Markov Chain Monte Carlo Using Adaptive Weighting Scheme](https://mlsanity.com/paper/2408.12888/) (2024)
- [Continuous Optimization for p-adic Models](https://mlsanity.com/paper/2609.25501/) (2026)

## Abstract (arXiv)

We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential 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/2) in unconstrained optimization and O(n1/4) in the separable-constrained case, where n is the number of variables. We describe results from implementation on 40-core processors.