2021/11/19 by Yihan He, He, Yihan
Computer Science · Mathematics · #Artificial intelligence #Bayesian Modeling and Causal Inference #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Data Management and Algorithms #Discrete mathematics #FOS: Computer and information sciences #Impossibility #Limit (mathematics) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical economics #Mathematical optimization #Mathematics #Minimax #Moment (physics) #Pairwise comparison #Parametric statistics #Rank (graph theory) #Ranking (information retrieval) #Set (abstract data type) #Statistics #Upper and lower bounds #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2111.10021
published in arXiv (Cornell University) (Cornell University)
arxiv created 2021/11/19 · openalex publication_date 2021/11/19 · arxiv updated 2021/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.