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

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

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.