Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

Abstract

We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning task) being distributed over $n$ machines that can only communicate to their neighbors on a fixed communication graph. To reduce the communication bottleneck, the nodes compress (e.g. quantize or sparsify) their model updates. We cover both unbiased and biased compression operators with quality denoted by $\omega \le 1$ ($\omega =1$ meaning no compression). We (i) propose a novel gossip-based stochastic gradient descent algorithm, CHOCO-SGD, that converges at rate $\mathcal{O}\left(1/(nT)+1/(T{\delta }^2\omega {)}^2\right)$ for strongly convex objectives, where $T$ denotes the number of iterations and $\delta$ the eigengap of the connectivity matrix. Despite compression quality and network connectivity affecting the higher order terms, the first term in the rate, $\mathcal{O}(1/(nT))$, is the same as for the centralized baseline with exact communication. We (ii) present a novel gossip algorithm, CHOCO-GOSSIP, for the average consensus problem that converges in time $\mathcal{O}(1/({\delta }^2\omega )\log (1/\epsilon ))$ for accuracy $\epsilon >0$. This is (up to our knowledge) the first gossip algorithm that supports arbitrary compressed messages for $\omega >0$ and still exhibits linear convergence. We (iii) show in experiments that both of our algorithms do outperform the respective state-of-the-art baselines and CHOCO-SGD can reduce communication by at least two orders of magnitudes.

Cited by in corpus (84)

• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• A Field Guide to Federated Optimization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Robust Federated Learning: The Case of Affine Distribution Shifts
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• Decentralized Deep Learning with Arbitrary Communication Compression
• Communication-Efficient Local Decentralized SGD Methods
• FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tiers
• Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
• Decentralized federated learning of deep neural networks on non-iid data
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Consensus Control for Decentralized Deep Learning
• $\text{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression
• Basil: A Fast and Byzantine-Resilient Approach for Decentralized Training
• On the Utility of Gradient Compression in Distributed Training Systems
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums
• Communication-efficient distributed SGD with Sketching
• Sparse Communication for Training Deep Networks
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• p2pGNN: A Decentralized Graph Neural Network for Node Classification in Peer-to-Peer Networks
• Linear Convergent Decentralized Optimization with Compression
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• An introduction to decentralized stochastic optimization with gradient tracking
• Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Periodic Stochastic Gradient Descent with Momentum for Decentralized Training
• Robust and Communication-Efficient Collaborative Learning
• PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• Distributed Fixed Point Methods with Compressed Iterates
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
• Wirelessly Powered Federated Edge Learning: Optimal Tradeoffs Between Convergence and Power Transfer
• On the Communication Latency of Wireless Decentralized Learning
• On the Convergence of Decentralized Adaptive Gradient Methods
• Improving the Transient Times for Distributed Stochastic Gradient Methods
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Adaptive Serverless Learning
• Efficient and Less Centralized Federated Learning
• Decentralized Composite Optimization with Compression
• On the Convergence of Nested Decentralized Gradient Methods with Multiple Consensus and Gradient Steps
• Trends and Advancements in Deep Neural Network Communication
• Accelerating Gossip SGD with Periodic Global Averaging
• Decentralized Optimization On Time-Varying Directed Graphs Under Communication Constraints
• State-of-the-art Techniques in Deep Edge Intelligence
• Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
• PPT: A Privacy-Preserving Global Model Training Protocol for Federated Learning in P2P Networks
• Boosting Asynchronous Decentralized Learning with Model Fragmentation
• GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
• Separation of Powers in Federated Learning
• Optimal Complexity in Decentralized Training
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• A general framework for decentralized optimization with first-order methods
• Decentralized Learning with Lazy and Approximate Dual Gradients
• Loss Landscape Dependent Self-Adjusting Learning Rates in Decentralized Stochastic Gradient Descent
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing
• Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying Networks
• Towards Tight Communication Lower Bounds for Distributed Optimisation
• ResIST: Layer-Wise Decomposition of ResNets for Distributed Training
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• Matrix Sketching for Secure Collaborative Machine Learning
• A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
• Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method
• Network-Density-Controlled Decentralized Parallel Stochastic Gradient Descent in Wireless Systems
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method
• An Empirical Study on Compressed Decentralized Stochastic Gradient Algorithms with Overparameterized Models