Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

By Nihar B. Shah, Sivaraman Balakrishnan, Joseph K. Bradley, Abhay K. Parekh, Kannan Ramchandran, Martin J. Wainwright. 2015

187 citations recorded by the source corpus.

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* e Rd 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* under this class of models. The bounds depend on the topology of the comparison graph induced by the subset of pairs being compared, via the spectrum of the Laplacian of the comparison graph. 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.

Subfields: Artificial Intelligence, Economics and Econometrics, Statistics and Probability, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Economics and Econometrics

In Statistics and Probability

In Scaling & Learning Theory

Michael I. Jordan

Citations in the corpus

Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, methodology): “Theorem 4.2 of Shah et al. (2016) decouples these two aspects.”
Graph Resistance and Learning from Pairwise Comparisons (2019, background): “A somewhat more general setting was considered in (Shah et al., 2016), which considered a wider class of noisy comparison models which include the BTL model as a special case.”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “…of ranking, most of the theoretical work focuses on the tabular case where the rewards for different actions are uncorrelated (Feige et al., 1994; Shah et al., 2015; Shah and Wainwright, 2017; Heckel et al., 2018; Mao et al., 2018; Jang et al., 2017; Chen et al., 2013; Chen and Suh, 2015;…”
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model (2020, methodology): “Considerably more general models of ranking are quite common in the literature; in particular, we mention the papers (Rajkumar & Agarwal, 2016; Shah et al. , 2016; Negahban et al. , 2018), discussed next.”
Computational and Statistical Tradeoffs in Learning to Rank (2016, background): “This is one of the motivations behind the algorithmic advances in learning from pairwise comparisons [19, 21, 17].”