Private Evolution Converges
Authors: Tomás González
Giulia Fanti
Aaditya Ramdas
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Synthetic Data
Private Evolution
Primary area: theory
TL;DR: We prove that Private Evolution, a practical algorithm for differentially private synthetic data generation, converges in Wasserstein distance as the number of samples increases under a new, realistic theoretical model

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 understand PE’s practical behavior and identify sufficient conditions for its convergence. For $d$-dimensional sensitive datasets with $n$ data points from a convex and compact domain, we prove that under the right hyperparameter settings and given access to the Gaussian variation API proposed in \cite{PE23}, PE 
produces an $(\varepsilon, \delta)$-DP synthetic dataset with expected 1-Wasserstein distance $\tilde{O}(d(n\varepsilon)^{-1/d})$ from the original; this establishes 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 experiments.

Private Evolution Converges
Tomas Gonzalez Carnegie Mellon University tcgonzal Candrew. cmu. edu
Giulia Fanti
Aaditya Ramdas Carnegie Mellon University aramdas@cs. cmu. edu
Carnegie Mellon University gfanti Gandrew. cmu. cmu.edu
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 new theoretical framework understand PE's practical behavior and identify sufficient conditions for its convergence. For d-dimensional sensitive datasets with data points from a convex and compact domain, we prove that under the right hyperparameter settings and given access to the Gaussian variation API proposed in [33. PE produces an (e, 8)-DP synthetic dataset with expected I-Wasserstein distance ((d(ne)-1/d) from the original; this establishes worst-case convergence of the algorithm as n D0. 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 experiments.
1
Introduction
Many modern machine learning upplications rely user data, making data privacy protection central concern. In this regard, differential privacy (DP) 19 has become de facto standard for safeguarding sensitive information of individuals. Given private dataset, many problems-including
regression 40 12 deep learning ①1 and stochastic optimization 6 can performed in DP manner. While it is possible to design a different DP algorithm for each specific task, a reasonable alternative is to generate a DP synthetic dataset that preserves many the statistical properties of the sensitive dataset. By the post-processing property of DP [1). the DP synthetic data can then be fed into existing non-DP algorithms without incurring additional privacy loss; this avoids modifying existing ML pipelines and enables data sharing with third parties (e.g. for reproducibility)).
Recently, (33 introduced Private Evolution (PE), a promising new framework for DP synthetic data generation that relies on public, pretrained data generators 488 32 27 competitive with and sometimes improves on tooosstat--offtiee the-art models terms of Fréchet inception distance (FID) and downstream task performance in settings such as images and text 33 48 27 In addition, PE is training- free, whereas current state-of-the-an art approaches typically train (or finetune) generative model on the sensitive dataset using DP-SGD 44 35 14 I1]. However, in some settings, including tabular data [41), and image data with mismatched distributions
50 28). PE is currently
[21], PE has achieved limited success. To better understand when PE works, it is crucial to improve our theoretical understanding of the algorithm.
At high level, PE works as follows (Figure I]. First, it creates a synthetic data set So with an API that is independent of the sensitive dataset S (e.g foundation model trained on public data). Then, iteratively it refines the synthetic data, creating S2, where S, is obtained from S,-1 by
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

generating variations V of the dataset St-1 and then privately selecting the samples that are closest S. Doing so, the synthetic datasets gets 'closer' to S over time.
In (3 the authors study a theoretically tractable variant of PE, analyzing its conver- gence in terms of the Wasserstein distance, with the aim of understanding its behavior and justi- fying its empirical success, However, this theo- retically tractable version of PE differs in many significant ways from the algorithm that is used experiments; further, the convergence analy- sis in (33] makes the unrealistic assumption that every point in repeated many times. We start by showing that the proof technique in [3] inherently limited by this multiplicity assump- tion; if we remove the assumption, then PE can only be e-DP with a parameter that scales as d (1/)), where d is the ambient dimension of the data and 1 is the final accuracy of the algorithm terms of the Wasserstein distance. This is impractical in even moderate dimensions.
S So
S
Vi
s
Si
s V2 wr
S ST
Figure 1: High-level illustration of private evolu- tion (PE), S represents the sensitive data, shown in red. S, are the synthetic datasets, shown in blue, and are created with the variations from Ve (in green) that closest to S.
In this paper, we address the limitations in prior analysis of PE by providing a convergence analysis that does not require strong assumptions about the nature of the dataset and more closely matches the PE algorithm used in practice. We formally prove worst-case convergence guarantees in terms the 1- 1-Wasserstein distance. We provide an informal version of our Theorem 4.1 below.
conss-eeeeeonnveeeeeeee
Theorem 1.1 (Convergence of PE (Informal)). Consider a data domain c Rdd with &2 diameter D. For any dataset S E Q2 and 0 < E, 8 < 1, there exist APIs and parameter setting such that PE (Algorithm 2 is (e, 8DP and outputs a synthetic dataset satisfying
1/d
/lo((1/0)
EIWi S dD
NE
where μs is the empirical distribution of the dataset S and similar for S', and W1 is the 1- I-Wasserstein
distance between distributions iaciiionnsDDiiniiiiiii (Defimition 2.2
As corollary, we find sufficient conditions on the APIs used by PE to understand its convergence in more general settings, such as Banach spaces. We also identify strong connections between and the Private Signed Measure Mechanism (PSMM), an algorithm for DP synthetic data generation under pure DP (25 that has theoretical guarantees. Hence, our work bridges the theory and practice of PE in both directions: provide theory for practical version of PE, and show how PE naturally arises as a practical version of PSMM.
Contributions Our work significantly improves the theory of PE presented in (33], providing more realistic theoretically tractable version of PE and climinating unrealistic assumptions in the convergence analysis. More concretely, we make the following contributions.
We prove lower bound (Lemma 3.1 that establishes that without the multiplicity assump- tion on the data, the convergence proof of PE provided in [33 only works for undesirable privacy parameters under pure DP. This indicates that new analysis for PE is needed.
theoretically tractable variant of PE, Algorithm 2 Under this model, formally prove worst-case convergence rates with respect to the 1- Wasssrrsteein distance as SS oo; see Theorem 4.1 We identify sufficient conditions for convergence of PE in more general settings such as Banach spaces (Appendix G).
We propose
We draw connections between PE and the Private Signed Measure Mechanism (PSMM), an algorithm for DP synthetic data generation [25]. We exploit this connection by using tools from the analysis of PSMM to prove the convergence of PE. Finally, we also show how PE arises naturally when trying to make PSMM 'practical'. See Section 5 for details.
Note that convergence is proven in the worst-case over problem instances for specific set of hyperparameters and APIs.

---

Our theory offers an explanation for phenomena observed in prior practical applications of PE TE-such as its sensitivity initialization and offers guidance for future use, including principled parameter selection based on theoretical insights. See Section 6 for details.
2 Preliminaries
Definition 2.1 (Differential Privacy 17
randomized algorithm A is (e, 8) (ee,))ddffffrenn diiffereent private for any pair of datasets S and S' differing in at most one data point and any event & in the output space, P[A(S) E] e'P[A(S") E E +
Definition 2.2 (1- (1-Wasserstein distance [44)) Lei (S2, p) be metric space and jr, v two probubility
measures over it. The 1- --Wassesstein distance between pi, v is defined as
/
Wi(u,
inf TET(Ee2) Jaxa p(a, (),
where (u, is the set of distributions over Ω2 whose marginals μ and v, respectively.
Next, we formally introduce the problem of DP Synthetic Data studied this paper.
Definition 2.3 (DP Synthetic Data). Let denote by μs the empirical distribution of a dataset S, given by [8] EzEgde. 8z. Let (S,, p) be the data metric space. Then, given a dataset containing sensitive information, the problem of DP Synthetic Data generation consists of designing an (e, 6)DP algorithm A 52" - 22th that returns a DP synthetic dataset S' with the property that W1 (Ps, Pss) is small either in expectation or with high probability, with respect to the randomness in A.
In the past, there have been different theoretical formulations of the DP Synthetic Data problem (see Section[A) A). In most of them, a fixed set of queries Q is used to measure the accuracy of the synthetic data: the answer to a query q E Q should be similar when querying the sensitive dataset and the synthetic dataset S" In other words, m (5()) q(S') should be small. By Kantorovich duality [44,, we can alternatively define the 1- W-Wasserstein distance as
W1 (us, Us+
sup JEFAL
[Bz-ps ((Z)) - Ez Ez~ps [f(2)]I.
where = (f: R. I1 S diam (52) and ( f(2)) S p(21. 22 221, 22 E 52} the set of bounded and 1-Lipschitz functions from S to TR. Hence, in Definition 2.3 W, (us, (&rr) being small implies that the synthetic dataset approximately preserves the answers of to all Lipschitz queries, making the synthetic dataset S' useful for any downstream task with Lipschitz loss.
Notation. Samples lie in the metric space p). The diameter of S2 denoted by diam(() su p(21, 22). P(2)) is the space of probability measures supported on Ω. A dataset is a set of elements from Q. For a dataset S, |.S] represents its cardinality, S[i] its i-th element and the empirical distribution (s) Σxes 82, where ò² the dirac delta mass at 2. The bounded Lipschitz distance between the signed measures μr, supported in 12 DEL v), == suP fdu- fdv. For probability measures v. DEL (n, v) = W1 (H, v). Aa is the standard probability simplex in Rd. ofi] indicates the i-th coordinate of a vector o E Rd. nint(x) denotes the nearest integer to x.
3 Background: Private Evolution (PE) and Prior Theory
Lin et al. present the only prior convergence analysis of PE B3). Their analysis applies to a variant Below, we first describe T explain how it differs from how PE is used in practice (Algorithm which we call practical PE). Then, we explain the limitations of prior analysis.
of PE (that we call theoretical PE), which is outlined in Algorithm []
PE (both the practical variant, and the theoretical variant in Algorithm I generates DP synthetic dataset by iteratively refining an initial random dataset using a DP rearest-neightt histogram (Algorithm 4p. To do so, it requires access to two APIs that are independent of the sensitive dataset S. Random API and Variation [ariation_APP] For our theory, we use the same theoretical API models proposed in 33 which we detail below.
In practice, generative models trained public data and simulators be used APls.
3

---

Algorithm 1 (Theoretical) Private Evolution; steps in blue differ from practical PE (3
1: Input: sensitive dataset: S E Q²", number of iterations: T, noise multiplier: a, distance function:
p(ss), multiplicity parameter B 2 threshold H >
2: Output: DP synthetic dataset: Sr E "mmen
3: So < Random API(n)
4: for t = I...I'd
5: Vi f- Variation API(S
6:
er NN IN_histogram(S P), E Aiai (see Alg. 4)
7:
Dr ju, + +N ON (M4)
8:
ML +
(1) for every i [[V]]]
9: S. + Uielin St where S; is multiset containing Vid nint(ng((i/BBBB times
end for
11: return ST
Random (aaudom_AP((n)) returns n, data points from the same domain as S. In practice, might generate random samples from pretrained foundation model. In Algorithm D Random (asddo__AP((nn)) returns n, data points sampled according to any distribution P(S2"*).
For dataset St, Variation_APIIs API(S)) Variation __p[[APP((() returns a set of variations of data point 2. In practical PE, a
U3ES, Srtiation_AP((2
where
variation of is another point z' which is close to = in some logical sense. In the of images, z' could be an image with a similar embedding to that of z. However, in Algorithm PiriationAA(({ returns of variations of calculated
{z} U (Ie (lng.... (atddaammmm()))))aaaaaaa) {proja(= ++*k)))))
(I)
where >> 0 is small constant and N rdd (O, la) with 01 (2
Note that noise is added at different scales. This key for the theory to work, because it allows to "explore" the data domain more effectively. Recall that for a dataset S,, Variation_APP(S) O[SS, log(diam(()) /ai) variations by adding independent, spherical Gaussian noises with increasing variances to each sample z.
Uzes, Variation (PTiiin That is, the API generates
In Algorithm the initial synthetic dataset So is created with Mandom_API The algorithm then iteratively creates synthetic datasets S1, S2. as follows. At each iteration, variations V, are created from the current synthetic dataset with Variation_APPl and nearest neighbor histogram indicating how many elements from S have a certain variation from V as nearest neighbor. This histogram is privatized by adding Gaussian noise. After thresholding small entries, new synthetic dataset St constructed deterministically by including variations with multiplicity proportional to the noisy histogram (Line()) 99. This process repeats for T steps, gradually aligning the synthetic data with the private dataset S.
Practical PE and Algorithm differ in significant ways, which are highlighted in blue in Algorithm 1 Most notably, Algorithm| creates the next synthetic dataset S, deterministically by adding variations to the next dataset proportionally to the entries of the DP histogram. In practical PE, the next synthetic dataset instead constructed by sampling with replacement from a distribution defined by the histogram. This seemingly small difference is important for their proof technique, discussed next. More differences between the two variants of PE are discussed in Appendix
The theoretical analysis in 33 relies on first showing that noiseless PE (Algorithm I with o = 0) converges, then arguing that when each data point from the sensitive dataset S' is repeated B times, with high probability the noisy version behaves like noiseless PE for large B.
Limitations of the utility analysis of Algorithm 1 in 333
In the noiseless case the elements of S and So are matched: assign Su[i] to Sli). Then iteratively. for each [+]i] is chosen as the element from Variation_API(SS_-
that closest to Sli), which is likely to be closer to 5[i] than S,-1 [i]. After enough steps, p(S [1. (i) < v for all i E [n]: we say the datasets are yl-cloee, written as =,, ST. To handle noise, [3] assumes every real data point
repeated B times. This boosts the signal in the noisy step (Line
allowing the algorithm to behave

---

like the noiseless version. In other words, although the proof assume each data point is repeated B times, the noise scale provides DP guarantce for neighboring datasets that differ in single sample. This setup is unrealistic and sidesteps the core challenge of differentially private learning. More details in Appendix C
We provide formal lower bound giving evidence that the proof technique in 33 is fundamentally limited, in the sense that their unrealistic assumption necessary for their proof technique work. More concretely, in Lemma 3.Iwe we show that if we remove the multiplicity assumption, then any e-DP algorithm can only output DP synthetic dataset S that is n-close when 12(dlog(1/m)) or
equivalently, 17 52(e </d). Proof in Appendix H
Lemma 3.1 (Lower bound for n-closeness). Consider metric (data) space (Ω. p) and fixed dataset $ E Ω" Let 1j > 0 and A Ω - -2 be such that IP A = A(S)] 2 T for some E (0, 1/4). Suppose A is (s, 6D- for some 5 E (0, 3r). Then, denoting M p; 2n) the 2n packing number of w.n. p. we must have
2 log(M p11)))
Remark 3.1. The packing number M(Ω. p; 2n) is the order (1/n)² when Q c. Rd and diam v 2 (see Lemma 5.5 and Example 5.8 in (45)).
4 Convergence of Private Evolution
We have established several limitations of prior utility analysis of PE: the algorithmic variant PE analyzed in [33] differs from what is done in practice, and the analysis itself is unlikely extend beyond very weak privacy regimes, as evidenced by Lemma 3.T In this section, we introduce a new theoretically tractable version of PE along with its utility convergence guarantees. The algorithm analyze more closely reflects how PE works in practice and amenable to worst-case utility analysis.
4.1 Convergence of PE in Euclidean space
We start by presenting the details of the algorithm that we analyze. Consider a metric (data) space (2, p) and a private dataset S E 52n Even though we will use the notation (St, p) throughout this section, we assume in this subsection that Ω Rdd is convex and compact with diam( D and -)-,)) is the &g distance. We also assume Algorithm 2 uses the same APIs Algorithm as described in Section 3
Algorithm 2 Private Evolution with DBL projection; steps in blue differ from practical PE 33
1: Input: sensitive dataset: Ω number of iterations: number generated samples: 71gr noise multiplier: distance function: p(-,))
2: Output: DP synthetic dataset: Sr E 12"
3: So < Random API(n,))
4: for = 1... do
5: Ve Variation (itaationAA[(Ss-))
6: te + NN WNN_histgrram (5, Vi, E AiKi (see Alg.
7:
e + A NN
8:
pi E arg angminn,eAv, (B,,
9: S, +- n. samples with replacement from p4
end for
11: return ST
Algorithm Saiimm@@ieeaaae iiteratively refines an initial random dataset Sy using DP nearest-neighhor information. At each iteration. generates variations Vú from the current synthetic dataset S,-1 and computes histogram fu indicating how often each candidate is the nearest neighbor of points in the sensitive dataset Gaussian noise is added to this histogram to ensure differential privacy, resulting a noisy vector Tr. Rather than using thresholding like Algorithm T in Line this algorithm projects i4 onto the probability simplex using the DI. distance in Line 8, yielding a valid distribution μ4 over V, that remains close to the noisy estimate under the BL metric. The next synthetic dataset S, is created
5

---

randomly by sampling n, points from V2 according to 1ú in Line 9 as opposed to Algorithm 1 which creates St deterministically Line This process is repeated for T iterations, after which the final synthetic dataset ST is returned. Note that unlike Algorithm | our version receives the number of synthetic data points as input. We provide comparison between Algorithms [ and in Appendix C
Comparison between Algorithm and practical PE. Algorithm i nearly identical to the practi- cal PE implementation [3]. differing only in how the noisy histogram fig is post- post-processed (high- lighted in blue). We project fi signed measure from Gaussian noise added to histogram onto P(V)) by minimizing the bounded Lipschitz distance, which can be done via linear programming (e.g., Algorithm 2 from (25)). This is crucial for obtaining worst-case convergence guarantees. In contrast, 33 applies a simpler heuristic: thresholding ( some > 0 and re-normalizing, which is more efficient but can discard all votes if values fall below the threshold, making it unsuitable for worst-case analysis. Section 4.2 we provide data-dependent accuracy bounds for a related noisy histogram obtained from adding Laplace noise and thresholding. These bounds are vacuous in the worst case but can be much tighter in favorable regimes, e.g., if the private data is highly clustered.
Main Result: Convergence of PE. We are now ready to present our main result: an upper bound on expected utility of Algorithm 2 We provide proof sketch, and the full proof is in Appendix [ Theorem 4.1 (Convergence of PE). Let (92, || (12) with Ω Ie closed and convex and (1) & D be the sample space. Fix a E (0,1) and let Y Suppose
S=([Vaalood())++Hooll D max(d,23 in T and let Sr be the output of Algorithm 2 run input
/ 1 ns = o " (D/a)l + 1)2/ max(d.2)-1 o, 1|2-
S QT
2 log
Do 47 maxe muxx(a.2y (a.y
Then
E [ (Hs, (Hs, S Ö(dDo>/a).
Furthermore, if (0. and we instead run Algorithm with the same parameter setting as / and a log((1 25/5) tten the algorithm
<(me)²/ max(d.2)
above except T log
(A/1og(1/5))
13.2
8) and its output ST satisfies
1/a
E [Wss SO dD Vlog(ne//log(1// log(1/6)
nE
Some comments are in order. First, note that n. 2 for E (0, 1) and to ensure a E (0, 1) under DP we only need (og(()))))) S NE Second, our analysis suggests that we should set number of evolution steps T (log(n=)) and the number of synthetic samples n, = Ô(ne/ VT). which use in Section 6 Finally, our rates are vacuous for d 2 log(n). This is expected when using W1 as a utility metric, as evidenced by the lower bound of n -1/d under pure DP from g Theorem 8.5].
Proof Sketch of 4.7 Given dataset S₁ and variations Vi, in iteration t, PE constructs: the NN his- togram 11+1, the noisy signed measure je and the projected probability measure μ4. Finally, S,+1 is sampled from n4. It is possible prove the following inequality that involves these measures:
Wi Wi(ss: 1) I Wi (Ms, Aa+1) + 2D (f (o41) + W1 (H..).)
At a high level, the convergence of PE follows from two facts:
First, by creating variations of S, and selecting the closest ones to S, the Wasserstein distance to S is reduced. That is, Wi(Hs, P(41) is noticeably smaller than W1 (Us, ps.).
Second, the progress made by creating variations is not affected by the noise from DP and sampling since Dar (fr41 11)1) and W, (1/=11 are both small.
"In the nonprivate setting (c = 2o), one can skip the noise addition and sampling steps and set n. n. since nt, does not need to be chosen to balance the enror terms that arise from DP. This results in nonprivate algorithm similar to that of [33] with an expected W3 enror of 2a after T' 2 (log(D/a) evolution steps without DP constraints, similar to Theorem of (33).

---

These statements are made rigorous in our proof. Regarding the first statement, Lemmata E. and E.2
give, [, (1s, 1c+1 S (1 - >) (ps: pss)) + a for some 7 (11/d), where E, denotes the expectation conditioned on the randomness of the algorithm up to iteration /.
To bound (BL( which by definition implies (pr, 1 suPreFaz Eielie-- [VV++ which is the supremum of Gaussian process. The ex-
we use the fact that i4+1 iu+1 + Z with 7 oN(0,22Tva))
supyeFar. Jn [(dp++1 d(βr+1 + 2))
pectation of this term can be bounded using empirical process theory; Lemma E.3 states that
B.DDz((R+1 1[+1]] S [VloGivj[FBBL where (Fva((FBL) is a Gaussian complexity term [5]. This term can be bounded using Corollary E..I which consequence of Lemma E.4
We use
Dudley's s chaining to prove these results. We remark that our technique prove this bound resembles
25]. with the difference that they deal with a Laplacian complexity arising from the analysis of Pu algorithm that uses the Laplace mechanism [9]
Finally, to control Wi (1441, we use results from the literature of the convergence of em- pirical measures in the Wasserstein distance [31. 20) that quantify the Wasserstein distance be- tween a measure and the empirical measure of iid samples from it; see Lemma E.5 We obtain [,
S Ö(n, 1/ max(2.4)). Putting all the inequalities together, we conclude that
E, (W (Ass,Ss.) 5 W + + 2/V (FRI)) + O m/axdd/ m)
Recursing this incquality,
get bound on W (Ms, (sy)] )] while carefully balancing the number of variations with the number of synthetic samples so that the error terms are as small as possible. This finishes the proof of E [Wi(us, Us,) )1 s O(DDo 1/a).
Regarding the second result, for privacy we use the fact that o v 4T log 1.25/8) (c, 8)- of an adaptive composition a NN histogram with Eg sensitivity v2/n ([15, Corollary 3.3). For convergence, we plug in the and then a in E [Wr (Ms, Hs, ) S O(do!/)).
is enough to ensure Gaussian mechanisms where each of them adds noise to
expression for T in o /4T (6/(1.25/6)
NE
Remark 4.1. Most of our proof techniques work in metric spaces. Under some conditions on the APIs, the analysis of Algorithm 2 can be extended to more general Banach spaces (Appendix G
4.2 Beyond worst-case analysis
Recall that our Algorithm differs from practical PE in the BL projection onto the space of probability distributions (Line (8. To connect our analysis more to the original PE algorithm, we can swap this BL projection for a different noisy histogram step, which works by thresholding and re-normalizing- similarly to practical PF. We derive a data-dependent bound on the 1-Wasserstein distance between this modified noisy histogram and the non-private one. The bound indicates that in favorable cases, such as when the data is highly clustered, this histogram is closer to the non-private one than the one we would obtain with Gaussian noise and DEL projection, but is looser in the worst case.
Algorithmmdiiferrs
In our updated histogram step, we add Laplace noise with scale 2/ [ns] the entries of the (non-DP) NN histogram that are positive, and then threshold the noisy entries at H = 2 logg(1 (10)(1//////) (n))(n)) + 1/n. More concretely, let î NN histogram(S, V. be the non-DP histogram between dataset S and set of variations V E Ω (see Algorithm 4 The noisy histogram ju is then given by sid x|| = [A]i + L,) 101g 4.2 where (Le)ve(m) ~ Lap(2/ne). While this algorithm was proven to be (c, 5)- Theorem 3.5 of [43] to the best of our knowledge, its utility guarantee in terms of W1 distance is new. Its proof can be found in Appendix H
Proposition 4.1. Let (S, p) be a metric (data) space and suppose diam({2) < D. Given S E Q and V E Q let be the noisy histogram described above and n' = [//l|/l] if الحا > 0 and n' = μ otherwise. Then, the procedure generating p' is (e, 8DP w.r. S and for any B E (0, 1)
2101
2D 2
ne 11 (FBr)) + 2DH 2DH (00++ (7,3) +
n
7

---

where L (FBL) ( is the Laplacian complexity of FBL. I = fiE E [m]] Ald > 0} is the set of positive entries the NN histogram js. {iE i M1 H
ne )} is the set of entries the
NN histogram below O (H logd (100) and = 2 log 1/6)/(ne) + 1/n is the threshold.
Examples. To demonstrate when this proposition yields tighter result, consider the case when [ and |7| are small. As extreme example, suppose S consists of one data point repeated times. Then, |/] = and / = O, leading to an error of ( ( + -) A similar intuition valid for highly clustered datasets. On the other extreme, if every positive entry of f is 1/n, then [ [ leading to a trivial error bound. See Appendix for simulations.
Connections between PE and Private Signed Measure Mechanism
In this section, we show connections between PE and the Private Signed Measure Mechanism (PSMM), DP synthetic data method with formal W1 guarantees from [25]. Despite its theoretical guarantees, PSMM is not currently used for high-dimensional, real datasets.
PSMM one-step version of PE. PSMM takes dataset S and partition (emm of Q. It privately counts how many points fall into each bin Q2 and then builds a DP distribution over S2 proportional to these counts (details in Appendix[]. Synthetic Symthheii data is sampled from this distribution.
We can reinterpret PSMM in the language of our framework. Instead of a partition, we can provide discrete support S2' C 22 such that the Voronoi partition induced by S2' coincides with { hijmm]- Counting how many elements fall into each Ω2 is then equivalent to counting how many points in S have [ as their nearest neighbor. The resulting private distribution can thus be viewed as a DP nearest-neighbor histogram over S We believe that the reason behind this (modified PSMM) algorithm working is that the NN histogram solves a W-Wasserstein minimization problem (Proposition
5.1 proof in Appendix
a property that also plays a key role in our analysis of PE.
Viewed this way, PSMM resembles single PE iteration where !2' plays the role of the variations. If Q' is roughly a (nz))1/A-nee 1/d-net of Ω PSMM achieves (S, < O(( (((v/og(1/)) (1/ //a), improving over PE's bound Theorem 4. by factor of d. However, under the PE setup. where ? must be sampled from Random API, this net condition is hard to ensure, explaining PE's slower worst-case convergence.
Proposition 5.1. Consider S E Q2, E Q² Let n² = NN histogram V. (see Alg. Then, μ² E arg minues.. W1 (ss. Eie(m) mlolōv1a)
PE as practical, sequential version of PSMM. PSMM's main practical limitation is constructing discrete support !2' that adequately covers Ω. For example, if 52 represents the space of images, one option is to discretize the pixel space to build S but this yields unrealistic images. To generate realistic elements, natural alternative is sample from a generative model and add images to N only if they are sufficiently distinct from those already included, aiming to cover as much of as possible. However, this process can be slow-ea especially if the generative model places low probability mass some regions of Ω. Moreover, full coverage of Ω is unnecessary; we only need to cover the region containing This motivates a sequential approach: start with an initial estimate Vo of Ω' and iteratively refine it to better match the support of S. This is precisely what PE does -at each step t, V, = Variation Pariation_API(S_1) DP synthetic dataset supported on V, whose empirical distribution approximately minimizes the I-Wasserstein distance to that of S.
API(S,.1) can be seen as a refined support estimate, and S, as a
Empirical Results
Simulations
We begin with simulations where the sample space is the unit & ball IR2 and the sensitive dataset is random over Ω n RR. We use privacy parameters 1, 10-1 Our theory indicates that
8

---

Performance Final iterate of Number of Steps
Error in 1-Vasserstein
0.35
with differentt
0.30
Prodicted T
0.00
PE different
with different
15
41
80
75
90
15
10
60
75
90
15
90
60
90
Number of steps
Number of steps
Number of steps
Performance of Final Iterate of PE vs Number of Synthetic Data Points
500
1000
2000
Enor 1-Wasserstein
Prodicted nus
Prodicted nus
0.6
with dufeernttiss
Prodictodin
160 Number of synthetic data points
14s
Number of synthetic data points
Number of synthetic data points
Figure 2: Impact of parameters on PE's performance. Top: performance of the last iterate of PE when run for different number of steps; 'Predicted 7 marks the theoretically suggested value T log(ne). Bottom:
setup, but replacing T by the number of synthetic samples ns: 'Predicted n, marks the value of nt given in Theorem[4. We repeat this for different sensitive sample sizes n, averaging over 100 runs. The plots illustrate the accuracy of our theoretical predictions.
Ologg(n)) PE steps ensure convergence; for simulations set T = 2 log(ne). The noise a is then computed with the analytic Gaussian mechanism 4 Theorem 8). The remaining parameters are set as in Theorem 4.1 We post-prue post-process noisy histograms by truncating H 0 and then re-normalizing.
Dependence initialization. Let T, A E (Ms, Ms.)), i.e. the expected Wasserstein- distance between the private data and the tth iteration of synthetic data. From equation (2) in the proof of Theorem 4.1 obtain Fr $ ->) 7 (To err) err where T. We note from this equation that f S err, then the optimal number of steps for PE is T However, when To is large, our worst-case upper bound will be more accurate. Figure 5 illustrates this phenomenon. Our findings help to explain prior empirical work. (33 found that PE requires steps converge and consistently improves time when To is large. In contrast, that in many instances, PE worsens with time, and the optimal number of steps is 1.
increases polynomially with
41 found
Hyperparameter selection. Theorem 4. suggests setting the number of PE steps T (log(nee/ /ooggnn////o(((// /log(1/o))) (independent of d). Similarly, the number synthetic samples n. should be chosen to balance the eтror due to adding noise to the NN histogram in Step of Algorithm 2 (which increases with number of synthetic samples) with the error due to sampling with replacement in Step (which decreases with the number of synthetic samples). Figure shows how suboptimal number PE steps or synthetic data points degrades data quality.
Experiments on CIFAR-10
Next, we evaluate our theoretical predictions on an image modeling task, using two subclasses (Dog and Plane) of images from the CIFAR- dataset [30]. We closely follow the experimental setup in 33 using the ImageNet inception embedding [42] and Improved Diffusion (36) trained on ImageNet as Random AP1 and Variation_APP3 Unlike (33), we create variations by running the diffusion model with different degrees of variation in each iteration, while (33 fixed the number of variation degrees per iteration and decreased across iterations. Figure shows that we run PE with the
'We use the checkpoint imagenet64_com cond_270N 270K,_00Kppp from https///gihhbbccooooeeua//pppppp diffusion

---

Class Dog
Class Plane
200
260
RD
240
220
160
140
140
Number samples
100
200
Number of samples
333
400
60e
Figure 3: We the privacy parameters to == 5, 10-4, For each n E {100, 200, ... 6003, we set the hyperparameters according to Theorem 4.1 and run PE. We repeat the experiment 3 times and report the average final FID achieved for each value of n, and note that decreases with larger n.
Class Dog
Class Plane
202
100
172-
170
16-
Predictd
144
Predicted T
amerntt
with cifferent
Number of iterations
Number of iterations
Figure 4: We set the privacy parameters to 5, = 10 We consider fixed number of samples n 300. Then, we set the all hyperparameters according to Theorem 4.1] except the number of steps T. For each T' E {4, 8, 12, 16, 20), we run PE 3 times and report the average final FID achieved.
hyperparameter setting (including T and n2) derived from Theorem 4.1 then the FID improves (decreases) with more samples. This empirically supports the main claim of our paper: PE converges with enough samples, as long as hyperparameters are correctly and with appropriate APIs. We also evaluate performance of PE with different choices of T, similar to Figure Figure4connfnng confirms that using the theoretically-infomee particular, the experiments on CIFARIC 10 data presented in [33 use T 20, which turns out to be suboptimal, while T' log(ne) is better choice.
number of evolution steps T is effective
real data. In
7 Conclusion
We identified key algorithmic and analytical issues prior theory for Private Evolution (PE) and introduced a new theoretical model with formal convergence guarantees. Our version preserves the core logic practical PE and offers a plausible explanation to behaviors observed by practitioners. The analysis combines empirical process theory, Wasserstein convergence, and properties of APIs. We also connect PE to the Private Signed Measure Mechanism, offering new insights into its thcoretical foundations. Overall, our work significantly deepens the formal understanding of PE.
Limitations and future work. The choice of Variation API that we presented in Section not the same as what practical variants of PE utilize. Furthermore, the convergence rate we proved in Theorem 4.1 suffers from the curse of dimensionality, requiring many samples to ensure convergence. Future work could expand the set of theoretically tractable Variation_Ai _PI for which we understand the convergence of PE or study alternative accuracy metrics that do not suffer from the curse of dimensionality.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by NSF grants CCF-2338772, RINGS-2148359 and CNS-2148359 and the Sloan Foundation. TG was partially funded to attend this conference by the CMU GSA/Provost Conference Funding.
References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, pages 308-318,24 2016.
[2] R. Arora, R. Bassily, T. González, C. A. Guzmán, M. Menart, and E. Ullah. Faster rates of convergence to stationary points in differentially private optimization. International Conference Muchine Leurning, pages 1060-1092, 2023.
[3] Aydore, W. Brown, M. Kearns, K. Kenthapadi, L. Melis, A. Roth, and A. A. Siva. Differen- tially private query release through adaptive projection. In Proceedings of the 38th International Conference on Muchine Learning, pages 457-467, 2021.
[4] B. Balle and Y.-X. Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 394-403 403, 2018.
[5] L. Bartlett and S. Mendelson. Rademacher and Gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
[6] R. Bassily, C. Guzmán, and M. Menart. Differentially private stochastic optimization: New results in convex and non-convex settings. Advances in Neural Information Processing Systems, 34:9317 1949317-9329, 9329, 2021.
[7] A. Blum, K. Ligett, and A. Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM, 60(2):1-25, 2013.
[8] M. Boedihardjo, T. Strohmer, and Vershynin. Metric geometry of the privacy-utility tradeoff. arXiv preprint arXiv:2405.00322 2024.
[9] M. Boedihardjo, T. Strohmer, and R. Vershynin. Private measures, random walks, and synthetic data. Probability theory and related fields, 189(1)556--611, 2024.
[10] S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013.
[11] T. Cao, A. Bie, A. Vahdat, S. Fidler, and K. Kreis. Don't generate me: Training differentially private generative models with sinkhorn divergence. Advances Neural Information Processing Systems, 12480-11-2 2021.
[12] K. Chaudhuri and C. Monteleoni. Privacy-presenyv logistic regression. Advances in neural information processing systems, 21, 2008.
[13] K. Chen, X. Li, C. Gong, R. McKenna, and T. Wang. Benchmarking differentially private tabular data synthesis. arXiv preprint arXiv:2504. 2025.
[14] T. Dockhorn, T. Cao, A. Vahdat, and K. Kreis. Differentially Private Diffusion Models. Transactions on Machine Learning Research, 2023.
[15] J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series (Statistical Methodology), 84(1):3-37, 2022.
[16] K. Donhauser, J. Lokna, A. Sanyal, M. Boedihardjo. R. Hönig, and F. Yang. Certified private data release for sparse lipschitz functions. In International Conference on Artificial Intelligence and Statistics, pages 1396-1404, 2024.

---

[17] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, volume 3876 of Lecture Notes in Computer Science, pages 265-284, 2006.
[18] C. Dwork, A. Nikolov, and K. Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrete & Computational Geometry, 53:650-66 (06660663,..- 2015.
[19] C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 0(3-4):211 10777, 2014.
[20] N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3))707-733, 2015.
[21] C. Gong, K. Li, Z. Lin, and T. Wang. DPImageBench: A unified benchmark for differentially private image synthesis. arXiv preprint arXiv: 14681, 2025.
[22] T. Gonzalez, C. Guzman, and C. Paquette. Mirror descent algorithms with nearly dimension- independent rates for differentially-piives stochastic saddle-poing point problems extended abstract. In Proceedings of T'hirty Seventh Conference Learning Theory, pages 1982-1982, 2024.
[23] L.-A. Gottlicb, Kontorovich, and R. Krauthgamer. Adaptive metric dimensionality reduction. Theoretical Computer Science, 620: 105-118, 2016.
[24] M. Hardt, K. Ligett, and F. Mesherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems, volume 25, 2012.
[25] Y. He, R. Vershynin, and Y. Zhu, Algorithmically effective differentially private synthetic data. In The Thirty Sixth Annual Conference on Learning Theory, pages 3941-3968. PMLR, 2023.
[26] Y. He, R. Vershynin, and Y. Zhu, Online differentially private synthetic data generation. JEEE Transactions on Privacy, 2024.
[27] C. Hou, A. Shrivastava, H. Zhan, R. Conway, Le, A. Sagar, G. Fanti, and D. Lazar. Pre-text: training language models on private federated data in the age of LLMs, In Proceedings of the 41st International Conference on Machine Learning, 2024.
[28] C. Hou, M.-Y. Wang. Y. Zhu, D. Lazar, and G. Fanti. Private federated learning using preference- optimized synthetic data. arXiv preprint arXiv:2504.1 16438, 2025.
[29] G. Kamath. Bounds on the expectation of the maximum of samples from a Gaussian. URL http:/atw....o.tiiig////siiiiiii baciussiiimmxxppffff 10(20-30)331,200 2015.
[30] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, Canada, 2009. Technical Report.
[31] J. Lei. Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767-798, 2020.
[32] Z. Lin, T. Baltrusaitis, and S. Yekhanin. Differentially private synthetic data via APIs 3: Using simulators instead of foundation models. arXiv preprint arXiv:2502.05505. 2025.
[33] Z. Lin, S. Gopi, J. Kulkarni, H. Nori, and S. Yekhanin. Differentially private synthetic data via foundation model APIS I: Images. In The Twelfth International Conference on Learning Representations, 2024.
[34] Liu, Tang, G. Vietri, and S. Wu. Generating private synthetic data with genetic algorithms. In International Conference on Machine Learning, pages 22009-22027, 2023.
[35] Y. Long, B. Wang, 7. Yang, B. Kailkhura, A. Zhang, C. Gunter, and B. Li. G-pate: Scalable differentially private data generator via private aggregation of teacher discriminators. Advances in Neural Information Processing Systems, 34:2965-2997, 2021.
[36] A. Q. Nichol and Dhariwal. Improved denoising diffusion probabilistic models. In Interna- tional conference on machine learning, pages 8162-8171. PMLR, 2021.
12

---

[37] A. Rakotomamoniy and R. Liva. Differentially private sliced Wasserstein distance. In Proceed- ings of the 38th International Conference on Machine Learning, pages 8810-8820, 2021.
[38] D. Reshetova, W.-N. Chen, and A. Özgür. Training generative models from privatized data entropic optimal transport. IEEE Journal on Selected Areas in Information Theory, 2024.
[39] I. Sebag, M. S. Pydi, J.-Y. Franceschi, A. Rakotomamoniy, M. Gartrell, J. Atif, and A. Allauzen. Differentially private gradient flow based on the sliced Wasserstein distance. Transactions on Machine Learning Research, 2025.
[40] O. Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory, pages 789-827, 2019.
[41] M. Swanberg, R. McKenna, E. Roth, A. Cheu, and P. Kairouz. Is API access to LLMs useful for generating private synthetic tabular data? In ICLR Workshop: Will Synthetic Data Finally Solve the Data Access Problem?, 2025.
[42] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the inception archi- tecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattemn recognition, pages 2818-2826, 2016.
[43] S. Vadhan. The Complexity Differential Privacy, pages 347-450. Springer International Publishing, Cham, 2017.
[44] C. Villani. Optimal Transport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008
[45] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[46] C. Waites and R. Cummings. Differentially private normalizing flows for privacy-presers density estimation. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, page 1000-1009, 2021.
[47] Z. Wang, C. Jin, K. Fan, J. Zhang, Huang, Y. Zhong, and L. Wang. Differentially private data releasing for smooth queries. Journal of Machine Learning Research, 17(51):1-42, 2016.
[48] C. Xie, Z. Lin, A. Backurs, S. Gopi, D. Yu, H. Inan, H. Nori, H. Jiang, H. Zhang, Y. T. Lee, Li, and S. Yekhanin. Differentially private synthetic data via foundation model APIs 2: text. In Proceedings of the 41st International Conference on Machine Learning, 2024.
[49] L. Xie, K. Lin, S. Wang, F. Wang, and J. Zhou. Differentially private generative adversarial network. arXiv preprint arXiv:1802.067: 2018
[50] Zou, Liu, Li, Y. Xiong, Zhang. J. Liu, X. Ye, Y. Ouyang, and Y.-Q. Zhang, Contrastive Private Data Synthesis via Weighted Multi-PL.N Fusion. arXiv preprint 25Xiv:2502.00245. 2025.
13

---

A Related work
Private evolution. There have been multiple follow up works since Lin et al.
B3 introduced the
framework of Private Evolution. [33 48
propose PE for images and text using foundation models as APIs. Other works have extended the framework in various ways, including adapting it to the federated setting (27), the tabular data setting [41] allowing access to many APIs (50), and replacing the API with a simulator 32 In a similar vein,
R4 proposed zeroth-order optimization methods
based on genetic algorithms before 33 order to handle non-differentiable accuracy measures.
Despite many empirical works PE, to the best of our knowledge, its theoretical properties are studied only in [33], under a number of unrealistic assumptions, as discussed Section 3
Theory of DP synthetic data. The utility of synthetic data is typically analyzed by quantifying how well the data can be used to answer queries. More concretely. let be set of queries and g(S) the answer of Q on sensitive dataset S. Most of the theory on synthetic DP data measures the quality of a synthetic dataset S' with max e (q() q(S") 24 I8] When contains all the bounded Lipschitz queries. then the accuracy measure coincides with Wi (us, (As=) (see 2.2 this case was studied in 26 25 g The cases of sparse Lipschitz queries and smooth queries are studied in [16] and [47]. respectively.
22 assumes that S is sampled according to unknown distribution D and the accuracy measure is given by max [Eg= [9(=)] (. In this work, we focus on the setting where the accuracy measure corresponds to the Wasserstein-1 distance, i.c., Q contains all bounded Lipschitz queries. [3] gives a practical algorithm along with accuracy guarantees for privately answering many queries, but only works for datasets from finite data space.
Practice of DP synthetic data. We provide non-exhaustive selection of practical works on DP synthetic data. For a more comprehensive survey, see [3 Most practical methods consist of training (either from scratch or finetuning) a non-DP generative model with DP-SGD (that is, the gradients are privatized during training). For example, the following methods have been proposed: DP-GAN 44), G-PATE 35 DP Normalizing Flows [46] and DP Diffusion models 14 [I]
uses the Sinkhorn divergence as loss function and also uses DP-SGD for training. Several works take inspiration from Optimal Transport (in particular, Wasserstein distances).
[37] introduces the Smoothed Sliced Wasserstein Distance, making the loss private (instead of the gradients), and the
gradient flow associated with this loss was recently studied in [39] 38) studied how to generate DP synthetic data under Local DP with entropic optimal transport, and is one of the few practical works which comes with theoretical convergence guarantees.
In general, most wracticall-cooppettii synthetic data algorithms do not come with accuracy guaran- tees, particularly in continuous data space settings, and algorithms with accuracy guarantees tend to be less practical in high dimensions. The bridge between the theory and the practice of DP Synthetic Data transcends PE.
B
More simulations
First, we provide the figure that shows how our theory captures the dependence on initialization, as explained in Section
14

---

Good initiolization
Bad initialization
Varying initialization
PE (1, 0.0001-DP
PC (1. 0.0001)-PP
0.0.0
Error Wasserstein
0.6
0.
0:0.3
0.4
0.0.
0.0.5
0.2
Steps
Steps
Steps
Figure 5: Recall from Section 6 that = = 10-4. We set the number of private samples to n 1000. We run PE on different initial datasets created with Random_ API and plot the accuracy trajectories over log(nE) = 12 iterations. We note that the best number of steps depends heavily on the initialization from Random API. The private dataset S is random dataset in f2 R. Left: When So 5 (i.e., To O, the private data is the same the initial synthetic data), the optimal number of PE steps is large), more iterations are needed. Right: Interpolating between the previous cases parametrized by 3: So = (1 - 2, PE can improve or degrade performance depending on Random API; it never exceeds the worst-case error bound. Results are averaged over 100 runs. Our analysis explains this phenomenon (see text Section 6).
Middle: When PE initialized poorly (e.g., Sg consists only (0, 0), so To
B.1 Simulations varying dimension and the privacy parameter
In the simulations presented in Section 6 we fixed the privacy parameters to E 1, 10-4 and the dimension to d = 2. We provide simulations that verify two expected behaviors that can be derived from the convergence rate provided Theorem 4.1 when varying e and Namely, the accuracy degrades as the dimension d grows, and improves when grows.
Error in 1 Wasserstein
0.8
Error 1-Wasserstein
0.50
0.7
0.55
0.6
0.50
0.45
0.4
0.40
0.3
0.35
0.2
0.30
2
6
10
0.2
0.4
0.6
0.8
1.0
Dimension
Epsilon
Figure 6: We set 8 10 4 and run PE with the hyperparameter setting suggested by Theorem 4.1 For the plot on the right, we fixed & = 1 and vary E 21,2,33 3, 3.., 10). For each value of d, we report the final accuracy of PE averaged over 100 runs. On the right, we repeat similar procedure but fixing d and varying e E
C Comparison between Algorithms
I and Practical PE
C.1 Practical Private Evolution
Let us start introducing Algorithm 3 the practical implementation of the PE algorithm from 33
C.2 Comparison between Algorithm and practical PE
We outline the main differences between the practical Algorithm 3 and the theoretical model in Algorithm [ initializes So with samples, and with high probability |So] |S1l
Algorithm [
15

---

Algorithm 3 (Practical) Private Evolution
33
1: Input: sensitive dataset: S Q² number of iterations: T. number of generated samples: 7a.
noise multiplier: a, distance function: p(:;), threshold H
2: Output: DP synthetic dataset: Sr E 92"
3: So & Random API(n.)
4: for t = I...T'd
5: Vi f- Variation -)
6:
er NN IN_histogram(S. Vi, E Aivil (see Alg.
7:
j4, + NO o (MI)
8:
#1 - w4/lll4li II,, where Ml + Po] (12m)) for every i [[V]]]
9: St < n, samples with replacement from 14
end for
11: return ST
Algorithm 4 Nearest Neighbor Histogram (NN histogram)
1: Input: datasets: S, E Umen? metric on Qt: p(:,))
2: Output: nearest neighbors histogram on V
3: histogram + (O...... E R/V
4: for I..., S| do
5: I f min (k: & arg mi ((S]) VbD) (ties are broken by picking the smallest
index in the argmin)
6: histogram[A] + histogram[k] + 1/|S|
7: end for
8: return histogram
= [ST]. This is required for their utility proof based on p-closeness to work. In practice, PE maintains synthetic datasets of size n, potentially different from n, and n, is part of the input. In our simulations (section 6 we show that setting n. correctly is critical for convergence, hence not being able to set it differently from n is serious algorithmic limitation.
Once the NN privatized by adding Gaussian noise and thresholded, Algorithm I creates the next dataset deterministically by adding variations to the next dataset proportionally the entries of the DP histogram. There are two issues with this. First, calculating the proportions requires exact knowledge of the multiplicity parameter B to create dataset 1y-close S. However, in practice B should be calculated privately from S. which gives access to up to an error. Second, the practical version of PE normalizes the DP NN histogram after thresholding and then samples with replacement variations to create the next dataset. Algorithm [ does not take into account these steps, and as consequence its convergence analysis does take into account the error incurred by them.
C.3 More details on the limitations of the analysis of Algorithm 1 from 33
The theoretical analysis of PE in 33 does not reflect how PE operates in practice. Their convergence proof relies first showing that noiseless PE (Algorithm with o 0) converges, then arguing that when each data point from the sensitive dataset S repeated B times, with high probability the noisy version behaves exactly the same for large B.
The convergence of noiseless PE is proven as follows. Given Q" and the initial random Sp E 22. the elements of S and So are matched: assign So to S(i.. Variations of So, denoted by Vo, created and [1] is chosen as the element from Vo that closest to Sl:], as indicated by the NN histogram. Vo contains the variations of So which are likely to contain point closer to Sli] than So Repeating this process, they construct Su, S1. Sr, where S.[i] is closer to S[i] than S They conclude that for any 1) 0 and sufficiently large T, it holds that for every E [n]], Sr is within distance 77 of S[i]. We say that S and ST are y-close when this happens, denoted by S -,, ST-
To prevent noise from overwhelming the vote signal in the noisy case, point in repeated B times. This ensures that, with high probability, the NN histogram entries least B n (dominating the added noise) and that the number of times
33 assumes that each data
BBB that
16

---

Vi[ii is included in St+1 is equal to nff In other words, with high probability the noisy NN histogram coincides with the non-DP NN histogram, which clearly violates DP when we remove the unrealistic multiplicity assumption. In fact, the exact assumption they make to argue that S = Sr is B v / (/)) log(1/6)/E (Theorem 2 in B3 If we let B be constant, then their convergence proof is valid only for e = ((V/llog(1))) log (6)) or, equivalently, 1) = 22(e==/(dloo(1//))
C.4 Comparison between Algorithms and
We note that Algorithm overcomes the unrealistic features present Algorithm For example, can generate random datasets of any number of samples a. since we do not use n--cosenesss arguments to prove its convergence. In addition, does not require exact knowledge of the multiplicity parameter B, since our convergence proof assumes B 1. which is usually the case in practice. Finally, Algorithm 2 post-processes the noisy NN histogram by projecting to the spaces of probability measures over the variations and then samples variations according to this probability distribution to generate the next dataset, resembling what is done in practice.
D More Definitions
Definition D.1 (Covering and packing number 45
). Lel p), be a metric space. For ā > 0,
ô-cover St St wet p is set Q' E ΩM such that for all w E S2 e [M] with p(w, (((i)) I 8. The covering number definition is the following:
NΩ2, 0) = min(n E N: exists ò-covering with n elements).
Similarly, 8-packing of St w.r. is a set St' E S with the property that V(i, E [M] x [M] with i # j. p(22 (1. ()) 2 The packing number is defined
M(2, p: 8) = max N: exists a 6-packing with n elements).
Definition D.2 (Gaussian and Laplace Complexity). Let F be a function class on a metric space (L, p). Then, the Gaussian complexity [45] of F is defined as
(F) := sup
E En Pl N(..)
sup Σ xxf((z) fer n
iE(m)
The Laplacian complexity (25 of is defined as
Σ x. sts( sup
LF(F) = sup E
En SI... Lap(1)
fer n
vE(m)
E Proof of main result
In this section we provide the proof of our main result, Theorem 4.1 along with the necessary auxiliary tools.
Proof of Theorem 4.1 Note that for any = O,..., T
Wi (us, (SS (Mss
Dar (ns,
S D (us; Pe+1) + Dar 1441) Dir(tees, + Dar (p
=Wi(us, (441) + DEL (Pet1 pe41) + DBL (P1441111444)) + Wa (
I Wi(us, Ae41) + 2D (Pe41, + W1 (1b4t,,
where the inequality follows from DEL (f441 (441) 2 DBL (fz(111,, by definition of the projection in DBL distance. Denote by E, the expectation when conditioning on the randomness up to iteration t of PE. Lemmata E. and give
E, W. A141 s (1 (1-))Wi(ss pss)) a,
17

---

with y 3r((v Further, using the definition of Variation (etiatioo_AP((S)),, it is easy to
see that V2 has nu (2 (2 loga D/ a:) + +) elements. Letting V -
Lemma E.3
implies
E [r. (fx+1, A &VGGv(FnL)
Putting everything together, we conclude that
E, [Wi (Jss, (S..) ) - (1 - W (us, + a 2VoGv (Fr)) + Wildee1sPsppl
Integrating on both sides and denoting I; = E (Hs. we obtain
T S (1 (1 2VoG +1
where
Vlog(2VV)
d =
vV log(2vV13/2
(FLL 10D
d=2
VV
ylug(avv/a(d/2-119g V=/a(d/2-1
d23
the upper bound on (FBL) from Corollary
E.1 and
n₂
1/2
d= 1
CD
log (n.(n)))
1/2
d = 2
1/d
71g
d 2
the upper bound on E[Wi (1441: from Lemma
B.5
Hence, after steps of we obtain
T-1
Pr (a
W1 (n.))
Σ (1 7)
1=0
- (1 - --
= (1 - 7) + (a + + (n
- (1 7)
lo a 2VoGG( (n,)))
a: + (VoGv(FBL) + (n
= (1 - 7)T
(2)
7
DD + 2VoGv(FBu) + W.(n)
where the last inequality follows from the fact that a- 2o 0 and To I D. Next, note that
20 20 (og(2vV) + Cn. -12
VVGG((FBL) (W.
20 Vo log (2)og(22V)))) 2V C'log(n,) 1/2 1/2
= 2
200 1/4 o (wtp//2//2////2222//////
Cn -1/4 1/d d 3
(d/2 1127
Since = n, (2 log (D/a)) + 1), picking n. = (222 + 1) 1/ max (d.2) -1
gives
2VoGy + (n.)) < Ō(Do1/ max(d,2))
We conclude that
Tr TI ò (0a a Do max
7
Finally, setting
1/ (dx(d.)) and T 2 [logly/ (D max( 1)/m1 we obtain
Do max(d,2)
Pr S
= O(dDo
4 T (o](oo((12))) 25/8)
This proves the first result. For the second, note that if e, < 1, then is enough noise privatize T' iterations of PE by viewing it the adaptive composition of
18

---

T Gaussian mechanisms where each of them adds noise to a NN histogram with &y sensitiv-
ity v2/n ((15), Corollary 3.3). Since we need T > log(n/o
suffices to set obtain
m2x(2.2))/ 0og(n/o//maxd22))
T log(ne/(Ay boggt///4//og((//111 (log(ne/ Vlog(L/o]) ((log(nee//lo(((//)))
max (
1/4
V Vlog(ne/ /log(ee//log(//// /oo/////((()))))) (1/6)
P1 SOO dD
E.1 Lemmata used in proof of Theorem 4.1
Lemma E.1. Assume Q is closed and convex. Then, for any 21, E 22 || z2|1al S 11-7))la, - 22112 + a with y sx((vo+og(2)) +log(2]]
APl(()) E|
where the expectation is taken w.r. Variation_AP((<.)
Proof.
Case 1: || - 22112 & a. Note that E|minn- (PI((r) ||2 - =212] S 2 #2 ||2 = a, since 21 E Variation_AP((s))
Case 2: || 22|12 2 a. In this case, there exists 1" E (1,..,, [ogg (diam((()))) such
that 2 a < || 22I|2 2 I 2' a. Now, we proceed as follows,
E
min se Variation (AP(())
||2 - 22112
E
|| proja + N...)) =2212 kE/2)/
min
< E
min [r(
||||| + Nodl1 2211?
EE
min [E())
|| 22113 2(V 1. 21 22) + 11
min E
min kE|2]
||
22112 2(N 21 22) || 112
(E(L)
||
22112 IE(A)
min
2F
max kE(2)
(N
21 22) +
|| |
kE(2]
0il1a1 22112
|
22112
min (E(L]
+
ofl( 1og(2))² 1og(()]
VT
| 2211
20 2"
a
+ of [[V[[ log(2))² log(2))
V
112
2
22l13
x[(Vd + (2) 2 + log
$ ||| 22112
(1- 4 4 1og log()))))(22))) log(2))
where we used the lower bound for the expected maximum of Gaussians from (29 and the upper bound for the expected maximum of chi-squared from [10] (Example 2.7). and the facts that inequality together with v1 - < 1-2 for t < 1 allow us to conclude.
(2)) and 2'" < || 22112 S 2 a. Jensen's
a2
Lemma E.2. Let Ω be closed and convex and S,S' E Um2112m be two datasets, V Variation_APTQe and NN WN_histogram(S, V, p) (see Algorithm Z.. Suppose that for any 21 E 22 22 E S, E/min V p(z, 22)] < (1 - 7))((1, 22) + a. Then,
B[Wi [)] (1 WPs, (s+)) a.
19

---

Proof. The general idea is the following. We will exploit the fact that the 1-Wasserstein distance is defined as the infimum of expected transport cost over couplings. First, will bound W, (ps, P)) by constructing an specific coupling between jts. ji that comes from the NN histogram. Then, by using Lemma T we will show that the resulting expression is upper bounded by the expected transport cost with respect to any coupling between Ms and jss,, up to an additive term. By taking infimum over the couplings we will obtain the final expression.
Let न E i[ss (i) be the coupling defined by
(S[], vb1) = 1 min (k: k arg m ((Si) vbD))
S
for every i E [|S]], E [[V]]. Let's verify that á E M(uss,), Clearly *(S[i, 2 0. Furthemore,
*(S|,,
VbD)
S
JELlII
equals the mass that As assigns to S(i), and
1 min {k: e arg j ((S (DD))
Σ A(S|), = Σ
S
rE[|S|]
SELVII
equals the mass that fi assigns to V[j], since j comes from nearest neighbor histogram according to Algorithm (f² NN NN_ histogram p)) Hence, the marginals of 7t are μa and jú, which proves that A E TI [Ms, j.). Next, note that
I plz1, 22 d2) ( 21, 22)
E inf rEll(ps.Bet axx
inf Ae jE(lV]
Σ
P(S(i), V(I) VD)
inf x(Il(
Σ sElIS|)
Σ
p(S V(I) vDi
< E
Σ
Σ
p(S (101) viT))
(E|[ST) jEllV]]
P(S vb]) 1(j min {k: & E ji ((S vDD))
Σ
Σ
E
[
jElIVI
mingev ((S(i), 2)
E
|
20

---

To continue the chain of inequalities, let us consider any coupling x' E I[ Hs+)). By definition it satisfies E)E[|S']] (SS 3 Hence,
Ev 2)
Σ [El[|Ss]]
min ((S
zEV p(S(i),
[5]
IE
Σ
Σ
ze VariatioonAAI(S""1 /(S(i),
min
jEl|sM)
Σ
Σ
S'(
min SE Variaation p(S()),
fellst JE
Σ
Σ
T'( 5')) max((1 mmxx(11-7)o0tt)s5100...)
JE(|s|)
s (1-7)
Σ
Σ
+
iE
811
JE[[S'
(1 7)) /
p( 22) (21, +a
nxn
where the second inequality comes from the assumption that for any E 22 E S. E| API(=)) ((2, 22]l I (1 7)p(21) 22) a. Putting the incqualities together, conclude that for any x² [[sss ps+) it holds that
(W,, 1e+1)l ) s (1 -)) /
p(21, 22))d'((2 22) + a.
Sux
Taking infimum over the couplings on the right hand side finishes the proof.
Lemma E.3. Let V E Q², Let μ E An be a probability measure supported on V. Let Z
(Zi,..,, Un) (0, o² In). Then,
Ez|DBL(H, + Z)] S (.GG((FB))
Proof. By definition of DEL. we have
DBL DBL + 2)
sup Jefmi 20
f(dp - d(p + Z)) sup Σ f(V[i)).
JEt iE/m
Hence,
f(V
( u Z)] =
sup SEF (E(x)
Σ f(V
= noB
sup JEF n
S (F
:E(n] σ
E.2
Upper bounds
We need upper bounds on Gaussian complexity terms and on the convergence of empirical measures Wi Let start showing an upper bound the Gaussian complexity via Dudley chaining. This proof follows closely the proof of upper bounds for Laplacian Complexity given in [25].
Lemma E.4 (Gaussian Complexity bound). Let (2) be metric space and F a set of functions on Ω. Suppose diam([) < D. Then
a 1" Vlog(N(FF 3))dB
G,,(F) S inf a20
where C. is an absolute constant.
21

---

Proof. For each j E Z, define E 2 and let T be Ey-coveinng of F, such that [T -F, E,) (i.e, the cardinality of the cover the covering number w.n.. lls)). Fix f F and let "j.f be the closest function to in 7j. Since we are assuming that P has bounded diameter, there exists jo such that for all l: S jo. [T = Then, for any set {2i)
m
sup SEF
Σ (z)) :E|n]
I sup Σ SEF n
x.(f(2))Tmm,
Tm. x
E
sup FEF n
Σ
a:(me,((2i) Th (2:))
iE/1
iE/m]
for all Z, m
jo-
will give in-expectation bounds on the two terms on the right hand side. First, we trivially have
sup /EF T
Σ
x;[s(zz) - Tm. (2+))
S
Σ
S 6m = 2-m
n sE(n]
sEin
For the second term, note that
1
1 1 sx-1(z=)
Tk. (2:) -T- (o-1(((2))]
Th
Th TT-
ck Ek-1
n
3
n
Hence, EiENn Del ((TT,,(())) - Tk Tk-1,f(2;)) is a BBee//m)-uubGuustee random variable. We con- clude that
Evvllo || (boi))))
Σ
sup SEF
vn
KE|M]
since the maximum is over at most WFF || (x) random variables, each of which (35k/ Vn)- subGaussian.
Putting everything together, we conclude that
m 8k log(N(F (F, (l)oiEk))
sup Σ (z)) JEF VE(n)
SC 2 m +
Vn
k=jot1
C inf a20
a
v Vlog(N(F. 1oxo 3))d3
Finally, since N(F, || (bxo;)) = 1 for 3 > D, the integral above can be computed between a and
D. This finishes the proof.
Corollary E.1. Let C Rdd and pl.,.) = 1|2. If dia S D, then
9 12g
d
Gn(FBL) S
10D 12g(2
d d 2
V
100 log (dd////////22/////2 1)2/2)
d 2
(1/2-dd//11)))
Proof. From 23 (Lemma 4.2), we know that
8 3
N(Fr. || 1)xi:) <
where FL is the class of L-Lipschitz functions mapping 9 to [-1, is easy that DFi/D FBL. since FBL contains all the 1-Lipschitz functions mapping Ω to I-D, D). Then, for any
22

---

3 [0, D]. log( |l (occi)) can be bounded as follows
log(N((BLL.) -loo: = |o 11 3))
= -log(W(Fi/D)) || bloc /3
D))
8DD
SV(2 || ||2: B/2) log
(8D
SV(DB2 || 112:8/2) log
3
(8D
= =V(B2, || 12: 3/2D) log
4D
8D
+
log
3
3
5D
d
8D
log
8
B
where the last inequality uses the fact that 3 E (0, D).
Replacing this expression in the bound given
by Lemma E.4
we get
1 D
5D
4/2
8D
Gu(FBL) S inf
a+
log
d3
a20
vn
3
Mlo((DD /a)
5D
4/2
inf 020
a
d3
Vn
/log(DD/))
inf a
+
d3
a20
Vn
We compute the integral for different values of d:
d 1. this case,
f B 4/2 4/2 = 2(VD Vo) s 2VVD.
It follows that
v loog (a)(8D/))2V5D
(n)
G.(FnL) S inf a +
a20
vn.
where the last inequality comes from picking
2v5D in the infimum. vn
d = 2. In this case,
[
4/2 = log ()) log(a) (D/) S log(8D/o).
It follows that
G (Fr.)) < inf (a log(8D/a)8/25))
1og(2vn))/25D
a00
Vn.
Vn
where the last inequality comes from picking
5D in the infimum. v
d > 3. In this case,
a1-d/2
D/-4/2
1-4/2
3 g/d/2
d/2 -
d/2 -
23

---

It follows that
(l)g(8D/))55)) d/2 a²-d/2
Gn(FRI) S inf a20
Vn
d/2 -
< 2 Vog 2n /d(d/2 1)2
nd/ddd/2- 1)2/d
where the last inequality comes from picking a n in the infimum.
5D
The convergence of empirical measures in 1- I-Wasserstein is topic of interest its own, that has been studied in the past. We obtain the following corollary from 31 We note the results in there hold more generally for Banach Spaces.
Lemma E.5 (Corollary of Theorem 3.1 in (I). Let μ be probability measure with finite discrete support on Rdd contained {x E Rdd ||x- - vll2 S RR for some y Rdd jun the empirical distribution of N üd samples from μs. Then, there exists absolute constant C, such that, for all
N 1 1,
d 1 Nog(N)N-1/22 N-1/d
N-2/2
([ SCR
d 2
d 2 3
Simulations with histogram from Section 4.2
We follow the same simulation setup from Section 6 Namely, consider the sample space be the unit l2 ball IR2. We use privacy parameters 1,5 10-4 We set T = 2 log(ne) and the noise is computed with the analytic Gaussian mechanism (44) Theorem 8). The rest of the parameters set as indicated in Theorem 4.1 We run Algorithm
2 with the only difference that we post-process noisy histograms truncating H 0 and then re-normalize. In Figure
refer this algorithm
as 'PE'.
In Section 4.2 introduced alternative histogram that is built by adding Laplace noise (only) to the NN entries that are positive and then truncating the noisy entries that fall below H log (1/5)/(ne) 1/n, followed by re-normalization step that the noisy histogram induces a probability measure over the variations. Running Algorithm [ with this histogram (instead of the one that adds Gaussian noise to all the entries of the NN histogram, thresholds at and re-normalizes) is referred to as 'PE with Laplace noise-thresholding in Figure
We argued in Section 4. 2 that this alternative DP histogram can work very well when the dataset is highly clustered, but can also lead vacuous utility guarantees in less favorable cases. We illustrate this in figure? 7
G Extension to Banach Spaces
We note that Algorithm 2 can operate on any Banach space (2, as long as has access to adequate APIs. Below define property on the variation API that suffices to prove algorithm convergence.
Definition G.1. Let 1 > y > E N and > 0. A (randomized) variation API is (7, v, a. for a dataset if
For all E Q, Variation_APHe and Variation_APl(()]
For all zι Q, 22 E S such that p(z1, 22) > a,
Eariiaiion _AP(()
min APP
p(z, 22) $ (1-7)p(22, 22).
If Variation API satisfies this definition, then prove the following result.
API

---

0.45
PL
Error in 1-Wasscrsteln
PE with Laplace noise + thresholding
Error in 1-Wasserstein
0.40
PE with Laplace noise thresholding
0.5
0.4
0.30
0.25
0.20
0.2
0.0
250
500
750
1750 2000
Sample size
Sample size
Figure 7: Comparison of the performance of PE with different histograms. Both algorithms, 'PE' and 'PE with Laplace noise+thresholding" are described Section F Left: the sensitive dataset is distributed uniformly in an &g ball of radious 0.02 around the origin (heavily clustered), leading "PE with Laplace noise+trresholding outperforming 'PE'. Right: the sensitive dataset is distributed uniformly in an Ez ball of radious 0.5 around the origin (not clustered). The votes signal in the noisy NN histograms is lost by 'PE with Laplace noise+thresholding during the thresholding step. Hence, it performs poorly. Results are averaged over 100 runs
preserve the votes signal in the noisy NN histograms,
Theorem G.1 (Convergence of PE). Let (St, p) be (sample) Banach space. Suppose St is compact. Let y > 0, v E N and a > 0. Sr be the output of Algorithm 2 run on input E 22", T E N,n, N > p.)() If EfariationAAPIy
is an (y,, v,, a)API for S, then
E [Wi [Wilus, (sr)) S (1 -)
>)" (W1 (Wi (Ms, (ss)) err) + err,
where So is the dataset created in Line 3 err (ax + Son,GGmm,ff (FBL) + (n.)))/ (m,) an upper bound on the rate of convergence of empirical measures from n, samples to the true measure in W1 and Gun, (FBt) is an upper bound on the Gaussian complexity Gun, (FBt).
The upper bound the Gaussian complexity that we provided in Lemma E.4 can be used to find
G um (FBL), since it works for general metric spaces, and the upper bound Wi (n,)), can be found in
31
The proof of Theorem G.1 follows similarly to Theorem 4.1 We provide it below for completeness.
Proof of Theorem
Note that for any = 0,
D DL (Bss
DBL (Ms: + 1144, DBL (pe41,1,,)4))) + DBL (1441,944))
WWss + DBL (Pe41, (P+1) + DBL (Mt41, W, (1441)
I (14)) + 2D (fr41, (v+1) + (S
where the inequality follows from DBL (fx+1 M441) 2 DBI(Fe+1, 14+1) by definition of pla Denote by [-[-] the expectation when conditioning on the randomness up to iteration t of PE. Since Variation_APIç is an (7, u, AA-API, then Lemma B.2 gives
E, [W, (us, (e41) S (1 Wiss) (s:) +
Further, since Vi] = 0m,, Lemma E.3 and the definition of G.,, (FBL) imply
E, [D (e41 & vn,oGun, (FBL. S on, (FBL).
Finally, by definition of W (n.))
E, W ( (S. (W()).)
Putting everything together:
Ee Pc+1)] 5 ( + 2n,o (FBL) + Wl.))..
25

---

Integrating on both sides and denoting I, = [[Wi(ps: (s.) we obtain
T++1 (1 7)' +a 2en.o (FBL) Wi (n.).
Hence, after 7 steps of PE we obtain
T-1
Pr s (1-7) (a + 2on, (FBL) + Wi(n.))
Σ (1 7) i=0
(1 7)²
=1 - (1-7)"oo To (a + 2mm (FBL) + (n,)))
(1 -1-
(1 - 7)² To + 2 ( W1 (n,)))
+ 2on, Gun, W1(n.)
H
Missing proofs
We start with the proof of Proposition 4.1
Proof. Recall that is given by [ (n[i) + I,)1 -000 where {T.)eem)) idd
Lap(2/ns). This can be seen alternatively constructing as follows
If Aili] = 0, then ūili] 0.
If [[[]] > O, then jilo] = [[[i] + L,, where L, Lap(2/ne). If if] < 2log((16)/(me))+++ (i.e the coordinate is small), then it is truncated: jili] 0.
Let be the measure after adding noise to á but before truncating the small coordinates to obtain j. Furthermore, note that all the entries with [[li] = O remain unchanged with our procedure. Hence, the effective support of all the measures L(3) such that the event É' {14i] S L(3VVi has probability of least 1 B. Recall that
= {i e [m] : ; > 0} rather than V. Also, define
H 2 log(1 (1/61)/)(s)) - 1/n.
First, note that
Wi(a, = DBL(A, H') & DBL v) (BL(U, (B,(k.
We will control the terms the right-hand side one by one.
Let's start with DBL v).
[( =E
sup Σ F(VViA(A L. -A(l) SEFBL iEi
2 ms
Lin (FnI.)
where Liz((FB is the Laplace complexity of FBL-
We continue by bounding DBL (v.
26

---

[[DDI[u, =E
sup Σ
[(VE(( L, [M0] + I.) (2)01+(+2.2)))
feJBL sel
$ DE
Σ ieT.Al++4<.1
A + Lr
S DB e 1: Ali] + L; < H}]
(i pil] L, H) EJP Bifi i: A + L, HI 19P((E
S DB([(i E L(3) HJ| + +1{13)
Finally, let's look (BL p²). If || then DAr. (P,, n²) O. Otherwise,
DBL(H, = DBL 1/1l@(11)
Σ (1-
= sup JEFNI jEf
|| [
< D
| = DIlA 1/.
|
Next,
11 ||/||11
Σ p
Σ
M + L
sei
E
A| + T4 Σ Tu
iEhAlt)LL
iE7
Σ
A +
+
Σ
EEĪ
$ Bl [ T: All + H +
Σ L
iei
We have already argued that
ElKi I A 44 < Hill l( 7 p
- L(B) < +11+
Furthemore, since the random variables L; are iid Laplace we have
E
Σ4
L
E
Σ
Li
iEĪ
Var
Σ
Li
iEi
V((Var(Tn)
2//27
ne
Hence, we conclude that
2D 2/ 2|
EiDnr (1) DH([(e pD L(B) s +H|+1/13)) +
nE
27

---

Putting everything together, we obtain
2
2D 2
+ +D E:: pld - L(3) & H + (T]3) +
Finally, observe that by the tail bounds of a Laplace random variable, L(B) - [og(I)i for P 2 B. This concludes the proof.
suffices
nE
Next, provide the proof of Lemma 3.1
Proof. For simplicity denote the packing number M( p; 2n) by this proof. Consider 21y-packing of Qt {=1, ..., RM Let S { For k E 24. define
(kk) = Bp(21, n- Bp(2k.)) 7)
It is easy to that if S = A(S) A(S) B(1), and if A(S) B(k)) for some A: > 2, then
S and A(S) can not be yy-close. Since P. S -n A(S)
> 1 - then
PA A(S) E UREAn|2,M B(k))
S..
Furthermore, B(1) n BG) = for all * E ZN M),
P^ A(S) M2 B(k)
E
PA A(S) B(K)
kE2n
Hence, there exists a set B(k*) such with PA A(S) E B(k*)
S 5T((M 1). Finally, construct
S' = (= U {zz-1 J. Note that S and S" are neighboring datasets. Then, by the inequalities that we have stated and (e, ()- follows that
ET 1-r P PA S' -, =, A(S') PA A((S)) E B(k')) < P A(S) E B(X*) + S M
8.
Solving for s, we get e 2 log((M - 1) Finally, note that
(M - 1)(1 - M(1 - -8)/(7]] 2 M,
where the last inequality follows from the fact that 1- 5 2r, which is consequence of assumption that < - 3r. This concludes the proof.
Finally, we give proof for Proposition 5.1
Proof. Let E Am and denote by (T)) the set of couplings between 1 Ere(n) Astg and Eje(m) ubilōviss. Then, the following lower bound holds
Wi
1 n
851 Σ pli]ōvil
inf Σ =ETT(N)
Σ p(S)i,, VLiDTT
sE/m]
fE(m]
inf rEll(n)
Σ
min p(S v151) jElml
Σ Thj
minje[m]
P(S)t) V(1)
Σ
In addition, note that if
1 (j minfk: k e arg minve p(S V(0)))
n
28

---

then (1) nT" II(x)):
Σ m
1
m Σ
10 [t],
5
and (2)
minse ml p(S(i), V vbil
Σ Σ ((S - E Σ pl M(S))) VDDTT
Σ
n
(I) and (2) together with the lower bound from
imply that
(H", E arg
min El)
Ee(s|d [(()),
which is equivalent to the statement we wanted to prove.
I Details on the Private Signed Measure Mechanism
The Private Signed Measure Mechanism is an algorithm for differentially private synthetic data generation presented in (25. It designed work under pure differential privacy. For completeness, we provide an extension of it that works under approximate DP. The algorithm and its proof closely resemble the one from 25 with the only difference being that we need deal with Gaussian noises instead of Laplace in order to achieve approximate DP. As we mentioned in Section [ as a sequential version of PSMM, and the gaussian mechanisms has better composition guarantees than the Laplace mechanism. Hence, even though changing Gaussian noise by Laplace in PSMM does not make a big difference, it does make a more notorious difference for PE when seen as sequential version of PSMM.
PE can be seen
Algorithm 5 Private signed measured mechanism with approx DP
Require: Dataset S = {=1, ..., ) partition (9.)) number of synthetic samples
1: Compute private counts: n; |S 22, N,, where N; ädd NOO log(1/)).
2: Let ji be signed measure such that for E [m]. (((w;))) = ū./n for an arbitrary wi E Q2 and
((2, [wi])
O.
3: Let fe be the closest probability measure over {wi,,....w,, Wm } to j in DEL distance.
4: Let ze be an arbitrary probability measure over Q2 such that ((+)) i (((w))) for all E [m].
5: return S ~ NM
Theorem 1.1 (Guarantees of PSMM under approximate DP). There exists partition {Lt (iljimm of such that Algorithm 5 run on S E Ω2, {24)ie(m) outputs an (E, 8)-DP synthetic dataset S' satisfying
(Ws us:) 2 max ( my log/oog11/)) Gm((F) + E(W (M, ps:)
eE|m]
ne
where is the probability measure from Step ||. 112, === /oe//D//og((//) /lo((1/8] and diam
Furthermore, if S C Rdd with diam([?) S D,
I O(Dm 1/ //xx((d.)). then
El <0 ( D [log(1/8) 1/ max)2,d)
1/ max ma,d)
1 Thas
D
TLS
Remark I.1. When running PSMM, we can select n, arbitrarily large, by the post-processing property
1/ max(2.d)
/log(1/8) ne
of DP. Hence,
safely assume that the error term D
dominates in the
utility bound presented in Theorem T.1 Note that, up to logarithmic factors, this bound improves over the bound that we provide for PE Theorem 4.1 by factor of However, it requires {2t (vel)) to be such that maxie[m] diam (S2) = 0Dmm max(d.))) Constructing such partition in practice is equivalent to finding O DD 11 max[d.2) )-ne J-net of points (wi..... Wm. such that the Voronoi partition induced by them is (Ω, (e))) We explained in Section 5 why such net can be difficult to construct in practice.
29

---

Proof. Since the fz-sensitivity of f(S) - (IS n Q2 Die[m]] is 22, privacy of the measure μ (from Step 4 follows from the Gaussian mechanism. The privacy of S' follows by post-processing.
The convergence proof is similar to the utility analysis of one step of PE. Let be probability
measure over S2 such that (((w;)) }) = n//n, where n, = |S n S2y1, and ((S2)/W), Win O. Let the measures P. and be given by Algorithm 5 Note that
Wi Wi(ps. (Bs, μ) & (BL(US, p) + (L, µ + DLL P)) + (BL(A,
Wi(us, p) DL (f. ()) DLL ( + (1,
2 WW (Ms, P)) + 2D (T,, p.) + W2(
2 max diam (S2,) + (BL (E(m)
where the second inequality follows from the fact that DBL (1) 2 D DBL (ū, pt). which is a conse- quence of üi being the closest probability measure over {WI, Wm to j in DBL. and in the last inequality we used max (Wi (Ms: F)), W1 (R, ()) I maX,g(m) diam (f2;) (these inequalities are trivial since the pairs of measures jas. fr and P. fa assign the same amount of probability mass into each region f2;). It remains to bound DBL (f, P.). The following equality
DBL(A, p = sup fer
f(dj dī)
sup Σ f(wi) JEF mEmm]
144
n4
+
N
sup NW SET
(E(m
allows to conclude that
1og(1/))
Gm (F))
E[Wi(us: p) <
max diam((2)) +
iE(m)
ne
The proof of the first claim is concluded by noting that IE(W (us, (ss))) < B[Wi (us, w)] B[W (H,
< max dSa +
m
Gm((F) + (H
.E(m]
ne
For the second claim, recall from Corollary
E. that
9 log (2 D)
Vm
Gm (FFB
(2. /2)aa///// 3/2
d= 2.
Vm
10D
d d 3
(d//1//2-1)3//
Using this in the inequality from the first claim and using that diam = O(Dm 11/ 11 max(2,d) for all i [m]] we obtain that
Dm--1/ 1/mxx(2,d) Vlo((1/))
(us, ò
Dm 1/ max{22d)
+ W (s:)
nE
Using the definition Lee//D//og((1//// it follows that
(D)
1/ m/aax(2.0 (2,4)
D (oo((1/))
E[Wi Ō
+ (H,
mE
Finally, since S ,r=,, Lemma empirical measure in Wi
E.5
gives the following upper bound on the convergence of the
= 1/max(2.d))
This finishes the proof.
Impact Statement
Our work is theoretical in nature, so it does not have direct societal impacts. However, we believe that our theory can improve the practice differentially private synthetic data generation, leading to positive social impact by enabling safe data sharing within and across organizations.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims from the abstract and introduction are discussed the rest of the main body, and the proofs appear in the Appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss in detail our theoretical model and elaborate on the only step that differs from practical algorithm in Section We also illustrate some limitations of our worst-case analysis for guiding practice with simulations in Section 6 and discuss some theory for beyond the worst-case analysis of our theoretical model in Subsection 4.2
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
31

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All of our theorems, lemmas and propositions state the assumptions made. We provide proof sketch of our main result in the main body and defer the full proof to the Appendix. For other results, we discuss intuition or motivation in the main body and provide formal proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Thcorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our experiments can be reproduced following the setup described in Section and we will provide the code for it.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
32

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We will provide the code the Supplemental Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips https/sccpublcccuuuddooooo
Coweeoomiisiieiieooeeeeeeoo Pollcyy))))) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Parameter setting is described in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our simulations are averaged over 100 independent runs and report the average and standard errors (shaded areas in figures).
Guidelines:
The answer NA means that the paper does not include experiments.
33

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Simulations are run on a personal laptop with Apple M2 Pro chip and 32GB of memory.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that cctpp//bbcc//tiiccccu..elellllll
didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The paper conforms with the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Impact statement in Section
34

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do release new data or models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our simulations use synthetic data.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
35

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets are introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No human subjects were involved in our research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
No human subjects were involved in our research.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
36

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are only used for writing and editing purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
37


Reviews:
[{"review_id": "XD4kBRD6fr", "reviewer": "Reviewer_iicN", "summary": "The authors provide new theoretical results supporting privacy evolution", "questions": "It would be good to discuss scalability issues to high-dimensional data, or for small / large data sets.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Theoretical support for existing approaches is a positive aspect. It was difficult to see what affect the results have in practical terms, especially for high dimensional data.", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review. \n\n>`It was difficult to see what affect the results have in practical terms, especially for high dimensional data. It would be good to discuss scalability issues to high-dimensional data, or for small / large data sets.`\n\n1) We agree that our variant of PE is not directly practical in high dimensions. It has been proven that under DP constraints, any computationally efficient algorithm cannot accurately preserve all marginals [1] and $W_1$ not only preserves all marginals, it preserves all Lipschitz queries. There may be metrics that do not suffer from the curse of dimensionality, but for $W_1$ this price is inherent and not an issue specific to our proposed variant of PE.  \n\n    However, this point is counterbalanced between the large theory-practice gap in the PE literature, where the practical algorithms are very far from the sole variant for which theory exists. In this light, we narrow the gap, and we  theoretically analyze a variant of PE that is much closer to what people run in practice. \n  \n2) With regards to scalability, we believe that the theoretical insights gained from our paper could still be useful to understand other variants of PE that pose more structure. For example, the if the intrinsic dimension of the data in practice is much smaller than the ambient dimension, then our rates should only pay for the intrinsic dimension.\n\n### References:\n\n[1] Ullman, Jonathan, and Salil Vadhan. \"PCPs and the hardness of generating private synthetic data.\" Theory of Cryptography Conference."}, {"review_id": "JNmv59qZHo", "reviewer": "Reviewer_MgMH", "summary": "Private evolution (PE) is a recently developed method for generating private synthetic data from generative AI systems. PE algorithms work by generating random initial data then iteratively re-sampling them to be more similar to a private dataset while respecting differential privacy. These methods have shown promise, particularly in the text and image domains but prior to this work there has only been one work that attempts to analyze PE and give a convergence result. The authors of this work show that the previous analysis of PE depends on several limiting assumptions and that the PE algorithm they analyze is significantly different from the PE algorithms that are used in practice. This paper analyzes a version of PE that is similar to practical PE algorithms and shows and gives both a worst case convergence guarantee and a data-dependent bound in terms of Wasserstein 1 distance. This new analysis also connects to the existing PSMM method and shows how it is related to PE.", "questions": "The authors model the variation api as being a noise addition step, it is unclear how accurate of an approximation this is for what generative models do when asked to create variations of an image. What kind of conditions are necessary for the variation api to meet to make this analysis work?\n\nIs the noise scale for the variation api given in section 3 optimal under both the previous analysis and your analysis. Do you believe that practitioners should be tweaking their variation api to target a particular amount of variation?", "limitations": "I believe the authors overstate how similar their theoretical PE is to practical PE, especially w.r.t. how they represent the variation api, this should be discussed as a limitation.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is written well and does a good job of giving the main proof ideas in the main text so that readers can understand the contribution at a high level before reading the full details in the supplementary material.\n\nThe authors clearly explain the assumptions made by the previous analysis of PE and give a convincing lower bound showing that those assumptions are necessary for their proof approach.\n\nThe proof techniques developed by the authors give reasonable upper bounds with respect to a version of PE that is more similar to the PE algorithms that are used in practice.\n\nThe connection between PE and the Private Signed Measure Mechanism (PSMM) is clear and gives a useful lens for understanding PE.\n\nWeaknesses:\n\nThe authors claim that their analysis gives useful information for practitioners who are trying to utilize PE (how to select the number of rounds and number of synthetic data points). The support for this empirical claim is all with respect to simulation studies where the data are points in a ball within R2. This is very different from the domains where the mechanism is actually being used in practice (text and images) so it is unclear if the insights from their analysis will transfer to these domains.", "was_revised": true, "final_justification": "My suggestions and questions were answered by the authors, and I believe that the changes in language that the authors agreed to will improve the manuscript. I feel that my original score of 5 was and still is appropriate based on the foreseeable impact of this work.", "rebuttal": "Thank you for your review. Below we address your concerns and questions. \n\n>`The authors claim that their analysis gives useful information for practitioners who are trying to utilize PE (how to select the number of rounds and number of synthetic data points). The support for this empirical claim is all with respect to simulation studies where the data are points in a ball within R2. This is very different from the domains where the mechanism is actually being used in practice (text and images) so it is unclear if the insights from their analysis will transfer to these domains.`\n\n\nWe claimed that our theory can guide the practice of PE and illustrated this with experiments in Section 6. We were able to guide the practice of our variant of PE because we studied it carefully, but we will clarify that this does not imply that every time a variant of PE is run in practice the parameter setting should be used. We will soften the language about connections to practice: the APIs used in practical PE variants are much harder to analyze theoretically, and we leave as an interesting future direction to understand the utility of PE when these are used. \n\n>`The authors model the variation api as being a noise addition step, it is unclear how accurate of an approximation this is for what generative models do when asked to create variations of an image. What kind of conditions are necessary for the variation api to meet to make this analysis work?`\n\nAdding noise at different scales can be seen as an attempt to model the different degrees of variation of the VARIATION_API. For example, the number of backward/forward steps of a diffusion model, or the amount of noise added at each step, affects the degree of similarity of the synthetic image to the original one. While one may challenge the Gaussianity assumption, the analogy to our modeling choice should at least be intuitively clear. We agree that future work could try to analyze more complex noise distributions that may be closer to the APIs used in practice, but we think our overall schema for modeling and analysis can likely still provide a blueprint for such a refined analysis. For amenable theoretical analysis, some analytically tractable approximations are required, which motivated our specific choice, which was also the choice made in the previous (impractical) PE theoretical analysis in [1]. \n\nWe will be more explicit about these observations in the paper and will add as future work to study the convergence of PE with different theoretically tractable APIs; for example, if we asume the API is a diffusion model, we could consider the variations as random variables arising from the discretization of certain diffusion processes underlying the model. \n\n>`Is the noise scale for the variation api given in section 3 optimal under both the previous analysis and your analysis`\n\nOur choice of noise scale optimally trades off two opposing terms in the proof of Lemma D.4, and it leads to an optimal rate in the leading order terms of $n,d,\\epsilon$, and in that sense is optimal. (And yes, it essentially matches the noise scale in the previous analysis, also obtained by trading off opposing terms.) \n\n\n>`Do you believe that practitioners should be tweaking their variation api to target a particular amount of variation?`\n\nOur algorithm and analysis suggest that we should not be adding noise only at a single scale but across multiple scales, and so in that sense the answer to your question would be no.\n\n\n\n>`I believe the authors overstate how similar their theoretical PE is to practical PE, especially w.r.t. how they represent the variation api, this should be discussed as a limitation.`\n\nThank you for pointing this out; we will add a paragraph on limitations of our work emphasizing that our variant of PE is not exactly the same as the one run in practice, but rather the meta-algorithm is almost the same one. Our analysis lays a foundation for future work to expand the set of APIs under which provable convergence is possible. We will also clarify these points in the introduction and abstract. \n\nReferences: \n\n[1] Lin, Zinan, et al. \"Differentially private synthetic data via foundation model apis 1: Images.\" arXiv preprint arXiv:2305.15560 (2023)."}, {"review_id": "ICvVULSdo1", "reviewer": "Reviewer_Kaym", "summary": "### Summary\n\nThis paper provides novel worst-case theoretical analysis for the Private Evolution (PE) algorithm, a promising training-free method for differentially private (DP) synthetic data generation. PE iteratively refines an initial synthetic dataset (generated independently of private data) by creating variations and privately voting for those closest to the private dataset.\n\nPrevious theoretical analyses of PE relied on highly unrealistic assumptions (e.g., every private data point is duplicated many times), making those convergence guarantees inapplicable in practice. This paper carefully analyzes these limitations, proving lower bounds that show why such assumptions are necessary for prior proofs.\n\nThe authors then propose a new theoretical variant of PE that better resembles the practical implementation. The authors prove worst-case convergence guarantees in terms of expected 1-Wasserstein distance under $(\\varepsilon, \\delta)$-DP, showing that PE's error decays as roughly $O(d(n\\varepsilon)^{-1/d})$. They also generalize parts of their analysis to Banach spaces and establish connections to the Private Signed Measure Mechanism (PSMM).\n\nThe paper includes simulations on synthetic datasets to validate and illustrate the theory, showing how PE’s convergence depends on initialization and parameter choices.\n\n---\n\n### Contributions\n\nThe main conceptual contribution is a more principled variant of PE that better resembles the practical implementation of PE and also lends itself well to worst-case theoretical analysis.\nSome experiments on synthetic datasets verify the worst-case rates.\n\nSome beyond worst-case analysis is also developed for \"well-clustered\" datasets, but it is unclear if the assumptions are realistic in practice.\n\nA connection is also made to the private signed measure mechanism (PSMM) to interpret PE as an iterative version of PSMM.\n\n---\n\n### Techniques\n\nThe authors show that the variation step of PE contracts the $W_1$ distance to the dataset in expectation while carefully controlling the error introduced in the private voting step.\nThe analysis of the variation step seems to be mostly taken from [31].\nThe private voting step uses empirical process theory, which, as the authors mention, resembles [24].\n\n---\n\n#### References\n\n[24] Y. He, R. Vershynin, and Y. Zhu. Algorithmically effective differentially private synthetic data. COLT'23\n\n [31] Z. Lin, S. Gopi, J. Kulkarni, H. Nori, and S. Yekhanin. Differentially private synthetic data via foundation model APIs 1: Images. ICLR'24", "questions": "### Main Questions\n1. How reasonable is the current definition of VARIATION_API?\n1. Is the worst-case dependence on dimension reflected in practice? It would be interesting to see if the dependence on dimension matches even on synthetic datasets. \n\n---\n\n### Minor Nitpicks\n1. The current proof of Theorem 4.1 (main theorem) might need to restrict $\\sigma$; the number of synthetic points $n_S\\propto \\sigma^{-1}$ wouldn't make sense for $\\sigma$ arbitrarily large.\n1. The domain $\\Omega$ should probably be taken to be closed and convex, otherwise the projection of the VARIATION_API does not necessarily shrink the distance from the unprojected point (Lemma D.1 Case 2)\n1. The statement of Lemma D.2 is intuitive, but its proof is notationally dense. A summary of the idea might help readers.\n1. Is the term $C$ in the statement of Lemma D.4 an absolute constant? Please state so if it is.\n1. Lemma D.4 is a nice application of chaining, but I wonder if a one-step discretization bound already suffices? Chaining usually helps to remove some log factors to achieve a sharp analysis but this doesn't seem to apply here.\n1. The proof of Lemma D.4 (Line 939) doesn't seem to go through as stated. For an arbitrary pair $f_k\\in T_k, f_{k-1}\\in T_{k-1}$, their value can vary significantly. Indeed, the current proof uses the fact that there is a fixed function $f$ that is close to both. But this is not guaranteed for all pairs. Some slightly smarter choice of $f_k, f_{k-1}$'s should still work.\n1. The $(5/\\beta)^{d/2}$ term in the integral of the proof of Corollary D.1 (Line 951) should be $(5{\\color{red}D}/\\beta)^{d/2}$.\n1. I believe Lemma D.5 can be proved via chaining and analyzing the Rademacher complexity of $\\mathcal{F}_{BL}$. Since the Gaussian complexity already upperbounds this quantity, it might make sense to briefly mention this fact to make the paper even more self-contained.", "limitations": "The authors claim that the only difference from practical PE is the projection in bounded Lipschitz distance. However, it is unclear if the current definition of VARIATION_API is a realistic model of the foundation model APIs applied in practice.\n\nTo be clear, I believe this work is a solid theoretical contribution.\nHowever, it is presented as an attempt to bridge theory and practice and thus merits a discussion of this issue.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. The main strength is a careful, rigorous analysis of PE’s convergence with more realistic assumptions.\nThis is important as PE is popular and seems to be quite practical.\n\n1. The exposition is clear, and the proof overview in the main body is very intuitive. The proofs included in the appendix are also well-structured and include a nice application of chaining.\n\n---\n\n### Weaknesses\n\n1. While the paper makes progress towards bridging theory and practice of PE, a major assumption that was not discussed at all is the theoretical formulation of the variation step, which is defined as taking random spherical Gaussian steps from the current synthetic data point, with variance chosen at different scales. While it may be very difficult to theoretically model the variation step of the actual PE implementation, as it relies on calling foundation model APIs, a paper that attempts to eliminate unrealistic assumptions should at least discuss this definition.\n\n1. While the algorithmic variation is interesting, the analysis mainly consists of (cleverly) bringing together existing techniques.\n\n1. The experiments do not vary the dimension and are performed in $\\mathbb{R}^2$. This cannot confirm how accurate the theoretical predictions are for higher dimensional settings, which is the main regime of interest these days.\n\n1. There are some small inconsistencies in the proofs within the appendix which should be easily addressable; I include the ones I found in the Questions section.", "was_revised": true, "final_justification": "The authors committed to providing a clearer framing of their theoretical contributions with respect to the practical implications. This addressed my main concern, and I maintain my score.", "rebuttal": "Thank you for your detailed review and constructive comments. Below we address your concerns and questions.\n\n>`How reasonable is the current definition of VARIATION_API? It is unclear if the current definition of VARIATION_API is a realistic model of the foundation model APIs applied in practice.`\n\nWe believe that our definition of VARIATION_API is reasonable. Adding noise at different scales can be seen as an attempt to model the different degrees of variation of the VARIATION_API. For example, the number of backward/forward steps of a diffusion model, or the amount of noise added at each step, affects the degree of similarity of the synthetic image to the original one. While one may challenge the Gaussianity assumption, the analogy to our modeling choice should at least be intuitively clear. We agree that future work could try to analyze more complex noise distributions that may be closer to the APIs used in practice, but we think our overall schema for modeling and analysis can likely still provide a blueprint for such a refined analysis. For amenable theoretical analysis, some analytically tractable approximations are required, which motivated our specific choice, which was also the choice made in the previous PE theoretical analysis in [1]. We will add this as a limitation of our work, and remark that while we took an important first step towards bridging theory and practice of PE, there is still room for improvement in the modeling of the APIs.   \n\n>`Is the worst-case dependence on dimension reflected in practice? It would be interesting to see if the dependence on dimension matches even on synthetic datasets.`\n\nIn synthetic experiments, we previously varied dimension $d$ from 1 to 10 and observed that error grows with the dimension when fixing the rest of the parameters. We will add these results to the Appendix. \n\n>`Minor Nitpicks`\n\nThanks for catching these! \n\n(1) We will restrict $n_s$ to be the maximum between the current definition and 1, which should lead to $W_1$ error of $\\min\\{dD\\sigma^{1/d}, D\\}$ in the main theorem. (2) We consider a domain that is compact and convex. (3) We'll add an explanation of Lemma D.2. (4) We will say $C$ is an absolute constant in Lemma D.4. (5) We believe one-step discretization loses poly(n) factors as compared to chaining. (6) The supremum will be taken appropriately; the argument still goes through. (7) The term $D$ that was missing has been corrected. (8) We will carefully verify the reviewer's claim and definitively add it to the paper if correct. \n\n[1] Lin, Zinan, et al. \"Differentially private synthetic data via foundation model apis 1: Images.\" arXiv preprint arXiv:2305.15560 (2023)."}, {"review_id": "hjrP5x9NuV", "reviewer": "Reviewer_SoiT", "summary": "Private Evolution (PE) is a synthetic data generation process that has shown some promising empirical results. A recent paper ([31] in the submission) gave convergence guarantees for a variant of PE, but this paper argues that the assumptions in [31] are quite unrealistic. Without those assumptions, the original method offers weak privacy guarantees. The current submission proposes a different (still not exactly the same as practical) variant of PE and proves worst-case convergence bounds for it.", "questions": "I’m a little confused about the implication of Lemma 3.1. There is no qualifier on $\\mathcal{A}$. Does this mean the lower bound applies to *any* algorithm $\\mathcal{A}$? If so, why doesn’t it apply to your algorithm? Or maybe you meant $\\mathcal{A}$ refers specifically to Algorithm 1?\n\nAlso, just a minor formatting thing, but in Algorithm 1, the line $S_0 \\gets \\mathrm{Random} \\\\_ \\mathrm{API}(n)$ is highlighted in blue, while the same step in Algorithm 2 isn’t. Was that intentional?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper does a nice job framing the problem, situating prior work, pointing out its limitations, and explaining the contribution clearly. This feels like a meaningful theoretical step toward understanding a practical method. I’m not an expert in this area, but the proof of Theorem 4.1 definitely doesn’t look routine. The sketch was helpful too: after applying some triangle inequalities, the key step becomes controlling uniform convergence over 1-Lipschitz functions under Gaussian perturbations, which his is handled using Gaussian complexity, and Wasserstein distance between a measure and its empirical version. That seems nontrivial.\n\nOn the downside, the introduction says that PE is competitive with—or even outperforms—state-of-the-art models in terms of FID and downstream task performance. But the algorithm in this paper isn’t exactly that practical version—it’s a variant. So it would’ve been useful to compare Algorithm 2 with the real-world PE.", "was_revised": true, "final_justification": "The authors have addressed my initial concerns. So, I maintain my original assessment of the work.", "rebuttal": "Thanks for your review. Below we address your questions and concerns. \n\n>` I’m a little confused about the implication of Lemma 3.1. There is no qualifier on $\\mathcal A}$. Does this mean the lower bound applies to any algorithm? If so, why doesn’t it apply to your algorithm? Or maybe you meant refers specifically to Algorithm 1?`\n\nThe implication of Lemma 1 does apply for any algorithm ${\\mathcal A}$ such that its output $\\mathcal A(S)$ is $\\eta$-close to $S$. Note that if $S$ and ${\\mathcal A}(S)$ are $\\eta$-close, then $W_1(\\mathcal A(S),S) \\leq \\eta$. While $\\eta$-closeness is sufficient to obtain a bound on the $W_1$ distance, it is not necessary. The reason our algorithm does not suffer from this lower bound is that the convergence of our variant of PE does not rely on $\\eta$-closeness arguments. \n\n>`Also, just a minor formatting thing, but in Algorithm 1, the line is highlighted in blue, while the same step in Algorithm 2 isn’t. Was that intentional?`\n\nIn algorithm 2 we have $S_0 \\leftarrow$ RANDOM\\_API(n_s) instead of $S_0 \\leftarrow$RANDOM\\_API(n). While subtle, this is a difference between our work and the previous theoretical work on PE: previously you were forced to create $n$ synthetic datapoints in order to use $\\eta$-closeness arguments, while our framework allows to vary the number of synthetic samples (see figure 3 for the effects of picking $n_s$ suboptimally). We will highlight this point.\n\n>`the algorithm in this paper isn’t exactly that practical version—it’s a variant. So it would’ve been useful to compare Algorithm 2 with the real-world PE.`\n\nThe differences between PE in practice and our variant are the $D_{BL}$ projection step and the API choice. Our variant is less practical but much more amenable to theoretical analysis. We will compare more explicitly both algorithms in the paper."}, {"review_id": "Epex8Mniuu", "reviewer": "Reviewer_gGaX", "summary": "This paper presents a new theoretical analysis of Private Evolution (PE), a training-free method for differentially private synthetic data generation. The authors identify limitations in prior work and propose a variant of PE for theoretical study (Algorithm 2) that more closely resembles the original PE. The main contribution is an upper bound on the Wasserstein distance between the synthetic data and the private data. The paper also draws an interesting connection between PE and the Private Signed Measure Mechanism (PSMM).", "questions": "1. How does Lemma 3.1 change if we relax from pure DP to approximate DP?\n2. What does \"worst-case\" refer to in the convergence guarantee?", "limitations": "No, the authors didn't discuss the limitations of this work. The authors should discuss the mismatch between the theoretical results and the empirical evidence, and what are the potential causes.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n- The theoretical analysis is sound and novel\n- The connection between PE and PSMM is interesting. It offers a new perspective on PE as an iterative method for constructing discrete support for data release.\n\n**Weaknesses**:\n- **Misleading convergence claim.**  The title \"Private Evolution Converges\" is misleading. Typically, the convergence of an iterative algorithm implies that a quality metric improves as the number of iterations $T \\to \\infty$. The analysis in this paper does not show this. Instead, the paper establishes convergence only in the limit of the dataset size $n \\to \\infty$. Furthermore, for the expected 1-Wasserstein distance to approach a small constant, $n$ must scale as $O(d^d)$, which is impossible in practice. \n- **Disconnect with empirical evidence.**  A major concern is the apparent disconnect between the paper's theoretical guarantees and the extensive empirical evidence on PE's behavior. \n  - Notably, multiple studies have documented that PE suffers from a lack of diversity or **mode collapse** (see Figs. 21 and 22 in [1] and Fig. 4 in [2]). This makes distributional convergence impossible. This critical point is not captured by the current analysis and has not been discussed in this paper.\n  - The analysis in Line 314 implies a monotonic progression of the Wasserstein distance, suggesting the optimal $T$ is either 1 or $\\infty$. This does not capture the U-shaped performance curves (e.g., Fig. 4 of [2]) where the fidelity of the synthetic data (e.g., FID) first improves and then degrades (due to overfitting to majority modes).\n- **Limited practical insights.**  The theoretical framework, while rigorous, struggles to provide new, actionable insights into PE's practical challenges. For example, the theory suggests that the optimal $T$ is 1 when the initial error is smaller than the asymptotic error term, which the authors use to explain PE's poor performance on tabular datasets. However, this explanation is not convincing, as the asymptotic error vanishes with $n$, and it is unclear why this condition would uniquely apply to tabular data.\n\nIn summary, while the paper succeeds as a theoretical exercise in deriving a bound for a variant of PE, it falls short of its goal to \"explain PE's practical behavior\". The core research question (convergence) is misaligned with PE's most pressing practical challenges, particularly mode collapse. A more interesting direction is to develop theory that explains why and when PE fails, as this would be more likely to guide the development of better algorithms for DP synthetic data generation (please cite [3] for this broad research topic).\n\n**References**\n\n[1] Lin, Zinan, et al. \"Differentially private synthetic data via foundation model apis 1: Images.\" arXiv preprint arXiv:2305.15560 (2023).\n\n[2] Hou, Charlie, et al. \"Private Federated Learning using Preference-Optimized Synthetic Data.\" arXiv preprint arXiv:2504.16438 (2025).\n\n[3] Hu, Yuzheng, et al. \"Sok: Privacy-preserving data synthesis.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.", "was_revised": true, "final_justification": "I think it is very risky to have this paper accepted, as the central message that it delivers (PE converges) is contradictory to many practical evidence on PE's underperformance. Without clarifying where the gap lies in, I am not comfortable about recommending acceptance.", "rebuttal": "Thank you for your feedback. We address your concerns below, and we will include reference [3] in the related work section of our paper. \n\n>`Misleading convergence claim.`\n\nWe agree that 'PE converges' could be interpreted as convergence as $T \\to \\infty$. This is why we clarified this point immediately in the abstract to indicate that it converges as $n\\to \\infty$, and in the main theorem we say that 'there exists a parameter setting' such that PE converges at the stated rate. In the DP literature, it is common to study convergence rates as a function of the number of samples. For example, the convergence rates of iterative algorithms for DP stochastic optimization are usually a function of the number of samples, ambient dimension and privacy and problem parameters, but usually they fix a nontrivial number of iterations in these methods that achieves optimal trade-offs between privacy and accuracy (e.g., SGD and Stochastic Frank-Wolfe variants in [6,7]); this is similar to what we do in our work. We will clarify this point in the paper. \n\n>`for the expected 1-Wasserstein distance to approach a small constant, $n$ must scale as $O(d^d), which is impossible in practice.`\n\nIt has been proven that under DP constraints, any computationally efficient algorithm cannot accurately preserve all marginals [4] and W_1 not only preserves all marginals, it preserves all Lipschitz queries. There may be metrics that do not suffer from the curse of dimensionality, but for W_1 this price is inherent and not an issue specific to our proposed variant of PE. Further, $d$ could actually be the intrinsic dimensionality of the data (e.g. if the data lies on a low-dimensional manifold, the RANDOM_API and VARIATION_API may generate data only on that manifold). We will clarify these points in the paper. \n\nTo improve the sample complexity, an interesting future direction would be to exploit more structure of specific PE instances. We proposed an analysis beyond the worst-case for very clustered data, but there are many other structural properties that one can exploit to improve the analysis, such as prior knowledge on the data and properties of the APIs. \n\n>`Disconnect with empirical evidence. (...) multiple studies have documented that PE suffers from a lack of diversity or mode collapse (see Figs. 21 and 22 in [1] and Fig. 4 in [2]). This makes distributional convergence impossible. This critical point is not captured by the current analysis and has not been discussed in this paper.`\n\nThis is a good point; actually, our paper shows that the mode collapse problem is not inherent to PE; rather, one can get *distributional* convergence in terms of W_1 with sufficient samples (and our choice of APIs). In practice, mode collapse could arise from several sources that reduce diversity, such as low-quality APIs or insufficient private data. In fact, under privacy constraints we should not expect a DP algorithm to capture small clusters of datapoints; this may manifest as dropped modes. Supporting this view, in the references that you mention, the authors acknowledge that mode collapse can be reduced by improving diversity of the generated data, e.g., by running a VARIATION_API as a postprocessing step (Appendix L in [1]).  \n\nWe have run an experiment to illustrate our point. We show that for datasets with $4$ clusters of $n/4$ datapoints in $R^2$, our variant of PE struggles to capture the 4 modes (clusters) when $n=100$, but gradually improves as $n$ grows and captures the cluster well when $n=1000$ and extremely well when $n=10000$. We will include this experiment in our paper.\n\n`The analysis in Line 314 implies a monotonic progression of the Wasserstein distance, suggesting the optimal $T$ is either $1$ or $\\infty$. This does not capture the U-shaped performance curves (e.g., Fig. 4 of [2]) where the fidelity of the synthetic data (e.g., FID) first improves and then degrades (due to overfitting to majority modes).`\n\nThe equation in line 314 does not imply that the optimal $T$ is $1$ or $\\infty$. We understand the confusion and will make the following more clear in the paper: the error term 'err' scales polynomially with the noise $\\sigma$, which by composition of DP scales at least as $\\sqrt{T}$. Hence, we do recover a U-shaped graph when plotting the error in $W_1$ as a function of $T$, as shown in Figure 3 of the paper. The point of our claim in line 314 is that it is possible that when the error term is large in early iterations, the optimal number of steps might be 0 or 1, as illustrated in our experiments in Section 6. In other cases the optimal number $T$ is not infinity, it is the solution to a nontrivial trade-off involving $T$ and other problem parameters (such as number of synthetic samples, privacy parameters, etc) that needs to be solved to maximize the accuracy. Finally, it is not clear to us that every time the error starts to degrade while running PE is because of overfitting to majority modes. \n\n`Limited practical insights. (...) the theory suggests that the optimal $T$ is 1 when the initial error is smaller than the asymptotic error term, which the authors use to explain PE's poor performance on tabular datasets. However, this explanation is not convincing, as the asymptotic error vanishes with $n$, and it is unclear why this condition would uniquely apply to tabular data.`\n\nAs mentioned before, the correct way of thinking of the error term is as an expression that increases polynomially with $T$, because when running PE $n$ is fixed and hence it is not relevant that the error vanishes as $n \\to \\infty$. We will emphasize this in the paper. \n\nWe believe that our explanation is feasible for the following reasons. \n\n1. The definition of accuracy in [5] aligns well with the definition of accuracy used in our work: both works define error as a maximum discrepancy over a class of queries (as opposed to other works that measure error with downstream tasks or by embedding the data and calculating FID, which is a 2-Wasserstein distance), so it makes sense that their measure of error and ours behave similarly.\n2. The findings of the authors in [5] align with our theory. Indeed, they claim that 'The observation that the workload-aware private evolution algorithm performs best with one shot data generation implies that: whatever marginal gains we get from iterating multiple times, they are outweighed by the privacy cost of composing over iterations'. This finding aligns well with our theoretical findings in the case where the error term 'err' from line 314 increases significantly after 1 iteration. \n3. Finally, we do not claim that our observation applies uniquely to tabular data; it is straightforward to find PE runs in other domains where the optimal number of PE steps is also 1.\n\n`How does Lemma 3.1 change if we relax from pure DP to approximate DP?`\n\nLetting $M$ be the $2\\eta$ packing number of $\\Omega$, the lower bound of epsilon in Lemma 3.1 changes to from $\\log((M-1)(1-\\tau)/\\tau)$ to $\\log((M-1)(1-\\tau-\\delta)/\\tau)$ for $\\delta < 1-\\tau$. This follows from including the $\\delta$ term in the equation below line 1048. We will add this to the paper. \n\n`What does \"worst-case\" refer to in the convergence guarantee?`\n\n'Worst-case' is over problem instances: for any dataset $S$ and dimension $d$, our proposed PE variant privately generates synthetic data whose empirical distribution is close to that of S with W_1 guarantees. It's not worse case over variants of PE though, we will add a remark on this. \n\n`the authors didn't discuss the limitations of this work. The authors should discuss the mismatch between the theoretical results and the empirical evidence, and what are the potential causes.`\n\nWe will make explicit the limitations of our work, and clarify that we are not claiming that that the theory and the practice of PE are completely bridged. We will also discuss the potential causes, which are related to our choice of APIs and to the fact that in practice it is possible to exploit problem-dependent structure. \n\nReferences\n  \n\n[1] Lin, Zinan, et al. \"Differentially private synthetic data via foundation model apis 1: Images.\" arXiv preprint arXiv:2305.15560 (2023).\n\n[2] Hou, Charlie, et al. \"Private Federated Learning using Preference-Optimized Synthetic Data.\" arXiv preprint arXiv:2504.16438 (2025).\n\n[3] Hu, Yuzheng, et al. \"Sok: Privacy-preserving data synthesis.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[4] Ullman, Jonathan, and Salil Vadhan. \"PCPs and the hardness of generating private synthetic data.\" Theory of Cryptography Conference.\n\n[5] M. Swanberg, R. McKenna, E. Roth, A. Cheu, and P. Kairouz. Is API access to LLMs useful for generating private synthetic tabular data? In ICLR Workshop: Will Synthetic Data Finally Solve the Data Access Problem?, 2025.\n\n[6] Bassily, Raef, et al. \"Private stochastic convex optimization with optimal rates.\" Advances in neural information processing systems 32 (2019).\n\n[7] Bassily, Raef, Cristóbal Guzmán, and Anupama Nandi. \"Non-euclidean differentially private stochastic convex optimization.\" Conference on Learning Theory (2021)."}]

Author rebuttal:

Meta-review: Private evolution (PE) is a recently proposed method that generates private synthetic data from generative AI systems by iteratively refining an initial synthetic dataset by creating variations and privately voting for those closest to the private dataset. The authors of this work show that the previous analysis of PE depends on several limiting assumptions, which are often not reflected in practice. This paper analyzes a version of PE that is similar to practical PE algorithms and shows a worst case convergence guarantee for the Wasserstein distance given the number of samples. 

Due to the high variance in the reviewer feedback, this paper received substantial deliberation in both the Reviewer-AC and the AC-SAC discussion phases. Although there were concerns about the practical performance of private evolution in specific domains, reviewers ultimately agreed that theoretical groundwork is valuable, even before the technology is fully mature.

Additionally, reviewers expressed concerns that this paper proves convergence in terms of the number of samples $n$, whereas the previous paper proves convergence in terms of the number of iterations $T$ (though there is also a somewhat implicit dependency on $n$). Thus, there is a mismatch between the convergence guarantees, which compromises the paper's main goal of filling gaps in previous literature. On the other hand, if the convergence guarantees are viewed strictly in terms of sample complexity and learning theory, then the results are meaningful in light of existing lower bounds for Wasserstein distance that are exponential in $d$. 

Action item: Clarify the context of the convergence guarantees with respect to sample complexity and the corresponding implications for the number of iterations, if relevant.
Decision: Accept (poster)