Quadratic approximation of L1 regularized cost function

Question

I'm reading the Deep Learning book of Goodfellow, but I fail to see why minimization of (7.22) gives (7.23). I tried to compute the gradient w.r.t. the $w_{i}$ and set this to zero, but it doesn't give me (7.23).

Thanks for your help!

Answer 1

The analysis becomes a little bit hairy because of the discontinuous derivative of the L1 penalty. There may be a better way of phrasing the argument, but here's something.

Taking the derivative of $|w_i|$ gives $\operatorname{sgn}(w_i)$, unless $w_i=0$ which we will take as a special case.
In the main case, when $w_i\neq0$, taking the derivative w.r.t. $w_i$ equal to zero gives: $$\begin{align*} H_{ii}(w_i-w_i^*) + \alpha \operatorname{sgn}(w_i) & = 0 \\ \Longrightarrow w_i &= w_i^* - \frac{\alpha \operatorname{sgn}(w_i)}{H_{ii}}. \end{align*}$$

Now for a trick. From the original loss formulation (7.22), it's clear that the optimum $w_i$ will have the same sign as $w_i^*$ (or is zero): otherwise, switching signs decreases the first term and doesn't change the second term inside the summation. So we have $$\begin{align*} w_i &= w_i^* - \frac{\alpha \operatorname{sgn}(w_i^*)}{H_{ii}} \\ &= \operatorname{sgn}(w_i^*) \left( |w_i^*| - \frac{\alpha}{H_{ii}} \right). \end{align*}$$ And again, knowing that $w_i$ and $w_i^*$ must share sign, we must have that $|w_i^*|-\frac{\alpha}{H_{ii}}\geq0$. If not, then this is not a location of zero-derivative, and we have to look to our other case. In that case, simply $w_i=0$, and we can tack that on as a separate case here using the maximum given in the text. (We should also confirm that $w_i=0$ is not the minimum when $|w_i^*|-\frac{\alpha}{H_{ii}}>0$, which is easy to do.)