近似差分隐私与高斯机制原文课程: Lecture 5 — Approximate Differential Privacy (Gautam Kamath, CS 860, Fall 2020)上一讲中我们学习了纯差分隐私ε-DP和拉普拉斯机制。纯 DP 有一个严格的要求隐私损失随机变量的绝对值必须以概率 1 被 ε 界住。这在很多场景下过于严格了导致添加的噪声过大。有没有办法稍微放宽一点从而显著提高数据的可用性答案是近似差分隐私。1. 从纯 DP 到近似 DP纯 DP 的严格性回忆一下纯 ε-DP 的定义对于所有相邻数据集 X 和 X’以及所有输出集合 TPr[M(X) ∈ T] ≤ e^ε · Pr[M(X’) ∈ T]这意味着无论输出什么两个数据集产生这个输出的概率比都必须被 e^ε 界住。但如果我们允许一个很小的概率 δ让这个比率失控呢这就是近似差分隐私的思路。(ε, δ)-差分隐私近似 DP ((ε,δ)-DP)「PrM(X)t ≤ e^ε · PrM(X)t δ对绝大多数输出成立δ: 允许隐私失败的概率纯 DP (ε-DP)「PrM(X)t ≤ e^ε · PrM(X)t对所有输出 t 都成立正式定义算法 M 是 (ε, δ)-差分隐私的如果对于所有相邻数据集 X, X’ 和所有 T ⊆ YPr[M(X) ∈ T] ≤ e^ε · Pr[M(X’) ∈ T] δ其中 δ 是一个非常小的数通常建议 δ 1/nn 为数据集大小。隐私损失变量Privacy Loss Random Variable为了理解近似 DP我们需要引入隐私损失变量的概念对于两个随机变量 Y M(X) 和 Z M(X’)隐私损失变量定义为L_(Y||Z) ln(Pr[Yt] / Pr[Zt])其中 t 服从 Y 的分布。纯 ε-DP 等价于说|L| ≤ ε 以概率 1 成立。而 (ε, δ)-DP 等价于说|L| ≤ ε 以概率至少 1 - δ|L| ε 的概率不超过 δ近似DP的隐私损失|L| ≤ ε概率≥1-δ|L| ε概率≤δ纯DP的隐私损失|L| ≤ ε概率12. 高斯机制Gaussian Mechanism既然我们放宽了隐私定义就可以使用高斯噪声代替拉普拉斯噪声。高斯分布的尾部比拉普拉斯更轻衰减更快意味着在相同的隐私参数下高斯噪声通常更小。敏感性的变化对于高斯机制我们需要的是ℓ₂-敏感性而不是 ℓ₁-敏感性Δ₂(f) max|X-X’| ‖f(X) - f(X’)‖₂为什么是 ℓ₂ 而不是 ℓ₁因为这涉及高斯分布的尾部性质和隐私损失变量的分析。高斯机制的定义对于函数 f: Xⁿ → ℝᵏ高斯机制输出M(X) f(X) (Y₁, …, Yₖ)其中 Yᵢ 是独立同分布的高斯随机变量 N(0, σ²)且 σ ≥ Δ₂(f) · √(2 ln(1.25/δ)) / ε拉普拉斯 vs 高斯的对比特性拉普拉斯机制高斯机制满足的定义ε-DP纯(ε,δ)-DP近似使用敏感性ℓ₁-敏感性ℓ₂-敏感性噪声分布Laplace(b)Gaussian(0,σ²)单变量噪声规模O(Δ₁/ε)O(Δ₂·√ln(1/δ)/ε)多变量维度 d误差 O(d^(3/2))误差 O(d)关键洞察: 在高维情况下高斯机制的误差可以小一个 d^(1/2) 因子这在高维数据分析中是巨大的优势。纯DP ε-DP近似DP (ε,δ)-DP需要发布的统计量需要纯DP还是近似DP?使用拉普拉斯机制使用高斯机制添加 Lap(Δ₁/ε) 噪声添加 N(0, σ²) 噪声σ Δ₂√(2ln(1.25/δ))/ε3. 用代码理解高斯 vs 拉普拉斯下面是 Python 实现直观对比两种机制的噪声行为importnumpyasnpimportmatplotlib.pyplotaspltdeflaplace_mechanism(value,sensitivity,epsilon):拉普拉斯机制添加 Lap(Δ/ε) 噪声scalesensitivity/epsilon noisenp.random.laplace(0,scale)returnvaluenoisedefgaussian_mechanism(value,sensitivity,epsilon,delta):高斯机制添加 N(0, σ²) 噪声σΔ·√(2ln(1.25/δ))/εsigmasensitivity*np.sqrt(2*np.log(1.25/delta))/epsilon noisenp.random.normal(0,sigma)returnvaluenoise# 实验1: 单变量均值估计 np.random.seed(42)n,d1000,1# 1000个样本1维数据true_mean0.5datanp.random.rand(n)# Xi ∈ [0,1]# 敏感性分析sensitivity_l11.0/n# ℓ₁-敏感性sensitivity_l21.0/n# ℓ₂-敏感性一维时相同epsilon,delta1.0,1e-5laplace_estlaplace_mechanism(true_mean,sensitivity_l1,epsilon)gaussian_estgaussian_mechanism(true_mean,sensitivity_l2,epsilon,delta)print(f真实均值:{true_mean:.4f})print(f拉普拉斯估计:{laplace_est:.4f}(误差:{abs(laplace_est-true_mean):.4f}))print(f高斯估计:{gaussian_est:.4f}(误差:{abs(gaussian_est-true_mean):.4f}))# 实验2: 高维数据中拉普拉斯 vs 高斯的噪声放大 print(\n--- 高维场景 (d100) ---)d100true_vectornp.random.rand(d)sensitivity_l1_highd/n# ℓ₁-敏感性 d/n最坏情况sensitivity_l2_highnp.sqrt(d)/n# ℓ₂-敏感性 √d/nlaplace_noise_scalesensitivity_l1_high/epsilon gaussian_sigmasensitivity_l2_high*np.sqrt(2*np.log(1.25/delta))/epsilonprint(f拉普拉斯每维噪声尺度 {laplace_noise_scale:.6f})print(f高斯 每维噪声标准差 {gaussian_sigma:.6f})print(f比值拉普拉斯/高斯:{laplace_noise_scale/gaussian_sigma:.1f}倍)print(f→ 高斯噪声在高维时远小于拉普拉斯)# 实验3: 隐私损失变量分析 print(\n--- 隐私损失变量分布 ---)defprivacy_loss(epsilon,delta,trials100000):模拟高斯机制的隐私损失losses[]for_inrange(trials):noisenp.random.normal(0,1)lossepsilon*noise-epsilon**2/2# 简化版本losses.append(loss)lossesnp.array(losses)exceed_probnp.mean(np.abs(losses)epsilon)returnexceed_prob exceed_probprivacy_loss(epsilon,delta)print(fε{epsilon}, 隐私损失超过ε的概率 ≈{exceed_prob:.6f})print(f理论上界 δ {delta})这段代码直观展示了两个关键结论①高维场景下高斯机制噪声远小于拉普拉斯②隐私损失超过 ε 的概率被 δ 严格控制。4. 一个具体的数值例子假设你想发布一个 100 维向量的均值每个维度取值范围 [0,1]。机制ℓ₁-敏感性ℓ₂-敏感性每维噪声规模拉普拉斯纯 DP100/n—O(100/εn)高斯近似 DP—√100/n 10/nO(10·√ln(1/δ)/εn)高斯机制的噪声大约是拉普拉斯的1/10忽略 ln(1/δ) 因子4. 为什么 δ 需要非常小δ 不能任意大。它的合理取值范围取决于数据集大小 nδ 的大小含义是否可接受δ 1/n²隐私失败概率 ≤ 1/n²✅ 很好δ 1/n平均每条记录有一次额外暴露⚠️ 边界δ 1/n可能系统性地泄露某些记录❌ 不可接受δ 0退化为纯 DP✅ 但噪声更大直觉上δ 表示算法完全失败隐私完全崩溃的概率。如果 δ 太大理论上可以通过运行算法多次来完全恢复某条记录的数据。5. 理解隐私损失变量为了更精确地理解近似 DP我们用隐私损失变量的尾部来思考假设我们运行高斯机制查询 1000 维向量的均值。对大多数输出结果隐私损失 |L| ≈ O(ε)高概率情况下单条记录改变不会导致输出发生显著变化但存在一个极小概率≤ δ输出落在尾部此时隐私损失可能非常大。这个概率必须小到可以忽略这正是 δ 的作用。隐私损失变量的分布中心区域|L| ≤ ε占概率 ≥ 1-δ尾部区域|L| ε占概率 ≤ δ6. 近似 DP 的组合近似 DP 的组合性质与纯 DP 类似但需要注意 δ 的累积若 M₁, …, Mₖ 分别是 (ε₁, δ₁)-DP, …, (εₖ, δₖ)-DP 的算法则它们的组合满足(∑εᵢ, ∑δᵢ)-DP这意味着 δ 也会线性叠加——这也是为什么每个算法的 δ 必须设得非常小的原因之一。小结概念要点(ε,δ)-DP允许以极小概率 δ 违反隐私保障隐私损失变量衡量两个相邻数据集输出的分布差异高斯机制使用高斯噪声依赖 ℓ₂-敏感性δ 的选择通常 δ ≪ 1/n与纯 DP 的取舍近似 DP 噪声更小但稍微弱化了隐私保障近似差分隐私是整个差分隐私领域的主力军——绝大多数实际部署如 DP-SGD、苹果的差分隐私系统使用的都是近似 DP因为它在可用性和隐私性之间取得了更好的平衡。下一讲我们将学习高级组合定理——如何用近似 DP 在一次分析中回答成千上万个查询而隐私预算只按 √k 增长而不是线性增长。下一篇: 高级组合定理提高隐私预算利用率
近似差分隐私与高斯机制原文课程: Lecture 5 — Approximate Differential Privacy (Gautam Kamath, CS 860, Fall 2020)上一讲中我们学习了纯差分隐私ε-DP和拉普拉斯机制。纯 DP 有一个严格的要求隐私损失随机变量的绝对值必须以概率 1 被 ε 界住。这在很多场景下过于严格了导致添加的噪声过大。有没有办法稍微放宽一点从而显著提高数据的可用性答案是近似差分隐私。1. 从纯 DP 到近似 DP纯 DP 的严格性回忆一下纯 ε-DP 的定义对于所有相邻数据集 X 和 X’以及所有输出集合 TPr[M(X) ∈ T] ≤ e^ε · Pr[M(X’) ∈ T]这意味着无论输出什么两个数据集产生这个输出的概率比都必须被 e^ε 界住。但如果我们允许一个很小的概率 δ让这个比率失控呢这就是近似差分隐私的思路。(ε, δ)-差分隐私近似 DP ((ε,δ)-DP)「PrM(X)t ≤ e^ε · PrM(X)t δ对绝大多数输出成立δ: 允许隐私失败的概率纯 DP (ε-DP)「PrM(X)t ≤ e^ε · PrM(X)t对所有输出 t 都成立正式定义算法 M 是 (ε, δ)-差分隐私的如果对于所有相邻数据集 X, X’ 和所有 T ⊆ YPr[M(X) ∈ T] ≤ e^ε · Pr[M(X’) ∈ T] δ其中 δ 是一个非常小的数通常建议 δ 1/nn 为数据集大小。隐私损失变量Privacy Loss Random Variable为了理解近似 DP我们需要引入隐私损失变量的概念对于两个随机变量 Y M(X) 和 Z M(X’)隐私损失变量定义为L_(Y||Z) ln(Pr[Yt] / Pr[Zt])其中 t 服从 Y 的分布。纯 ε-DP 等价于说|L| ≤ ε 以概率 1 成立。而 (ε, δ)-DP 等价于说|L| ≤ ε 以概率至少 1 - δ|L| ε 的概率不超过 δ近似DP的隐私损失|L| ≤ ε概率≥1-δ|L| ε概率≤δ纯DP的隐私损失|L| ≤ ε概率12. 高斯机制Gaussian Mechanism既然我们放宽了隐私定义就可以使用高斯噪声代替拉普拉斯噪声。高斯分布的尾部比拉普拉斯更轻衰减更快意味着在相同的隐私参数下高斯噪声通常更小。敏感性的变化对于高斯机制我们需要的是ℓ₂-敏感性而不是 ℓ₁-敏感性Δ₂(f) max|X-X’| ‖f(X) - f(X’)‖₂为什么是 ℓ₂ 而不是 ℓ₁因为这涉及高斯分布的尾部性质和隐私损失变量的分析。高斯机制的定义对于函数 f: Xⁿ → ℝᵏ高斯机制输出M(X) f(X) (Y₁, …, Yₖ)其中 Yᵢ 是独立同分布的高斯随机变量 N(0, σ²)且 σ ≥ Δ₂(f) · √(2 ln(1.25/δ)) / ε拉普拉斯 vs 高斯的对比特性拉普拉斯机制高斯机制满足的定义ε-DP纯(ε,δ)-DP近似使用敏感性ℓ₁-敏感性ℓ₂-敏感性噪声分布Laplace(b)Gaussian(0,σ²)单变量噪声规模O(Δ₁/ε)O(Δ₂·√ln(1/δ)/ε)多变量维度 d误差 O(d^(3/2))误差 O(d)关键洞察: 在高维情况下高斯机制的误差可以小一个 d^(1/2) 因子这在高维数据分析中是巨大的优势。纯DP ε-DP近似DP (ε,δ)-DP需要发布的统计量需要纯DP还是近似DP?使用拉普拉斯机制使用高斯机制添加 Lap(Δ₁/ε) 噪声添加 N(0, σ²) 噪声σ Δ₂√(2ln(1.25/δ))/ε3. 用代码理解高斯 vs 拉普拉斯下面是 Python 实现直观对比两种机制的噪声行为importnumpyasnpimportmatplotlib.pyplotaspltdeflaplace_mechanism(value,sensitivity,epsilon):拉普拉斯机制添加 Lap(Δ/ε) 噪声scalesensitivity/epsilon noisenp.random.laplace(0,scale)returnvaluenoisedefgaussian_mechanism(value,sensitivity,epsilon,delta):高斯机制添加 N(0, σ²) 噪声σΔ·√(2ln(1.25/δ))/εsigmasensitivity*np.sqrt(2*np.log(1.25/delta))/epsilon noisenp.random.normal(0,sigma)returnvaluenoise# 实验1: 单变量均值估计 np.random.seed(42)n,d1000,1# 1000个样本1维数据true_mean0.5datanp.random.rand(n)# Xi ∈ [0,1]# 敏感性分析sensitivity_l11.0/n# ℓ₁-敏感性sensitivity_l21.0/n# ℓ₂-敏感性一维时相同epsilon,delta1.0,1e-5laplace_estlaplace_mechanism(true_mean,sensitivity_l1,epsilon)gaussian_estgaussian_mechanism(true_mean,sensitivity_l2,epsilon,delta)print(f真实均值:{true_mean:.4f})print(f拉普拉斯估计:{laplace_est:.4f}(误差:{abs(laplace_est-true_mean):.4f}))print(f高斯估计:{gaussian_est:.4f}(误差:{abs(gaussian_est-true_mean):.4f}))# 实验2: 高维数据中拉普拉斯 vs 高斯的噪声放大 print(\n--- 高维场景 (d100) ---)d100true_vectornp.random.rand(d)sensitivity_l1_highd/n# ℓ₁-敏感性 d/n最坏情况sensitivity_l2_highnp.sqrt(d)/n# ℓ₂-敏感性 √d/nlaplace_noise_scalesensitivity_l1_high/epsilon gaussian_sigmasensitivity_l2_high*np.sqrt(2*np.log(1.25/delta))/epsilonprint(f拉普拉斯每维噪声尺度 {laplace_noise_scale:.6f})print(f高斯 每维噪声标准差 {gaussian_sigma:.6f})print(f比值拉普拉斯/高斯:{laplace_noise_scale/gaussian_sigma:.1f}倍)print(f→ 高斯噪声在高维时远小于拉普拉斯)# 实验3: 隐私损失变量分析 print(\n--- 隐私损失变量分布 ---)defprivacy_loss(epsilon,delta,trials100000):模拟高斯机制的隐私损失losses[]for_inrange(trials):noisenp.random.normal(0,1)lossepsilon*noise-epsilon**2/2# 简化版本losses.append(loss)lossesnp.array(losses)exceed_probnp.mean(np.abs(losses)epsilon)returnexceed_prob exceed_probprivacy_loss(epsilon,delta)print(fε{epsilon}, 隐私损失超过ε的概率 ≈{exceed_prob:.6f})print(f理论上界 δ {delta})这段代码直观展示了两个关键结论①高维场景下高斯机制噪声远小于拉普拉斯②隐私损失超过 ε 的概率被 δ 严格控制。4. 一个具体的数值例子假设你想发布一个 100 维向量的均值每个维度取值范围 [0,1]。机制ℓ₁-敏感性ℓ₂-敏感性每维噪声规模拉普拉斯纯 DP100/n—O(100/εn)高斯近似 DP—√100/n 10/nO(10·√ln(1/δ)/εn)高斯机制的噪声大约是拉普拉斯的1/10忽略 ln(1/δ) 因子4. 为什么 δ 需要非常小δ 不能任意大。它的合理取值范围取决于数据集大小 nδ 的大小含义是否可接受δ 1/n²隐私失败概率 ≤ 1/n²✅ 很好δ 1/n平均每条记录有一次额外暴露⚠️ 边界δ 1/n可能系统性地泄露某些记录❌ 不可接受δ 0退化为纯 DP✅ 但噪声更大直觉上δ 表示算法完全失败隐私完全崩溃的概率。如果 δ 太大理论上可以通过运行算法多次来完全恢复某条记录的数据。5. 理解隐私损失变量为了更精确地理解近似 DP我们用隐私损失变量的尾部来思考假设我们运行高斯机制查询 1000 维向量的均值。对大多数输出结果隐私损失 |L| ≈ O(ε)高概率情况下单条记录改变不会导致输出发生显著变化但存在一个极小概率≤ δ输出落在尾部此时隐私损失可能非常大。这个概率必须小到可以忽略这正是 δ 的作用。隐私损失变量的分布中心区域|L| ≤ ε占概率 ≥ 1-δ尾部区域|L| ε占概率 ≤ δ6. 近似 DP 的组合近似 DP 的组合性质与纯 DP 类似但需要注意 δ 的累积若 M₁, …, Mₖ 分别是 (ε₁, δ₁)-DP, …, (εₖ, δₖ)-DP 的算法则它们的组合满足(∑εᵢ, ∑δᵢ)-DP这意味着 δ 也会线性叠加——这也是为什么每个算法的 δ 必须设得非常小的原因之一。小结概念要点(ε,δ)-DP允许以极小概率 δ 违反隐私保障隐私损失变量衡量两个相邻数据集输出的分布差异高斯机制使用高斯噪声依赖 ℓ₂-敏感性δ 的选择通常 δ ≪ 1/n与纯 DP 的取舍近似 DP 噪声更小但稍微弱化了隐私保障近似差分隐私是整个差分隐私领域的主力军——绝大多数实际部署如 DP-SGD、苹果的差分隐私系统使用的都是近似 DP因为它在可用性和隐私性之间取得了更好的平衡。下一讲我们将学习高级组合定理——如何用近似 DP 在一次分析中回答成千上万个查询而隐私预算只按 √k 增长而不是线性增长。下一篇: 高级组合定理提高隐私预算利用率
)
)
