Differential Privacy (DP) has become a gold standard in privacy-preserving data analysis. While it provides one of the most rigorous notions of privacy, there are many settings where its applicability is limited. Our main contribution is in augmenting differential privacy with {\em Flexible Accuracy}, which allows small distortions in the input (e.g., dropping outliers) before measuring accuracy of the output, allowing one to extend DP mechanisms to high-sensitivity functions. We present mechanisms that can help in achieving this notion for functions that had no meaningful differentially private mechanisms previously. In particular, we illustrate an application to differentially private histograms, which in turn yields mechanisms for revealing the support of a dataset or the extremal values in the data. Analyses of our constructions exploit new versatile composition theorems that facilitate modular design. All the above extensions use our new definitional framework, which is in terms of "lossy Wasserstein distance" -- a 2-parameter error measure for distributions. This may be of independent interest.
翻译:差异隐私(DP) 已经成为隐私保护数据分析中最严格的隐私概念之一。 虽然它提供了最严格的隐私概念之一, 但有许多限制其适用性的环境。 我们的主要贡献是增加了与 prelive Accureacy} 之间的差异隐私, 这使得在测量输出的准确性之前对输入进行小的扭曲( 比如, 弃离器), 使得一个人能够将 DP 机制扩大到高敏感度功能。 我们提出了一些机制, 帮助实现这个概念, 而这些功能以前没有有意义的私人机制。 特别是, 我们演示了对有区别的私有直方图的应用, 而这又产生了显示数据集或数据中极端值支持的机制 。 分析我们的构造利用了新的多功能构成来便利模块设计。 上述所有扩展都使用了我们的新定义框架, 其用词是“ 损失的瓦塞斯坦距离”, 这是用于分配的2 参数错误测量。 这也许具有独立的兴趣 。