Timezone: »
Poster
A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda Suresh
Symmetric distribution properties such as support size, support coverage, entropy, and proximity to uniformity, arise in many applications. Recently, researchers applied different estimators and analysis tools to derive asymptotically sample-optimal approximations for each of these properties. We show that a single, simple, plug-in estimator---\emph{profile maximum likelihood (PML)}--is sample competitive for all symmetric properties, and in particular is asymptotically sample-optimal for all the above properties.
[
PDF]
[
Summary/Notes]
Summary/Notes]
Author Information
Jayadev Acharya (Cornell University)
Hirakendu Das (Yahoo!)
Alon Orlitsky (UCSD)
Ananda Suresh (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Tue. Aug 8th 06:06 -- 06:24 AM Room C4.8
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 -
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 Workshop: Updatable Machine Learning »
Ayush Sekhari · Gautam Kamath · Jayadev Acharya -
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 Poster: Robust Testing and Estimation under Manipulation Attacks »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
2021 Poster: Principal Bit Analysis: Autoencoding with Schur-Concave Loss »
Sourbh Bhadane · Aaron Wagner · Jayadev Acharya -
2021 Spotlight: Principal Bit Analysis: Autoencoding with Schur-Concave Loss »
Sourbh Bhadane · Aaron Wagner · Jayadev Acharya -
2021 Spotlight: Robust Testing and Estimation under Manipulation Attacks »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
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: Context Aware Local Differential Privacy »
Jayadev Acharya · Kallista Bonawitz · Peter Kairouz · Daniel Ramage · Ziteng Sun -
2020 Poster: Data Amplification: Instance-Optimal Property Estimation »
Yi Hao · Alon Orlitsky -
2019 Poster: Communication-Constrained Inference and the Role of Shared Randomness »
Jayadev Acharya · Clément Canonne · Himanshu Tyagi -
2019 Poster: Agnostic Federated Learning »
Mehryar Mohri · Gary Sivek · Ananda Suresh -
2019 Oral: Agnostic Federated Learning »
Mehryar Mohri · Gary Sivek · Ananda Suresh -
2019 Oral: Communication-Constrained Inference and the Role of Shared Randomness »
Jayadev Acharya · Clément Canonne · Himanshu Tyagi -
2019 Poster: Distributed Learning with Sublinear Communication »
Jayadev Acharya · Christopher De Sa · Dylan Foster · Karthik Sridharan -
2019 Oral: Distributed Learning with Sublinear Communication »
Jayadev Acharya · Christopher De Sa · Dylan Foster · Karthik Sridharan -
2019 Poster: Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters »
Jayadev Acharya · Ziteng Sun -
2019 Poster: Doubly-Competitive Distribution Estimation »
Yi Hao · Alon Orlitsky -
2019 Oral: Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters »
Jayadev Acharya · Ziteng Sun -
2019 Oral: Doubly-Competitive Distribution Estimation »
Yi Hao · Alon Orlitsky -
2018 Poster: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
2018 Poster: The Limits of Maxing, Ranking, and Preference Learning »
Moein Falahatgar · Ayush Jain · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar -
2018 Oral: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
2018 Oral: The Limits of Maxing, Ranking, and Preference Learning »
Moein Falahatgar · Ayush Jain · Alon Orlitsky · Venkatadheeraj Pichapati · Vaishakh Ravindrakumar -
2017 Poster: Maximum Selection and Ranking under Noisy Comparisons »
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh -
2017 Talk: Maximum Selection and Ranking under Noisy Comparisons »
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh