Covariance’s Loss is Privacy’s Gain: Computationally Efficient, Private and Accurate Synthetic Data
Covariance’s Loss is Privacy’s Gain: Computationally Efficient, Private and Accurate Synthetic Data
复制标题
DOI：
10.1007/s10208-022-09591-7
复制
发表时间：
2021-07
影响因子：
3
通讯作者：
M. Boedihardjo;T. Strohmer;R. Vershynin
中科院分区：
文献类型：
--
作者：
M. Boedihardjo;T. Strohmer;R. Vershynin
保护私人信息对于数据驱动的研究、商业和政府至关重要。隐私与实用之间的冲突引发了计算机科学和统计学界的深入研究，他们开发了多种保护隐私的数据发布方法。出现的主要概念包括匿名和差异隐私。如今，另一种解决方案正在获得关注，那就是合成数据。然而，通往隐私的道路上布满了 NP 难题。在本文中，我们重点关注 NP 难题，以开发一种计算效率高、具有可证明的隐私保证并严格量化数据效用的合成数据生成方法。我们通过研究一个基本但乍一看完全不相关的概率问题来解决这个问题的轻松版本，该问题涉及协方差损失的概念。也就是说，对于当我们采用条件期望时会丢失多少信息这一问题，我们找到了一个近乎最优且有建设性的答案。令人惊讶的是，这种对理论概率的探索产生了数学技术，使我们能够针对微聚合、隐私和合成数据等困难的应用问题得出建设性的、近似最优的解决方案。
The protection of private information is of vital importance in data-driven research, business and government. The conflict between privacy and utility has triggered intensive research in the computer science and statistics communities, who have developed a variety of methods for privacy-preserving data release. Among the main concepts that have emerged are anonymity and differential privacy. Today, another solution is gaining traction, synthetic data. However, the road to privacy is paved with NP-hard problems. In this paper, we focus on the NP-hard challenge to develop a synthetic data generation method that is computationally efficient, comes with provable privacy guarantees and rigorously quantifies data utility. We solve a relaxed version of this problem by studying a fundamental, but a first glance completely unrelated, problem in probability concerning the concept of covariance loss. Namely, we find a nearly optimal and constructive answer to the question how much information is lost when we take conditional expectation. Surprisingly, this excursion into theoretical probability produces mathematical techniques that allow us to derive constructive, approximately optimal solutions to difficult applied problems concerning microaggregation, privacy and synthetic data.