# Accelerated, Parallel and Proximal Coordinate Descent

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

## Key facts

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

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

- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Beyond L1: Faster and Better Sparse Models with skglm](https://mlsanity.com/paper/2204.07826/) (2022)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient](https://mlsanity.com/paper/2206.01209/) (2022)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization](https://mlsanity.com/paper/2510.00823/) (2025)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [Distributed stochastic optimization with large delays](https://mlsanity.com/paper/2107.02919/) (2021)
- [Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization](https://mlsanity.com/paper/2303.16279/) (2023)
- [A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning](https://mlsanity.com/paper/2309.09977/) (2023)
- [A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data](https://mlsanity.com/paper/2203.03808/) (2022)
- [Low-complexity subspace-descent over symmetric positive definite manifold](https://mlsanity.com/paper/2305.02041/) (2023)
- [A Variational Inequality Approach to Bayesian Regression Games](https://mlsanity.com/paper/2103.13509/) (2021)
- [Stochastic Primal-Dual Three Operator Splitting Algorithm with Extension to Equivariant Regularization-by-Denoising](https://mlsanity.com/paper/2208.01631/) (2022)
- [Block-Structured Optimization for Subgraph Detection in Interdependent Networks](https://mlsanity.com/paper/2210.02702/) (2022)
- [An Asynchronous Decentralized Algorithm for Wasserstein Barycenter Problem](https://mlsanity.com/paper/2304.11653/) (2023)
- [Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimization](https://mlsanity.com/paper/2304.11665/) (2023)
- [Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification](https://mlsanity.com/paper/2410.09420/) (2024)
- [Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimization](https://mlsanity.com/paper/2411.15795/) (2024)
- [Differentially Private Random Block Coordinate Descent](https://mlsanity.com/paper/2412.17054/) (2024)
- [A block-coordinate descent framework for non-convex composite optimization. Application to sparse precision matrix estimation](https://mlsanity.com/paper/2601.21467/) (2026)
- [Randomized Subspace Nesterov Accelerated Gradient](https://mlsanity.com/paper/2605.00740/) (2026)

## Abstract (arXiv)

We propose a new stochastic coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel and PROXimal; this is the first time such a method is proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate 2barωbarL R2/(k+1)2 , where k is the iteration counter, barω is an average degree of separability of the loss function, barL is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and R is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of existing accelerated coordinate descent methods. The fact that the method depends on the average degree of separability, and not on the maximum degree of separability, can be attributed to the use of new safe large stepsizes, leading to improved expected separable overapproximation (ESO). These are of independent interest and can be utilized in all existing parallel stochastic coordinate descent algorithms based on the concept of ESO.