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 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
We provide a continuous relaxation to the sorting operator, enabling end-to-end, gradient-based stochastic optimization.The paper considers how to sort a number of items without explicitly necessarily learning their actual meanings or values and proposes a method to perform the optimization via a continuous relaxation.This work builds on a sum(top k) identity to derive a pathwise differentiable sampler of 'unimodal row stochastic' matrices.", 'Introduces a continuous relaxation of the sorting operator in order to construct an end-to-end gradient-based optimization and introduces a stochastic extension of its method using Placket-Luce distributions and Monte Carlo.