Abstract

We study the fundamental problems of identity and equivalence testing over a discrete population from random samples. Our goal is to develop efficient testers while guaranteeing differential p vacy to the individuals of the population. We provide sample-efficient differentially private tester for these problems. Our theoretical results significantly improve over the best known algorithms for identity testing, and are the first results for vate equivalence testing. The conceptual message of our work is that there exist private hypothesis testers that are nearly as sample-efficient as thei non-private counterparts. We perform an experimental evaluation of our algorithms on synthetic data. Our experiments illustrate that our private testers achieve small type I and type II errors wit sample size sublinear in the domain size of the underlying distributions.