$L^1$ Regularization

Question

Let $J(w)$ be some cost function. By adding $L^1$ regularization we get $$ \tilde{J}(w) = J(w) + \beta\sum_i|w_i| $$ To study the effect of $L^1$ regularization on the optimum weights, we can approximate $J(w)$ with a quadratic function: $$ \hat{J}(w) = J(w^*) + \frac{1}{2}(w-w^*)^T H(w^*)(w-w^*), $$ where $w^*$ is the minimum of $J$ and so the gradient is zero. According to the Deep Learning book (see pages 207-208) I'm reading, if we assume that $H = diag(\gamma_1,\ldots,\gamma_N)$, where each $\gamma_i>0$, then

the solution of the minimum of the $L^1$ regularized objective function decomposes into a system of equations of the form: $$ \tilde{J}(w) = \frac{1}{2}\gamma_i(w_i-w_i^*)^2 + \beta|w_i|. $$ It admits an optimal solution (for each dimension $i$), with the following form: $$ w_i = sign(w_i^*)\max(|w_i^*|-\frac{\beta}{\gamma_i},0). $$

I don't understand the quoted part. This is my starting point: $$ \tilde{J}(w) = J(w^*) + \frac{1}{2} \sum_i \gamma_i (w_i - w^*_i)^2 + \beta \sum_i |w_i| $$ Shouldn't we look for points where the gradient is zero? From $$ \frac{\partial\tilde{J}(w)}{\partial w_i} = \gamma_i (w_i - w^*_i) + \beta sign(w_i) = 0, $$ I get $$ w_i = w^*_i - \frac{\beta}{\gamma_i}sign(w_i). $$ What am I doing wrong?

Answer 1

$w_i=w^*_i-\frac{\beta}{\gamma_i}sign(w_i)$ is correct for $w_i\ne 0$ (at zero the gradient is undefined)

Either $sign(w_i)=sign(w_i^*)$ ( which corresponds to $|w^*_i|>\frac{\beta}{\gamma_i}$)and there is a solution to the gradient=0 equation, or there is no solution to gradient =0.

Since $\tilde J(w)$ is continuous at 0 and the gradient at $0^+$ and $0^-$ changes sign when $|w^*_i|\le\frac{\beta}{\gamma_i}$, you have a minimum at 0 in that case, so put that all together and you get the answer in the text book.