Private Evolution Converges
Journal:
arXiv
Published Date:
Jun 10, 2025
Abstract
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 explain PE's practical behavior and identify
sufficient conditions for its convergence. For $d$-dimensional sensitive
datasets with $n$ data points from a bounded domain, we prove that PE produces
an $(\epsilon, \delta)$-DP synthetic dataset with expected 1-Wasserstein
distance of order $\tilde{O}(d(n\epsilon)^{-1/d})$ from the original,
establishing worst-case convergence of the algorithm as $n \to \infty$. 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 simulations.
