Differentially Private Identity and Closeness Testing of Discrete Distributions

By Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld. 2017

15 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

The structure of optimal private tests for simple hypotheses (2018, background): “[3] and [4] have given worst-case nearly optimal algorithms for goodness-of-fit and closeness testing of arbitrary discrete distributions.”
BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “As a start, one can differentially privately evaluate whether the distributions are different using a small sample of records from both groups using the techniques of [1, 4].”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “Both [16], and [7] consider only pure-differential privacy, which are a special case of our results.”
INSPECTRE: Privately Estimating the Unseen (2018, background): “Perhaps most relevant to this work are (Cai et al., 2017; Acharya et al., 2017c; Aliakbarpour et al., 2017), which study the sample complexity of differentialy privately performing classical distribution testing problems, including identity and closeness testing.”
Test without Trust: Optimal Locally Private Distribution Testing (2018, background): “Identity testing in the finite sample setting has been considered in [10, 7], with a complete characterization of sample complexity derived in [6].”