# Covariance's Loss is Privacy's Gain: Computationally Efficient, Private and Accurate Synthetic Data

arXiv: https://arxiv.org/abs/2107.05824 · HTML: https://mlsanity.com/paper/2107.05824/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2021.

## Built on by (most cited first, 7 of 7)

- [Synthetic Data -- what, why and how?](https://mlsanity.com/paper/2205.03257/) (2022)
- [Graphical vs. Deep Generative Models: Measuring the Impact of Differentially Private Mechanisms and Budgets on Utility](https://mlsanity.com/paper/2305.10994/) (2023)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Does Differentially Private Synthetic Data Lead to Synthetic Discoveries?](https://mlsanity.com/paper/2403.13612/) (2024)
- [Differentially Private Synthetic Data with Private Density Estimation](https://mlsanity.com/paper/2405.04554/) (2024)
- [Geometry-Adaptive Mechanisms for Private Synthetic Data](https://mlsanity.com/paper/2609.33363/) (2026)

## Abstract (arXiv)

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.