You're right, the paper's messaging is very confusing. What they want to do (eventually) is propose loss functions for machine learning. NOT algorithms for sor

You're right, the paper's messaging is very confusing. 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.