Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable

Area of Science:

• Machine Learning
• Distributed Systems
• Optimization Theory

Background:

• Federated Learning (FL) faces challenges with non-uniform client availability and diverse data distributions.
• Existing algorithms like FedAvg often require decaying learning rates for convergence, leading to slow performance.
• These issues hinder the practical deployment and efficiency of FL systems.

Purpose of the Study:

• To develop a Federated Learning algorithm that guarantees exact convergence.
• To address the challenges of arbitrary client participation and data heterogeneity in FL.
• To provide a novel theoretical framework for analyzing FL dynamics.

Main Methods:

• Introduction of stochastic matrices and time-varying graphs to model FL dynamics.
• Development of FOCUS (Federated Optimization with Exact Convergence via Push-pull Strategy).
• Rigorous mathematical proofs to demonstrate convergence properties.

Main Results:

• FOCUS achieves provable exact convergence with a linear rate.
• The algorithm effectively handles arbitrary client participation.
• Demonstrates superior performance compared to existing methods in heterogeneous data settings.

Conclusions:

• FOCUS offers a significant advancement in Federated Learning by ensuring exact and efficient convergence.
• The novel modeling approach provides a new perspective on decentralized optimization.
• This work paves the way for more robust and practical FL deployments.