# Private Synthetic Data Generation in Bounded Memory

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2024.

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

- [Minimax optimal differentially private synthetic data for smooth queries](https://mlsanity.com/paper/2602.01607/) (2026)

## Abstract (arXiv)

We propose mathttPrivHP, a lightweight synthetic data generator with textitdifferential privacy guarantees. mathttPrivHP uses a novel hierarchical decomposition that approximates the input's cumulative distribution function (CDF) in bounded memory. It balances hierarchy depth, noise addition, and pruning of low-frequency subdomains while preserving frequent ones. Private sketches estimate subdomain frequencies efficiently without full data access. A key feature is the pruning parameter k, which controls the trade-off between space and utility. We define the skew measure mathtttailk, capturing all but the top k subdomain frequencies. Given a dataset X, mathttPrivHP uses M=O(klog2 |X|) space and, for input domain Omega = [0,1], ensures varepsilon-differential privacy. It yields a generator with expected Wasserstein distance: [ Oleft(fraclog2 Mvarepsilon n + frac||mathtttailk(X)||1M nright) ] from the empirical distribution. This parameterized trade-off offers a level of flexibility unavailable in prior work. We also provide interpretable utility bounds that account for hierarchy depth, privacy noise, pruning, and frequency estimation errors.