Research map / Federated learning and privacy / Differential privacy

Private Evolution Converges

NeurIPS 2025 · Federated learning and privacy › Differential privacy · approach: Differentially private synthetic data

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a new theoretically tractable variant of Private Evolution (PE) with a worst-case W1 convergence guarantee under DP, and links PE to the Private Signed Measure Mechanism, validated on simulations and CIFAR-10.

Problem

Existing convergence theory for Private Evolution (PE) relies on unrealistic assumptions (every sensitive point repeated many times) and a variant that differs from practical PE, so it does not explain PE's behavior for DP synthetic data.

Approach

Replace PE's thresholding with a bounded-Lipschitz projection of the Gaussian-noised nearest-neighbor histogram onto the simplex, sample the next synthetic set randomly, and use Gaussian variation APIs at multiple scales; this yields worst-case W1 convergence of order d(n eps)^{-1/d} without multiplicity assumptions, and shows PE is a sequential version of PSMM.

Key results

• Proves that under DP the expected W1 error of the modified PE is O~(d D (sqrt(log(1/delta))/(n eps))^{1/d}), giving worst-case convergence as n grows.
• Lower bound: without multiplicity assumption, eta-closeness requires eps = Omega(d log(1/eta)), showing the prior proof technique is limited.
• On CIFAR-10 (Dog and Plane) with eps=5, delta=1e-4, FID decreases as n grows over 100 to 600 when hyperparameters follow the theory; T=log(n eps) is better than T=20 used in prior work.

Measured effects reported in the paper

Surprising findings

• The prior convergence proof only works for privacy parameters eps = Omega(sqrt(d log(1/eta) log(1/delta))) when the multiplicity assumption is dropped, i.e., impractical regimes.
• Under the theory-optimal settings, PE can perform worse than doing no evolution steps when the initial synthetic data is already close to the sensitive data (optimal T may be 0).

Limitations

• Convergence rate suffers from the curse of dimensionality and is vacuous for d gtrsim log(n).
• The variation API used in theory (multi-scale Gaussian noise) differs from variations used in practical PE.
• Experiments are small-scale (2D simulations and two CIFAR-10 classes).

Experimental setup

Datasets: CIFAR-10 (Dog and Plane subclasses) ImageNet (for pretrained generator)

Benchmarks: CIFAR-10 (Dog and Plane) simulated 2D unit ball data

Metrics: W1 distance FID

Baselines: Private Evolution (practical, Lin et al.) Lin et al. theoretical PE analysis

Builds on: Private Evolution Private Signed Measure Mechanism analytic Gaussian mechanism Improved Diffusion

Closest papers by meaning

• PCEvolve: Private Contrastive Evolution for Synthetic Dataset Generation via Few-Shot Private Data and Generative APIs (ICML 2025 · similarity 0.92)
• Differentially Private Synthetic Data via Foundation Model APIs 1: Images (ICLR 2024 · similarity 0.91)
• Differentially Private Synthetic Data via Foundation Model APIs 2: Text (ICML 2024 · similarity 0.89)
• Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.88)
• PrE-Text: Training Language Models on Private Federated Data in the Age of LLMs (ICML 2024 · similarity 0.88)
• SynBench: A Benchmark for Differentially Private Text Generation (NeurIPS 2026 · similarity 0.88)