Zero-Cost Denoising for Optimizing Differentially Private Synthetic Data Generation

Private Evolution (PE) is a leading API-only framework for differentially private (DP) synthetic text. Each PE iteration spends privacy budget on a noisy nearest-neighbor vote histogram used to select synthetic candidates. We show that this histogram is under-utilized and can be denoised without additional privacy loss under the public-$N$ PE framework: the denoiser is DP post-processing of the noisy histogram, the synthetic candidate graph, and the public vote sum constraints. Our estimator, GRE, solves one convex program that combines the sum-to-$N$ simplex constraint with Laplacian smoothness on the candidate kNN graph. The two terms are complementary: the simplex constraint preserves the known total but ignores geometry, while the graph penalty uses geometry but does not enforce the histogram constraints. Empirically, histogram error minimization, one-shot ranking accuracy maximization, and closed-loop PE generation quality are not strictly connected. We therefore tune by a degrees-of-freedom rule calibrated to closed-loop synthetic data generation behavior. Our experiments on domain-mismatched text corpora including AG News and DBpedia, graph-regularized histogram-constrained denoising improve top-$N$ PE quality at tight privacy budgets.