Timezone: »
Oral
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 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)
-
2018 Poster: The Limits of Maxing, Ranking, and Preference Learning »
Wed. Jul 11th 04:15 -- 07:00 PM Room Hall B #36
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