# Online Differentially Private Synthetic Data Generation

arXiv: https://arxiv.org/abs/2402.08012 · HTML: https://mlsanity.com/paper/2402.08012/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 66 references that are in the map.
- First posted on arXiv 12 Feb 2024.

## Builds on (most cited first, 28 of 28)

- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [A Dynamical System Perspective for Lipschitz Neural Networks](https://mlsanity.com/paper/2110.12690/) (2021)
- [Private Synthetic Data for Multitask Learning and Marginal Queries](https://mlsanity.com/paper/2209.07400/) (2022)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations](https://mlsanity.com/paper/1308.1385/) (2013)
- [Differentially Private Neural Tangent Kernels for Privacy-Preserving Data Generation](https://mlsanity.com/paper/2303.01687/) (2023)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown](https://mlsanity.com/paper/2103.16787/) (2021)
- [Algorithmically Effective Differentially Private Synthetic Data](https://mlsanity.com/paper/2302.05552/) (2023)
- [Differentially Private Continual Releases of Streaming Frequency Moment Estimations](https://mlsanity.com/paper/2301.05605/) (2023)
- [Differential Privacy for Growing Databases](https://mlsanity.com/paper/1803.06416/) (2018)
- [Private sampling: a noiseless approach for generating differentially private synthetic data](https://mlsanity.com/paper/2109.14839/) (2021)
- [Privacy-preserving data release leveraging optimal transport and particle gradient descent](https://mlsanity.com/paper/2401.17823/) (2024)
- [Covariance's Loss is Privacy's Gain: Computationally Efficient, Private and Accurate Synthetic Data](https://mlsanity.com/paper/2107.05824/) (2021)
- [Certified private data release for sparse Lipschitz functions](https://mlsanity.com/paper/2302.09680/) (2023)
- [Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections](https://mlsanity.com/paper/2306.07884/) (2023)
- [Optimal Bounds on Private Graph Approximation](https://mlsanity.com/paper/2309.17330/) (2023)
- [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022)
- [Differentially Private Continual Release of Graph Statistics](https://mlsanity.com/paper/1809.02575/) (2018)
- [Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets](https://mlsanity.com/paper/2305.17148/) (2023)
- [An Algorithm for Streaming Differentially Private Data](https://mlsanity.com/paper/2401.14577/) (2024)

## Built on by (most cited first, 4 of 4)

- [InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy](https://mlsanity.com/paper/2507.02974/) (2025)
- [Private Evolution Converges](https://mlsanity.com/paper/2506.08312/) (2025)
- [Private Continuous-Time Synthetic Trajectory Generation via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2506.12203/) (2025)
- [Minimax optimal differentially private synthetic data for smooth queries](https://mlsanity.com/paper/2602.01607/) (2026)

## Abstract (arXiv)

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≥ 2 and O(log4.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.