Consider Lasso problem with the Lasso parameter $\lambda$. Suppose that the set of active predictors is unchanged for $\lambda_0 \geq \lambda \geq \lambda_1$. Show that there is a vector $\gamma_0$ such that $$\hat{\theta}(\lambda) = \hat{\theta}(\lambda_0) - (\lambda - \lambda_0)\gamma_0.$$ Thus, the Lasso solution path is linear as $\lambda$ ranges from $\lambda_0$ to $\lambda_1$.

Background: Let $A$ be a real $m \times n$ matrix. The Lasso optimization problem is $$ \text{minimize} \quad \frac12 \| Ax - b \|_2^2 + \lambda \| x \|_1 $$ The optimization variable is $x \in \mathbb R^n$.

The $\ell_1$-norm regularization term encourages $x$ to be sparse, so Lasso is useful for finding a sparse vector $x$ that satisfies $Ax \approx b$. The parameter $\lambda > 0$ controls how sparse the solution to the Lasso problem is.

I am not sure how to proceed with this problem, or what technique to use in order to show that the solution path is linear.

  • $\begingroup$ Hint: the 1-norm is a linear function on the relevant interval. $\endgroup$ – LinAlg Oct 16 '18 at 1:01

The question is not $\hat{\lambda}=\hat{\lambda}_0-(\lambda-\lambda_0)\gamma_0$, it should be $\hat{x}(\lambda) =\hat{x}(\lambda_0)-(\lambda-\lambda_0)\gamma_0$. Here $\hat{x}(\lambda)$ is the minimizer, which is independent the parameter $\lambda$.

  • $\begingroup$ Okay. Nonetheless, how does one go about showing the existence of such a vector $\gamma_0$ that satisfies $\hat{x}(\lambda)=\hat{x}(\lambda_0) - (\lambda-\lambda_0)\gamma_0$? $\endgroup$ – Dragonite Oct 15 '18 at 19:58

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.