Minimax Rates and Efficient Algorithms for Noisy Sorting

Cheng Mao, Jonathan Weed, Philippe Rigollet
Proceedings of Algorithmic Learning Theory, PMLR 83:821-847, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-mao18a, title = {Minimax Rates and Efficient Algorithms for Noisy Sorting}, author = {Mao, Cheng and Weed, Jonathan and Rigollet, Philippe}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {821--847}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/mao18a/mao18a.pdf}, url = {https://proceedings.mlr.press/v83/mao18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Minimax Rates and Efficient Algorithms for Noisy Sorting %A Cheng Mao %A Jonathan Weed %A Philippe Rigollet %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-mao18a %I PMLR %P 821--847 %U https://proceedings.mlr.press/v83/mao18a.html %V 83 %X 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.
APA
Mao, C., Weed, J. & Rigollet, P.. (2018). Minimax Rates and Efficient Algorithms for Noisy Sorting. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:821-847 Available from https://proceedings.mlr.press/v83/mao18a.html.

Related Material