# Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems

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

## Key facts

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

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

- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [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)
- [A dual approach for federated learning](https://mlsanity.com/paper/2201.11183/) (2022)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data](https://mlsanity.com/paper/2203.03808/) (2022)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [ALS: Augmented Lagrangian Sketching Methods for Linear Systems](https://mlsanity.com/paper/2208.06152/) (2022)
- [Accelerated Doubly Stochastic Gradient Algorithm for Large-scale Empirical Risk Minimization](https://mlsanity.com/paper/2304.11665/) (2023)
- [Zero-Order Optimization for LLM Fine-Tuning via Learnable Direction Sampling](https://mlsanity.com/paper/2602.13659/) (2026)
- [How AI settled the complexity of the oldest SGD algorithm](https://mlsanity.com/paper/2606.29593/) (2026)

## Abstract (arXiv)

In this paper we show how to accelerate randomized coordinate descent methods and achieve faster convergence rates without paying per-iteration costs in asymptotic running time. In particular, we show how to generalize and efficiently implement a method proposed by Nesterov, giving faster asymptotic running times for various algorithms that use standard coordinate descent as a black box. In addition to providing a proof of convergence for this new general method, we show that it is numerically stable, efficiently implementable, and in certain regimes, asymptotically optimal. To highlight the computational power of this algorithm, we show how it can used to create faster linear system solvers in several regimes: - We show how this method achieves a faster asymptotic runtime than conjugate gradient for solving a broad class of symmetric positive definite systems of equations. - We improve the best known asymptotic convergence guarantees for Kaczmarz methods, a popular technique for image reconstruction and solving overdetermined systems of equations, by accelerating a randomized algorithm of Strohmer and Vershynin. - We achieve the best known running time for solving Symmetric Diagonally Dominant (SDD) system of equations in the unit-cost RAM model, obtaining an O(m log^{3/2} n (log log n)^{1/2} log (log n / eps)) asymptotic running time by accelerating a recent solver by Kelner et al. Beyond the independent interest of these solvers, we believe they highlight the versatility of the approach of this paper and we hope that they will open the door for further algorithmic improvements in the future.