Collaborative Research: SaTC: CORE: Small: Differentially Private Data Synthesis: Practical Algorithms and Statistical Foundations

组织和机构收集的数据是当今信息时代的关键资源，也是当今经济的重要组成部分。然而，这些数据的披露对个人隐私构成了严重威胁。在保护隐私的同时使用数据的一个重要方法是差分私有数据合成（DPDS）。也就是说，给定一个私有数据集作为输入，使用差分私有算法生成与输入数据集“相似”的合成数据集。虽然dpd近年来已获得了高度的关注,关于这一主题的理解仍然有限。该项目采用多学科的方法来提高我们对DPDS的科学认识，并改进实践技术。更具体地说，这个项目的新奇之处如下。首先，它系统地探索了基于边缘的DPDS算法的设计空间，这些算法已被证明在NIST的DPDS竞赛中是有效的，同时也从类似领域开发的数据合成技术中获得了见解（通常不满足DP）。其次，发展了由DPDS算法的经验性能驱动的统计理论，并指导了这些算法的实证研究。该项目更广泛的意义和重要性如下。我们处在信息经济时代。各种各样的数据，如在线交互、医疗传感器数据、基因组数据和位置数据正在被收集。在保护个人隐私的同时能够使用这些数据的实用技术是至关重要的，并且将大大提高这些数据的价值。用户将从加强对其私人信息的控制中获益，整个社会将从汇总数据中获得最大利益。pi计划根据该领域的现有研究以及本项目的研究成果，共同开发和教授研究生水平的综合数据课程，并让本科生参与研究。这个项目有两个重点。第一个重点是开发新的基于边际的DPDS算法，以改进经验评估的最新水平。任务包括：对“边际到数据集”问题（如何在给定一组边际时合成数据集）进行深入研究；开发和评估处理数字属性的新方法；并开发自适应和自动选择边缘的技术，以便与它们合成的数据集从输入数据集中捕获尽可能多的有用信息。第二部分是对第一部分实证研究的补充，旨在为高维边缘数据合成算法发展统计理论，并为评估合成数据在下游任务中的效用提供一个通用的学习理论框架。这两个重点是高度互补和相互支持的。推力1的实验研究将为推力2的理论研究提供见解和方向，有助于解释实验结果，并指导后续的实验研究。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Data collected by organizations and agencies are a key resource in today’s information age and fuel a significant part of today's economy. However, the disclosure of those data poses serious threats to individual privacy. One important approach to using data while protecting privacy is differential private data synthesis (DPDS). That is, given as input a private dataset, one uses a differentially private algorithm to generate synthetic datasets that are “similar” to the input dataset. While DPDS has received much attention in recent years, our understanding on this topic remains limited. This project takes a multi-disciplinary approach to advance our scientific understanding as well as improve practice techniques for DPDS. More specifically, this project’s novelties are as follows. First, it systematically explores the design space in marginal-based DPDS algorithms that have been proven to be effective in NIST competitions on DPDS, while also taking insights from data synthesis techniques developed in similar fields (often not satisfying DP). Second, it develops statistical theories that both are motivated by the empirical performances of DPDS algorithms, and guide the empirical research of these algorithms. The project’s broader significance and importance are as follows. We are in the information economy. Data of all kinds, such as online interaction, medical sensor data, genomic data, and location data are being collected. Practical techniques that enable use of these data while protecting individual privacy are crucially needed and will greatly enhance the value of such data. Users will gain from increased control of their private information, and society as a whole will benefit from deriving maximal benefit from aggregated data. PIs plan to jointly develop and teach a graduate-level course on synthetic data based on the existing research in this area as well as research results from this project, and involve undergraduate students in research. This project has two thrusts. The first thrust aims to develop new marginal-based DPDS algorithms that improve upon the state-of-art in empirical evaluations. The tasks include: perform an in-depth study of the “marginal-to-dataset” problem (how to synthesize a dataset when given a set of marginals); develop and evaluate new approaches for handling numerical attributes; and develop adaptive and automated techniques for selecting marginals so that dataset synthesized with them captures as much useful information from the input dataset as possible. The second thrust complements the empirical research in the first thrust, and aims to develop statistical theory for high dimensional marginal-based data synthesis algorithms, and also a general learning theory framework to evaluate the utility of synthetic data in downstream tasks. The two thrusts are highly complementary and support each other. The experimental study in Thrust 1 will provide insights and directions for theoretical studies in Thrust 2, which will help explain the experimental findings as well as guide additional experimental studies.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.