Why proximal gradient descent instead of plain subgradient methods for Lasso? I was thinking to solve Lasso via vanilla subgradient methods. But I have read people suggesting to use Proximal gradient descent. Can somebody highlight why proximal GD instead of vanilla subgradient methods be used for Lasso?
 A: An approximate solution can indeed be found for lasso using subgradient methods. For example, say we want to minimize the following loss function:
$$f(w; \lambda) = \| y - Xw \|_2^2 + \lambda \|w\|_1$$
The gradient of the penalty term is $-\lambda$ for $w_i < 0$ and $\lambda$ for $w_i > 0$, but the penalty term is nondifferentiable at $0$. Instead, we can use the subgradient $\lambda \text{sgn}(w)$, which is the same but has a value of $0$ for $w_i = 0$.
The corresponding subgradient for the loss function is:
$$g(w; \lambda) = -2X^T (y - X w) + \lambda \text{sgn}(w)$$
We can minimize the loss function using an approach similar to gradient descent, but using the subgradient (which is equal to the gradient everywhere except $0$, where the gradient is undefined). The solution can be very close to the true lasso solution, but may not contain exact zeros--where weights should have been zero, they make take extremely small values instead. This lack of true sparsity is one reason not to use subgradient methods for lasso. Dedicated solvers take advantage of the problem structure to produce truly sparse solutions in a computationally efficient way. This post says that, besides producing sparse solutions, dedicated methods (including proximal gradient methods) have faster convergence rates than subgradient methods. He gives some references.
