Maxing, Ranking and Preference Learning
Venkatadheeraj Pichapati · eScholarship (California Digital Library) · 2019
PAC maximum selection (maxing) and ranking of $n$ elements via randompairwise comparisons have diverse applications and have been studiedunder many models and assumptions. We consider $(\\epsilon,\\delta)$-PACmaxing and ranking using pairwise comparisons for \ obreak{general}probabilistic models. We present a comprehensive understanding ofthree important problems in PAC preference learning: maxing, ranking,and estimating \\emph{all} pairwise preference probabilities, in theadaptive setting.{\\bf SST + STI:} We consider $(\\epsilon,\\delta)$-PAC maximum-selectionand ranking using pairwise comparisons for \ obreak{general}probabilistic models whose comparison probabilities satisfy\\emph{strong stochastic transitivity (SST)} and \\emph{stochastic triangle inequality (STI)}. Modifying the popular knockouttournament, we propose a simple maximum-selection algorithm that uses$\\mathcal{O}\\left(\\frac{n}{\\epsilon^2} \\log\\frac1{\\delta}\\right)$ comparisons, optimal up to a constantfactor. We then derive a general framework that uses noisy binarysearch to speed up many ranking algorithms, and combine it with mergesort to obtain a ranking algorithm that uses $\\mathcal{O}\\left(\\fracn{\\epsilon^2}\\log n(\\log \\log n)^3\\right)$ comparisons for$\\delta=\\frac1n$, optimal up to a $(\\log \\log n)^3$ factor.{\\bf SST +/- STI and Borda:} With just one simple natural assumption:\\emph{strong stochastic transitivity (SST)}, we show that maxing canbe performed with linearly many comparisons yet ranking requiresquadratically many. With no assumptions at all, we show that for theBorda-score metric, maximum selection can be performed with linearlymany comparisons and ranking can be performed with $\\cO(n\\log n)$comparisons.{\\bf General Transitive Models} With just \\emph{Weak Stochastic Transitivity (WST)}, we show that maxing requires $\\Omega(n^2)$comparisons and with slightly more restrictive \\emph{Medium Stochastic Transitivity (MST)}, we present a linear complexity maxingalgorithm. With \\emph{Strong Stochastic Transitivity (SST)} and\\emph{Stochastic Triangle Inequality (STI)}, we derive a rankingalgorithm with optimal $\\mathcal{O}(n\\log n)$ complexity and anoptimal algorithm that estimates all pairwise preferenceprobabilities.{\\bf Sequential and Competitive} We extend the well-known\\emph{secretary problem} to a probabilistic setting, and apply theintuition gained to derive the first query-optimal sequentialalgorithm for probabilistic-maxing. Furthermore, departing fromprevious assumptions, the algorithm and performance guarantees applyeven for infinitely many items, hence in particular do not requirea-priori knowledge of the number of items. The algorithm has linearcomplexity, and is optimal also in the streaming setting and for bothtraditional- and dueling-bandits. In a non-streaming setting, amodification of the algorithm is \\emph{competitive} in that itrequires essentially the lowest number of queries not just in theworst case, but for every underlying distribution.