Online Differentially Private Synthetic Data Generation

Abstract

We present a polynomial-time algorithm for online differentially private synthetic data generation. For a data stream within the hypercube $[0,1{]}^d$ and an infinite time horizon, we develop an online algorithm that generates a differentially private synthetic dataset at each time $t$. This algorithm achieves a near-optimal accuracy bound of $O(\log (t)t^{-1/d})$ for $d\ge 2$ and $O({\log }^{4.5}(t)t^{-1})$ for $d=1$ in the 1-Wasserstein distance. This result extends the previous work on the continual release model for counting queries to Lipschitz queries. Compared to the offline case, where the entire dataset is available at once, our approach requires only an extra polylog factor in the accuracy bound.

21 pages

References in corpus (5)

• Lipschitz clustering in metric spaces
• Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections
• Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown
• Differentially Private Neural Tangent Kernels for Privacy-Preserving Data Generation
• Differential Privacy on Dynamic Data

Cited by in corpus (1)

• Cyclic Adaptive Private Synthesis for Sharing Real-World Data in Education