Image: Carol M. Highsmith, public domainWhat the lasso does to a regression
A study measures the activity of 20,000 genes in 200 patients and asks which genes predict whether a tumour will respond to a drug. Ordinary regression cannot even begin: with more variables than observations there are infinitely many sets of coefficients that fit the data perfectly, and all of them are useless. The lasso, a method Robert Tibshirani published in 1996, returns a regression with a few dozen nonzero coefficients and the rest exactly zero. This article explains how a single change to the least-squares criterion produces that.
Least squares and a penalty
Ordinary least squares chooses the coefficients \(\beta_1, \ldots, \beta_p\) that make the sum of squared residuals as small as possible:
\[ \sum_{i=1}^{n} \left( y_i - \beta_0 - \sum_{j=1}^{p} \beta_j x_{ij} \right)^2. \]When \(p\) is large relative to \(n\), this fits noise as readily as signal, and the coefficients become large and erratic. The classical remedy, ridge regression from 1970, adds a penalty that grows with the squared size of the coefficients, \(\lambda \sum_j \beta_j^2\), where \(\lambda\) is a number you choose. A large \(\lambda\) pulls every coefficient towards zero. None of them reaches it.
The lasso changes the square to an absolute value:
\[ \sum_{i=1}^{n} \left( y_i - \beta_0 - \sum_{j=1}^{p} \beta_j x_{ij} \right)^2 + \lambda \sum_{j=1}^{p} |\beta_j|. \]The name is an acronym, least absolute shrinkage and selection operator, and the two nouns are the two things it does. It shrinks, as ridge does. It also selects: as \(\lambda\) increases, coefficients hit zero exactly and stay there, so the model drops variables. With 20,000 genes and a well-chosen \(\lambda\), most coefficients are zero and the model names the handful that are not.
Why the absolute value gives zeros
The cleanest way to see it is a picture with two coefficients. The penalized problem is equivalent to minimizing the residual sum of squares subject to the constraint that the penalty is below some budget. For ridge the constraint \(\beta_1^2 + \beta_2^2 \le t\) is a disc. For the lasso the constraint \(|\beta_1| + |\beta_2| \le t\) is a diamond, a square standing on its corner, with its corners on the axes.
The residual sum of squares is smallest at the ordinary least-squares solution and grows in ellipses around it. The constrained solution is the point where the expanding ellipse first touches the constraint region. A disc has no corners, so the ellipse touches it at some point where both coefficients are nonzero. A diamond has corners on the axes, and an ellipse expanding towards it is likely to hit a corner first, and at a corner one coefficient is exactly zero. In higher dimensions the diamond becomes a shape with many corners, edges, and faces lying in the coordinate planes, and the solution lands on one of them, with all the coefficients of that face zeroed out.
There is a one-line algebraic version. If the predictors are uncorrelated and standardized, the lasso coefficient is obtained from the least-squares coefficient \(\hat{\beta}_j\) by soft thresholding:
\[ \hat{\beta}_j^{\text{lasso}} = \operatorname{sign}(\hat{\beta}_j)\,\big(|\hat{\beta}_j| - \lambda\big)_{+}, \]where the subscript plus means "or zero if negative". Every coefficient is moved towards zero by the same amount \(\lambda\), and the ones that were smaller than \(\lambda\) to begin with are set to zero. Ridge, by contrast, multiplies every coefficient by the same factor less than one, which makes small coefficients smaller without ever removing them.
Choosing the penalty
The lasso produces not one model but a path: \(\lambda\) very large gives the empty model with every coefficient zero, and as \(\lambda\) falls variables enter one at a time until at \(\lambda = 0\) the ordinary least-squares fit is recovered, where it exists. The usual way to choose a point on the path is cross-validation, the subject of Unit 13 of the Statistics Masterclass: fit the path on nine tenths of the data, measure the prediction error on the held-out tenth, rotate, and pick the \(\lambda\) with the smallest error. A common refinement picks the largest \(\lambda\) whose error is within one standard error of the minimum, on the grounds that a simpler model that predicts almost as well is to be preferred.
Computing the whole path used to be expensive. In 2004 Efron, Hastie, Johnstone, and Tibshirani showed with the least angle regression algorithm that the path is piecewise linear and can be computed about as fast as a single least-squares fit, and the coordinate descent algorithms that followed made fitting a lasso to a million variables routine.
What it costs
Shrinkage is bias. The lasso's nonzero coefficients are smaller in magnitude than the truth, because every coefficient paid the toll of \(\lambda\) on the way in, and the standard practice is to use the lasso to select the variables and then refit least squares on the selected set if unbiased estimates are wanted. When several predictors are highly correlated, the lasso tends to pick one of them arbitrarily and zero the others, which is awkward when they are genes in the same pathway; the elastic net of 2005 mixes the lasso and ridge penalties to let correlated predictors enter together. And a p-value for a lasso coefficient is a hard problem, because the same data chose the variable and estimated its effect; the knockoff method of Rina Foygel Barber and Emmanuel Candès, the research spotlight of Unit 16, is one answer.
Against those costs stands the fact that the lasso made regression possible where it had been impossible. Tibshirani's paper, Regression Shrinkage and Selection via the Lasso, appeared in the Journal of the Royal Statistical Society in 1996 and is on JSTOR; the textbook treatment he wrote with Trevor Hastie and Jerome Friedman, and the gentler An Introduction to Statistical Learning, are both free to download.
Unit 14 of the Statistics Masterclass derives soft thresholding, draws the diamond and the circle, and traces the lasso path on the prostate cancer data of the original papers, which are the dataset of the week. Tibshirani is the unit's research spotlight. If you have not met cross-validation, the article on the bootstrap introduces the resampling idea it rests on.


