The Least Absolute Shrinkage and Selection Operator (LASSO) was introduced by Tibshirani (1996). It is a regularization technique that performs both continuous shrinkage and automatic variable selection, producing sparse, interpretable models.
LASSO is particularly useful when:
The LASSO estimator is defined as the solution to the following penalized least squares problem:
\[ \hat{\beta}^{\text{lasso}} = \arg\min_{\beta} \left\{ \frac{1}{2n} \|y - X\beta\|_2^2 + \lambda \|\beta\|_1 \right\} \]
Expanding:
\[ \hat{\beta}^{\text{lasso}} = \arg\min_{\beta} \left\{ \frac{1}{2n} \sum_{i=1}^{n} \left( y_i - x_i'\beta \right)^2 + \lambda \sum_{j=1}^{p} |\beta_j| \right\} \]
where:
The equivalent constrained formulation is:
\[ \min_{\beta} \frac{1}{2n} \|y - X\beta\|_2^2 \quad \text{subject to} \quad \sum_{j=1}^{p} |\beta_j| \leq t \]
where \(t\) is in one-to-one correspondence with \(\lambda\).
The \(L_1\) ball \(\{\ \beta : \|\beta\|_1 \leq t\ \}\) is a diamond (in 2D) with corners on the coordinate axes. The contours of the RSS loss function are ellipses centered at the OLS solution. The constrained optimum occurs where the ellipse first touches the constraint region. Because the \(L_1\) ball has corners, this contact point is likely to occur at a corner, where one or more coordinates are exactly zero.
In contrast, the \(L_2\) ball (Ridge) is smooth — contact points generically have all coordinates nonzero.
The \(L_1\) norm is not differentiable at zero. The subdifferential of \(|\beta_j|\) is:
\[ \partial |\beta_j| = \begin{cases} \{+1\} & \text{if } \beta_j > 0 \\ \{-1\} & \text{if } \beta_j < 0 \\ [-1, +1] & \text{if } \beta_j = 0 \end{cases} \]
The optimality (KKT) condition for the LASSO is:
\[ -\frac{1}{n} x_j'(y - X\beta) + \lambda \cdot s_j = 0, \quad s_j \in \partial|\beta_j| \]
When \(\beta_j = 0\), this requires \(\left| \frac{1}{n} x_j'(y - X\beta) \right| \leq \lambda\), which is satisfiable — hence exact zeros are possible.
For orthonormal design (\(X'X = nI\)), the LASSO solution has a closed form via the soft-thresholding operator:
\[ \hat{\beta}_j = S_\lambda(\hat{\beta}_j^{\text{OLS}}) = \text{sign}(z_j)(|z_j| - \lambda)_+ \]
where \(z_j = \hat{\beta}_j^{\text{OLS}}\) and \((x)_+ = \max(0, x)\). Coefficients with \(|z_j| \leq \lambda\) are set exactly to zero; others are shrunk toward zero by \(\lambda\).
The standard algorithm for solving the LASSO is coordinate descent (Friedman, Hastie, Tibshirani, 2010):
Algorithm:
\[ \tilde{\beta}_j \leftarrow S_\lambda\left( \frac{1}{n} x_j'(y - X_{-j}\beta_{-j}) \right) \bigg/ \left( \frac{1}{n} x_j'x_j \right) \]
where \(X_{-j}\beta_{-j}\) is the partial residual excluding predictor \(j\).Key properties:
The LASSO regularization path traces the solutions \(\hat{\beta}(\lambda)\) as \(\lambda\) varies from \(\lambda_{\max}\) down to 0:
\[ \lambda_{\max} = \frac{1}{n} \|X'y\|_\infty = \max_j \left| \frac{1}{n} x_j'y \right| \]
This is the smallest \(\lambda\) for which all coefficients are zero. As \(\lambda\) decreases:
Efron et al. (2004) showed that the entire LASSO path can be computed efficiently using the LARS algorithm:
The computational cost is similar to a single OLS fit: \(O(np \cdot \min(n,p))\) for the entire path.
The standard approach is K-fold CV (typically \(K=10\)):
Alternatives to CV:
where \(\text{df}(\lambda) = |\{j : \hat{\beta}_j(\lambda) \neq 0\}|\) (number of nonzero coefficients).
Under the irrepresentable condition (a requirement on the correlation structure between relevant and irrelevant predictors):
\[ \|X_{\mathcal{S}^c}'X_{\mathcal{S}}(X_{\mathcal{S}}'X_{\mathcal{S}})^{-1} \text{sign}(\beta_{\mathcal{S}}^*)\|_\infty < 1 \]
the LASSO consistently selects the true support \(\mathcal{S} = \{j : \beta_j^* \neq 0\}\) as \(n \to \infty\).
The standard LASSO does not satisfy the oracle property in general. The adaptive LASSO (Zou, 2006) uses data-dependent weights and achieves:
Under restricted eigenvalue conditions, the LASSO achieves the near-minimax prediction error rate:
\[ \frac{1}{n}\|X(\hat{\beta} - \beta^*)\|_2^2 = O_P\left( s \frac{\log p}{n} \right) \]
where \(s = |\mathcal{S}|\) is the true sparsity level.
For the LASSO with fixed \(\lambda\) (Zou, Hastie, Tibshirani, 2007):
\[ \text{df}(\hat{\beta}^{\text{lasso}}) = E\left[ |\{j : \hat{\beta}_j \neq 0\}| \right] \]
An unbiased estimate of df is simply the number of nonzero coefficients.
Uses weighted penalties to achieve the oracle property:
\[ \min_{\beta} \frac{1}{2n}\|y - X\beta\|_2^2 + \lambda \sum_{j=1}^{p} w_j |\beta_j| \]
with weights \(w_j = 1/|\hat{\beta}_j^{\text{init}}|^\gamma\), where \(\hat{\beta}^{\text{init}}\) is a \(\sqrt{n}\)-consistent initial estimator (e.g., OLS or Ridge) and \(\gamma > 0\).
For grouped predictors (e.g., dummy variables from a factor), groups enter or leave the model together:
\[ \min_{\beta} \frac{1}{2n}\|y - X\beta\|_2^2 + \lambda \sum_{g=1}^{G} \sqrt{p_g} \|\beta_g\|_2 \]
where \(\beta_g\) is the subvector for group \(g\) and \(p_g\) its size.
Penalizes differences between adjacent coefficients (useful for ordered/spatial data):
\[ \min_{\beta} \frac{1}{2n}\|y - X\beta\|_2^2 + \lambda_1 \sum_{j=1}^{p} |\beta_j| + \lambda_2 \sum_{j=2}^{p} |\beta_j - \beta_{j-1}| \]
The \(L_1\) penalty extends naturally to generalized linear models. For example, the logistic LASSO:
\[ \min_{\beta} \left\{ -\frac{1}{n} \sum_{i=1}^{n} \left[ y_i x_i'\beta - \log(1 + e^{x_i'\beta}) \right] + \lambda \|\beta\|_1 \right\} \]
Similarly for Poisson regression, Cox proportional hazards, and other exponential family models. Coordinate descent adapts via iteratively reweighted least squares (IRLS) within each coordinate update.
A comparison of the two most common regularization approaches:
| LASSO (\(L_1\)) | Ridge (\(L_2\)) | |
|---|---|---|
| Penalty | \(\lambda \sum |\beta_j|\) | \(\lambda \sum \beta_j^2\) |
| Sparsity | Produces exact zeros | Shrinks toward zero, never exactly zero |
| Variable selection | Yes (built-in) | No |
| Correlated predictors | Tends to select one, discard others | Shrinks correlated predictors together |
| Best when | True model is sparse; many irrelevant features | Many correlated, relevant features |
| Unique solution | Not guaranteed when \(p > n\) | Always unique (\(X'X + \lambda I\) invertible) |
| Computational | Coordinate descent / LARS | Closed form: \((X'X + \lambda I)^{-1}X'y\) |
Elastic Net — when in doubt, combine both penalties:
\[ \min_{\beta} \frac{1}{2n}\|y - X\beta\|_2^2 + \lambda \left[ \alpha \|\beta\|_1 + \frac{1-\alpha}{2} \|\beta\|_2^2 \right] \]
with \(\alpha \in [0,1]\). The Elastic Net inherits sparsity from LASSO and the grouping effect from Ridge, making it robust in practice when the true model structure is unknown.