Date Time

21/04/4 11:22

Author

icebound

联邦学习理解及实现

最近毕设要接触到联邦学习，在这里记录一下对联邦学习的理解，防止以后忘了。

机器学习小白一个，可能有错，欢迎指出！

FedAvg以及FedSGD的实现

谈到联邦学习，最重要的一个点是梯度融合时的策略。如何巧妙地融合各个客户端之间的梯度，以保证最优的模型效果，是联邦学习中需要着重研究的问题。FedAvg是一个经典且简单的策略。

一句话描述：所有client的梯度取平均值得到最终梯度。具体证明如下。

机器学习问题建模

首先，对于一切损失函数非凸的机器学习问题(例如神经网络)，都可以表示为以下式子：

\min _{w \in \mathbb{R}^{d}} f(w) \quad where \quad f(w) \stackrel{\text { def }}{=} \frac{1}{n} \sum_{i=1}^{n} f_{i}(w)

$f(w)$ $w$ $f_{i}(w)$ 是第i个数据的损失，或者说第i个数据的代价。上面式子的意思是：一切非凸机器学习问题，都是一个最小化目标函数的问题，这个目标函数是由每个数据的损失平均贡献的。

$f_{i}(w)=$ $\ell\left(x_{i}, y_{i} ; w\right)$ $\left(x_{i}, y_{i}\right)$ $w$ $f_i(w)$ $K$ $\mathcal{P}_{k}$ $n_{k}=\left|\mathcal{P}_{k}\right|$ ，那么我们可以改写上面的式子为：

f(w)=\sum_{k=1}^{K} \frac{n_{k}}{n} F_{k}(w) \quad where \quad F_{k}(w)=\frac{1}{n_{k}} \sum_{i \in \mathcal{P}_{k}} f_{i}(w)

如果数据呈IID，即独立同分布，那么根据期望的性质可以得到：

\mathbb{E}_{\mathcal{P}_{k}}\left[F_{k}(w)\right]=f(w)

当然，这个独立同分布不一定能实现，所以需要后面进一步讨论。

SGD算法

SGD算法全称是：stochastic gradient descent，随机梯度下降法，是一种常见的梯度下降算法。

和SGD相对的算法是BGD：batch gradient descent，批量梯度下降法BGD。BGD在每次更新时，要用到所有的样本来得到一个标准梯度，然后沿着这个梯度更新。因此对于凸优化问题BGD肯定可以得到一个收敛的解。而SGD则是每次取一个样本，来代替整个样本集合进行梯度下降，这样虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解发展的。还有一种mini-batch梯度下降，是这两个方法的折中。

根据一些证明，SGD和BGD都能收敛，所以都是可用的。因为联邦学习是分布式的，所以肯定只能用SGD。

基线算法FederatedSGD

定义一个值C：每次参与联邦学习聚合的client数量占总client数量的比例。当C=1时，代表全员参与聚合。FedSGD就是在C=1时的一个基线算法，也就是每次让所有client参与，把本地所有的数据进行训练，在本地只训练一次，然后进行聚合（说实话我很迷惑，这不应该叫FedBGD吗）。

聚合时的操作是这样的：

$\eta$ $k$ $g_{k}=\nabla F_{k}\left(\omega_{t}\right)$ $w_t$ $g_k$ 的平均值对整个模型进行更新：

w_{t+1} \leftarrow w_{t}-\eta \sum_{k=1}^{K} \frac{n_{k}}{n} g_{k}

$f(w)$ 的变化可以这么表示：

\sum_{k=1}^{K} \frac{n_{k}}{n} g_{k}=\nabla f(\omega)

所以，这个式子也可以写为：

\forall k, \quad \omega_{t+1}^{k} \leftarrow \omega_{t}+\eta g_{k}

$g_k$ 那一项换掉，可以得到：

\omega_{t+1} \leftarrow \sum_{k=1}^{K} \frac{n_{k}}{n} \omega_{t+1}^{k}

上面这个式子就很清晰了，新的模型=每个设备的权重*每个设备的模型。在聚合之前，每个设备自己还可以自娱自乐，自己迭代多轮：

\omega^{k} \leftarrow \omega^{k}+\eta \nabla F_{k}\left(\omega_{k}\right)

至此，FedSGD的操作就介绍完毕了，其实就是个求均值。

Federated Averaging

上面介绍了FedSGD，然而FedSGD其实是FedAvg的特殊情况。

我们定义三个参数：

$C$ ：每轮参与联邦学习聚合的client数量占总client数量的比例。

$E$ ：每个client在本地的训练次数（即自娱自乐的次数）。

$B$ ：每个client在本地训练时的BatchSize。

然后FedAvg可以表示为如下伪代码：

$w_{0}$ $t=1,2, \ldots$ do

\begin{array}{l} m \leftarrow \max (C \cdot K, 1) \\ S_{t} \leftarrow \text { (random set of } m \text { clients) } \end{array}

$k \in S_{t}$ in parallel do

\begin{aligned} w_{t+1}^{k} & \leftarrow \text { ClientUpdate }\left(k, w_{t}\right) \\ \end{aligned} \\ w_{t+1} \leftarrow \sum_{k=1}^{K} \frac{n_{k}}{n} w_{t+1}^{k}

$(k, w):$ $k$

$\mathcal{B} \leftarrow\left(\right.$ $\mathcal{P}_{k}$ $\left.B\right)$

$i$ $E$ $b \in \mathcal{B}$ do

w \leftarrow w-\eta \nabla \ell(w ; b)

$w$ to server

可以看出，当C=B=1，且B为无穷大时，FedAvg与FedSGD一样。

至此，FedAvg的原理也介绍完毕了。

HierFAVG策略

具体请见这篇论文：https://arxiv.org/abs/1905.06641

目前来说，FedAvg是基于云的，client连到云上，然后进行FL。这里有一个巨大缺陷：设备连接时产生了巨大的网络资源消耗，与云服务器的连接也不一定稳定，一旦断掉很麻烦。所以，可以引入边缘计算来解决这个问题。但是边缘节点毕竟接入量有限，可能导致训练性能的大量损失。

因此，上面那篇论文提出了一种边云协同策略，具体来说就是：

首先，client先训练，然后把参数上传到边缘
边缘进行聚合，当边缘聚合k轮后，把聚合好的数据上传到云。
云总共聚合n轮。

所以总共训练n*k论，根据那个文章，训练性能还不错。

Icebound

icebound-area