Pairwise Comparison Models for High-Dimensional Ranking: Some Statistical and Computational Trade-Offs

• Activity Number: 92 - Computational Challenges in Statistics
• Type: Invited
• Date/Time: Monday, July 31, 2017 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Sivaraman Balakrishnan* and Nihar B Shah and Martin J. Wainwright
• Companies: Department of Statistics, CMU and Univ of California - Berkeley and EECS and Statistics, University of California, Berkeley

Abstract

Data in the form of pairwise comparisons between a collection of items arises in many settings, including voting schemes, tournament play, and online search rankings. We study a flexible non-parametric model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity (SST). The SST class includes a large family of classical parametric models as special cases, among them the Bradley-Terry-Luce and Thurstone models, but is substantially richer. We characterize the global minimax risk for estimating the matrix of pairwise comparisons, as well as some locally adaptive variants. We then discuss various computational trade-offs that arise in achieving these optimal rates in an efficient way.