How does Lasso scale with the design matrix size?

Question

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.

Answer 1

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.