Introduction
Coordinate descent (CD) has become a cornerstone of high-dimensional optimization, serving as the primary engine for widely-used machine learning libraries such as glmnet and scikit-learn. Its popularity stems from its efficiency in updating one variable at a time, which is particularly effective for large-scale datasets. However, while the empirical success of cyclic CD is well-documented, a rigorous theoretical understanding of its "endgame" behavior—specifically how it identifies the underlying structure of a solution and the rate at which it converges—has remained relatively elusive compared to other proximal methods.
This paper bridges the gap between practice and theory by providing a rigorous foundation for cyclic proximal coordinate descent. The authors demonstrate that for a broad class of nonsmooth problems, such as the Lasso, Sparse Logistic Regression, and Support Vector Machines (SVM), cyclic CD identifies the correct model structure in a finite number of steps and subsequently converges at a predictable linear rate.
Theoretical Framework
To analyze the convergence of cyclic CD, the authors employ two sophisticated mathematical frameworks:
- Partial Smoothness: The objective function is treated as being "smooth" along specific manifolds (e.g., the set of non-zero coefficients in a Lasso problem) and "sharp" in directions that require zeroing out. This allows for a geometric interpretation of how the algorithm navigates the optimization landscape.
- Fixed-Point Analysis of Epochs: Rather than analyzing individual coordinate updates, which can be erratic, the authors analyze a full "epoch" (a complete pass through all $p$ variables) as a single operator. By calculating the Jacobian of this epoch-wide operator, they can derive the exact local convergence rate.
Model Identification: The "Endgame"
A central contribution of this work is the proof of finite-time model identification. Under a "non-degeneracy" condition, the authors prove there exists a specific iteration $K$ after which the algorithm stops fluctuating between different sparsity patterns. From this point forward, the support (the set of non-zero indices) of the iterates matches the support of the true solution exactly.
Notably, the authors show that CD can identify the correct model even in cases where the solution to the optimization problem is not unique. This is a significant advancement over previous analyses of other algorithms that often required strict uniqueness assumptions.
Local Linear Convergence
The paper establishes that linear convergence is a local phenomenon that begins precisely after the model has been identified. Once the algorithm enters this "endgame" phase, the convergence rate is dictated by the spectral radius of the Jacobian of the epoch operator.
If the spectral radius is small, the algorithm converges rapidly to the solution. Conversely, if the radius is near 1, convergence slows. This provides a clear mathematical explanation for why CD performance can vary across different datasets and regularization parameters.
Experimental Validation
The researchers validated their theoretical findings using several classic machine learning datasets from the libsvm repository, including leukemia, gisette, rcv1, real-sim, and 20news. These datasets represent a range of challenges, from small-$n$/large-$p$ scenarios to large-scale sparse text classification.
Key findings from the experiments include:
- Theoretical Alignment: The empirical progress of the algorithm matches the predicted theoretical linear rates with high precision.
- Early Identification: In practice, model identification (the point where the support is correctly found) occurs relatively early in the process. This suggests that CD spends the majority of its computational effort refining the values of the relevant features rather than searching for the features themselves.
- Sharpness of Rates: The derived rates are "sharp," meaning they accurately predict the slope of the error curve on a log scale once the support is identified.
Limitations and Future Directions
While the paper provides a robust framework for understanding cyclic CD, it also identifies specific limitations. The proof for linear convergence relies on "restricted injectivity"—the requirement that the Hessian of the smooth part of the objective is positive definite on the support. When this condition fails (for instance, when the regularization parameter $\lambda$ is very small), the linear rate can degrade.
Future work may extend these findings to Block Coordinate Descent, where groups of variables are updated simultaneously. Additionally, the authors noted that linear convergence is often observed even when strict injectivity assumptions are not met, suggesting that further theoretical work is needed to explore non-strongly convex nonsmooth optimization.
Summary updated