# Quadratic approximation of L1 regularized cost function

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!

## 1 Answer

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, 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. 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.)