【源头活水】联邦学习 | FedProx 算法

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

作者：知乎—lokinko

地址：https://www.zhihu.com/people/qu-xiang-mou

论文来源: 《Federated Optimization in Heterogeneous Networks》 2020 MLSys

地址：https://arxiv.org/abs/1812.06127

联邦学习在使用过程中面临的两大挑战：

数据异构（主要是用户间数据Non-IID）
系统异构（设备间通信和计算能力的差异）

本文在对 FedAvg 更新策略上稍作调整设计了 FedProx 算法并给出了收敛性证明。

FedAvg 的一般步骤：在每个 Communication Round 内，参与更新的  个设备在本地 SGD 迭代  epochs，然后在将模型上传到 Server 端进行聚合。一方面，本地迭代次数 E 的增大能减少通信成本；另一方面，不同 local objectives  在本地迭代次数过多后容易偏离全局最优解，影响收敛。（如下图所示）

《Communication-Efficient Learning of Deep Networks from Decentralized Data》

并且 FedAvg 这种固定 E 的操作没考虑到不同硬件间的差异，如果在固定时间内未完成 E epochs 的迭代就会被系统 drop 掉。

文章指出直接 drop 掉这些用户或者单纯把他们未迭代完成的模型进行聚合都会严重影响收敛的表现。因为丢掉的这些设备可能导致模型产生 bias，并且减少了设备数量也会对结果精度造成影响。

文章提出了 proximal term 来保证对这些未完成计算的 partial information 进行聚合

传统联邦学习的优化目标是最小化经验损失 Empirical risk: 

作者在此处引入 proximal term :

将原来的  变为  的目的：使得本地更新不要太过远离初始 global model，在容忍系统异构性的前提下减少 Non-IID 的影响。

同时定义了  -inexact solution，通过对 local function 的非精确求解，动态调整本地迭代次数，保证对异构系统的容忍度。

如果  满足下式则称为  的  -inexact solution. 

用  作为本地迭代的 proxy，值越小更新精度越高。

算法流程

替换了原本的 local epoch E，

改为求解  -inexact minimizer.

Experiment

验证 drop 那些 stragglers 对 FedAvg 和 FedProx 的影响

在相同更新 Epochs 下，验证异构数据对算法的影响

Conclusion

文章将 FedAvg 作为 FedProx 的特殊情况  ，对原有算法进行了微调，考虑到了数据异构和系统异构的情况，并推导了收敛证明。

通过加入 proximal term 修正项，提高了整体收敛的稳定性。

通过对本地设备动态调整迭代轮数，保证了对系统异构的容忍性。

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！