本文详细介绍了DP(差分隐私)+FL(联邦学习)的实现方法,笔者经过一年多的学习,基本上摸清了这个领域的一些套路,这里做一个总结。
距离上次发表联邦学习相关的文章已经是一年多前了,笔者接触这个领域差不多也有快两年的时间了,那时候笔者还是本科生,现在已经是快毕业的师兄了(逃),这两年对FL和DP的理解变化很大,应该说是对这个领域已经较为了解了,两年前写基于差分隐私的FL(i)这篇文章时,笔者对很多概念和算法描述的可能并不是特别到位,这里请大家以这篇文章的描述为准。
为了简单起见,这里只讲解Client端的过程,以添加Laplace噪音为例,假设Client端收到来自Server的初始参数为w s \mathbf{w}_s w s ,学习率为η \eta η,本地数据集为D \mathcal{D}D,梯度裁剪的Clip为C C C,损失函数为l ( D , w s ) l(\mathcal{D}, w_s)l (D ,w s ), 当前这一轮的隐私预算为ϵ \epsilon ϵ,那么基于DP的Client端算法为:
- 接受来自Server的初始参数w s \mathbf{w}_s w s
- 通过前向传播和反向传播计算出梯度 g \mathbf{g}g 其中计算的过程应该为,首先计算出D \mathcal{D}D中每条数据D i \mathcal{D_i}D i 的梯度g i \mathbf{g_i}g i ,进行梯度裁剪: g i = g i m a x ( 1 , ∣ g i ∣ / C ) \mathbf{g_i} = \frac{\mathbf{g_i}}{max(1, |\mathbf{g_i}| / C)}g i =ma x (1 ,∣g i ∣/C )g i 然后再求平均值,把这个过程写成公式就应该是:g = 1 ∣ D ∣ ∑ g i = 1 ∣ D ∣ ∑ a r g m i n w s l ( D i , w s ) \mathbf{g} = \frac{1}{|\mathcal{D}|} \sum \mathbf{g_i} = \frac{1}{|\mathcal{D}|} \sum arg \ min_{\mathbf{w_s}} l(\mathcal{D_i}, \mathbf{w_s})g =∣D ∣1 ∑g i =∣D ∣1 ∑a r g mi n w s l (D i ,w s )
- 进行梯度下降:w c = w s − η g \mathbf{w_c} = \mathbf{w_s} – \eta \mathbf{g}w c =w s −ηg
- 对参数添加噪音:w c ~ = w c + L a p ( Δ f / ϵ ) \widetilde{\mathbf{w_c}} = \mathbf{w_c} + Lap(\Delta f / \epsilon)w c =w c +L a p (Δf /ϵ)
上述算法可能有很多人有疑问,DP似乎不仅仅做了加噪的操作,还有很多额外的操作(比如Clip梯度),这里我将说明这些做法,以及为什么要这么做。
敏感度 Δ f \Delta f Δf 的计算
根据敏感度Δ f \Delta f Δf的定义,考虑两个临近数据集D , D ′ \mathcal{D}, \mathcal{D’}D ,D ′,两个数据集仅仅在数据D k \mathcal{D_k}D k 处不同,其他数据都是相同的,由于我们是对参数添加噪音,那么此时我们需要计算参数在D , D ′ \mathcal{D}, \mathcal{D’}D ,D ′设定下的敏感度,假设D , D ′ \mathcal{D}, \mathcal{D’}D ,D ′设定下计算出来参数为w c , w c ′ \mathbf{w_c}, \mathbf{w_c’}w c ,w c ′,敏感度的计算如下:
Δ f = m a x D , D ′ ∣ w c − w c ′ ∣ = m a x D , D ′ ∣ ( w s − η g ) − ( w s − η g ′ ) ∣ = m a x D , D ′ η ∣ g − g ′ ∣ \Delta f = max_{\mathcal{D}, \mathcal{D’}} | \mathbf{w_c} – \mathbf{w_c’} | = max_{\mathcal{D}, \mathcal{D’}}| (\mathbf{w_s} – \eta \mathbf{g}) – (\mathbf{w_s} – \eta \mathbf{g’}) | = max_{\mathcal{D}, \mathcal{D’}} \eta | \mathbf{g} – \mathbf{g’} |Δf =ma x D ,D ′∣w c −w c ′∣=ma x D ,D ′∣(w s −ηg )−(w s −ηg ′)∣=ma x D ,D ′η∣g −g ′∣
(注意这里是一范数,因为是Laplace机制。)
然后我们只需要求解∣ g − g ′ ∣ | \mathbf{g} – \mathbf{g’} |∣g −g ′∣的值就可以了,根据算法的第二步,那么有:
∣ g − g ′ ∣ = 1 ∣ D ∣ ∣ ( ∑ g i − ∑ g i ′ ) ∣ = 1 ∣ D ∣ ∣ ∑ a r g m i n w s l ( D i , w s ) − ∑ a r g m i n w s l ( D i ′ , w s ) ∣ | \mathbf{g} – \mathbf{g’} | = \frac{1}{|\mathcal{D}|} | (\sum \mathbf{g_i} – \sum\mathbf{g_i’}) | = \frac{1}{|\mathcal{D}|} | \sum arg \ min_{\mathbf{w_s}} l(\mathcal{D_i}, \mathbf{w_s}) – \sum arg \ min_{\mathbf{w_s}} l(\mathcal{D_i’}, \mathbf{w_s}) |∣g −g ′∣=∣D ∣1 ∣(∑g i −∑g i ′)∣=∣D ∣1 ∣∑a r g mi n w s l (D i ,w s )−∑a r g mi n w s l (D i ′,w s )∣
根据我们前面的假设,两个临近数据集D , D ′ \mathcal{D}, \mathcal{D’}D ,D ′,两个数据集仅仅在数据D k \mathcal{D_k}D k 处不同,那么除了D k \mathcal{D_k}D k 处所计算出来的梯度,其他的梯度应该都是相同的,所以可以消去,那么有:
∣ g − g ′ ∣ = 1 ∣ D ∣ ∣ a r g m i n w s l ( D k , w s ) − a r g m i n w s l ( D k ′ , w s ) ∣ = 1 ∣ D ∣ ∣ ( g k − g k ′ ) ∣ | \mathbf{g} – \mathbf{g’} | = \frac{1}{|\mathcal{D}|} | arg \ min_{\mathbf{w_s}} l(\mathcal{D_k}, \mathbf{w_s}) – arg \ min_{\mathbf{w_s}} l(\mathcal{D_k’}, \mathbf{w_s})| = \frac{1}{|\mathcal{D}|} | (\mathbf{g_k} – \mathbf{g_k’}) |∣g −g ′∣=∣D ∣1 ∣a r g mi n w s l (D k ,w s )−a r g mi n w s l (D k ′,w s )∣=∣D ∣1 ∣(g k −g k ′)∣
由于每一个梯度都进行过梯度裁剪,所谓梯度裁剪,其实就是把梯度的一范数限制在一定的范围内,此时:
∣ g − g ′ ∣ < = ∣ g k ∣ + ∣ g k ′ ∣ ∣ D ∣ < = 2 C ∣ D ∣ | \mathbf{g} – \mathbf{g’} |
那么敏感度就为:
Δ f = η 2 C D \Delta f = \eta \frac{2C}{\mathcal{D}}Δf =ηD 2 C
为什么要Clip?
从上一部分可以看出,如果不Clip梯度的话,g \mathbf{g}g就是一个无法被bound住的值,
也就是他的一范数的范围无法被确定,这样的话就无法计算敏感度,无法计算敏感度就不能添加DP噪音,敏感度对于差分隐私来说是一个非常重要的参数。
关于Clip的值,有很多种不同的算法,也有很多不同的加法,这里只是展示了最常见的一种,不同的加法可能会造成Clip的值不同, 如何降低敏感度是目前这个DP领域研究的一个重点。
当前这一轮的隐私预算VS全局的隐私预算
很多FL+DP的文章将当前这一轮的隐私预算与全局的隐私预算混淆,这里明确一下。
算法中提到的当前这一轮的隐私预算是指暴露Client当前信息所消耗的隐私预算,
根据差分隐私的Simple Composition,假设Client暴漏T次数据,那么这T次数据所消耗的隐私预算为T ϵ T \epsilon T ϵ
大多数FL+DP的论文中所提到的隐私预算都是指全局的隐私预算,也就是说暴露T次数据所消耗的隐私预算,按照这些论文的设定,Client端每一轮消耗的隐私预算应该等于ϵ / T \epsilon / T ϵ/T,也就是总的隐私预算除以暴露次数。
假设你全局隐私预算为ϵ \epsilon ϵ,你当然可以选择在前几次暴露使用较大的隐私预算,后几次使用较小的隐私预算,只要你能保证总的预算为ϵ \epsilon ϵ就可以,这一部分也有一些文章在进行研究,比如Adaptive DP[2]。
也有一些文章认为Simple Composition不够严谨,他没有考虑噪音的分布,还有更加严谨的 Composition以及专门针对深度学习记录隐私预算的算法,比如Moment Account,这些就不是本文研究的重点了,可以参考:https://zhuanlan.zhihu.com/p/264779199
关于本地迭代轮数
在传统的FL中,本地可以迭代多轮,而在基于FL+DP的设定下,本地迭代一轮是最好的选择。
在本地迭代多轮的情况下,无法保证每一个迭代轮数开始的时候w s \mathbf{w_s}w s 是相同的,这时无法消去除了D k \mathcal{D_k}D k 之外的其他数据计算出来的梯度,此时如果单纯对梯度进行Clip,那么得到的敏感度将是多轮迭代出来的∣ D ∣ |\mathcal{D}|∣D ∣倍,考虑到数据集的大小一般都很大,所以敏感度将会扩大几十倍甚至上百倍,所以迭代一轮是最好的选择。
以上是笔者写的使用拉普拉斯机制添加差分隐私噪音的基本过程,当然这个领域还有其他机制,比如高斯机制等,其实过程感觉都比较类似,计算Sensitivity,添加噪音等等[1,3],只不过可能加噪音的操作或者位置不同(比如有些是对梯度加噪),还有一些文章专注于FL+DP的收敛性的分析,这一块也是比较难懂的一块,笔者还在学习过程中。
笔者小硕一枚,虽然有过一些研究经验,但是本人对于DP的理解不敢说非常精通,很多时候也是摸着石头过河,笔者觉得目前网上关于DP的中文资料良莠不齐,鱼龙混杂,入门起来非常困难,笔者也是花了很长时间才搞清楚这个领域,可能有些地方写的不太准确,欢迎大家多提意见,互相交流!
[1]Wei, Kang, et al. “Federated learning with differential privacy: Algorithms and performance analysis.” IEEE Transactions on Information Forensics and Security 15 (2020): 3454-3469.
[2]Wu, Nan, et al. “The value of collaboration in convex machine learning with differential privacy.” 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 2020.
[3]Abadi, Martin, et al. “Deep learning with differential privacy.” Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016.
[4]Lee, Jaewoo, and Daniel Kifer. “Concentrated differentially private gradient descent with adaptive per-iteration privacy budget.” Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018.
[5]https://zhuanlan.zhihu.com/p/264779199
[6]Truex, Stacey, et al. “LDP-Fed: Federated learning with local differential privacy.” Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking. 2020.
Original: https://blog.csdn.net/wenzhu2333/article/details/124556920
Author: wenzhu2333
Title: 联邦学习入门笔记(四)— 基于差分隐私的FL(ii)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/618105/
转载文章受原作者版权保护。转载请注明原作者出处!