0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Hi: I can't answer your question directly but the whole point of the lasso is to obtain lots of zeros so, if gradient descent can't do that, you probably don't want to use it. $\endgroup$ – mark leeds May 1 '18 at 5:01
  • 1
    $\begingroup$ If you are doing least squares, use the proximal gradient method. en.wikipedia.org/wiki/Proximal_gradient_methods_for_learning $\endgroup$ – user18764 May 1 '18 at 13:29
  • $\begingroup$ @ mark leeds. Yes, I agree. However, there many sparsifying algorithms such as automatic relevance determination (also known as Sparse Bayesian Learning SBL or Normals with unknown Variance NuV, etc.) where one does not obtain hard-zeros either. Some sort of hard-thresholding at the end can then (if desired) be applied to get hard zeros. $\endgroup$ – Effesian May 2 '18 at 11:10
  • $\begingroup$ @Effesian. Thanks for wisdom. You know way more about this than I do. I just wasn't sure if you knew about the zeros which is why I mentioned it. $\endgroup$ – mark leeds Jun 2 '18 at 21:19
1
$\begingroup$

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 Notes which discuss gradient descent, sub-gradient descent and ADMM.

$\endgroup$
  • $\begingroup$ Fantastic answer! Thank you very much! Regarding point 2, Huber functions, how exactly would you use them? Would you have, let's say a quadratic data fit term and a Huber loss as regularizer or would you use the Huber loss as commonly done in robust statistics on the data fit term. In either case one would not get sparsity, right? Probably having a Huber-loss as regularizer would do something in the direction of the LASSO without generating hard zeros though $\endgroup$ – Effesian May 2 '18 at 7:53
  • $\begingroup$ Instead of the pure $l_1$ norm you would use a Huber norm as a regularizer. The Huber function is equivalent to the $l_1$ norm for large values, but for small values it is quadratic. Thus, it is differentiable everywhere. For an example see "An Alternative Robust SL0 Based on Recursive Huber Stochastic Estimation Technique in Frequency Domain" from 2012. For other smoothing approaches you could look at SL0 - which uses a smooth approximation to $l_0$ instead of $l_1$. Both techniques yield sparse solutions. $\endgroup$ – David May 2 '18 at 13:33
  • $\begingroup$ Here's a link to an open access paper that uses Huber functions for sparse reconstruction Huber Paper. $\endgroup$ – David May 2 '18 at 13:39
2
$\begingroup$

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:

enter image description here

Implementation is included so you can see how it works.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.