Breaking the n^{-1/2} barrier for permutation-based ranking models
The task of ranking from pairwise comparison data arises frequently in various applications, such as recommender systems, sports tournaments and social choice theory. There has been a recent surge of interest in studying permutation-based models, such as the noisy sorting model and the strong stochastic transitivity model, for ranking from pairwise comparisons. Although permutation-based ranking models are richer than traditional parametric models, a wide gap exists between the statistically optimal rate n^{-1} and the rate n^{-1/2} achieved by the state-of-the-art computationally efficient algorithms. In this poster, I will demonstrate our work tightening this statistical-computational gap. More precisely, I will present new algorithms that achieve rates n^{-1} and n^{-3/4} for the noisy sorting model and the more general strong stochastic transitivity model respectively.
Authors: Cheng Mao, Jonathan Weed, Philippe Rigollet, Ashwin Pananjady and Martin J. Wainwright
