# Accelerating Greedy Coordinate Descent Methods

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2018.

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

- [Toward Understanding Why Adam Converges Faster Than SGD for Transformers](https://mlsanity.com/paper/2306.00204/) (2023)
- [Order Matters: Agent-by-agent Policy Optimization](https://mlsanity.com/paper/2302.06205/) (2023)
- [A dual approach for federated learning](https://mlsanity.com/paper/2201.11183/) (2022)
- [Optimal low-rank stochastic gradient estimation for LLM training](https://mlsanity.com/paper/2603.20632/) (2026)

## Abstract (arXiv)

We study ways to accelerate greedy coordinate descent in theory and in practice, where "accelerate" refers either to O(1/k2) convergence in theory, in practice, or both. We introduce and study two algorithms: Accelerated Semi-Greedy Coordinate Descent (ASCD) and Accelerated Greedy Coordinate Descent (AGCD). While ASCD takes greedy steps in the x-updates and randomized steps in the z-updates, AGCD is a straightforward extension of standard greedy coordinate descent that only takes greedy steps. On the theory side, our main results are for ASCD: we show that ASCD achieves O(1/k2) convergence, and it also achieves accelerated linear convergence for strongly convex functions. On the empirical side, we observe that both AGCD and ASCD outperform Accelerated Randomized Coordinate Descent on a variety of instances. In particular, we note that AGCD significantly outperforms the other accelerated coordinate descent methods in numerical tests, in spite of a lack of theoretical guarantees for this method. To complement the empirical study of AGCD, we present a Lyapunov energy function argument that points to an explanation for why a direct extension of the acceleration proof for AGCD does not work; and we also introduce a technical condition under which AGCD is guaranteed to have accelerated convergence. Last of all, we confirm that this technical condition holds in our empirical study.