The experiments section is pretty clear in what potential applications can be, e.g. "optimizing directly for top-k classification loss" or "label ranking via soft Spearman’s rank correlation coefficient". In Google's case, there are pretty clear applications towards web search (top-k results, classification = do you click or not), and things like entity labeling (e.g. what label should we assign to a news story).
That's akin to saying that minimizing cross entropy empirically maximizes accuracy but there's no strong theoretical backing for that either
LambdaRank is one way of getting a smooth differentiable approximation to NDCG by slapping a sigmoid somewhere. The paper we're discussing now offers another way. Hard to say which way would turn out to be empirically better on problems of practical significance without actually experimenting.
What they want to do (eventually) is propose loss functions for machine learning. NOT algorithms for sorting per se.
The consider ML models of the form f: x --> r that take features x to some permutation or list of ranks. For example in their CIFAR experiments, I think (correct me if I'm wrong) that x is an image and there are n possible labels, e.g. "dog, cat, giraffe, ...", and given x, f(x) should rank the labels from most likely to least likely.
Now, how do we train such a model f? We use empirical risk minimization over some labeled dataset, e.g. a collection of pairs (x,y) where x is the image and y is a label.
So we train our neural net to become the f that minimizes average Loss(f(x), y) over pairs x,y.
But what Loss function do we use? That's what this paper is ultimately about. And they claim theirs is efficient to compute and produces good hypotheses f.
However I must admit that I do not fully grasp the implications of this paper. Why do we really need differentiable sorting for deep learning in the first place? What new possibilities open up as a result? My best uneducated guess is that the gradients produced by differentiable sorting are more informative than regular piecewise sorting, and this allows the gradient descent to progress faster, therefore training faster. (Think about how you can know an entire analytic function can be completely known from any small neighborhood. Are these sorting functions analytic too?) My intuition tells me that the derivatives produced with this technique allow the optimizer to see true gradients across classes.
Are higher order derivatives also meaningful here?