Private Evolution Converges
Not on the map. Why?
Abstract (arXiv)
Private Evolution (PE) is a promising training-free method for differentially private (DP) synthetic data generation. While it achieves strong performance in some domains (e.g., images and text), its behavior in others (e.g., tabular data) is less consistent. To date, the only theoretical analysis of the convergence of PE depends on unrealistic assumptions about both the algorithm's behavior and the structure of the sensitive dataset. In this work, we develop a new theoretical framework to understand PE's practical behavior and identify sufficient conditions for its convergence. For d-dimensional sensitive datasets with n data points from a convex and compact domain, we prove that under the right hyperparameter settings and given access to the Gaussian variation API proposed in citePE23, PE produces an (varepsilon, δ)-DP synthetic dataset with expected 1-Wasserstein distance tildeO(d(nvarepsilon)-1/d) from the original; this establishes worst-case convergence of the algorithm as n → ∞. Our analysis extends to general Banach spaces as well. We also connect PE to the Private Signed Measure Mechanism, a method for DP synthetic data generation that has thus far not seen much practical adoption. We demonstrate the practical relevance of our theoretical findings in experiments.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 32 of its 52 references that are in the map. First posted on arXiv 10 Jun 2025.
Builds on
32 of 52 references.
References · 32
- 2015Rethinking the Inception Architecture for Computer Visioncited by 5,475
- 2021Improved Denoising Diffusion Probabilistic Modelscited by 3,761
- 2016Deep Learning with Differential Privacycited by 2,728
- 2018Differentially Private Generative Adversarial Networkcited by 235
- 2018Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoisingcited by 218
- 2022Differentially Private Diffusion Modelscited by 119
- 2024Differentially Private Synthetic Data via Foundation Model APIs 2: Textcited by 76
- 2023Differentially Private Synthetic Data via Foundation Model APIs 1: Imagescited by 65
- 2021Don't Generate Me: Training Differentially Private Generative Models with Sinkhorn Divergencecited by 54
- 2019G-PATE: Scalable Differentially Private Data Generator via Private Aggregation of Teacher Discriminatorscited by 53
- 2021Differentially Private Query Release Through Adaptive Projectioncited by 52
- 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
20 more
- 2018Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spacescited by 41
- 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
- 2024PrE-Text: Training Language Models on Private Federated Data in the Age of LLMscited by 29
- 2021Differentially Private Sliced Wasserstein Distancecited by 19
- 2023Generating Private Synthetic Data with Genetic Algorithmscited by 18
- 2013Efficient Algorithms for Privately Releasing Marginals via Convex Relaxationscited by 17
- 2013Adaptive Metric Dimensionality Reductioncited by 14
- 2025Benchmarking Differentially Private Tabular Data Synthesiscited by 14
- 2025POPri: Private Federated Learning using Preference-Optimized Synthetic Datacited by 14
- 2025Differentially Private Synthetic Data via APIs 3: Using Simulators Instead of Foundation Modelcited by 13
- 2023Algorithmically Effective Differentially Private Synthetic Datacited by 11
- 2025Contrastive Private Data Synthesis via Weighted Multi-PLM Fusioncited by 11
- 2025DPImageBench: A Unified Benchmark for Differentially Private Image Synthesiscited by 11
- 2021Differentially Private Normalizing Flows for Privacy-Preserving Density Estimationcited by 10
- 2023Certified private data release for sparse Lipschitz functionscited by 7
- 2025Is API Access to LLMs Useful for Generating Private Synthetic Tabular Data?cited by 5
- 2023Differentially Private Gradient Flow based on the Sliced Wasserstein Distancecited by 4
- 2024Online Differentially Private Synthetic Data Generationcited by 4
- 2024Metric geometry of the privacy-utility tradeoffcited by 3
- 2023Training generative models from privatized datacited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.