10
$\begingroup$

If I have a design matrix $X\in\mathcal{R}^{n\times d}$, where $n$ is the number of observations of dimension $d$, what is the complexity of solving for $\hat{\beta}=\text{argmin}_{\beta}\frac{1}{2n} ||X\beta-y||^{2} + \lambda||\beta||_{1}$ with LASSO, wrt $n$ and $d$? I think the answer should refer to how one LASSO iteration scales with these parameters, rather than how the number of iterations (convergence) scales, unless you feel otherwise.

I have read this previous LASSO complexity question, but it seems at odds with the discussion about glmnet here and here. I am aware that there are many algorithms out there, including glmnet's GLM approach, but I am writing a paper about replacing a LASSO component to a parent algorithm and would like to include a discussion about LASSO complexity in general, especially with $d$ and $n$. I would also like to know glmnet's complexity in the basic non-sparse case, but the referenced paper is a little confusing as the entire algorithm complexity is not explicit.

$\endgroup$
  • 3
    $\begingroup$ It's not clear why this answer stats.stackexchange.com/a/190717/28666 (in the thread that you linked to) does not answer your question. Can you elaborate? What is at odds with what? $\endgroup$ – amoeba May 22 '17 at 20:22
  • $\begingroup$ Page 6 in [pdf][1], states "Thus a complete cycle through all d variables costs $O(dn)$". However the question you link to states $O(d^{2}n)$. Am I missing a loop here to get the $d^{2}$ complexity? [1]: jstatsoft.org/article/view/v033i01 $\endgroup$ – rnoodle May 24 '17 at 11:21
  • $\begingroup$ @amoeba The link you provide is for the LARS algorithm - I want to know about the GLM approach. $\endgroup$ – rnoodle Aug 9 '17 at 10:56
  • $\begingroup$ The references, $\mathcal{O}(d^2n)$ for least angle regression and $\mathcal{O}(dn)$ for coordinate descent, are correct. The difference is that (1) LARS finds an exact solution in $\mathcal{O}(d^2n)$ (and doing so going across the entire path of possible $\lambda$ with complexity equal to the OLS problem to the entire problem, which also scales as $\mathcal{O}(d^2n)$), while (2) coordinate descent is doing "only" a single approximation step in $\mathcal{O}(dn)$, converging/'descending' closer to the minimum of the LASSO problem. LARS uses $d$ steps. With coordinate descent... nobody knows. $\endgroup$ – Martijn Weterings Aug 9 '17 at 22:47
3
+100
$\begingroup$

The answers from the references,

  • $\mathcal{O}(d^2n)$ for least angle regression
  • $\mathcal{O}(dn)$ for coordinate descent

, are correct.


The difference is that

LARS equations are written in a closed form and finds an exact solution

(and doing so going across the entire path of possible λ while the computational complexity is scaling the same as finding the solution of the ordinary least squares problem, which also scales as $O(d^2n)$)

while

coordinate descent is an iterative scheme to approximate the solution. The referred step (whose computational costs scale as as $\mathcal{O}(dn)$) is "only" a single approximation step, converging/'descending' closer to the minimum of the LASSO problem.


LARS uses (exactly) $d$ steps to find the solution (with the complexity of the k-th step scaling as $\mathcal{O}((d-k)n+k^2)$, first term for finding $d-k$ inner-products in the inactive set and second term for solving the new angle in the $k$ active variables). With coordinate descent, nobody really knows the convergence rate and the number of required/expected steps for 'sufficient' convergence (or at least it has not been described well).

On the other hand the cost $d^2n$ increases a lot for high dimensions (while there is no strong reason to expect that coordinate descent's convergence rate scales similarly, =linear, if $d$ increases). So intuitively coordinate descent will perform better above a certain limit for $d$. This has also been shown by case studies (see also the reference which shows that glmnet performs mostly better than LARS when $d>>100$, while for $d=100$ the algorithms perform similar).


Scaling LARS is a problem involving computational complexity. Scaling coordinate descent is a problem involving computational complexity and convergence.

$\endgroup$

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.