Least Angle Regression

1. Introduction.

• The motivating diabetes study measured 442 patients on 10 baseline variables to predict one-year disease progression while identifying potentially important covariates.The covariates are standardized in the theory, although numerical results are reported in the example’s original units.Source: §1 · pp. 2–3
• The Lasso traces solutions from β = 0 at t = 0 to the OLS regression vector at t = 3460.00, while shrinking coefficients toward zero for smaller t.This shrinkage trades increased bias for decreased variance and can improve prediction accuracy.Source: §1 · p. 4
• At t = 1000, the Lasso selects only variables 3, 9, 4, and 7, illustrating how its constraint produces parsimonious models.The paper presents this subset as potentially useful when the resulting model provides adequate predictions.Source: §1 · p. 4
• Forward Stagewise updates the regression function in small steps toward the predictor with greatest current correlation, avoiding the greediness of large Forward Selection steps.Choosing ε small prevents the procedure from impulsively eliminating covariates correlated with the selected predictor.Source: §1 · pp. 4–5
• Although Lasso and Stagewise have different definitions, their coefficient estimates for the diabetes data are nearly identical but not exactly the same.The Stagewise path uses 6000 small steps in the displayed analysis.Source: §1 · p. 5
• LARS provides a common framework for the Lasso and Forward Stagewise regression, with modifications that reduce their computational burden by at least an order of magnitude.The paper also verifies these connections in later sections and provides an efficient implementation for all three methods.Source: §1 · pp. 2, 5

2. The LARS algorithm.

• LARS uses larger analytically calculated steps than Stagewise, which would otherwise repeat many updates of size ε.In the two-predictor case, the second direction is the unit bisector; with more predictors, the step ends before reaching the corresponding OLS projection.Source: §2 · pp. 5–7
• LARS starts at μ̂0 = 0, follows the predictor most correlated with the residual, and changes direction when another predictor reaches equal correlation.After the change, it proceeds along an equiangular direction rather than continuing greedily along the first predictor.Source: §2 · pp. 6–7
• Each LARS step adds one covariate to the active set and advances along a vector making equal angles with the active predictors.The step size is chosen so that the next variable joins when its absolute current correlation reaches the active maximum.Source: §2 · pp. 7–8
• The complete diabetes analysis requires only m = 10 LARS steps, compared with 6000 Stagewise steps, while selecting variables in the order 3, 9, 4, 7, ..., 1.The resulting coefficient tracks are nearly, but not exactly, the same as the Lasso and Stagewise tracks.Source: §2 · pp. 6, 9
• For the diabetes data, the right-hand diagnostic tracks absolute current correlations against LARS step, with the maximum correlation declining as variables enter the active set.The left panel plots coefficient estimates against their absolute-sum size, and the active-set order is 3, 9, 4, 7, ..., 1.Source: Figure 3 · p. 9, §2 · p. 9
• At each stage, the LARS estimate approaches but does not reach the corresponding OLS projection, except at the final stage where it equals the full-model OLS estimate.The final convention sets γ̂m = γ̄m and gives μ̂m = ȳm.Source: §2 · p. 10, Figure 4 · p. 10
• The full m-step LARS computation has the same order of cost as the usual least-squares solution for all m covariates.The same program can provide economical Lasso and Stagewise solutions after the corresponding modifications.Source: §2 · p. 10

Common geometry

• LARS, Lasso, and Stagewise share a moderately greedy forward-stepwise geometry based on compromise among the currently most correlated covariates.LARS follows the equiangular direction, whereas Lasso and Stagewise restrict that strategy differently.Source: §3 · p. 11

LARS–Lasso relationship

• A minor LARS modification yields all Lasso solutions under the “one at a time” condition.The Lasso modification stops a LARS step when a coefficient would violate the sign restriction and removes that variable from the next active-set calculation.Source: §3.1 · p. 12

Computational path length

• The Lasso modification can require more steps than unmodified LARS, taking 12 rather than 10 steps in the diabetes example and 103 rather than 64 for the quadratic model.All three methods eventually reach OLS, but LARS does so in m steps while Lasso and especially Stagewise can take longer; Stagewise required 255 steps for the m = 64 quadratic model.Source: §3.1 · p. 12, §3.2 · p. 14

LARS–Stagewise relationship

• The Stagewise procedure uses infinitesimal steps, and coefficient reversals can occur only after a current correlation changes sign while a coefficient is resting.In the diabetes example, this happened to variable 7 between the eighth and tenth Stagewise-modified LARS steps.Source: §3.2 · pp. 13–14
• A second modification yields all Stagewise solutions by replacing the equiangular direction with its projection into the relevant convex cone.This projected direction permits the active set to decrease by one or more indices.Source: §3.2 · pp. 13–14

Simulation study

• In the simulation, LARS, Lasso, and Stagewise performed nearly identically, reaching an average proportion explained of 0.963 at k = 10 before declining slowly.Classic Forward Selection rose and fell more abruptly, reaching 0.950 after k = 3; stopping between k = 5 and 25 typically gave true predictive R2 about 0.40 versus an ideal value of 0.416.Source: §3.3 · pp. 15–16

Other LARS modifications

• A positive Lasso modification is appropriate when predictors must enter in predefined directions, but it usually does not converge to the full OLS solution.The positive Stagewise version instead has coefficient tracks that are always monotone.Source: §3.4 · p. 16

• The diabetes example showed R2 increases of about 0.01 for k ≥4, compared with R2 ≈ 0.50.The small gains are consistent with continuing LARS until successive R2 improvements become small.Source: LARS–OLS hybrid · p. 17
• The fitted coefficient vectors ¯βk and bβk were likely to lie near each other in the diabetes example.Source: LARS–OLS hybrid · p. 17
• LARS can restrict the order in which variables are allowed to enter, supporting a subsequent interaction check after obtaining A4 = {3,9,4,7}.The interaction procedure begins LARS again after replacing y with the residual expression described in the passage.Source: Main effects first · p. 17

Main effects first

• The proposed interaction stage uses residual response after the selected main effects and supplies their pairwise interactions as new predictors.No performance result for this interaction-expanded model is reported in the supplied passage.Source: Main effects first · p. 17

Backward Lasso

• Lasso can be viewed as a backward-moving algorithm because its equiangular direction permits navigation from the full OLS solution toward sparser solutions.Original LARS and Stagewise remain inherently forward-moving.Source: Backward Lasso · p. 17

• The proposed Cp formula estimates LARS risk without calculations beyond those already used to obtain the LARS estimates, unlike its applicability to Lasso or Stagewise.It is the analogue of the Cp estimate for OLS subsets of k preselected predictors.Source: §4 · pp. 18–19
• Minimum Cp selects LARS steps k = 7 for the m = 10 model and k = 16 for the m = 64 model, with both selected models appearing sensible.The first several selected covariates agreed with an earlier medically informed data analysis.Source: §4 · p. 19, Figure 7 · p. 20

Orthogonal designs

• Under mutually orthogonal covariates, the k-step LARS estimate has exactly k degrees of freedom.In this setting, LARS reduces to soft thresholding at the ordered absolute data values.Source: §4 · p. 19, §4.1 · pp. 21–22

• Under the positive cone condition, LARS, Lasso, and Stagewise coincide, and each has degrees of freedom k for the k-step estimate.The condition is more general than orthogonality, but the diabetes design does not satisfy it.Source: §4 · p. 20, §4.3 · p. 25
• For LARS, the simple approximation df(bµ_k) ≈ k is accurate in simulations even with highly correlated covariates, although pathological designs can differ substantially.The approximation is also supported by a delta-method argument based on a locally linear representation whose matrix has trace k.Source: §4 · p. 21
• The df(bµ_k) ≈ k approximation is not justified for general Lasso sequences because their total number of steps can exceed the m degrees of freedom of the full model.Empirically, Lasso degrees of freedom are approximately the number of nonzero predictors at the last model containing k predictors, but this claim lacks mathematical support.Source: §4 · p. 21

Active-set selection

• New variables enter the LARS active set in the direction consistent with their current correlations, a requirement crucial for matching the Lasso constraints.The sign agreement supplies one of the conditions needed for the LARS–Lasso relationship.Source: §5 · pp. 25–26

Lasso properties

• The Lasso shrinks coefficients toward zero as its constraint relaxes, while retaining only a subset of covariates at each constraint value.The path is uniquely defined and continuous because the relevant objective functions are convex, with strict convexity in S.Source: §5 · p. 27

Piecewise-linear path

• Between active-set changes, the Lasso coefficients and fitted values move linearly along an edge and the active set determines the LARS equiangular direction.The nonactive coefficients remain zero while the fitted values advance along u_A.Source: §5 · pp. 28–29

Active-set selection

• The Lasso active set must minimize A_A because this choice makes the residual sum of squares decline at the fastest possible rate.The geometric argument links the optimal negative slope of the (T,S) curve to the active-set choice.Source: §5 · pp. 31–33

LARS–Lasso equivalence

• Under the one-at-a-time condition, modified LARS yields all Lasso solutions by induction across successive active-set breakpoints.The equivalence continues within each step and is checked when variables enter or leave the active set.Source: §5 · p. 33

Scope condition

• When multiple variables enter simultaneously, the LARS–Lasso algorithm remains available but requires examining additional active-set possibilities and therefore more computation.The standard algorithm is not equipped for many-at-a-time problems without such extra work.Source: §5 · pp. 33–34

Stagewise constraints

• For sufficiently small ε, only predictors in the current maximal-correlation set can receive positive forward-step weights.The resulting direction is represented as a nonnegative combination of those predictors.Source: §6 · p. 34
• The allowable Stagewise direction is proportional to the equiangular vector of a subset B of the currently maximally correlated predictors.The direction must keep correlations in B declining equally and prevent excluded maximal predictors from immediately reentering.Source: §6 · p. 35

Piecewise path

• The Stagewise direction depends only on the current maximal-correlation set, and the LARS–Stagewise path preserves that direction between breakpoints.The maximal set may shrink to B during an interval without changing the resulting direction.Source: §6 · p. 38

LARS–Stagewise equivalence

• The LARS–Stagewise algorithm produces a legitimate version of the idealized Stagewise track and is unique among procedures satisfying its three constraints.The idealized procedure uses ε →0, while the modified LARS implementation takes larger piecewise-linear steps.Source: §6 · pp. 36, 38

Scope and interpretation

• Stagewise generalizes naturally to nonlinear fitting problems, whereas the paper’s LARS and Lasso comparisons are developed within the linear-model framework.The linear analysis clarifies the relationship between Stagewise methodology and the other procedures.Source: §6 · p. 38

Comparison with LARS

• Stagewise chooses directions that reduce maximal absolute residual correlation rather than greedily maximizing the instantaneous decrease in residual squared error.This makes Stagewise less greedy than LARS within parsimonious forward search.Source: §6 · p. 39

LARS complexity

• The complete LARS sequence requires O(m^3 + nm^2) computations when m < n, comparable to the cost of a least-squares fit on m variables.Each step updates correlations and the Cholesky factorization of the active predictors’ cross-product matrix.Source: §7 · p. 39

Modified algorithms

• The Lasso modification occasionally drops variables and downdates the active-set Cholesky factor, while Stagewise additionally checks coefficient-direction signs and may invoke NNLS downdates.These operations add at most O(m^2) per Lasso downdate and can substantially increase Stagewise work.Source: §7 · pp. 39–40

Computational limitation

• With many correlated variables, the Stagewise modification can take many more steps than LARS, increasing computation by a factor of up to 5 or more in extreme cases.Frequent dropping and adding of variables drives the extra cost.Source: §7 · p. 40

High-dimensional regime

• For m ≫n, LARS reaches the saturated least-squares fit after n −1 active variables enter, at a cost of O(n^3) operations.Mean centering gives the design matrix row-rank n −1.Source: §7 · p. 40
• LARS continues to provide Lasso solutions in the m ≫n setting, with no more than n −1 nonzero coefficients in any fitted model.Across the full sequence, however, more than n −1 different variables may enter at different times.Source: §7 · p. 40

8. Boosting procedures.

• Small ε values improve prediction accuracy relative to ε = 1, but making ε very small causes computational slowness.Least-squares boosting repeatedly updates the fit by ε·t1 and refits to the residuals.Source: §8 · p. 41
• Forward Stagewise regression underlies least-squares boosting because fitting the best predictor to current residuals resembles selecting the most correlated predictor.The analogy is idealized when the predictor set is all possible trees, which is infinite and only partially searched by greedy CART procedures.Source: §8 · pp. 40–41
• The Lasso and Forward Stagewise regression are closely related, suggesting that least-squares boosting may approximate a Lasso fit over tree predictors.Direct LARS computation is infeasible when the predictor set contains infinitely many trees.Source: §8 · p. 41
• A modified Forward Stagewise procedure takes a small least-squares step across all currently modeled trees, approximating LARS while remaining applicable to infinite predictor sets.The procedure still identifies the best tree conventionally but updates all trees currently in the model.Source: §8 · p. 41

A.1. Local linearity and Lemma 2.

• On an open set of full measure, successive LARS active sets are locally fixed, differ by one variable, and the fitted value μ̂k(y) is locally linear.The sets supporting these properties decrease with k.Source: §A.1 · p. 42
• Near a point where one variable is selected, the joining variable remains unchanged locally, making the step size and fitted value continuous and locally linear.The result follows because qualifying correlation comparisons retain their signs and ordering in a neighborhood.Source: §A.1 · pp. 43–44
• The exceptional set governing competing variable entries is a finite union of hyperplanes and therefore closed.Outside this set, a unique new variable joins the active set locally.Source: §A.1 · p. 43
• The induction establishes local continuity, linearity, and uniform Lipschitz behavior when the preceding fitted value already has those properties.The argument begins with μ̂0 = 0 and propagates the regularity through successive active-set updates.Source: §A.1 · pp. 42–44

A.2. Consequences of the positive cone condition.

• The regularity argument is explicitly developed for double points and is then stated to extend to points where three or more variables enter simultaneously.This extension yields continuity, uniform local Lipschitz behavior, and almost differentiability of the fitted-value map.Source: §A.3 · pp. 45–47
• At a double point, nearby active-set changes can add the first variable, the second variable, or both, while the fitted value remains continuous and locally Lipschitz.The proof compares the two tied entry quantities and handles each of the three possible local active-set configurations.Source: §A.3 · p. 45
• Under the positive cone condition, LARS fitted values remain continuous and locally Lipschitz even at double points where two variables enter simultaneously.Without this condition, multiple points can cause discontinuities in the fitted path.Source: §A.3 · pp. 45–47
• The positive cone condition prevents discontinuities by ensuring the next-step coefficient behavior remains well controlled as a second variable approaches entry.In particular, the relevant step size tends to zero when approaching the set of double points.Source: §A.2 · p. 45, §A.3 · p. 46