Active ranking from pairwise comparisons and when parametric assumptions do not help

DOI10.1214/18-AOS1772MaRDI QIDQ2284367zbMATH OpenFDO

Authors Reinhard Heckel, Nihar B. Shah, Kannan Ramchandran, Martin J. Wainwright

Publication date 15 January 2020

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.08842, https://projecteuclid.org/euclid.aos/1572487385

zbMATH Keywords

rankingonline learningactive learningpairwise comparisonsmulti-armed banditsBradley-Terry-Luce model

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Paired and multiple comparisons; multiple testing (62J15)

Abstract: We consider sequential or active ranking of a set of n items based on noisy pairwise comparisons. Items are ranked according to the probability that a given item beats a randomly chosen item, and ranking refers to partitioning the items into sets of pre-specified sizes according to their scores. This notion of ranking includes as special cases the identification of the top-k items and the total ordering of the items. We first analyze a sequential ranking algorithm that counts the number of comparisons won, and uses these counts to decide whether to stop, or to compare another pair of items, chosen based on confidence intervals specified by the data collected up to that point. We prove that this algorithm succeeds in recovering the ranking using a number of comparisons that is optimal up to logarithmic factors. This guarantee does not require any structural properties of the underlying pairwise probability matrix, unlike a significant body of past work on pairwise ranking based on parametric models such as the Thurstone or Bradley-Terry-Luce models. It has been a long-standing open question as to whether or not imposing these parametric assumptions allows for improved ranking algorithms. For stochastic comparison models, in which the pairwise probabilities are bounded away from zero, our second contribution is to resolve this issue by proving a lower bound for parametric models. This shows, perhaps surprisingly, that these popular parametric modeling choices offer at most logarithmic gains for stochastic comparisons.

Recommendations

• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• A nearly instance optimal algorithm for top-\(k\) ranking under the multinomial logit model
• Rank Centrality: Ranking from Pairwise Comparisons
• Top-\(\kappa\) selection with pairwise comparisons
• An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity

Cites work

• scientific article; zbMATH DE number 3152611 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3073477 (Why is no real title available?)
• A Sequential Procedure for Selecting the Population with the Largest Mean from $k$ Normal Populations
• Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
• Active ranking from pairwise comparisons and when parametric assumptions do not help
• Competitive analysis of the top-\(K\) ranking problem
• Estimation from pairwise comparisons: sharp minimax bounds with topology dependence
• MM algorithms for generalized Bradley-Terry models.
• Majorization, entropy and paired comparisons
• On the complexity of best-arm identification in multi-armed bandit models
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
• The \(K\)-armed dueling bandits problem

Cited in

(18)

• Top-\(\kappa\) selection with pairwise comparisons
• Time-homogeneous top-\(K\) ranking using tensor decompositions
• Pair-matching: link prediction with adaptive queries
• Optimal full ranking from pairwise comparisons
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• A General Pairwise Comparison Model for Extremely Sparse Networks
• Minimax rates and efficient algorithms for noisy sorting
• A new and flexible approach to the analysis of paired comparison data
• Asymptotically Optimal Sequential Design for Rank Aggregation
• Ranking and selection for pairwise comparison
• Active ranking from pairwise comparisons and when parametric assumptions do not help
• Robust Learning of Consumer Preferences
• Spectral method and regularized MLE are both optimal for top-\(K\) ranking
• Low permutation-rank matrices: structural properties and noisy completion
• scientific article; zbMATH DE number 7370524 (Why is no real title available?)
• A nearly instance optimal algorithm for top-\(k\) ranking under the multinomial logit model
• Competitive analysis of the top-\(K\) ranking problem
• Towards optimal estimation of bivariate isotonic matrices with unknown permutations

This page was built for publication: Active ranking from pairwise comparisons and when parametric assumptions do not help

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2284367)