高级组合定理提高隐私预算利用率原文课程: Lecture 6 — Advanced Composition (Gautam Kamath, CS 860, Fall 2020)隐私预算就像钱包里的钱——你希望每笔查询花的钱越少越好。纯 DP 的基本组合定理告诉我们运行 k 个 ε-DP 算法整体是kε-DP。隐私预算线性增长这太奢侈了高级组合定理Advanced Composition Theorem改变了游戏规则它允许隐私预算按O(√k)增长而非 k——这是数量级上的提升。1. 基本组合 vs 高级组合假设你要回答 10,000 个查询每个查询使用 ε0.01 的隐私预算组合方式总隐私损失可用性基本组合ε_total 10,000 × 0.01 100❌ 隐私完全崩溃高级组合ε_total ≈ 0.01 × √(2×10,000×log(1/δ)) ≈1.4✅ 仍然可接受这是70 倍的差距高级组合 - O(√k)增长1个查询: ε10个查询: ~3ε100个查询: ~10ε10,000个查询: ~100ε ✅基本组合 - 线性增长1个查询: ε10个查询: 10ε100个查询: 100ε10,000个查询: 10,000ε ❌2. 高级组合定理的正式表述定理高级组合对于所有 ε, δ, δ’ 0设 M (M₁, …, Mₖ) 是一系列自适应选择的 (ε, δ)-差分隐私算法。那么整体算法满足(ε̃, δ̃)-差分隐私其中ε̃ ε·√(2k·ln(1/δ’)) k·ε·(e^ε - 1)/(e^ε 1)δ̃ kδ δ’看起来很复杂让我们拆解一下三项的含义主导项: ε·√(2k·ln(1/δ’)) —— 从 k 变为 √k 的核心当 k 很大时这一项主导δ’ 是一个调优参数——让它越大√k 前的系数就越小二阶项: k·ε·(e^ε - 1)/(e^ε 1)当 ε 很小时高隐私区(e^ε - 1)/(e^ε 1) ≈ ε/2此时二阶项 ≈ k·ε²/2 —— 对很小的 ε 可以忽略δ 累积: δ̃ kδ δ’k 个算法各自的 δ 累积δ’ 是额外的调优参数简化版本高隐私区当 ε 很小比如 ε ≤ 1且忽略常数因子时(ε̃, δ̃)-DP其中 ε̃ ≈ O(ε·√(k·log(1/δ)))3. 直观理解为什么能从 O(k) 变成 O(√k)关键直觉在于隐私损失变量的随机性。基本组合的错误假设基本组合假设最坏情况每次查询的隐私损失方向都相同每次都是坏方向。就像连续抛硬币总是正面——概率极低但基本组合保守地考虑了这种情况。高级组合的正确洞察高级组合认识到隐私损失变量是一个均值为 0 的随机变量。就像抛硬币一样大多数时候正面和反面会互相抵消。平均总隐私损失 ≈ 0中心极限定理总隐私损失 ≥ t 的概率 ≈ exp(-t²/2kε²)所以 t ≈ ε·√k 就能使这个概率很小第1次查询 隐私损失 L₁组合隐私损失第2次查询 隐私损失 L₂...第k次查询 隐私损失 Lₖ总损失 ∑Lᵢ N(0, kσ²)|总损失| ≥ ε̃ 的概率 ≤ δ4. 一个实际例子假设你要用 DP 训练一个深度学习模型每轮梯度更新SGD step使用 ε1, δ10⁻⁵。如果你训练 1,000 轮组合方式总 ε可用性评估基本组合ε_total 1,000❌ 完全不可用高级组合ε_total ≈ 1·√(2·1000·ln(1/0.01)) ≈ 30⚠️ 还可以高级组合调优到 δ’0.1更小的 ε̃✅ 实用这就是DP-SGD差分隐私随机梯度下降的核心——通过高级组合定理来摊销隐私成本使得在成千上万轮迭代后仍然保持有意义的隐私保障。5. 自适应查询 vs 非自适应查询高级组合定理的一个强大特性是支持自适应查询。查询类型含义高级组合支持非自适应所有查询事先确定✅自适应下一个查询可依赖于前面的答案✅这意味着研究者可以根据之前的结果动态选择下一个分析方向而不必提前决定所有问题——这更符合现实的数据分析流程。DP算法分析师DP算法分析师DP算法分析师DP算法分析师高级组合总隐私 不论查询如何选择查询1根据公共知识加噪回答1查询2根据回答1设计加噪回答2查询3根据回答1,2设计加噪回答36. 用代码计算高级组合隐私预算下面这个 Python 函数可以帮你计算任意场景下的总隐私预算非常适合实际部署时使用importnumpyasnpimportmathdefbasic_composition(epsilon,k):基本组合总隐私 k × ε线性returnk*epsilondefadvanced_composition(epsilon,delta,k,delta_prime1e-6): 高级组合定理总隐私预算计算 参数: epsilon: 每次查询的隐私预算 delta: 每次查询的δ k: 查询次数 delta_prime: 调优参数越小ε̃越小但δ̃略增 返回: (epsilon_total, delta_total) term1epsilon*math.sqrt(2*k*math.log(1/delta_prime))term2k*epsilon*(math.exp(epsilon)-1)/(math.exp(epsilon)1)epsilon_totalterm1term2 delta_totalk*deltadelta_primereturnepsilon_total,delta_total# 场景对比 print( 基本组合 vs 高级组合 \n)scenarios[(少量精确查询,10,0.5,1e-5),(中等规模查询,100,0.1,1e-5),(DP-SGD 100轮,100,0.1,1e-5),(DP-SGD 1000轮,1000,0.1,1e-5),(普查级大规模,10000,0.01,1e-6),]forname,k,eps,dinscenarios:basicbasic_composition(eps,k)adv_eps,adv_deltaadvanced_composition(eps,d,k)print(f场景:{name})print(f k{k}, ε{eps}, δ{d})print(f 基本组合: ε_total {basic:.2f}{❌ifbasic5else⚠️ifbasic1else✅})print(f 高级组合: ε_total {adv_eps:.2f}, δ_total {adv_delta:.2e}{❌ifadv_eps5else⚠️ifadv_eps1else✅})print()# 关键可视化增长趋势对比 print(--- k从1到10000的ε_total增长对比 ---)ks[1,10,50,100,500,1000,5000,10000]forkinks:basicbasic_composition(0.1,k)adv,_advanced_composition(0.1,1e-5,k)print(f k{k:5d}: 基本{basic:.1f}高级{adv:.2f}(比值{basic/adv:.0f}x))运行这段代码你会看到在 k10000 时基本组合的 ε1000完全不可用而高级组合仅约 9.2仍可接受差距超过100 倍。7. 与基本组合的对比总结特性基本组合高级组合增长方式O(k)O(√k)隐私定义ε-DP 或 (ε,δ)-DP(ε,δ)-DP是否支持自适应✅✅数学复杂度简单中等k10, ε0.1 的结果ε_total 1.0ε_total ≈ 0.4k100, ε0.1 的结果ε_total 10.0 ❌ε_total ≈ 1.3 ✅小结高级组合定理是差分隐私走向实用化的关键里程碑之一。它解决了基本组合中隐私预算线性增长这一致命缺陷使得在大规模查询场景如机器学习多轮训练、普查数据发布中使用差分隐私变得可行。概念要点基本组合总隐私 k × ε线性高级组合总隐私 ≈ O(√k) × ε次线性实现机制识别隐私损失变量的随机性利用抵消效应δ 调优通过 δ’ 参数控制 ε̃ 和 δ̃ 的权衡实践意义DP-SGD、普查数据发布等大规模应用的基础下一讲我们将介绍指数机制——当要输出的不是数值而是一个对象时如选择最佳价格或最佳模型参数我们该如何保护隐私下一篇: 指数机制从数值到对象的隐私保护