Moments accountant 理解🙌🙌

SIGSAC 2016 Deep Learning with Differential Privacy

特别棒的一篇文章，将几种常见的 Composition Theorem（组合定理）说的很清楚：
论文提出的方法就是在计算的梯度中加入噪声，而重要的就是噪声的大小，整篇文章的重点就是研究如何在满足差分隐私的前提下加入噪声来实现满足 DP 的深度学习。
算法通过计算一组样本的损失梯度并取平均值来估计的梯度。平均值提供了一个无偏估计量，其方差随着群体的规模迅速减小。作者称这样的分组样本为“lot”，以区别于通常称为“batch”的计算分组。为了限制内存消耗，可以将 batchsize 设置得比算法的参数“lot”大小小很多。算法在“batch”中执行计算，然后将几个“batch”分组为一个“lot”，以添加噪声。
变量概念及基本过程含义：

• ：输入数据集大小
• ：分组样本“lot”的大小
• ：，采样概率，用于在输入数据集中采样“lot”
• epoch：处理输入的数据集（以概率被采样成多个“lot”，“lot”的大小为），作用对象为多个“lot”
• step：区别于 epoch 或 iteration，作用对象为 batch。为了限制内存消耗，可以将 batchsize 设置得比算法的参数“lot”大小小很多。算法在“batch”中执行计算，然后将几个“batch”分组为一个“lot”，以添加噪声。

Moments Accountant 总览

1. 如果在训练过程中注入的高斯噪声满足（定义了噪声的大小）。每一个“lot”都满足-DP。
2. 每个 step 都满足-DP，其中即为“lot”的采样概率（类比于“batch”的采样概率）。
3. 经过次 iterations，通过不同的高级组成定理，可以得到不同的约束，Navie Composition Throrem 给出的约束为-DP。
4. Strong Composition Throrem 给出的约束为-DP
5. 本文提出的 Moments Accountant 给出了更加严格的约束为-DP

Moments Accountant 计算过程

1. 差分隐私等价于约束两个分布的差异
2. 两个分布的差异可以用来衡量
   
3. 这个差异是一个满足亚高斯分布的随机变量
4. 考虑这个随机变量的矩母函数 MGF
5. 结合 Markov 不等式，推出矩母函数:

6. 约束，取得矩母函数的最小值：
而这个决定了加入噪声的大小，其中。一个简单的例子：

在三种方法中，Moment Account 方法在同样的花费的隐私预算最小。
Theorem(1)
如果存在两个常数,并且给出采样概率，算法迭代次数，对于任何，则算法满足-DP的前提是选择：

如果使用 Strong Composition Throrem，选择，如果带入具体数值来计算，如果使用 Moments Accountant 可实现，Strong Composition Throrem 只能实现
Theorem(2)
[Composability] 假设一个算法机制包含一个自适应算法序列，其中，对于任何存在 ：

[Tail bound] 对于任意，如果满足，则算法机制满足-DP
Privacy Loss
对于一个相邻的输入，一个算法机制，辅助输入，输出，则隐私损失 Privacy Loss 基于输出定义为：

Moment Generating Function
给出一个算法机制，定义阶的矩作为在处评估的矩母函数的对数：

整体矩为：

Deriving Moments bound for Gaussian
令代表高斯分布的 PDF，代表高斯分布的 PDF，代表两个高斯分布的混合：，对 GMF 有，其中
在实现中，通过数值积分来计算，此外，渐进约束如下：

再加上这个约束和 Theorem(2)，得到 Theorem(1) 的证明。