Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

Abstract

Data in the form of pairwise comparisons arises in many domains, including preference elicitation, sporting competitions, and peer grading among others. We consider parametric ordinal models for such pairwise comparison data involving a latent vector $w^{\ast }\in {\mathbb{R}}^d$ that represents the "qualities" of the $d$ items being compared; this class of models includes the two most widely used parametric models--the Bradley-Terry-Luce (BTL) and the Thurstone models. Working within a standard minimax framework, we provide tight upper and lower bounds on the optimal error in estimating the quality score vector $w^{\ast }$ under this class of models. The bounds depend on the topology of the comparison graph induced by the subset of pairs being compared via its Laplacian spectrum. Thus, in settings where the subset of pairs may be chosen, our results provide principled guidelines for making this choice. Finally, we compare these error rates to those under cardinal measurement models and show that the error rates in the ordinal and cardinal settings have identical scalings apart from constant pre-factors.

39 pages, 5 figures. Significant extension of arXiv:1406.6618

References in corpus (6)

• Matrix estimation by Universal Singular Value Thresholding
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Noisy Sorting Without Resampling
• Active Ranking using Pairwise Comparisons
• Minimax-optimal Inference from Partial Rankings
• When is it Better to Compare than to Score?

Cited by in corpus (26)

• Double or Nothing: Multiplicative Incentive Mechanisms for Crowdsourcing
• Poisoning Attack against Estimating from Pairwise Comparisons
• Hybrid-MST: A Hybrid Active Sampling Strategy for Pairwise Preference Aggregation
• The Smoothed Possibility of Social Choice
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
• On Strategyproof Conference Peer Review
• Learning from Comparisons and Choices
• Learning to Approximate a Bregman Divergence
• Strategy for Boosting Pair Comparison and Improving Quality Assessment Accuracy
• Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
• Simultaneous Preference and Metric Learning from Paired Comparisons
• Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model
• Learning Rich Rankings
• Two-Sample Testing on Ranked Preference Data and the Role of Modeling Assumptions
• Spectral Methods for Ranking with Scarce Data
• Pair-Matching: Links Prediction with Adaptive Queries
• Graph Resistance and Learning from Pairwise Comparisons
• Arena Model: Inference About Competitions
• Active embedding search via noisy paired comparisons
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Accelerated MM Algorithms for Ranking Scores Inference from Comparison Data
• Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice
• Aggregating Incomplete and Noisy Rankings
• A Normal Approximation Method for Statistics in Knockouts