【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD

這篇具有很好參考價值的文章主要介紹了【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（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…梯度實際上是對用戶數(shù)據(jù)進(jìn)行函數(shù)變換，在訓(xùn)練數(shù)據(jù)時攜帶信息，可能有泄露梯度隱私的風(fēng)險。

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（隨機(jī)梯度）： $g_i=\frac{\partial \ l(w,x_i,y_i)}{\partial w}=(x_i^Tw-y_i)x_i$

2…通信代價

影響通信代價的幾個因素：參數(shù)的維度、梯度的維度；網(wǎng)絡(luò)延遲、帶寬；每次參與通信的客戶端個數(shù)
減少通信代價的方式：減少單次傳輸代價（參數(shù)壓縮、量化、只傳輸重要梯度）；減少通信次數(shù)；部分設(shè)備參與通訊（節(jié)點調(diào)度）
判斷通信代價的高低，更加可信的指標(biāo)是達(dá)到收斂時的總通信數(shù)據(jù)量（總通信數(shù)據(jù)量 = 通信次數(shù) * 單次傳輸?shù)臄?shù)據(jù)量）

SCAFFOLD

證明FedAvg方法，在數(shù)據(jù)是異構(gòu)的（non-iid）時會出現(xiàn)client-drift（客戶漂移），導(dǎo)致不穩(wěn)定和緩慢的收斂；

提出了SCAFFOLD算法，通過增加一個額外的參數(shù) control variate（使用控制變量，減小方差），來修正 client-drift 問題；

用嚴(yán)格的數(shù)學(xué)理論證明了該算法是收斂的；

實驗部分證明了這種算法是不受客戶端數(shù)據(jù)異構(gòu)性（數(shù)據(jù)分布）的影響，并且可以加快收斂速度，從而顯著減少通信次數(shù)。

一、算法核心

	更新過程	優(yōu)缺
SGD	在本地更新一次就進(jìn)行一次通信	路徑與server理想的更新路徑相近，但是通信代價大
FedAvg	在本地更新k次才進(jìn)行一次通信	由于Non-IID，路徑與server理想的更新路徑發(fā)生了偏移，即client-drift，導(dǎo)致收斂速度緩慢
SCAFFOLD	在本地更新k次才進(jìn)行一次通信	增加了修正項，使每次本地更新被拉回到理想的更新路徑附近，收斂速度較快

用圖來進(jìn)行講解：

左邊為FedAvg出現(xiàn)client-drift的分析（兩個客戶端），其中橙色方塊為客戶端損失函數(shù)的最優(yōu)，藍(lán)色方塊為全局最優(yōu)，藍(lán)色線為客戶端的更新方向，綠色線為中心服務(wù)器的更新方向?？梢钥闯觯肿顑?yōu)不是客戶端損失函數(shù)最優(yōu)的平均，兩者間的差距造成了client-drift問題（綠色線和空白方格間的距離）；
右邊為SCAFFOLD在單客戶端上的更新步驟，其中紅色線為（c-ci）修正。可以看出，使用本文的修正，可以將更新方向從指向局部最優(yōu)修正到指向全局最優(yōu)。

【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD

算法理解：

SCAFFOLD算法主要是計算客戶端和服務(wù)器端的差異來進(jìn)行修正（不受客戶抽樣的影響），相比FedAvg只是加了一個修正項 $c-c_i$ ；
可以有效地解決本地更新時的client-drift，讓每個客戶端在本地更新的時候“看到”其他客戶端更新的信息（不是真的看到，而是利用客戶端數(shù)據(jù)的相似性進(jìn)行猜測），算法中不僅要更新參數(shù)，還要更新這種猜測；
可以克服客戶端異質(zhì)性（異質(zhì)性視為不同客戶端之間更新中引入的“客戶端方差”，需盡力減少)。

【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（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)$ 控制變量局部更新（額外傳遞本地數(shù)據(jù)來計算中心服務(wù)器上的梯度或重用之前計算的梯度；前者更穩(wěn)定，后者計算成本低且通常夠用，用后者）： $\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)$
中心服務(wù)器	聚合更新： $\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)$

【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD

二、實驗

主要發(fā)現(xiàn)：在所有參數(shù)范圍內(nèi)，SCAFFOLD始終優(yōu)于SGD和FedAvg；局部更新次數(shù)的好處/壞處，取決于算法和客戶數(shù)據(jù)的相似性。

模擬數(shù)據(jù)：
【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD
K為局部更新次數(shù)，G可衡量梯度差異（從左到右異質(zhì)性增大）；可看出提出的算法在數(shù)據(jù)異質(zhì)性程度改變時，具有更好的適應(yīng)性。

EMNIST數(shù)據(jù)：
【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD 衡量使用更多局部更新的好處/壞處；縱向增加局部更新次數(shù)，橫向增加客戶相似性，通過輪數(shù)反應(yīng)收斂速度；可看出效果上 SCAFFOLD > FedAvg > FedProx 【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD
左圖研究了客戶端抽樣彈性，縱向改變客戶端抽樣比例，橫向改變客戶相似性；可看出在抽樣客戶端數(shù)目及異質(zhì)性相同時，SCAFFOLD有更好表現(xiàn)；

右圖展示了三種算法的最佳測試精度，使用2層全連接神經(jīng)網(wǎng)絡(luò)(非凸)訓(xùn)練1k輪，本地方法每輪5個epoch(25步)，20%的客戶每輪取樣；可看出SCAFFOLD的準(zhǔn)確率最高，SGD的準(zhǔn)確率最低，SGD基本不受相似度的影響，而其他兩種算法會隨著客戶端的相似度而提高。

三、總結(jié)

優(yōu)點：文章來源地址http://www.zghlxwxcb.cn/news/detail-419121.html

FedAvg可能會因不同client的梯度差異，收斂速度受到嚴(yán)重影響（即使使用全梯度且全部設(shè)備參與每輪通信），甚至可能比SGD慢；
而SCAFFOLD對本地更新策略進(jìn)行改進(jìn)，利用control variates克服client drift，有較快的收斂速度，且不受client數(shù)據(jù)分布的影響，能有效減少通信次數(shù)；
已證明SCAFFOLD其至少和SGD一樣快，且對任意異構(gòu)數(shù)據(jù)收斂；可以利用客戶端的相似性，進(jìn)一步減少通信；相對不受客戶抽樣帶來的方差減少率的影響。

不足：

每次與Server通信，不僅要傳模型的參數(shù)，還要傳control variates(梯度和參數(shù)向量維度一樣)，增加了單次通信代價（2倍）；
要求每個客戶端是stateful的，因此只適用于少量的客戶端（thousands級別）；
使用上一輪的梯度狀態(tài)去猜測下一輪梯度的可能方向，這要求所有損失函數(shù)是平滑的。

思考（參考他人博客）：

能否只用最后一個梯度去更新 $c_i$ ；
用總的通信量來評估模型優(yōu)劣可能更有可信度；
$c_i$ 在第3輪被選中，但下次可能在第100輪才被選中，這時的 $c_i$ 存的還是第3輪被選中時參數(shù)所在位置的梯度，是否會造成誤差。

FedPD

FedBN

在局部模型中加入批量歸一化層（BN），解決聯(lián)邦學(xué)習(xí)數(shù)據(jù)異構(gòu)性中 feature shift 情況（之前很多文章都是研究label shift或client shift）

一、算法核心

y為標(biāo)簽，x為特征，feature shift定義為以下情況：

covariate shift：所有客戶的Pi(y|x)是相同的，不同客戶之間的邊緣分布Pi(x)是不同的；
concept shift：不同客戶的條件分布Pi(x|y)不同，但P(y)相同

例如：醫(yī)學(xué)成像中不同的掃描儀/傳感器，自動駕駛中不同的環(huán)境分布(公路和城市)，使得本地客戶端的樣本分布不同于其他客戶端。

與FedAvg類似，F(xiàn)edBN也進(jìn)行局部更新和模型聚合；不同的是，F(xiàn)edBN假設(shè)局部模型有批量歸一化層（BN），且BN的參數(shù)不參與聚合。思想是直接把BN層的所有參數(shù)保留在本地，而把其他層的參數(shù)用于全局聚合，待服務(wù)端返回全局模型后，再與本地的BN參數(shù)結(jié)合構(gòu)成本地模型，這在保護(hù)數(shù)據(jù)隱私的同時也實現(xiàn)了模型個性化設(shè)計。
【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD

二、實驗

使用benchmark和real-world datasets兩種數(shù)據(jù)進(jìn)行實驗，在卷積層和全連接層后面加入BN層。

benchmark：SVHN, USPS, MNIST-M, MNIST, SynthDigits這五個來自不同域且?guī)в衒eature shift性質(zhì)的數(shù)據(jù)集（不同域的數(shù)據(jù)具有異構(gòu)的性質(zhì)，但具有相同的標(biāo)簽和標(biāo)簽分布）；為控制無關(guān)因素，使BN的作用在實驗中更加易于觀察，對這五個數(shù)據(jù)集進(jìn)行預(yù)處理（如客戶之間樣本數(shù)量不平衡問題）

【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD 分析收斂速度。與收斂性分析的結(jié)論相同，聚合模型在每個數(shù)據(jù)集（也就是每個客戶端）上的收斂曲線顯示，F(xiàn)edBN的收斂比FedAvg更快更光滑。
【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD 從左到右依次研究了局部模型訓(xùn)練迭代次數(shù)、本地數(shù)據(jù)集大小、統(tǒng)計異質(zhì)性對準(zhǔn)確率的影響：不同迭代次數(shù)(E)下，F(xiàn)edBN和FedAvg測試集上的準(zhǔn)確率曲線顯示，在各種E上FedBN的準(zhǔn)確率穩(wěn)定地超過FedAvg；每個客戶端持有的Non-IID數(shù)據(jù)越少，F(xiàn)edBN的優(yōu)越性越明顯；更多的客戶端對應(yīng)更小的異構(gòu)性，在所有異質(zhì)性水平上，F(xiàn)edBN都比FedAvg實現(xiàn)了更高的測試精度。

【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD

比較不同算法的最高準(zhǔn)確度：FedBN實現(xiàn)了最高的精度；FedBN對SVHN數(shù)據(jù)集的性能最為顯著，SVHN的圖像外觀與其他圖像有很大的不同。
【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD

三、總結(jié)

優(yōu)點：

在feature shift場景下，F(xiàn)edBN的收斂比FedAvg更快更光滑；
有望與其他方法和框架，例如客戶端選擇策略，聚合策略等等相結(jié)合；
BN本身的優(yōu)化版本可以嘗試應(yīng)用于此。

到了這里，關(guān)于【聯(lián)邦學(xué)習(xí)論文閱讀】常用算法理解（SCAFFOLD、FedPD、FedBN）-目前僅SCAFFOLD的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！