Regression Shrinkage and Selection via the Lasso

In linear regression we model an outcome $y$ as a weighted sum of $p$ predictors $x_1, x_2, \dots, x_p$ plus noise. Ordinary Least Squares (OLS) finds the weights $\hat{\beta}$ that minimize the sum of squared residuals. When $p$ is small relative to $n$ (the number of observations), this works well.

But in many real problems — genomics with thousands of genes, finance with hundreds of indicators, text with millions of word features — $p$ can rival or exceed $n$. OLS then has infinitely many perfect-fit solutions, all of them useless for prediction: the model memorizes noise instead of learning signal. Even when $p < n$, including irrelevant predictors inflates variance and makes the model fragile.

Before the Lasso, the standard remedy for overfitting was Ridge regression (Hoerl & Kennard, 1970). Ridge adds a penalty proportional to the sum of squared coefficients:

Ridge stabilizes predictions and reduces variance, but it never produces a sparse model. If you started with 1,000 gene expression features, Ridge gives you 1,000 shrunken coefficients — none zero, none dropped. Interpretation becomes a wall of small numbers with no clear answer to "which genes matter?"

Tibshirani's insight was deceptively simple: replace the squared L2 penalty with an L1 penalty — the sum of absolute values instead of squared values:

An equivalent way to state the Lasso is as a constrained optimization: minimize the sum of squared errors subject to $\sum_j |\beta_j| \leq t$. This constraint defines the feasible region — and its shape is the key to everything.

Think of a two-coefficient problem on a flat plane. The least-squares loss defines elliptical contours centered on the OLS solution — each contour is a set of $(\beta_1, \beta_2)$ values with the same total error.

Ridge's constraint $\beta_1^2 + \beta_2^2 \leq t$ is a circle. When the smallest ellipse that touches the circle makes contact, it almost always touches the smooth curve at a point where both coefficients are nonzero.

The Lasso's constraint $|\beta_1| + |\beta_2| \leq t$ is a diamond — a square rotated 45°, with sharp corners sitting right on the axes. When the loss ellipse expands until it just touches this diamond, it preferentially hits a corner, and at a corner one coordinate is exactly zero. That coefficient has been eliminated. In higher dimensions the diamond becomes a cross-polytope with far more corners than faces, so the probability of landing on a corner (a sparse solution) is even higher.

When the design matrix columns are orthonormal (each predictor is uncorrelated with the others and has unit variance), the Lasso solution has a beautiful closed form called soft thresholding:

As $\lambda$ decreases from a large value (where all coefficients are zero) toward zero (the OLS solution), coefficients "enter" the model one by one. The regularization path — the curve of each coefficient as a function of $\lambda$ — is piecewise linear for the Lasso, a remarkable property discovered by Efron et al. (2004) through the LARS algorithm.

This path reveals the story of variable importance: the first coefficient to become nonzero is the strongest predictor, the next is the second-strongest given the first, and so on. Cross-validation then picks the $\lambda$ that gives the best out-of-sample performance, yielding a principled sparse model.

The L1 penalty makes the objective non-smooth — there is no simple closed-form solution when predictors are correlated. The modern workhorse algorithm is coordinate descent: optimize one coefficient at a time while holding the others fixed.

For a single coefficient the subproblem is one-dimensional, and the solution is just the soft-thresholding formula applied to the partial residual. Cycling through all $p$ coefficients repeatedly converges to the global optimum because the objective is convex. Coordinate descent is remarkably fast — it handles millions of predictors in seconds — and is the engine behind the popular glmnet library (Friedman, Hastie, Tibshirani 2010).

The L1 penalty has a beautiful probabilistic interpretation. Placing an independent Laplace prior $p(\beta_j) \propto \exp(-\lambda|\beta_j|)$ on each coefficient and computing the MAP (maximum a posteriori) estimate is mathematically identical to solving the Lasso. The Laplace distribution is sharply peaked at zero with heavy tails — it encodes the belief that most coefficients should be zero, but the few that are nonzero can be large. Compare this with Ridge's Gaussian prior, which is smoothly peaked at zero and decays quickly — it believes coefficients are small but never exactly zero.

The three methods form a spectrum of discipline. OLS is fully permissive — use any coefficients you want. Ridge adds a smooth budget that shrinks everything proportionally. Lasso adds a sharp budget that eliminates the weakest contributors entirely. The interactive comparison below makes this concrete.

The Lasso is not perfect. It has two well-known limitations:

• Correlated predictors. When two features are highly correlated, Lasso arbitrarily picks one and zeros out the other. It doesn't "share credit" — it selects a representative from each correlated cluster rather than keeping the whole group.

• The p > n case. When predictors outnumber observations, Lasso can select at most $n$ variables, even if more are truly relevant.

These limitations motivated important extensions. The Elastic Net (Zou & Hastie, 2005) combines L1 and L2 penalties, inheriting Lasso's sparsity while handling correlated features gracefully. The Adaptive Lasso (Zou, 2006) assigns different penalty weights to each coefficient, achieving oracle properties. The Group Lasso (Yuan & Lin, 2006) selects or eliminates entire groups of related variables together.