Why can't the gradient descent optimize a quantile regression loss?

Question

Ok, so this may be a silly question, I know the literature recommends at length the simplex or interior point method to optimize a quantile regression problem. However I cannot figure out why a simple (stochastic or not) gradient descent isn't able to minimize the quantile loss which as a reminder looks like this.

Of course the gradient isn't defined at 0, but we can set it to 0 and in real life on large datasets with numerous dimensions, especially considering Doubles are rarely precisely equal with enough precision, it seems like a non issue.

I decided to experiment on a dataset and indeed it doesn't seem to work... I just can't figure out an intuition as to why. Can anybody help?

Follow up question, does anyone know of a way/library to fit a quantile regression with an easily distributable algorithm?

Answer 1

The intuition is as you say there is no gradient at $0$ for the quantile loss. Therefore any sub-gradient that you pick will be unstable. In general the way around this is to construct a Minorizing function and use an MM algorithm to fit the quantile regression. As far as I can tell spark.mllib does not have quantile regression support as of now.

Answer 2

You can. I don't know which data you experimented with, but on my toy data (both 1D and 4D) this works fine and give similar results to the linear programming methods (simplex, interior-point) and to the IRLS method.

The objective in (simple) quantile regression is:

$$ \mathcal L= \sum_i \rho_\alpha(y_i-\beta_0-x\cdot\beta_1)$$

where $\rho_\alpha(y_i-\beta_0-x\cdot\beta_1)= \begin{cases} (\alpha-1)(y_i-\beta_0-x\cdot\beta_1), &y_i-\beta_0-x\cdot\beta_1<0 \\ \alpha(y_i-\beta_0-x\cdot\beta_1), & y_i-\beta_0-x\cdot\beta_1 \ge 0 \end{cases} $

If we take the gradient w.r.t. say $\beta_0$, you get $1-\alpha$ in the 1st case, and $-\alpha$ in the 2nd case. You can evaluate the conditions given some initial $\beta$'s, and so you can preform gradient-descent.

Here is how I defined the quant_loss in python (tau replacing $\alpha$):

def quant_loss(y_hat, y):
    e = y - y_hat
    loss = (tau-1)*e*(e<0) + tau*e*(e>=0)
    return loss.sum()

You can check out my code implementation in Python on GitHub here.