Minimax Rates and Efficient Algorithms for Noisy Sorting
This work addresses the lack of efficient algorithms and statistical understanding in permutation-based ranking models, which are more robust than parametric alternatives, for applications like recommendation systems.
The paper tackles the problem of ranking from pairwise comparisons using the noisy sorting model, establishing optimal learning rates and providing a fast algorithm that achieves near-optimal rates for independent sampling.
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.