# Alternating Randomized Block Coordinate Descent

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2018.

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

- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2209.08244/) (2022)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)
- [On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport](https://mlsanity.com/paper/2109.15030/) (2021)
- [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)
- [An Optimal Algorithm for Strongly Convex Min-min Optimization](https://mlsanity.com/paper/2212.14439/) (2022)

## Abstract (arXiv)

Block-coordinate descent algorithms and alternating minimization methods are fundamental optimization algorithms and an important primitive in large-scale optimization and machine learning. While various block-coordinate-descent-type methods have been studied extensively, only alternating minimization -- which applies to the setting of only two blocks -- is known to have convergence time that scales independently of the least smooth block. A natural question is then: is the setting of two blocks special? We show that the answer is "no" as long as the least smooth block can be optimized exactly -- an assumption that is also needed in the setting of alternating minimization. We do so by introducing a novel algorithm AR-BCD, whose convergence time scales independently of the least smooth (possibly non-smooth) block. The basic algorithm generalizes both alternating minimization and randomized block coordinate (gradient) descent, and we also provide its accelerated version -- AAR-BCD. As a special case of AAR-BCD, we obtain the first nontrivial accelerated alternating minimization algorithm.