差分隐私深度学习(CCS16'(CCF A))
时隔半年重读这篇论文，终于懂了个七七八八，现在来做一下总结。
摘要
基于神经网络的机器学习技术在众多领域都取得了令人瞩目的成果。通常，模型的训练需要大量具有代表性的数据集，这些数据集可能是众包的，包含敏感信息。模型不应暴露这些数据集中的隐私信息。为了实现这一目标，我们开发了新的学习算法技术，并在差分隐私框架内对隐私成本进行了精细分析。我们的实施和实验证明，我们可以在适度的隐私预算下，以可控的软件复杂度、训练效率和模型质量成本，训练具有非凸目标的深度神经网络。
引言
我们将最先进的机器学习方法与先进的隐私保护机制相结合，在适度（"个位数"）的隐私预算内训练神经网络。我们处理的模型具有非凸目标、多个层以及数万至数百万个参数。（相比之下，之前的研究在参数数量较少的凸模型上取得了很好的结果，或者处理了复杂的神经网络，但隐私损失很大）。为此，我们开发了新的算法技术，在微分隐私框架内对隐私成本进行了重新精细分析，并制定了谨慎的实施策略：
- 我们证明，通过跟踪隐私损失的详细信息（高阶矩），我们可以从渐进和经验两方面对整体隐私损失获得更严格的估计。
- 我们通过引入新技术来提高差分隐私训练的计算效率。这些技术包括计算单个训练实例梯度的高效算法、将任务细分为更小的批次以减少内存占用，以及在输入层应用差分隐私主投影。
- 我们基于机器学习框架 TensorFlow [3]，训练具有差分隐私的模型。我们在两个标准图像分类任务 MNIST 和 CIFAR-10 上评估了我们的方法。我们之所以选择这两个任务，是因为它们基于公共数据集，并且长期以来一直是机器学习的基准。我们的经验表明，深度神经网络的隐私保护可以在软件复杂性、训练效率和模型质量方面以适度的成本实现。
本文的方法
本节将介绍我们的神经网络差分隐私训练方法的主要组成部分：差分隐私随机梯度下降算法（SGD）、矩统计（矩会计）和超参数调整。
差分隐私SGD算法
为了保护训练数据的隐私性，我们可以只研究训练过程中产生的最终参数，将这一过程视为黑箱。遗憾的是，一般情况下，我们可能无法对这些参数与训练数据的依赖关系进行有用的严密描述；在参数中加入过于保守的噪声（噪声是根据最坏情况分析选择的），会破坏所学模型的实用性。因此，我们倾向于采用一种更复杂的方法，即在训练过程中，特别是在 SGD 计算中，控制训练数据的影响。这种方法已在之前的研究中得到应用（例如，[52, 7]）；我们对其进行了一些修改和扩展，特别是在隐私开销核算方面。
注：这个算法与原始算法的主要区别是作者用了Lot的概念与Batch区分开，在这里Batch是梯度下降的执行基本单位，而Lot是添加差分隐私噪声的基本单位，一个Lot含多个Batch（文中说Lot比Batch大得多）。相当于多个Batch一起添加噪声，这样可以提升加噪的计算效率。
后文中Lot的大小记作\(L\)。
此外求敏感度的方法是考虑相邻数据集（变化一条数据）对于函数输出的影响（对函数输出的最大影响是多少）。
隐私核算
对于差分隐私 SGD，一个重要的问题是计算训练的整体隐私成本。差分隐私的可组合性使我们能够实现一个 "会计 "程序，在每次访问训练数据时计算隐私成本，并随着训练的进行累积这一成本。每一步训练通常都需要多个层的梯度，会计师会累积所有梯度对应的成本。
矩统计
很多研究都致力于研究特定噪声分布的隐私损失以及隐私损失的构成。对于我们使用的高斯噪声，如果我们在 算法1 中选择 \(\sigma\) 为 \(\sqrt{2\log\frac{1.25}\delta}/\varepsilon\)。那么根据标准论证 [20]：相对于批次而言，每一步都服从\((\epsilon, \delta)\)-差分隐私。由于批次本身是从数据库中随机抽样的，因此根据隐私放大定理 [33, 8]：相对于整个数据库，每一步都是\((O(q\epsilon), q\delta)\)-差分隐私的，其中 \(q = L/N\) 是每个加噪批次的抽样比率，\(\epsilon ≤ 1\)。文献中产生最佳总体约束的结果是强组合定理[22]。
然而，强组合定理可能比较松散，没有考虑到所考虑的特定噪声分布。在我们的工作中，我们发明了一种更强的计算方法，我们称之为矩统计（矩会计）。通过这种方法，我们可以证明，在适当选择噪声尺度和剪切阈值的情况下，算法1 是 \((O(q\varepsilon\sqrt{T}),\delta)\) -差分隐私的。与强组合定理的结果相比，我们的约束在两个方面更为严格：\(\epsilon\) 部分节省了 \(\sqrt{\log(1/\delta)}\) 倍，\(\delta\) 部分节省了 \(Tq\) 倍。由于我们预计 \(\delta\) 较小，且 \(T\gg1/q\)（即每个例子都要检查多次），因此我们的约束所带来的隐私开销的节省相当可观。这一结果是我们的主要贡献之一。
定理1 存在常数 \(c_1\) 和 \(c_2\)，因此在给定采样概率 \(q = L/N\) 和步骤数 \(T\) 的情况下，对于任意的 \(\varepsilon<c_{1}q^{2}T\)，算法1 对于任意 \(\delta > 0\) 都是 \((ε, δ)\)-差分隐私的，如果我们选择
\[\sigma\geq c_2\frac{q\sqrt{T\log(1/\delta)}}\varepsilon. \]
如果我们使用强组成定理，则需要选择\(\sigma=\Omega(q\sqrt{T\log(1/\delta)\log(T/\delta)}/\varepsilon)\)。请注意，我们在渐近约束中节省了\(\sqrt{\log(T/\delta)}\)的系数。正如这一结果所示，矩统计在理论上是有益的，在实践中也是如此，这一点可以从第 4 节中的图 2 中看出。例如，在 \(L = 0.01N\)、\(\sigma = 4\)、\(\delta = 10^{-5}\) 和 \(T = 10000\) 的条件下，使用矩统计，我们可以得到 \(\varepsilon\approx1.26\)。相比之下，使用强组合定理会得到更大的\(\varepsilon\approx9.34\)。 （使用矩统计更节约隐私开销）
矩统计：细节
（这一节具体讲解了作者提出的更加紧的隐私开销统计方法以及具体的公式推导，最重要的一节，重点看懂逻辑：作者先提出了结论——上面的 定理1，这一节是在讲这个\(\epsilon\)和\(\delta\)界怎么通过高阶矩的方法推导出来的）
隐私损失是一个随机变量，取决于添加到算法中的随机噪声。机制 \(\mathcal{M}\) 是\((\epsilon,\delta)\)-差分隐私的，这等同于 \(\mathcal{M}\) 的隐私损失随机变量的某个尾界。虽然尾界是关于分布的非常有用的信息，但直接从尾界组合会导致相当宽松的边界。我们转而计算隐私损失随机变量的对数矩，它是线性组合的。然后，我们利用矩约束和标准马尔可夫不等式，得到尾约束，即差分隐私意义上的隐私损失。
更具体地说，对于相邻数据库\(d,d'\in \mathcal{D}_n\)、机制 \(\mathcal{M}\)、辅助输入 \(\mathsf{aux}\) 和结果 \(o\in \mathcal{R}\)，定义 \(o\) 处的隐私损失为
\[c(o;\mathcal{M},\text{aux},d,d^{\prime})\stackrel{\Delta}{=}\log\frac{\Pr[\mathcal{M}(\text{aux},d)=o]}{\Pr[\mathcal{M}(\text{aux},d^{\prime})=o]} \]注意：上面这个式子是隐私损失的标准定义：就是两个相邻数据集下相同输出的概率之比的对数，只不过这里还考虑了辅助信息\(\mathsf{aux}\)，这里的辅助信息其实就是前面几轮的输出结果.
对于给定的机制 \(\mathcal{M}\)，我们将第 \(\lambda\) 阶矩 \(\alpha_\mathcal{M}(\lambda;\text{аих},d,d^{\prime})\) 定义为在数值 \(\lambda\) 处求值的矩母函数的对数：
$$\alpha_{\mathcal{M}}(\lambda;\mathsf{aux},d,d^{\prime})\triangleq\log\mathbb{E}_{o\sim\mathcal{M}(\mathsf{aux},d)}[\exp(\lambda c(o;\mathcal{M},\mathsf{aux},d,d^{\prime}))].$$
注：随机变量\(X\)的矩母函数定义是\(M_X(t)=\mathrm{E}[e^{tX}]\)
所以这里的矩母函数是\(\mathbb{E}_{o\sim\mathcal{M}(\mathsf{aux},d)}[\exp(x c(o;\mathcal{M},\mathsf{aux},d,d^{\prime}))]=\mathbb{E}_{o\sim\mathcal{M}(\mathsf{aux},d)}[\exp(x \log\frac{\Pr[\mathcal{M}(\mathrm{aux},d)=o]}{\Pr[\mathcal{M}(\mathrm{aux},d^{\prime})=o]})]\)，其中这就是关于隐私损失随机变量\(c\)的矩母函数.
为了证明机制的隐私保证，我们需要约束所有可能的 \(\alpha_\mathcal{M}(\lambda;\text{аих},d,d^{\prime})\)。我们定义
\[\alpha_{\mathcal{M}}(\lambda)\triangleq\max_{\mathrm{aux},d,d^{\prime}}\alpha_{\mathcal{M}}(\lambda;\mathrm{aux},d,d^{\prime}), \]其中，最大值取自所有可能的 \(\mathsf{aux}\) 和所有相邻数据库 \(d,d'\)（即要遍历所有可能的\(\mathsf{aux}\)和相邻数据集找到那个最大值）。
注：这里求 \(\lambda\) 阶矩的最大值是为了在后面的尾界定理能够求出 \(\delta\) 的上界。
定理2 令 \(\alpha_\mathcal{M}\) 如上定义，那么有以下两个性质：
\[\alpha_{\mathcal M}(\lambda)\leq\sum_{i=1}^{k}\alpha_{\mathcal M_{i}}(\lambda). \]
1. [可组合性] 假设机制 \(\mathcal{M}\) 由一系列自适应机制\(\mathcal{M}_{1},\ldots,\mathcal{M}_{k}\)组成，其中\(\mathcal{M}_{i}\colon\prod_{j=1}^{i-1}\mathcal{R}_{j}\times\mathcal{D}\to\mathcal{R}_{i}.\) 那么对于任意的\(\lambda\)有\[\delta=\min_{\lambda}\exp(\alpha_{\mathcal{M}}(\lambda)-\lambda\varepsilon). \]
- [尾界定理] 对于任意 \(\epsilon > 0\)，机制 \(\mathcal{M}\) 在以下条件下是 \((\epsilon, \delta)\)-差分隐私的：
特别地，当机制本身是根据先前机制的（公开）输出来选择时，定理 2.1 仍成立（我认为这是不等号的来源，因为噪声不独立了，附录中证明的时噪声独立的情况，即全是等号）。
根据 定理 2，只需计算或约束每一步的 \(\alpha_{\mathcal{M}_i}(\lambda)\) 并求和，就能约束整个机制的矩。然后，我们就可以利用尾部约束将矩量约束转换为 \((\epsilon, \delta)\)-差分隐私保证。（这是 定理2 如何应用的逻辑）
注：定理 2 的具体证明如下
\[P(X\ge a)\le\frac{E[X]}{a} \]
这里补充一个差分隐私收敛性分析中经常用到的（概率论）重要概念——马尔科夫不等式。马尔科夫不等式（Markov's inequality）是概率论中的一个基本不等式，描述了随机变量取非负值时的上界。该不等式由俄罗斯数学家安德烈·马尔可夫（Andrey Markov）于 1906 年提出。
马尔科夫不等式陈述如下：设 \(X\) 是一个非负的随机变量，即 \(X \geq 0\)，且 \(a\) 是一个正数，那么对于任意大于 \(a\) 的实数 \(t\)，有：其中 E[X] 是 X 的期望值（或者说均值）。
换句话说，马尔科夫不等式告诉我们，对于任何非负的随机变量 \(X\) 和任意正数 \(a\)，\(X\) 超过 \(a\) 的概率不超过其期望值除以 \(a\)。这个不等式在概率论和统计学中有着广泛的应用，例如在证明其他重要不等式，或者作为估计边界时使用。
那么剩下的主要挑战是如何约束每一步的 \(\alpha_{\mathcal{M}_t}(\lambda)\) 值。对于随机抽样的高斯机制，只需估计以下矩即可。让 \(\mu_0\) 表示 \(N (0,\sigma^2)\) 的概率密度函数(probability density function, pdf)，\(\mu_1\) 表示 \(N (1,\sigma^2)\) 的 pdf。让 \(\mu\) 成为两个高斯分布的混合 \(\mu=(1-q)\mu_0+q\mu_1\)。然后我们需要计算 \(\alpha(\lambda)=\log\max(E_1,E_2)\)。其中
\[E_{1}=\mathbb{E}_{z\sim\mu_{0}}[(\mu_{0}(z)/\mu(z))^{\lambda}],\\E_{2}=\mathbb{E}_{z\sim\mu}[(\mu(z)/\mu_{0}(z))^{\lambda}]. \]在实现矩会计时，我们进行数值积分来计算 \(\alpha(\lambda)\)。此外，我们还可以证明渐近约束
\[\alpha(\lambda)\leq q^2\lambda(\lambda+1)/(1-q)\sigma^2+O(q^3/\sigma^3). \]注：定理1 的具体证明如下
step1：先证明引理3
注：引理 3 中 \(\mathcal{M}(d)\sim\mu\triangleq(1-q)\mu_0+q\mu_1\) 是因为\(d\)是由\(d'\)和一个抽取的元素\(d_n\)组成的，而对于随机抽取的元素有\(f(d_n)=e_1\)也就是第一个元素是\(1\)其他元素是\(0\)的向量。又因为有\(q\)的概率抽到\(d_n\)，其他概率是原本的\(d'\)，所以最终分布是这样的.
注：\(\mathbb{E}_{z\sim\nu_0}[(\nu_0(z)/\nu_1(z))^\lambda]=\mathbb{E}_{z\sim\nu_1}[(\nu_0(z)/\nu_1(z))^{\lambda+1}]\)的推导如下：
这里用了一个重要性采样方法，用另一个分布计算当前分布的期望
以上证明完了引理 3，后面依据 引理 3 证明 定理 1
实验
在实验中，我们设定 \(q = 0.01\)、\(\sigma = 4\) 和 \(\delta = 10^{-5}\)，并计算了 \(\epsilon\) 值与训练历时 \(E\) 的函数关系。图 2 显示了分别对应于使用强组成定理和矩会计的两条曲线。我们可以看到，使用矩会计可以更精确地估计隐私损失。例如，当 \(E = 100\) 时，数值分别为 \(9.34\) 和 \(1.26\)，而当 \(E = 400\) 时，数值分别为 \(24.22\) 和 \(2.55\)。也就是说，利用矩约束，我们可以获得 \((2.55, 10^{-5})\)-差分隐私，而之前的技术只能获得 \((24.22, 10^{-5})\)-差分隐私的保证。
