Least Squares Approximation (LSA) for Unifed Lasso (Wang, Leng 2007) mentions Least Angle Regression (LAR) several times. Here's a direct link to the paper.

Specifically, in Section 4 they say:

All studies were conducted in R with the lars package (Efron et al. 2004). This package (and many others used here) can be downloaded at http://cran.r-project.org/. The LSA method uses $\widetilde{\beta}$ and $\widehat{\Sigma}$ as standard inputs. The computational load consists of one single unpenalized full model fitting and one additional LARS processing; therefore, the extra computational cost is minimal.

I'm having trouble seeing the connection between LAR and LSA. From my understanding, LSA tells us that any LASSO style problem with a loss function $\mathcal{L}_n$ can be approximated by $(\beta - \widetilde{\beta})^T \hat{\Sigma^{-1}} (\beta - \widetilde{\beta}) + \sum_{j=1}^{d} \lambda_j |\beta_j|$, where $\widetilde{\beta}$ is the OLS estimate of $\beta$.

How does LSA give us the approximate LASSO solution to the approximation above?


The Least Squares Approximation (LSA) method justifies the approximation $\mathcal{L_n(\beta)} \approx (\beta - \widetilde{\beta})^T \hat{\Sigma^{-1}} (\beta - \widetilde{\beta}).$ This is used to approximate a complex objective function in a LASSO problem by one that is simpler: $$\mathcal{L}_n(\beta) + \sum_{j=1}^{d} \lambda_j |\beta_j| \approx (\beta - \widetilde{\beta})^T \hat{\Sigma^{-1}} (\beta - \widetilde{\beta}) + \sum_{j=1}^{d} \lambda_j |\beta_j|.$$ The approximation is illustrated in Section 2.2 of the paper by assuming some smoothness in $\mathcal{L_n}$ and using a Taylor series approximation, although the authors assert that the method does not depend on this assumption. The right-hand side is the objective function of an $L_1$-penalized least squares problem that can be solved using (a simple modification of) the LARS algorithm. So, LSA does not provide the solution. Rather, LSA is a method for approximating the LASSO problem, and LARS is used to find the solution to that simpler problem.

  • $\begingroup$ I'm unsure of what the modification is. Here's what I think:(1) modify LARS so its solution path is the same as LASSO (2) set the predictor, Y, as the OLS estimate and the predictors, X, as the square root of the estimated covariance matrix. $\endgroup$ – Eli May 24 '17 at 20:44
  • $\begingroup$ I'm not sure either; I have not implemented this method before. One could use a Cholesky decomposition to write $\hat{\Sigma^{-1}} = M^TM$; then the least squares part can be written as \begin{align} (\beta - \widetilde{\beta})^T M^TM (\beta - \widetilde{\beta}) & = [M(\beta - \widetilde{\beta})]^T[M (\beta - \widetilde{\beta})] \newline & = (M\widetilde{\beta} - M\beta)^T(M\widetilde{\beta} - M\beta) \newline & = (\widetilde{Y} - M\beta)^T(\widetilde{Y} - M\beta), \end{align} where $\widetilde{Y} = M\widetilde{\beta}$. $\endgroup$ – Breaking Waves May 25 '17 at 21:28
  • $\begingroup$ This would suggest using the LARS algorithm (modified to produce the LASSO path) with response equal to $M$ times the OLS estimate, and predictor equal to $M$. Chenlei Leng, one of the authors, has as an implementation in R along with some examples on his website (see the last item under Software), so you could try using that as well. $\endgroup$ – Breaking Waves May 25 '17 at 21:28
  • $\begingroup$ That makes sense to me. That's what I was trying to get at, but I didn't think it through as clearly as you. I'll check out the author's implementation. Thanks for the help! $\endgroup$ – Eli May 26 '17 at 15:44

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.