Gradient Descent with Compressed Iterates

Abstract

We propose and analyze a new type of stochastic first order method: gradient descent with compressed iterates (GDCI). GDCI in each iteration first compresses the current iterate using a lossy randomized compression technique, and subsequently takes a gradient step. This method is a distillation of a key ingredient in the current practice of federated learning, where a model needs to be compressed by a mobile device before it is sent back to a server for aggregation. Our analysis provides a step towards closing the gap between the theory and practice of federated learning, and opens the possibility for many extensions.

arXiv commentNeurIPS 2019 Workshop on Federated Learning for Data Privacy and Confidentiality. 10 pages, 1 algorithm, 1 theorem, 5 lemmas

References in corpus (26)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Learning with Non-IID Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Federated Machine Learning: Concept and Applications
• Differentially Private Federated Learning: A Client Level Perspective
• Sparsified SGD with Memory
• Don't Use Large Mini-Batches, Use Local SGD
• Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis
• Local SGD Converges Fast and Communicates Little
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Distributed Learning with Compressed Gradient Differences
• signSGD: Compressed Optimisation for Non-Convex Problems
• Adaptive Federated Learning in Resource Constrained Edge Computing Systems
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Natural Compression for Distributed Deep Learning
• First Analysis of Local GD on Heterogeneous Data
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• Decentralized Deep Learning with Arbitrary Communication Compression
• Robust and Communication-Efficient Collaborative Learning
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it

Cited by in corpus (8)

• Distributed Learning of Deep Neural Networks using Independent Subnet Training
• From Local SGD to Local Fixed-Point Methods for Federated Learning
• RingFed: Reducing Communication Costs in Federated Learning on Non-IID Data
• Distributed Fixed Point Methods with Compressed Iterates
• FLFE: A Communication-Efficient and Privacy-Preserving Federated Feature Engineering Framework
• Quantized Adam with Error Feedback
• Matrix Sketching for Secure Collaborative Machine Learning
• Wireless Distributed Edge Learning: How Many Edge Devices Do We Need?