Differentially Private Testing of Identity and Closeness of Discrete Distributions
Differentially Private Testing of Identity and Closeness of Discrete Distributions
复制标题
DOI：
--
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
Jayadev Acharya;Ziteng Sun;Huanyu Zhang
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;Ziteng Sun;Huanyu Zhang
我们研究了差分隐私下$k$元素上分布的同一性测试（拟合优度）和接近性测试（两样本测试）的基本问题。虽然这些问题在统计学中有很长的历史，但这些问题的有限样本界限是最近才建立起来的。在这项工作中，我们推导了$(\varepsilon, \delta)$ -微分隐私下这两个问题的样本复杂度的上界和下界。我们为所有参数范围的同一性测试问题提供了最优的样本复杂度算法，并为接近性测试提供了第一个结果。我们的接近性测试边界在样本数量最多为$k$的稀疏区域是最优的。我们的上界是通过将这些问题的非私有估计量私有化得到的。选择非私有估计量以使其具有较小的灵敏度。我们提出了一个通用框架来建立差分隐私下统计任务样本复杂度的下界。根据我们要测试的两个假设类之间的耦合，我们展示了差分私有算法的界。通过在假设类上构造精心选择的先验，并使用Le Cam的两点定理，我们提供了证明下界的一般机制。我们相信该框架可以用于在隐私条件下获得其他统计任务的强下界。
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.