# Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2015.

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

- [Personalized Federated Learning: A Unified Framework and Universal Optimization Techniques](https://mlsanity.com/paper/2102.09743/) (2021)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [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)
- [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)
- [A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data](https://mlsanity.com/paper/2203.03808/) (2022)
- [Understanding Progressive Training Through the Framework of Randomized Coordinate Descent](https://mlsanity.com/paper/2306.03626/) (2023)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [L-SVRG and L-Katyusha with Adaptive Sampling](https://mlsanity.com/paper/2201.13387/) (2022)
- [Information FOMO: The unhealthy fear of missing out on information. A method for removing misleading data for healthier models](https://mlsanity.com/paper/2208.13080/) (2022)
- [CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity](https://mlsanity.com/paper/2309.13307/) (2023)
- [KAKURENBO: Adaptively Hiding Samples in Deep Neural Network Training](https://mlsanity.com/paper/2310.10102/) (2023)
- [Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis](https://mlsanity.com/paper/2504.02957/) (2025)
- [Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization](https://mlsanity.com/paper/2207.07543/) (2022)
- [An Optimal Algorithm for Strongly Convex Min-min Optimization](https://mlsanity.com/paper/2212.14439/) (2022)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)
- [Randomized Subspace Nesterov Accelerated Gradient](https://mlsanity.com/paper/2605.00740/) (2026)

## Abstract (arXiv)

Accelerated coordinate descent is widely used in optimization due to its cheap per-iteration cost and scalability to large-scale problems. Up to a primal-dual transformation, it is also the same as accelerated stochastic gradient descent that is one of the central methods used in machine learning. In this paper, we improve the best known running time of accelerated coordinate descent by a factor up to √n. Our improvement is based on a clean, novel non-uniform sampling that selects each coordinate with a probability proportional to the square root of its smoothness parameter. Our proof technique also deviates from the classical estimation sequence technique used in prior work. Our speed-up applies to important problems such as empirical risk minimization and solving linear systems, both in theory and in practice.