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.

翻译：联合会(FedAvg)及其变体是联合会学习中最受欢迎的优化算法(FL)。FedAvg以前的趋同分析要么假定客户充分参与,要么假定客户可以统一抽样,部分客户参与。然而,在实用的交叉设计FL系统中,只有符合电池状况、网络连通和最大参与频率要求(确保隐私)等当地标准的一组客户可在特定时间接受培训。因此,客户的可用性遵循自然周期模式。我们(根据我们的知识)提供了第一个理论框架,用以分析FedAvg与循环客户参与的趋同,以及若干不同的客户优化者,如GD、SGD和冲洗的SGD。我们的分析发现,循环客户参与可以比在适当条件下统一客户参与的Vanilla FedAvg更快的吸附性趋同率,为客户抽样协议的设计提供了宝贵的见解。