Differentially Private Identity and Closeness Testing of Discrete Distributions

Abstract

We investigate the problems of identity and closeness 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 describe an approach that yields sample-efficient differentially private testers for these problems. Our theoretical results show that there exist private identity and closeness 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 I and type II errors with sample size sublinear in the domain size of the underlying distributions.

arXiv commentSubmitted, May 2017

References in corpus (4)

• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Optimal Testing for Properties of Distributions
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• A New Class of Private Chi-Square Tests

Cited by in corpus (6)

• Privately Learning High-Dimensional Distributions
• A Primer on Private Statistics
• BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model
• Locally Private Hypothesis Selection
• Private Identity Testing for High-Dimensional Distributions
• SoK: Chasing Accuracy and Privacy, and Catching Both in Differentially Private Histogram Publication