【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD-Toy模板网

这篇具有很好参考价值的文章主要介绍了【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

SCAFFOLD（ICML-2020）：SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
FedPD：https://arxiv.org/abs/2005.11418
FedBN（ICLR 2021）：FEDBN: FEDERATED LEARNING ON NON-IID FEATURES VIA LOCAL BATCH NORMALIZATION

杂七杂八

1…梯度实际上是对用户数据进行函数变换，在训练数据时携带信息，可能有泄露梯度隐私的风险。

least squares regression（最小二乘回归）： $\underset{w}{min}\sum_{i=1}^{n}l(w,x_i,y_i),\ \texttt{where} \ l(w,x_i,y_i)=\frac{1}{2}(x_i^Tw-y_i)^2$
stochastic gradient（随机梯度）： $g_i=\frac{\partial \ l(w,x_i,y_i)}{\partial w}=(x_i^Tw-y_i)x_i$

2…通信代价

影响通信代价的几个因素：参数的维度、梯度的维度；网络延迟、带宽；每次参与通信的客户端个数
减少通信代价的方式：减少单次传输代价（参数压缩、量化、只传输重要梯度）；减少通信次数；部分设备参与通讯（节点调度）
判断通信代价的高低，更加可信的指标是达到收敛时的总通信数据量（总通信数据量 = 通信次数 * 单次传输的数据量）

SCAFFOLD

证明FedAvg方法，在数据是异构的（non-iid）时会出现client-drift（客户漂移），导致不稳定和缓慢的收敛；

提出了SCAFFOLD算法，通过增加一个额外的参数 control variate（使用控制变量，减小方差），来修正 client-drift 问题；

用严格的数学理论证明了该算法是收敛的；

实验部分证明了这种算法是不受客户端数据异构性（数据分布）的影响，并且可以加快收敛速度，从而显著减少通信次数。

一、算法核心

	更新过程	优缺
SGD	在本地更新一次就进行一次通信	路径与server理想的更新路径相近，但是通信代价大
FedAvg	在本地更新k次才进行一次通信	由于Non-IID，路径与server理想的更新路径发生了偏移，即client-drift，导致收敛速度缓慢
SCAFFOLD	在本地更新k次才进行一次通信	增加了修正项，使每次本地更新被拉回到理想的更新路径附近，收敛速度较快

用图来进行讲解：

左边为FedAvg出现client-drift的分析（两个客户端），其中橙色方块为客户端损失函数的最优，蓝色方块为全局最优，蓝色线为客户端的更新方向，绿色线为中心服务器的更新方向。可以看出，全局最优不是客户端损失函数最优的平均，两者间的差距造成了client-drift问题（绿色线和空白方格间的距离）；
右边为SCAFFOLD在单客户端上的更新步骤，其中红色线为（c-ci）修正。可以看出，使用本文的修正，可以将更新方向从指向局部最优修正到指向全局最优。

【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD

算法理解：

SCAFFOLD算法主要是计算客户端和服务器端的差异来进行修正（不受客户抽样的影响），相比FedAvg只是加了一个修正项 $c-c_i$ ；
可以有效地解决本地更新时的client-drift，让每个客户端在本地更新的时候“看到”其他客户端更新的信息（不是真的看到，而是利用客户端数据的相似性进行猜测），算法中不仅要更新参数，还要更新这种猜测；
可以克服客户端异质性（异质性视为不同客户端之间更新中引入的“客户端方差”，需尽力减少)。

【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD

	SCAFFOLD	FedAvg
客户端 i	模型局部更新k次： $\leftarrow x+\frac{\eta_{g}}{\textup{l}\mathcal{S}\textup{l}} \sum_{i \in \mathcal{S}}\left(y_{i}-x\right)$ 控制变量局部更新（额外传递本地数据来计算中心服务器上的梯度或重用之前计算的梯度；前者更稳定，后者计算成本低且通常够用，用后者）： $\boldsymbol{c}_{i}^{+} \leftarrow \begin{cases}\text { Option I. } & g_{i}(\boldsymbol{x}), \text { or } \\ \text { Option II. } & \boldsymbol{c}_{i}-\boldsymbol{c}+\frac{1}{K_{η_l}}\left(\boldsymbol{x}-\boldsymbol{y}_{i}\right)\end{cases}$	局部更新k次（ $η_l$ 为局部步长）： $y_i ← y_i − η_lg_i(y_i)$
中心服务器	聚合更新： $\begin{cases} \boldsymbol{x} \leftarrow \boldsymbol{x}+\frac{\eta_{g}}{\textup{l}\mathcal{S}\textup{l}} \sum_{i \in \mathcal{S}}\left(\boldsymbol{y}_{i}-\boldsymbol{x}\right) \\ \boldsymbol{c} \leftarrow \boldsymbol{c}+\frac{1}{N} \sum_{i \in \mathcal{S}}\left(\boldsymbol{c}_{i}^{+}-\boldsymbol{c}_{i}\right)\end{cases}$	聚合更新（ $η_g$ 为全局步长， $y_i − x$ 为客户端 i 的更新）： $\frac{η_g}{\textup{l}\mathcal{S}\textup{l}} \sum_{i∈\mathcal{S}}(y_i − x)$

【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD

二、实验

主要发现：在所有参数范围内，SCAFFOLD始终优于SGD和FedAvg；局部更新次数的好处/坏处，取决于算法和客户数据的相似性。

模拟数据：
【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD
K为局部更新次数，G可衡量梯度差异（从左到右异质性增大）；可看出提出的算法在数据异质性程度改变时，具有更好的适应性。

EMNIST数据：
【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD 衡量使用更多局部更新的好处/坏处；纵向增加局部更新次数，横向增加客户相似性，通过轮数反应收敛速度；可看出效果上 SCAFFOLD > FedAvg > FedProx
左图研究了客户端抽样弹性，纵向改变客户端抽样比例，横向改变客户相似性；可看出在抽样客户端数目及异质性相同时，SCAFFOLD有更好表现；

右图展示了三种算法的最佳测试精度，使用2层全连接神经网络(非凸)训练1k轮，本地方法每轮5个epoch(25步)，20%的客户每轮取样；可看出SCAFFOLD的准确率最高，SGD的准确率最低，SGD基本不受相似度的影响，而其他两种算法会随着客户端的相似度而提高。

三、总结

优点：文章来源地址https://www.toymoban.com/news/detail-419121.html

FedAvg可能会因不同client的梯度差异，收敛速度受到严重影响（即使使用全梯度且全部设备参与每轮通信），甚至可能比SGD慢；
而SCAFFOLD对本地更新策略进行改进，利用control variates克服client drift，有较快的收敛速度，且不受client数据分布的影响，能有效减少通信次数；
已证明SCAFFOLD其至少和SGD一样快，且对任意异构数据收敛；可以利用客户端的相似性，进一步减少通信；相对不受客户抽样带来的方差减少率的影响。

不足：

每次与Server通信，不仅要传模型的参数，还要传control variates(梯度和参数向量维度一样)，增加了单次通信代价（2倍）；
要求每个客户端是stateful的，因此只适用于少量的客户端（thousands级别）；
使用上一轮的梯度状态去猜测下一轮梯度的可能方向，这要求所有损失函数是平滑的。

思考（参考他人博客）：

能否只用最后一个梯度去更新 $c_i$ ；
用总的通信量来评估模型优劣可能更有可信度；
$c_i$ 在第3轮被选中，但下次可能在第100轮才被选中，这时的 $c_i$ 存的还是第3轮被选中时参数所在位置的梯度，是否会造成误差。

FedPD

FedBN

在局部模型中加入批量归一化层（BN），解决联邦学习数据异构性中 feature shift 情况（之前很多文章都是研究label shift或client shift）

一、算法核心

y为标签，x为特征，feature shift定义为以下情况：

covariate shift：所有客户的Pi(y|x)是相同的，不同客户之间的边缘分布Pi(x)是不同的；
concept shift：不同客户的条件分布Pi(x|y)不同，但P(y)相同

例如：医学成像中不同的扫描仪/传感器，自动驾驶中不同的环境分布(公路和城市)，使得本地客户端的样本分布不同于其他客户端。

与FedAvg类似，FedBN也进行局部更新和模型聚合；不同的是，FedBN假设局部模型有批量归一化层（BN），且BN的参数不参与聚合。思想是直接把BN层的所有参数保留在本地，而把其他层的参数用于全局聚合，待服务端返回全局模型后，再与本地的BN参数结合构成本地模型，这在保护数据隐私的同时也实现了模型个性化设计。
【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD

二、实验

使用benchmark和real-world datasets两种数据进行实验，在卷积层和全连接层后面加入BN层。

benchmark：SVHN, USPS, MNIST-M, MNIST, SynthDigits这五个来自不同域且带有feature shift性质的数据集（不同域的数据具有异构的性质，但具有相同的标签和标签分布）；为控制无关因素，使BN的作用在实验中更加易于观察，对这五个数据集进行预处理（如客户之间样本数量不平衡问题）

【联邦学习论文阅读】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前仅SCAFFOLD 分析收敛速度。与收敛性分析的结论相同，聚合模型在每个数据集（也就是每个客户端）上的收敛曲线显示，FedBN的收敛比FedAvg更快更光滑。
从左到右依次研究了局部模型训练迭代次数、本地数据集大小、统计异质性对准确率的影响：不同迭代次数(E)下，FedBN和FedAvg测试集上的准确率曲线显示，在各种E上FedBN的准确率稳定地超过FedAvg；每个客户端持有的Non-IID数据越少，FedBN的优越性越明显；更多的客户端对应更小的异构性，在所有异质性水平上，FedBN都比FedAvg实现了更高的测试精度。