Timezone: »
A central server needs to perform statistical inference based on samples that are distributed over multiple users who can each send a message of limited length to the center. We study problems of distribution learning and identity testing in this distributed inference setting and examine the role of shared randomness as a resource. We propose a general purpose \textit{simulate-and-infer} strategy that uses only private-coin communication protocols and is sample-optimal for distribution learning. This general strategy turns out to be sample-optimal even for distribution testing among private-coin protocols. Interestingly, we propose a public-coin protocol that outperforms simulate-and-infer for distribution testing and is, in fact, sample-optimal. Underlying our public-coin protocol is a random hash that when applied to the samples minimally contracts the chi-squared distance of their distribution from the uniform distribution.
Author Information
Jayadev Acharya (Cornell University)
Clément Canonne (Stanford University)
Himanshu Tyagi (IISC)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Oral: Communication-Constrained Inference and the Role of Shared Randomness »
Thu. Jun 13th 11:00 -- 11:20 PM Room Room 102
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 -
2022 Workshop: Updatable Machine Learning »
Ayush Sekhari · Gautam Kamath · Jayadev Acharya -
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 -
2020 Poster: Context Aware Local Differential Privacy »
Jayadev Acharya · Kallista Bonawitz · Peter Kairouz · Daniel Ramage · Ziteng Sun -
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 Oral: Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters »
Jayadev Acharya · Ziteng Sun -
2018 Poster: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
2018 Oral: INSPECTRE: Privately Estimating the Unseen »
Jayadev Acharya · Gautam Kamath · Ziteng Sun · Huanyu Zhang -
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