Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

2019/02/01 by Anastasia Koloskova, Koloskova, Anastasia, Sebastian U. Stich +3 · 88 citations
Computer Science · Mathematics · #Distributed Control Multi-Agent Systems #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #acm:68W10 #acm:68W15 #acm:68W40 #acm:90C06 #acm:90C25 #acm:90C35 #cs.DC #cs.DS #cs.LG #math.OC #msc:68W10 #msc:68W15 #msc:68W40 #msc:90C06 #msc:90C25 #msc:90C35 #stat.ML

paper · pdf · doi:10.48550/arxiv.1902.00340

arxiv created 2019/02/01 · arxiv updated 2019/02/04

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 ω≤ 1 (ω=1 meaning no compression). We (i) propose a novel gossip-based stochastic gradient descent algorithm, CHOCO-SGD, that converges at rate O(1/(nT) + 1/(T δ² ω)²) for strongly convex objectives, where T denotes the number of iterations and δ the eigengap of the connectivity matrix. Despite compression quality and network connectivity affecting the higher order terms, the first term in the rate, 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 O(1/(δ²ω) log (1/ε)) for accuracy ε> 0. This is (up to our knowledge) the first gossip algorithm that supports arbitrary compressed messages for ω> 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

• Communication Compression for Distributed Learning with Aggregate and Server-Guided Feedback
• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication
• Compressed Momentum-based Single-Point Zeroth-Order Algorithm for Stochastic Distributed Nonconvex Optimization
• Distributed Online Randomized Gradient-Free Optimization with Compressed Communication
• A Communication-Efficient Distributed Optimization Algorithm for Problems with Coupling Constraints
• Row-Stochastic Matrices Can Provably Outperform Doubly Stochastic Matrices in Decentralized Learning
• Learning Performance Optimization for Edge AI System with Time and Energy Constraints
• Spectral-Convergent Decentralized Machine Learning: Theory and Application in Space Networks
• Decentralized Federated Learning with Distributed Aggregation Weight Optimization
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• Efficient and Less Centralized Federated Learning
• Loss Landscape Dependent Self-Adjusting Learning Rates in Decentralized Stochastic Gradient Descent
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning: Examining Distributed and Centralized Stochastic Gradient Descent
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications
• Matrix Sketching for Secure Collaborative Machine Learning
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• DFCA: Decentralized Federated Clustering Algorithm
• Separation of Powers in Federated Learning
• Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy
• Privacy-Preserving Distributed Estimation with Limited Data Rate
• CoNeT-GIANT: A compressed Newton-type fully distributed optimization algorithm
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Robust and Efficient Collaborative Learning
• DeMuon: A Decentralized Muon for Matrix Optimization over Graphs
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• A non-smooth regularization framework for learning over multitask graphs
• On the Convergence of Decentralized Adaptive Gradient Methods
• Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Tracking
• Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneity
• FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tiers
• Distributed Online Learning for Joint Regret with Communication Constraints
• Jointly Computation- and Communication-Efficient Distributed Learning
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• On the Communication Latency of Wireless Decentralized Learning
• A Field Guide to Federated Optimization
• Decentralized Relaxed Smooth Optimization with Gradient Descent Methods
• Decentralized Composite Optimization with Compression
• Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• Power-Constrained Policy Gradient Methods for LQR
• Communication-efficient distributed SGD with Sketching
• Communication-Efficient Local Decentralized SGD Methods
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Distributed Fixed Point Methods with Compressed Iterates
• Improving the Transient Times for Distributed Stochastic Gradient Methods
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Advances and Open Problems in Federated Learning
• Wirelessly Powered Federated Edge Learning: Optimal Tradeoffs Between Convergence and Power Transfer
• Periodic Stochastic Gradient Descent with Momentum for Decentralized Training
• Linear Convergent Decentralized Optimization with Compression
• Robust and Communication-Efficient Collaborative Learning
• Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
• Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossiping
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method
• Stochastic Push-Pull for Decentralized Nonconvex Optimization
• A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
• Tight analyses of first-order methods with error feedback
• On the Benefits of Multiple Gossip Steps in Communication-Constrained\n Decentralized Optimization
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Memory-Efficient Distributed Unlearning
• Subspace Networks: Scaling Decentralized Training with Communication-Efficient Model Parallelism
• Enhancing Parallelism in Decentralized Stochastic Convex Optimization
• Accelerating Gossip SGD with Periodic Global Averaging
• Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means
• Adaptive Serverless Learning
• PowerGossip: Practical Low-Rank Communication Compression in\n Decentralized Deep Learning
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• Topology-Aware Knowledge Propagation in Decentralized Learning
• Network-Density-Controlled Decentralized Parallel Stochastic Gradient Descent in Wireless Systems
• Heterogeneous Decentralized Diffusion Models
• Source Anonymity for Private Random Walk Decentralized Learning
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• A Tight Theory of Error Feedback Algorithms in Distributed Optimization
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Distributed Online Randomized Gradient-Free optimization with Compressed Communication
• Hubs and Spokes Learning: Efficient and Scalable Collaborative Machine Learning
• FedCritic-MIMO: Communication-Efficient Serverless Federated Critic Learning for Massive-MIMO Resource Control in Open and Disaggregated 6G RANs
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Decentralized Learning with Lazy and Approximate Dual Gradients
• p2pGNN: A Decentralized Graph Neural Network for Node Classification in Peer-to-Peer Networks
• Distributed Optimization with Efficient Communication, Event-Triggered Solution Enhancement, and Operation Stopping
• Trends and Advancements in Deep Neural Network Communication
• A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip

Related

• On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks
• On the Benefits of Multiple Gossip Steps in Communication-Constrained\n Decentralized Optimization
• A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
• Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
• DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity