Fast Regularization Paths via Least Angle Regression

Least Angle Regression (LARS) is an efficient algorithm used in artificial intelligence to fit sparse linear models. This article explains how LARS computes the entire regularization path of model coefficients for the same computational cost as a single ordinary least-squares fit. We will cover the geometric mechanics of the algorithm, the piecewise-linear nature of the solution path, and the exact mathematical complexity that makes this speed possible.

The Challenge of Regularization Paths

In sparse linear models, such as the Lasso, a regularization parameter controls the penalty applied to the model's coefficients. Finding the optimal parameter usually requires training the model multiple times across a grid of values. This brute-force approach is computationally expensive because it solves an optimization problem from scratch for every single parameter value. LARS bypasses this bottleneck by tracking how coefficients evolve continuously from zero to their full least-squares values.

The Geometric Mechanics of LARS

LARS builds a linear model sequentially, adding one variable at a time based on its correlation with the current residual (the error between the target and the current prediction).

  1. Initialization: Start with all coefficients set to zero. The residual is equal to the target vector.
  2. First Selection: Find the predictor variable most correlated with the residual.
  3. Progression: Move the coefficient of this variable in the direction of its correlation. As the coefficient increases, the residual decreases, and the correlation between this active variable and the residual drops.
  4. Equiangular Shift: Stop moving solely in this direction the exact moment a second variable achieves the exact same absolute correlation with the residual as the first variable.
  5. Joint Movement: Move both coefficients together in a direction that keeps their correlations with the residual equal and decreasing. In geometry, this direction bisects the angle between the two predictors, which gives "Least Angle" Regression its name.

This process repeats. Whenever a new variable catches up in correlation, it joins the active set, and the direction of movement is updated to remain equiangular to all active variables.

Exploiting Piecewise Linearity

The secret to the speed of LARS is that the regularization path is piecewise linear. Because the equiangular direction remains constant until a new variable enters the active set, the coefficients change in straight lines between these transition points (called knots).

Instead of taking thousands of tiny gradient descent steps, LARS calculates the exact step size needed to reach the next knot using simple trigonometry and linear algebra. It jumps directly from one knot to the next. If a model has \(p\) predictors, the standard LARS algorithm requires exactly \(p\) steps to compute the entire path from a completely sparse model (all zeros) to the full ordinary least-squares solution.

Computational Cost Breakdown

An ordinary least-squares (OLS) fit with \(n\) samples and \(p\) predictors (where \(n > p\)) requires computing the Gram matrix and solving a linear system. The total computational complexity for a single OLS fit is \(O(np^2 + p^3)\).

LARS achieves the exact same asymptotic complexity for the entire path through two main optimizations:

  • Exact Step Calculation: At each step \(k\), finding the equiangular direction requires inverting a covariance matrix of the currently active variables.
  • Matrix Updating: Instead of inverting this matrix from scratch at every step, LARS uses Cholesky decomposition updates. Because only one variable is added at each step, updating the Cholesky factorization of size \(k\) takes only \(O(k^2)\) operations.

Summing \(O(k^2)\) over \(p\) steps yields \(O(p^3)\) total operations for the matrix inversions. Combining this with the \(O(np^2)\) operations required to calculate correlations between the \(p\) predictors and the \(n\)-dimensional residuals across the steps, the total cost of LARS is \(O(np^2 + p^3)\).

The Lasso Modification

To compute the exact Lasso path, LARS requires one minor rule change: if an active coefficient crosses zero while moving along the equiangular direction, stop at the zero-crossing, remove that variable from the active set, and recalculate the equiangular direction. Even with variables occasionally dropping out and re-entering, the number of steps remains heavily bounded, preserving the computational efficiency of a single least-squares fit.