Lasso and sparsity

A clinic measures forty blood markers on each of thirty patients and wants to predict one outcome. A straight line with forty coefficients can pass through all thirty rows with no error at all, because it has more dials than there are rows to constrain them. A model that reproduces its table exactly and predicts the next patient badly is the plainest case of overfitting in this chapter.

The lasso is a cousin of ridge that answers a different question. Ridge shrinks every coefficient and keeps all of them, while the lasso shrinks and also deletes, driving some coefficients to exactly zero [S:49:254]. The difference comes from the shape of the charge rather than from any new machinery. !The ellipses are level sets of the residual sum of squares around the least-squares estimate, and the shaded region is what each charge allows. In (a) the ridge circle is met away from both axes, where both coefficients are nonzero; the least-squares fit is the open square outside the region. In (b), with the same error contours, the lasso diamond is met at a corner on an axis, where the second coefficient is exactly zero. Status: schematic.

!Three standardized, uncorrelated inputs whose single-input fits are 3, 1 and −0.4. At λ = 1 the lasso subtracts 0.5 from each fit and stops at zero, so the third input is deleted, while ridge divides by 2 and leaves it at −0.2. At λ = 2 the lasso deletes the second input, which sits exactly at the threshold. Status: schematic.

Only the exponent changed, and the behaviour changed with it, because the penalty is now a sum of absolute values, and such a sum has a corner at zero which the squared version lacks [S:49:255]. A corner gives the fit a place to land exactly, so a coefficient can be set to zero and remain there.

Think of a budget rather than a price, because the charge confines the coefficients to a region. The region is a circle for ridge, since the squared charge bounds the sum of squares, and a diamond for the lasso, since the absolute charge bounds the sum of absolute values [S:49:254]. The fit expands its error contours, the curves along which the residual sum of squares is constant, until they touch that region. The diamond's corners sit on the axes, and a corner is a place where one coordinate is zero, so the touching point often puts one coefficient exactly at zero [S:49:255].

In higher dimensions the diamond becomes a polytope, a flat-sided solid with many corners, edges and faces, and the same tangency argument still holds. The extra corners and faces are extra opportunities for coefficients to be exactly zero, and many can vanish at once. What fails to generalise is the drawing, not the geometry [S:49:255] [S:64:91].

Worked example. The cleanest case gives each coefficient one standardized input, with no correlation between inputs. There the lasso answer is a subtraction: take half the charge away from each least-squares fit, and stop at zero whenever the result would cross it [S:49:258]. The half appears because the squared error's slope is twice the residual while the absolute charge has slope one. Three inputs have single-input fits of 4, 2 and $-1$.

With λ = 2, half the charge is 1, so the three coefficients become 3, 1 and 0. The third input is deleted rather than shrunk, because its fit was no larger than half the charge.

Compare that with ridge on the same three inputs. Ridge divides each fit by one plus the charge. At λ = 2 each coefficient is divided by three, so the first fit falls to four thirds and the second to two thirds, while the third input keeps a small negative weight of minus one third instead of disappearing entirely. Neither answer is wrong, and the difference between them is the difference between compressing a model and deciding what belongs in it.

The operation has a name. Shrinking by a fixed amount and stopping at zero is soft-thresholding, and it explains why the lasso selects inputs while ridge merely compresses them [S:49:258]. Raising the charge usually deletes inputs in order of how weakly they were supported, but the path need not be nested: with correlated inputs a coefficient can leave and return. The curve records where each input enters or leaves the set, and that order is a rough ranking, not a one-way filter [S:49:253].

The path is the object to inspect rather than any single value of the charge, since sweeping λ upward produces a sequence of models. The order of entry is a rough ranking of how much each input adds, which is often more useful than the coefficients of one fit.

There is also a probabilistic reading of the two charges. A squared penalty matches a prior belief, meaning a distribution stated before the table is seen, that coefficients are spread around zero in a bell shape, while an absolute penalty matches a prior with a sharp peak at zero [S:49:259]. The lasso therefore begins from the expectation that many coefficients are exactly zero, and the table then moves the ones it can support away from that peak.

The result is a sparse model: most coefficients are zero and a few survivors carry the prediction. That is a gain in interpretation, and sometimes a gain in accuracy. When a handful of inputs drives the outcome and the rest are noise, the lasso tends to beat ridge, while ridge tends to win when many inputs each contribute a little [S:49:256].

The idea has a cost. Neither method dominates the other, and which one wins depends on how many inputs truly matter, a number nobody knows in advance [S:49:256]. A lasso model also reports which inputs survived, not which inputs caused the outcome. Two inputs carrying the same information leave the fit to choose between them, and that choice is not a claim about which of the two is doing the work.

The formal statement. The lasso returns the coefficient vector that minimises

$$\mathrm{RSS}+\lambda \sum _{j=1}^p\left|{\beta }_j\right|,$$

with the intercept outside the charge [S:49:253]. The same estimate solves a constrained problem: keep the absolute weights inside a budget $s$ and make the residual sum of squares as small as possible [S:49:254]. There is no closed form in general. There is one when the input columns are standardised and uncorrelated, and that case is enough to show the mechanism.

The derivation. With standardised, uncorrelated columns, the objective splits into one term per coefficient, each of the form $({\beta }_j-{\hat{\beta }}_j{)}^2+\lambda |{\beta }_j|$, where ${\hat{\beta }}_j$ is that input's own least-squares fit. Minimise each term alone. Where the coefficient is positive the derivative is $2({\beta }_j-{\hat{\beta }}_j)+\lambda$, which vanishes at ${\hat{\beta }}_j-\lambda /2$. That point lies in the positive region exactly when the fit exceeds half the charge. Below that threshold the derivative at zero is already positive, so the corner wins. The negative side mirrors the argument. The result is

$${\hat{\beta }}_j=\mathrm{sign}\left({\hat{\beta }}_j^{\mathrm{OLS}}\right){\left(\left|{\hat{\beta }}_j^{\mathrm{OLS}}\right|-\frac{\lambda }{2}\right)}_{+},$$

a subtraction with a floor at zero [S:49:258]. The floor is the whole difference from ridge, which divides each fit by one plus the charge and never reaches zero.

The edge case. Give the model two identical columns and the objective is flat along the line where their weights sum to a fixed total. Every non-negative split of that total is a minimiser, so the lasso returns one of them and the choice falls to the algorithm's tie-breaking, not to the table. L1's closing warning says two inputs carrying the same information leave the fit to choose. Formally it is worse than a choice: the answer is not unique, and a different solver or a different row order can hand you the other column.

What L1 hid. L1 explains deletion by the corners of the diamond. The deeper reason is that the absolute penalty is the tightest convex stand-in for counting non-zero coefficients. The family of charges with exponent $q$ runs from counting at $q=0$ through the lasso at $q=1$ to ridge at $q=2$, and $q=1$ is the smallest exponent whose constraint region stays convex [S:64:91]. Convexity is what makes the fit a solvable problem rather than a search over subsets [S:49:254]. The corner picture is a two-dimensional view of that fact.

Where the analogy breaks. A budget suggests a fixed purse shared among the inputs. In two dimensions you can draw the purse and the contours. In twenty dimensions the same purse is a polytope with a corner for many combinations of columns, and the touching point can sit on an edge where several weights vanish together [S:49:255]. The picture tells you that some coefficients can be zero. It does not tell you how many, and the path of fits under a rising charge is the object that answers that question.

Original sources. ISLP section 6.2.2 writes the penalised criterion, contrasts it with ridge, and derives the variable-selection property from the shape of the constraint region [S:49:253] [S:49:255]. The worked special case that reduces the estimate to a subtraction with a floor at zero appears in the same section [S:49:258]. The Bayesian reading follows: the absolute penalty matches a prior with a sharp peak at zero, so the method starts from the expectation that many coefficients vanish [S:49:259]. The Elements of Statistical Learning puts the family in one line, with counting at the zero exponent, the lasso at one and ridge at two [S:64:91].

An open question. Neither penalty wins everywhere, and the corpus says why: the winner depends on how many inputs truly matter, a number nobody knows before the analysis [S:49:256]. Two tables drawn from the same process can rank the methods differently. The field has no default that survives both regimes. Evidence that would settle a case: a selector whose error bound holds without knowledge of the number of non-zero coefficients, tested on tables that span both regimes with the truth fixed in advance.

A frontier method. Compressed sensing takes the same objective out of statistics. Recovering a sparse vector from fewer measurements than unknowns is hopeless for least squares, because the sparsest consistent vector is found by a combinatorial search. The absolute penalty replaces that search with a convex programme, but the relaxation is not unconditional: recovery holds with high probability only when the measurement matrix is incoherent with respect to the sparsifying basis and the number of measurements is on the order of K log(n/K), and even then the guarantee is probabilistic rather than certain [S:52:122] [S:52:123]. The noisy form, squared residual plus λ times the absolute weights, is the lasso objective under another name [S:52:126]. The corpus names the step that made this possible: the convex relaxation of a counting problem into an absolute-value problem [S:52:125]. The section's picture of a corner is the same corner that lets a measurement scheme beat the counting intuition.

What to read next. Read ISLP section 6.2.2 for the criterion, the constraint picture and the special case [S:49:253], then section 6.2.3 for the choice of charge. Read the Elements of Statistical Learning's section 3.4 for the exponent family and the prior [S:64:91]. Then read Brunton and Kutz's chapter 3 for the compressed-sensing form of the same problem [S:52:126].