Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems

Ruoyu Sun, Mingyi Hong

Abstract

The iteration complexity of the block-coordinate descent (BCD) type algorithm has been under extensive investigation. It was recently shown that for convex problems the classical cyclic BCGD (block coordinate gradient descent) achieves an $\mathcal{O}(1/r)$ complexity ($r$ is the number of passes of all blocks). However, such bounds are at least linearly depend on $K$ (the number of variable blocks), and are at least $K$ times worse than those of the gradient descent (GD) and proximal gradient (PG) methods. In this paper, we aim to close such theoretical performance gap between cyclic BCD and GD/PG. First we show that for a family of quadratic nonsmooth problems, the complexity bounds for cyclic Block Coordinate Proximal Gradient (BCPG), a popular variant of BCD, can match those of the GD/PG in terms of dependency on $K$ (up to a $\log^2(K)$ factor). For the same family of problems, we also improve the bounds of the classical BCD (with exact block minimization) by an order of $K$. Second, we establish an improved complexity bound of Coordinate Gradient Descent (CGD) for general convex problems which can match that of GD in certain scenarios. Our bounds are sharper than the known bounds as they are always at least $K$ times worse than GD. Our analyses do not depend on the update order of block variables inside each cycle, thus our results also apply to BCD methods with random permutation (random sampling without replacement, another popular variant).

Introduction

In large-scale optimization, Block Coordinate Descent (BCD) is a fundamental algorithm. By updating one "block" of variables at a time while keeping others fixed, it offers computational simplicity and strong empirical performance. However, a significant gap has persisted between its practical success and theoretical analysis. Standard convergence analysis for convex problems typically shows that Gradient Descent (GD) has a complexity of $\mathcal{O}(1/r)$, where $r$ is the number of iterations. In contrast, the best known bounds for cyclic BCD were $\mathcal{O}(K/r)$, where $K$ is the number of blocks. This suggests that BCD could be $K$ times slower than GD—a pessimistic prediction for high-dimensional problems where $K$ is large.

This research investigates whether this $K$-factor gap is a fundamental limitation or an artifact of conservative analysis. By focusing on cyclic Block Coordinate Proximal Gradient (BCPG) and classical BCD, we provide tighter bounds that more accurately reflect the algorithm's efficiency.

Methodology and Analytical Framework

To derive these improved bounds, we utilize a refined "three-step" analytical framework:

  1. Descent Estimation: Quantifying the objective function decrease over a full cycle.
  2. Cost-to-go Estimation: Estimating the remaining distance to the optimal value.
  3. Recursive Combination: Merging these estimates to determine the overall convergence rate.

A key technical innovation is the analysis of a "moving-iterate Hessian." This matrix captures the second-order behavior of the function across the different points visited during a single update cycle. We also leverage the spectral norm of triangular truncation operators to bound the impact of sequential updates.

Key Theoretical Insights

Our analysis reveals several counter-intuitive properties of BCD:

  • The Logarithmic Breakthrough: For quadratic nonsmooth problems (e.g., LASSO), the complexity depends on $\log^2(K)$ rather than $K$. This logarithmic factor is a massive improvement over linear dependency in high-dimensional settings.
  • Stepsize Sensitivity: We found that choosing a "conservative" global stepsize ($1/L$) leads to better theoretical complexity bounds (matching GD) than using "aggressive" block-specific stepsizes ($1/L_k$) in certain scenarios.
  • Order Independence: For quadratic problems, the analysis does not strictly depend on the update order within a cycle. Consequently, these results extend to Random Permutation BCD, where block orders are shuffled each cycle.

Results and Comparison

The following table summarizes our improved bounds compared to existing literature. Notably, for Quadratic Problems (QP), Theorem 2.1 establishes a bound of $\mathcal{O}(\log^2(2K)L/r)$, effectively removing the linear dependency on $K$ seen in previous cyclic BCGD analyses.

Comparison of iteration complexity bounds for various coordinate descent methods.

Furthermore, for general convex problems, Corollary 4.1 shows that Cyclic CGD can match the $L/r$ complexity of GD when using a small stepsize ($1/L$), providing a bound that is $K$ times sharper than previously known results.

Conclusion

This work significantly narrows the theoretical gap between cyclic BCD and Gradient Descent. While we have established near-optimal bounds for quadratic problems, the general convex case still presents challenges. Our "meta-bound" for general functions is tighter than previous work but may still exhibit a $K$-factor in worst-case scenarios. Future research will focus on extending these results to multi-dimensional blocks and determining if the remaining gap in general convex optimization can be entirely eliminated through even more refined analysis.

Summary updated

Abstract

The iteration complexity of the block-coordinate descent (BCD) type algorithm has been under extensive investigation. It was recently shown that for convex problems the classical cyclic BCGD (block coordinate gradient descent) achieves an $\mathcal{O}(1/r)$ complexity ($r$ is the number of passes of all blocks). However, such bounds are at least linearly depend on $K$ (the number of variable blocks), and are at least $K$ times worse than those of the gradient descent (GD) and proximal gradient (PG) methods. In this paper, we aim to close such theoretical performance gap between cyclic BCD and GD/PG. First we show that for a family of quadratic nonsmooth problems, the complexity bounds for cyclic Block Coordinate Proximal Gradient (BCPG), a popular variant of BCD, can match those of the GD/PG in terms of dependency on $K$ (up to a $\log^2(K)$ factor). For the same family of problems, we also improve the bounds of the classical BCD (with exact block minimization) by an order of $K$. Second, we establish an improved complexity bound of Coordinate Gradient Descent (CGD) for general convex problems which can match that of GD in certain scenarios. Our bounds are sharper than the known bounds as they are always at least $K$ times worse than GD. Our analyses do not depend on the update order of block variables inside each cycle, thus our results also apply to BCD methods with random permutation (random sampling without replacement, another popular variant).
BibTeX
@inproceedings{sun2015improved,
  author = {Ruoyu Sun and Mingyi Hong},
  title = {{Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=BJWK1vbd-H},
}
Figure