Private Synthetic Data Generation in Small Memory

2024/12/12 by Holland, Rayne, Camtepe, Seyit, Thapa, Chandra +1 · 2 citations
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2412.09756

Abstract

We propose \mathttPrivHP, a lightweight synthetic data generator with differential 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 \mathtttail_k, capturing all but the top k subdomain frequencies. Given a dataset X, \mathttPrivHP uses M=O(klog² |X|) space and, for input domain Ω= [0,1], ensures ε-differential privacy. It yields a generator with expected Wasserstein distance: O((log² M)/(ε n) + \frac||\mathtttail_k(X)||₁M n) 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.

Cited by

• An Iconic Heavy Hitter Algorithm Made Private
• Scalable Differentially Private Sketches under Continual Observation

Related

• Winning the NIST Contest: A scalable and general approach to differentially private synthetic data
• Privacy-Preserving Synthetic Datasets Over Weakly Constrained Domains
• Partition-based differentially private synthetic data generation
• A One-Pass Private Sketch for Most Machine Learning Tasks
• Universal Exact Compression of Differentially Private Mechanisms