Client Scheduling for Federated Learning over Wireless Networks: A Submodular Optimization Approach
Lintao Ye, Vijay Gupta · 2021 60th IEEE Conference on Decision and Control (CDC) · 2021
Federated Learning (FL) has recently been proposed as a distributed optimization framework under resource constraints and privacy concerns. We study the problem of client scheduling for FL, where the goal is to optimize the performance of FL under certain resource constraints on the FL setup. We show that this problem is a special instance of the general problem of maximizing a submodular function subject to a submodular upper bound constraint. We propose a greedy algorithm to solve this general problem, and provide theoretical approximation guarantees to characterize its performance. The greedy algorithm proposed for the general problem is then applied to solve the FL client scheduling problem with the approximation guarantee. We evaluate the performance of the algorithm using experiments.