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 $\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.

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