# Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 29 references that are in the map.
- First posted on arXiv 3 Jul 2023.

## Builds on (most cited first, 8 of 8)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence](https://mlsanity.com/paper/1712.08859/) (2017)
- [Efficient Greedy Coordinate Descent for Composite Problems](https://mlsanity.com/paper/1810.06999/) (2018)
- [A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints](https://mlsanity.com/paper/1302.3074/) (2013)
- [Accelerated Stochastic Greedy Coordinate Descent by Soft Thresholding Projection onto Simplex](https://mlsanity.com/paper/1702.07842/) (2017)
- [Faster Convergence of a Randomized Coordinate Descent Method for Linearly Constrained Optimization Problems](https://mlsanity.com/paper/1709.00982/) (2017)

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

- [BlockLLM: Memory-Efficient Adaptation of LLMs by Selecting and Optimizing the Right Coordinate Blocks](https://mlsanity.com/paper/2406.17296/) (2024)
- [A stochastic gradient descent algorithm with random search directions](https://mlsanity.com/paper/2503.19942/) (2025)

## Abstract (arXiv)

We consider minimizing a smooth function subject to a summation constraint over its variables. By exploiting a connection between the greedy 2-coordinate update for this problem and equality-constrained steepest descent in the 1-norm, we give a convergence rate for greedy selection under a proximal Polyak-Lojasiewicz assumption that is faster than random selection and independent of the problem dimension n. We then consider minimizing with both a summation constraint and bound constraints, as arises in the support vector machine dual problem. Existing greedy rules for this setting either guarantee trivial progress only or require O(n2) time to compute. We show that bound- and summation-constrained steepest descent in the L1-norm guarantees more progress per iteration than previous rules and can be computed in only O(n log n) time.