On the Convergence of Federated Averaging with Cyclic Client Participation
This work addresses the gap in convergence analysis for federated learning with realistic client availability patterns, which is crucial for designing efficient and privacy-preserving cross-device systems.
The paper tackles the problem of analyzing Federated Averaging (FedAvg) under cyclic client participation, which is common in practical federated learning systems due to constraints like battery status and privacy requirements. It provides the first theoretical framework showing that cyclic participation can achieve a faster asymptotic convergence rate than uniform participation under suitable conditions.
Federated Averaging (FedAvg) and its variants are the most popular optimization algorithms in federated learning (FL). Previous convergence analyses of FedAvg either assume full client participation or partial client participation where the clients can be uniformly sampled. However, in practical cross-device FL systems, only a subset of clients that satisfy local criteria such as battery status, network connectivity, and maximum participation frequency requirements (to ensure privacy) are available for training at a given time. As a result, client availability follows a natural cyclic pattern. We provide (to our knowledge) the first theoretical framework to analyze the convergence of FedAvg with cyclic client participation with several different client optimizers such as GD, SGD, and shuffled SGD. Our analysis discovers that cyclic client participation can achieve a faster asymptotic convergence rate than vanilla FedAvg with uniform client participation under suitable conditions, providing valuable insights into the design of client sampling protocols.