# What optimization problem does least angle regression try to solve?

In Hastie et al's Elements of Statistical Learning, it says

Least angle regression (LAR) ... can be viewed as a kind of “democratic” version of forward stepwise regression (Section 3.3.2). As we will see, LAR is intimately connected with the lasso, and in fact provides an extremely eﬃcient algorithm for computing the entire lasso path as in Figure 3.10.

Forward stepwise regression tries to solve the following optimization problem for selection of best subset of features: $$\min_x \|Ax-b\|_2$$ s.t. $$\|x\|_0 \leq M.$$

LASSO tries to solve the following optimization problem $$\min_x \|Ax-b\|_2$$ s.t. $$\|x\|_1 \leq \epsilon.$$

I was wondering what optimization problem does least angle regression try to solve?

Thanks!

• i think it's important to point out that forward stepwise does indeed try to solve the first problem, but lasso does solve the second problem. Sep 10 '17 at 21:53

If I don't miss anything, LAR tries to solve the same optimization problem with LASSO in a way that the solutions for all possible equivalent $\epsilon$s are given (i.e., the so-called LASSO path)
• Thanks! (1) In Hastie's ESL, algorithm 3.2 for LAR is modified in algorithm 3.2a to provide solutions to the optimization problem of LASSO. So I think LAR solves a different optimization problem? (2) in algorithm 3.2 and 3.2a, I don't see they solve for every values of $\epsilon$?
• (3) what does equivalent $\epsilon$'s mean? If some $\epsilon$'s are equivalent, are their solutions the same?
• Equivalent $\epsilon$s, by definition, lead to the same minimizer for LASSO problem. Apr 7 '13 at 18:25
• Thanks! I was wondering why LAR solves for the solutions for all values of $\epsilon$?