Introduction
In large-scale machine learning and data science, optimization problems are frequently solved by updating one "block" of variables at a time while keeping others fixed—a method known as Block Coordinate Descent (BCD). While BCD is incredibly popular in practice due to its ease of implementation and empirical speed, its theoretical "iteration complexity" (the number of passes through the data required to reach a certain accuracy) has historically contained a troubling flaw.
Existing mathematical proofs suggested that BCD was at least $K$ times slower than standard Gradient Descent (GD), where $K$ is the number of variable blocks. For a problem with millions of variables, a factor of $K$ represents the difference between an algorithm finishing in minutes versus years. This paper bridges this long-standing theoretical gap by proving that Cyclic BCD is much faster than previously thought. The authors demonstrate that for many convex problems, BCD’s performance is nearly independent of $K$, effectively matching the efficiency of standard Gradient Descent and debunking the idea that BCD is inherently $K$ times slower.
Methods
The authors provide a refined analysis of two popular BCD variants:
- Cyclic Block Coordinate Proximal Gradient (BCPG): Typically used for nonsmooth quadratic problems (such as LASSO).
- Coordinate Gradient Descent (CGD): Used for general smooth convex problems.
Their proof strategy follows a rigorous "three-step approach":
- Sufficient Descent: Proving the objective value drops sufficiently at each step.
- Cost-to-go Estimate: Estimating the remaining distance the algorithm must cover to reach the optimum.
- Convergence Bound: Combining these estimates to derive the final convergence rate.
The core novelty lies in how the authors handle the "cross-talk" between variable blocks. Instead of assuming worst-case interactions among all $K$ blocks, they leverage advanced matrix analysis—specifically properties of the Hessian and Kronecker products—to show that errors do not accumulate as severely as previously feared.
Key Insights and Results
The paper provides significantly tighter bounds than previous state-of-the-art analyses, closing the theoretical performance gap between BCD and GD.
- Closing the $K$-Gap for Quadratic Problems: For quadratic problems like least squares or LASSO, the authors prove the complexity depends on $K$ only through a minor $\log^2(K)$ factor. The new bound is $O(\frac{\log^2(K)}{r})$, where $r$ is the number of passes. Previous bounds were $O(\frac{K}{r})$. This represents a massive theoretical improvement when $K$ is large.
- General Convex Problems: They established a bound of $O(1/r)$ with a constant that can match Gradient Descent in specific scenarios, such as when the problem's Hessian is diagonal.
- The "Conservative Step-size" Paradox: A surprising finding is that using a "conservative" (smaller) step-size can sometimes yield a better theoretical complexity bound than an "aggressive" (larger) step-size. Conservative steps cause the algorithm to behave more like a stable global gradient update.
- Update Order: The analysis reveals that these improved bounds apply not just to the standard cyclic order (1, 2, ..., K), but also to "random permutations" (shuffling the blocks before each pass without replacement), a common practice in modern machine learning.
The improvements are summarized by comparing the new bounds against previously established ones (such as those by Beck & Tetruashvili). In several common scenarios, the new bounds are $K$ to $K^2$ times better than the best previously known results.
Limitations and Future Work
While this paper makes significant theoretical strides, a few limitations remain:
- The Log Factor: Although vastly superior to a linear $K$ factor, a $\log^2(K)$ factor still persists for quadratic problems. Whether this can be removed entirely remains an open question.
- Scalar vs. Block: For general convex problems, the current analysis is limited to "scalar" blocks (where each block consists of just one variable). Extending this to multi-dimensional blocks is a target for future work.
- Convexity Constraint: The results strictly apply to convex problems. Because BCD is widely used for non-convex problems (like Matrix Factorization or Deep Learning), extending these tight bounds to the non-convex regime remains a major challenge for the optimization community.
Summary updated