Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable
This addresses slow and inexact convergence in practical FL settings, though it is incremental as it builds on existing FL methods with a novel modeling approach.
The paper tackles the challenges of arbitrary client participation and data heterogeneity in Federated Learning by introducing FOCUS, an algorithm that achieves exact convergence with a linear rate, making it the first to demonstrate this result.
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.