Federated Learning with Compression: Unified Analysis and Sharp Guarantees

Abstract

In federated learning, communication cost is often a critical bottleneck to scale up distributed optimization algorithms to collaboratively learn a model from millions of devices with potentially unreliable or limited communication and heterogeneous data distributions. Two notable trends to deal with the communication overhead of federated algorithms are gradient compression and local computation with periodic communication. Despite many attempts, characterizing the relationship between these two approaches has proven elusive. We address this by proposing a set of algorithms with periodical compressed (quantized or sparsified) communication and analyze their convergence properties in both homogeneous and heterogeneous local data distribution settings. For the homogeneous setting, our analysis improves existing bounds by providing tighter convergence rates for both strongly convex and non-convex objective functions. To mitigate data heterogeneity, we introduce a local gradient tracking scheme and obtain sharp convergence rates that match the best-known communication complexities without compression for convex, strongly convex, and nonconvex settings. We complement our theoretical results and demonstrate the effectiveness of our proposed methods by several experiments on real-world datasets.

arXiv commentversion 2. more experiments and comparisons

References in corpus (27)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Personalized Federated Learning: A Meta-Learning Approach
• Adaptive Personalized Federated Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Three Approaches for Personalization with Applications to Federated Learning
• LEAF: A Benchmark for Federated Settings
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• Communication Compression for Decentralized Training
• On the Convergence of Local Descent Methods in Federated Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Distributed Mean Estimation with Limited Communication
• Adaptive Federated Optimization
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Variance Reduced Local SGD with Lower Communication Complexity
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Parallel SGD: When does averaging help?
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Is Local SGD Better than Minibatch SGD?
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

Cited by in corpus (7)

• From Distributed Machine Learning to Federated Learning: A Survey
• FedML: A Research Library and Benchmark for Federated Machine Learning
• Exploiting Shared Representations for Personalized Federated Learning
• MARINA: Faster Non-Convex Distributed Learning with Compression
• FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Wyner-Ziv Gradient Compression for Federated Learning