Timezone: »

Poster
The Limits of Maxing, Ranking, and Preference Learning
Moein Falahatgar · Ayush Jain · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar

Wed Jul 11 09:15 AM -- 12:00 PM (PDT) @ Hall B #36
We present a comprehensive understanding of three important problems in PAC preference learning: maximum selection (maxing), ranking, and estimating \emph{all} pairwise preference probabilities, in the adaptive setting. With just Weak Stochastic Transitivity, we show that maxing requires $\Omega(n^2)$ comparisons and with slightly more restrictive Medium Stochastic Transitivity, we present a linear complexity maxing algorithm. With Strong Stochastic Transitivity and Stochastic Triangle Inequality, we derive a ranking algorithm with optimal $\mathcal{O}(n\log n)$ complexity and an optimal algorithm that estimates all pairwise preference probabilities.