Lasso Regression

1 Fundamentals of Lasso Regression

1.1 Definition and Objective Function

Lasso regression, short for Least Absolute Shrinkage and Selection Operator, is a linear regression method that adds an L1 penalty to the ordinary least squares (OLS) objective function. The goal is to minimize the sum of squared residuals plus a penalty proportional to the sum of the absolute values of the coefficients. The objective function is:

\[

\min_{\beta} \left\{ \frac{1}{2n} \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p} \beta_j x_{ij})^2 + \lambda \sum_{j=1}^{p}	\beta_j	\right\}

\]

where \(\lambda \ge 0\) is a tuning parameter controlling the strength of the penalty.

1.1.1 Relationship with Ordinary Least Squares

When \(\lambda = 0\), the lasso objective reduces to ordinary least squares (OLS) estimation. As \(\lambda\) increases, the penalty term forces some coefficients to shrink toward zero. Unlike OLS, lasso can set coefficients exactly to zero, thereby performing automatic variable selection.

1.1.2 L1 Penalty Term and Its Geometric Interpretation

The L1 penalty \(\lambda \sum	\beta_j	\) creates a diamond‑shaped constraint region in parameter space (in two dimensions, a rhombus). The OLS solution is the point that minimizes the residual sum of squares. The lasso solution is the point where the elliptical contours of the residual sum of squares first touch the L1 constraint region. Because the constraint region has corners, the tangency point often occurs on an axis, forcing some coefficients to zero.

1.2 History and Motivation

Lasso was introduced by Robert Tibshirani in a 1996 paper titled “Regression Shrinkage and Selection via the Lasso.” It was motivated by the need for a method that could both shrink coefficients (like ridge regression) and perform variable selection (like subset selection) in a continuous, stable fashion.

1.2.1 Limitations of Ridge Regression

Ridge regression uses an L2 penalty (\(\lambda \sum \beta_j^2\)), which shrinks coefficients toward zero but never sets them exactly to zero. In high‑dimensional or noisy settings, ridge retains all predictors, making interpretation difficult when many are irrelevant.

1.2.2 The Need for Sparse Models

In fields like genomics, economics, and signal processing, researchers often face data with many predictors but only a few believed to be relevant. Subset selection (e.g., best‑subset or stepwise) is unstable and computationally expensive. Lasso provides a convex optimization approach to sparse model fitting with efficient algorithms.

1.3 Comparison with Other Regularization Methods

1.3.1 Ridge Regression (L2 Penalty)

Ridge adds an L2 penalty \(\lambda \sum \beta_j^2\), which shrinks coefficients proportionally but does not perform variable selection. It handles correlated predictors better than lasso (coefficients of correlated variables tend to be shrunk together). Lasso, by contrast, selects one variable from a correlated group and sets others to zero.

1.3.2 Elastic Net (Combination of L1 and L2)

Elastic net combines L1 and L2 penalties: \(\lambda_1 \sum	\beta_j	+ \lambda_2 \sum \beta_j^2\). It retains the variable selection property of lasso while encouraging grouping of correlated predictors. Elastic net is particularly useful when the number of predictors \(p\) is much larger than the sample size \(n\) and when predictors are highly correlated.

2 Mathematical Formulation and Properties

2.1 Lagrangian Form and Constraint Formulation

The lasso problem can be expressed in two equivalent ways. The Lagrangian form is given above. An equivalent constrained form is:

\[

\min_{\beta} \frac{1}{2n} \sum_{i=1}^{n} (y_i - \beta_0 - \sum_{j=1}^{p} \beta_j x_{ij})^2 \quad \text{subject to} \quad \sum_{j=1}^{p}	\beta_j	\le t

\]

where \(t\) is a bound on the L1 norm. The tuning parameter \(\lambda\) in the Lagrangian form corresponds inversely to \(t\).

2.1.1 Dual Problem and Tuning Parameter λ

The Lagrange multiplier \(\lambda\) is the parameter that controls the trade‑off between fit and sparsity. Larger \(\lambda\) yields more shrinkage and more zero coefficients. The dual problem involves maximizing a concave function; the solution path as \(\lambda\) varies is piecewise linear.

2.1.2 Solution Path and Piecewise Linear Behavior

The lasso solution \(\hat{\beta}(\lambda)\) changes linearly as \(\lambda\) decreases, except at a finite set of “knots” where variables enter or leave the active set. This piecewise linear path is the basis for efficient algorithms like least angle regression (LARS).

2.2 Subgradient and Optimality Conditions

Since the L1 norm is not differentiable at zero, optimality conditions are expressed using subgradients.

2.2.1 Subgradient of the L1 Norm

For \(\beta_j \neq 0\), the subgradient of \(	\beta_j	\) is \(\operatorname{sign}(\beta_j)\). For \(\beta_j = 0\), the subgradient is any value in \([-1, 1]\).

2.2.2 KKT Conditions for Lasso

The Karush–Kuhn–Tucker (KKT) conditions for lasso are:

For each coefficient \(j\):

• If \(\hat{\beta}_j \neq 0\), then \(\frac{1}{n} \mathbf{x}_j^\top (\mathbf{y} - \mathbf{X}\hat{\beta}) = \lambda \operatorname{sign}(\hat{\beta}_j)\).

- If \(\hat{\beta}_j = 0\), then \(\left	\frac{1}{n} \mathbf{x}_j^\top (\mathbf{y} - \mathbf{X}\hat{\beta}) \right	\le \lambda\).

These conditions characterize the solution and are used in numerical algorithms.

2.3 Feature Selection and Sparsity

2.3.1 How Coefficients Are Shrunk to Zero

The L1 penalty creates a singularity at zero. For a given predictor, if its correlation with the current residual is smaller than \(\lambda\), then its coefficient stays at zero. As \(\lambda\) decreases, predictors with sufficiently strong correlation enter the active set. Continuous shrinkage occurs for nonzero coefficients.

2.3.2 Degrees of Freedom in Lasso

For a fixed \(\lambda\), the degrees of freedom of the lasso fit is approximately the number of nonzero coefficients (the active set size). More precisely, the unbiased estimate of degrees of freedom is the number of nonzero coefficients, provided the model is linear and the predictors are not too correlated. This property aids in model selection using information criteria.

3 Estimation Algorithms

3.1 Coordinate Descent

Coordinate descent is the most widely used algorithm for lasso due to its simplicity and speed, especially for large \(p\).

3.1.1 Univariate Soft-Thresholding Update

For a single coefficient \(\beta_j\) with all others fixed, the update is:

\[ \hat{\beta}_j = S\left( \frac{1}{n} \mathbf{x}_j^\top \mathbf{r}_{(-j)}, \lambda \right) \]

where \(\mathbf{r}_{(-j)}\) is the partial residual (excluding variable \(j\)), and \(S(z, \gamma) = \operatorname{sign}(z) \max(	z	- \gamma, 0)\) is the soft‑thresholding operator.

3.1.2 Cyclic Coordinate Descent Procedure

The algorithm cycles through all coefficients, updating each with the soft‑thresholding formula. This is repeated until convergence. For a decreasing sequence of \(\lambda\) values, the solution for a larger \(\lambda\) is used as a warm start for the next smaller \(\lambda\), dramatically speeding up the computation.

3.2 Least Angle Regression (LARS)

LARS is a forward stagewise algorithm that can be modified to compute the entire lasso solution path efficiently.

3.2.1 Forward Stagewise Relationship

Forward stagewise regression makes small incremental updates to the coefficient of the predictor most correlated with the residual. LARS is a faster variant that takes larger steps while maintaining a equiangular direction among active predictors.

3.2.2 LARS Algorithm for Lasso

The LARS algorithm is adapted for lasso by checking when a coefficient crosses zero; if that happens, the corresponding variable is removed from the active set. The resulting algorithm, known as LARS‑Lasso, produces the full piecewise linear solution path in \(O(p^3 + np^2)\) time for \(p\) predictors, though coordinate descent is often preferred for very large \(p\).

3.3 Stochastic and Proximal Methods

3.3.1 Proximal Gradient Descent

Proximal gradient methods handle the non‑smooth L1 penalty by alternating between a gradient step on the smooth part (residual sum of squares) and a proximal operator (soft‑thresholding). This approach is useful when \(n\) or \(p\) is extremely large and stochastic or incremental updates are desired.

3.3.2 Alternating Direction Method of Multipliers (ADMM)

ADMM decomposes the lasso problem into subproblems that can be solved in parallel. It introduces an auxiliary variable to separate the differentiable and non‑differentiable parts, then iteratively updates primal and dual variables. ADMM is suitable for distributed computing and large‑scale datasets.

4 Tuning Parameter Selection

4.1 Cross-Validation

Cross‑validation is the most common method for choosing \(\lambda\).

4.1.1 K-Fold Cross-Validation

The data are split into \(K\) folds (typically 5 or 10). For each fold, the model is trained on the remaining \(K-1\) folds for a sequence of \(\lambda\) values, and the prediction error is computed on the held‑out fold. The optimal \(\lambda\) is the one minimizing the average cross‑validated error.

4.1.2 One-Standard-Error Rule

To select a simpler model, the one‑standard‑error rule chooses the largest \(\lambda\) within one standard error of the minimum cross‑validated error. This penalty value yields a sparser model whose performance is statistically indistinguishable from the best.

4.2 Information Criteria

4.2.1 Akaike Information Criterion (AIC)

AIC is defined as \(-2\log L + 2k\), where \(L\) is the likelihood and \(k\) the degrees of freedom. For lasso, using the active set size as \(k\), AIC can be computed for each \(\lambda\) to select a model. It tends to favor larger models compared to BIC.

4.2.2 Bayesian Information Criterion (BIC)

BIC uses \(-2\log L + k\log n\), imposing a larger penalty for model complexity. Consequently, BIC often selects sparser models. It is particularly useful when \(n\) is large relative to \(p\).

4.3 Stability Selection

Stability selection is a resampling‑based technique that enhances variable selection consistency.

4.3.1 Subsampling and Selection Probabilities

The data are repeatedly subsampled (e.g., 100 times), and lasso is fitted to each subsample across a range of \(\lambda\). For each variable, the selection probability (proportion of subsamples where its coefficient is nonzero) is recorded.

4.3.2 Threshold Selection

Variables with selection probabilities exceeding a pre‑specified threshold (e.g., 0.8 or 0.9) are considered “stable” and included in the final model. This approach controls the expected number of false positives.

5 Extensions and Variants

5.1 Adaptive Lasso

Adaptive lasso modifies the penalty to achieve the oracle property (asymptotically equivalent to knowing the true set of relevant variables).

5.1.1 Weighted Penalties for Oracle Properties

The objective becomes \(\sum_{j} w_j	\beta_j	\), where weights \(w_j\) are typically \(1/	\tilde{\beta}_j	^\gamma\) for some \(\gamma > 0\), with \(\tilde{\beta}_j\) an initial consistent estimate (e.g., OLS or ridge). This assigns heavier penalties to unimportant variables.

5.1.2 Two-Step Estimation Procedure

First, obtain initial coefficient estimates \(\tilde{\beta}\) (e.g., via OLS or ridge). Second, solve the weighted lasso with \(w_j = 1/	\tilde{\beta}_j	^\gamma\). The adaptive lasso selects variables consistently and has the same bias order as the lasso.

5.2 Group Lasso

Group lasso penalizes predefined groups of variables, encouraging either all variables in a group to be zero or all nonzero.

5.2.1 Penalizing Groups of Variables

The objective uses an L2 penalty on each group: \(\lambda \sum_{g} \sqrt{p_g} \| \beta_g \|_2\), where \(p_g\) is the group size. This norm induces group sparsity.

5.2.2 Application to Categorical Predictors

Categorical predictors with multiple levels (dummy variables) naturally form groups. Group lasso can select or drop entire categorical variables rather than individual levels.

5.3 Fused Lasso

Fused lasso penalizes both the coefficients and their successive differences, encouraging local constancy.

5.3.1 Penalty on Successive Coefficient Differences

The objective adds a term \(\lambda_1 \sum_{j=1}^{p}	\beta_j	+ \lambda_2 \sum_{j=2}^{p}	\beta_j - \beta_{j-1}	\). The second term encourages adjacent coefficients to be equal.

5.3.2 Applications in Signal Processing and Genomics

Fused lasso is used for detecting changepoints in time‑series data, smoothing signals, and identifying genomic segments with equal copy number variations.

5.4 Sparse Multivariate Lasso

5.4.1 Lasso for Multiple Response Variables

When there are \(q\) correlated response variables, the multivariate lasso minimizes the Frobenius norm of residuals plus an L1 penalty on a matrix of coefficients (or L2,1 norm for joint sparsity).

5.4.2 Joint Feature Selection

The regularization term can be designed to select the same set of predictors for all responses (e.g., \(\sum_j \|\beta_j\|_2\)), promoting a common support across tasks.

6 Applications and Practical Considerations

6.1 High-Dimensional Regression

Lasso excels when the number of predictors \(p\) exceeds the sample size \(n\), a regime where OLS fails because the design matrix is singular.

6.1.1 When p >> n

In such settings, lasso can still produce a unique solution under certain sparsity assumptions. The L1 regularization ensures that only \(n\) or fewer coefficients become nonzero, making the model identifiable.

6.1.2 Gene Expression and Genomic Data

A classic application is in genomics, where the number of genes (predictors) can be tens of thousands while the number of patient samples may be only a few hundred. Lasso is used to identify a small set of genes associated with a disease outcome.

6.2 Variable Selection in Linear Models

6.2.1 Parsimonious Model Building

By automatically setting irrelevant coefficients to zero, lasso produces models that are easier to interpret and less prone to overfitting. It is often used as a screening tool to select a subset of variables for further analysis.

6.2.2 Interpretability in Econometrics

In econometric studies with many potential predictors (e.g., macroeconomic indicators), lasso helps identify the most influential factors while providing a sparse, interpretable model.

6.3 Software Implementation

6.3.1 R (glmnet Package)

The glmnet package in R is a fast implementation using coordinate descent. It supports linear, logistic, multinomial, Poisson, and Cox models with elastic net penalties. The function cv.glmnet provides built‑in cross‑validation.

6.3.2 Python (scikit-learn, statsmodels)

In Python, sklearn.linear_model.Lasso and sklearn.linear_model.LassoCV (with cross‑validation) are widely used. The statsmodels library also includes lasso via statsmodels.regression.linear_model.OLS with regularization.

6.3.3 MATLAB and Other Platforms

MATLAB offers lasso in the Statistics and Machine Learning Toolbox. Other languages (Julia, C++) have libraries such as GLMNet.jl or custom implementations.

6.4 Limitations and Caveats

6.4.1 Bias in Coefficient Estimates

The L1 penalty shrinks nonzero coefficients toward zero, introducing bias. This bias can reduce prediction accuracy for large coefficients, though it often lowers overall variance. Extensions like the relaxed lasso (two‑stage fitting) or the adaptive lasso mitigate this issue.

6.4.2 Correlation among Predictors

When predictors are highly correlated, lasso tends to select only one from the group and ignores the others. This can be unstable and may miss important predictors. Elastic net or group lasso are better choices in such scenarios.

6.4.3 When Lasso Fails (e.g., Non-Linear Relationships)

Lasso assumes a linear relationship between predictors and response. It may perform poorly if the true relationship is non‑linear, unless basis expansions (polynomials, splines) are used. Additionally, lasso cannot handle interactions automatically; these require manual inclusion or methods like Basis‑expansion lasso.