mlsanityData to 7 Oct 2026

MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

arXiv 1905.09435 ↗First posted 23 May 2019cs.LG cs.SY eess.SYcited by 67

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 16; 2022: 23; 2023: 7; 2024: 7; 2025: 10; 2026: 4.

67 papers.

Sort:

  1. 2021Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learningcited by 93
  2. 2021Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Datacited by 69
  3. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 68
  4. 2021From Distributed Machine Learning to Federated Learning: A Surveycited by 65
  5. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 55
  6. 2021Federated Learning over Wireless Device-to-Device Networks: Algorithms and Convergence Analysiscited by 51
  7. 2021Consensus Control for Decentralized Deep Learningcited by 49
  8. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  9. 2022Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Datacited by 31
  10. 2022Beyond spectral gap: The role of the topology in decentralized learningcited by 27
  11. 2022Communication-Efficient Topologies for Decentralized Learning with O(1) Consensus Ratecited by 25
  12. 2022CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learningcited by 24
38 more
  1. 2021Decentralized federated learning of deep neural networks on non-iid datacited by 23
  2. 2022On the (In)security of Peer-to-Peer Decentralized Machine Learningcited by 23
  3. 2022Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimizationcited by 22
  4. 2022SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communicationcited by 21
  5. 2023Epidemic Learning: Boosting Decentralized Learning with Randomized Communicationcited by 21
  6. 2022Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Datacited by 20
  7. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  8. 2022Semi-Decentralized Federated Learning with Collaborative Relayingcited by 16
  9. 2022Data-heterogeneity-aware Mixing for Decentralized Learningcited by 12
  10. 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 10
  11. 2021Efficient and Reliable Overlay Networks for Decentralized Federated Learningcited by 9
  12. 2022Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Datacited by 9
  13. 2021A General Theory for Client Sampling in Federated Learningcited by 8
  14. 2023Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergencecited by 8
  15. 2021Cross-Silo Federated Learning for Multi-Tier Networks with Vertical and Horizontal Data Partitioningcited by 6
  16. 2024Boosting Asynchronous Decentralized Learning with Model Fragmentationcited by 6
  17. 2022Robust Federated Learning with Connectivity Failures: A Semi-Decentralized Framework with Collaborative Relayingcited by 5
  18. 2022DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphscited by 5
  19. 2023Cooperative Federated Learning over Ground-to-Satellite Integrated Networks: Joint Local Computation and Data Offloadingcited by 5
  20. 2022FedSPLIT: One-Shot Federated Recommendation System Based on Non-negative Joint Matrix Factorization and Knowledge Distillationcited by 4
  21. 2022Optimal Complexity in Non-Convex Decentralized Learning over Time-Varying Networkscited by 4
  22. 2021Asynchronous speedup in decentralized optimizationcited by 3
  23. 2021Secure Multi-Party Computation based Privacy Preserving Data Analysis in Healthcare IoT Systemscited by 3
  24. 2021Learning, Computing, and Trustworthiness in Intelligent IoT Environments: Performance-Energy Tradeoffscited by 3
  25. 2023Beyond spectral gap (extended): The role of the topology in decentralized learningcited by 3
  26. 2023Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updatescited by 3
  27. 2025Scalable Decentralized Learning with Teleportationcited by 3
  28. 2025Mitigating Privacy-Utility Trade-off in Decentralized Federated Learning via f-Differential Privacycited by 3
  29. 2022Accelerating Parallel Stochastic Gradient Descent via Non-blocking Mini-batchescited by 2
  30. 2022Personalized Decentralized Multi-Task Learning Over Dynamic Communication Graphscited by 2
  31. 2023Sparse Decentralized Federated Learningcited by 2
  32. 2024Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walkscited by 2
  33. 2024Heterogeneity-Aware Cooperative Federated Edge Learning with Adaptive Computation and Communication Compressioncited by 2
  34. 2024FedPeWS: Personalized Warmup via Subnetworks for Enhanced Heterogeneous Federated Learningcited by 2
  35. 2025FedEFM: Federated Endovascular Foundation Model with Unseen Datacited by 2
  36. 2021Finite-Time Consensus Learning for Decentralized Optimization with Nonlinear Gossipingcited by 1
  37. 2022Reducing Training Time in Cross-Silo Federated Learning using Multigraph Topologycited by 1
  38. 2022Scaling up Stochastic Gradient Descent for Non-convex Optimisationcited by 1

50 most cited of 67 All 67 (JSON)