Private measures, random walks, and synthetic data-猫眼课题宝

DOI：

10.48550/arxiv.2204.09167

发表时间：

2022-04

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

M. Boedihardjo;T. Strohmer;R. Vershynin

差分隐私是一种数学概念，它提供了一种信息论安全保障。虽然差分隐私已成为数据共享中保障隐私的事实上的标准，但已知的实现它的机制存在一些严重的局限性。效用保障通常仅针对一组固定的、先验指定的查询提供。此外，对于更复杂但非常常见的机器学习任务，如聚类或分类，没有效用保障。在本文中，我们克服了其中一些局限性。利用度量隐私（差分隐私的一种强大推广），我们开发了一种多项式时间算法，该算法从数据集中创建一种隐私度量。这种隐私度量使我们能够有效地构建对多种统计分析工具都准确的隐私合成数据。此外，我们针对一般紧度量空间中的隐私度量和合成数据证明了一个渐近尖锐的极小极大结果。我们构建过程中的一个关键要素是一种新的超正则随机游走，其步长的联合分布与独立随机变量的联合分布一样正则，但从原点偏离得对数级缓慢。

Differential privacy is a mathematical concept that provides an information-theoretic security guarantee. While differential privacy has emerged as a de facto standard for guaranteeing privacy in data sharing, the known mechanisms to achieve it come with some serious limitations. Utility guarantees are usually provided only for a fixed, a priori specified set of queries. Moreover, there are no utility guarantees for more complex - but very common - machine learning tasks such as clustering or classification. In this paper we overcome some of these limitations. Working with metric privacy, a powerful generalization of differential privacy, we develop a polynomial-time algorithm that creates a private measure from a data set. This private measure allows us to efficiently construct private synthetic data that are accurate for a wide range of statistical analysis tools. Moreover, we prove an asymptotically sharp min-max result for private measures and synthetic data for general compact metric spaces. A key ingredient in our construction is a new superregular random walk, whose joint distribution of steps is as regular as that of independent random variables, yet which deviates from the origin logarithmicaly slowly.

Private measures, random walks, and synthetic data

文献摘要

相似文献