# Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence

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

## Key facts

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

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

- [BAdam: A Memory Efficient Full Parameter Optimization Method for Large Language Models](https://mlsanity.com/paper/2404.02827/) (2024)
- [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)
- [BlockLLM: Memory-Efficient Adaptation of LLMs by Selecting and Optimizing the Right Coordinate Blocks](https://mlsanity.com/paper/2406.17296/) (2024)
- [ForestPrune: Compact Depth-Controlled Tree Ensembles](https://mlsanity.com/paper/2206.00128/) (2022)
- [On Surprising Effectiveness of Masking Updates in Adaptive Optimizers](https://mlsanity.com/paper/2602.15322/) (2026)
- [Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization](https://mlsanity.com/paper/2510.00823/) (2025)
- [Critical Influence of Overparameterization on Sharpness-aware Minimization](https://mlsanity.com/paper/2311.17539/) (2023)
- [Rockafellian Relaxation and Stochastic Optimization under Perturbations](https://mlsanity.com/paper/2204.04762/) (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)
- [Multi-convex Programming for Discrete Latent Factor Models Prototyping](https://mlsanity.com/paper/2504.01431/) (2025)
- [Laplacian-based Semi-Supervised Learning in Multilayer Hypergraphs by Coordinate Descent](https://mlsanity.com/paper/2301.12184/) (2023)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [FAST: An Optimization Framework for Fast Additive Segmentation in Transparent ML](https://mlsanity.com/paper/2402.12630/) (2024)
- [Analyzing the Evolution of Graphs and Texts](https://mlsanity.com/paper/2411.06295/) (2024)
- [A block-coordinate descent framework for non-convex composite optimization. Application to sparse precision matrix estimation](https://mlsanity.com/paper/2601.21467/) (2026)
- [BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning](https://mlsanity.com/paper/2610.13382/) (2026)

## Abstract (arXiv)

Block coordinate descent (BCD) methods are widely used for large-scale numerical optimization because of their cheap iteration costs, low memory requirements, amenability to parallelization, and ability to exploit problem structure. Three main algorithmic choices influence the performance of BCD methods: the block partitioning strategy, the block selection rule, and the block update rule. In this paper we explore all three of these building blocks and propose variations for each that can significantly improve the progress made by each BCD iteration. We (i) propose new greedy block-selection strategies that guarantee more progress per iteration than the Gauss-Southwell rule; (ii) explore practical issues like how to implement the new rules when using "variable" blocks; (iii) explore the use of message-passing to compute matrix or Newton updates efficiently on huge blocks for problems with sparse dependencies between variables; and (iv) consider optimal active manifold identification, which leads to bounds on the "active-set complexity" of BCD methods and leads to superlinear convergence for certain problems with sparse solutions (and in some cases finite termination at an optimal solution). We support all of our findings with numerical results for the classic machine learning problems of least squares, logistic regression, multi-class logistic regression, label propagation, and L1-regularization.