Understanding Private Evolution as Learning-Augmented Clustering
Abstract
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.
Related
- Well-posedness of a stress-augmented Moore-Gibson-Thompson-type model for thermoviscoelastic evolution in a standard linear solid
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
- When to spend privacy: optimal allocation in private learning
- High-Dimensional Asymptotics and Dataset Selection for Private Transfer Learning
BibTeX
@misc{mcmillan2026understanding,
title = {{Understanding Private Evolution as Learning-Augmented Clustering}},
author = {Audra McMillan and Kunal Talwar and Felix Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36678},
eprint = {2609.36678},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36678},
}
RIS
TY - UNPB
TI - Understanding Private Evolution as Learning-Augmented Clustering
AU - Audra McMillan
AU - Kunal Talwar
AU - Felix Zhou
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36678
UR - https://arxiv.org/abs/2609.36678
AB - 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.
ER -