Breaking the n^(-1/2) Barrier for Permutation-Based Ranking Models

There has been a recent surge of interest in studying permutation-based models, such as the noisy sorting (NS) model and the strong stochastic transitivity (SST) 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 best computationally efficient algorithms. In this talk, I will discuss new algorithms that achieve rates n^{-1} and n^{-3/4} for the NS and the SST model respectively.