Timezone: »

On the Convergence of Federated Averaging with Cyclic Client Participation
Yae Jee Cho · PRANAY SHARMA · Gauri Joshi · Zheng Xu · Satyen Kale · Tong Zhang

Wed Jul 26 02:00 PM -- 03:30 PM (PDT) @ Exhibit Hall 1 #602

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.

Author Information

Yae Jee Cho (Carnegie Mellon University)

I am a postdoctoral researcher in the Dept. of Electrical and Computer Engineering, at Carnegie Mellon University. I'm working with Prof. Gauri Joshi. In August 2021, I finished my Ph.D. in Electrical Engineering and Computer Science at Syracuse University. My advisor was Prof. Pramod K. Varshney. I finished my B.Tech-M.Tech dual-degree in Electrical Engineering from IIT Kanpur.

Gauri Joshi (Carnegie Mellon University)
Zheng Xu (Google Research)
Satyen Kale (Google Research)
Tong Zhang (HKUST)
Tong Zhang

Tong Zhang is a professor of Computer Science and Mathematics at the Hong Kong University of Science and Technology. His research interests are machine learning, big data and their applications. He obtained a BA in Mathematics and Computer Science from Cornell University, and a PhD in Computer Science from Stanford University. Before joining HKUST, Tong Zhang was a professor at Rutgers University, and worked previously at IBM, Yahoo as research scientists, Baidu as the director of Big Data Lab, and Tencent as the founding director of AI Lab. Tong Zhang was an ASA fellow and IMS fellow, and has served as the chair or area-chair in major machine learning conferences such as NIPS, ICML, and COLT, and has served as associate editors in top machine learning journals such as PAMI, JMLR, and Machine Learning Journal.

More from the Same Authors