Priv'IT: Private and sample efficient identity testing

© 2017 by the author(s). We develop differentially private hypothesis testing methods for the small sample regime. Given a sample V from a categorical distribution p over some domain ∑, an explicitly described distribution q over ∑, some privacy parameter e, accuracy parameter ϵ, and requirements βI and βII for the type I and type II errors of our test, the goal is to distinguish between p = q and dTV(p, q) ≥ α. We provide theoretical bounds for the sample size \V\ so that our method both satisfies (e, 0)-differential privacy, and guarantees βi and βu 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 χ2-test with noisy counts, or standard approaches such as repetition for endowing non-private χ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 (Gaboardi et al., 2016; Kifer & Rogers, 2017)