THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
Priv’IT: Private and Sample Efficient Identity Testing
Bryan Cai · Constantinos Daskalakis · Gautam Kamath

Tue Aug 08 05:48 PM -- 06:06 PM (PDT) @ C4.8
in Privacy and security 1 »

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.

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Bryan Cai (MIT)
Constantinos Daskalakis (MIT)
Gautam Kamath (MIT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors