Skip to yearly menu bar Skip to main content


Oral

Differentially Private Identity and Equivalence Testing of Discrete Distributions

Maryam Aliakbarpour · Ilias Diakonikolas · MIT Ronitt Rubinfeld

Abstract:

We study the fundamental problems of identity and equivalence testing over a discrete populationfrom random samples. Our goal is to develop efficient testers while guaranteeingdifferential 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 thatthere 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.

Chat is not available.