Achievability and Impossibility of Exact Pairwise Ranking
This work addresses a fundamental ranking problem in statistics and machine learning, with incremental improvements in theoretical guarantees.
The paper tackles the problem of exact pairwise ranking from noisy comparisons under the SST model, deriving sharp information-theoretic bounds that match exactly in the parametric limit and improving the minimax optimal rate constant compared to prior work.
We consider the problem of recovering the rank of a set of $n$ items based on noisy pairwise comparisons. We assume the SST class as the family of generative models. Our analysis gave sharp information theoretic upper and lower bound for the exact requirement, which matches exactly in the parametric limit. Our tight analysis on the algorithm induced by the moment method gave better constant in Minimax optimal rate than ~\citet{shah2017simple} and contribute to their open problem. The strategy we used in this work to obtain information theoretic bounds is based on combinatorial arguments and is of independent interest.