Maryam Aliakbarpour
Differentially Private Identity and Equivalence Testing of Discrete
Distributions

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 privacy to the individuals of the population. We provide
sample-efficient differentially private testers for these problems.
Our theoretical results significantly improve over the best known
algorithms for identity testing, and are the first results for private
equivalence testing. The conceptual message of our work is that there
exist private hypothesis testers that are nearly as sample-efficient
as their non-private counterparts.  We perform an experimental
evaluation of our algorithms on synthetic data. Our experiments
illustrate that our private testers achieve small type \rom{1} and
type \rom{2} errors with sample size {\em sublinear} in the domain
size of the underlying distributions.  Specifically, the sample
complexity of our private identity tester significantly outperforms
the sample complexity of recently proposed methods for this problem.