Timezone: »
We develop differentially private hypothesis testing methods for the small sample regime. Given a sample D from a categorical distribution p over some domain Sigma, an explicitly described distribution q over Sigma, some privacy parameter epsilon, accuracy parameter alpha, and requirements betaI$ and betaII for the type I and type II errors of our test, the goal is to distinguish between p=q and dtv(p,q) > alpha. We provide theoretical bounds for the sample size |D| so that our method both satisfies (epsilon,0)-differential privacy, and guarantees betaI and betaII type I and type II errors. We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the chi^2-test with noisy counts, or standard approaches such as repetition for endowing non-private chi^2-style statistics with differential privacy guarantees. We experimentally compare the sample complexity of our method to that of recently proposed methods for private hypothesis testing.
Author Information
Bryan Cai (MIT)
Constantinos Daskalakis (MIT)
Gautam Kamath (MIT)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Priv’IT: Private and Sample Efficient Identity Testing »
Wed. Aug 9th 08:30 AM -- 12:00 PM Room Gallery #33
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 : Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data »
Gautam Kamath · Xingtu Liu · Huanyu Zhang -
2023 Poster: Exploring the Limits of Indiscriminate Data Poisoning Attacks »
Yiwei Lu · Gautam Kamath · Yaoliang Yu -
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 Poster: Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis -
2022 Oral: Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data »
Gautam Kamath · Xingtu Liu · Huanyu Zhang -
2022 Spotlight: Score-Guided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis -
2021 Workshop: Theory and Practice of Differential Privacy »
Rachel Cummings · Gautam Kamath -
2021 : Opening Remarks »
Gautam Kamath · Rachel Cummings -
2021 Poster: Statistical Estimation from Dependent Data »
Vardis Kandiros · Yuval Dagan · Nishanth Dikkala · Surbhi Goel · Constantinos Daskalakis -
2021 Spotlight: Statistical Estimation from Dependent Data »
Vardis Kandiros · Yuval Dagan · Nishanth Dikkala · Surbhi Goel · Constantinos Daskalakis -
2021 Poster: PAPRIKA: Private Online False Discovery Rate Control »
Wanrong Zhang · Gautam Kamath · Rachel Cummings -
2021 Spotlight: PAPRIKA: Private Online False Discovery Rate Control »
Wanrong Zhang · Gautam Kamath · Rachel Cummings -
2020 Poster: SGD Learns One-Layer Networks in WGANs »
Qi Lei · Jason Lee · Alexandros Dimakis · Constantinos Daskalakis -
2020 Poster: Privately Learning Markov Random Fields »
Huanyu Zhang · Gautam Kamath · Janardhan Kulkarni · Steven Wu -
2019 Poster: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
2019 Oral: Sever: A Robust Meta-Algorithm for Stochastic Optimization »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Jacob Steinhardt · Alistair Stewart -
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: Being Robust (in High Dimensions) Can Be Practical »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Ankur Moitra · Alistair Stewart -
2017 Talk: Being Robust (in High Dimensions) Can Be Practical »
Ilias Diakonikolas · Gautam Kamath · Daniel Kane · Jerry Li · Ankur Moitra · Alistair Stewart