提出首个在任意客户端参与下实现线性收敛的联邦学习算法
Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable
- 用时变图建模客户端任意参与与本地更新
- 新算法FOCUS在任意参与下仍实现线性收敛
- 适合关注实际联邦学习收敛性的研究者
本文针对实际联邦学习中普遍存在的客户端任意参与和数据异构性带来的根本挑战展开研究。现有主流的FedAvg类算法因需递减学习率以缓解这些问题，难以实现精确收敛且收敛速度慢。为此，我们引入随机矩阵及相应时变图作为新型建模工具，精准捕捉客户端任意参与动态与本地更新过程。基于此，我们从去中心化视角重新设计联邦学习算法，提出FOCUS（Federated Optimization with Exact Convergence via Push-pull Strategy），一种可证明收敛的算法，有效克服前述两大挑战。具体而言，我们严格证明了FOCUS在任意客户端参与下均能实现精确线性收敛，成为首个达成此重要结果的工作。
原文摘要 · Abstract (English)
This work tackles the fundamental challenges in Federated Learning (FL) posed by arbitrary client participation and data heterogeneity, prevalent characteristics in practical FL settings. It is well-established that popular FedAvg-style algorithms struggle with exact convergence and can suffer from slow convergence rates since a decaying learning rate is required to mitigate these scenarios. To address these issues, we introduce the concept of stochastic matrix and the corresponding time-varying graphs as a novel modeling tool to accurately capture the dynamics of arbitrary client participation and the local update procedure. Leveraging this approach, we offer a fresh decentralized perspective on designing FL algorithms and present FOCUS, Federated Optimization with Exact Convergence via Push-pull Strategy, a provably convergent algorithm designed to effectively overcome the previously mentioned two challenges. More specifically, we provide a rigorous proof demonstrating that FOCUS achieves exact convergence with a linear rate regardless of the arbitrary client participation, establishing it as the first work to demonstrate this significant result.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。