On the Tradeoff Between Heterogeneity and Communication Complexity in Federated Learning

The heterogeneity-complexity tradeoff in federated learning (FL) is a key challenge facing the deployment of FL in the real world. While learning on heterogeneous data is key to required performance improvement in many applications, training with state-of-the-art uncoordinated FL methods in the presence of substantial heterogeneity can lead to prohibitively large communication complexity. Most state-of-the-art techniques designed to deal with heterogeneity employ sampling across the client pool, inducing low aggregation or coverage in the datasets of the out-of-sample clients. In this paper, we challenge the common wisdom of learning a single global model across multi-distribution data and propose a federated learning mechanism (without money) that partitions the pool of clients into a minimal number of subsets of clients and then learns a global model for each subset of the clients. This leads to a reduced degree of heterogeneity across each subset of clients while ensuring positive aggregation across all client datasets. In particular, we pose the problem of federated learning as a repeated multi-agent basic utility game and use no-regret learning algorithms to solve the game. Experiments on multi-distribution datasets show that the proposed method outperforms the key benchmarks in terms of both communication complexity and global accuracy.