Solving LASSO ($ {L}_{1} $ Regularized Least Squares) with Gradient Descent

Question

To the best of my knowledge, state of the art methods for optimizing the LASSO objective function include the LARS algorithm and proximal gradient methods.

I was wondering however, if the LASSO objective function $$ ||y-Ax||_2^2 + \lambda ||x||_1$$ can be optimized using (vanilla) gradient descent?

I know that the 1-norm is not differentiable at zero, but numerically one is never exactly at zero. Therefore the gradient exists at each iteration point $x^{(k)}$ and I do not really need to resort to subgradients.

Unlike for the L2-penalized least squares, the gradient descent step would of course need a decreasing step size and would not yield exact zeros.

Can this method be called gradient descent or would it be better to call it subgradient descent or something else?

Many thanks!

Answer 1

Due to the non-smoothness of the $l_1$ norm, the algorithm is called subgradient descent. Because the you are looking for a solution that has a lot of zeros in it, you are still going to have to evaluate sub-gradients around points where elements of $\mathbf{x}$ are zero. In fact most of the algorithms effectively treat elements below a certain threshold as 0 - see Soft Thresholding or Shrinkage based algorithms.

The convergence rate on gradient descent is $O(1/\epsilon)$ over the convex class, differentiable functions with Lipschitz gradients. Over the same class, sub-gradient methods have $O(1/\epsilon^2)$ convergence rate.

There are a couple of ways of the algorithms typically progress:

1. Proximal algorithms - specializing in optimization of the form $f(x) +g(x)$ , where $f(x)$ is smooth and $g(x)$ is not.
2. Smoothing algorithms - Replace the $l_1$ norm with a function that is smooth. See Huber functions for example.
3. Project Gradient
4. Introduce an equivalent problem with a constraint. This tends to lead to Augmented Lagrangians and the Alternating Direction Method of Multipliers (ADMM) methods. These are just a subset of the most common technique; there are many others.

Here is a link to some lecture notes from Ryan Tibshirani's course - Convex Optimization: Fall 2019 which discuss gradient descent, sub-gradient descent and ADMM.

Answer 2

It can easily solved by the Gradient Descent Framework with one adjustment in order to take care of the $ {L}_{1} $ norm term.

Since the $ {L}_{1} $ norm isn't smooth you need to use the concept of Sub Gradient / Sub Derivative.
When you integrate Sub Gradient instead of Gradient into the Gradient Descent Method it becomes the Sub Gradient Method.

In the case of the $ {L}_{1} $ norm the Sub Gradient is given by the function $ \operatorname{sign} \left( \cdot \right) $.
In this context it works on vector in Element Wise manner.

So the Pseudo Code (MATLAB) would look something like:

for ii = 1:numIterations
    vG = (mA.' * (mA * vX - vY)) + (paramLambda * sign(vX)); %<! Sub Gradient
    vX = vX - (stepSize * vG); %<! Sub Gradient Update
end

Yet, As mentioned by @David, this is not a modern way to solve this problem.
Iteration wise it seems that Coordinate Descent is the fastest method for solving the LASSO ($ {L}_{1} $ Regularized Least Square) problem.

You may look at a project I created (${L}_{1}$ Regularized Least Squares - Solvers Analysis) which compares many method for that optimization problem:

Implementation is included so you can see how it works.