  Federated Learning (FL) algorithms commonly sample a random subset of clients
to address the straggler issue and improve communication efficiency. While
recent works have proposed various client sampling methods, they have
limitations in joint system and data heterogeneity design, which may not align
with practical heterogeneous wireless networks. In this work, we advocate a new
independent client sampling strategy to minimize the wall-clock training time
of FL, while considering data heterogeneity and system heterogeneity in both
communication and computation. We first derive a new convergence bound for
non-convex loss functions with independent client sampling and then propose an
adaptive bandwidth allocation scheme. Furthermore, we propose an efficient
independent client sampling algorithm based on the upper bounds on the
convergence rounds and the expected per-round training time, to minimize the
wall-clock time of FL, while considering both the data and system
heterogeneity. Experimental results under practical wireless network settings
with real-world prototype demonstrate that the proposed independent sampling
scheme substantially outperforms the current best sampling schemes under
various training models and datasets.
