3
$\begingroup$

This question already has an answer here:

It is given in the book Machine Learning A probabilistic Perspective, but i am not able to understand it. Can some one provide an explanation for that ?

I am not clear with the way sub gradient is defined and how is it helping in the optimization enter image description here enter image description here.enter image description here

$\endgroup$

marked as duplicate by kjetil b halvorsen, Peter Flom Sep 19 '17 at 22:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ The proof, such as it were, is in the pudding. I.e., a lot of numerical experience. That is not a rigorous proof that sparseness is always achieved. $\endgroup$ – Mark L. Stone May 21 '17 at 12:42
  • 1
    $\begingroup$ So there is no proof, just practical observations that say sparsity is achieved ? $\endgroup$ – Siddharth Shakya May 21 '17 at 13:01
  • 2
    $\begingroup$ I think there is a feeling or hope that L1 might induce sparsity, based on L0 really inducing sparseness and "closeness" of L1 to L0. And there is a large body of experience that it often (usually) does, at least to some extent. $\endgroup$ – Mark L. Stone May 21 '17 at 14:01
  • 1
    $\begingroup$ When I don't understand the proof I usually conclude that I don't need it $\endgroup$ – Aksakal Jul 10 '17 at 18:59
  • $\begingroup$ @MarkL.Stone To be sure that this is clear: the work that statisticians have put into the lasso has been related to understanding which model the lasso selects. It is rigorous and quick to show that that the lasso does induce sparsity (consider, for instance, having large tuning parameter as shown here: stats.stackexchange.com/questions/210040) $\endgroup$ – user795305 Jul 30 '17 at 23:11
7
$\begingroup$

Answer

As shown in my answer at http://stats.stackexchange.com/questions/210040/, the lasso estimator $$\hat\beta_\lambda = \arg\min_{\beta \in \mathbb{R}^p} \left\{ \|y - X \beta\|_2^2 + \lambda \|\beta\|_1 \right\}$$ equals zero if and only if $\lambda \geq \frac{1}{n} \|X^T y\|_\infty =: \lambda_\max$. This result does, in some sense, answer your question: we now know that for a large enough tuning parameter $\lambda$, the lasso estimator $\hat\beta_\lambda$ is fully sparse. On the other hand, we also know that there exists a least squares estimator $\hat\beta_0$ which is almost surely fully dense.

More

assumption: For convenience, let us assume that every estimator considered is unique. (If the estimators are not unique, all we've shown is that there exists at least one estimator that is sparse, which also answers the question.)

In light of this, we may be interested in knowing more about the possible sizes of the support of $\hat\beta_\lambda$ for $\lambda \in (0, \lambda_\max)$. In particular, we'll now answer whether it's true that for all $k \in \{0, 1, \dots, p\}$, there exists $\lambda$ so that $\mathrm{card} (\mathrm{supp} (\hat\beta_\lambda)) = k$. It turns out that the answer is (almost surely) yes! The best proof I can come up with relies on explicitly constructing the lasso solution. (If there's a better proof you know, please do comment!)

Since we've answered the other cases above, restrict $k \in (1, \dots, p-1)$. Write the knots of the lasso solution path as $0 \leq \lambda_1 \leq \dots \leq \lambda_q$. Let $\lambda_{r+1}$ be the largest knot so that $\mathrm{card}(\mathrm{supp}(\hat\beta_\lambda)) \leq k$ for all $\lambda > \lambda_{r+1}$. By definition, we know that a feature will leave the support at the knot $\lambda_{r+1}$. We will know show that exactly one will leave the support.

From KKT considerations (to be filled in later), we see that, for $\lambda \in [\lambda_r, \lambda_{r+1}]$, $$\hat\beta_\lambda^j = \hat\beta_{\lambda_r}^j + (\lambda_r - \lambda) e_j^T (X_S^T X_S)^{-1} z_S$$ for $j \in S$, and $\hat\beta_\lambda^j = 0$ for $j \not\in S$. Here $S = \mathrm{supp} (\hat\beta_{\lambda_r})$ and $z$ is the subgradient of the $\ell_1$ norm evaluated at $\hat\beta_{\lambda_r}$. Assuming that $j$ is one of the features that leaves the active set at the knot $\lambda_{r+1}$, we can set the above equation to zero and solve for $\lambda$ to find that $$\lambda_{r+1} = \lambda_r + \frac{\hat\beta_j^{\lambda_r}}{e_j^T (X_S^T X_S)^{-1} z_S}.$$ (Note that if the denominator were zero, then the $j^\textrm{th}$ feature could not be leaving the active set at the knot $\lambda_{r+1}$.) At this point, we see that the proof will conclude when it is shown that $$\lambda_j^\mathrm{update} := \frac{\hat\beta_j^{\lambda_r}}{e_j^T (X_S^T X_S)^{-1} z_S}$$ is distinct for each $j \in S$. However, the subgradient $z_S \in \{-1,1\}^{|S|}$, a finite set, and so it follows that under a continuous distribution on the response $y$, the update $\lambda_j^\mathrm{update}$ is almost surely unique for each $j \in S$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.