Coordinate descent on objective function with discontinuous derivative

Question

I'm trying to perform a customized nonlinear regression. I'm using the Linex loss function instead of least-squares. I'm doing LASSO-style regularization, so that my objective function has abs() terms.

I think the resultant objective function, $f(\theta)$, is different enough from a vanilla regression so as to make direct use of standard libraries impossible. So I plugged into Matlab's all-purpose fmincon() instead. I haven't yet derived a gradient/Hessian to pass in but I plan to.

However, this fails to produce the desired LASSO-like behavior of setting coefficients to exactly 0. It's not hard to see why, as I haven't told the optimization routine about the derivative discontinuities resulting from the abs() terms.

My question is whether there is a simple way to incorporate the fact that $\partial f/\partial \theta_i$ is undefined at $\theta_i=0$ for some $i$ into a general purpose optimization routine, or whether I have to implement the whole optimization routine from scratch.

(I am new to Matlab and to custom optimization in general. Please let me know if I have some obvious fundamental misunderstandings here. Thanks!)

Answer 1

I solved my problem by simply writing a custom version of fminunc() that accepts auxiliary discontinuity information.

fminunc() accepts the gradient as a function that returns an $n\times 1$ matrix g such that g(i,1) equals $\partial f/\partial x_i$. Problem with my function was that $\partial f/\partial x_i$ was not defined at some points due to abs() terms.

My custom method accepts the gradient as a function that returns an $n\times 2$ matrix g' such that g'(i,1) equals the limit of $\partial f/\partial x_i$ from the negative direction, and g'(i,2) equals the limit of $\partial f/\partial x_i$ from the positive direction. It also accepts a list of hyperplanes along which the derivative is not defined.

It then performs coordinate descent with Newton step size. When determining which coordinate to descend along, it considers a move in the negative direction and a move in the positive direction separately. When performing a step, the step is truncated if necessary so as to not cross a hyperplane of discontinuity.

This works.

Answer 2

You haven't said whether your problem is actually constrained or is simply an unconstrained problem. I'll assume in the following that you've got an unconstrained problem in which you've moved the regularization into the objective function rather than making it a constraint.

All of the algorithms used by fmincon (there are several options that you can pick from or just let it pick a method by default) assume that the objective function is differentiable and then either use a user supplied gradient or compute finite difference approximations to the gradient. They don't have good theoretical properties for non-smooth objective functions like yours and generally shouldn't be used in this way.

Since your objective is mostly OK, except for those points where one of the abs() functions is at 0, chances are that fmincon will perform reasonably well. However, it probably won't be able to do a very good job with those components of the solution that should be 0.

If the solutions you're getting are basically good enough, then you might be able to simply round these small components of the solution down to 0 and call it a day.

If fmincon and thresholding the solution just isn't doing the job, then you should start to look at methods for non-differentiable convex optimization. These methods typically require a subgradient (which should be easy to compute for your problem.)

We could probably provide a more specific answer if you'd provide more information about your problem. What exactly is your objective function? How many variables are involved?