Private Synthetic Data Generation in Bounded Memory

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.