0
$\begingroup$

In orthogonal design of lasso, we get $\hat{\beta}_j^{\text{lasso}} = 0 \text{ if abs}(\hat{\beta}_j) \le \lambda /2$. WHY?

I've seen the answer and derived it myself, but don't know why.

We begin with definition of lasso, $$\hat{\beta}^{\text{lasso}} = \underset{x} {\arg\min} \sum_{i=1}^{n} ( y_i - \sum_{j=1}^{p}\beta_{ij}x_{ij} )^2 + \lambda \sum_{j=1}^{p} |\beta_j| $$

In orthogonal design case where $X^T X= I$, $\hat{\beta} = (X^TX)^{-1}X^{T}y = X^Ty$

\begin{align} L(\beta, \lambda) & = \sum_{i=1}^{n} ( y_i - \sum_{j=1}^{p}\beta_{ij}x_{ij} )^2 + \lambda \sum_{j=1}^{p} |\beta_j| \\ & = (Y - X \beta)^T(Y - X \beta) + \lambda \mathbf{I}_p \text{ abs}(\beta) \\ & = Y^TY -2\hat{\beta}^T\beta + \beta^T \beta+ \lambda \mathbf{I}_p \text{ abs}(\beta) \\ & = Y^TY + \sum_{j=1}^{p} L_j(\beta_j, \lambda) \end{align}

where $L_j(\beta_j, \lambda) = -2 \hat{\beta}_j \beta_j + 2\beta^2_j + \lambda \text{ abs}(\beta_j)$.

Leave aside $\beta_j=0$, take dereivative w.r.t. $\beta_j$ for abs$(\beta_j) > 0$, $$\frac{L_j(\beta_j, \lambda)}{\partial \beta_j} = -2 \hat{\beta}_j + 2\beta_j + \lambda \text{ sign}(\beta_j)$$

and $\hat{\beta}^{\text{lasso}}$ is either zero or solve, $$\beta_j + \lambda \text{ sign}(\beta_j) / 2 = \hat{\beta}_j,$$

which is, $$ \hat{\beta}^{lasso}_j = \begin{cases} \hat{\beta}_j - \lambda/2, & \text{if } \hat{\beta}_j > \lambda/2\\ \hat{\beta}_j + \lambda/2, & \text{if } \hat{\beta}_j < -\lambda/2 \end{cases} $$

My question is the following derivation,

If abs$(\hat{\beta}_j) \le \lambda / 2$, we get $$L_j(\beta, \lambda) = -2 \hat{\beta}_j \beta_j + 2\beta^2_j + \lambda \text{ abs}(\beta_j) \ge -\lambda \text{ abs}(\beta_j) + \lambda \text{ abs}(\beta_j) \ge 0 = L_j(0, \lambda)$$ and, we can tell $\hat{\beta}_j^{\text{lasso}} = 0 \text{ if abs}(\hat{\beta}_j) \le \lambda /2$ (Why? How can you tell?)

Why $\mathbf{\hat{\beta}_j^{\text{lasso}} = 0}$? The explanation of $L_j(\beta_j, \lambda) \ge L_j(0, \lambda)$ does not seem to justify the reason.

$\endgroup$
4
$\begingroup$

Your derivation is not really precise, you are not really taking the derivative, but the subderivative, the function $|x|$ is not differentiable when $x = 0$. The subderivative $s$ of the absolute value when $x =0$ is $s\in [-1, 1]$

Thus, the conditions you derived are for the case where $\hat{\beta}^{lasso}_j \neq 0$ where indeed the subdifferential of the absolute value is equal the sign. But now consider the case $\hat{\beta}^{lasso}_j = 0$. By the KKT conditions, this will happen when $-\hat{\beta}_j^{ols} + s\frac{\lambda}{2} = 0$ which implies $|\hat{\beta}_j^{ols}| \leq \frac{\lambda}{2}$, since $s\in [-1, 1]$ when $\hat{\beta}^{lasso}_j = 0$.

The LASSO problem

For the sake of completeness I will write down the the lasso problem here. Our goal is to minimize

$$\min_{\beta} || Y - X\beta||_2^2 + \lambda||\beta||_1$$

where $||\cdot||_1$ is the $l_1$ norm. This a convex optimization problem, and the optimum is characterized by the KKT conditions:

$$ -2X'(Y - X\beta) + \lambda s = 0 $$

where $s$ is the subgradient of the $l_1$ norm, that is, $s_j = sign(\beta_j)$ if $\beta_j \neq 0$ and $s_j \in [-1, 1]$ if $\beta_j = 0$.

In the orthonormal case, $X'Y = \hat{\beta}^{OLS}$ and $X'X = I$, simplifying this to:

$$ -2\hat{\beta}^{OLS} +2\beta + \lambda s = 0 $$

Thus, consider the case where the solution would be $\beta_j = 0$. For this to be true we must have that $-2\hat{\beta}_j^{OLS} + \lambda s_j = 0$ which implies $|\hat{\beta}_j^{OLS}| \leq \frac{\lambda}{2}$, since $s_i \in [-1, 1]$. Since this a convex program, KKT is sufficient, and the condition works both ways, that is, $|\hat{\beta}_j^{OLS}| \leq \frac{\lambda}{2} \implies \beta_j = 0$

$\endgroup$
  • $\begingroup$ I renamed loss function S to L, so the notation more consistent. But, why is $L \in [-1, 1]$? Which step of the derivation are you referring to? $\endgroup$ – user13985 Jan 15 '18 at 19:21
  • 3
    $\begingroup$ The absolute value does not have a derivative when $x =0$. Recall that a derivative is the slope of the tangent line and at zero the absolute value has a "corner", you might want to check this (math.stackexchange.com/questions/991475/…). But we can extend the idea to subderivatives, and in this case it's not a single number, but a set, consisting of the slope of all lines below the function that touches the point. You might want to check this see.stanford.edu/materials/lsocoee364b/… $\endgroup$ – Carlos Cinelli Jan 15 '18 at 19:25
  • $\begingroup$ The part of the derivation I'm referring to is $-2 \hat{\beta}_j + 2\beta_j + \lambda \text{ sign}(\beta_j)$, where this only true for $\beta_j \neq 0$. For the case where $\beta_j = 0$, which is the case of your doubt, this should read $-2 \hat{\beta}_j + \lambda s$ where $s$ is the subdifferential of the absolute value at $0$, which is $[-1,1]$. $\endgroup$ – Carlos Cinelli Jan 15 '18 at 19:46
  • $\begingroup$ I was reading that this $L_j(\beta, \lambda) = -2 \hat{\beta}_j \beta_j + 2\beta^2_j + \lambda \text{ abs}(\beta_j) \ge -\lambda \text{ abs}(\beta_j) + \lambda \text{ abs}(\beta_j) \ge 0 = L_j(0, \lambda)$ implies $\hat{\beta}_j^{lasso} = 0$. Why is that? $\endgroup$ – user13985 Jan 15 '18 at 20:19
  • $\begingroup$ I'm still reading your explanation with the KTT condition, which I think is different from my derivation? $\endgroup$ – user13985 Jan 15 '18 at 20:22

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.