mlsanityData to 14 Oct 2026

Stochastic Optimization of Sorting Networks via Continuous Relaxations

arXiv 1903.08850 ↗First posted 21 Mar 2019stat.ML cs.LG cs.NEcited by 111

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 111 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Mar 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 18; 2022: 19; 2023: 19; 2024: 16; 2025: 21; 2026: 18.

111 papers.

Sort:

By area:

  1. 2022Git Re-Basin: Merging Models modulo Permutation Symmetriescited by 471
  2. 2025LeJEPA: Provable and Scalable Self-Supervised Learning Without the Heuristicscited by 254
  3. 2021Implicit MLE: Backpropagating Through Discrete Exponential Family Distributionscited by 98
  4. 2021A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learningcited by 82
  5. 2022Ordered Subgraph Aggregation Networkscited by 57
  6. 2022Unsupervised Learning of Group Invariant and Equivariant Representationscited by 39
  7. 2021Single Image Depth Estimation: An Overviewcited by 35
  8. 2022SIMPLE: A Gradient Estimator for k-Subset Samplingcited by 34
  9. 2021Differentiable Sorting Networks for Scalable Sorting and Ranking Supervisioncited by 31
  10. 2021Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertisingcited by 31
  11. 2022Generalized Differentiable RANSACcited by 30
  12. 2023A Large-Scale Study of Probabilistic Calibration in Neural Network Regressioncited by 27
38 more
  1. 2023Ensuring User-side Fairness in Dynamic Recommender Systemscited by 27
  2. 2023Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspectivecited by 26
  3. 2023Learning Probabilistic Symmetrization for Architecture Agnostic Equivariancecited by 26
  4. 2022Monotonic Differentiable Sorting Networkscited by 25
  5. 2021Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learningcited by 23
  6. 2022Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergencecited by 22
  7. 2021Learning with Algorithmic Supervision via Continuous Relaxationscited by 21
  8. 2022Differentiable Top-k Classification Learningcited by 21
  9. 2023ProtoGate: Prototype-based Neural Networks with Global-to-local Feature Selection for Tabular Biomedical Datacited by 18
  10. 2021Structured Reordering for Modeling Latent Alignments in Sequence Transductioncited by 17
  11. 2024Softened Symbol Grounding for Neuro-symbolic Systemscited by 16
  12. 2021Discovering Non-monotonic Autoregressive Orderings with Variational Inferencecited by 15
  13. 2021Self-Supervised Learning of Audio Representations from Permutations with Differentiable Rankingcited by 14
  14. 2021Learning Revenue-Maximizing Auctions With Differentiable Matchingcited by 14
  15. 2026Learning to Evict from Key-Value Cachecited by 14
  16. 2022Optimizing generalized Gini indices for fairness in rankingscited by 13
  17. 2023Learning by Sorting: Self-supervised Learning with Group Ordering Constraintscited by 13
  18. 2025LapSum -- One Method to Differentiate Them All: Ranking, Sorting and Top-k Selectioncited by 13
  19. 2022Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Modelscited by 12
  20. 2023Performative Recommendation: Diversifying Content via Strategic Incentivescited by 12
  21. 2025VisionSelector: End-to-End Learnable Visual Token Compression for Efficient Multimodal LLMscited by 11
  22. 2021Unbiased Gradient Estimation with Balanced Assignments for Mixtures of Expertscited by 10
  23. 2025ESPFormer: Doubly-Stochastic Attention with Expected Sliced Transport Planscited by 10
  24. 2025Breaking the Top-K Barrier: Advancing Top-K Ranking Metrics Optimization in Recommender Systemscited by 9
  25. 2021Differentiable Agent-Based Simulation for Gradient-Guided Simulation-Based Optimizationcited by 8
  26. 2024Permutative Preference Alignment from Listwise Ranking of Human Judgmentscited by 7
  27. 2021Set-to-Sequence Methods in Machine Learning: a Reviewcited by 6
  28. 2022Relevance-based Margin for Contrastively-trained Video Retrieval Modelscited by 6
  29. 2022Differentiable Mathematical Programming for Object-Centric Representation Learningcited by 6
  30. 2023Beam Tree Recursive Cellscited by 6
  31. 2023Polynomial Width is Sufficient for Set Representation with High-dimensional Featurescited by 6
  32. 2023Deciphering Raw Data in Neuro-Symbolic Learning with Provable Guaranteescited by 6
  33. 2023Adaptive Neural Ranking Framework: Toward Maximized Business Goal for Cascade Ranking Systemscited by 6
  34. 2023PAC-Bayes Generalization Certificates for Learned Inductive Conformal Predictioncited by 6
  35. 2024Probabilistic Calibration by Design for Neural Network Regressioncited by 6
  36. 2024SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groupscited by 6
  37. 2022Learning Group Importance using the Differentiable Hypergeometric Distributioncited by 5
  38. 2023Kissing to Find a Match: Efficient Low-Rank Permutation Representationcited by 5

50 most cited of 111 All 111 (JSON)