How many zeroes from lasso linear regression?

Question

Given a dataset $X$ with $d$-dimensional features $x \in R^d$, and a response variable $y$ you can perform a lasso regression, ie linear regression with L1 regularization, as

$$ \min_{\beta} (X\beta - y)^2 + \lambda \sum_j |\beta_j| $$

It's well known that this kind of regularization yields sparse solutions, ie the estimated $\beta$ has coefficients set to zero. This method can be used as a feature selection technique.

Is there a relation between $\lambda$ and the number of non-zero coefficients? For example, if you set $\lambda = 0.01$ you would expect around 10% of the coefficients to be zero (I'm making these numbers out).

I guess it heavily depends on the distribution of $X$ and $y$, but I was wondering if there's a rule of thumb - or a rigorous relation - that tells you how many features would you select depending on $\lambda$. By rigorous relation, I mean a function $f$ like

$$ \# \text{zeroes} = f(X, y, \lambda) $$

Answer 1

There are simple relationships for the bounds of $\lambda$ where you get all coefficients zero and where you get none of the coefficients zero.

• LASSO: Deriving the smallest lambda at which all coefficient are zero $$\lambda_{\text{all zero}} = \sqrt{k} \vert \vert X^T y\vert \vert_\infty$$

• What is the smallest $\lambda$ that gives a 0 component in lasso? $$\lambda_{\text{non zero}} = \frac{d}{n} \vert \vert X \vec{\beta}_{last,normalized} \vert \vert_2^2 $$ with $$\vec{\beta}_{last,normalized} = \frac{\vec{\beta}_{last}}{\sum \vec{\beta}_{last} \cdot sign(\hat{\beta})} $$ and $$\vec{\beta}_{last} = - (X^TX)^{-1} \text{sign} (\hat{\beta}) $$

---

A demonstration of the above formula's with some code

library(lars)

### generate some data
set.seed(1)
n = 50
m = 20
X = matrix(rnorm(m*n),n)
y = rnorm(n)

### perform lasso
mod = lars(X,y, intercept = 0, normalize = 0)    
nonzero = rowSums(mod$beta^2 > 0)
lambda = mod$lambda
lambda = c(lambda[1]+1,lambda) # add one additional point

### plot the number of nonzero estimated coefficients
### as function of lambda
plot(lambda,nonzero, log ="x", type = "s")

### upper bound above which all coefficients are zero

l_max = max(abs(t(X) %*% y))
lines(l_max*c(1,1), c(-1,m+1), lty = 2, col = 2)

### lower bound below which all coefficients are non-zero

mod = lm(y~0+X)
beta = mod$coefficients
bl = - solve(t(X)%*%X) %*% sign(beta)
bln = bl/sum(bl*sign(beta))
br = beta/bln
d = min(br[br>0])
l_min = sum((X %*% bln)^2)*d
lines(l_min*c(1,1), c(-1,m+1), lty = 2, col = 2)

---

A simple algorithm to compute the path of solutions to LASSO is least angle regression.

A difficulty to compute directly the value of the penalty $\lambda$ where a particular coefficient becomes non-zero is that it depends on which other coëfficiënts are already non-zero.

This is because of correlations between the coefficients, which makes that the increase of one coefficient can reduce the effect of another. For example one may get even a situation where a coefficient reduces in magnitude as we decrease the penalty (Why under joint least squares direction is it possible for some coefficients to decrease in LARS regression?). Sometimes a coefficient can change from positive to negative (cross zero) as we change the penalty parameter (https://stats.stackexchange.com/a/594633/) and the number of non-zero components as function of the penalty parameter can be a non-monotonic function.

It is easy to compute the points in the paths when either:

• We only look at the beginning or the end, as is done in this answer.

• When there are no correlations between the regressors, as is done in the answer by EdM.

Answer 2

In the case of an orthonormal model matrix, Section 2.9 of Statistical Learning with Sparsity (SLS) shows one pretty simple result: if the absolute value of a predictor's least-squares coefficient is greater than $\lambda$, it will be retained. Otherwise, it won't.

Beyond that, when you get into the $p>n$ regime or have correlated predictors, I don't know that there's much to say about the relationship between the number of predictors maintained and the penalty term, even if you've scaled the predictors to get around the measurement-unit problems pointed out by @whuber in comments.

What you can say, according to Section 2.5 of SLS, is that for any value of $\lambda$ the number of retained coefficients "is an unbiased estimate of the degrees of freedom" used in fitting the model, taking the penalization into account.

Your invocation of eigenvalues of the model matrix doesn't seem at first to make much sense for lasso, but it's quite relevant to ridge regression. As shown on this page and several others on this site, ridge regression can be thought of as a smooth version of principal components regression (PCR). In PCR, PCs are included in an all-or-none fashion; in ridge, all PCs are included but those with small singular values are penalized more than those with large ones.