SGD and quantile regression

Question

It is my understanding that the quantile loss is not differentiable (at 0) so base gradient descent cannot be used.

However, Vowpal Wabbit which is an SGD-based learner very much includes quantile regression, and calculates the derivative as:

float e = label - prediction;
if(e == 0) return 0;
return e > 0 ? -tau : (1-tau);

Am I missing something here? Is this an accepted way to use SGD with QR?

Answer 1

Many things in applied statistical computing (and computer science in general) is based on approximations. In case of absolute loss function, it has constant decrease rate for loss < 0 and constant increase rate at loss > 0, it neither increases, nor decreases at zero. That's about theory, but in practice, it is unlikely that you will hit exact zero. Moreover, it is not differentiable at zero, but since it is neither increasing, nor decreasing, 0 is a reasonable value to use if we need to choose something for our algorithm to work. If error is equal to zero, then we are done with training and not need to update the weights any more, so this makes perfect sense.

Answer 2

You can use Gradient Descent in quantile-regression. I experimented with some toy data (both 1D and 4D) and this works fine and gives similar results to the linear programming methods (simplex, interior-point) and to the IRLS method.

The objective in (simple=1D) 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 then sum on the data, and so you can perform 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.