THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Poster
Maximum Selection and Ranking under Noisy Comparisons
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh

Tue Aug 08 01:30 AM -- 05:00 AM (PDT) @ Gallery #95
in Posters Tue »
We consider $(\epsilon,\delta)$-PAC maximum-selection and ranking using pairwise comparisons for \nobreak{general} probabilistic models whose comparison probabilities satisfy strong stochastic transitivity and stochastic triangle inequality. Modifying the popular knockout tournament, we propose a simple maximum-selection algorithm that uses $\mathcal{O}\left(\frac{n}{\epsilon^2} \left(1+\log \frac1{\delta}\right)\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.

Author Information

Moein Falahatgar (UCSD)
Alon Orlitsky (UCSD)
Venkatadheeraj Pichapati (University of California San Diego)
Ananda Theertha Suresh (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors