Lasso

Section of High-dimensional analysis, part of Statistical learning

Lasso

Type	Section
Taught in	High-dimensional analysis
Part	Statistical learning
Questions using it	3

Single-variable tests ignore the other explanatory variables. If the selected variables are also going to be used for prediction, the fit has to be joint: each coefficient is the association that remains after the others are in the model. Variable selection is a special case of model selection. Only two types of model are considered here: multiple linear regression for a continuous response, and logistic regression for a binary response. The hope is a small model that predicts well. With p large, exhaustive search over 2^p subsets can exceed a practical computation budget, and the normal equations may not have a unique solution. A penalty that can set coefficients to exact zeros does both shrinkage and selection in one convex problem.

Subset selection and shrinkage

Main article: Subset selection and shrinkage

One way of limiting overfitting is to penalise the magnitude of the parameters. Another, as with the Bayesian information criterion, is to penalise the number of parameters. Another way to choose a subset begins with a method of assessing predictive accuracy: the cross-validation PRESS statistic for a continuous response, or classical cross-validation for a nominal response. One then searches over all possible combinations of the available variables. With p explanatory variables the number of subsets is 2^p. For p=30 this is more than 10^9, and for p=100 about 10^{30}.

Greedy searches make a manageable sequence of comparisons. Forward selection adds one variable at a time. Backward selection removes one from an initially fitted model. That reduces the search, and it does not guarantee the best subset. A better training fit does not settle the prediction question. For nested least-squares models, training R^2 cannot decrease as variables are added. Selection therefore needs a criterion that accounts for complexity or evaluates predictions on observations excluded from the relevant fitting and selection steps.

Best subset selection fixes the number of selected variables at some value k<p and searches over this smaller domain. It can be viewed as a hard-constraint version of the information criterion, or as a method that uses an L^0 penalty, which counts the nonzero elements:

\lVert\beta\rVert_{L^0}=\#\{j:\beta_j\neq 0\}.

This is not formally a norm. Absolute homogeneity fails in general: \lVert a\beta\rVert_{L^0}\neq |a|\,\lVert\beta\rVert_{L^0} for most scalars a and vectors \beta.

Least squares, ridge, and the lasso objective

Main article: Least squares, ridge, and the lasso objective

For standard linear regression use Y=\beta_0+X^\top\beta+\epsilon with \beta=(\beta_1,\ldots,\beta_p)^\top the slopes, \beta_0 the constant, and \epsilon\sim\operatorname{N}(0,\sigma^2). The intercept and the error variance are present in every model of interest. They are not shrunk or removed. The maximum-likelihood solution is the least-squares solution

(\hat\beta_0,\hat\beta) =\arg\min_{\beta_0,\beta} \sum_{i=1}^{n}\Biggl(y_i-\beta_0-\sum_{j=1}^{p}\beta_j x_{ij}\Biggr)^2,

which has the inverse-based closed form above when the augmented design has full column rank.

Ridge regression, also called weight decay or Tikhonov regularisation (Hoerl and Kennard, 1970), is a long-standing shrinkage method. Standardise the predictors first: subtract each sample mean and divide by the sample standard deviation. Then add the sum of squared regression weights, an L^2 penalty. Do not run one \lambda on variables that live on different scales. Divide a variable by 1000 and its coefficient has to grow by 1000 to give the same fit. The same \lambda is then a different penalty, because a large coefficient dominates the sum.

(\hat\beta_0,\hat\beta) =\arg\min_{\beta_0,\beta} \Biggl\{ \sum_{i=1}^{n}\Biggl(y_i-\beta_0-\sum_{j=1}^{p}\beta_j x_{ij}\Biggr)^2 +\lambda\sum_{j=1}^{p}\beta_j^2 \Biggr\}.

Here \lambda controls the amount of shrinkage. It can be chosen manually or by optimising a measure of predictive accuracy such as cross-validation. Two layers of cross-validation are needed to both select such a parameter and estimate the accuracy of the resulting model. Ridge regression was introduced to improve regression for non-orthogonal predictors, those with substantial multicollinearity, where the slope estimates are unstable, with large confidence intervals and high sensitivity to individual observations. This is also seen as near-singularity of X^\top X. With centred y and standardised X, so that the intercept is \bar y,

\hat\beta_R=(X^\top X+\lambda I)^{-1}X^\top y.

Adding \lambda I reduces the condition number of the matrix to be inverted. If p>n then X^\top X is rank-deficient, so not invertible. It is positive semi-definite, so at least one eigenvalue is zero and the others are nonnegative. Adding \lambda I raises every eigenvalue by \lambda>0, making the matrix positive definite and invertible, and hence allowing a unique solution even when p>n.

Tibshirani (1996), building in part on Donoho and Johnstone (1994) and Breiman (1995), replaces the L^2 penalty by an L^1 penalty. The resulting estimator is the lasso, the least absolute shrinkage and selection operator:

(\hat\beta_0,\hat\beta) =\arg\min_{\beta_0,\beta} \Biggl\{ \sum_{i=1}^{n}\Biggl(y_i-\beta_0-\sum_{j=1}^{p}\beta_j x_{ij}\Biggr)^2 +\lambda\sum_{j=1}^{p}|\beta_j| \Biggr\}.

This is the Lagrangian equivalent of minimising the same sum of squares subject to \sum_j|\beta_j|\le t, with a corresponding constraint radius t. The correspondence need not be one-to-one: flat portions of the solution path and inactive constraints can give multiple parameter values for the same fit. The method aims to shrink some parameter values and set others to exactly zero, achieving both shrinkage and variable selection. With standardised data the solution for \hat\beta_0 is \bar y, and one then only needs to choose \beta_1,\ldots,\beta_p.

On the Bayesian page, a Laplace prior on the slopes has a posterior mode at this same L^1-penalised least-squares fit. The derivation here is the objective and the coordinate-wise solution, not the prior.

Why the L^1 penalty gives zeros

Main article: Why the L¹ penalty gives zeros

The ellipses of a least-squares cost are centred at the unpenalised estimate. The constraint sets are |\beta_1|+|\beta_2|\le t and \beta_1^2+\beta_2^2\le t^2. The penalised estimate is the point where the lowest contour still touches the constraint. The L^1 set is a diamond. A smooth ellipse tends to touch it at a corner, and a corner sets one coefficient to zero. The L^2 set is a disk. The ellipse meets the disk at a smooth point, and both coefficients stay nonzero. Sparsity depends on the penalty, the loss, and the data. High dimension alone does not force the right variables to be the ones selected.

The diamond does not force the optimum to a corner on every data set. It makes corners available over a range of loss contours, which is the mechanism for exact zeros. Ridge can have a zero coefficient through cancellation or symmetry. Its smooth penalty does not create a thresholding region around zero.

Soft-thresholding for orthonormal predictors

Main article: Soft-thresholding for orthonormal predictors

When X^\top X=I, the penalty separates across coordinates. For ridge, the derivative of (\beta_j-\hat\beta_j^{\mathrm{LS}})^2+\lambda\beta_j^2 is zero at

\hat\beta_j=\frac{\hat\beta_j^{\mathrm{LS}}}{1+\lambda}.

Every coefficient shrinks by the same factor. For the lasso, minimise (\beta_j-b)^2+\lambda|\beta_j| with b=\hat\beta_j^{\mathrm{LS}}. For \beta_j>0 the derivative is 2(\beta_j-b)+\lambda, zero at \beta_j=b-\lambda/2, which is positive only if b>\lambda/2. The negative side is symmetric. If |b|\le\lambda/2 the minimum is at 0. Hence

\hat\beta_j^{\mathrm{lasso}}=\operatorname{sign}(b)\bigl(|b|-\lambda/2\bigr)_+,

the soft-thresholding operator. Coefficients smaller than \lambda/2 in magnitude are set to zero, and the others are shrunk towards zero by \lambda/2. The factor \lambda/2, rather than \lambda, is the derivative of a square that was not written with a leading \tfrac12.

Best-subset selection with a penalty \lambda on \lVert\beta\rVert_{L^0} gives hard thresholding: keep b unchanged if |b|>\sqrt{\lambda} and set it to 0 otherwise. At |b|=\sqrt{\lambda}, both 0 and b minimise the criterion (\beta-b)^2+\lambda\,1_{\beta\neq 0}. The displayed rule chooses zero.

For example, with least-squares estimates (3,-1.5,0.8,-0.3,0.1) and \lambda=1: ridge gives (1.5,-0.75,0.4,-0.15,0.05), all nonzero; the lasso gives (2.5,-1.0,0.3,0,0); hard thresholding gives (3,-1.5,0,0,0). The soft-threshold also shows the lasso’s bias: even a coefficient as large as 3 is shrunk by \lambda/2.

Choosing \lambda

Main article: Choosing the lasso penalty

The penalty determines a trade-off, so it must be chosen for an objective. Prediction-oriented tuning can use cross-validation with the entire fitting procedure repeated within each fold. The broader family \lambda\sum_j|\beta_j|^q connects several familiar penalties: q=2 gives ridge, q=1 gives the lasso, and counting nonzero coefficients gives the L^0 formulation. The mathematical appeal of q=1 is concrete: it retains convexity while introducing a corner at zero. For 0<q<1, the penalty is nonconvex. These geometric facts do not by themselves select a penalty value (Tibshirani, 1996; Frank and Friedman, 1993).

A path algorithm computes fits over a range of penalties. Each fixed-\lambda least-squares lasso problem is convex. Under the usual nondegeneracy conditions, coefficients vary piecewise linearly with \lambda, with changes when variables enter or leave the active set. Calling the path itself convex is a different claim. Efficient path algorithms exploit the piecewise-linear structure. Their workload still depends on the design and the number of changes.

Read a coefficient path as a sequence of fitted models, not a ranking of biological importance. A coefficient can change sign, reach zero, or later re-enter. A seeded sparse regression produces one such path, together with a ten-fold cross-validation curve and its reported standard errors. The curve selects a prediction trade-off. It does not certify support recovery.

Extensions

Main article: Extensions of the lasso

The lasso can also be used with a generalised linear model, one with g(\mu(x))=x^\top\beta where \mu(x)=\mathbb{E}(Y\mid X=x), g is monotone, and Y has a distribution from the exponential family. In particular it applies to logistic regression: minimise the negative log-likelihood plus \lambda\sum_j|\beta_j|, with \lambda chosen by cross-validation of the binomial deviance.

The lasso is a shrinkage method. An L^1 penalty constrains the overall coefficient size, but with correlated predictors an individual coefficient need not be smaller in magnitude than its least-squares counterpart, so the estimator is biased. One question is whether this bias can be reduced, at least as n grows.

Assume a lasso is fit with \lambda chosen by cross-validation. This typically removes many variables. Refitting an unpenalised model on the same data the lasso selected is biased. A sample the lasso did not see is the clean check. Only about half the data is then used for each of selection and fitting.

Another option, proposed by Zou (2006), is the adaptive lasso

(\hat\beta_0,\hat\beta) =\arg\min_{\beta_0,\beta} \Biggl\{ \sum_{i=1}^{n}\Biggl(y_i-\beta_0-\sum_{j=1}^{p}\beta_j x_{ij}\Biggr)^2 +\lambda\sum_{j=1}^{p} w_j|\beta_j| \Biggr\}.

The displayed version uses w_j=1/|\tilde\beta_j| from a pilot fit. The general adaptive lasso permits powers |\tilde\beta_j|^{-\gamma} with \gamma>0. Large pilot coefficients receive less shrinkage. A zero pilot requires an explicit rule, such as exclusion or a stated stabilisation. Zou (2006, Theorem 2) gives oracle properties under assumptions on the design, a sufficiently accurate pilot, and the rate of the penalty sequence. These are not guarantees for any cross-validated penalty or any marginal-regression pilot, particularly with correlated predictors and growing dimension. Selection consistency and coefficient consistency must be checked under the stated asymptotic regime.

Used in

Taught in High-dimensional analysis
Also used in Bayesian linear regression · Networks in practice · Graphical models
Questions that use it (3) — Soft threshold · A tempting wrong turn (answer) · Selection in many dimensions
All 9 questions on High-dimensional analysis