「隐语小课」深度学习下的DP-SGD
原创刘颖婷隐语的小剧场 2023-03-02 07:08 发表于浙江
收录于合集#隐语小课23个
前言：
基于差分隐私随机梯度下降法 (DP-SGD) 是深度学习中最流行的 DP 训练方法，与传统的随机梯度下降算法（SGD）的主要不同点是：DP-SGD算法在每一轮迭代过程中都会进行梯度裁剪和添加高斯噪声。本篇内容将对深度学习下的DP-SGD进行分析总结，隐语在此方向也有相关探索，敬请期待后续开源进展。
1.深度学习下的差分隐私
1.1 深度学习中的差分隐私的定义
在深度学习中，差分隐私的定义如下：
(Definition 1. Differential Privacy in Deep Training System)
- 记数据集为
，由所有
的子集组成的训练数据库记为
，参数空间为
- 一个具有随机性质的深度学习训练机制，将训练数据集
作为输入，训练后输出参数
，记作
我们称这一训练机制满足
，如果对于任意两个毗邻的训练集
, 以及任何参数范围
，其输出的参数分布满足[1]：
在该定义下，数据集中的单个数据对于模型的影响被控制在一定的范围内，实现了差分攻击在模型层面的“不可分辨性”。
1.2 梯度扰动DP-SGD
在深度学习的训练中，模型参数采用梯度下降法进行更新，即
其中
是随机初始化参数。为了控制个体数据的影响，文献[2]利用高斯机制对梯度施加差分隐私。在每轮训练中，首先对训练集的每一个样本计算梯度进行裁剪，之后进行高斯噪音的加噪，最后用满足差分隐私的梯度
进行参数更新。DP-SGD伪码如下：
利用高斯机制，深度学习的梯度更新分为3步：
1.梯度裁剪
- 单梯度级别的裁剪（clipping），若该梯度的L2范数大于C，则对其进行修剪，以控制个体数据的影响
- 此时梯度的敏感度为
- 其中
和C 在不同的网络层、不同的迭代轮次中都是可变的 - 对比深度学习，通常的clipping在求过均值以后
2.高斯加噪
- 梯度更新时用的是均值，这个计算平均的group被称作一个Lot（和batch做区分）
- 效率优化：计算梯度和clipping时以batch为单位（1、2步），之后将很多个batch聚合为一个Lot进行加噪和更新（3、4步），此时设置的batch size 要远小于（much smaller than） the Lot size L
- 采样率(N为样本量)
3.更新模型
最后我们还需要计算模型的隐私损失 (Privacy accounting & Moments accountant)
- 计算每次访问数据的privacy cost，随着训练的进行将其累积（串行组合）
- 计算整体的privacy cost
1.3整个训练系统的隐私损失（Privacy accounting）
moments accountant[2]的基本思想是将训练的隐私损失（privacy loss）看成随机变量，通过计算随机变量的矩生成函数（moment generating function），可以得到更精准的隐私界。而总隐私损失的分布又为各轮随机变量的加和分布，进而可以推广到深度学习的多轮迭代中。该方法最终可以归结为RDP的计算，并且在高斯机制下具有解析解。论文证明部分总览如下：
1.3.1 定义损失随机变量
对于训练机制，差分隐私的目标是令其在相邻数据库上得到的参数
的分布尽量相似。在差分隐私中，隐私损失是一个非常重要的定义，深度学习中的针对参数
的隐私损失定义如下：
(Definition 2. Privacy Loss in Deep Training System)
- 记数据集为d，由所有d的子集组成的训练数据库记为
，参数空间为
- 一个具有随机性质的深度学习训练机制，将训练数据集
作为输入，训练后输出参数
，记作
该随机函数造成的隐私损失
定义为：
我们知道训练是一个的迭代过程，对于第k step，我们用
对于相邻数据集
，及一系列的输出
，我们有
因此，训练系统
的隐私损失随机变量可以由多个时刻的隐私损失随机变量的加和Composition来表示，我们将其简写为
1.3.2 对数矩母函数
如果在任意相邻数据集
上训练机制的输出参数分布完全一致，那么
的估计都应当趋向于0，也就是说随机变量c的一阶矩
，二阶矩
，以至n阶矩都应当在0附近，因此我们可以用随机变量c的矩的大小来衡量隐私损失。
考虑
的对数矩生成函数（Moment Generating Functions）：
利用(2)式的独立性，当对由t次训练轮构成的系统
而言，它的对数矩生成函数也具有求和性：
因为差分隐私界需要遍历所有的相邻数据集
, 因此我们记：
利用最大值的性质, 我们有：
1.3.3 差分隐私刻画
那么，如何利用隐私损失
的矩母函数
来刻画单个数据对于模型的影响被控制在一定的范围内这件事情呢？如何将其联系到差分隐私呢？
根据差分隐私的定义，对于任意相邻数据库
，以及任意
，我们都有：
也就是说，此时
可以理解为，整个训练过程的隐私损失随机变量为
值大于
的概率小于
。它的直观含义为，对于一个数据量为
的数据库，我们可以构造
组相邻子数据库
。
对于每一组相邻子数据库我们都可以计算对应的度量隐私损失的矩生成函数值
。遍历所有的相邻子数据库，大概只有比率为
的数据库会导致该隐私损失函数值大于
。
于是我们的得到
[尾界 Tail bound]对于任意
, 随机机制
为
，其中：
1.3.4 约束每个step的隐私损失
在上文中，我们讨论了整个训练系统的差分隐私损失计算。但是
的计算需要遍历整个数据集，这种计算成本是不可接受的。此外，采样率在隐私计算中起到了隐私增幅，减小隐私损失的作用，这也需要在Moments Accountant的计算中得到广泛考虑。
对于高斯噪声，文献[2]提出了一种广泛使用的计算Moments Accountant的方法，如下所述：
(Proposition 1. Calculations of Moments Accountant with Gaussian Mechanism)
考虑具有随机Subsample的高斯机制, 其中高斯机制的噪声乘子(noise multiplier)为
，记采样率为
。
- 令
为分布
的概率密度函数，
为分布
的概率密度函 - 令
结合文献 [2,5] , 我们需要计算
,其中
以上式为例，我们要求的是对数矩母函数：
注意到此时
对于给定的采样率
以及噪声乘子
是一个固定的数值，这也就是说，对于任何的神经网络模型与任何数据集，采用基于Subsample的高斯机制的隐私损失的上界都是一样的。
对于整数
，(3)式可以写成：
此时, 对于任意正整数
，
具有解析解为：
将其代入则可得到(3)的数值解。
对于非整数的
, 我们可以直接进行数值积分, 或者采用基于揷值的估计方法。文献 [4] 提出了一个利用
的向下取整
与向上取整
构造估计值，即
此外, 文献[2]还给了一个近似上界, 即
对于Rényi Differential Privacy，文献[4,5]都对高斯机制的Subsample进行了研究，提出了更紧的基于Subsample的隐私损失.
1.3.5 RDP
（Definition3 Rényi divergence). 文献[3]设
和
是
上定义在相同的概率空间上的两个分布，p和q是它们各自的概率密度函数。则分布
间有限阶（
）的Rényi散度定义为：
处的Rényi散度由连续性定义
(Definition4 Rényi differential privacy (RDP).
若一个随机机制
对任意两个邻接输入
满足
-Rényi differential privacy (RDP) ，则如下不等式成立：
注意到：
因此，
可以与RDP进行直接联系，进而可以扩展到
。
我们有：
(Proposition 2. From RDP to DP) 如果训练机制
服从
一 RDP, 那么对于所有的
, 服从
,
服从
.
(Proposition 3. Moments Accountant and RDP) 对于任意的
，在t时刻具有随机性的训练机制
满足
，而整个训练系统
则至少具有:
利用Proposition 1中从RDP到DP的转换，以及Proposition 2中从Moments Accountant到 RDP的转换，我们有如下结论：
(Proposition 4. From Moments Accountant to
)
- 在t时刻具有随机性的训练机制
满足:
- 给定
，则最佳的
取值为：
- 给定
，则最佳的
取值为:
1.3.6 总结
综上所述，对于一个使用高斯机制的深度学习训练系统，计算隐私损失大概可以分为三步（这也是Tensorflow的Moments Accountant官方库中的计算方法）：
- 确定给定的噪声乘子
，梯度裁剪系数C以及采样率q。 - 对某个范围的order(
)计算
。一般而言，我们取
- 确定
的数值（一般为N/1，N为样本量），根据
对表中所有的
计算最佳的
，然后得出整个训练系统的隐私损失。
附录
a. 尾概率(Tail Probabilities)
假设
是一个i.i.d 随机变量序列- 均值
及方差
均存在
若采用如下估计量来估计
:
问：
- 该估计量是否为无偏估计？
和
之间大概相差多远？
answer 1:
answer2:
（定义：尾概率)
若
是一个均值为
的随机变量，
是一个常数：
称作右尾概率（upper tial probability）
称作左尾概率（lower tial probability）
称作双尾概率（two-sided tial probability）
b. 马尔科夫不等式（Markov's inequality）
(马尔科夫不等式)
给定样本空间
上的非负随机变量
, 且
的期望 E(X) 存在,
为一个常数，则有
c. 矩母函数（Moment Generating Function）
用函数刻画概率分布：cdf，pdf，矩母函数
（定义：矩母函数）
假设
为一个随机变量，若存在
，对于任意
均存在，则称
存在矩母函数（MGF）记作
，定义式为：
性质：
(第i阶导=i阶原点矩 )
d. 瑞丽熵（Renyi Divergence）
Divergence并不是距离，因为不满足距离定义中的对称性，但是我们仍然可以用它来衡量两个分布之间的差距，比如常用的KL-Divergence。而和Renyi Entropy一样，Renyi Divergence也是KL-Divergence和Max-Divergence的推广。
离散形式为：
其中, P和Q分别表示两个随机变量。
1. KL Divergece
当
，
利用洛必达法则(
形)，得到：
2.MaxDivergece
当
，
当对这个Max-Divergence进行约束之后，就可以得到pure差分隐私定义:
Ref
[1]The Algorithmic Foundation of Differential Privacy
[2]Deep Learning with Differential Privacy
[3] Rényi differential privacy
[4] Rényi Differential Privacy of the Sampled Gaussian Mechanism
[5]Subsampled Rényi Differential Privacy and Analytical Moments Accountant
