Understanding Private Evolution as Learning-Augmented Clustering¶

会议: NeurIPS 2026
arXiv: 2609.36678
代码: https://github.com/microsoft/DPSDA
领域: 其他
关键词: 差分隐私、私有演化、学习增强算法、几何感知候选选择、倍增维度

一句话总结¶

本文将差分隐私合成数据生成算法 Private Evolution (PE) 重构为学习增强型聚类框架，不仅证明其 Wasserstein 误差界摆脱环境维度依赖、仅取决于生成器内在维度，而且针对传统选择机制在多聚类数据上的投票稀释失效问题，提出了具备收敛理论保证的几何感知选择算法 GAPE。

研究背景与动机¶

差分隐私（Differential Privacy, DP）合成数据生成是隐私保护机器学习与数据分析的核心范式，它允许研究人员在消耗固定隐私预算后无限制复用生成数据进行下游查询、统计建模与模型训练。近年来，利用预训练基础模型（Foundation Models）生成隐私合成数据的私有演化算法（Private Evolution, PE）因其仅需通过提示词接口（RandomAPI 与 VariationAPI）与真实敏感数据交互，展现出优异的跨模态生成质量并广泛应用于集中式与联邦学习场景中。理论上，隐私合成数据生成可形式化为 Wasserstein 距离下的分布学习；然而，经典的极小极大下界分析指出，任何 $d$ 维 Wasserstein 学习算法的样本复杂度在最坏情况下必然指数级依赖于环境维度 $d$（即便嵌入维度低至 128，降低一半误差所需的样本量也会爆炸），这与 PE 在实践中展现出的高效收敛能力形成了尖锐矛盾。

深入分析 PE 的实际运行机制可以发现，算法的惊人表现高度依赖于底层基础模型 API 提供的结构化归纳偏置。然而，现有理论分析要么直接采用与数据无关的各向同性高斯假设，要么将环境嵌入空间视为黑盒最坏情形，无法解释基础模型生成流形究竟如何降低学习复杂度。更为严重的是，即便在极为良态且结构简单的数据集（如由若干分离聚类组成的数据）上，以往基于无序子抽样（Subsampling）或单纯加噪计数排序（Ranking/AugPE）的候选筛选机制也存在严重的机制缺陷：当各聚类大小不均衡或候选点分散时，由于投票稀释效应（Vote Dilution），多数类候选点会压倒性侵占筛选名额，导致算法在迭代初期就彻底丢失少数类聚类，且一旦丢失便由于局部变异无法跨越聚类鸿沟而永久不可逆。

针对上述两大致命断层，本文从超越最坏情形分析（Beyond Worst-Case Analysis）的视角重新审视 PE，将其纳入学习增强算法（Learning-Augmented Algorithms）框架。研究首先刻画了 VariationAPI 输出空间的内在倍增维度（Doubling Dimension）与面向私有数据的有效秩（Effective Rank），严格证明样本复杂度仅取决于生成器内在维度而非环境维度；随后针砭现有候选选择策略在聚类数据上的失效机理，提出了一种基于最小费用流局部搜索的几何感知选择算法 GAPE（Geometrically Aware Private Evolution），并给出了可证明的多聚类恢复理论边界。核心 idea：将私有演化形式化为利用基础模型低维先验的学习增强学习，不仅证明其收敛速率摆脱环境维度依赖，而且通过构建融合截断距离流的几何感知候选选择算法 GAPE，从理论与算法两端彻底解决聚类稀释失效难题。

方法详解¶

整体框架¶

PE 算法的标准流程在每轮迭代中交替执行三项操作：首先由 VariationAPI 基于当前合成点生成候选变异集合，随后敏感数据点向最近候选点投票构建最近邻直方图并注入高斯噪声以满足差分隐私，最后通过选择机制（Selection）筛选出下一轮合成点。本文提出的 GAPE 算法保留了最近邻直方图加噪的差分隐私骨架，但对其生成尺度覆盖与候选筛选逻辑进行了关键革新：算法在多尺度几何幂次下生成多样化候选集，并在加噪直方图上施加计数阈值过滤；随后，针对过滤后的候选集合，通过求解基于截断距离的有向最小费用流局部搜索问题，选取出能够均匀覆盖不同几何聚类的 $m$ 个合成代表点。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["敏感私有数据集 D ⊆ ℝᵈ 与隐私预算 (ε, δ)"] --> B["多尺度变异与尺度逼近<br/>基于当前合成点 S⁽ᵗ⁻¹⁾ 生成 ℓ* 尺度候选集合 V⁽ᵗ⁾"]
    B --> C["高斯加噪最近邻直方图<br/>构建最近邻计数 H⁽ᵗ⁾ 并注入噪声 𝒩(0, σ²I) 保证 DP"]
    C --> D["噪声阈值过滤候选集<br/>提取高置信度候选子集 H̃_τ⁽ᵗ⁾ = {v : H̃⁽ᵗ⁾(v) > τ}"]
    D --> E["基于截断距离流的局部搜索选择<br/>求解有向流目标 LSObj 选出几何均衡代表点 S⁽ᵗ⁾"]
    E -->|未达到迭代上限 T| B
    E -->|完成 T 轮迭代| F["输出高覆盖度差分隐私合成数据集 S⁽ᵀ⁾"]

关键设计¶

1. 学习增强型低内在维度分析：摆脱环境维度灾难的理论刻画

经典 Wasserstein 学习的最坏情形下界受制于高维环境空间的体积膨胀，导致样本复杂度与 $d$ 成指数关系。本文建立学习增强框架，假定 VariationAPI 支撑在倍增维度为 $k \ll d$ 的度量流形上，并引入相对于私有数据流向的有效秩 $\lambda$ 与反集中常数 $c$ 刻画生成器与私有分布的几何兼容性（Reachability，可达性）。对于给定输入点 $y$ 与变异尺度 $s^2$，有效秩约束要求沿私有数据方向 $(x-y)$ 的一维方差至少占据总方差 $\mathrm{tr}(\mathrm{Cov}[Z])$ 的 $1/\lambda$ 比例： $$\frac{\mathrm{tr}(\mathrm{Cov}[Z]) \cdot \|x-y\|_2^2}{(x-y)^\top \mathrm{Cov}[Z] (x-y)} \leq \lambda$$ 当生成器满足可达性时，若尺度选在 $s^2 \asymp c\|x-y\|_2^2 / \lambda$，则单次变异以至少 $1/4$ 的概率使到目标数据点的距离平方收缩 $(1 - c / (25\lambda))$。结合覆盖数链式法则（Chaining），加噪直方图的投影误差由高维高斯复杂度降维收敛至 $\tilde{O}(\sigma m_V^{1 - 1/k})$，最终将 PE 的期望 Wasserstein-1 误差界由不可行的 $\tilde{O}(n^{-1/d})$ 提升至与环境维度 $d$ 完全解耦的 $\tilde{O}(\lambda^{1 + 1/(2k)} (\sqrt{\log(1/\delta)} / (\varepsilon n))^{1/k})$。

2. 几何感知候选选择机制：基于截断距离流的局部搜索

针对传统 SubsamplePE（按加噪比例重抽样）与 AugPE（按加噪计数值贪心排序）在聚类数据上必然发生的“多数类垄断、少数类灭绝”现象，本文设计了截断距离最小费用流目标函数。设截断距离函数为 $c(x, y) = \min\{\rho(x, y), R/3\}$（其中 $R$ 为已知聚类间最小间隔），候选集按加噪权重正负划分为正权重集合 $D^+$ 与负权重集合 $D^-$。对于待选取的 $m$ 个合成中心 $z = \{z_1, \dots, z_m\}$，局部搜索目标 $\mathrm{LSObj}(D, \tilde{H}, z)$ 定义为求解如下有向流优化： $$\min_{f \geq 0} \sum_{x \in D^+} \sum_{y \in D^-} c(x,y) f(x,y) + \sum_{\ell=1}^m \sum_{x \in D^+} c(x, z_\ell) f(x, z_\ell)$$ 满足约束 $\sum_{y \in D^-} f(x,y) + \sum_{\ell} f(x, z_\ell) = w_x$（对任意 $x \in D^+$）以及 $\sum_{x \in D^+} f(x,y) = -w_y$（对任意 $y \in D^-$）。该流模型巧妙之处在于：正权节点流向负权节点的边抵消了差分隐私高斯噪声带来的负值扰动，而流向合成中心的边则迫使所选候选点必须在空间几何分布上贴近所有正权稠密区域。

3. 阈值剪枝与交替置换搜索：保证跨聚类收敛的鲁棒求解

在算法求解层面，直接对全候选集做连续空间流优化在计算上难以承受。GAPE 采取两阶段策略：第一阶段设立加噪计数置信度阈值 $\tau = \sigma \sqrt{2 \log(6Tm_V/\beta)}$，仅保留满足 $\tilde{H}^{(t)}(v) > \tau$ 的候选点构成集合 $\tilde{H}_\tau^{(t)}$，从概率上彻底阻绝没有任何真实私有数据支持的“虚假变异点”被选中；第二阶段初始化任意 $m$ 个候选中心，采用 1-置换局部搜索（1-swap Local Search），在每一次循环中遍历检查是否存在将集合内点 $z$ 替换为集合外点 $x \in \tilde{H}_\tau \setminus \mathrm{solution}$ 能够严格降低 $\mathrm{LSObj}$ 成本。理论分析证明，当任意聚类的有效样本量满足 $|C_i| > 8n/m + 3m_V\tau$ 时，未覆盖聚类中候选点带来的截断距离收益必然压过剔除冗余中心带来的流重分配代价，从而迫使局部搜索终止时在每一个聚类附近均精确落盘至少一个合成候选点。

差分隐私理论分析与一致性鲁棒性保证¶

GAPE 每一轮迭代对敏感数据集 $D$ 的唯一访问入口为最近邻直方图构建 $\mathrm{NNhistogram}(D, V^{(t)}, \rho)$。敏感数据中任一单个样本的增加、修改或删除，最多使其中一个候选柱计数减 1、另一个候选柱计数加 1，因此未归一化直方图的 $\ell_2$ 敏感度严格满足 $\Delta_2 \leq \sqrt{1^2 + (-1)^2} = \sqrt{2}$。经过 $T$ 轮自适应交互释放，根据高斯机制高级组合定理，配置高斯噪声方差 $\sigma = 2\sqrt{T\log(1.25/\delta)} / \varepsilon$ 即可严格满足 $(\varepsilon, \delta)$-DP。随后的阈值过滤 $\tilde{H}_\tau$、局部搜索流求解以及代表点输出均属于无敏感数据交互的后处理（Post-processing），严格保持隐私保证不被破坏。

在聚类恢复理论保证方面，定理 4.2 证明：在数据集满足 $(r, R)$-良好聚类（簇内直径 $\leq r$，簇间距离 $\geq R \geq 400r\lambda/c$）且具备温和暖启动初始化时，经过 $T = \lceil (50\lambda/c)\log(R/r) \rceil$ 轮迭代，GAPE 输出的合成数据集与私有数据集之间的最大覆盖误差以至少 $1-\beta$ 的高概率收敛至 $O(r\lambda)$，即： $$\sup_{x \in D} \inf_{s \in S^{(T)}} \rho(x, s) \leq \frac{100r\lambda}{c} = O(r\lambda)$$ 该结论表明生成点最终能紧密逼近真实数据簇，且算法在聚类极度不平衡（最小簇仅需满足 $\tilde{\Omega}(n^{1/2}\lambda^{1/4})$ 阶）的情况下仍具备稳健的发现能力。

实验关键数据¶

主实验¶

论文在两项广泛使用的文本基准数据集上进行实验评估：包含约 7.5 万条医学论文摘要的 PubMed 数据集（生成样本数 $m=2000$）和包含约 500 万条对话的 Reddit 数据集（生成样本数 $m=10000$）。基础生成模型采用 GPT-2，语义嵌入模型采用 Sentence Transformers (sentence-t5-base，环境嵌入维度 $d=768$)。对比基线包括经典的子抽样私有演化（SubsamplePE）与排序私有演化（AugPE）。评价指标采用衡量分布差异的 Sinkhorn $W_1$ 距离以及基于数据最近邻小球交集的改进召回率（Recall）。

下表展示了在 PubMed 与 Reddit 数据集上不同隐私预算 $\varepsilon$ 下的召回率（Recall）主实验数据对比（$\delta=10^{-5}$，数值越高越优）：

数据集	算法 / 方法	$\varepsilon=0.1$	$\varepsilon=0.5$	$\varepsilon=1.0$	$\varepsilon=2.0$	$\varepsilon=4.0$	$\varepsilon=8.0$	$\varepsilon=100.0$
PubMed ($m=2000$)	SubsamplePE	0.0032	0.0062	0.0083	0.0102	0.0118	0.0124	0.0139
	AugPE	0.0040	0.0105	0.0161	0.0234	0.0288	0.0276	0.0281
	GAPE (本文)	0.0036	0.0104	0.0148	0.0211	0.0258	0.0286	0.0282
Reddit ($m=10000$)	SubsamplePE	0.0975	0.1465	0.1683	0.1982	0.2086	0.2156	0.2045
	AugPE	0.1269	0.2220	0.2734	0.3216	0.3320	0.3354	0.3107
	GAPE (本文)	0.1282	0.2312	0.2809	0.3204	0.3246	0.3241	0.3260
	Random Sample Baseline	–	–	–	–	–	–	0.1946

消融与合成实验¶

在二维高斯混合合成数据集（包含 90% 多数簇与 10% 少数簇，$n=2000, m=3$）上进行轨迹跟踪分析，对比三种选择机制对于少数簇的覆盖能力；同时在真实文本数据上实测不同温度下基础语言模型的内在维度。

实验配置 / 机制	多数簇跟踪表现	少数簇跟踪表现	最终聚类覆盖状态	实测内在维度 ($d=768$, 解释方差 $\geq 80\%$)
Ranking (AugPE)	垄断所有 3 个合成点	第 1 轮即丢失少数簇	严重失效，无法跨簇恢复	—
SubsamplePE	随机震荡逼近多数簇	迭代初期概率性丢弃	严重失效，召回率极低	—
GAPE (本文)	稳定保留 1-2 个代表点	持续锁定至少 1 个代表点	全覆盖收敛至目标聚类	—
GPT-2 (PubMed)	—	—	—	$k \approx 10 \sim 25$ (随温度 $0.6 \sim 1.4$ 上升)
Mistral-7B-v0.2	—	—	—	$k \approx 10 \sim 21$ (随温度 $0.6 \sim 1.4$ 上升)
Llama-3.2-1B	—	—	—	$k \approx 4 \sim 32$ (随温度 $0.6 \sim 1.4$ 上升)

关键发现¶

合成聚类严重失效模式的证实：在二维不平衡混合高斯模型中，标准 AugPE 由于多数类计数值绝对占优，在第 1 轮迭代中就完全舍弃了少数类的候选点；SubsamplePE 也因多项分布抽样的高方差迅速丢弃少数类。唯有 GAPE 能通过最小费用流的几何惩罚项，始终在少数类内部维持至少一个有效候选点。
高维环境下的极低内在维度证实：尽管文本嵌入空间的环境维度高达 768，但经 SVD 奇异值分解检验，常见生成模型在不同采样温度下只需 4 到 32 个主成分即可解释超过 80% 的变异方差，充分验证了理论假设中 $k \ll d$ 的合理性。
高隐私预算下真实数据的召回优势：在 Reddit 等超大规模真实文本数据集上，GAPE 在强隐私约束（$\varepsilon \in [0.1, 1.0]$）及弱隐私约束（$\varepsilon=100.0$）下均超越 AugPE，尤其是在极高隐私要求下，几何流的全局平衡作用有效抑制了单纯加噪计数排序产生的虚假高频点。

亮点与洞察¶

理论视角的重构突破：打破了过去将基础模型辅助的差分隐私生成硬套进 worst-case Wasserstein 学习下界（样本量需 $O(2^d)$）的理论僵局，首次从学习增强算法的视角切入，用倍增维度与有效秩刻画了“生成器先验如何帮助差分隐私绕过维度灾难”。
精巧的流模型目标设计：将加噪直方图的离散选择问题升华至含正负权重的有向最小费用流模型，正负权相抵消除了高斯差分隐私噪声的均值偏移，截断距离 $c(x, y)$ 则天然充当了防范远离簇外离群点的几何护栏。
算法思路的可迁移性：基于截断距离的局部搜索候选选择算子不仅适用于文本私有演化，同样可无缝迁移至差分隐私图像扩散反演、受保护群体的公平代表性采样以及流形学习增强等更广泛的约束生成任务中。

局限与展望¶

计算开销限制了候选点规模：每一轮迭代都需要运行 1-swap 局部搜索并多次计算最小费用流，在大规模候选集（如 $m_V \gg 10^4$）场景下的计算耗时明显高于简单的排序或无放回抽样。
对聚类尺度超参数的依赖：算法理论保证要求事先给定或估计聚类间隔截断距离 $R$ 和簇内半径 $r$。在实际复杂分布中，若聚类层级模糊或各簇尺度差异悬殊，$R$ 的选择可能会对几何流的敏感性产生显著影响。
流形测地距离与欧氏距离的失配：当前直方图投票依然在嵌入空间的欧氏度量下进行。如作者在图 1 路径病态示例中所指出的，当生成模型变异流形呈高弯曲特性时，欧氏最近邻易陷入局部极值，未来引入可学习的流形测地度量将是极具前景的拓展方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从学习增强聚类视角解析私有演化，提出融合流优化的几何感知选择算法并给出突破性理论分析。
实验充分度: ⭐⭐⭐⭐ 覆盖合成聚类仿真、生成模型内在维度实测以及两大真实文本基准的大量隐私预算对比。
写作质量: ⭐⭐⭐⭐⭐ 理论推导严密精炼，反例构建极具说服力，几何流直觉叙述清晰透彻。
价值: ⭐⭐⭐⭐⭐ 为差分隐私基础模型生成机制奠定了坚实的理论基石，对后续设计高保真、抗稀释的隐私数据生成算法具有重要指导意义。

数据集	算法 / 方法	\(\varepsilon=0.1\)	\(\varepsilon=0.5\)	\(\varepsilon=1.0\)	\(\varepsilon=2.0\)	\(\varepsilon=4.0\)	\(\varepsilon=8.0\)	\(\varepsilon=100.0\)
PubMed (\(m=2000\))	SubsamplePE	0.0032	0.0062	0.0083	0.0102	0.0118	0.0124	0.0139
	AugPE	0.0040	0.0105	0.0161	0.0234	0.0288	0.0276	0.0281
	GAPE (本文)	0.0036	0.0104	0.0148	0.0211	0.0258	0.0286	0.0282
Reddit (\(m=10000\))	SubsamplePE	0.0975	0.1465	0.1683	0.1982	0.2086	0.2156	0.2045
	AugPE	0.1269	0.2220	0.2734	0.3216	0.3320	0.3354	0.3107
	GAPE (本文)	0.1282	0.2312	0.2809	0.3204	0.3246	0.3241	0.3260
	Random Sample Baseline	–	–	–	–	–	–	0.1946