差分隐私经验风险最小化

原文课程: Lecture 13 — Private ML and Stats: Differentially Private ERM (Gautam Kamath, CS 860, Fall 2020)现在真正开始讲差分隐私机器学习。我们先从最经典的机器学习框架开始——经验风险最小化Empirical Risk Minimization, ERM。1. 什么是经验风险最小化问题定义我们有数据集 D包含 n 个样本 (xᵢ, yᵢ)。我们的目标是找到一个参数 θ最小化在训练集上的损失L(θ, D) Σᵢ ℓ(θ, xᵢ, yᵢ)其中 ℓ 是损失函数。比如线性回归的平方损失ℓ(θ, xᵢ, yᵢ) (⟨xᵢ, θ⟩ - yᵢ)²graph LR A[数据集 D] -- B[定义损失函数 ℓ] B -- C[找到 θ* argmin L(θ,D)] C -- D[得到分类器 f_θ]非私有的做法标准方法是梯度下降重复计算梯度并更新参数。θ θ₀ for t in range(T): gradient ∇L(θ, D) # 计算所有数据的平均梯度 θ θ - η * gradient # 更新参数问题梯度直接依赖于训练数据——查看梯度本身就是一种隐私泄露。2. 差分隐私 ERM 的三种策略要使 ERM 满足差分隐私有三种经典方法策略思路特点输出扰动先求解再给解加噪简单适合凸问题目标扰动给损失函数加噪再求解对优化器友好梯度扰动在每次梯度更新时加噪最灵活适合深度学习3. 输出扰动Output Perturbation做法在非私有数据上求解 ERMθ* argmin L(θ, D)给 θ* 加噪声θ̃ θ* 噪声flowchart LR A[训练数据 D] -- B[求解 argmin L(θ,D)] B -- C[得到最优参数 θ*] C -- D[给 θ* 加噪声] D -- E[输出 θ̃]关键问题需要知道最优解 θ* 的敏感性——相邻数据集的最优解最多能差多少对于凸、L-Lipschitz 损失函数且参数域有界的情况敏感度是O(直径/√n)。特点优点缺点实现简单只适用于凸优化只需一次加噪需要知道参数域的直径适合一次性发布不能用于深度学习非凸4. 目标扰动Objective Perturbation做法修改损失函数添加一个隐私项L̃(θ, D) L(θ, D) (ε/Δ)·‖θ‖² ← 目标扰动项然后最小化这个修改后的目标函数。flowchart LR A[原始损失 L(θ,D)] -- B[添加扰动项] C[正则化项] -- B B -- D[修改后的损失 L̃(θ,D)] D -- E[求解 argmin L̃(θ,D)] E -- F[输出 θ̃]直觉添加的扰动项相当于一种隐私正则化它惩罚过度拟合——与差分隐私的目标一致求解过程本身不引入额外隐私成本特点优点缺点不需要给解加噪需要修改优化器适用于某些非凸场景数学分析复杂可配合标准优化算法加噪量需要精确计算5. 梯度扰动Gradient Perturbation——最关键这也是 DP-SGD 的基础我们详细讲。做法在每次梯度下降迭代中对梯度的平均值添加噪声θ θ₀ for t in range(T): gradient ∇L(θ, D) # 计算平均梯度 noisy_gradient gradient N(0, σ²) # 添加高斯噪声 θ θ - η * noisy_gradient # 更新flowchart TD A[参数 θₜ] -- B[计算梯度 ∇L(θₜ, D)] B -- C[添加高斯噪声∇̃ ∇L N(0,σ²)] C -- D[更新 θₜ₊₁ θₜ - η·∇̃] D -- E{是否收敛} E --|否| B E --|是| F[输出差分隐私模型 θ]隐私分析每次迭代的隐私成本使用高斯机制每次迭代是 (ε₀, δ₀)-DPT 次迭代后的总隐私使用高级组合定理ε_total ≈ O(ε₀·√(T·log(1/δ)))6. 三种方法的对比特性输出扰动目标扰动梯度扰动加噪时机训练结束后训练开始前每次迭代凸优化支持✅✅✅深度学习支持❌❌✅实现复杂度低中中隐私分析简单中等需高级组合典型误差O(1/εn)O(1/εn)O(√T/εn)7. 核心数学梯度裁剪Gradient Clipping梯度扰动的一个关键概念是梯度裁剪。为什么需要它敏感性控制如果某个样本的梯度很大那么它会对平均梯度产生很大影响→敏感性高→需要加更多噪声。解决办法限制每个样本梯度的 ℓ₂ 范数。def clip_gradient(g, C): 将梯度 g 裁剪到 ℓ₂ 范数 ≤ C norm sqrt(sum(g_i² for g_i in g)) if norm C: return g * (C / norm) return ggraph LR A[样本梯度 g₁||g₁||100] -- C[裁剪到 C1] B[样本梯度 g₂||g₂||0.5] -- D[不变] C -- E[裁剪后:所有梯度范数 ≤ C] D -- E E -- F[加噪后:敏感度 C/n]裁剪阈值 C 是一个超参数C太大→ 敏感性高 → 噪声大C太小→ 梯度信息丢失 → 模型不收敛通常 C 设为梯度的中位数或众数8. DP-ERM 的误差分析对于凸、L-Lipschitz 损失函数DP-ERM 能达到的误差超过最优解场景误差非私有基准0可精确找到最优解输出扰动O(L·直径/εn)目标扰动O(L·直径/εn)梯度扰动O(L·√T·直径/εn)关键观察误差与 1/n 成正比——收集更多数据可以直接降低隐私带来的误差。小结概念要点ERM最小化训练损失找到最优参数输出扰动先求解再加噪目标扰动修改损失函数梯度扰动每次迭代加噪梯度裁剪控制梯度敏感性数据越多越隐私误差 ∝ 1/n下一讲我们将讨论现代深度学习中的差分隐私——当模型不再是简单的凸函数时如何有效地保护隐私。下一篇: 现代机器学习中的差分隐私DP-SGD 与 PATE