Convergence of Common Proximal Methods for L1-Regularized Least Squares

Shaozhe Tao, Daniel Boley, Shuzhong ZhangIJCAI 2015

Introduction

The LASSO ($L_1$-regularized least squares) is a cornerstone of modern machine learning, yet the practical behavior of its solvers often deviates from theoretical global convergence bounds. While FISTA is theoretically faster than ISTA ($O(1/k^2)$ vs $O(1/k)$), practitioners frequently observe "stagnation" phases or find that Coordinate Descent (CD) outperforms accelerated methods in the final stages of convergence. This research, presented at IJCAI 2015, provides a rigorous explanation for these phenomena by analyzing the local behavior of ADMM, ISTA, FISTA, and CD through the lens of matrix eigenanalysis.

Theoretical Framework: The Matrix Recurrence

The authors model the non-linear updates of these proximal methods as linear recurrences once the algorithm identifies the correct "support" (the set of non-zero coefficients). By introducing a "flag matrix" ($D$) to represent the state of the shrinkage operator, the iteration is expressed as a unified matrix recurrence: $w^{[k+1]} = M w^{[k]} + h$.

This linearization allows for a spectral analysis where the local convergence rate is determined by the spectral radius of the iteration matrix $M$. The study identifies four distinct regimes:

  • Regime A: Linear convergence to the unique solution.
  • Regime B: Stagnation, where the algorithm takes small, constant-length steps (associated with a Jordan block for an eigenvalue of 1).
  • Regime C: Convergence to a non-unique solution.
  • Regime D: A transitional phase where the active set is still being determined.
Convergence behavior of various algorithms showing the transition between regimes and the stagnation of ISTA in Regime B.

Key Insights: Why Coordinate Descent Wins Locally

A primary contribution of this work is the mathematical proof that Coordinate Descent acts as a preconditioned version of ISTA. In the final regime, ISTA corresponds to a Richardson iteration, while CD corresponds to a Gauss-Seidel iteration. This preconditioning effect significantly reduces the spectral radius, explaining why CD's local convergence rate is often orders of magnitude faster than its counterparts.

Furthermore, the analysis reveals the "FISTA Paradox." While FISTA's momentum provides a superior global rate, it can introduce oscillations near the solution. In the final regime, the unaccelerated ISTA can actually reach high precision faster because it avoids these momentum-induced fluctuations. This insight led the authors to propose a Hybrid F/ISTA approach: use FISTA to reach the correct neighborhood quickly, then switch to ISTA or CD to finalize the solution without oscillations.

Spectral visualization of the iteration matrices. CD's eigenvalues are clustered significantly closer to the origin than those of ISTA or ADMM, indicating faster local convergence.

Empirical Results

The theoretical findings were validated using synthetic compressed sensing problems. The results confirmed that:

  • Local Rates: CD consistently achieved the smallest eigenvalues (e.g., a rate of 0.141 compared to ADMM's 0.897 and FISTA's 0.975 in specific tests).
  • Iteration Efficiency: While FISTA reaches the "final regime" in fewer steps than ISTA, CD often requires the fewest total iterations to reach high precision.

Conclusion

By moving beyond global bounds to local eigenanalysis, this paper clarifies the practical trade-offs between popular LASSO solvers. The insights suggest that for high-precision applications, switching to a "slower" unaccelerated method or using Coordinate Descent in the final stages is often the most efficient strategy. Future work may extend this methodology to other proximal operators, such as Group LASSO.

Summary updated

BibTeX
@inproceedings{tao2015convergence,
  author = {Shaozhe Tao and Daniel Boley and Shuzhong Zhang},
  title = {{Convergence of Common Proximal Methods for L1-Regularized Least Squares}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure