STOCHASTIC OPTIMIZATION OF SORTING NETWORKS VIA CONTINUOUS RELAXATIONS
Sorting input objects is an important step in many machine learning pipelines. However, the sorting operator is non-differentiable with respect to its inputs, which prohibits end-to-end gradient-based optimization. In this work, we propose NeuralSort, a general-purpose continuous relaxation of the output of the sorting operator from permutation matrices to the set of unimodal row-stochastic matrices, where every row sums to one and has a distinct arg max. This relaxation permits straight-through optimization of any computational graph involve a sorting operation. Further, we use this relaxation to enable gradient-based stochastic optimization over the combinatorially large space of permutations by deriving a reparameterized gradient estimator for the Plackett-Luce family of distributions over permutations. We demonstrate the usefulness of our framework on three tasks that require learning semantic orderings of high-dimensional objects, including a fully differentiable, parameterized extension of the k-nearest neighbors algorithm.
After responses: I now understand the paper, and I believe it is a good contribution. 
================================================
At a high level, the paper considers how to sort a number of items without explicitly necessarily learning their actual meanings or values. Permutations are discrete combinatorial objects, so the paper proposes a method to perform the optimization via a continuous relaxation. 
This is an important problem to sort items, arising in a variety of applications, particularly when the direct sorting can be more efficient than the two step approach of computing the values and then sorting.
I like both the theoretical parts and the experimental results. In the context of ICLR, the specific theoretical modules comprise some cute results (Theorem 4; use of past works in Lemma 2 and Proposition 5). possibly of independent interest. The connections to the (Gumbel distribution <--> Plackett Luce) results are also nicely used. This Gumbel<-->PL result is well known in the social choice community but perhaps not so much in the ML community, and it is always nice to see more connections drawn between techniques in different communities. The empirical evaluations show quite good results.
However, I had a hard time parsing the paper. The paper is written in a manner that may be accessible to readers who are familiar with this (or similar) line of research, but for someone like me who is not, I found it quite hard to understand the arguments (or lack of them) made in the paper connecting various modules. Here are some examples:
- Section 6.1 states "Each sequence contains n images, and each image corresponds to an integer label. Our goal is to learn to predict the permutation that sorts these labels". One interpretation of this statement suggests that each row of Fig 3a is a sequence, that each sequence contains n=4 images (e.g., 4 images corresponding to each digit in 2960), and the goal is to sort [2960] to [0269]. However, according to the response of authors to my earlier comment, the goal is to sort [2960,1270,9803] to [1270,2960,9803]. 
- I did not understand Section 2.2.
- I would appreciate a more detailed background on the concrete goal before going into the techniques of section 3 and 4.
- I am having a hard time in connecting the experiments in Section 6 with the theory described in earlier sections. And this is so even after my clarifying questions to the authors and their responses. For instance, the authors explained that the experiments in Section 6.1 have \theta as vacuous and that the function f represents the cross-entropy loss between permutation z and the true permutation matrix. Then where is this true permutation matrix captured as an argument of f in (6)? Is the optimisation/gradients in (7) over s or over the CNN parameters?