Data to 7 Oct 2026

Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence

arXiv 1505.01462 ↗First posted 6 May 2015cs.LG cs.IT math.ITcited by 59

Not on the map. Why?

Abstract (arXiv)

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^* ∈ ℝ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^* 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.

Key facts. Cited by 59 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 May 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 6; 2023: 15; 2024: 13; 2025: 14; 2026: 7.

59 papers.

Sort:

By area:

2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 244
2023Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHFcited by 125
2023ReviewerGPT? An Exploratory Study on Using Large Language Models for Paper Reviewingcited by 118
2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
2024Active Preference Optimization for Sample Efficient RLHFcited by 61
2024Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHFcited by 57
2024Direct Judgement Preference Optimizationcited by 33
2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferencescited by 27
2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
2021Lagrangian Inference for Ranking Problemscited by 19
2022A Tale of HodgeRank and Spectral Method: Target Attack Against Rank Aggregation Is the Fixed Point of Adversarial Gamecited by 16
2021Poisoning Attack against Estimating from Pairwise Comparisonscited by 14

38 more

2025Towards User-level Private Reinforcement Learning with Human Feedbackcited by 13
2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
2023Differentially Private Reward Estimation with Preference Feedbackcited by 12
2023Spectral Ranking Inferences based on General Multiway Comparisonscited by 10
2025Understanding the Performance Gap in Preference Learning: A Dichotomy of RLHF and DPOcited by 10
2025J4R: Learning to Judge with Equivalent Initial State Group Relative Policy Optimizationcited by 9
2021ℓ∞-Bounds of the MLE in the BTL Model under General Comparison Graphscited by 8
2023Learning Rich Rankingscited by 8
2022Perfect Sampling from Pairwise Comparisonscited by 6
2023On Sinkhorn's Algorithm and Choice Modelingcited by 6
2024Learning Linear Utility Functions From Pairwise Comparison Queriescited by 6
2024Statistical ranking with dynamic covariatescited by 5
2022A Perceptually Optimized and Self-Calibrated Tone Mapping Operatorcited by 3
2023Ranking from Pairwise Comparisons in General Graphs and Graphs with Localitycited by 3
2023Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learningcited by 3
2024Inferring Dynamic Networks from Marginals with Iterative Proportional Fittingcited by 3
2024Minimax Hypothesis Testing for the Bradley-Terry-Luce Modelcited by 3
2023Optimal and Private Learning from Human Response Datacited by 2
2024Statistical inference for pairwise comparison modelscited by 2
2024Top-K ranking with a monotone adversarycited by 2
2025Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspectivecited by 2
2025PITA: Preference-Guided Inference-Time Alignment for LLM Post-Trainingcited by 2
2025Generative Bayesian Optimization: Generative Models as Acquisition Functionscited by 2
2026What Does Preference Learning Recover from Pairwise Comparison Data?cited by 2
2022Antipatterns in Software Classification Taxonomiescited by 1
2024MENTOR: Guiding Hierarchical Reinforcement Learning with Human Feedback and Dynamic Distance Constraintcited by 1
2024An Analysis of Elo Rating Systems via Markov Chainscited by 1
2025Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorizationcited by 1
2025Optimal Differentially Private Ranking from Pairwise Comparisonscited by 1
2025Hypothesis Testing for Generalized Thurstone Modelscited by 1
2021Achievability and Impossibility of Exact Pairwise Rankingcited by 0
2022Modeling and Correcting Bias in Sequential Evaluationcited by 0
2022Allocation Schemes in Analytic Evaluation: Applicant-Centric Holistic or Attribute-Centric Segmented?cited by 0
2023Scoring Cycling Environments Perceived Safety using Pairwise Image Comparisonscited by 0
2023Sample Complexity of Preference-Based Nonparametric Off-Policy Evaluation with Deep Networkscited by 0
2024Random pairing MLE for estimation of item parameters in Rasch modelcited by 0
2025Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applicationscited by 0
2025Learning Guarantee of Reward Modeling Using Deep Neural Networkscited by 0

50 most cited of 59 All 59 (JSON)