Non-IID Federated Learning With Sharper Risk Bound
Bojian Wei, Jian Li, Yong Liu, Weiping Wang
Abstract
In federated learning (FL), the not independently or identically distributed (non-IID) data partitioning impairs the performance of the global model, which is a severe problem to be solved. Despite the extensive literature related to the algorithmic novelties and optimization analysis of FL, there has been relatively little theoretical research devoted to studying the generalization performance of non-IID FL. The generalization research of non-IID FL still lack effective tools and analytical approach. In this article, we propose weighted local Rademacher complexity to pertinently analyze the generalization properties of non-IID FL and derive a sharper excess risk bound based on weighted local Rademacher complexity, where the convergence rate is much faster than the existing bounds. Based on the theoretical results, we present a general framework federated averaging with local rademacher complexity (FedALRC) to lower the excess risk without additional communication costs compared to some famous methods, such as FedAvg. Through extensive experiments, we show that FedALRC outperforms FedAvg, FedProx and FedNova, and those experimental results coincide with our theoretical findings.