Timezone: »
Poster
Maximum Selection and Ranking under Noisy Comparisons
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh
We consider $(\epsilon,\delta)$-PAC maximum-selection and ranking
using pairwise comparisons for \nobreak{general} probabilistic models whose
comparison probabilities satisfy strong stochastic
transitivity and stochastic triangle inequality.
Modifying the popular knockout tournament, we propose a simple
maximum-selection algorithm that uses $\mathcal{O}\left(\frac{n}{\epsilon^2}
\left(1+\log \frac1{\delta}\right)\right)$ comparisons, optimal up to a constant
factor. We then derive a general framework that uses noisy binary
search to speed up many ranking algorithms, and
combine it with merge sort to obtain a ranking algorithm that uses
$\mathcal{O}\left(\frac n{\epsilon^2}\log n(\log \log n)^3\right)$ comparisons
for $\delta=\frac1n$, optimal up to a $(\log \log n)^3$ factor.
Author Information
Moein Falahatgar (UCSD)
Alon Orlitsky (UCSD)
Venkatadheeraj Pichapati (University of California San Diego)
Ananda Theertha Suresh (Google Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: Maximum Selection and Ranking under Noisy Comparisons »
Tue. Aug 8th 04:24 -- 04:42 AM Room C4.1
More from the Same Authors
-
2021 : Remember What You Want to Forget: Algorithms for Machine Unlearning »
Ayush Sekhari · Ayush Sekhari · Jayadev Acharya · Gautam Kamath · Ananda Theertha Suresh -
2021 : On the Renyi Differential Privacy of the Shuffle Model »
Antonious Girgis · Deepesh Data · Suhas Diggavi · Ananda Theertha Suresh · Peter Kairouz -
2021 : Learning with User-Level Privacy »
Daniel A Levy · Ziteng Sun · Kareem Amin · Satyen Kale · Alex Kulesza · Mehryar Mohri · Ananda Theertha Suresh -
2023 : Federated Heavy Hitter Recovery under Linear Sketching »
Adria Gascon · Peter Kairouz · Ziteng Sun · Ananda Suresh -
2023 : SpecTr: Fast Speculative Decoding via Optimal Transport »
Ziteng Sun · Ananda Suresh · Jae Ro · Ahmad Beirami · Himanshu Jain · Felix Xinnan Yu · Michael Riley · Sanjiv Kumar -
2023 Poster: Subset-Based Instance Optimality in Private Estimation »
Travis Dick · Alex Kulesza · Ziteng Sun · Ananda Suresh -
2023 Poster: Federated Heavy Hitter Recovery under Linear Sketching »
Adria Gascon · Peter Kairouz · Ziteng Sun · Ananda Suresh -
2023 Poster: Algorithms for bounding contribution for histogram estimation under user-level privacy »
Yuhan Liu · Ananda Suresh · Wennan Zhu · Peter Kairouz · Marco Gruteser -
2022 Poster: The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning »
Wei-Ning Chen · Christopher Choquette Choo · Peter Kairouz · Ananda Suresh -
2022 Spotlight: The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning »
Wei-Ning Chen · Christopher Choquette Choo · Peter Kairouz · Ananda Suresh -
2022 Poster: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
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 -
2022 Spotlight: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
2021 Spotlight: A Discriminative Technique for Multiple-Source Adaptation »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh · Ningshan Zhang -
2021 Poster: A Discriminative Technique for Multiple-Source Adaptation »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh · Ningshan Zhang -
2021 Poster: Compressed Maximum Likelihood »
Yi Hao · Alon Orlitsky -
2021 Spotlight: Relative Deviation Margin Bounds »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh -
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 Poster: Relative Deviation Margin Bounds »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh -
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: SCAFFOLD: Stochastic Controlled Averaging for Federated Learning »
Sai Praneeth Reddy Karimireddy · Satyen Kale · Mehryar Mohri · Sashank Jakkam Reddi · Sebastian Stich · Ananda Theertha Suresh -
2020 Poster: Optimal Robust Learning of Discrete Distributions from Batches »
Ayush Jain · Alon Orlitsky -
2020 Poster: FedBoost: A Communication-Efficient Algorithm for Federated Learning »
Jenny Hamer · Mehryar Mohri · Ananda Theertha Suresh -
2020 Poster: Data Amplification: Instance-Optimal Property Estimation »
Yi Hao · Alon Orlitsky -
2019 Poster: Agnostic Federated Learning »
Mehryar Mohri · Gary Sivek · Ananda Suresh -
2019 Oral: Agnostic Federated Learning »
Mehryar Mohri · Gary Sivek · Ananda Suresh -
2019 Poster: Doubly-Competitive Distribution Estimation »
Yi Hao · Alon Orlitsky -
2019 Oral: Doubly-Competitive Distribution Estimation »
Yi Hao · Alon Orlitsky -
2018 Poster: The Limits of Maxing, Ranking, and Preference Learning »
Moein Falahatgar · Ayush Jain · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar -
2018 Oral: The Limits of Maxing, Ranking, and Preference Learning »
Moein Falahatgar · Ayush Jain · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar -
2017 Poster: Distributed Mean Estimation with Limited Communication »
Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2017 Poster: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda 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: Distributed Mean Estimation with Limited Communication »
Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan