Top-$K$ Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal

Abstract

We explore the top-$K$ rank aggregation problem. Suppose a collection of items is compared in pairs repeatedly, and we aim to recover a consistent ordering that focuses on the top-$K$ ranked items based on partially revealed preference information. We investigate the Bradley-Terry-Luce model in which one ranks items according to their perceived utilities modeled as noisy observations of their underlying true utilities. Our main contributions are two-fold. First, in a general comparison model where item pairs to compare are given a priori, we attain an upper and lower bound on the sample size for reliable recovery of the top-$K$ ranked items. Second, more importantly, extending the result to a random comparison model where item pairs to compare are chosen independently with some probability, we show that in slightly restricted regimes, the gap between the derived bounds reduces to a constant factor, hence reveals that a spectral method can achieve the minimax optimality on the (order-wise) sample size required for top-$K$ ranking. That is to say, we demonstrate a spectral method alone to be sufficient to achieve the optimality and advantageous in terms of computational complexity, as it does not require an additional stage of maximum likelihood estimation that a state-of-the-art scheme employs to achieve the optimality. We corroborate our main results by numerical experiments.

arXiv comment23 pages, 3 figures, submitted to the Journals of Machine Learning Research

References in corpus (5)

• Noisy Sorting Without Resampling
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Active Ranking using Pairwise Comparisons
• A Statistical Decision-Theoretic Framework for Social Choice
• Rank Centrality: Ranking from Pair-wise Comparisons

Cited by in corpus (8)

• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Maximum Selection and Ranking under Noisy Comparisons
• Lagrangian Inference for Ranking Problems
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Learning from Comparisons and Choices
• A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model
• Pair-Matching: Links Prediction with Adaptive Queries
• Secretary Ranking with Minimal Inversions