# Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2015.

## Built on by (most cited first, 30 of 39)

- [Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data](https://mlsanity.com/paper/2502.04664/) (2025)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [Beyond L1: Faster and Better Sparse Models with skglm](https://mlsanity.com/paper/2204.07826/) (2022)
- [MoFO: Momentum-Filtered Optimizer for Mitigating Forgetting in LLM Fine-Tuning](https://mlsanity.com/paper/2407.20999/) (2024)
- [Large-Scale Gaussian Processes via Alternating Projection](https://mlsanity.com/paper/2310.17137/) (2023)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [BlockLLM: Memory-Efficient Adaptation of LLMs by Selecting and Optimizing the Right Coordinate Blocks](https://mlsanity.com/paper/2406.17296/) (2024)
- [Data-driven reduced order models using invariant foliations, manifolds and autoencoders](https://mlsanity.com/paper/2206.12269/) (2022)
- [FIRE: An Optimization Approach for Fast Interpretable Rule Extraction](https://mlsanity.com/paper/2306.07432/) (2023)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [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)
- [A dual approach for federated learning](https://mlsanity.com/paper/2201.11183/) (2022)
- [Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm](https://mlsanity.com/paper/2307.01169/) (2023)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Quantum Speedup of Natural Gradient for Variational Bayes](https://mlsanity.com/paper/2106.05807/) (2021)
- [High-fidelity Interpretable Inverse Rig: An Accurate and Sparse Solution Optimizing the Quartic Blendshape Model](https://mlsanity.com/paper/2302.04820/) (2023)
- [Machine-learning invariant foliations in forced systems for reduced order modelling](https://mlsanity.com/paper/2403.14514/) (2024)
- [Joker: Joint Optimization Framework for Lightweight Kernel Machines](https://mlsanity.com/paper/2505.17765/) (2025)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [Neural Architecture Search for Quantum Autoencoders](https://mlsanity.com/paper/2511.19246/) (2025)
- [Differentially Private and Federated Structure Learning in Bayesian Networks](https://mlsanity.com/paper/2512.01708/) (2025)
- [CobBO: Coordinate Backoff Bayesian Optimization with Two-Stage Kernels](https://mlsanity.com/paper/2101.05147/) (2021)
- [An efficient projection neural network for ℓ1-regularized logistic regression](https://mlsanity.com/paper/2105.05449/) (2021)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization](https://mlsanity.com/paper/2207.07543/) (2022)

## Abstract (arXiv)

There has been significant recent work on the theory and application of randomized coordinate descent algorithms, beginning with the work of Nesterov [SIAM J. Optim., 22(2), 2012], who showed that a random-coordinate selection rule achieves the same convergence rate as the Gauss-Southwell selection rule. This result suggests that we should never use the Gauss-Southwell rule, as it is typically much more expensive than random selection. However, the empirical behaviours of these algorithms contradict this theoretical result: in applications where the computational costs of the selection rules are comparable, the Gauss-Southwell selection rule tends to perform substantially better than random coordinate selection. We give a simple analysis of the Gauss-Southwell rule showing that---except in extreme cases---its convergence rate is faster than choosing random coordinates. Further, in this work we (i) show that exact coordinate optimization improves the convergence rate for certain sparse problems, (ii) propose a Gauss-Southwell-Lipschitz rule that gives an even faster convergence rate given knowledge of the Lipschitz constants of the partial derivatives, (iii) analyze the effect of approximate Gauss-Southwell rules, and (iv) analyze proximal-gradient variants of the Gauss-Southwell rule.