MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

Abstract

This paper studies the problem of error-runtime trade-off, typically encountered in decentralized training based on stochastic gradient descent (SGD) using a given network. While a denser (sparser) network topology results in faster (slower) error convergence in terms of iterations, it incurs more (less) communication time/delay per iteration. In this paper, we propose MATCHA, an algorithm that can achieve a win-win in this error-runtime trade-off for any arbitrary network topology. The main idea of MATCHA is to parallelize inter-node communication by decomposing the topology into matchings. To preserve fast error convergence speed, it identifies and communicates more frequently over critical links, and saves communication time by using other links less frequently. Experiments on a suite of datasets and deep neural networks validate the theoretical analyses and demonstrate that MATCHA takes up to $5\times$ less time than vanilla decentralized SGD to reach the same training loss.

References in corpus (13)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Wide Residual Networks
• Sensor Networks with Random Links: Topology Design for Distributed Consensus
• Local SGD Converges Fast and Communicates Little
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
• Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates
• On Nonconvex Decentralized Gradient Descent
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

Cited by in corpus (23)

• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data
• Decentralized Deep Learning with Arbitrary Communication Compression
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Communication-Efficient Local Decentralized SGD Methods
• FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tiers
• Decentralized federated learning of deep neural networks on non-iid data
• TornadoAggregate: Accurate and Scalable Federated Learning via the Ring-Based Architecture
• Consensus Control for Decentralized Deep Learning
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• Distributed Deep Learning with Event-Triggered Communication
• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Decentralized Federated Learning via SGD over Wireless D2D Networks
• On the Communication Latency of Wireless Decentralized Learning
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization
• Multi-Level Local SGD for Heterogeneous Hierarchical Networks
• Optimal Complexity in Decentralized Training
• Matrix Sketching for Secure Collaborative Machine Learning