PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Private Evolution as Learning-Augmented Clustering

Audra McMillan, Kunal Talwar, Felix Zhou

arXiv:2609.36678v1cs.LGcs.CRstat.ML

TL;DR

Worst-case Wasserstein analyses can require sample complexity exponential in dimension, while PE performs better in practice. This paper analyzes PE using assumptions about its generator and proposes geometry-aware GAPE; under stated cluster conditions it has provable coverage guarantees, while standard variants can fail on clustered data.

  • Problem

    Worst-case Wasserstein-learning bounds can be exponential in dimension, and the analysis does not capture how a generator may help PE.

    Source: §1 · p. 2

  • Method

    The paper analyzes PE as learning-augmented Wasserstein learning and proposes GAPE, which modifies selection to account for geometry.

    Source: §1 · p. 3

  • Results

    Under the stated reachability and cluster-separation conditions, GAPE achieves O(λr) coverage error with high probability, while ranking or subsampling PE can incur Ω(R) error on some instances.

    Source: §1 · p. 3

  • Takeaways & Limitations

    When the generator is compatible with the distribution and captures its low-dimensional structure, PE’s bounds can depend on intrinsic rather than ambient dimension.

    Source: §1 · p. 2

    Extension of the results to low-dimensional, low-curvature manifolds is conjectured rather than established.

    Source: §3.1 · p. 9

Abstract

from arXiv · show

Private Evolution (PE) is a differentially private algorithm for synthetic data generation. While it can be viewed as a Wasserstein learning algorithm, it performs much better in practice than worst-case Wasserstein analyses would predict. We recast PE as generative model-augmented Wasserstein learning. We show theoretically that when we take into account the use of a generative model that is able to capture something about the true distribution, then we can obtain much better performance bounds. For example, if the generator gives samples in the same low-dimensional space as the distribution, then sample complexity depends on intrinsic, not ambient, dimension. We also show that standard variants of PE can fail to converge on simple well-clustered instances, and propose a new geometry-aware version of PE with provable convergence on such instances. Experimentally, we show that our new algorithm is competitive with standard baselines and can improve recall.

1 Introduction

Worst-case Wasserstein bounds can obscure how generators help Private Evolution (PE), while standard PE variants can also fail on simple clustered data. The paper analyzes generator-augmented learning and introduces GAPE, a geometry-aware variant with guarantees on well-separated clusters and competitive empirical performance.

1 Introduction

  • Private synthetic datasets can be reused for queries, evaluation, and training without repeated privacy-budget use.The introduction also notes they can avoid computational and complexity overheads of differentially private algorithms for the same tasks.Source: §1 · p. 1
  • Generator-augmented analysis gives PE bounds that depend on intrinsic rather than ambient dimension, unlike private Wasserstein learning without a compatible generator.The analysis still has an n^-1/k rate, and the paper notes this can be slow for moderately large intrinsic dimension k.Source: §1 · pp. 2–3
  • Standard PE variants can badly fail on well-separated clustered data; the paper identifies selection as a cause and proposes GAPE’s geometry-aware selection step.Random and rank-based selection can miss a constant fraction of clusters.Source: §1 · p. 3
  • Under the stated reachability and cluster-separation conditions, GAPE achieves O(λr) coverage error with high probability, while PE with ranking or subsampling can incur Ω(R) error.The theorem also gives GAPE a differential privacy guarantee; the failure result applies to some clustered instances.Source: §1 · p. 3
  • The paper frames its improved PE analysis as learning-augmented Wasserstein learning that accounts for properties of the foundation-model generator.Generator usefulness depends on compatibility with the distribution being learned.Source: §1 · pp. 2–3
  • On text datasets, GAPE is competitive with existing PE variants and improves recall in several settings.The reported comparison says its performance depends on dataset, metric, and privacy budget.Source: §1 · pp. 3–4

2 Preliminaries

The preliminaries describe PE as an iterative process that uses generative APIs and private-data feedback to improve synthetic data. Its framework generates variations, forms a noisy nearest-neighbor histogram, and selects candidates for the next iteration.

2.1 Private Evolution Framework

  • PE assumes a RandomAPI for unconditional samples and a VariationAPI for data-conditioned variations, then iteratively improves a synthetic dataset over T rounds.At each round, the VariationAPI generates candidate variations from the current synthetic data.Source: §2.1 · p. 4
  • Each private data point votes for its nearest synthetic candidate, forming a histogram to which Gaussian noise is added for differential privacy.A selection mechanism chooses the next synthetic dataset from the noisy histogram.Source: §2.1 · p. 4
  • The analyzed PE instantiation uses bounded-Lipschitz projection and subsampling for selection.The paper assumes Euclidean distance in an embedding space for its nearest-neighbor computation.Source: §2.1 · pp. 4–5

3 VariationAPI with Low Effective Rank & Doubling Dimension

The section analyzes Private Evolution using intrinsic properties of the VariationAPI, yielding Wasserstein bounds independent of ambient dimension under stated assumptions. It also explains how reachability supports progress and outlines the proof’s contraction, privacy-noise, and subsampling terms.

3 VariationAPI with Low Effective Rank & Doubling Dimension

  • The analysis assumes a low-doubling-dimension domain and reachability, which ensures VariationAPI can produce variants directed toward private data.Reachability is framed through effective rank and anticoncentration; the section says it is required for PE to progress at each iteration.Source: §3 · pp. 7–8
  • When reachability fails, PE can stall because variants closer in geodesic distance may be farther under its Euclidean selection metric.In the example, PE retains its current point and makes no progress.Source: §3 · p. 8

3.1 Main Theorem

  • The Wasserstein bound depends on intrinsic dimension k and effective rank λ, not ambient dimension d, improving on worst-case n^-1/d scaling.The bound still scales as n^-1/k.Source: §3.1 · p. 9

3.2 Proof Outline

  • The proof outline bounds iteration contraction using effective rank, then controls Gaussian-noise distortion and subsampling error through chaining.The subsampling contribution is bounded by C ≤ Õ(m^-1/k), where k is the domain’s doubling dimension.Source: §3.2 · p. 10

4 Candidate-Selection via Clustering

GAPE replaces count-only candidate selection with geometry-aware local search to address failures of ranking and subsampling on well-separated clusters. On PubMed and Reddit, it is competitive with AugPE and has higher recall for large ε.

4 Candidate-Selection via Clustering

  • Ranking and subsampling can miss a cluster after its votes are diluted, and the cluster may never return if variations cannot move between clusters.In the example, a 70% majority cluster and a 30% minority cluster are used to generate three synthetic points.Source: §4 · p. 11
  • For well-separated clusters, a warm start, reachability, and minimum cluster-size conditions yield a 1−β guarantee after T GAPE iterations.The theorem applies under the stated well-clustered and VariationAPI assumptions.Source: §4 · pp. 11–12
  • GAPE filters candidates by noisy-vote threshold, then uses cost-decreasing local-search swaps to select a geometry-aware representative set.Its objective resembles k-median and uses distances truncated at R/3.Source: §4 · pp. 12–13

4.1 Experiments

  • On PubMed and Reddit, GAPE is competitive with AugPE in W1 distance and recall, and has higher recall for large ε; SubsamplePE has the worst recall.Figures 2 and 3 show the Sinkhorn W1 distance and recall comparisons.Source: Figure 2 · p. 15, Figure 3 · p. 15, §4.1 · p. 15

D Intrinsic Dimensionality

The authors estimate the intrinsic dimension of text variations by examining embedding differences generated by language models. In the reported examples, that dimension remains much smaller than the 768-dimensional embedding space.

D Intrinsic Dimensionality

  • For GPT-2 variations on PubMed, intrinsic dimension grows with temperature but remains an order of magnitude below the 768-dimensional embedding space, reaching about 20 even at higher temperatures.The estimate uses the number of singular values needed to explain the variance of embedding differences.Source: D Intrinsic Dimensionality · pp. 24–25
  • Figure 5 plots singular-value decay for 3,000 embedding-difference vectors from one PubMed entry, with temperature-specific curves distinguished using a log-scaled x-axis.Source: D Intrinsic Dimensionality · p. 25, Figure 5 · p. 26
  • For Mistral-7B-Instruct-v0.2, intrinsic dimension ranges from 10 to 21, and for Llama-3.2-1B it ranges from 4 to 32, versus 768 ambient dimensions for each.Both ranges are reported for temperatures from 0.6 to 1.4.Source: D Intrinsic Dimensionality · p. 26

E Proof of Theorem 3.4

Theorem 3.4 is stated for a low-doubling-dimensional domain and requires VariationAPI compatibility at each iteration. A simple example illustrates that without such compatibility PE may fail to converge.

E Proof of Theorem 3.4

  • Theorem 3.4 assumes a domain of diameter 1 and doubling dimension at most k, plus reachability and effective-rank conditions for each data point outside the synthetic set.Source: E Proof of Theorem 3.4 · p. 26
  • In the example, γ=0 makes the generator vary only along the first coordinate, so no finite effective rank suffices and PE cannot converge to the data point.Source: E Proof of Theorem 3.4 · p. 27
  • For γ>0, the generator has variance s2γ/(1+γ) in the second coordinate, while its effective rank scales as Θ(1/γ), reflecting slower convergence when that variance is smaller.Source: E Proof of Theorem 3.4 · p. 27

E.1 Contraction via Variations

The contraction analysis relates a single PE iteration to VariationAPI reachability and effective rank. Under the stated conditions, one iteration contracts W1 distance up to an additive error.

E.1 Contraction via Variations

  • The argument assumes a centered VariationAPI with trace covariance s2 and reachability of the target point with effective rank λ.Source: §E.1 · p. 27
  • At a suitable VariationAPI scale, a variation shrinks the distance by a factor of 1−c/(25λ) with probability at least 1/4; otherwise the distance remains unchanged.Source: §E.1 · p. 28
  • A single PE iteration contracts W1 distance by a factor of 1−γ, up to additive error α, with γ=Θ(1/λ).Source: §E.1 · p. 28

E.2 Private Histogram Error

This section bounds private-histogram error using bounded-Lipschitz function complexity. With bounded doubling dimension, the analysis controls that complexity through covering numbers.

E.2 Private Histogram Error

  • The section bounds error from adding privacy noise and projection using bounded-Lipschitz distance and Gaussian complexity.The bounded-Lipschitz distance extends to the signed measure formed by adding Gaussian noise to the nearest-neighbor histogram.Source: §E.2 · pp. 28–29
  • Covering-number bounds for bounded 1-Lipschitz functions provide the route to controlling their Gaussian complexity.The stated setting has a diameter-one domain with doubling dimension at most k.Source: §E.2 · pp. 29–30
  • The section combines its complexity bounds to bound the expected BL-distance between noiseless and noisy histogram distributions.The excerpt does not include the bound's full rate.Source: §E.2 · p. 30

E.3 Subsampling Error

The section controls subsampling error through Gaussian complexity, then combines the bounds to give a worst-case W1 guarantee whose dimension dependence is intrinsic to VariationAPI.

E.3 Subsampling Error

  • The subsampling error for the empirical measure is bounded above using the Gaussian complexity of FBL.The proof uses symmetrization and relates Rademacher complexity to Gaussian complexity.Source: §E.3 · pp. 30–31
  • The section reuses the FBL complexity bound to control the error from sparsifying variations.It combines this subsampling control with earlier bounds in the next subsection.Source: §E.3 · pp. 30–31, §E.4 · p. 31

E.4 Putting it Together

  • The combined worst-case W1 guarantee for private evolution depends on VariationAPI's intrinsic dimension rather than the ambient dimension.This is the stated outcome of combining the preceding bounds to prove Theorem 3.4.Source: §E.4 · p. 31

F Proof of Theorem 4.2

The proof establishes a cluster-discovery step for local search under well-clustered-data and noise conditions, then applies it iteratively from a warm start.

F Proof of Theorem 4.2

  • Under Theorem 4.2's stated assumptions, GAPE is run for T = ⌈(50λ/c) log(R/r)⌉ iterations with noise parameter σ.The assumptions include a warm start and a lower bound on every cluster's size; the excerpt does not show the theorem's final guarantee.Source: F Proof of Theorem 4.2 · p. 33

F.1 Cluster Discovery

  • If every data point votes within R/8 of its voter and cluster sizes exceed the stated threshold, local search selects at most m candidates, one within R/8 of each cluster.The lemma also assumes bounded candidate count and coordinate-wise noise at most τ.Source: §F.1 · p. 34

F.2 Putting it Together

  • Conditioned on successful generator and noise events, the proof uses the warm start and cluster-discovery lemma to preserve a nearby synthetic point for every cluster across iterations.A union bound over the 2T failure events yields the stated failure-probability control.Source: F Proof of Theorem 4.2 · p. 33, §F.2 · p. 35

G Synthetic Data Experiments

In the 2D mixture experiment, ranking and subsampling lose coverage of the smaller cluster, while the simplified GAPE variant keeps a point near each cluster, with its third point sometimes oscillating.

G Synthetic Data Experiments

  • The experiment uses 2,000 points from a two-component Gaussian mixture and runs three-point PE for 20 iterations.Each synthetic point generates two variations per iteration; selection uses ranking, subsampling, or clustering.Source: G Synthetic Data Experiments · p. 35
  • GAPE consistently selects a point near each cluster, while ranking loses the smaller cluster immediately and subsampling loses it and does not quite converge to the larger cluster.The third GAPE point may oscillate between clusters.Source: G Synthetic Data Experiments · p. 36, Figure 6 · p. 36, Figure 7 · p. 37

H Additional Experimental Details

The appendix details shared experimental settings, the precision and recall metrics, and the dataset-specific prompts used by RandomAPI and VariationAPI.

H.1 Hyperparameter Tuning

  • For PubMed, experiments use m = 2000, T = 10, and 7 variations per synthetic point per iteration; Reddit uses m = 10,000, and further GAPE tuning could improve relative performance.The initial RandomAPI calls number 2m; R is set to 10 times the maximum distance from a data point to its k-means center, using k = m.Source: §H.1 · p. 39

H.2 Precision & Recall

  • Precision checks whether synthetic points fall within data-based nearest-neighbor balls, while modified recall checks what fraction of data-based balls intersect the synthetic dataset.The authors note that their recall metric is tuned for m close to n; when m ≪ n, recall may be small and other metrics may be more appropriate.Source: §H.2 · p. 39

H.3.1 PubMed

  • For PubMed, RandomAPI prompts for a medical-research abstract, while VariationAPI rephrases source text as an abstract using a randomly selected tone.The source text replaces {sample}; tones include professional, concise, creative, and storytelling styles.Source: §H.3.1 · p. 40

H.3.2 Reddit

  • For Reddit, RandomAPI requests a 30–100-word post title, while VariationAPI rephrases text as a Reddit poster using a randomly selected tone.The listed tones include detailed, professional, and concise styles.Source: §H.3.2 · p. 40

H.4 Further Results

The appendix presents further results for PubMed and Reddit, including recall across a wider range of ε.

H.4 Further Results

  • Figure 9 covers PubMed with m = 2000.Its caption identifies the dataset and sample count, but the supplied text does not state an outcome.Source: Figure 9 · p. 41
  • Table 1 reports recall for a wider range of ε on PubMed (m = 2000) and Reddit (m = 10,000).The supplied caption does not include the table's values or establish a comparison winner.Source: Table 1 · p. 41
  • Figure 10 covers Reddit with m = 10,000.The supplied caption identifies the dataset and sample count without reporting an outcome.Source: Figure 10 · p. 42
Loading 2609.36678v1…