超越全局敏感性：更精确的噪声添加

原文课程: Lecture 10 — Beyond Global Sensitivity (Gautam Kamath, CS 860, Fall 2020)

截至目前，我们使用的所有差分隐私机制——拉普拉斯机制、高斯机制、指数机制——都有一个共同点：它们依赖**全局敏感性（Global Sensitivity）**来校准噪声。

全局敏感性确实很安全：它在所有可能的相邻数据集上取敏感性的最大值，保证了无论数据长什么样，隐私都不会泄露。但问题是——这种「安全」太昂贵了。如果你的数据集的敏感性实际上远低于全局最坏情况，你就是在为一种「几乎不会发生」的场景支付保护成本。

这一讲我们探索如何打破这种保守性。三个核心概念：局部敏感性（Local Sensitivity）、Propose-Test-Release（PTR）框架和平滑敏感性（Smooth Sensitivity）。

1. 全局敏感性的「过度保险」问题

先回顾一下

拉普拉斯机制添加的噪声量取决于查询 f 的全局敏感性：

Δf = max_{X ≈ X'} |f(X) - f(X')|

噪声大小 = Lap(Δf / ε)。关键问题在于：Δf 是取所有相邻数据集上的最大值。

一个直觉化的例子：均值查询

假设你的数据集中有 n 个人的年龄，你想查询平均年龄。均值查询的全局敏感性是多少？

Δ_mean = (max - min) / n

如果人的年龄在 0 到 120 之间且 n=1000，那么 Δ_mean = 120/1000 = 0.12。

但大多数情况下，你的数据集中所有人的年龄其实都在 20-50 岁之间。局部的敏感性远小于 0.12，但你却被迫按照 0.12 加噪声。10\% 的数据波动会被 0.12 的噪声掩盖，而实际上你的数据只需要 0.03 的噪声就足够了。

graph TB subgraph "全局敏感性视角" A1["年龄 0 到 120Δ=0.12"] --> B1["噪声: Lap(0.12/ε)保守但浪费"] end subgraph "实际数据集" A2["年龄 20 到 50实际敏感性 ≈ 0.03"] --> B2["如果可以按实际敏感性加噪声..."] end C["全局敏感性为最坏场景的2-4 倍为不可能的情况支付了不必要的隐私成本"] B1 -.-> C B2 -.-> C style A1 fill:#ffcdd2,stroke:#c62828 style A2 fill:#c8e6c9,stroke:#2e7d32 style C fill:#fff3e0,stroke:#e65100

为什么不能直接用实际敏感性？

这个问题的答案并不平凡。如果你根据当前数据集 X 的真实敏感性来决定加多少噪声，那么噪声量本身就会泄露关于数据集的信息。

试想一个极端例子：一个数据集 X 的局部敏感性是 0.01，另一个数据集 Y（只差一条记录）的局部敏感性是 100。如果攻击者看到第一个返回了很小的噪声（意味着结果很精确），第二个返回了很大的噪声（意味着结果很模糊），攻击者就知道数据集更接近 X 还是 Y——这本身就是一个隐私泄露！

2. 局部敏感性（Local Sensitivity）

定义

局部敏感性只关注当前数据集 X 周围的敏感性，而非所有可能的数据集：

定义：对于查询 f 和数据集 X，f 在 X 处的局部敏感性（Local Sensitivity）为：

LS_f(X) = max_{X': X 和 X' 是相邻数据集} |f(X) - f(X')|

对比全局敏感性：

主线案例：最近两点距离

让我们用一个贯穿全文的经典例子来理解。考虑以下查询：

查询 f：给定一组点坐标，找出最近两点之间的距离。

graph LR subgraph "数据集 A (局部敏感性小)" A1["• (0, 0)"] A2["• (1, 0)"] A3["• (0, 1)"] A4["• (1, 1)"] end subgraph "数据集 B (局部敏感性大)" B1["• (0, 0)"] B2["• (0, 0)"] B3["• (0, 0)"] B4["• (10, 10) ← 离群点"] end A5["最近距离 = 1加一个点 Δ≈1局部敏感性 ≈ 1"] B5["最近距离 = ~14.14加一个点 Δ=~4.14局部敏感性 ≈ 14.14"] A1 --> A5 B1 --> B5 style A5 fill:#e8f5e9,stroke:#2e7d32 style B5 fill:#ffcdd2,stroke:#c62828

在数据集 A 中，所有点均匀分布在单位正方形内，最近两点距离约 1。添加或删除一个点，最近距离的变化很小，局部敏感性大约为 1。

在数据集 B 中，三个点重叠在原点，一个点在 (10, 10)。最近两点距离约 14.14。但如果删掉 (10, 10)，剩下的三点距离为 0——局部敏感性大约为 14.14！

同样的查询，不同的数据集，局部敏感性可以相差 14 倍之多。

下面我们用 Python 代码直观地展示这个差异：

import numpy as np # === 局部敏感性 vs 全局敏感性：最近两点距离 === np.random.seed(42) def nearest_distance(points): """计算点集中最近两点之间的欧几里得距离""" min_dist = float('inf') for i in range(len(points)): for j in range(i + 1, len(points)): dist = np.linalg.norm(points[i] - points[j]) if dist < min_dist: min_dist = dist return min_dist def local_sensitivity(points): """ 计算最近两点距离查询在当前数据集上的局部敏感性。 即：删除每个点后，最近距离的最大变化量。 """ original_dist = nearest_distance(points) max_change = 0 for i in range(len(points)): reduced = np.delete(points, i, axis=0) if len(reduced) >= 2: new_dist = nearest_distance(reduced) change = abs(original_dist - new_dist) if change > max_change: max_change = change return max_change # 生成两种不同的数据集 # 数据集 A：所有点均匀分布在单位正方形内 points_A = np.random.uniform(0, 1, (20, 2)) # 数据集 B：大部分点在原点附近，一个离群点 points_B = np.vstack([ np.random.normal(0, 0.01, (19, 2)), # 19个点聚集在原点附近 np.array([10.0, 10.0]) # 1个离群点 ]) print("=" * 60) print("局部敏感性 vs 全局敏感性：最近两点距离查询") print("=" * 60) print(f"\n📊 数据集 A（均匀分布）：") print(f" 最近两点距离 = {nearest_distance(points_A):.4f}") print(f" 局部敏感性 = {local_sensitivity(points_A):.4f}") print(f"\n📊 数据集 B（聚集 + 离群点）：") print(f" 最近两点距离 = {nearest_distance(points_B):.4f}") print(f" 局部敏感性 = {local_sensitivity(points_B):.4f}") print(f"\n⚠️ 全局敏感性（理论上界）≈ 无可估量（~14.14 甚至更大）") print(f" 因为最坏情况下，数据集可以构造得使最近距离从 0 跳到任意大。")

运行结果会显示，同样的查询在不同数据集上的局部敏感性可以相差数十倍——但全局敏感性对所有数据集一视同仁，取的是最坏情况下的最大值。

全局敏感性是多少？

对于「最近两点距离」这个查询，全局敏感性是多少？答案是：它可能非常大。

想象最坏情况：在一个数据集中，最近两点距离可以非常小（两个点距离趋近 0），而相邻数据集上可以非常大（这两个点中有一个被替换成非常远的点）。所以 Δ_f 理论上可以是无界的——这意味着用拉普拉斯机制根本无法处理这个查询！

但如果真实数据运行良好，局部敏感性就会很小。这正是我们想要利用的特性。

3. Propose-Test-Release（PTR）框架

既然我们不能直接使用局部敏感性（噪声量会泄露信息），那怎么办？

Propose-Test-Release（PTR）框架提供了一个优雅的解决方案：

三步走

flowchart TD A["第一步：提出提出一个局部敏感性的上界 B"] --> B["第二步：测试差分隐私地测试'LS_f(X) ≤ B' 是否成立"] B --> C{"测试结果"} C -->|"通过 ✅"| D["第三步：发布使用全局敏感性 Δ=B加噪声发布结果"] C -->|"未通过 ❌"| E["放弃 🛑返回'无法回答'"] style A fill:#e3f2fd,stroke:#1565c0 style B fill:#fff3e0,stroke:#e65100 style D fill:#e8f5e9,stroke:#2e7d32 style E fill:#ffcdd2,stroke:#c62828

步骤详解

第一步：提出

用户（数据分析师）根据数据集的已有知识或领域经验，提出一个局部敏感性的上界 B。

例如，对于最近两点距离查询，分析师可能说：「我猜所有点都分布在一个 100×100 的网格内，最近两点距离不会超过 2。」于是提出 B = 2。

第二步：差分隐私测试

现在我们需要差分隐私地测试：B 是否真的是局部敏感度的上界？

具体来说，我们需要测试：

对于所有相邻的 X'（与 X 差一条记录），是否都有 |f(X) - f(X')| ≤ B？

这可以用一个阈值查询来实现：计算有多少条记录违反了 B（即，如果删除这条记录，查询结果的变化超过 B），然后判断这个计数是否为零。

测试本身需要消耗一些隐私预算（比如用 ε₁/2 的拉普拉斯机制加噪声测试）。这个测试本身是差分隐私的。

第三步：发布或放弃

• 如果测试通过：我们就安全了。可以确信在当前数据集上，局部敏感性确实 ≤ B。然后用全局敏感性 Δ = B（而不是真正的全局最坏情况）来校准噪声，发布加噪后的结果。
• 如果测试未通过：说明我们的假设 B 不成立，数据集可能包含异常值，局部敏感性超过了 B。为了保护隐私，我们不能发布结果，只能返回「放弃」。

隐私预算分配

PTR 需要将总隐私预算 ε 分成两部分：

ε_total = ε_test + ε_release

• ε_test：用于差分隐私地测试 LS_f(X) ≤ B
• ε_release：用于最终发布加噪的结果

graph LR subgraph "预算分配" A["总预算 ε"] --> B["ε_test用于测试"] A --> C["ε_release用于发布"] end B --> D["阈值查询'有多少记录违反 B？'加 Lap(1/ε_test)"] C --> E["结果发布加 Lap(B/ε_release)"] style A fill:#e3f2fd,stroke:#1565c0 style B fill:#fff3e0,stroke:#e65100 style C fill:#c8e6c9,stroke:#2e7d32

PTR 的优缺点

一个完整例子

回到最近两点距离的例子。假设数据点是 100 个分布在 0-1 区间内的随机点：

数据集 X: 100 个点，点间距离在 0.01 到 0.5 之间 查询 f: 最近两点距离 全局敏感性: 理论上可以接近无穷大

PTR 登场：

1. 提出 B = 0.1：分析师根据经验认为最近点不会超过 0.1
2. 测试：用 ε_test = 0.5 差分隐私地测试「删除任意一个点，最近距离变化 ≤ 0.1」
   • 加噪计数为 0（通过）→ 可以继续
   • 加噪计数 > 0（未通过）→ 放弃
3. 发布：用 ε_release = 0.5，Δ = 0.1 加噪声，发布最近距离 ≈ 0.05 ± Lap(0.2)

对比：

• 传统方法：全局敏感性近乎无穷大→无法回答
• PTR：成功回答了近似距离，消耗 ε=1.0

下面我们用一个完整可运行的 Python 实现来展示 PTR 框架的完整流程：

from scipy import stats import numpy as np # === Propose-Test-Release (PTR) 框架实现 === np.random.seed(42) def nearest_distance(points): """计算点集中最近两点之间的欧几里得距离""" min_dist = float('inf') for i in range(len(points)): for j in range(i + 1, len(points)): dist = np.linalg.norm(points[i] - points[j]) if dist < min_dist: min_dist = dist return min_dist def local_sensitivity(points): """计算最近距离查询的局部敏感性""" original_dist = nearest_distance(points) max_change = 0 for i in range(len(points)): reduced = np.delete(points, i, axis=0) if len(reduced) >= 2: new_dist = nearest_distance(reduced) change = abs(original_dist - new_dist) if change > max_change: max_change = change return max_change def ptr_nearest_distance(points, B, epsilon_test, epsilon_release): """ PTR 框架：最近两点距离查询 参数: points: 点集 (n, 2) B: 提出的局部敏感性上界 epsilon_test: 用于差分隐私测试的预算 epsilon_release: 用于发布结果的预算 返回: (result, status): (发布结果或None, 状态说明) """ n = len(points) # ========== 第一步：Propose ========== print(f"📌 第一步（Propose）：提出局部敏感性上界 B = {B}") # ========== 第二步：Test ========== original_dist = nearest_distance(points) violation_count = 0 for i in range(n): reduced = np.delete(points, i, axis=0) new_dist = nearest_distance(reduced) if abs(original_dist - new_dist) > B: violation_count += 1 # 使用 scipy.stats.laplace 添加噪声（差分隐私测试） noisy_count = violation_count + stats.laplace.rvs( loc=0, scale=1.0 / epsilon_test ) print(f"🔍 第二步（Test）：差分隐私测试") print(f" 实际违规记录数 = {violation_count}") print(f" 加噪后违规数 = {noisy_count:.3f} (Lap(1/{epsilon_test}))") threshold = 0.5 if noisy_count <= threshold: # ========== 第三步：Release ========== noise = stats.laplace.rvs(loc=0, scale=B / epsilon_release) noisy_result = original_dist + noise print(f"✅ 第三步（Release）：测试通过 → 发布结果") print(f" 噪声分布: Lap({B}/{epsilon_release}) = Lap({B/epsilon_release:.3f})") print(f" 真实值: {original_dist:.4f} → 发布值: {noisy_result:.4f}") return noisy_result, "通过 ✅" else: print(f"❌ 第三步：测试未通过 → 放弃（放弃也是一种保护机制）") return None, "放弃 🛑" # ========== 对比实验 ========== print("=" * 70) print("Propose-Test-Release (PTR) 框架 —— 完整实现与对比") print("=" * 70) # 生成一个"行为良好"的数据集 points_good = np.random.uniform(0, 1, (50, 2)) true_dist = nearest_distance(points_good) print(f"\n📋 测试数据集：50个点均匀分布在 [0,1]² 内") print(f" 真实最近距离 = {true_dist:.4f}") print(f" 局部敏感性 = {local_sensitivity(points_good):.4f}") print(f" 全局敏感性（理论） = ∞（无法用拉普拉斯机制）\n") # ===== 方案 A：传统全局敏感性 ===== print("-" * 70) print("🔴 方案 A：传统全局敏感性方案") print("-" * 70) print(" 全局敏感性 Δ = ∞ → 拉普拉斯噪声 Lap(∞/ε) = ∞") print(" ❌ 结论：无法使用全局敏感性方案回答此查询\n") # ===== 方案 B：PTR 方案 ===== print("-" * 70) print("🟢 方案 B：PTR 方案（合理的 B）") print("-" * 70) epsilon_total = 1.0 result1, status1 = ptr_nearest_distance( points_good, B=0.3, epsilon_test=epsilon_total / 2, epsilon_release=epsilon_total / 2 ) print(f" 总预算 ε = {epsilon_total}，其中 ε_test={epsilon_total/2}, ε_release={epsilon_total/2}") print(f" 最终状态: {status1}\n") # ===== 方案 C：PTR 方案（B 过于乐观）===== print("-" * 70) print("🟡 方案 C：PTR 方案（过于乐观的 B，测试可能失败）") print("-" * 70) result2, status2 = ptr_nearest_distance( points_good, B=0.001, epsilon_test=epsilon_total / 2, epsilon_release=epsilon_total / 2 ) print(f" 最终状态: {status2}\n") # ===== 噪声对比总结 ===== print("-" * 70) print("📊 三种方案噪声对比总结") print("-" * 70) print(f" 方案 A（全局敏感性） ❌ 无法使用（Δ=∞）") print(f" 方案 B（PTR, B=0.3） ✅ 噪声 ≈ Lap(0.3/0.5) = Lap(0.600)") print(f" 方案 C（PTR, B 过于乐观） ⚠️ 测试未通过，无结果返回") print(f"") print(f" 关键洞察：PTR 用有限的隐私预算 ε_test 来验证局部敏感性的上界，") print(f" 如果验证通过，就可以用这个更小的上界 B 替代无穷大的全局敏感性来加噪声。") print(f" 代价是：① 预算需要分成两部分；② 可能因测试失败而放弃回答。")

运行上述代码可以看到 PTR 的完整工作流程：当数据集行为良好（局部敏感性较小）时，PTR 能够用远小于全局敏感性的噪声量回答查询；而当分析师提出的上界过于乐观时，PTR 会选择放弃——这是一种差分隐私框架下的安全保护机制。

4. 平滑敏感性（Smooth Sensitivity）

PTR 很巧妙，但它有一个「内置开销」——你需要在测试和发布之间分配预算，而且有放弃的风险。有没有办法直接用局部敏感性来校准噪声？

答案是：平滑敏感性（Smooth Sensitivity）。

核心思想

局部敏感性的问题在于它本身不稳定——两个只差一条记录的数据集，其局部敏感性可能相差很大（还记得全零点和 (10,10) 点集的例子吗？）。如果局部敏感性本身太「敏感」，那么用它来校准噪声就会泄露信息。

平滑敏感性的思路是：对局部敏感性进行平滑处理，使得平滑后的版本对于相邻数据集变化不会太大，从而可以安全地用来校准噪声。

定义：f 在 X 处的 β-平滑敏感性为：

S_f^*(X; β) = max_{k ≥ 0} e^{-βk} · max_{X': d(X, X') = k} LS_f(X')

其中 d(X, X') 表示两个数据集之间的汉明距离（差异记录数）。

翻译成人话：平滑敏感性就是考虑在距离当前数据集 k 步的所有数据集中，取局部敏感性的最大值，并乘以一个衰减因子 e^{-βk}，然后取所有这些值中的最大值。

graph TB subgraph "平滑敏感性的构造" A["X (当前数据集)LS_f(X) = 0.5"] --> B["考虑所有 X 的k步相邻数据集"] B --> C["k=1: LS_f(X₁) ≤ 1.0加权: e^(-β)×1.0"] B --> D["k=2: LS_f(X₂) ≤ 2.0加权: e^(-2β)×2.0"] B --> E["k=3: LS_f(X₃) ≤ 50.0加权: e^(-3β)×50.0"] C --> F["取所有加权值的最大值"] D --> F E --> F F --> G["S_f^*(X) = 平滑后的安全敏感性"] end style A fill:#e3f2fd,stroke:#1565c0 style G fill:#c8e6c9,stroke:#2e7d32

为什么平滑敏感性「安全」？

关键在于衰减因子e^{-βk}。即使某个远处的数据集有巨大的局部敏感性，它也会被指数衰减因子「压扁」。而衰减率 β 经过精心选择，保证平滑敏感性本身对于相邻数据集的变化被控制在合适的范围内——从而可以通过拉普拉斯或高斯机制安全使用。

如何选择 β？

β 的选择取决于你希望最终的机制满足 ε-差分隐私还是 (ε, δ)-差分隐私：

• 对于ε-DP（纯 DP）：β = ε / (2·ln(2/ε))（近似值，与具体查询相关）
• 对于(ε, δ)-DP（近似 DP）：β 可以更小一些

β 越小，衰减越慢，平滑敏感性越保守（越大），噪声也越大。β 越大，衰减越快，但要求相邻数据集间的变化更小。

用平滑敏感性校准噪声

一旦计算出了平滑敏感性 S^*(X)，我们就可以用它来校准噪声：

输出 = f(X) + Lap(2·S^*(X) / ε)

注意这里用的是2 × S^*（不是 S^*），这是因为平滑敏感性与全局敏感性之间有 2 倍的关系。

回到最近两点距离的例子

对于最近两点距离查询，平滑敏感性有一个闭式解：

S^*(X) = max_{k ≥ 0} e^{-βk} · (distance to (k+1)-th nearest neighbor)

直观理解：随着 k 增加，第 (k+1) 近的点距离一般会变大，但 e^{-βk} 会快速衰减。这个最大值通常出现在 k 比较小的时候。

假设数据集 X 中，最近的两点距离为 0.01，第二近的两点距离为 0.02， 第三近的两点距离为 0.1，第四近的两点距离为 0.5... 若 β=2： k=0: e^0 × 0.01 = 0.010 k=1: e^{-2} × 0.02 = 0.0027 k=2: e^{-4} × 0.1 = 0.0018 k=3: e^{-6} × 0.5 = 0.0012 平滑敏感性 = max(...) = 0.010 噪声量 = 2 × 0.010 / ε = 0.020 / ε

对比：

• 全局敏感性：接近无穷大 → ❌ 无法回答
• PTR：需要测试预算 + 可能放弃 → ✅ 可回答但复杂
• 平滑敏感性：仅需 0.020/ε 的噪声 → ✅ 直接可用

平滑敏感性的限制

平滑敏感性虽然优雅，但它有一个实际困难：计算它可能非常复杂。

对于最近两点距离这样的查询，我们可以推导出闭式解。但对于更复杂的查询（比如中位数、四分位距、聚类半径等），计算平滑敏感性可能需要复杂的几何或组合分析。

这限制了平滑敏感性的直接应用范围——它更适合理论分析，而 PTR 在实际工程中更常见。

5. PTR vs 平滑敏感性：对比

graph LR subgraph "选择指南" A["查询类型"] --> B{"有闭式解？"} B -->|"是 ✅"| C["平滑敏感性简洁高效"] B -->|"否 ❌"| D{"有领域知识？"} D -->|"是 ✅"| E["PTR提出上界 + 测试"] D -->|"否 ❌"| F["回到全局敏感性或寻求理论分析"] end style C fill:#c8e6c9,stroke:#2e7d32 style E fill:#e3f2fd,stroke:#1565c0 style F fill:#ffcdd2,stroke:#c62828

6. 这些方法的意义

不只是技术细节

超越全局敏感性不仅仅是一个「是否少加噪声」的问题。它触及了差分隐私实用化的核心障碍：

差分隐私被批评为「噪声太大了没法用」，这很大程度上是因为全局敏感性是最悲观的情况。局部敏感性、PTR 和平滑敏感性证明：噪声可以大幅降低——只要算法愿意观察数据的结构。

这就像是：

• 全局敏感性：假设所有司机都是杀人犯，给所有人都带上镣铐开车
• PTR：先测试这个司机是不是杀人犯，如果不是就少关着点
• 平滑敏感性：根据司机的历史驾驶记录，动态调整限制程度

实际部署中的选择

苹果、谷歌和人口普查局的差分隐私部署中，三者都有使用：

• 人口普查局：主要使用全局敏感性（因为查询标准化后敏感性可控），但对于某些特殊表使用了 PTR
• 苹果的 LDP：使用本地敏感性概念（每个用户的局部敏感度）
• 谷歌的 RAPPOR：使用了类似平滑敏感性的频率估计技术

7. 小结

mindmap root((超越全局敏感性)) 问题 全局敏感度过于保守 为不可能的场景支付成本 噪声量泄露信息 局部敏感性 当前数据集周围的敏感度 不能直接用于加噪 本身可能泄露信息 PTR 框架 提出上界 B 差分隐私测试 LS ≤ B 通过则发布，否则放弃 需要预算分配 平滑敏感性 指数衰减远处敏感度 可安全用于加噪 计算复杂 有闭式解的查询更适用

下一篇: 下界理论：差分隐私能有多好？ —— 任何差分隐私机制都有其内在的精度限制，这些限制由信息论下界决定。从 Packing 论证看差分隐私的「不可能三角」。