Least angle regression

Lower the tension slowly and predictors engage one at a time, each held at the ceiling.

The Lasso demo replaced the shrinkage spring with a constant-tension pulley of force $\lambda$. A predictor sits at zero until its correlation with the residual exceeds $\lambda$. Then it engages. Least angle regression (LARS) is what you get when you take that one threshold and lower it continuously from very high to zero. The whole configuration re-forms as it descends.

The Karush-Kuhn-Tucker conditions for the Lasso say this. At penalty $\lambda$, every active predictor has $|x_j^{\top} r| = \lambda$. Its correlation with the residual is pinned to the ceiling. Every idle one sits strictly below, $|x_j^{\top} r| \le \lambda$. So as $\lambda$ falls the active predictors march down together, always tied, always equal to the current tension:

$$ x_j^{\top}\!\left(y - X\beta\right) = \lambda\,\operatorname{sign}(\beta_j)\ \ (j\ \text{active}), \qquad \left|x_k^{\top}\!\left(y - X\beta\right)\right| \le \lambda\ \ (k\ \text{idle}). $$

The name is the mechanism. To keep every active correlation equal as the fit advances, the fitted vector must move along the direction that makes equal angles with all active predictors. That is the least angle, equiangular direction. Move that way and the tied correlations decay in lockstep. An idle predictor stays out until the descending ceiling reaches its correlation, and then it joins. Between two such joins the coefficients are linear in $\lambda$. So the whole solution path is piecewise-linear with a kink at each engagement. This is the Lasso path traced from the top down, as long as no active coefficient crosses zero. The design here never does. When a coefficient would cross zero the Lasso needs an extra step that drops it from the active set. This version has no such step.

tension / penalty $\lambda$

active set λ β

Top: the descending ceiling. Each line is one predictor's absolute correlation with the current residual, $|x_j^{\top} r|$, plotted against $\lambda$. The penalty runs from high to low, left to right. The dashed diagonal is the ceiling $|c| = \lambda$ itself. Idle predictors ride below it. The moment a line touches the ceiling that predictor engages. It then travels down the diagonal, glued to $\lambda$ and tied with every other active one. Bottom: the coefficient path, sharing the same $\lambda$ axis. The dotted sweep line links the two. Each $\beta_j$ leaves zero at the same $\lambda$ where its correlation hit the ceiling directly above. Every segment is a straight line. Drag $\lambda$, or press Lower the ceiling, and watch the four predictors engage one after another. At $\lambda = 0$ the path arrives at the ordinary least-squares fit.

Efron, Hastie, Johnstone and Tibshirani introduced LARS in 2004 as this descent. One sweep builds the path in a handful of equiangular segments, one per active-set change. With the drop step added it produces the full Lasso path. It is the constant-tension device of the previous demo, filmed as its weight is slowly lifted. Their paper appeared in the Annals of Statistics.

The usual explanation the KKT derivation, in full

Start from the lasso objective for the whole coefficient vector $\beta$, with design $X$ and response $y$:

$$ \tfrac12\,\|y - X\beta\|^2 + \lambda\,\|\beta\|_1. $$

The subgradient of the $L_1$ term is $\operatorname{sign}(\beta_j)$ where $\beta_j \ne 0$ and any value in $[-1,1]$ where $\beta_j = 0$. Setting $0$ in the subdifferential gives the stationarity conditions. For an active coordinate:

$$ x_j^{\top}(y - X\beta) = \lambda\,\operatorname{sign}(\beta_j), \qquad j \in \mathcal{A}. $$

For an idle coordinate the correlation stays inside the band:

$$ \big|x_k^{\top}(y - X\beta)\big| \le \lambda, \qquad k \notin \mathcal{A}. $$

Every active correlation has magnitude $\lambda$, so they are tied. Hold the active set fixed, let $s$ be the vector of active signs, and impose the active equations together:

$$ X_{\mathcal{A}}^{\top}\big(y - X_{\mathcal{A}}\,\beta_{\mathcal{A}}\big) = \lambda\,s. $$

Solve for the active coefficients and read off the slope in $\lambda$:

$$ \beta_{\mathcal{A}}(\lambda) = \big(X_{\mathcal{A}}^{\top} X_{\mathcal{A}}\big)^{-1} \big(X_{\mathcal{A}}^{\top} y - \lambda s\big), \qquad \frac{d\beta_{\mathcal{A}}}{d\lambda} = -\big(X_{\mathcal{A}}^{\top} X_{\mathcal{A}}\big)^{-1} s. $$

The slope is constant while the active set does not change, so $\beta$ is linear in $\lambda$. That fixed direction is the equiangular one. It makes equal angles with every active predictor, which is exactly what keeps the tied correlations equal as $\lambda$ falls. The path bends only at a breakpoint, and a breakpoint is triggered one of two ways. An idle correlation rises to meet $\lambda$ and its coordinate joins the active set. Or an active coefficient reaches zero and must leave, the drop step. Between breakpoints the path is a straight segment. The add-only descent traces the lasso path exactly as long as no coefficient crosses zero. With the drop step it is the full lasso path everywhere.

The physics proof read off the descending ceiling

The lasso demo proved the mechanism. The penalty is a constant-tension pulley of force $\lambda$, and a predictor stays at zero until the data out-pull it. This page lowers $\lambda$.

Lower the ceiling and the active predictors ride it down together, every one pinned at the same tension, because one constant force is one force for all of them.

$$ \big|x_j^{\top} r\big| = \lambda \quad \text{for every active } j. $$

A shared force falling at a steady rate moves the coefficients in straight lines, and bends them all at once when the set changes. The caveat rides along. This add-only descent equals the lasso path only while no coefficient crosses back through zero, and the design here is arranged so none does. Read the answer off the ceiling. The film is the algorithm.