Home / Curated / Algorithms / MATCHA Matching Decomposition Sampling for Decentralized SGD

MATCHA Matching Decomposition Sampling for Decentralized SGD

Algorithms AIMech:MatchaMatchingDecompositionSamplingForDecentralizedSgd DRAFT

Aliases: MATCHA, Matching Decomposition Sampling for Decentralized SGD, MATCHA Decentralized SGD

A topology-aware decentralized stochastic gradient descent algorithm (MATCHA) that decomposes a base communication graph G(V, E) into M vertex-disjoint matchings G_1, ..., G_M with Laplacians L_1, ..., L_M, solves a concave algebraic-connectivity optimization problem max_{p_1, ..., p_M} lambda_2(sum_{j=1}^M p_j L_j) subject to a communication budget sum_{j=1}^M p_j <= C_b * M and 0 <= p_j <= 1, and at each iteration k independently samples Bernoulli indicators B_j^(k) ~ Bernoulli(p_j) to form the time-varying symmetric doubly-stochastic mixing matrix W^(k) = I - alpha * sum_{j=1}^M B_j^(k) L_j with SDP-optimized step weight alpha.

Identity Notes & Concept Scope Introduced by Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar (MLSys 2020; arXiv:1905.09435). Distinct from vanilla Decentralized SGD (Lian et al., NeurIPS 2017) and Periodic DecenSGD, which activate all edges of the base graph simultaneously with equal frequency; and distinct from Stochastic Gradient Push (Assran et al., ICML 2019), which uses a deterministic time-varying directed exponential graph rather than algebraic-connectivity-optimized random matching decomposition.

Claims & Grounded Evidence

4 Claims

Mechanism #matcha-disjoint-matching-algebraic-connectivity-and-sdp-mixing-mechanism

MATCHA decomposes G(V, E) via edge coloring into M in {Delta(G), Delta(G) + 1} disjoint matchings with Laplacians L_j satisfying L_j^2 = 2 * L_j, maximizes the Fiedler eigenvalue lambda_2(sum_{j=1}^M p_j L_j) under sum_{j=1}^M p_j <= C_b * M to assign higher activation probabilities p_j to connectivity-critical links, and solves a convex semidefinite program to select alpha minimizing the second-moment spectral norm rho = ||I - 2*alpha*L_bar + alpha^2*(L_bar^2 + 2*L_tilde) - (1/m)*1*1^T||_2.

supports Source: MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling · Locator: Section 3 Equations (4)-(5), Section 4 Equations (6)-(7), & Appendix B Equations (11)-(29), pp. 4-6, 11-14

Scope #matcha-nonconvex-linear-speedup-arbitrary-budget-scope

For any communication budget C_b > 0 on a connected base graph G, Theorem 1 guarantees the existence of alpha > 0 such that rho = ||E[W^(k)^T W^(k)] - (1/m)*1*1^T||_2 < 1, and Theorem 2 / Corollary 1 establish non-convex convergence at rate (1/K) sum_{k=1}^K E[||grad F(x_bar^(k))||^2] = O(1 / sqrt(m*K)) + O(m / K).

supports Source: MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling · Locator: Section 4 Theorem 1 & Section 5 Theorem 2 and Corollary 1, pp. 5-7

Limitation #matcha-undirected-symmetric-matching-and-two-stage-optimization-limitation

Jointly optimizing the matching probabilities {p_j} and mixing weight alpha to minimize rho is non-convex, requiring a two-stage heuristic that first maximizes lambda_2(L_bar) and then solves an SDP for alpha, and the formulation assumes undirected symmetric links with uniform unit link delay.

supports Source: MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling · Locator: Section 4 p. 6, Section 7 Concluding Remarks p. 9, & Appendix B.2 p. 14

Application #matcha-distributed-vision-and-language-modeling-application

Applied to decentralized training of WideResNet and ResNet-50 on CIFAR-10/100 and two-layer LSTM language modeling on Penn Treebank over Erdos-Renyi and random geometric graphs, achieving up to 5.2x wall-clock speedup.

supports Source: MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling · Locator: Section 6 Experimental Results, Figures 4-5, pp. 7-9

⚠️ Curated Limitations & Negative Results

Requires offline edge-coloring matching decomposition and convex/SDP optimization of matching probabilities p_j and step weight alpha.
Formulated for undirected graphs with symmetric doubly-stochastic mixing matrices.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	related_match	AIO:FederatedLearning covers distributed model training across networked nodes, whereas MATCHA is a decentralized peer-to-peer SGD protocol based on algebraic-connectivity-weighted matching decomposition sampling.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r554-primary-pdf`	MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, Soummya Kar	primary paper full_text	ID: https://dblp.org/rec/journals/corr/abs-1905-09435 sha256:afc63eca4b54…
`r554-arxiv-abs`	MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (arXiv abstract) Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, Soummya Kar	primary paper abstract_only	ID: https://arxiv.org/abs/1905.09435 sha256:a1ff1f480b34…
`r554-metadata-cr`	MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (Crossref metadata) Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, Soummya Kar	primary paper abstract_only	ID: https://dblp.org/rec/journals/corr/abs-1905-09435 sha256:80c5e165a6d2…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:37:00Z

Updated: 2026-10-19T10:37:00Z

Source File: data/curated/MatchaMatchingDecompositionSamplingForDecentralizedSgd.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories