Minimax Rates of Estimating Approximate Differential Privacy
Minimax Rates of Estimating Approximate Differential Privacy
复制标题
估计近似差分隐私的极小极大率
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sewoong Oh
中科院分区：
文献类型：
--
作者：
Xiyang Liu;Sewoong Oh
差异隐私已经成为一个被广泛接受的隐私概念，导致了许多私有化机制的引入和部署。然而，确保隐私保证是一个容易出错的过程，无论是在设计机制和实现这些机制。如果我们有一个数据驱动的方法来验证隐私保证，从黑盒访问到机制，这两种类型的错误都会大大减少。我们把它作为一个属性估计问题，并研究基本的权衡估计隐私保证的准确性和所需的样本数量。我们介绍了一种新的估计，使用多项式逼近的精心选择的程度，以最佳的权衡偏差和方差。与$n$样本，我们表明，这种估计实现了一个简单的插件估计与$n \ln n$样本，一种现象称为有效的样本大小放大的性能。通过与一个匹配的基本下界比较，证明了该估计量的极大极小最优性。
Differential privacy has become a widely accepted notion of privacy, leading to the introduction and deployment of numerous privatization mechanisms. However, ensuring the privacy guarantee is an error-prone process, both in designing mechanisms and in implementing those mechanisms. Both types of errors will be greatly reduced, if we have a data-driven approach to verify privacy guarantees, from a black-box access to a mechanism. We pose it as a property estimation problem, and study the fundamental trade-offs involved in the accuracy in estimated privacy guarantees and the number of samples required. We introduce a novel estimator that uses polynomial approximation of a carefully chosen degree to optimally trade-off bias and variance. With $n$ samples, we show that this estimator achieves performance of a straightforward plug-in estimator with $n \ln n$ samples, a phenomenon referred to as effective sample size amplification. The minimax optimality of the proposed estimator is proved by comparing it to a matching fundamental lower bound.
哪些分布距离是可次线性测试的？
DOI：
--
发表时间：
2018
期刊：
Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Daskalakis, Constantinos;Kamath, Gautam;Wright, John
通讯作者：
Wright, John
离散分布之间 KL 散度的极小最大速率最优估计。
DOI：
--
发表时间：
2016
期刊：
International Symposium on Information Theory and its Applications. International Symposium on Information Theory and its Applications
影响因子：
--
作者：
Han,Yanjun;Jiao,Jiantao;Weissman,Tsachy
通讯作者：
Weissman,Tsachy
影响因子：
4.5
作者：
Berrett, Thomas B.;Samworth, Richard J.;Yuan, Ming
通讯作者：
Yuan, Ming