The Limits of Maxing, Ranking, and Preference Learning


Moein Falahatgar, Ayush Jain, Alon Orlitsky, Venkatadheeraj Pichapati, Vaishakh Ravindrakumar ;
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1426-1435, 2018.


We present a comprehensive understanding of three important problemsin PAC preference learning: maximum selection (maxing), ranking, andestimating 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.

Related Material