Stochastic Optimization of Sorting Networks via Continuous Relaxations

Aditya Grover, Eric Wang, Aaron Zweig, Stefano Ermon

Introduction

Sorting input objects is a fundamental step in many machine learning pipelines, from search engine ranking to $k$-nearest neighbors (kNN) classification. However, the standard sorting operator is inherently discrete and non-differentiable. If you change the input values slightly, the sorted order remains identical until it suddenly jumps to a new configuration. This "jumpiness" means gradients are zero almost everywhere, prohibiting the use of backpropagation to train models end-to-end if they include a sorting step.

To solve this, researchers introduce NeuralSort, a general-purpose, continuous relaxation of the sorting operator. By replacing discrete permutation matrices with continuous approximations, NeuralSort enables neural networks to learn semantic orderings of complex data through standard gradient-based optimization.

The Core Method: Relaxing the Sort

Previously, researchers relied on noisy "straight-through" estimators or relaxations like the Sinkhorn operator, which are better suited for matching problems than sorting. NeuralSort provides a more principled approach using two main components:

1. Continuous Relaxation

The authors leverage a mathematical identity that expresses the $k$-th largest element in a set based on absolute pairwise differences. By replacing the discrete argmax in this identity with a continuous softmax (controlled by a temperature parameter $\tau$), they transform the output into a "unimodal row-stochastic matrix." As the temperature $\tau$ approaches zero, this relaxed matrix converges to a standard, discrete permutation matrix.

2. Stochastic Optimization

To handle uncertainty and explore different rankings during training, NeuralSort is extended to distributions over permutations—specifically the Plackett-Luce family.

Comparison of standard stochastic optimization and the proposed reparameterized stochastic optimization using Gumbel noise.

The authors employ a "reparameterization trick" akin to the Gumbel-Softmax trick. By adding Gumbel noise to the input scores before applying the NeuralSort operator, the model can sample different permutations while remaining fully differentiable. This allows gradients to flow smoothly back to the network parameters.

Key Insight: The Importance of Unimodality

A major theoretical contribution of NeuralSort is its focus on unimodality.

Venn diagram illustrating the relationship between Row-stochastic, Doubly-stochastic, Unimodal, and Permutation matrices.

Unlike previous relaxations (such as Sinkhorn) that produce "doubly-stochastic" matrices, NeuralSort produces "unimodal" matrices. In a unimodal matrix, every row has a distinct maximum value. This property is crucial because it makes it significantly easier to "project" the continuous, relaxed matrix back into a hard, discrete sorting order for final evaluation or downstream tasks.

Applications and Results

The paper evaluates NeuralSort across several tasks that require learning semantic orderings of high-dimensional objects:

  • Sorting as a Representation Learner: The authors created a large-MNIST benchmark by concatenating four MNIST digits to form 4-digit numbers (e.g., images of "1", "8", "1", "0" form 1810). The model had to learn the semantic value of the images to sort them. For sequences of 15 images, NeuralSort achieved ~40% exact match accuracy (correctly identifying the entire permutation), whereas traditional relaxations like Sinkhorn failed entirely (0% accuracy).
  • Quantile Regression: When tasked with predicting the median value of a sequence of images, a network equipped with NeuralSort achieved a Mean Squared Error (MSE) nearly 10x lower than a standard vanilla neural network.
  • Differentiable kNN: Traditionally, kNN is a fixed algorithm. By making the "top-k" selection differentiable, NeuralSort enables a kNN classifier to train its own feature extractor (a CNN) end-to-end. On CIFAR-10, this Differentiable kNN reached 90.7% accuracy, outperforming standard kNN and PCA-based kNN, and approaching the performance of a pure CNN (95.1%) while preserving the interpretability of a nearest-neighbor approach.

Limitations and Future Directions

While powerful, NeuralSort has a few limitations:

  • Computational Complexity: The operator requires $O(n^2)$ operations due to the calculation of pairwise differences between all $n$ elements. While highly parallelizable on modern GPUs, it is theoretically slower than the $O(n \log n)$ complexity of standard sorting algorithms.
  • Temperature Sensitivity: Like many continuous relaxations, performance is sensitive to the temperature parameter $\tau$. High temperatures yield smoother gradients but coarser approximations, while low temperatures are more accurate but risk vanishing gradients.

Looking forward, the authors suggest this framework could be applied to other discrete structures, such as relaxing beam search in natural language processing or tackling broader combinatorial optimization problems.

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 argmax. 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