# Markov Chain Block Coordinate Descent

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

## Key facts

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

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

- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning](https://mlsanity.com/paper/2309.09977/) (2023)
- [Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates](https://mlsanity.com/paper/2201.01652/) (2022)

## Abstract (arXiv)

The method of block coordinate gradient descent (BCD) has been a powerful method for large-scale optimization. This paper considers the BCD method that successively updates a series of blocks selected according to a Markov chain. This kind of block selection is neither i.i.d. random nor cyclic. On the other hand, it is a natural choice for some applications in distributed optimization and Markov decision process, where i.i.d. random and cyclic selections are either infeasible or very expensive. By applying mixing-time properties of a Markov chain, we prove convergence of Markov chain BCD for minimizing Lipschitz differentiable functions, which can be nonconvex. When the functions are convex and strongly convex, we establish both sublinear and linear convergence rates, respectively. We also present a method of Markov chain inertial BCD. Finally, we discuss potential applications.