6
$\begingroup$

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 efficient 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!

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user795305
    Sep 10 '17 at 21:53
1
$\begingroup$

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)

$\endgroup$
4
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Tim
    Apr 7 '13 at 18:14
  • 1
    $\begingroup$ (3) what does equivalent $\epsilon$'s mean? If some $\epsilon$'s are equivalent, are their solutions the same? $\endgroup$
    – Tim
    Apr 7 '13 at 18:19
  • $\begingroup$ Equivalent $\epsilon$s, by definition, lead to the same minimizer for LASSO problem. $\endgroup$ Apr 7 '13 at 18:25
  • $\begingroup$ Thanks! I was wondering why LAR solves for the solutions for all values of $\epsilon$? $\endgroup$
    – Tim
    Apr 7 '13 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.