Stochastic Optimization of Sorting Networks via Continuous Relaxations

Aditya Grover, Eric Wang, Aaron Zweig, Stefano Ermon

Abstract

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. This relaxation permits straight-through optimization of any computational graph involving 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.

The Sorting Bottleneck

In deep learning, we rely on gradients to tell us how to tweak model parameters to improve performance. However, the standard sorting operator is a "step function": if you slightly change the input values, the sorted order usually stays the same (zero gradient), or it suddenly jumps to a new order (undefined gradient).

This "sorting bottleneck" prevents researchers from building models where the loss function depends on the relative order of items—such as ranking documents for search engines or selecting the $k$ closest neighbors in a classification task. Previously, researchers used "soft" approximations like Sinkhorn networks, but these were often designed for matching problems rather than the specific logic of sorting.

NeuralSort: A Continuous Relaxation

The core contribution of this work is treating sorting not as a list rearrangement, but as a matrix transformation. Instead of outputting a hard permutation matrix (a grid of 0s and 1s), NeuralSort produces a unimodal row-stochastic matrix. In this matrix, every row sums to one and has a clear "peak" (maximum value) that corresponds to the sorted position.

NeuralSort relaxes permutation matrices (P) into unimodal row-stochastic matrices (U) within the broader set of row-stochastic matrices (R).

This is achieved by using a mathematical identity for the sum of the $k$-largest elements and applying a temperature parameter ($\tau$). As the temperature approaches zero, the "soft" matrix converges to a standard, "hard" permutation matrix. High temperatures provide smooth gradients that help the model explore during early training, while low temperatures allow the model to "harden" its decisions as it converges.

Stochastic Optimization over Permutations

For cases where the sorting order is uncertain or latent, the authors derive a reparameterized gradient estimator for the Plackett-Luce distribution. By adding Gumbel noise to the scores before applying NeuralSort, they create a differentiable way to sample permutations, similar to the "Gumbel-Softmax" trick used for categorical variables.

Comparison between a standard stochastic graph (a) and the proposed reparameterized stochastic graph (b) using Gumbel noise (g) and the sorting relaxation.

This reparameterization allows gradients to flow through the stochastic sorting operation, enabling the optimization of parameters $\theta$ in downstream functions $f$ that depend on the sorted order.

Experimental Results

The framework was evaluated on tasks requiring semantic ordering of high-dimensional objects:

  • Large-MNIST Sorting: Using a dataset of 4-digit numbers formed from MNIST images, NeuralSort correctly identified entire permutations of 15 images ~40% of the time, while baselines like Sinkhorn networks failed completely.
  • Quantile Regression: NeuralSort predicted the median value of image sets with a Mean Squared Error (MSE) nearly 10x lower than standard neural network baselines.
  • Differentiable kNN: Traditionally, $k$-nearest neighbors (kNN) is a fixed algorithm. By making the sorting step differentiable, the model can learn a feature space specifically optimized for kNN classification. On CIFAR-10, this approach reached 90.7% accuracy, nearly matching standard deep CNNs while maintaining the interpretability of a neighbor-based approach.

Conclusion and Future Work

While NeuralSort introduces an $O(n^2)$ computational cost due to pairwise differences, it is highly parallelizable on GPUs. This work opens the door for applying differentiable sorting to other discrete structures, such as beam search in natural language processing, which currently relies on non-differentiable top-$k$ selections. By bridging the gap between discrete sorting and continuous optimization, NeuralSort enables a new class of end-to-end trainable architectures.

Summary updated

Abstract

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.
BibTeX
@inproceedings{grover2019stochastic,
  author = {Aditya Grover and Eric Wang and Aaron Zweig and Stefano Ermon},
  title = {{Stochastic Optimization of Sorting Networks via Continuous Relaxations}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=JWG5V2rpARY},
}
Figure