Private Evolution 作为学习增强型聚类算法的理解
Understanding Private Evolution as Learning-Augmented Clustering

Private Evolution (PE) 是一种差分隐私的合成数据生成算法,作者将其重新定义为生成模型增强型 Wasserstein 学习,并证明结合能捕捉真实分布的生成模型可显著提升性能界限,例如在低维空间中生成样本时复杂度取决于内在维度而非环境维度。实验表明,新提出的几何感知版本 PE 在简单聚集实例上具有可证明收敛性,且与标准基线算法相比能提高召回率。
AuthorsAudra McMillan, Kunal Talwar, Felix Zhou†**
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.
- † Yale University
- ** Work done while at Apple
Related readings and updates.
Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation…
Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation…
来源: Apple Machine Learning Research · machinelearning.apple.com