原文课程: 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 个特征隐私模型所需样本量 n误差 ≤ αε-DP纯n Õ(d/αε)(ε,δ)-DP近似n Õ(√d/αε)直方图查询k 个类别隐私模型所需样本量 n误差 ≤ αε-DP纯n O(log k / αε)(ε,δ)-DP近似n O(log(1/δ) / αε)注意到一维边际查询中纯 DP 和近似 DP 有个√d 的差距——近似 DP 好得多。3. Packing 下界核心思想如何证明一个 DP 算法不可能比某个精度更好Packing 下界是标准方法。直观思路graph TD A[可能的数据库集合] -- B[分割成很多个packing球] B -- C[球心互不相交任意两个球心距离 ≥ 2α] C -- D{DP算法区分它们} D --|如果能区分→误差 α| E[违反DP] D --|不能区分→误差 ≥ α| F[下界成立]步骤构造大量不同的数据库这些数据库两两之间差异较大足够多的行不同运用 DP 的组合性质DP 限制了算法对不同输入产生截然不同输出的能力取大多数情况如果数据库数量太大必然有一些会被混淆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/εα)O(d/εα) ✅紧的近似 DPΩ(√d/εα)O(√d/εα) ✅也紧的这就解释了为什么近似 DP 在实际中如此重要——在高维数据d 很大上近似 DP 只需要纯 DP 的 1/√d 的样本量。graph LR subgraph 特征维度 d10000 A[纯DP需要的样本: n ≈ 10000/εα] B[近似DP需要的样本: n ≈ 100/εα] end C[近似DP只需要纯DP的1% 的样本量!]6. 直方图查询纯 DP 的胜利对于直方图查询结果是不同的模型下界上界纯 DPΩ(log k / εα)O(log k / εα) ✅ 紧的近似 DPΩ(log(1/δ) / εα)O(log(1/δ) / εα) ✅ 紧的对于直方图纯 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, axis0) 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, axis0) 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, axis0) pure_errors.append(np.max(np.abs(pure_out - true_means))) approx_errors.append(np.max(np.abs(approx_out - true_means))) print(fn{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 倍d50 时√50 ≈ 7与 Packing 下界的理论预测完全一致Packing 下界不仅仅告诉我们现有算法已经够好还有一些更深层的含义1隐私与精确度的必然权衡任何提供差分隐私的算法必然损失一定的精度。这个损失不是设计缺陷而是隐私的价格。2纯 DP 的固有代价纯 DP 在某些问题上有固有的限制比如高维边际查询需要 Ω(d) 的样本量这是信息论上不可避免的与具体的算法设计无关。3近似 DP 的优势根源近似 DP 的 √d 优势来自 δ 提供的喘息空间——允许以极小概率发生隐私损失违反从而可以用高斯分布的高维集中性质。小结概念要点Packing 下界证明 DP 误差不可能低于某个值的方法纯 DP vs 近似 DP高维问题上近似 DP 有 √d 的优势直方图纯 DP 在此问题上表现也很好隐私-精度权衡隐私不是免费的——代价是降低精度已有算法拉普拉斯/高斯/指数机制在最基本问题上已经最优下界的存在其实是件好事——当你的问题有下界时你知道努力的方向不是寻找更精确的算法而是放松隐私要求、收集更多数据、或改变问题设定。下一讲开始我们将进入机器学习与差分隐私的交叉领域探讨更实际的问题。下一篇: 隐私与机器学习什么才是真正的隐私