SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization

Abstract

In this paper, we propose and analyze SPARQ-SGD, which is an event-triggered and compressed algorithm for decentralized training of large-scale machine learning models. Each node can locally compute a condition (event) which triggers a communication where quantized and sparsified local model parameters are sent. In SPARQ-SGD each node takes at least a fixed number ($H$) of local gradient steps and then checks if the model parameters have significantly changed compared to its last update; it communicates further compressed model parameters only when there is a significant change, as specified by a (design) criterion. We prove that the SPARQ-SGD converges as $O(\frac{1}{nT})$ and $O(\frac{1}{\sqrt{nT}})$ in the strongly-convex and non-convex settings, respectively, demonstrating that such aggressive compression, including event-triggered communication, model sparsification and quantization does not affect the overall convergence rate as compared to uncompressed decentralized training; thereby theoretically yielding communication efficiency for "free". We evaluate SPARQ-SGD over real datasets to demonstrate significant amount of savings in communication over the state-of-the-art.

arXiv comment41 pages, 4 figures

References in corpus (9)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Local SGD Converges Fast and Communicates Little
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• Error Feedback Fixes SignSGD and other Gradient Compression Schemes
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• Distributed Mean Estimation with Limited Communication
• Stochastic Gradient Push for Distributed Deep Learning
• Decentralized Deep Learning with Arbitrary Communication Compression

Cited by in corpus (7)

• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Communication Efficient Distributed Learning with Censored, Quantized, and Generalized Group ADMM
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis
• Decentralized Federated Learning via SGD over Wireless D2D Networks
• Randomized Reactive Redundancy for Byzantine Fault-Tolerance in Parallelized Learning
• A Decentralized Approach to Bayesian Learning