FEDERATED OPTIMIZATION IN HETEROGENEOUS NETWORKS
每日一诗：《当年万马尽腾空，就中紫骝尤最雄》
明·张居正
当年万马尽腾空，就中紫骝尤最雄。
战罢不知身着箭，飞来祇觉足生风。
北风猎猎吹原野，长河水澌血流赭。
谁言百万倒戈中，犹有弯弧射钩者。
1.概述：
联邦学习不同于传统的分布式优化的两个关键挑战:高度的系统和统计异构性。引入了一个框架，FedProx以解决联邦网络的异构性（统计异构 系统异构）。FedProx可以看作是FedAvg的泛化、重构。
对于非独立分布(统计异质性)的训练数据，框架提供收敛性保证（统计异构）；允许每个参与的设备执行可变数量的工作(系统异构性)来遵守设备级系统约束。FedProx在一组真实的联邦数据集上比FedAvg更健壮的收敛。特别是，在高度异构的环境下，FedProx表现出比FedAvg更稳定和准确的收敛行为——平均提高22%的绝对测试精度。
1.1 系统挑战
通信传输瓶颈、存储能力、计算能力、联网能力、电池、stragglers、容错
1.2 统计挑战
数据异构、非独立同分布、不平衡
关键词具体描述见本人系列相关文章
2.FedAvg：
2.1 优劣：
FedAvg在FedSGD的基础上为每个节点设定统一的E （epochs），用以增大本地计算量 提升本地模型更新的精度，进而加快全局拟合速度，减少通信次数；同时可以解决非凸损失函数的问题。
从系统异构角度：FedAvg不允许参与设备根据其系统约束执行可变数量的本地工作;相反，通常是简单地丢弃在指定时间段内无法计算E个epoch的设备
从统计角度：FedAvg在数据非独立同分布的情况下适应性弱，因此FedAvg很难在现实场景中（多为非独立同分布）进行理论分析来保证其收敛性。
2.2 算法：
2.3 参数E控制：
正确调整其优化超参数至关重要 本地epochs的大小在其拟合的过程中发挥重要作用。
1.执行更多的局部迭代允许更多的局部计算和减少通信，这可以大大提高通信受限网络的整体收敛速度。
2.由于本地客户端间不同的目标函数，局部epoch太大可能会导致每个客户端朝向其局部目标的最优更新，而不是全局目标最优——潜在地影响全局收敛，甚至导致收敛偏离。
3.强迫每个设备执行统一的工作量是不现实的(即，在FedAvg中所有客户端运行相同数量的局部epoch, E）由于系统资源异构，本地epoch大会导致客户端无法在给定的迭代伦次内完成训练而掉队。
实践中，在允许鲁棒收敛的同时，将局部epoch设为高(以减少通信)。
注意到本地epoch数量的“最佳”设置可能会在每次迭代和每个设备上改变-，可以将其设置为关于本地数据和可用系统资源的函数。比强制规定固定数量的局部epochs更好的方法是允许epochs根据iteration和本地数据与资源进行变更。来适应实际联邦学习中的异质性
3.FedProx
3.1 Tolerating partial work：
系统异构：联邦网络中的不同设备在计算硬件、网络连接和电池水平方面通常有不同的资源约束。强迫每个设备执行统一的epochs是不现实的(即，运行相同数量的局部epoch, E）。
在FedProx中，将FedAvg泛化，允许根据本地数据和可用的系统资源在本地执行可变数量的工作（相比于丢弃设备，该机制会聚合从掉线设备发送的部分结果。）换句话说，不是假设在整个训练过程中所有设备都有一个统一的γ，适应不同的设备和不同的迭代轮数产生λ。
3.2 λ-inexact solution：
λtk 衡量第k个客户端在全局第t iteration 本地计算量，因此可以根据该变量代理本地epochs次数。
3.3 近似术语：Proximal term
虽然λtk 可以帮助减轻系统异构的影响。但是由于统计异构，不太好通过λtk 来严格限制本地更新的次数，过多的本地更新仍然可能(潜在地)导致全局模型偏离。
引入了近似术语（Proximal term）来辅助FedProx应对统计异构的挑战。
在本地目标函数表达式上添加辅助式子。 有效地限制本地更新对全局模型更新的影响。
改进后的目标函数：
3.3.1 优点：
1.它通过限制本地更新，使其更接近初始(全局)模型，而不需要手动设置本地epochs的数量，解决了统计异质性的问题。（限制）
2.它允许安全地合并由系统异构性产生的可变数量的本地工作。（辅助）
该辅助函数在优化问题中很常见。
3.4 算法
references：
Li, Tian, et al. “Federated optimization in heterogeneous networks.” Proceedings of Machine Learning and Systems 2 (2020): 429-450.