Achievability and Impossibility of Exact Pairwise Ranking
Not on the map. Why?
Abstract (arXiv)
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 ~citetshah2017simple 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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 5 of its 13 references that are in the map. First posted on arXiv 19 Nov 2021.
Builds on
5 of 13 references.
References · 5
- 2015Simple, Robust and Optimal Ranking from Pairwise Comparisonscited by 70
- 2015Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependencecited by 61
- 2015Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisonscited by 34
- 2015Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issuescited by 32
- 2016Competitive analysis of the top-K ranking problemcited by 6
Built on by
Not cited yet.