Di erentially Private Testing of Identity and Closeness of Discrete Distributions
We study the fundamental problems of identity testing (goodness of fit), and closeness testing (two sample test) of distributions over k elements, under di erential 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 (Á, ")-di erential privacy. We provide sample optimal 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 di erential privacy. We show a bound on di erentially private algorithms in terms of a coupling between the two hypothesis classes we aim to test. By carefully constructing 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.
This paper studies two basic testing problems for distributions over finite domains. The first is the identity testing problem, where given a known distribution q and i.i.d. samples from p, the goal is to distinguish between the case where p = q and the case where the distributions are far in total variation distance. A second, closely related problem, is the closeness testing problem where q is also taken to be an unknown distribution accessed via i.i.d. samples. This submission studies the sample complexity of solving these problems subject to differential privacy. For identity testing, it gives sample complexity upper and lower bounds which match up to constant factors. For closeness testing, it gives bounds which match in the "sparse" regime where the data domain is much larger than the accuracy/privacy parameters, and which match up to polynomial factors otherwise.  The private identity testing problem that the authors consider had been studied in prior work of Cai, Diakonikolas, and Kamath, and this submission gives an improved (and simplified) upper bound. Private closeness testing appears not to have been studied before. (Independent work of Aliakbarpour, Diakonikolas, and Rubinfeld gives similar upper bounds which are complemented by experimental results, but does not study lower bounds.)  The upper bounds are obtained by a) privatizing a reduction from identity testing to uniformity testing, due to Goldreich, and b) modifying recent uniformity and closeness testers to guarantee differential privacy. These modifications turn out to be relatively straightforward, as the test statistics introduced in these prior works have low sensitivity. Hence, private testers can be obtained by making randomized decisions based on these test statistics, instead of deterministically thresholding them.  Lower bounds follow from a new coupling technique. The idea is to construct two distributions on finite samples that an accurate tester must be able to distinguish. However, if there is a coupling between these distributions where the samples have low expected Hamming distance, then differentially private algorithms will have a hard time telling them apart. This is a nice trick which is powerful enough to prove tight lower bounds, and extends generically to give lower bounds for (eps, delta)-DP.  To summarize, the results are fairly interesting, deftly leverage recent advances in distribution testing, and introduce some nice new techniques. I think this is a solid paper for NIPS.  After reading author feedback: I still believe this is a strong paper and should be accepted.