联邦学习论文阅读：Federated Learning with Non-IID Data

论文简介

论文名称：Federated Learning with Non-IID Data
作者：Yue Zhao
论文链接：https://arxiv.org/abs/1806.00582
发表时间：2018年

写在前面

这篇论文的结论比较怪：在CIFAR10上进行实验，发现如果能给所有客户端共享5%的数据集，可以使模型的准确率提高30%。而这个结论明显触犯了联邦学习的天条，客户端的数据是不可能共享的。
后来请教了导师，导师的答复是：这篇论文是比较早的工作了，他的贡献在于强调了Non-IID的重要性，他的方法也不重要，毕竟真实情况下也没数据可以共享。。。

FL的两大挑战

Communication challenge
Statistical challenge

论文动机

FedAvg在non-IID数据下的准确率显著降低。

图1

FedAvg在Non-IID数据上的表现

IID数据的构造法

训练集平均划分成10个客户端；每个客户端随机分配了超过10个类的平均分布。

Non-IID数据的构造法

1-class non-IID：每个客户端只有一个类
2-class non-IID：数据排序后分成20个部分，每个客户端随机分配到2个部分的2类。

non-IID数据引起的权重差异

从图1可以看出来，2-class non-IID对准确率造成的影响比1-class造成的影响要少，说明FedAvg的准确率会受到数据分布的偏度影响。比较FedAvg和SGD的方法：在相同的权值初始化的情况下，查看相对于SGD的权值的差异。

$$ weight\ divergence = \|t w^{FedAvg}-w^{SGD} \| / \| w^{SGD} \| $$

随着数据的Non-IID性增加（IID → 2-class non-IID → 1-class non-IID），网络中所有层的权重差异都在增加，因此可以预见权重差异和数据的偏度是有关联的（如下图图2）。

图2

权重差异的根源

权重差异的根源是由于每个客户端上的数据分布和类别分布之间的距离。

在Non-IID的数据分布上，FedAvg的表现欠佳，客户端权值分散与中央服务器权值分散的差异会越来越大。

如何约束权重差异

作者推导出如下公式：

造成权重差异的两个因素（Remark 3.2）

公式阐明：第$m$次同步后的权值差异有2部分构成：

第$m-1$次同步后的权值差异
客户端$k$上的数据分布与数据总体的实际分布的概率距离引起的权重差异。

客户端初始参数不同对权重差异的影响（Remark 3.3）

第$m-1$次同步后，权重差异以下式的方式增加：

$$ \sum^K_{k=1} \frac{n^{(k)} (a^{(k)})^T}{\sum^K_{k=1} n^{(k)}} $$

若不同客户端初始化$w$不同，则即使数据满足IID，仍然会使得权重差异增大，进而降低模型精度。

客户端初始参数相同时权重差异的影响因素（Remark 3.4）

所有客户端初始化权重相同时，权重差异受如下公式影响：

$$ \sum^C_{i=1} \| p^{(k)}(y=i) -p(y=i) \| $$

上式为客户端k数据分布和数据总分布之间的搬土距离（Earth Mover’s Distance, EMD）。EMD受如下因素影响：

学习率$\eta$
同步次数$T$
最大梯度$g_{max}(w_{mT-1-k}^{(c)})$

论文提出的解决方案

数据共享策略：创建一个在边缘设备之间全局共享的小数据子集。

按照作者的实验，在CIFAR-10数据集上，共享5%的数据，可以使准确率提高30%。
（可是共享5%的数据集，不就违反隐私条约了吗？）

联邦学习论文阅读：Federated Learning with Non-IID Data

论文简介

写在前面

FL的两大挑战

论文动机