# Minimax Rates and Efficient Algorithms for Noisy Sorting

arXiv: https://arxiv.org/abs/1710.10388 · HTML: https://mlsanity.com/paper/1710.10388/

## Key facts

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

## Built on by (most cited first, 15 of 15)

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Problem Solving Through Human-AI Preference-Based Cooperation](https://mlsanity.com/paper/2408.07461/) (2024)
- [Optimal detection of the feature matching map in presence of noise and outliers](https://mlsanity.com/paper/2106.07044/) (2021)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Ranking with Confidence for Large Scale Comparison Data](https://mlsanity.com/paper/2202.01670/) (2022)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [On the Optimal Bounds for Noisy Computing](https://mlsanity.com/paper/2306.11951/) (2023)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [Learning to Defer for Causal Discovery with Imperfect Experts](https://mlsanity.com/paper/2502.13132/) (2025)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein](https://mlsanity.com/paper/2311.13595/) (2023)
- [Learning Parametric Distributions from Samples and Preferences](https://mlsanity.com/paper/2505.23557/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## 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.