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:1427-1436, 2018.

Abstract

We present a comprehensive understanding of three important problems in PAC preference learning: maximum selection (maxing), ranking, and estimating all pairwise preference probabilities, in the adaptive setting. With just Weak Stochastic Transitivity, we show that maxing requires Ω(n2) 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 O(nlogn) complexity and an optimal algorithm that estimates all pairwise preference probabilities.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-falahatgar18a, title = {The Limits of Maxing, Ranking, and Preference Learning}, author = {Falahatgar, Moein and Jain, Ayush and Orlitsky, Alon and Pichapati, Venkatadheeraj and Ravindrakumar, Vaishakh}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1427--1436}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/falahatgar18a/falahatgar18a.pdf}, url = {https://proceedings.mlr.press/v80/falahatgar18a.html}, abstract = {We present a comprehensive understanding of three important problems in PAC preference learning: maximum selection (maxing), ranking, and estimating 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.} }
Endnote
%0 Conference Paper %T The Limits of Maxing, Ranking, and Preference Learning %A Moein Falahatgar %A Ayush Jain %A Alon Orlitsky %A Venkatadheeraj Pichapati %A Vaishakh Ravindrakumar %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-falahatgar18a %I PMLR %P 1427--1436 %U https://proceedings.mlr.press/v80/falahatgar18a.html %V 80 %X We present a comprehensive understanding of three important problems in PAC preference learning: maximum selection (maxing), ranking, and estimating 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.
APA
Falahatgar, M., Jain, A., Orlitsky, A., Pichapati, V. & Ravindrakumar, V.. (2018). The Limits of Maxing, Ranking, and Preference Learning. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1427-1436 Available from https://proceedings.mlr.press/v80/falahatgar18a.html.

Related Material