Source-linked AI summary
Federated Learning: Strategies for Improving Communication Efficiency
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, Dave Bacon
TL;DR
Federated learning needs communication-efficient training because clients have unreliable, slow connections and uplink transmission can bottleneck large-model updates. This paper proposes structured and sketched updates, reducing communication by two orders of magnitude with only slight convergence-speed degradation in simulated CIFAR experiments.
Problem
Federated learning requires reducing uplink communication costs because clients often have slow, unreliable connections and naive full-update transmission can bottleneck training.
Method
The paper learns updates from compact structured spaces or compresses full updates using quantization, random rotations, and subsampling.
Results
Two orders of magnitude less communication was achieved with only slight convergence-speed degradation in simulated CIFAR experiments, alongside effective convolutional and recurrent-network training.
Takeaways & Limitations
The proposed methods substantially reduce federated-learning communication while retaining good prediction accuracy across convolutional and recurrent networks.
Takeaways & Limitations
The analysis simplifies the setting to a single matrix and chooses the server learning rate η_t = 1.
Abstract
from arXiv · showhide
Federated Learning is a machine learning setting where the goal is to train a high-quality centralized model while training data remains distributed over a large number of clients each with unreliable and relatively slow network connections. We consider learning algorithms for this setting where on each round, each client independently computes an update to the current model based on its local data, and communicates this update to a central server, where the client-side updates are aggregated to compute a new global model. The typical clients in this setting are mobile phones, and communication efficiency is of the utmost importance. In this paper, we propose two ways to reduce the uplink communication costs: structured updates, where we directly learn an update from a restricted space parametrized using a smaller number of variables, e.g. either low-rank or a random mask; and sketched updates, where we learn a full model update and then compress it using a combination of quantization, random rotations, and subsampling before sending it to the server. Experiments on both convolutional and recurrent networks show that the proposed methods can reduce the communication cost by two orders of magnitude.
1 INTRODUCTION
Federated Learning trains a shared global model across many clients with slow or unstable connections, making uplink communication a key practical bottleneck. This paper proposes structured and sketched updates to reduce uplink cost and evaluates their effects on neural-network training and convergence.
- 1 INTRODUCTION: Federated Learning coordinates a shared global model across many clients that often have slow or unstable internet connections.The setting is motivated by large client populations, unbalanced and non-i.i.d. data, and unreliable networks.
- 1 INTRODUCTION: Each synchronized round selects clients, downloads the current model, computes local updates, sends them to the server, and aggregates them into an improved global model.Client updates may involve multiple stochastic-gradient-descent steps on local data, and aggregation is typically averaging.
- 1 INTRODUCTION: Sending a full model update each round can bottleneck Federated Learning because uplink connections are typically slower than downlink connections.The cited US average broadband speeds were 55.0Mbps download and 18.9Mbps upload.
- 1 INTRODUCTION: The paper studies structured updates that learn from a smaller parametrized space and sketched updates that compress full model updates before transmission.The two approaches can also be combined, although that combination is not evaluated in this work.
- 1 INTRODUCTION: Two orders of magnitude less total communicated data was achieved with only a slight degradation in convergence speed in simulated CIFAR experiments.The experiments evaluated these techniques with Federated Averaging and obtained good prediction accuracy with an all-convolutional model while communicating less information than the original CIFAR data size.
2 STRUCTURED UPDATE
Structured updates restrict client updates to pre-specified low-rank or random-mask forms, training within those restricted spaces rather than sketching general updates. Low-rank updates can reduce communication by a factor of d1/k, while random-mask updates transmit only nonzero values and a seed.
- Structured update types: Structured updates use either low-rank matrices or sparse matrices defined by random masks, and train updates directly within these structures.This differs from approximating general updates with structured objects, which is discussed in Section 3.
- Low rank: Low-rank updates factor each update into two matrices, with rank at most fixed k.The update is expressed as the product of two matrices, although the supplied passages do not show the full factorization notation.
- Low rank: A low-rank update can be communicated by sending only the trained matrix and a random seed, saving a factor of d1/k in communication.The other matrix is generated randomly and can be represented by its seed.
- Low rank: The approach performed as well as the best techniques considered in Denil et al. (2013), without hand-crafted features.The passage attributes this to optimizing the projection while using a random reconstruction, whereas fixing the projection can discard important subspaces.
- Random mask: Random-mask updates follow a predefined random sparsity pattern generated independently for each client and round, sending only nonzero values and the seed.The sparse pattern is fully specified by a random seed.
3 SKETCHED UPDATE
Sketched updates compute unconstrained full updates locally, then encode them in lossy compressed form for transmission and decode them at the server before aggregation. The section presents subsampling, probabilistic quantization, and structured random rotations as compatible sketching tools for reducing communication cost.
- 3 SKETCHED UPDATE: Sketched updates compute full local updates without constraints, compress them before transmission, and have the server decode them before aggregation.The sketching tools are mutually compatible and can be used jointly.
- Subsampling: Subsampling sends scaled values from a random subset of each update, and the server averages them into the global update.Random masks are independently generated for each client and round, with the mask stored as a synchronized seed.
- Subsampling: The subsampled global update is an unbiased estimator of the true average: E[ ˆHt] = Ht.The server averages the subsampled updates to produce ˆHt.
- Probabilistic quantization: 32× compression is achieved by probabilistically quantizing each scalar to one bit instead of using a 4 byte float, while preserving an unbiased estimate.More than one bit can be used to balance accuracy and communication costs through the parameter b.
- Improving the quantization by structured random rotations: Random orthogonal rotations before quantization address unequal coordinate scales and can reduce quantization error by O(d/ log d).The server applies the inverse rotation before aggregating updates; general rotations are costly when d = 106 or more, so structured Walsh-Hadamard and binary diagonal matrices are used.
4 EXPERIMENTS
Experiments evaluate the proposed communication-efficient Federated Learning methods on CIFAR-10 image classification and Reddit next-word prediction. CIFAR-10 studies show that random-mask structured updates and sketched updates can substantially reduce communication while preserving convergence and accuracy under Federated Averaging.
- Experimental tasks: Experiments cover CIFAR-10 image classification with convolutional networks and Reddit next-word prediction with a recurrent network.The Reddit data provide natural per-user partitions by post author, reflecting practical federated-learning characteristics.
- Experimental setup: All experiments use Federated Averaging, while structured updates restrict SGD to the low-rank or unmasked parameter space.Learning rates are varied and the best result is reported.
- Structured updates: On CIFAR-10, random-mask structured updates perform significantly better than low-rank updates as update size decreases, with convergence speed essentially unaffected in rounds.The CIFAR-10 model has over 10^6 parameters, and only its inner 7 of 9 convolutional layers are compressed.
- Structured updates: Reducing all 9 layers yields negligible communication savings and slightly degrades convergence speed.The experiments therefore focus compression on the inner 7 layers.
- Sketched updates: Compared with structured random-mask updates, sketched updates are expected to converge to slightly lower accuracy because sketching discards information learned during training.The comparison omits low-rank updates and examines sketched updates with or without randomized Hadamard rotation.
- Sketched updates: Random rotation, subsampling, and quantization jointly enable strong compression: sketching all but 6.25% of elements with 2-bit quantization saves a factor of 256 in layer-update representation with only a minor convergence drop.Randomized Hadamard preprocessing has a particularly positive effect at small quantization bit-widths, and with 2 bits it incurs no performance loss across subsampling ratios.
- Client participation: With 1024 clients per round, subsampling can reduce the retained fraction to 1% with only a minor accuracy drop compared with 10%.This result uses Federated Averaging for 500 and 2500 fixed rounds with 1-bit quantized updates.