通过逆误差分析揭示联邦学习收敛差异的内在机制
Convergence Analysis of Federated Learning Methods Using Backward Error Analysis
- 用逆误差分析找出各算法隐式正则项
- 发现FedAvg增加梯度方差，影响收敛速度
- 解释了FedSAM与SCAFFOLD在非独立同分布数据下的优劣
逆误差分析可识别优化方法下参数更新实际遵循的修正损失函数，其中新增项称为隐式正则项。本文研究非独立同分布数据下多种联邦学习算法的隐式正则项，解释其收敛行为差异。结果表明，FedAvg的隐式正则项使各客户端梯度偏离平均梯度，增大梯度方差，实证显示这阻碍收敛。对FedSAM和SCAFFOLD的分析显示，前者可部分消除FedAvg一阶项中的偏差，后者能完全消除一阶项偏差但无法消除二阶项偏差。该分析从新理论视角揭示联邦学习收敛特性的内在原因。
原文摘要 · Abstract (English)
Backward error analysis allows finding a modified loss function, which the parameter updates really follow under the influence of an optimization method. The additional loss terms included in this modified function is called implicit regularizer. In this paper, we attempt to find the implicit regularizer for various federated learning algorithms on non-IID data distribution, and explain why each method shows different convergence behavior. We first show that the implicit regularizer of FedAvg disperses the gradient of each client from the average gradient, thus increasing the gradient variance. We also empirically show that the implicit regularizer hampers its convergence. Similarly, we compute the implicit regularizers of FedSAM and SCAFFOLD, and explain why they converge better. While existing convergence analyses focus on pointing out the advantages of FedSAM and SCAFFOLD, our approach can explain their limitations in complex non-convex settings. In specific, we demonstrate that FedSAM can partially remove the bias in the first-order term of the implicit regularizer in FedAvg, whereas SCAFFOLD can fully eliminate the bias in the first-order term, but not in the second-order term. Consequently, the implicit regularizer can provide a useful insight on the convergence behavior of federated learning from a different theoretical perspective.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。