Timezone: »
We develop differentially private methods for estimating various distributional properties.Given a sample from a discrete distribution p, some functional f, and accuracy and privacy parameters alpha and epsilon, the goal is to estimate f(p) up to accuracy alpha, while maintaining epsilon-differential privacy of the sample.We prove almost-tight bounds on the sample size required for this problem for several functionals of interest, including support size, support coverage, and entropy.We show that the cost of privacy is negligible in a variety of settings, both theoretically and experimentally.Our methods are based on a sensitivity analysis of several state-of-the-art methods for estimating these properties with sublinear sample complexities
Author Information
Jayadev Acharya (Cornell University)
Gautam Kamath (MIT)
Ziteng Sun (Cornell University)
Huanyu Zhang (Cornell University)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: INSPECTRE: Privately Estimating the Unseen »
Wed. Jul 11th 04:15 -- 07:00 PM Room Hall B #59
More from the Same Authors
-
2021 : Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization »
Pranav Subramani · Nicholas Vadivelu · Gautam Kamath -
2021 : Remember What You Want to Forget: Algorithms for Machine Unlearning »
Ayush Sekhari · Ayush Sekhari · Jayadev Acharya · Gautam Kamath · Ananda Theertha Suresh -
2021 : The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection »
Shubhankar Mohapatra · Shubhankar Mohapatra · Sajin Sasy · Gautam Kamath · Xi He · Om Dipakbhai Thakkar -
2021 : Unbiased Statistical Estimation and Valid Confidence Sets Under Differential Privacy »
Christian Covington · Xi He · James Honaker · Gautam Kamath -
2021 : Learning with User-Level Privacy »
Daniel A Levy · Ziteng Sun · Kareem Amin · Satyen Kale · Alex Kulesza · Mehryar Mohri · Ananda Theertha Suresh -
2021 : Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data »
Gautam Kamath · Xingtu Liu · Huanyu Zhang -
2021 : Wide Network Learning with Differential Privacy »
Huanyu Zhang · Ilya Mironov · Meisam Hejazinia -
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 Social: Black in AI »
Black in AI Events · Kalesha Bullard · Stacy Fay Hobson · Gautam Kamath -
2023 Poster: Federated Heavy Hitter Recovery under Linear Sketching »
Adria Gascon · Peter Kairouz · Ziteng Sun · Ananda Suresh -
2023 Poster: User-level Private Stochastic Convex Optimization with Optimal Rates »
Raef Bassily · Ziteng Sun -
2023 Poster: Exploring the Limits of Model-Targeted Indiscriminate Data Poisoning Attacks »
Yiwei Lu · Gautam Kamath · Yaoliang Yu -
2023 Poster: Federated Linear Contextual Bandits with User-level Differential Privacy »
Ruiquan Huang · Huanyu Zhang · Luca Melis · Milan Shen · Meisam Hejazinia · Jing Yang -
2022 Workshop: Updatable Machine Learning »
Ayush Sekhari · Gautam Kamath · Jayadev Acharya -
2022 Workshop: Theory and Practice of Differential Privacy »
Gautam Kamath · Audra McMillan -
2022 Poster: Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data »
Gautam Kamath · Xingtu Liu · Huanyu Zhang -
2022 Oral: Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data »
Gautam Kamath · Xingtu Liu · Huanyu Zhang -
2022 Poster: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
2022 Spotlight: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
2021 Workshop: Theory and Practice of Differential Privacy »
Rachel Cummings · Gautam Kamath -
2021 : Opening Remarks »
Gautam Kamath · Rachel Cummings -
2021 Poster: PAPRIKA: Private Online False Discovery Rate Control »
Wanrong Zhang · Gautam Kamath · Rachel Cummings -
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: PAPRIKA: Private Online False Discovery Rate Control »
Wanrong Zhang · Gautam Kamath · Rachel Cummings -
2021 Spotlight: Robust Testing and Estimation under Manipulation Attacks »
Jayadev Acharya · Ziteng Sun · Huanyu Zhang -
2020 Poster: Privately Learning Markov Random Fields »
Huanyu Zhang · Gautam Kamath · Janardhan Kulkarni · Steven Wu -
2020 Poster: Context Aware Local Differential Privacy »
Jayadev Acharya · Kallista Bonawitz · Peter Kairouz · Daniel Ramage · Ziteng Sun -
2019 Poster: Communication-Constrained Inference and the Role of Shared Randomness »
Jayadev Acharya · Clément Canonne · Himanshu Tyagi -
2019 Oral: Communication-Constrained Inference and the Role of Shared Randomness »
Jayadev Acharya · Clément Canonne · Himanshu Tyagi -
2019 Poster: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
2019 Poster: Distributed Learning with Sublinear Communication »
Jayadev Acharya · Christopher De Sa · Dylan Foster · Karthik Sridharan -
2019 Oral: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
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 -
2017 Poster: Priv’IT: Private and Sample Efficient Identity Testing »
Bryan Cai · Constantinos Daskalakis · Gautam Kamath -
2017 Poster: Being Robust (in High Dimensions) Can Be Practical »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Ankur Moitra · Alistair Stewart -
2017 Talk: Priv’IT: Private and Sample Efficient Identity Testing »
Bryan Cai · Constantinos Daskalakis · Gautam Kamath -
2017 Talk: Being Robust (in High Dimensions) Can Be Practical »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Ankur Moitra · Alistair Stewart -
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