聯邦學習的收斂性分析

在聯邦學習中，我們的目標是分析全局模型的收斂性，考慮設備異構性（不同用戶的本地訓練輪次不同）和數據異質性（用戶數據分布不均勻）。以下推導從全局模型更新開始，逐步引入假設并推導期望損失的遞減關系，最終給出收斂性結論。

1. 全局模型更新與泰勒展開

全局模型更新

在聯邦學習中，設全局模型在第 $t$ 輪為 $g_t$，共有 $U$ 個用戶參與訓練。每個用戶 $k$ 從全局模型 $g_t$ 開始（即 $w_t^{k,0}=g_t$），進行 $l_k^t$ 輪本地梯度下降更新：

$$w_t^{k,i+1}=w_t^{k,i}?\eta ?{\mathcal{G}}_t^{k,i},$$

其中 $\eta$ 是學習率，$?{\mathcal{G}}_t^{k,i}$ 是用戶 $k$ 在第 $i$ 輪本地訓練時的梯度。經過 $l_k^t$ 輪訓練后，用戶 $k$ 的本地模型為：

$$w_t^{k,l_k^t}=w_t^{k,0}?\eta \sum _{i=0}^{l_k^t?1}?{\mathcal{G}}_t^{k,i}=g_t?\eta \sum _{i=0}^{l_k^t?1}?{\mathcal{G}}_t^{k,i}.$$

全局模型通過聚合所有用戶的本地模型得到：

$$g_{t+1}=\frac{1}{U}\sum _{k=1}^U{w}_t^{k,l_k^t}=g_t?\frac{\eta }{U}\sum _{k=1}^U\sum _{i=0}^{l_k^t?1}?{\mathcal{G}}_t^{k,i}.$$

泰勒展開

為了分析全局損失 $F(g_{t+1})$ 的變化，我們對 $F(g_{t+1})$ 在 $g_t$ 處進行二階泰勒展開：

$$F(g_{t+1})\approx F(g_t)+?F(g_t{)}^T(g_{t+1}?g_t)+\frac{1}{2}(g_{t+1}?g_t{)}^T{?}^{2}F(g_t)(g_{t+1}?g_t).$$

代入 $g_{t+1}?g_t=?\frac{\eta }{U}{\sum }_{k=1}^U{\sum }_{i=0}^{l_k^t?1}?{\mathcal{G}}_t^{k,i}$：

F ( g t + 1 ) ≈ F ( g t ) ? η U ? F ( g t ) T ( ∑ k = 1 U ∑ i = 0 l k t ? 1 ? G t k , i ) + η 2 2 ( 1 U ∑ k = 1 U ∑ i = 0 l k t ? 1 ? G t k , i ) T ? 2 F ( g t ) ( 1 U ∑ k = 1 U ∑ i = 0 l k t ? 1 ? G t k , i ) . F(g_{t+1}) \approx F(g_t) - \frac{\eta}{U} \nabla F(g_t)^T \left( \sum_{k=1}^U \sum_{i=0}^{l_k^t - 1} \nabla \mathcal{G}_t^{k, i} \right) + \frac{\eta^2}{2} \left( \frac{1}{U} \sum_{k=1}^U \sum_{i=0}^{l_k^t - 1} \nabla \mathcal{G}_t^{k, i} \right)^T \nabla^2 F(g_t) \left( \frac{1}{U} \sum_{k=1}^U \sum_{i=0}^{l_k^t - 1} \nabla \mathcal{G}_t^{k, i} \right). F(gt+1?)≈F(gt?)?Uη??F(gt?)T