Minimax Rates and Efficient Algorithms for Noisy Sorting

Cheng Mao, Jonathan Weed, Philippe Rigollet

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)821-847
Number of pages27
JournalProceedings of Machine Learning Research
StatePublished - 2018
Event29th International Conference on Algorithmic Learning Theory, ALT 2018 - Lanzarote, Spain
Duration: Apr 7 2018Apr 9 2018


  • Minimax Estimation
  • Noisy Sorting
  • Pairwise Comparisons
  • Permutations
  • Ranking

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Minimax Rates and Efficient Algorithms for Noisy Sorting'. Together they form a unique fingerprint.

Cite this