Maximum Selection and Ranking under Noisy Comparisons

By Moein Falahatgar, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh. 2017

56 citations recorded by the source corpus.

We consider $(\epsilon,\delta)$-PAC maximum-selection and ranking for general probabilistic models whose comparisons probabilities satisfy strong stochastic transitivity and stochastic triangle inequality. Modifying the popular knockout tournament, we propose a maximum-selection algorithm that uses $\mathcal{O}\left(\frac{n}{\epsilon^2}\log \frac{1}{\delta}\right)$ comparisons, a number tight up to a constant factor. We then derive a general framework that improves the performance of many ranking algorithms, and combine it with merge sort and binary search to obtain a ranking algorithm that uses $\mathcal{O}\left(\frac{n\log n (\log \log n)^3}{\epsilon^2}\right)$ comparisons for any $\delta\ge\frac1n$, a number optimal up to a $(\log \log n)^3$ factor.

Subfields: Economics and Econometrics, Management Science and Operations Research, Evaluation & Benchmarks

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 Evaluation & Benchmarks

Citations in the corpus

Human Preferences as Dueling Bandits (2022, background): “For example, strategies that repeatedly compare two arms until a winner is found may require too many independent assessors to be feasible when arms are nearly equal [12, 13, 26].”
Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons (2022, methodology): “1189 Knockout, Seq Elim, Single Elim: Knockout1190 (Falahatgar et al., 2017b), Sequential Elimination1191 (Falahatgar et al., 2017a), Single Elimination (Mo-1192 hajer et al., 2017) are all algorithms that proceed in1193 a knockout tournament fashion where the systems1194 are randomly paired, and…”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, methodology): “For example, under SST, OPT-Maximize [15] achieves the minimax optimal rate for dueling bandits.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “…ﬁltering (Yue et al., 2012) Beat-the-mean (Yue and Joachims, 2011) Knockout tournaments (Falahatgar et al., 2017b) Sequaential elimination (Falahatgar et al., 2017a) Single elimination tournament (Mohajer et al., 2017) Successive elimination (Jamieson et al., 2015) RUCB (Zoghi et al.,…”
Graph Resistance and Learning from Pairwise Comparisons (2019, background): “, 2015) considered the online version of this problem with corresponding regret, (Chen & Suh, 2015) considered recovering the top K ranked items, (Falahatgar et al., 2017; Agarwal et al., 2017; Maystre & Grossglauser, 2015) consider recovering a ranked list of the items, and (Ajtai et al.”
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons (2020, methodology): “We note that assumptions A1) to A3) are common in the literature (e.g., (Szörényi et al., 2015; Shah and Wainwright, 2017; Falahatgar et al., 2017a;b; 2018; Heckel et al., 2018; Katariya et al., 2018; Heckel et al., 2019; Saha and Gopalan, 2019a;b; Ren et al., 2019)).”