Optimal Gradient Compression for Distributed and Federated Learning

Abstract

Communicating information, like gradient vectors, between computing nodes in distributed and federated learning is typically an unavoidable burden, resulting in scalability issues. Indeed, communication might be slow and costly. Recent advances in communication-efficient training algorithms have reduced this bottleneck by using compression techniques, in the form of sparsification, quantization, or low-rank approximation. Since compression is a lossy, or inexact, process, the iteration complexity is typically worsened; but the total communication complexity can improve significantly, possibly leading to large computation time savings. In this paper, we investigate the fundamental trade-off between the number of bits needed to encode compressed vectors and the compression error. We perform both worst-case and average-case analysis, providing tight lower bounds. In the worst-case analysis, we introduce an efficient compression operator, Sparse Dithering, which is very close to the lower bound. In the average-case analysis, we design a simple compression operator, Spherical Compression, which naturally achieves the lower bound. Thus, our new compression schemes significantly outperform the state of the art. We conduct numerical experiments to illustrate this improvement.

References in corpus (19)

• Deep Learning in Neural Networks: An Overview
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• ATOMO: Communication-efficient Learning via Atomic Sparsification
• PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization
• Distributed Mean Estimation with Limited Communication
• DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
• Natural Compression for Distributed Deep Learning
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• On Biased Compression for Distributed Learning
• Distributed learning with compressed gradients
• Rate Distortion For Model Compression: From Theory To Practice

Cited by in corpus (9)

• Federated Learning with Spiking Neural Networks
• Rethinking gradient sparsification as total error minimization
• What Do We Mean by Generalization in Federated Learning?
• Wyner-Ziv Gradient Compression for Federated Learning
• Towards cost-effective and resource-aware aggregation at Edge for Federated Learning
• Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
• Parallel and Distributed algorithms for ML problems
• Improved Communication Efficiency for Distributed Mean Estimation with Side Information
• MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization