TL;DR
This paper provides a comprehensive review of the numerical engines behind Lasso regression, comparing five major algorithms: ISTA, FISTA, CGDA, SLA, and PFA. The authors highlight that while most methods converge at a rate of $O(1/k)$, the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) stands out with a superior $O(1/k^2)$ convergence rate, making it the most robust choice for high-dimensional sparse modeling.
What Problem Does This Paper Address?
The Least Absolute Shrinkage and Selection Operator (Lasso) is a cornerstone of modern statistics, prized for its ability to perform variable selection and regularization simultaneously. However, there is a mathematical "catch": the Lasso objective function includes an $\ell_1$ penalty (the absolute value of the coefficients).
Because the absolute value function has a sharp "kink" at zero, it is non-differentiable. This means we cannot use standard calculus to find a closed-form solution. Instead, we must rely on iterative numerical algorithms. While the statistical properties of Lasso are well-documented, this paper fills a gap by providing a clear, comparative review of the optimization strategies used to actually solve the problem.
Methods
The authors categorize and analyze five representative algorithms:
- ISTA (Iterative Shrinkage-Thresholding Algorithm): A first-order method that uses a quadratic approximation of the loss function combined with a "soft-thresholding" operator to handle the non-differentiable $\ell_1$ term.
- FISTA (Fast ISTA): An "accelerated" version of ISTA that incorporates a momentum term (using information from the previous two iterations rather than just one).
- CGDA (Coordinate Gradient Descent Algorithm): The logic behind the popular
glmnetpackage. It optimizes one coefficient at a time while holding others fixed, cycling through all variables until convergence. - SLA (Smooth L1 Algorithm): Instead of tackling the "kink" at zero, SLA replaces the $\ell_1$ penalty with a smooth, twice-differentiable surrogate function (using a log-sum-exp approximation).
- PFA (Path Following Algorithm): This method exploits the fact that the Lasso solution is "piecewise linear" with respect to the regularization parameter $\lambda$. It attempts to find the specific values of $\lambda$ where the set of non-zero coefficients changes.
Datasets
As a theoretical survey and review, the paper does not utilize empirical datasets for performance benchmarking. Instead, it relies on mathematical proofs of convergence rates and a constructed counter-example in Section 3.5.1 to demonstrate the specific conditions under which the Path Following Algorithm (PFA) fails to recover the correct support set.
Key Insights and Ideas
- The Power of Momentum: The jump from ISTA to FISTA illustrates the massive impact of Nesterov-style acceleration. By simply adding a smart "momentum" weight to the update rule, the convergence rate improves from $O(1/k)$ to $O(1/k^2)$ without significantly increasing the computational cost per iteration.
- The Smoothing Trade-off: While SLA makes the problem "easier" by making it differentiable, the approximation itself introduces an error. This error prevents SLA from reaching the $O(1/k^2)$ rate of other accelerated methods when measured against the original Lasso objective.
- Coordinate Descent's Popularity: Even though CGDA has a theoretical convergence rate of $O(1/k)$ (similar to basic ISTA), it is highly effective in practice because many real-world datasets have sparse solutions where updating one variable at a time is computationally cheap.
- The Fragility of Path Following: PFA is mathematically elegant but practically risky. The authors show that in general cases, PFA can fail to visit the correct subsets of variables, meaning it isn't a universal solver for Lasso.
Key Results
The paper summarizes the theoretical efficiency of the algorithms in a concise comparison:
| Algorithm | Convergence Rate | Computational Complexity |
|---|---|---|
| ISTA | $O(1/k)$ | $O(kp^2)$ |
| FISTA | $O(1/k^2)$ | $O(kp^2)$ |
| CGDA | $O(1/k)$ | $O(kp^2)$ |
| SLA | $O(1/k)$ | $O(kp^2)$ |
| PFA | Variable/Unpredictable | $O(nKp^2)$ (can be $O(np^3)$) |
Note: $k$ is the number of iterations, $p$ is the number of covariates, and $n$ is the number of observations.
FISTA is identified as the "best and relatively robust" performer due to its superior theoretical convergence rate while maintaining the same per-iteration complexity as simpler methods.
Limitations and Future Work
- PFA Convergence: The authors note that the upper bound for the number of steps ($K$) in the Path Following Algorithm remains an open question in contemporary literature, making its worst-case complexity unpredictable.
- LARS Limitations: The paper briefly discusses Least Angle Regression (LARS), noting that it has fallen out of favor because its stopping criteria are poorly defined in existing literature and it is not workable for all cases.
- Hyperparameter Selection: The review explicitly excludes the problem of choosing the regularization parameter $\lambda$, focusing purely on the optimization once $\lambda$ is fixed. Future work could bridge the gap between optimization efficiency and automated parameter tuning (like cross-validation).
Summary updated