Timezone: »
Poster
The Limits of Maxing, Ranking, and Preference Learning
Moein Falahatgar · Ayush Jain · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar
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)
-
2018 Oral: The Limits of Maxing, Ranking, and Preference Learning »
Wed. Jul 11th 12:30 -- 12:50 PM Room A5
More from the Same Authors
-
2023 Poster: Efficient List-Decodable Regression using Batches »
Abhimanyu Das · Ayush Jain · Weihao Kong · Rajat Sen -
2022 Poster: TURF: Two-Factor, Universal, Robust, Fast Distribution Learning Algorithm »
Yi Hao · Ayush Jain · Alon Orlitsky · Vaishakh Ravindrakumar -
2022 Spotlight: TURF: Two-Factor, Universal, Robust, Fast Distribution Learning Algorithm »
Yi Hao · Ayush Jain · Alon Orlitsky · Vaishakh Ravindrakumar -
2021 Poster: Compressed Maximum Likelihood »
Yi Hao · Alon Orlitsky -
2021 Spotlight: Compressed Maximum Likelihood »
Yi Hao · Alon Orlitsky -
2021 Poster: Robust Density Estimation from Batches: The Best Things in Life are (Nearly) Free »
Ayush Jain · Alon Orlitsky -
2021 Oral: Robust Density Estimation from Batches: The Best Things in Life are (Nearly) Free »
Ayush Jain · Alon Orlitsky -
2020 Poster: Optimal Sequential Maximization: One Interview is Enough! »
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati -
2020 Poster: Optimal Robust Learning of Discrete Distributions from Batches »
Ayush Jain · Alon Orlitsky -
2020 Poster: Data Amplification: Instance-Optimal Property Estimation »
Yi Hao · Alon Orlitsky -
2019 Poster: Doubly-Competitive Distribution Estimation »
Yi Hao · Alon Orlitsky -
2019 Oral: Doubly-Competitive Distribution Estimation »
Yi Hao · Alon Orlitsky -
2017 Poster: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda Suresh -
2017 Poster: Maximum Selection and Ranking under Noisy Comparisons »
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh -
2017 Talk: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda Suresh -
2017 Talk: Maximum Selection and Ranking under Noisy Comparisons »
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh