0
$\begingroup$

For the lasso problem $$ \hat \beta(\lambda) = \underset{\beta \in \mathbb{R}^p}{\operatorname{argmin}}\|Y - X \beta\|_2^2 + \lambda \|\beta\|_1, $$ where $Y$ is $p \times 1$, $X$ is $n \times p$, it is clear that when $p < n$, we have $$ \hat \beta(0) = (X^TX)^{-1}X^TY. $$ The lars algorithm with the lasso modification returns a sequence of tuning parameter values $\lambda_1 >\dots>\lambda_M >0$ along with the corresponding lasso solutions $\hat \beta(\lambda_1),\dots,\hat\beta(\lambda_M)$ as well as, in the case in which $p < n$, the least-squares estimator $\hat \beta(0)$.

Now, in the case in which $p\geq n$, the algorithm likewise returns a sequence of tuning parameter values $\lambda_1 >\dots>\lambda_M >0$ along with the corresponding solutions $\hat \beta(\lambda_1),\dots,\hat\beta(\lambda_M)$ as well as another value of the estimator $\hat \beta(?)$.

My question is: to what value of the tuning parameter $\lambda$ does this additional value of the estimator correspond when $p \geq n$? In the $p<n$ case it corresponds to $\lambda = 0$, but in the $p \geq n$ case, the lasso estimator is undefined for $\lambda = 0$, so it cannot correspond to this. If it corresponds to some other value of $\lambda$, why is this value not returned?

The R code below gives an example:

library(lars)

# Generate some data with n > p
n <- 12
p <- 10
p0 <- 3
X <- scale(matrix(rnorm(n*p),n,p), center=TRUE)
beta <- c(rep(1,p0),rep(0,p-p0))
Y <- X %*% beta + rnorm(n)

# Run the lars algorithm
lars.out <- lars(y = Y, x = X, type = "lasso", intercept = FALSE)

# View the solutions at knot points in the path
coef(lars.out)

# Print the sequence of lambda values. 
# There is no lambda value corresponding to the final row:
lars.out$lambda

# Compute the least-squares estimator: 
# It is the same as the final row of coef(lars.out)
solve(t(X)%*%X)%*%t(X)%*%Y

So far so good. But if we consider the case in which $p \geq n$ we have

# Generate some data with n >= p
n <- 8
p <- 10
p0 <- 3
X <- scale(matrix(rnorm(n*p),n,p), center=TRUE)
beta <- c(rep(1,p0),rep(0,p-p0))
Y <- X %*% beta + rnorm(n)

# Run the lars algorithm
lars.out <- lars(y = Y, x = X, type = "lasso", intercept = FALSE)

# View the solutions at knot points in the path
coef(lars.out)

# Print the sequence of lambda values. 
# There is no lambda value corresponding to the final row:
lars.out$lambda

How is the last row of coef(lars.out) computed?

$\endgroup$
1
$\begingroup$

In short, the answer is that it's the minimum $\ell_1$ norm least squares estimator. This was shown in Lemma 7 of:

Tibshirani, R. J. (2013). The lasso problem and uniqueness. Electronic Journal of Statistics, 7, 1456-1490.

In order to quickly see why, all we need to take for granted is that the LARS (with lasso modification) coefficient path is continuous and is supported at $\lambda = 0$. Write $\hat{\beta}_\lambda$ as the LARS estimator for regularization parameter $\lambda$ in the lasso problem with objective $\|y - X \beta\|_2^2 + \lambda \|\beta\|_1$. When $\lambda = 0$, we know that $\hat{\beta}_0$ is a least squares estimator. Which one, though??

Let $\tilde{\beta}$ be any least squares estimator and $\lambda \geq 0$. From the definition, we know that $$\|y - X \hat{\beta}_\lambda\|_2^2 + \lambda \|\hat{\beta}_\lambda\|_1 \leq \|y - X \tilde{\beta}\|_2^2 + \lambda \|\tilde{\beta}\|_1.$$ However, since the least squares estimator provides the closest fit, we know that $\|y - X \hat{\beta}_\lambda\|_2^2 \geq \|y - X \tilde{\beta}\|_2^2,$ which makes $$\|\hat{\beta}_\lambda\|_1 \leq \|\tilde{\beta}\|_1.$$ Taking a limit $\lambda \to 0$ of this inequality, we find that the LARS estimator $\hat{\beta}_0$ has $\ell_1$ norm no bigger than any least squares estimator.

$\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.