Online Differentially Private Synthetic Data Generation
Yiyun He Roman Vershynin Yizhe Zhu
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(t^{-1/d}\log(t))$ for $d\geq 2$
and $O(t^{-1}\log^{4.5}(t))$ for $d=1$ in the 1-Wasserstein distance. This
result generalizes the previous work on the continual release model for
counting queries to include 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.