提出新理论框架，证明私有演化在高维表格式数据上可收敛。
Private Evolution Converges
- 基于凸紧域假设与高斯扰动接口，建立收敛性分析框架。
- 在高维数据下，合成数据与原数据的Wasserstein距离为O(d(nε)^(-1/d))。
- 首次将私有演化与私有符号测度机制关联，理论指导实际应用。
私有演化（Private Evolution, PE）是一种有前景的无训练差分隐私（DP）合成数据生成方法。尽管在图像和文本等领域表现良好，但在表格式数据上的表现仍不一致。现有理论分析依赖于对算法行为和敏感数据结构的不切实际假设。本文构建新的理论框架，揭示PE的实际行为并给出收敛的充分条件。对于维度为d、包含n个数据点的凸紧域敏感数据集，在合理超参数设置及使用文献[PE23]提出的高斯变体接口条件下，我们证明PE可生成满足(ε, δ)-差分隐私的合成数据集，其期望1-Wasserstein距离为˜O(d(nε)^{-1/d})，该结果在n→∞时确立了算法的最坏情况收敛性。分析还扩展至一般Banach空间。此外，我们建立了PE与私有符号测度机制之间的联系，后者此前缺乏实际应用。实验验证了理论发现的实用性。
原文摘要 · Abstract (English)
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, δ)$-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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。