I am trying to understand how Lars algorithm can be modified to generate Lasso. While I do understand LARS, I am not able to see the Lasso modification from the paper by Tibshirani et al. In particular I don't see why the sign condition in that the sign of the non-zero coordinate must agree with the sign of the current correlation. Can someone please help me with this. I guess I am looking for a mathematical proof using KKT condition on the original L-1 norm problem i.e the Lasso. Thanks much!
2
-
$\begingroup$ Are you referring to Efron et al's stanford.edu/~hastie/Papers/LARS/LeastAngle_2002.pdf? It proves this in Lemma 8 of section 5. Or am I misunderstanding your question? $\endgroup$– Peter EllisCommented May 4, 2012 at 23:26
-
1$\begingroup$ I'm also not sure about the question, but actually, the Lasso is a simplification of the Lars: For Lasso, you're only looking for positive correlations between the current residual and the remaining basis functions, since only positive correlations lead to positive (~non-negative) coefficients. $\endgroup$– Mr. WhiteCommented Oct 26, 2012 at 19:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Let $X$ (size $n\times p$) denote a set of standardised inputs, $y$ (size $n \times 1$) centered responses, $\beta$ (size $p \times 1$) regression weights and $\lambda > 0$ a $l_1$-norm penalisation coefficient.
The LASSO problem then writes \begin{align} \beta^* &= \text{argmin}_{\beta}\ L(\beta,\lambda) \\ L(\beta,\lambda) &= \Vert y-X\beta \Vert_2^2 + \lambda \Vert \beta \Vert_1 \end{align}
Solving this for all values of $\lambda > 0$ yields the so-called LASSO regularisation path $\beta^*(\lambda)$.
For a fixed value of the penalisation coefficient $\lambda^*$ (i.e. fixed number of active predictors = fixed step of the LARS algorithm), it is possible to show that $\beta^*$ satisfies (simply write out the KKT stationarity condition as in this answer)
$$ \lambda^* = 2 \ \text{sign}(\beta_a^*) X_a^T (y - X \beta^*),\ \ \ \forall a \in A $$
with $A$ representing the set of active predictors.
Because $\lambda^*$ must be positive (it is a penalisation coefficient), it is clear that the sign of $\beta_a^*$ (weight of any non-zero hence active predictor) should be the same than that of $X_a^T (y - X\beta^*) = X_{a}^T r$ i.e. the correlation with the current regression residual.
answered Apr 25, 2016 at 11:20
$\begingroup$
$\endgroup$
@Mr._White provided a great intuitive explanation of the major difference between LARS and Lasso; the only point I would add is that lasso is (kind of) like a backward selection approach, knocking out a term at each step as long as a term exists for which of those ("normalized" over $X \times X$) correlations exist. LARS keeps everything in there -- basically performing the lasso in every possible order. That does mean that in lasso, each iteration is dependent on which terms have already been removed.
Effron's implementation illustrates the differences vary well: lars.R in the source pkg for lars. Notice the update step of matrices $X \times X$ matrix and $\zeta$ starting at line 180, and the dropping of the terms for which $\zeta_{min} < \zeta_{current}$. I can imagine some weird situations arising from spaces $A$ where the terms are unbalanced ($x_1$ and $x_2$ are very correlated but not with others, $x_2$ with $x_3$ but not with others, etc.) the selection order could be quite biased.
