Optimal Client Sampling for Federated Learning

Abstract

It is well understood that client-master communication can be a primary bottleneck in Federated Learning. In this work, we address this issue with a novel client subsampling scheme, where we restrict the number of clients allowed to communicate their updates back to the master node. In each communication round, all participating clients compute their updates, but only the ones with "important" updates communicate back to the master. We show that importance can be measured using only the norm of the update and give a formula for optimal client participation. This formula minimizes the distance between the full update, where all clients participate, and our limited update, where the number of participating clients is restricted. In addition, we provide a simple algorithm that approximates the optimal formula for client participation, which only requires secure aggregation and thus does not compromise client privacy. We show both theoretically and empirically that for Distributed SGD (DSGD) and Federated Averaging (FedAvg), the performance of our approach can be close to full participation and superior to the baseline where participating clients are sampled uniformly. Moreover, our approach is orthogonal to and compatible with existing methods for reducing communication overhead, such as local methods and communication compression methods.

arXiv commentPublished in Transactions on Machine Learning Research, code available: https://github.com/SamuelHorvath/FL-optimal-client-sampling

References in corpus (18)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Prioritized Experience Replay
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• LEAF: A Benchmark for Federated Settings
• Federated Learning of a Mixture of Global and Local Models
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Online Batch Selection for Faster Training of Neural Networks
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Not All Samples Are Created Equal: Deep Learning with Importance Sampling
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Natural Compression for Distributed Deep Learning
• Nonconvex Variance Reduced Optimization with Arbitrary Sampling
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it

Cited by in corpus (13)

• A Field Guide to Federated Optimization
• Study of the performance and scalability of federated learning for medical imaging with intermittent clients
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• Multi-Model Federated Learning
• Local Adaptivity in Federated Learning: Convergence and Consistency
• Securing Secure Aggregation: Mitigating Multi-Round Privacy Leakage in Federated Learning
• FedNL: Making Newton-Type Methods Applicable to Federated Learning
• Sustainable Federated Learning
• Communication-Efficient Distributed SVD via Local Power Iterations
• Uplink Scheduling in Federated Learning: an Importance-Aware Approach via Graph Representation Learning
• On Large-Cohort Training for Federated Learning
• Defending Against Diverse Attacks in Federated Learning Through Consensus-Based Bi-Level Optimization
• Accelerating Federated Edge Learning via Optimized Probabilistic Device Scheduling