MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
Open accessThe DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Abstract
Decentralized stochastic gradient descent (SGD) is a promising approach to learn a machine learning model over a network of workers connected in an arbitrary topology. Although a densely-connected network topology can ensure faster convergence in terms of iterations, it incurs more communication time/delay per iteration, resulting in longer training time. In this paper, we propose a novel algorithm MATCHA to achieve a win-win in this error-runtime trade-off. MATCHA uses matching decomposition sampling of the base topology to parallelize inter-worker information exchange so as to significantly reduce communication delay. At the same time, the algorithm communicates more frequently over critical links such that it can maintain the same convergence rate as vanilla decentralized SGD. Experiments on a suite of datasets and deep neural networks validate the theoretical analysis and demonstrate the effectiveness of the proposed scheme as far as reducing communication delays is concerned.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Characterizing such fundamental trade-offs between accuracy and communication has been of recent interest in theoretical statistics [507, 89, 221, 7, 49, 444, 50].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [49]
In the citing paper
“These works characterize the optimal minimax rates for distributed statistical estimation and learning under communication constraints.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [49]
Citations
Cites
Learning Multiple Layers of Features from Tiny Images
Krizhevsky, A. (2024) · doi:10.57702/zp44cu3g · Cited by 23,395
Wide Residual NetworksPreprint
Zagoruyko, S., & Komodakis, N. (2016) · British Machine Vision Conference · doi:10.48550/arxiv.1605.07146 · Cited by 9,452 · cited 1×
“2: Comparison between vanilla decentralized SGD (DecenSGD) and MATCHA when training WideResNet [14] on CIFAR-100 [15].”
BackgroundBuilding a Large Annotated Corpus of English: The Penn Treebank
Marcus, M. (1993) · doi:10.21236/ada273556 · Cited by 7,405
Zagoruyko, S., & Komodakis, N. (2016) · Procedings of the British Machine Vision Conference 2016 · doi:10.5244/c.30.87 · Cited by 7,244
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719 · cited 1×
“In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
BackgroundBoyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439 · cited 1×
“or constraining the number of allowable links, have been proposed [17].”
BackgroundDistributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2161027 · Cited by 947 · cited 1×
“In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
BackgroundDual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
On the Convergence of Decentralized Gradient Descent
Yuan, K., Ling, Q., & Yin, W. (2013) · arXiv · doi:10.48550/arxiv.1310.7063 · Cited by 635 · cited 1×
“In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
Background
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
Self-citationA survey on security and privacy of federated learning
Mothukuri, V., Parizi, R. M., Pouriyeh, S., Huang, Y., Dehghantanha, A., & Srivastava, G. (2021) · Future Generation Computer Systems · doi:10.1016/j.future.2020.10.007 · Cited by 1,480
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
Wang, J., Liu, Q., Liang, H., Joshi, G., & Poor, H. V. (2020) · arXiv · doi:10.48550/arxiv.2007.07481 · Cited by 927
“The analysis relies on Assumptions 1 and 2 used in the standard analysis of SGD [51] and Assumption 3 commonly used in the federated optimization literature [38, 12, 13, 20, 40, 52, 2] to capture the dissimilarities of local objectives.”
BackgroundMethodSelf-citationFedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
Reisizadeh, A., Mokhtari, A., Hassani, H., Jadbabaie, A., & Pedarsani, R. (2019) · arXiv · doi:10.48550/arxiv.1909.13014 · Cited by 587
From distributed machine learning to federated learning: a survey
Liu, J., Huang, J., Zhou, Y., Li, X., Ji, S., Xiong, H., & Dou, D. (2022) · Knowledge and Information Systems · doi:10.1007/s10115-022-01664-x · Cited by 356
Metadata
- Authors
- Wang, J., Sahu, A. K., Yang, Z., Joshi, G., & Kar, S.
- Affiliations
- Carnegie Mellon University (US)
- Robert Bosch (United States) (US)
- Venue
- 2019 Sixth Indian Control Conference (ICC)
- Publisher
- IEEE
- Published
- 2019-12
- Pages
- 299-300
- OpenAlex
- W3038057116
- Cited by
- 149
- References
- 20
- Citations by year
- 2026: 6 · 2025: 14 · 2024: 25 · 2023: 25 · 2022: 27 · 2021: 23 · 2020: 22 · 2019: 7
- FWCI
- 7.56
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- Indian Control Conference (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Keywords
- matcha, communication delay reduction, distributed learning, network topology, convergence rate
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling. https://app.cochat.ai/papers/10.1109/icc47138.2019.9123209
- The paper
- Wang, J., Sahu, A. K., Yang, Z., Joshi, G., & Kar, S. (2019). MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling. 2019 Sixth Indian Control Conference (ICC). https://doi.org/10.1109/icc47138.2019.9123209
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.