Communication-Efficient Learning of Deep Networks from Decentralized Data

Communication-Efficient Learning of Deep Networks from Decentralized Data是最早提出Federated learning这个概念的论文，可以说是FL的开山之作。

We advocate an alternative that leaves the training data distributed on the mobile devices, and learns a shared model by aggregating locally-computed updates. We term this decentralized approach Federated Learning.

之前被论文里的FedSGD和FedAvg(两个都是非常重要的算法)搞混，现在对他们总结一下。

FederatedSGD (or FedSGD)是指只有一个batch(a single batch)和Epoch数为1的算法。
令B和E分别对应与本地客户(lcoal client)的Batch-Size和Epoch数，那么FedSGD对应于B=∞和E=1。
直观理解：传统的SGD算法可以看成是梯度更新速度最快的优化算法，因为每一个sample就更新一次梯度了，这里也是一样，FedSGD是应用FL时梯度或模型更新速度最快的算法，它只要求每个local client计算一次平均梯度就可以上传到central server进行加权平均了，所以它需要的computation power是最少的(the lowest)。这也是论文把他当做基线(baseline)的原因。

因为作者想研究如何通过利用额外的计算容量来降低通信损失，而无疑基线就是计算容量最小的FedSGD算法了。这样作者就能够增加计算能力来看通信损失的变化。

由此可知，只要B≠∞和E≠1，那么此时的算法就叫做FedAvg。而FedAvg(FederatedAveraging )算法是指local client先在本地计算多次梯度并且更新权值，这时的计算成本是提升的。

上图的上半部分说的是，当我们用FedSGD算法是，具体的distributed optimization可以写成公式
其中,代表在当前模型上通过它的本地数据集计算出的平均梯度。
我们知道对任何一个客户，有，
故有

其中
上式等式说明了将每个local client的平均梯度上传到server再对这个梯度进行加权平均后更新模型的效果是和先在每个local client算出梯度并且用梯度更新本地模型 $\omega _{t}^{k}$ 后在server上对这个更新后的模型取加权平均的效果是一样的。

或者说，该等式使得从原先的上传梯度值( $g_{k}$ )模式变成了上传模型( $\omega ^{k}_{t+1}$ )模式了。

这就引出了上图的下半部分，即每个local client可以先在本地多次迭代更新模型 $\omega _{t}^{k}$ ，然后再上传到server上执行averaging step
即当我们使用FedAvg算法时，假设在 $t$ 时刻，每个local client的模型为 $\forall k:\omega _{t}^{k}$ (注意如果不加右上角的 $k$ 则代表 $t$ 时刻的全局模型)，则在Epoch=E，Batchsize=B时，local client k的模型更新为 $\omega_{t}^{k}\overset{-\eta g_{k1}}{\rightarrow} \omega _{t1}^{k}\overset{-\eta g_{k2}}{\rightarrow} \omega _{t2}^{k}\overset{-\eta g_{k3}}{\rightarrow}\cdot \cdot \cdot \overset{-\eta g_{ki}}{\rightarrow}\omega _{ti}^{k}$
意思是模型 $\omega_{t}^{k}$ 在将模型上传到server前本地更新了 $i$ 次。
接着有 $\omega _{t+1}^{k}\leftarrow \omega _{ti}^{k}$ 和 $\omega _{t+1}\leftarrow \sum_{k=1}^{K}\frac{n_k}{n}\omega_{t+1}^{k}$ 。
最后将在 $t+1$ 时刻的全局模型 $\omega_{t+1}$ 赋值给每个local client作为 $t+1$ 时刻的新模型
$\forall k:\omega _{t+1}^{k}\leftarrow \omega_{t+1}$