# Iteration Complexity Analysis of Block Coordinate Descent Methods

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

## Key facts

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

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

- [LP++: A Surprisingly Strong Linear Probe for Few-Shot CLIP](https://mlsanity.com/paper/2404.02285/) (2024)
- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [Boosting Vision-Language Models with Transduction](https://mlsanity.com/paper/2406.01837/) (2024)
- [Convergence of coordinate ascent variational inference for log-concave measures via optimal transport](https://mlsanity.com/paper/2404.08792/) (2024)
- [MoFO: Momentum-Filtered Optimizer for Mitigating Forgetting in LLM Fine-Tuning](https://mlsanity.com/paper/2407.20999/) (2024)
- [Delay-adaptive step-sizes for asynchronous learning](https://mlsanity.com/paper/2202.08550/) (2022)
- [Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization](https://mlsanity.com/paper/2212.05088/) (2022)
- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [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)
- [Complexity of Block Coordinate Descent with Proximal Regularization and Applications to Wasserstein CP-dictionary Learning](https://mlsanity.com/paper/2306.02420/) (2023)
- [Generate, Transduct, Adapt: Iterative Transduction with VLMs](https://mlsanity.com/paper/2501.06031/) (2025)
- [MISA: Memory-Efficient LLMs Optimization with Module-wise Importance Sampling](https://mlsanity.com/paper/2511.00056/) (2025)
- [Design Optimization of NOMA Aided Multi-STAR-RIS for Indoor Environments: A Convex Approximation Imitated Reinforcement Learning Approach](https://mlsanity.com/paper/2406.13280/) (2024)
- [Distributed optimization: designed for federated learning](https://mlsanity.com/paper/2508.08606/) (2025)
- [Two-Timescale Optimization Framework for Sparse-Feedback Linear-Quadratic Optimal Control](https://mlsanity.com/paper/2406.11168/) (2024)
- [Semantic-based Distributed Learning for Diverse and Discriminative Representations](https://mlsanity.com/paper/2604.18237/) (2026)

## Abstract (arXiv)

In this paper, we provide a unified iteration complexity analysis for a family of general block coordinate descent (BCD) methods, covering popular methods such as the block coordinate gradient descent (BCGD) and the block coordinate proximal gradient (BCPG), under various different coordinate update rules. We unify these algorithms under the so-called Block Successive Upper-bound Minimization (BSUM) framework, and show that for a broad class of multi-block nonsmooth convex problems, all algorithms covered by the BSUM framework achieve a global sublinear iteration complexity of O(1/r), where r is the iteration index. Moreover, for the case of block coordinate minimization (BCM) where each block is minimized exactly, we establish the sublinear convergence rate of O(1/r) without per block strong convexity assumption. Further, we show that when there are only two blocks of variables, a special BSUM algorithm with Gauss-Seidel rule can be accelerated to achieve an improved rate of O(1/r2).