Differentially Private Testing of Identity and Closeness of Discrete Distributions

By Jayadev Acharya, Ziteng Sun, Huanyu Zhang. 2017

83 citations recorded by the source corpus.

We study the fundamental problems of identity testing (goodness of fit), and closeness testing (two sample test) of distributions over $k$ elements, under differential privacy. While the problems have a long history in statistics, finite sample bounds for these problems have only been established recently. In this work, we derive upper and lower bounds on the sample complexity of both the problems under $(\varepsilon, \delta)$-differential privacy. We provide optimal sample complexity algorithms for identity testing problem for all parameter ranges, and the first results for closeness testing. Our closeness testing bounds are optimal in the sparse regime where the number of samples is at most $k$. Our upper bounds are obtained by privatizing non-private estimators for these problems. The non-private estimators are chosen to have small sensitivity. We propose a general framework to establish lower bounds on the sample complexity of statistical tasks under differential privacy. We show a bound on differentially private algorithms in terms of a coupling between the two hypothesis classes we aim to test. By constructing carefully chosen priors over the hypothesis classes, and using Le Cam's two point theorem we provide a general mechanism for proving lower bounds. We believe that the framework can be used to obtain strong lower bounds for other statistical tasks under privacy.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

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 Electrical and Electronic Engineering

Citations in the corpus

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].”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, background): “Acharya, Sun, and Zhang [2] showed that Θ( √ k ) is the optimal dependence under approximate central privacy, and Θ( k ) is optimal for the strictly more private model of approximate sequentially interactive local privacy [3, 5] (see Section 2 for a deﬁnition of local privacy).”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, result): “A similar observation was made independently in (Acharya et al., 2017).”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, background): “Our first result is a complete characterization of the sample complexity under ε-LDP up to constant factors.”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, methodology): “An indirect proof of the interactive lower bound in the L1 case with p0 uniform, can be found in Amin et al. [2019]. The role of interactivity in locally private testing is studied in Joseph et al.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “Under the notion of (global) differential privacy (DP) [28], identity testing has been considered in [11], [20], with a complete characterization of the sample complexity derived in [8].”
Pan-Private Uniformity Testing (2019, methodology): “First note that the last three terms in this lower bound are inherited directly from the centrally private lower bound [4].”
Private Mean Estimation of Heavy-Tailed Distributions (2020, methodology): “Then by Theorem 11 of [ASZ18], we get that We conclude by using the equivalence of pure and approximate DP for testing problems (e.g., Lemma 5 of [ASZ18]).”