 Main
Maxing, Ranking and Preference Learning
 Pichapati, Venkatadheeraj
 Advisor(s): Orlitsky, Alon
Abstract
PAC maximum selection (maxing) and ranking of $n$ elements via random
pairwise comparisons have diverse applications and have been studied
under many models and assumptions. We consider $(\epsilon,\delta)$PAC
maxing and ranking using pairwise comparisons for \nobreak{general}
probabilistic models. We present a comprehensive understanding of
three important problems in PAC preference learning: maxing, ranking,
and estimating \emph{all} pairwise preference probabilities, in the
adaptive setting.
{\bf SST + STI:} We consider $(\epsilon,\delta)$PAC maximumselection
and ranking using pairwise comparisons for \nobreak{general}
probabilistic models whose comparison probabilities satisfy
\emph{strong stochastic transitivity (SST)} and \emph{stochastic
triangle inequality (STI)}. Modifying the popular knockout
tournament, we propose a simple maximumselection algorithm that uses
$\mathcal{O}\left(\frac{n}{\epsilon^2} \log
\frac1{\delta}\right)$ comparisons, optimal up to a constant
factor. We then derive a general framework that uses noisy binary
search to speed up many ranking algorithms, and combine it with merge
sort to obtain a ranking algorithm that uses $\mathcal{O}\left(\frac
n{\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 can
be performed with linearly many comparisons yet ranking requires
quadratically many. With no assumptions at all, we show that for the
Bordascore metric, maximum selection can be performed with linearly
many 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 maxing
algorithm. With \emph{Strong Stochastic Transitivity (SST)} and
\emph{Stochastic Triangle Inequality (STI)}, we derive a ranking
algorithm with optimal $\mathcal{O}(n\log n)$ complexity and an
optimal algorithm that estimates all pairwise preference
probabilities.
{\bf Sequential and Competitive} We extend the wellknown
\emph{secretary problem} to a probabilistic setting, and apply the
intuition gained to derive the first queryoptimal sequential
algorithm for probabilisticmaxing. Furthermore, departing from
previous assumptions, the algorithm and performance guarantees apply
even for infinitely many items, hence in particular do not require
apriori knowledge of the number of items. The algorithm has linear
complexity, and is optimal also in the streaming setting and for both
traditional and duelingbandits. In a nonstreaming setting, a
modification of the algorithm is \emph{competitive} in that it
requires essentially the lowest number of queries not just in the
worst case, but for every underlying distribution.
Main Content
Enter the password to open this PDF file:













