Fast Differentiable Sorting and Ranking

• URL: http://arxiv.org/abs/2002.08871v2
• Date: Mon, 29 Jun 2020 23:11:03 GMT
• Title: Fast Differentiable Sorting and Ranking
• Authors: Mathieu Blondel, Olivier Teboul, Quentin Berthet, Josip Djolonga
• Abstract summary: We propose the first differentiable sorting and ranking operators with $O(n log n)$ time and $O(n)$ space complexity. We achieve this feat by constructing differentiable operators as projections onto the permutahedron, the convex hull of permutations, and using a reduction to isotonic optimization.
• Score: 36.40586857569459
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The sorting operation is one of the most commonly used building blocks in computer programming. In machine learning, it is often used for robust statistics. However, seen as a function, it is piecewise linear and as a result includes many kinks where it is non-differentiable. More problematic is the related ranking operator, often used for order statistics and ranking metrics. It is a piecewise constant function, meaning that its derivatives are null or undefined. While numerous works have proposed differentiable proxies to sorting and ranking, they do not achieve the $O(n \log n)$ time complexity one would expect from sorting and ranking operations. In this paper, we propose the first differentiable sorting and ranking operators with $O(n \log n)$ time and $O(n)$ space complexity. Our proposal in addition enjoys exact computation and differentiation. We achieve this feat by constructing differentiable operators as projections onto the permutahedron, the convex hull of permutations, and using a reduction to isotonic optimization. Empirically, we confirm that our approach is an order of magnitude faster than existing approaches and showcase two novel applications: differentiable Spearman's rank correlation coefficient and least trimmed squares.

Related papers

• Variation Matters: from Mitigating to Embracing Zero-Shot NAS Ranking Function Variation [18.672184596814077]
  We propose taking into account the variation in the ranking function output as a random variable representing a proxy performance metric. During the search process, we strive to construct a ordering of the performance metrics to determine the best architecture. Our experiments show that the proposed ordering can effectively boost performance of a search on standard benchmark search spaces.
  arXiv  Detail & Related papers  (2025-02-27T01:01:22Z)
• Sorting with Predictions [1.7042264000899532]
  We explore the fundamental problem of sorting through the lens of learning-augmented algorithms. We design new and simple algorithms using only $O(sum_i log eta_i)$ exact comparisons. We prove that the comparison complexity is theoretically optimal with respect to the examined error measures.
  arXiv  Detail & Related papers  (2023-11-01T18:00:03Z)
• Generalized Neural Sorting Networks with Error-Free Differentiable Swap Functions [44.71975181739874]
  We consider sorting problems for more abstract yet expressive inputs, e.g., multi-digit images and image fragments, through a neural sorting network. To learn a mapping from a high-dimensional input to an ordinal variable, the differentiability of sorting networks needs to be guaranteed.
  arXiv  Detail & Related papers  (2023-10-11T03:47:34Z)
• Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective [21.6146047576295]
  The top-k operator returns a sparse vector, where the non-zero values correspond to the k largest values of the input. We view the top-k operator as a linear program over the permutahedron, the convex hull of permutations. Our framework is significantly more general than the existing one and allows for example to express top-k operators that select values in magnitude.
  arXiv  Detail & Related papers  (2023-02-02T21:32:13Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Monotonic Differentiable Sorting Networks [29.75063301688965]
  Differentiable sorting algorithms allow training with sorting and ranking supervision, where only the ordering or ranking of samples is known. One problem of current differentiable sorting methods is that they are non-monotonic. We propose a novel relaxation of conditional swap operations that guarantees monotonicity in differentiable sorting networks.
  arXiv  Detail & Related papers  (2022-03-17T21:51:29Z)
• Beware of the Simulated DAG! Varsortability in Additive Noise Models [70.54639814319096]
  We show how varsortability dominates the performance of continuous structure learning algorithms on synthetic data. We aim to raise awareness that varsortability easily occurs in simulated additive noise models.
  arXiv  Detail & Related papers  (2021-02-26T18:52:27Z)
• PiRank: Learning To Rank via Differentiable Sorting [85.28916333414145]
  We propose PiRank, a new class of differentiable surrogates for ranking. We show that PiRank exactly recovers the desired metrics in the limit of zero temperature.
  arXiv  Detail & Related papers  (2020-12-12T05:07:36Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  The SOFT top-k operator approximates the output of the top-k operation as the solution of an Entropic Optimal Transport (EOT) problem. We apply the proposed operator to the k-nearest neighbors and beam search algorithms, and demonstrate improved performance.
  arXiv  Detail & Related papers  (2020-02-16T04:57:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.