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

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?

• Re parallelization - this package, cran.r-project.org/web/packages/cqrReg/index.html, presents an ADMM algo to solve quantile regression, and the ADMM algo can be parallelized... Commented Feb 21, 2019 at 13:31
• Note that there are also smooth approximations of the quantile regression objective function that enable one to use gradient descent - see link.springer.com/article/10.1007/s13042-011-0031-2 and R package github.com/KarimOualkacha/cdaSQR Commented Feb 21, 2019 at 13:52
• Commented Feb 21, 2019 at 13:53
• I realize this is an old question, but... Did you try diminishing step sizes?
– bean
Commented Aug 16, 2019 at 14:11

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.

• Why will any sub-gradient be unstable? Because of chattering near the minimum? Commented Jun 23, 2020 at 15:05
• Also, what is a minorizing function? Commented Jun 23, 2020 at 15:05
• @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/… Commented Jun 23, 2020 at 15:25
• @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. Commented Jun 23, 2020 at 15:28

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.