Timezone: »

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

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)

More from the Same Authors