Achievability and Impossibility of Exact Pairwise Ranking

Alike Shah and Wainwright [2017], we also considered comparisons. We assume the SST class the random design observation model, where as the family of generative models. Our the observation of any pairs in each round is observed analysis gave sharp information theoretic upper with probability p. In particular, we focus on the problem and lower bound for the exact requirement, of exact recovery, where the estimator converges which matches exactly in the parametric almost surely to the ground truth as the scale of the limit. Our tight analysis on the algorithm problem goes to infinity. Under this requirement, we induced by the moment method gave better formally discuss the fundamental limits in this problem.