Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
复制标题
平均情况平均值：平滑灵敏度和均值估计的私有算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
T. Steinke
中科院分区：
文献类型：
--
作者：
Mark Bun;T. Steinke
保证差异隐私的最简单和最广泛应用的方法是向感兴趣的统计量中添加实例无关的噪声，该统计量按比例缩放到其全局灵敏度。然而，全局敏感性是一个最坏情况的概念，对于已实现的数据集实例来说往往过于保守。我们提供了以实例依赖的方式缩放噪声的方法，并证明它们在平均情况下的分布假设下提供了更高的精度。
The simplest and most widely applied method for guaranteeing differential privacy is to add instance-independent noise to a statistic of interest that is scaled to its global sensitivity. However, global sensitivity is a worst-case notion that is often too conservative for realized dataset instances. We provide methods for scaling noise in an instance-dependent way and demonstrate that they provide greater accuracy under average-case distributional assumptions.
Specifically, we consider the basic problem of privately estimating the mean of a real distribution from i.i.d.~samples. The standard empirical mean estimator can have arbitrarily-high global sensitivity. We propose the trimmed mean estimator, which interpolates between the mean and the median, as a way of attaining much lower sensitivity on average while losing very little in terms of statistical accuracy.
To privately estimate the trimmed mean, we revisit the smooth sensitivity framework of Nissim, Raskhodnikova, and Smith (STOC 2007), which provides a framework for using instance-dependent sensitivity. We propose three new additive noise distributions which provide concentrated differential privacy when scaled to smooth sensitivity. We provide theoretical and experimental evidence showing that our noise distributions compare favorably to others in the literature, in particular, when applied to the mean estimation problem.
登录
查看更多内容
DOI：
10.1145/3188745.3188946
发表时间：
2018-06
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Mark Bun;C. Dwork;G. Rothblum;T. Steinke
通讯作者：
Mark Bun;C. Dwork;G. Rothblum;T. Steinke
DOI：
10.1145/3319535.3339821
发表时间：
2019
期刊：
Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS
影响因子：
--
作者：
Couch, Simon;Kazan, Zeki;Shi, Kaiyan;Bray, Andrew;Groce, Adam
通讯作者：
Groce, Adam
DOI：
--
发表时间：
2018-05
期刊：
--
影响因子：
--
作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
通讯作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
利用节点差分隐私有效估计鄂尔多斯-仁义图
DOI：
--
发表时间：
2019
期刊：
Advances in Neural and Information Processing Systems
影响因子：
--
作者：
Sealfon, Adam;Ullman, Jonathan
通讯作者：
Ullman, Jonathan
DOI：
--
发表时间：
2020
期刊：
Advances in Neural Information Processing Systems
影响因子：
--
作者：
Canonne, Clement;Kamath, Guatam;McMillan, Audra;Ullman, Jonathan;Zakynthinou, Lydia
通讯作者：
Zakynthinou, Lydia