What is the time complexity of Lasso regression?

Question

What is the asymptotic time complexity of Lasso regression as either the number of rows or columns grows?

Answer 1

Recall that lasso is a linear model with a $l_1$ regularization.

Finding the parameters can be formulated as a unconstrained optimization problem, where the parameters are given by

$\arg \min_\beta ||y - X\beta||^2 + \alpha||\beta||_1$.

In the constrained formuation the parameters are given by

$\arg \min_\beta ||y - X\beta||^2 s.t.||\beta||_1 < \alpha$

Which is a quadratic programming problem and thus polynomial.

Almost all convex optimization routines, even for flexible nonlinear things like neural networks, rely on computing the derivative of your target w.r.t. parameters. You cannot take the derivative of $\alpha||w||_1$ though. As such you rely on different techniques. There are many methods for finding the parameters. Here's a review paper on the subject, Least Squares Optimization with L1-Norm Regularization. Time-complexity of iterative convex optimization is kind of tricky to analyze, as it depends on a convergence criterion. Generally, iterative problems converge in fewer epochs as the observations increase.

Answer 2

While @JacobMick provides a broader overview and a link to a review paper, let me give a "shortcut answer" (which may be considered a special case of his answer).

Let the number of candidate variables (features, columns) be $K$ and the sample size (number of observations, rows) be $n$. Consider LASSO implemented using LARS algorithm (Efron et al., 2004). The computational complexity of LASSO is $\mathcal{O}(K^3 + K^2 n)$ (ibid.)

• For $K<n$, $K^3 < K^2 n$ and the computational complexity of LASSO is $\mathcal{O}(K^2 n)$, which is the same as that of a regression with $K$ variables (Efron et al., 2004, p. 443-444; also cited in Schmidt, 2005, section 2.4; for computational complexity of a regression, see this post).
• For $K \geqslant n$, $K^3 \geqslant K^2 n$ and the computational complexity of LASSO is $\mathcal{O}(K^3)$ (Efron et al., 2004).

References:

• Efron, Bradley, et al. "Least angle regression." The Annals of Statistics 32.2 (2004): 407-499.
• Schmidt, Mark. "Least squares optimization with l1-norm regularization." CS542B Project Report (2005).