Online Differentially Private Synthetic Data Generation
This work addresses privacy-preserving data analysis for streaming applications, extending prior offline methods to an online setting with minimal accuracy loss.
The paper tackles the problem of generating differentially private synthetic data from a continuous data stream, achieving near-optimal accuracy bounds of O(log(t)t^{-1/d}) for d≥2 and O(log^{4.5}(t)t^{-1}) for d=1 in 1-Wasserstein distance.
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\geq 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.