A survey of numerical algorithms that can solve the Lasso problems

Yujie Zhao, Xiaoming Huo

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:

  1. 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.
  2. FISTA (Fast ISTA): An "accelerated" version of ISTA that incorporates a momentum term (using information from the previous two iterations rather than just one).
  3. CGDA (Coordinate Gradient Descent Algorithm): The logic behind the popular glmnet package. It optimizes one coefficient at a time while holding others fixed, cycling through all variables until convergence.
  4. 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).
  5. 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

Abstract

Abstract In statistics, the least absolute shrinkage and selection operator (Lasso) is a regression method that performs both variable selection and regularization. There is a lot of literature available, discussing the statistical properties of the regression coefficients estimated by the Lasso method. However, there lacks a comprehensive review discussing the algorithms to solve the optimization problem in Lasso. In this review, we summarize five representative algorithms to optimize the objective function in Lasso, including iterative shrinkage threshold algorithm (ISTA), fast iterative shrinkage‐thresholding algorithms (FISTA), coordinate gradient descent algorithm (CGDA), smooth L1 algorithm (SLA), and path following algorithm (PFA). Additionally, we also compare their convergence rate, as well as their potential strengths and weakness. This article is categorized under: Statistical Models > Linear Models Algorithms and Computational Methods > Numerical Methods Algorithms and Computational Methods > Computational Complexity
BibTeX
@inproceedings{zhao2022survey,
  author = {Yujie Zhao and Xiaoming Huo},
  title = {{A survey of numerical algorithms that can solve the Lasso problems}},
  booktitle = {Wiley},
  year = {2022},
  doi = {10.1002/wics.1602},
}
Figure