AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data
AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data
复制标题
DOI：
10.14778/3551793.3551817
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Ryan McKenna;Brett Mullins;D. Sheldon;G. Miklau
中科院分区：
文献类型：
--
作者：
Ryan McKenna;Brett Mullins;D. Sheldon;G. Miklau
我们提出了AIM，一个新的算法差分私人合成数据生成。AIM是一种工作负载自适应算法，它首先选择一组查询，然后私下测量这些查询，最后从噪声测量中生成合成数据。它使用一组创新的功能来迭代地选择最有用的度量，反映它们与工作负载的相关性以及它们在近似输入数据方面的价值。我们还提供了解析表达式，以高概率约束每个查询的错误，可用于构建置信区间，并告知用户生成的数据的准确性。我们的经验表明，AIM始终优于各种现有的机制在各种实验设置。
We propose AIM, a new algorithm for differentially private synthetic data generation. AIM is a workload-adaptive algorithm within the paradigm of algorithms that first selects a set of queries, then privately measures those queries, and finally generates synthetic data from the noisy measurements. It uses a set of innovative features to iteratively select the most useful measurements, reflecting both their relevance to the workload and their value in approximating the input data. We also provide analytic expressions to bound per-query error with high probability which can be used to construct confidence intervals and inform users about the accuracy of generated data. We show empirically that AIM consistently outperforms a wide variety of existing mechanisms across a variety of experimental settings.