Priv'IT: Private and Sample Efficient Identity Testing

arXiv1703.10127MaRDI QIDQ6284932

Author name not available (Why is that?)

Publication date: 29 March 2017

Abstract: We develop differentially private hypothesis testing methods for the small sample regime. Given a sample $calD$ from a categorical distribution $p$ over some domain $Sigma$, an explicitly described distribution $q$ over $Sigma$, some privacy parameter $varepsilon$, accuracy parameter $alpha$, and requirements $$ and $$ for the type I and type II errors of our test, the goal is to distinguish between $p=q$ and $d_{mTV}(p,q)geqalpha$. We provide theoretical bounds for the sample size $|calD|$ so that our method both satisfies $(varepsilon,0)$-differential privacy, and guarantees $$ and $$ 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 $ch{i}^2$-test with noisy counts, or standard approaches such as repetition for endowing non-private $ch{i}^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.

Has companion code repository: https://github.com/hoonose/privit

This page was built for publication: Priv'IT: Private and Sample Efficient Identity Testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284932)