Private Evolution for IPM Optimization: Limits and Alternatives

Private Evolution (PE) is a framework for differentially private (DP) synthetic data generation. Given a sensitive dataset $S$ and a public dataset $S_0$, PE evolves by generating public variations of $S_t$ and privately selecting $S_{t+1}$ from them to reduce a target discrepancy to $S$. Prior work proves that PE converges to $S$ in $1$-Wasserstein ($W_1$) distance, but generating DP synthetic data with $W_1$ accuracy suffers from the curse of dimensionality, even outside the evolution framework. The $W_1$ distance is an integral probability metric (IPM), defined by the largest discrepancy over a class of queries. It is known that more structured query classes can produce DP synthetic data that converge faster than existing lower bounds on $W_1$ convergence. We ask whether PE can exploit this structure by optimizing IPMs other than $W_1$. Our first result is that even simple IPMs induced by linear or convex-quadratic queries can be difficult to optimize directly via evolution. Even without privacy, exponentially many variations may be needed to generate a candidate dataset with strictly smaller target IPM. For linear queries, we recover statistically- and computationally-efficient PE by replacing the target IPM with a surrogate distance that bounds it, and for which polynomial-size Gaussian variation pools decrease the surrogate in expectation. We then use a DP Frank–Wolfe subroutine within PE to efficiently optimize a distribution over the variations and construct $S_{t+1}$ to match the mean of it. The resulting PE achieves IPM error $\tilde{O}((d^2/(n\epsilon ){)}^{1/3})$ and avoids the curse of dimensionality. This works in part because a dataset with a prescribed mean is easy to construct; for richer queries, reconstruction can itself be hard: we prove that matching only two bounded convex quadratic queries with a fixed-size dataset is already NP-hard. Overall, our results disentangle statistical and computational aspects of the three pieces of PE: the IPM, the evolution, and privacy. Our lower bounds show how non-private evolution fails (computationally), even for simple IPMs, while our positive result shows that replacing the target IPM by a compatible surrogate can recover efficient PE in some special cases.