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.
Code (1)
Tasks
Stochastic OptimizationSimilar Papers 제목 키워드 기반
SoftSort: A Continuous Relaxation for the argsort Operator
While sorting is an important procedure in computer science, the argsort operator - which takes as input a vector and returns its sorting permutation - has a discrete image and thus zero gradients almost everywhere. This…
SoftSort: A Differantiable Continuous Relaxation of the argsort Operator
Sorting is an important procedure in computer science. However, the argsort operator - which takes as input a vector and returns its sorting per-mutation - has a discrete image and thus zero gradients almost everywhere. …
The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
The reparameterization trick enables optimizing large scale stochastic computation graphs via gradient descent. The essence of the trick is to refactor each stochastic node into a differentiable function of its parameter…
Density EstimationStructured PredictionFunctional Nonlinear Sparse Models
Signal processing is rich in inherently continuous and often nonlinear applications, such as spectral estimation, optical imaging, and super-resolution microscopy, in which sparsity plays a key role in obtaining state-of…
Robust classificationSpectrum CartographySuper-ResolutionNon-local Optimization: Imposing Structure on Optimization Problems by Relaxation
In stochastic optimization, particularly in evolutionary computation and reinforcement learning, the optimization of a function $f: \Omega \to \mathbb{R}$ is often addressed through optimizing a so-called relaxation $\th…
reinforcement-learningReinforcement Learning (RL)Stochastic Optimization