企业官网建设流程全解析

原文课程: Lecture 11 — Packing Lower Bounds (Gautam Kamath, CS 860, Fall 2020)

上几讲我们看到了各种 DP 算法，自然会问一个问题：我们能不能做得更好？或者说，现在已经有的算法是否已经是最优的了？

答案是：在很多基本问题上，我们之前介绍的简单算法已经是最优或接近最优的了。这节课就介绍如何证明这一点。

1. 两个核心问题

我们主要关注两类查询：

（1）一维边际查询（One-Way Marginals）

数据域 X = {0,1}ᵈ。我们有 d 个查询：

fⱼ(X) = (1/n) · Σᵢ Xᵢ⁽ʲ⁾

即：第 j 个特征在人群中的比例。

（2）直方图查询（Histograms）

数据域 X = [k]（k 个类别）。有 k 个查询：

fⱼ(X) = (1/n) · Σᵢ 1{Xᵢ = j}

即：每个类别的人数占比。

2. 已知的上界

用我们之前学过的算法，可以得到以下上界（即存在算法能达到的精度）：

一维边际查询（d 个特征）

直方图查询（k 个类别）

注意到一维边际查询中纯 DP 和近似 DP 有个√d 的差距——近似 DP 好得多。

3. Packing 下界：核心思想

如何证明一个 DP 算法不可能比某个精度更好？Packing 下界是标准方法。

直观思路

graph TD A["可能的数据库集合"] --> B["分割成很多个packing球"] B --> C["球心互不相交任意两个球心距离 ≥ 2α"] C --> D{"DP算法区分它们"} D -->|"如果能区分→误差 < α"| E["违反DP"] D -->|"不能区分→误差 ≥ α"| F["下界成立"]

步骤

1. 构造大量"不同"的数据库：这些数据库两两之间差异较大（足够多的行不同）
2. 运用 DP 的组合性质：DP 限制了算法对不同输入产生截然不同输出的能力
3. 取"大多数"情况：如果数据库数量太大，必然有一些会被混淆

4. 纯 DP 的下界：证明直觉

对于一维边际查询（d 个特征），假设我们的算法能回答所有查询误差 ≤ α。

构造

考虑一组数据库的集合，每个数据库只由 {0,1} 组成（全是 0 或全是 1 的向量）。

取这些数据库，使得任意两个数据库在至少 d/2 个维度上取值相反。现在，如果我们能在密码学意义上"区分"两个在 d/2 个维度上不同的数据库，我们就能推断出大量信息。

应用 DP 的 Packing 论证

数据库数量 ≈ 2^d 两两之间的距离 ≥ d/2 DP 保证：任何两个数据库的输出的分布是"相近的" （相似性由 ε 衡量） 包覆论证： 2^d 个数据库太多， 必然有至少两个会被"混淆" → 无法区分

推得：n 必须 ≥ Ω(d/εα)。而拉普拉斯机制正好达到这个界限！

5. 纯 DP vs 近似 DP 的差距

对于一维边际查询，我们发现：

这就解释了为什么近似 DP 在实际中如此重要——在高维数据（d 很大）上，近似 DP 只需要纯 DP 的 1/√d 的样本量。

graph LR subgraph "特征维度 d=10000" A["纯DP需要的样本: n ≈ 10000/εα"] B["近似DP需要的样本: n ≈ 100/εα"] end C["近似DP只需要纯DP的1% 的样本量!"]

6. 直方图查询：纯 DP 的胜利

对于直方图查询，结果是不同的：

对于直方图，纯 DP 和近似 DP 的差距不大。这是因为直方图的 ℓ₁-敏感性只有 2（与类别数 k 无关），拉普拉斯直方图本身已经非常高效。

7. 下界技术的更深含义

用代码感受：为什么纯 DP 的样本量是 Ω(d)

下面用模拟实验展示纯 DP 在处理高维边际查询时的固有困难：

import numpy as np def pure_dp_marginals(data, epsilon): """纯DP：用拉普拉斯机制回答所有一维边际查询""" n, d = data.shape means = np.mean(data, axis=0) sensitivity = d / n # ℓ₁敏感性：最坏情况 noise = np.random.laplace(0, sensitivity / epsilon, d) return means + noise def approx_dp_marginals(data, epsilon, delta): """近似DP：用高斯机制回答所有一维边际查询""" n, d = data.shape means = np.mean(data, axis=0) l2_sensitivity = np.sqrt(d) / n # ℓ₂敏感性 sigma = l2_sensitivity * np.sqrt(2 * np.log(1.25 / delta)) / epsilon noise = np.random.normal(0, sigma, d) return means + noise # ===== 实验：固定n和d，看两种DP的误差 ===== np.random.seed(42) n, d = 500, 50 # 500条数据，50个二进制特征 data = np.random.randint(0, 2, (n, d)) # 随机二进制数据 epsilon, delta = 1.0, 1e-5 # Packing下界预测： # 纯DP需要 n ≥ Ω(d/εα) → α ≥ Ω(d/(εn)) = 50/(1×500) = 0.1 # 近似DP需要 n ≥ Ω(√d/εα) → α ≥ Ω(√d/(εn)) = 7/(1×500) = 0.014 trials = 100 pure_errors, approx_errors = [], [] for _ in range(trials): pure_out = pure_dp_marginals(data, epsilon) approx_out = approx_dp_marginals(data, epsilon, delta) true_means = np.mean(data, axis=0) pure_errors.append(np.max(np.abs(pure_out - true_means))) approx_errors.append(np.max(np.abs(approx_out - true_means))) print(f"n={n}, d={d}, ε={epsilon}, δ={delta}\n") print(f"纯DP (拉普拉斯): 平均最大误差 = {np.mean(pure_errors):.4f}") print(f" Packing下界预测: α ≥ {d/(epsilon*n):.4f}") print(f"近似DP (高斯): 平均最大误差 = {np.mean(approx_errors):.4f}") print(f" Packing下界预测: α ≥ {np.sqrt(d)/(epsilon*n):.4f}") print() print(f"→ 纯DP误差是近似DP的 {np.mean(pure_errors)/np.mean(approx_errors):.1f} 倍") print(f"→ 这就是Packing下界揭示的 √d 差距!")

运行这个实验，你会发现纯 DP（拉普拉斯）的误差大约是近似 DP（高斯）的 7 倍（d=50 时，√50 ≈ 7），与 Packing 下界的理论预测完全一致！

Packing 下界不仅仅告诉我们"现有算法已经够好"，还有一些更深层的含义：

（1）隐私与精确度的必然权衡

任何提供差分隐私的算法，必然损失一定的精度。这个损失不是设计缺陷，而是隐私的"价格"。

（2）纯 DP 的固有代价

纯 DP 在某些问题上有固有的限制（比如高维边际查询需要 Ω(d) 的样本量），这是信息论上不可避免的，与具体的算法设计无关。

（3）近似 DP 的优势根源

近似 DP 的 √d 优势来自 δ 提供的"喘息空间"——允许以极小概率发生隐私损失违反，从而可以用高斯分布的高维集中性质。

小结

"下界"的存在其实是件好事——当你的问题有下界时，你知道努力的方向不是寻找更精确的算法，而是放松隐私要求、收集更多数据、或改变问题设定。

下一讲开始，我们将进入机器学习与差分隐私的交叉领域，探讨更实际的问题。

下一篇: 隐私与机器学习：什么才是真正的隐私？