Timezone: »

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

Wed Jul 11 05:30 AM -- 05:50 AM (PDT) @ A5
We present a comprehensive understanding of three important problemsin PAC preference learning: maximum selection (maxing), ranking, andestimating \emph{all} pairwise preference probabilities, in theadaptive setting. With just Weak Stochastic Transitivity, we show thatmaxing requires $\Omega(n^2)$ comparisons and with slightly morerestrictive Medium Stochastic Transitivity, we present a linearcomplexity maxing algorithm. With Strong Stochastic Transitivity andStochastic Triangle Inequality, we derive a ranking algorithm withoptimal $\mathcal{O}(n\log n)$ complexity and an optimal algorithmthat 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