Gradient Descent with Lasso¶
Definition¶
The issue with gradient descent on the l1 regularizer (lasso), is that it isn't differentiable at 0. (see the graph of Laplace Distribution to understand why).
Thus, we introduce the idea that we use gradient descent for the smooth component of the optimization (the error term \(||\mathbf{Xw-y}||^2_{2}\)), and for \(\mathbf{w}\) values that are close to zero, we set them to zero.
This means that each time we use gradient descent to update \(\mathbf{w}\), we may stray away from a Sparse Solution, but the proximal operator will bring us back into the space of sparse solutions.
The proximal operator for l1 is applies element-wise to \(\mathbf{w}\), so with each step-size \(\eta\) and regularization parameter \(\lambda\):
\[
\text{prox}_{\eta \lambda l_{1}}(w_{j}) = \begin{cases}
w_{j}- \eta \lambda & \text{if } w_{j} > \eta \lambda \\
0 & \text{if } |w_{j}| \leq \eta \lambda \\
w_{j} + \eta \lambda & \text{if } w_{j} < - \eta \lambda
\end{cases}
\]