A Survey of Numerical Algorithms that can Solve the Lasso Problems

Yujie Zhao, Xiaoming Huo

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 the 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.

Introduction

The Least Absolute Shrinkage and Selection Operator (Lasso) has become a cornerstone of modern statistical modeling, particularly in high-dimensional settings where variable selection and regularization are paramount. By adding an $\ell_1$ penalty to the least squares objective, Lasso encourages sparsity in the estimated coefficients. However, this mathematical elegance comes with a computational challenge: the $\ell_1$ norm (the sum of absolute values) is non-differentiable at zero.

Comparison between convex and non-convex functions

As illustrated in the comparison between convex and non-convex functions, Lasso remains a convex optimization problem, which guarantees that any local minimum is a global minimum. However, the "kink" at the origin prevents the use of standard calculus-based optimization. This review explores the numerical engines that have been developed to solve this specific optimization problem efficiently.

Numerical Optimization Algorithms

We categorize and analyze five representative algorithms that address the non-smooth nature of the Lasso objective.

Summary of Lasso optimization algorithms and their convergence rates

1. Iterative Shrinkage-Thresholding Algorithm (ISTA)

ISTA is a first-order proximal gradient method. It simplifies the optimization by using a quadratic approximation of the smooth part of the objective function (the least squares term) at each step. The non-differentiable $\ell_1$ term is then handled using a "soft-thresholding" operator, which effectively sets small coefficients to zero.

2. Fast Iterative Shrinkage-Thresholding Algorithm (FISTA)

FISTA is an "accelerated" version of ISTA. It incorporates a momentum term based on Nesterov’s accelerated gradient method, using information from the previous two iterations to inform the current update. This simple modification dramatically improves the theoretical convergence rate from $O(1/k)$ to $O(1/k^2)$ without significantly increasing the computational cost per iteration.

3. Coordinate Gradient Descent Algorithm (CGDA)

CGDA is the algorithmic foundation for popular software packages like glmnet. Instead of updating all coefficients simultaneously, it optimizes one coefficient at a time while holding the others fixed. It cycles through all variables until the entire set of coefficients converges. This approach is particularly effective for sparse problems where many updates are computationally trivial.

4. Smooth L1 Algorithm (SLA)

SLA takes a different approach by approximating the non-differentiable $\ell_1$ penalty with a smooth, twice-differentiable surrogate function, such as a log-sum-exp approximation. While this allows for the use of standard second-order optimization methods, the approximation itself introduces an error that can prevent the algorithm from reaching the high-precision convergence rates of accelerated methods like FISTA.

5. Path Following Algorithm (PFA)

PFA exploits the fact that the Lasso solution is "piecewise linear" with respect to the regularization parameter $\lambda$. It attempts to trace the entire regularization path by finding the specific "knots" where the set of non-zero coefficients changes. While mathematically elegant, it can be computationally expensive and may fail to recover the correct support set in certain general cases.

Comparative Analysis of Convergence and Complexity

The following table summarizes the theoretical performance of these algorithms. FISTA is identified as the most robust performer due to its superior convergence rate.

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)$ (up to $O(np^3)$)

Note: $k$ represents the number of iterations, $p$ the number of covariates, and $n$ the number of observations.

Key Insights

  • Momentum Acceleration: The transition from ISTA to FISTA demonstrates that incorporating momentum can improve the convergence rate from $O(1/k)$ to $O(1/k^2)$ without increasing per-iteration complexity.
  • Smoothing Approximation: While SLA simplifies the problem by making it differentiable, the inherent approximation error limits its convergence rate relative to the original objective.
  • Practical Efficiency of CGDA: Despite its $O(1/k)$ theoretical rate, CGDA is often the fastest in practice for high-dimensional sparse data due to the low cost of coordinate-wise updates.
  • Unpredictability of PFA: PFA is theoretically elegant but can fail to identify the correct support set in certain conditions, and its worst-case complexity remains poorly bounded.

Conclusion

Selecting the appropriate algorithm for Lasso depends on the specific requirements of the dataset and the desired precision. FISTA remains the theoretical leader due to its superior convergence rate. Future research may further explore the bounds of Path Following Algorithms and the integration of automated hyperparameter tuning within these optimization frameworks.

Summary updated

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 the 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.
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