Priv'IT: Private and Sample Efficient Identity Testing
This work addresses the challenge of performing private statistical tests with limited data, which is crucial for privacy-sensitive applications like healthcare or social science research, though it is incremental as it builds on prior private testing methods.
The paper tackles the problem of differentially private hypothesis testing for categorical distributions in the small sample regime, providing a method that achieves privacy and error guarantees with improved sample complexity compared to existing approaches.
We develop differentially private hypothesis testing methods for the small sample regime. Given a sample $\cal D$ from a categorical distribution $p$ over some domain $Σ$, an explicitly described distribution $q$ over $Σ$, some privacy parameter $\varepsilon$, accuracy parameter $α$, and requirements $β_{\rm I}$ and $β_{\rm II}$ for the type I and type II errors of our test, the goal is to distinguish between $p=q$ and $d_{\rm{TV}}(p,q) \geq α$. We provide theoretical bounds for the sample size $|{\cal D}|$ so that our method both satisfies $(\varepsilon,0)$-differential privacy, and guarantees $β_{\rm I}$ and $β_{\rm II}$ 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.