Lagrangian Inference for Ranking Problems

Abstract

We propose a novel combinatorial inference framework to conduct general uncertainty quantification in ranking problems. We consider the widely adopted Bradley-Terry-Luce (BTL) model, where each item is assigned a positive preference score that determines the Bernoulli distributions of pairwise comparisons' outcomes. Our proposed method aims to infer general ranking properties of the BTL model. The general ranking properties include the "local" properties such as if an item is preferred over another and the "global" properties such as if an item is among the top $K$-ranked items. We further generalize our inferential framework to multiple testing problems where we control the false discovery rate (FDR), and apply the method to infer the top-$K$ ranked items. We also derive the information-theoretic lower bound to justify the minimax optimality of the proposed method. We conduct extensive numerical studies using both synthetic and real datasets to back up our theory.

References in corpus (14)

• On asymptotically optimal confidence regions and tests for high-dimensional models
• Adversarial Personalized Ranking for Recommendation
• Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search
• Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Active Ranking using Pairwise Comparisons
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Top-$K$ Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Novel Distance Measures for Vote Aggregation
• Constrained High Dimensional Statistical Inference
• High-Dimensional Inference for Cluster-Based Graphical Models
• Bayesian Decision Process for Cost-Efficient Dynamic Ranking via Crowdsourcing
• Spectral Methods for Ranking with Scarce Data

Cited by in corpus (2)

• Sequential Manipulation Against Rank Aggregation: Theory and Algorithm
• Minimax Hypothesis Testing for the Bradley-Terry-Luce Model