Client Selection in Federated Learning: Convergence Analysis and\n Power-of-Choice Selection Strategies

Federated learning is a distributed optimization paradigm that enables a\nlarge number of resource-limited client nodes to cooperatively train a model\nwithout data sharing. Several works have analyzed the convergence of federated\nlearning by accounting of data heterogeneity, communication and computation\nlimitations, and partial client participation. However, they assume unbiased\nclient participation, where clients are selected at random or in proportion of\ntheir data sizes. In this paper, we present the first convergence analysis of\nfederated optimization for biased client selection strategies, and quantify how\nthe selection bias affects convergence speed. We reveal that biasing client\nselection towards clients with higher local loss achieves faster error\nconvergence. Using this insight, we propose Power-of-Choice, a communication-\nand computation-efficient client selection framework that can flexibly span the\ntrade-off between convergence speed and solution bias. Our experiments\ndemonstrate that Power-of-Choice strategies converge up to 3 $\\times$ faster\nand give $10$% higher test accuracy than the baseline random selection.\n