Skip to yearly menu bar Skip to main content


Poster

Priv’IT: Private and Sample Efficient Identity Testing

Bryan Cai · Constantinos Daskalakis · Gautam Kamath

Gallery #33

Abstract:

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.

Live content is unavailable. Log in and register to view live content