Least Angle Regression (LARS)
Forward stagewise selection and the piecewise-linear regularization path.
On this page
Beginner: lasso (section 2.3.3) gives one answer for one chosen λ. But often what you actually want to see is the WHOLE STORY — every coefficient's value, for every λ from huge (everything zero) down to zero (the full OLS answer). Solving lasso separately at a hundred different λ values would be slow. LARS computes the entire path in roughly the cost of a single OLS fit.
Intermediate: LARS is a careful middle ground between two extremes: forward selection (add one variable FULLY at a time — too abrupt, ignores how much other variables are still explaining) and solving the full lasso path directly (correct, but computationally expensive). LARS moves coefficients in small, geometrically precise steps that trace out the lasso-equivalent path almost for free.
Advanced: the algorithm: start with every coefficient at 0. Find the predictor most correlated with the current residual, and move its coefficient in the direction that reduces the residual — but only until some OTHER predictor becomes EQUALLY correlated with the shrinking residual. At that point, move both together in the "equiangular direction" — the direction equally correlated with every currently active predictor. Repeat, adding one predictor to the active set at a time.
At each step, find the predictor most correlated with the residual r, then move along the unique direction u that keeps every active predictor's correlation with the (shrinking) residual equal.
Fix an active set of predictors (the ones tied for most correlated with the residual so far). The equiangular direction u must satisfy x_j^T(r_0 - su) = c for every active j, for some common constant c and every distance s moved — this is a linear system in u, built from the currently FIXED active predictors' inner products. A linear system with fixed coefficients has one fixed solution u, independent of s. Since moving distance s along a FIXED direction u is, by definition, a straight line, θ(s) = θ_0 + su is piecewise linear within any segment where the active set doesn't change.
The segment ends — a KINK occurs — exactly when a new predictor's correlation with the shrinking residual catches up to the active set's common correlation. Both the active predictors' correlation and every inactive predictor's correlation change LINEARLY in s (since the residual itself changes linearly along the segment). Setting the active correlation's linear expression equal to an inactive predictor's linear expression and solving for s gives the exact, closed-form distance to the next kink — no search required, just solving a linear equation per candidate predictor and taking the smallest positive root.
Where this is used: this exact piecewise-linear structure is why LARS-based solvers can report the complete lasso solution path efficiently, instead of re-solving the full optimization from scratch at every λ grid point.
Each colored line is one coefficient's value as 'distance traveled' increases. The path is built one straight segment at a time; a red flash marks each kink, where a new predictor joins the active set and the direction of travel changes.
Every predictor's |correlation| with the shrinking residual, computed from an actual run of the LARS algorithm on a 4-predictor synthetic dataset (not a hand-drawn illustration). A dashed line turns solid the instant that predictor's correlation ties the active set's declining correlation -- exactly the kink condition the derivation solves for in closed form -- and from then on it travels locked to the rest of the active set along the equiangular direction.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
int main() {
// Simplified LARS-style entry-order demo: repeatedly pick the column most
// correlated with the residual, project it out, and report the order.
std::vector<std::vector<double>> X = {{1, 0, 2}, {0, 1, -1}, {1, 1, 0}, {2, -1, 1}, {0, 2, 1}};
std::vector<double> y = {3, -1, 1, 6, 1};
int n = X.size(), p = X[0].size();
std::vector<double> residual = y;
std::vector<bool> entered(p, false);
for (int step = 0; step < p; ++step) {
int best = -1;
double bestCorr = -1;
for (int j = 0; j < p; ++j) {
if (entered[j]) continue;
double corr = 0;
for (int i = 0; i < n; ++i) corr += X[i][j] * residual[i];
if (std::abs(corr) > bestCorr) { bestCorr = std::abs(corr); best = j; }
}
entered[best] = true;
std::cout << "predictor " << best << " enters, |corr|=" << bestCorr << "\n";
// Crude residual reduction along the newly entered predictor's direction.
double norm2 = 0;
for (int i = 0; i < n; ++i) norm2 += X[i][best] * X[i][best];
double coef = bestCorr / norm2 * 0.5;
for (int i = 0; i < n; ++i) residual[i] -= coef * X[i][best] * (bestCorr > 0 ? 1 : -1);
}
return 0;
}- Genomics and other
p ≫ nsettings — computing the full regularization path cheaply matters enormously when a single OLS-scale fit is already expensive. - Model selection workflows that want to see the ENTIRE path of which variables enter and in what order, not just one
λ's answer. - LARS as the algorithm underneath many forward-selection-style variable importance rankings used in exploratory statistics.
- Its historical role as the fast way to compute the lasso path before modern coordinate-descent solvers (section 2.2.5) became the standard default.
- Confusing plain LARS with "the lasso path algorithm" — as originally described, LARS needs one extra modification (allowing a coefficient to be dropped from the active set if it would cross zero) to exactly reproduce the lasso solution path; without it, the two can diverge slightly.
- Treating the entry order of predictors as a definitive causal or importance ranking — it's an artifact of correlation structure in this particular sample, not a guaranteed statement about the true underlying relationship.
- Numerical sensitivity when predictors are nearly perfectly correlated — near-ties in correlation can make the entry order unstable from run to run or under small data perturbations.
Going deeper
The precise relationship between LARS and lasso is a subtlety worth naming exactly: LARS as originally proposed is closer to a refined forward-stagewise algorithm. It reproduces the exact lasso path only with the added rule that a variable is DROPPED from the active set the instant its coefficient would cross zero (rather than just changing sign) — this "LARS-lasso" modification is what production solvers implement when the goal is specifically the lasso path, not generic LARS.
Why is the LARS coefficient path guaranteed to be piecewise LINEAR rather than some other shape?
Within any stretch where the active set of predictors doesn't change, the 'equiangular direction' the path moves along is the solution to a linear system built from the currently-active (fixed) predictors — a fixed system has one fixed solution, and moving any distance along one fixed direction is by definition a straight line. The path only bends at a 'kink,' which happens exactly when a new predictor's correlation with the shrinking residual catches up to the active set's, changing which linear system defines the direction going forward.
LARS turns "solve lasso at every λ" into "trace one piecewise-linear path once," using nothing more than repeated linear-system solves. The next lesson moves away from penalties on a coefficient vector entirely, toward expanding the FEATURES themselves — polynomial and general basis-function regression.