Minimax Rates and Efficient Algorithms for Noisy Sorting

Cheng Mao, Jonathan Weed, Philippe Rigollet

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 par…