Differentially Private Identity and Equivalence Testing of Discrete Distributions
Differentially Private Identity and Equivalence Testing of Discrete Distributions
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
M. Aliakbarpour;Ilias Diakonikolas;R. Rubinfeld
中科院分区：
文献类型：
--
作者：
M. Aliakbarpour;Ilias Diakonikolas;R. Rubinfeld
本文研究了离散总体上随机样本的同一性和等价性检验的基本问题。我们的目标是开发高效的测试人员，同时保证人口中个人的差异隐私。我们为这些问题提供样本有效的差异私有测试。我们的理论结果显着提高了最知名的算法的身份测试，是第一个结果的私人等价性测试。我们工作的概念信息是，存在私人假设测试者，其样本效率几乎与非私人测试者一样。我们对合成数据的算法进行了实验评估。我们的实验表明，我们的私人测试人员实现小的I型和II型错误的样本量次线性域大小的基础分布。
We study the fundamental problems of identity and equivalence 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 provide sample-efficient differentially private testers for these problems. Our theoretical results significantly improve over the best known algorithms for identity testing, and are the first results for private equivalence testing. The conceptual message of our work is that there exist private hypothesis 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.