Private Evolution Converges

Conference: NeurIPS 2025 arXiv: 2506.08312 Code: Unavailable Area: Other Keywords: Differential Privacy, Synthetic Data, Private Evolution, Wasserstein Distance, Convergence Analysis

TL;DR

This paper provides the first convergence guarantee for the Private Evolution (PE) synthetic data generation algorithm that does not rely on unrealistic assumptions, proving that under appropriate hyperparameter settings, the \((ε,δ)\)-DP synthetic dataset output by PE achieves a 1-Wasserstein distance of \(\tilde{O}(d(nε)^{-1/d})\).

Background & Motivation

Differentially private (DP) synthetic data generation is a critical tool for enabling data sharing while preserving privacy. Private Evolution (PE) is a promising training-free DP synthetic data method that iteratively refines synthetic data using pretrained public generative models.

PE achieves competitive performance with state-of-the-art methods in image and text domains without requiring modifications to the training pipeline, as DP-SGD does. However:

Performance is unstable in certain domains: e.g., tabular data and image data with distribution mismatch.

Existing theory is severely insufficient: The convergence analysis in PE23 relies on two unrealistic assumptions: - Algorithm discrepancy: The theoretically analyzed version of PE (Algorithm 1) differs fundamentally from the practically used PE (Algorithm 3) in a key step (deterministic construction vs. probabilistic sampling). - Data repetition assumption: Each point in the sensitive dataset is assumed to be repeated \(B\) times so that Gaussian noise does not overwhelm the signal. This is highly unrealistic and sidesteps the core challenge of DP learning.

The authors first establish a lower bound (Lemma 3.1): after removing the data repetition assumption, the proof technique of PE23 is valid only when \(\varepsilon = \Omega(d\log(1/\eta))\)—which is impractical even in moderate dimensions. This demonstrates the need for an entirely new analysis approach.

Method

Overall Architecture

The high-level pipeline of PE: 1. Generate initial synthetic data \(S_0\) using Random_API (e.g., a pretrained foundation model). 2. Iteratively refine: \(S_0 \to S_1 \to \cdots \to S_T\) - Generate mutation candidates \(V_t\) from the current synthetic data. - Compute a nearest-neighbor histogram (which candidates are closest to the sensitive data). - Add Gaussian noise to ensure DP. - Sample from the noisy histogram to produce the next round of synthetic data.

Key Designs

1. New theoretically tractable variant (Algorithm 2): Unlike the theoretical version in PE23, Algorithm 2 more closely resembles the practical PE:

   • Sampling construction (non-deterministic): Uses probabilistic sampling to generate the next synthetic dataset \(S_t\) rather than deterministically replicating points proportionally.
   • \(B_L\) distance projection (non-threshold truncation): Projects the noisy histogram onto the probability simplex using bounded Lipschitz distance minimization.
   • Flexible synthetic dataset size: \(n_s\) is an input parameter and need not equal \(n\).

The only difference from practical PE lies in the post-processing step (projection vs. threshold + normalization), which is nevertheless critical for worst-case guarantees.

1. Three-term decomposition for the convergence proof: At each iteration \(t\), \(W_1(\mu_S, \mu_{S_{t+1}})\) is decomposed as:

   \(W_1(\mu_S, \mu_{S_{t+1}}) \leq \underbrace{W_1(\mu_S, \hat{\mu}_{t+1})}_{\text{progress from mutation}} + \underbrace{2D_{BL}(\hat{\mu}_{t+1}, \tilde{\mu}_{t+1})}_{\text{effect of DP noise}} + \underbrace{W_1(\mu'_{t+1}, \mu_{S_{t+1}})}_{\text{sampling error}}\)

   • Mutation progress: By generating mutations and selecting the nearest ones, the Wasserstein distance contracts by a factor of \((1-\gamma)\), where \(\gamma = \Theta(1/d)\).
   • DP noise effect: The supremum of the Gaussian process is bounded via empirical process theory (Dudley chaining).
   • Sampling error: Controlled using Wasserstein convergence results for empirical measures.

2. Connection to the Private Signed Measure Mechanism (PSMM): The key insight is that the nearest-neighbor histogram itself solves a 1-Wasserstein minimization problem (Prop. 5.1). PSMM can be viewed as a "one-step version" of PE, while PE is a "practical iterative version" of PSMM—when the data domain is too large to be covered in a single step, PE progressively refines coverage through iteration.

Main Theorem (Theorem 4.1)

Let \(\Omega \subset \mathbb{R}^d\) be a convex compact set with diameter \(\leq D\). For any \(\varepsilon, \delta \in (0,1)\), set: - Number of iterations \(T = O(\log(n\varepsilon))\) - Number of synthetic samples \(n_s = O(n\varepsilon/\sqrt{T})\) - Noise scale \(\sigma = O(\sqrt{T\log(1/\delta)}/(n\varepsilon))\)

Then Algorithm 2 is \((ε,δ)\)-DP, and its output satisfies:

\[\mathbb{E}[W_1(\mu_S, \mu_{S_T})] \leq \tilde{O}\left(dD\left(\frac{\sqrt{\log(1/\delta)}}{n\varepsilon}\right)^{1/d}\right)\]

Beyond Worst-Case Analysis

For practical variants using Laplace noise with threshold truncation (which more closely resemble practical PE), data-dependent bounds are provided (Prop. 4.1). When the data is highly clustered (i.e., the non-private histogram has few positive entries), the bound can be significantly tighter than the worst-case guarantee.

Key Experimental Results

Main Results: 2D Simulation (\(\varepsilon=1, \delta=10^{-4}\))

Parameter	Theoretical Prediction	Experimental Verification
Optimal iterations \(T\)	\(2\log(n\varepsilon)\)	Peak performance aligns with prediction
Optimal synthetic samples \(n_s\)	Value given by Theorem 4.1	Deviating in either direction degrades performance
Effect of initialization	Optimal \(T=0\) when \(\Gamma_0 \leq err\)	Three initialization scenarios validate theoretical predictions

CIFAR-10 Experiments

Setting	Key Metric	Notes
Theoretical hyperparameters (\(\varepsilon=5, \delta=10^{-4}\))	FID decreases as \(n\) grows	Validates the core claim that PE converges with sufficient samples
Varying steps \(T\)	\(T=\log(n\varepsilon)\) is optimal	\(T=20\) used in PE23 is suboptimal
\(n=100\to600\)	FID consistently improves	Convergence empirically verified on real data

Effect of Dimensionality and Privacy Parameters

Variable	Theoretical Prediction	Experimental Result
Increasing \(d\)	Accuracy degrades (curse of dimensionality)	\(d=1\to10\): final \(W_1\) distance increases monotonically
Increasing \(\varepsilon\)	Accuracy improves	\(\varepsilon=0.1\to1.0\): final \(W_1\) distance decreases monotonically

Key Findings

• PE convergence is strongly initialization-dependent: When \(\Gamma_0 \leq err\), the optimal number of steps is \(T=0\) (no iteration needed); poor initialization requires more iterations. This explains the contradictory observations in prior practice (PE23 found PE consistently improves vs. Swanberg et al. found PE deteriorates over time).
• Theoretically guided hyperparameter selection is effective: \(T = O(\log(n\varepsilon))\) and the theoretically derived \(n_s\) outperform the manually chosen \(T=20\) from PE23 on CIFAR-10.
• Convergence rate suffers from the curse of dimensionality: The bound becomes vacuous when \(d \gtrsim \log(n)\), consistent with the inherent limitations of using \(W_1\).

Highlights & Insights

• Bridging theory and practice: The paper not only provides theoretical guarantees for practical PE but also shows how PE naturally emerges from a "practicalization" of PSMM.
• The lower bound in Lemma 3.1 demonstrates why the proof technique of PE23 is fundamentally limited—a limitation not fixable by simple technical improvements.
• Data-dependent bounds (Prop. 4.1) provide a theoretical framework for understanding when PE succeeds (clustered data) and when it fails (dispersed data).
• Actionable hyperparameter guidance: \(T = O(\log(n\varepsilon))\) and \(n_s = O(n\varepsilon/\sqrt{T})\) are practical and experimentally validated.

Limitations & Future Work

• Curse of dimensionality in convergence rate: \(\tilde{O}(d(n\varepsilon)^{-1/d})\) becomes vacuous when \(d \gtrsim \log(n)\), an inherent limitation of the \(W_1\) metric.
• Theoretical Variation_API differs from practice: The theory uses multi-scale Gaussian perturbations, while practice uses diffusion models and similar generative approaches.
• Computational cost of \(D_{BL}\) projection: Requires solving a linear program, which is more expensive than the simple threshold + normalization used in practical PE.
• Restricted to convex compact spaces: Applicability to data lying on high-dimensional manifolds (e.g., natural images) requires further investigation.
• Lack of systematic evaluation on high-dimensional real data: The CIFAR-10 experiments use only two subclasses at a limited scale.

Related Work & Insights

• Complementary to DP-SGD-based generative model training: PE is a training-free alternative.
• The connection to PSMM provides theoretical guidance for designing new DP synthetic data algorithms.
• Offers insights into understanding the convergence of other evolution-based or iterative refinement privacy algorithms (e.g., Private Query Release).

Rating

• Novelty: ⭐⭐⭐⭐ Rigorously falsifies the limitations of prior analysis and provides more realistic convergence guarantees.
• Experimental Thoroughness: ⭐⭐⭐ Simulation validation is thorough, but real-data experiments are limited in scale (only 2 classes of CIFAR-10).
• Writing Quality: ⭐⭐⭐⭐⭐ Theoretical derivations are rigorous and clear; comparisons and connections to prior work are well articulated.
• Value: ⭐⭐⭐⭐ Fills an important gap in the theoretical analysis of PE with direct practical implications.

Related Papers

• [AAAI 2026] Improved Differentially Private Algorithms for Rank Aggregation
• [ICLR 2026] Missing Mass for Differentially Private Domain Discovery
• [AAAI 2026] Private Frequency Estimation via Residue Number Systems
• [ICLR 2026] Learning Structure-Semantic Evolution Trajectories for Graph Domain Adaptation
• [CVPR 2026] What Is Wrong with Synthetic Data for Scene Text Recognition? A Strong Synthetic Engine with Diverse Simulations and Self-Evolution