mlsanityData to 14 Oct 2026

Minimax Rates and Efficient Algorithms for Noisy Sorting

arXiv 1710.10388 ↗First posted 28 Oct 2017stat.ML cs.LG math.STcited by 15

Not on the map. Why?

Abstract (arXiv)

There has been a recent surge of interest in studying permutation-based models for ranking from pairwise comparison data. Despite being structurally richer and more robust than parametric ranking models, permutation-based models are less well understood statistically and generally lack efficient learning algorithms. In this work, we study a prototype of permutation-based ranking models, namely, the noisy sorting model. We establish the optimal rates of learning the model under two sampling procedures. Furthermore, we provide a fast algorithm to achieve near-optimal rates if the observations are sampled independently. Along the way, we discover properties of the symmetric group which are of theoretical interest.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). First posted on arXiv 28 Oct 2017.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 4; 2023: 4; 2024: 1; 2025: 3.

15 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  2. 2021Optimal Full Ranking from Pairwise Comparisonscited by 16
  3. 2021Random Graph Matching with Improved Noise Robustnesscited by 16
  4. 2024Problem Solving Through Human-AI Preference-Based Cooperationcited by 11
  5. 2021Optimal detection of the feature matching map in presence of noise and outlierscited by 5
  6. 2022Dynamic Ranking and Translation Synchronizationcited by 4
  7. 2022Ranking with Confidence for Large Scale Comparison Datacited by 3
  8. 2022Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithmscited by 2
  9. 2023On the Optimal Bounds for Noisy Computingcited by 2
  10. 2023Improved theoretical guarantee for rank aggregation via spectral methodcited by 2
  11. 2025Learning to Defer for Causal Discovery with Imperfect Expertscited by 2
  12. 2022Matching Map Recovery with an Unknown Number of Outlierscited by 1
3 more
  1. 2023Covariance alignment: from maximum likelihood estimation to Gromov-Wassersteincited by 1
  2. 2025Learning Parametric Distributions from Samples and Preferencescited by 1
  3. 2025Statistical and computational challenges in rankingcited by 0