Timezone: »

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.

Author Information

Moein Falahatgar (UC San Diego)
Ayush Jain (UC San Diego)
Alon Orlitsky (UCSD)
Venkatadheeraj Pichapati (University of California San Diego)
Vaishakh Ravindrakumar (UC San Diego)

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

More from the Same Authors