The paper "Federated Learning: Strategies for Improving Communication Efficiency" by Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Ananda Theertha Suresh, and Dave Bacon, along with Peter Richtárik, addresses the challenge of reducing communication costs in Federated Learning, a machine learning setting where data is distributed across multiple clients with unreliable and slow network connections. The authors propose two methods to reduce uplink communication costs: structured updates and sketched updates. 1. **Structured Updates**: These updates are learned from a restricted space, such as low-rank matrices or random masks, which significantly reduce the number of parameters that need to be communicated. The low-rank updates are formed by the product of two matrices, where one matrix is randomly generated and optimized, while the other is fixed. The random mask updates restrict the update to a sparse matrix following a predefined pattern. 2. **Sketched Updates**: These updates first compute the full update and then compress it using techniques like quantization, random rotations, and subsampling. Quantization reduces the precision of the update, while random rotations improve the accuracy of the quantization. Subsampling involves sending only a subset of the update values. Experiments on both convolutional and recurrent neural networks show that these methods can reduce communication costs by two orders of magnitude. The structured random mask updates perform better than low-rank updates in terms of communication efficiency. The sketched updates, when combined with structured random rotations, achieve modest accuracy with a significant reduction in communication. In a realistic experiment using Reddit post data, the techniques were shown to be effective in training a recurrent neural network for next-word prediction, demonstrating the practical utility of these methods in Federated Learning.The paper "Federated Learning: Strategies for Improving Communication Efficiency" by Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Ananda Theertha Suresh, and Dave Bacon, along with Peter Richtárik, addresses the challenge of reducing communication costs in Federated Learning, a machine learning setting where data is distributed across multiple clients with unreliable and slow network connections. The authors propose two methods to reduce uplink communication costs: structured updates and sketched updates. 1. **Structured Updates**: These updates are learned from a restricted space, such as low-rank matrices or random masks, which significantly reduce the number of parameters that need to be communicated. The low-rank updates are formed by the product of two matrices, where one matrix is randomly generated and optimized, while the other is fixed. The random mask updates restrict the update to a sparse matrix following a predefined pattern. 2. **Sketched Updates**: These updates first compute the full update and then compress it using techniques like quantization, random rotations, and subsampling. Quantization reduces the precision of the update, while random rotations improve the accuracy of the quantization. Subsampling involves sending only a subset of the update values. Experiments on both convolutional and recurrent neural networks show that these methods can reduce communication costs by two orders of magnitude. The structured random mask updates perform better than low-rank updates in terms of communication efficiency. The sketched updates, when combined with structured random rotations, achieve modest accuracy with a significant reduction in communication. In a realistic experiment using Reddit post data, the techniques were shown to be effective in training a recurrent neural network for next-word prediction, demonstrating the practical utility of these methods in Federated Learning.