# MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

arXiv: https://arxiv.org/abs/1905.09435 · HTML: https://mlsanity.com/paper/1905.09435/

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

## Built on by (most cited first, 30 of 67)

- [Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learning](https://mlsanity.com/paper/2105.05883/) (2021)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [From Distributed Machine Learning to Federated Learning: A Survey](https://mlsanity.com/paper/2104.14362/) (2021)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2101.12704/) (2021)
- [Consensus Control for Decentralized Deep Learning](https://mlsanity.com/paper/2102.04828/) (2021)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [Beyond spectral gap: The role of the topology in decentralized learning](https://mlsanity.com/paper/2206.03093/) (2022)
- [Decentralized federated learning of deep neural networks on non-iid data](https://mlsanity.com/paper/2107.08517/) (2021)
- [Communication-Efficient Topologies for Decentralized Learning with O(1) Consensus Rate](https://mlsanity.com/paper/2210.07881/) (2022)
- [CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learning](https://mlsanity.com/paper/2210.02912/) (2022)
- [On the (In)security of Peer-to-Peer Decentralized Machine Learning](https://mlsanity.com/paper/2205.08443/) (2022)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication](https://mlsanity.com/paper/2210.14026/) (2022)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2209.15505/) (2022)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Semi-Decentralized Federated Learning with Collaborative Relaying](https://mlsanity.com/paper/2205.10998/) (2022)
- [Data-heterogeneity-aware Mixing for Decentralized Learning](https://mlsanity.com/paper/2204.06477/) (2022)
- [FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning](https://mlsanity.com/paper/2108.06869/) (2021)
- [Efficient and Reliable Overlay Networks for Decentralized Federated Learning](https://mlsanity.com/paper/2112.15486/) (2021)
- [Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data](https://mlsanity.com/paper/2203.01214/) (2022)
- [Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence](https://mlsanity.com/paper/2305.11420/) (2023)
- [A General Theory for Client Sampling in Federated Learning](https://mlsanity.com/paper/2107.12211/) (2021)
- [Cross-Silo Federated Learning for Multi-Tier Networks with Vertical and Horizontal Data Partitioning](https://mlsanity.com/paper/2108.08930/) (2021)
- [Boosting Asynchronous Decentralized Learning with Model Fragmentation](https://mlsanity.com/paper/2410.12918/) (2024)
- [Robust Federated Learning with Connectivity Failures: A Semi-Decentralized Framework with Collaborative Relaying](https://mlsanity.com/paper/2202.11850/) (2022)
- [FedSPLIT: One-Shot Federated Recommendation System Based on Non-negative Joint Matrix Factorization and Knowledge Distillation](https://mlsanity.com/paper/2205.02359/) (2022)

## Abstract (arXiv)

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× less time than vanilla decentralized SGD to reach the same training loss.