How does Lasso scale with the design matrix size? 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.
 A: 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.
