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

Wednesday, February 28, 2018 - 4:30pm to Thursday, March 1, 2018 - 4:55pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Cheng Mao


Mathematics Department, MIT

Building and Room Number

LIDS Lounge


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.


I am a fifth-year graduate student in the Mathematics Department at MIT. My advisor is Philippe Rigollet. My research interests include statistics theory, machine learning and probability. Previously, I was an undergraduate student at UCLA.