6
$\begingroup$

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.

Quantile loss

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?

$\endgroup$
4

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Why will any sub-gradient be unstable? Because of chattering near the minimum? $\endgroup$ Jun 23, 2020 at 15:05
  • $\begingroup$ Also, what is a minorizing function? $\endgroup$ Jun 23, 2020 at 15:05
  • $\begingroup$ @RylanSchaeffer RE: what is minorizing function? probably would help to read => en.wikipedia.org/wiki/MM_algorithm which also describes the algorithm. Or the tutorial which describes the approach for quantiles (but not regression IIRC) pdfs.semanticscholar.org/cc21/… $\endgroup$ Jun 23, 2020 at 15:25
  • $\begingroup$ @RylanSchaeffer RE: Why will any sub-gradient be unstable? Because of chattering near the minimum? I'm not sure what you mean by chattering but you can visually intuit the reason by looking at the figure in your question and consider the discontinuous point where the horizontal and vertical axis (depicted) meet. Consider the derivative as a tangent line and the sub-gradient as the set of all tangent lines. The instability comes from the non-uniqueness. Basically, you can pick any tangent line as a sub-gradient, with a deterministic code it may appear stable, but is an artifact of code. $\endgroup$ Jun 23, 2020 at 15:28
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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