Priv'IT: Private and Sample Efficient Identity Testing

Abstract

We develop differentially private hypothesis testing methods for the small sample regime. Given a sample $\mathcal{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 ${\beta }_{\mathrm{I}}$ and ${\beta }_{\mathrm{II}}$ for the type I and type II errors of our test, the goal is to distinguish between $p=q$ and $d_{\mathrm{TV}}(p,q)\ge \alpha$. We provide theoretical bounds for the sample size $|\mathcal{D}|$ so that our method both satisfies $(\epsilon ,0)$-differential privacy, and guarantees ${\beta }_{\mathrm{I}}$ and ${\beta }_{\mathrm{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 ${\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.

To appear in ICML 2017

References in corpus (3)

• Optimal Testing for Properties of Distributions
• Revisiting Differentially Private Hypothesis Tests for Categorical Data
• A New Class of Private Chi-Square Tests

Cited by in corpus (2)

• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms