Minimax-optimal Inference from Partial Rankings

By Bruce E. Hajek, Sewoong Oh, Jiaming Xu. 2014

104 citations recorded by the source corpus.

This paper studies the problem of rank aggregation under the Plackett-Luce model. The goal is to infer a global ranking and related scores of the items, based on partial rankings provided by multiple users over multiple subsets of items. A question of particular interest is how to optimally assign items to users for ranking and how many item assignments are needed to achieve a target estimation error. Without any assumptions on how the items are assigned to users, we derive an oracle lower bound and the Cramer-Rao lower bound of the estimation error. We prove an upper bound on the estimation error achieved by the maximum likelihood estimator, and show that both the upper bound and the Cramer-Rao lower bound inversely depend on the spectral gap of the Laplacian of an appropriately defined comparison graph. Since random comparison graphs are known to have large spectral gaps, this suggests the use of random assignments when we have the control. Precisely, the matching oracle lower bound and the upper bound on the estimation error imply that the maximum likelihood estimator together with a random assignment is minimax-optimal up to a logarithmic factor. We further analyze a popular rank-breaking scheme that decompose partial rankings into pairwise comparisons. We show that even if one applies the mismatched maximum likelihood estimator that assumes independence (on pairwise comparisons that are now dependent due to rank-breaking), minimax optimal performance is still achieved up to a logarithmic factor.

Subfields: Economics and Econometrics, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

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

In Economics and Econometrics

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, background): “Novel bounds on the (cid:96) 2 estimation of the BLT models are derived in Negahban et al. (2012); Hajek et al. (2014); Khetan & Oh (2016); Shah et al. (2016); Chen et al. (2020a).”
Graph Resistance and Learning from Pairwise Comparisons (2019, methodology): “A number of other models in the literature have also been used as the basis of inference, we mention the Mallows model introduced in (Mallows, 1957) and the PL and Thurstone models (see description in (Hajek et al., 2014)).”
Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons (2023, background): “On the other hand, in the literature 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.,”
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking (2017, unknown): “For many of these algorithms, the sample complexities needed for perfect total ranking were determined by Rajkumar and Agarwal (2014), although the top-K ranking accuracy was not considered there. Going beyond the parametric models, a recent line of works Shah et al. (2017); Shah and Wainwright (201”
Fast and Accurate Inference of Plackett-Luce Models (2015, methodology): “In order to evaluate the accuracy of an estimate π to ground truth parameters π∗, we therefore use a log transformation, reminiscent of the random-utilitytheoretic formulation of the choice model [1, 11].”
Active Ranking with Subset-wise Preferences (2018, background): “In particular, prior work has addressed the problem of statistical parameter estimation given preference observations from the Plackett-Luce model in the offline setting [30, 15, 26, 21].”
Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence (2015, methodology): “In independent and concurrent work, Hajek et al. (2014) consider the problem of estimation in the Plackett-Luce model, which extends the BTL model to comparisons of two or more items.”
Optimal Algorithms for Stochastic Contextual Preference Bandits (2021, background): “[18] Bruce Hajek, Sewoong Oh, and Jiaming Xu.”
Computational and Statistical Tradeoffs in Learning to Rank (2016, background): “For such traditional preferences, efﬁcient schemes for learning to rank have been proposed, e.g. [12, 9].”
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model (2020, methodology): “There are many variations of the problem that have been studied, from more sophisticated models such as Thurstone and Placket-Luce (Hajek et al. , 2014; Maystre & Grossglauser, 2015), to online or bandit versions (Sz¨or´enyi et al. , 2015; Yue et al. , 2012), to models with active learning (Jamieson”