MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

Jianyu Wang; Anit Kumar Sahu; Zhouyi Yang; Gauri Joshi; Soummya Kar

Source-linked AI summary

MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, Soummya Kar

arXiv:1905.09435v3May 23, 2019cs.LGeess.SYmath.OCstat.ML

TL;DR

Decentralized SGD faces a trade-off between faster iteration-wise convergence on dense networks and greater wall-clock communication delay. MATCHA decomposes the network into matchings and samples them with connectivity-aware probabilities under a communication budget. Experiments show that it can reach the same training loss up to 5× faster than vanilla decentralized SGD in wall-clock time.

Problem
Prior work focused mainly on iteration complexity, without explicitly accounting for how network topology affects wall-clock training runtime.
Method
MATCHA decomposes communication graphs into matchings and samples connectivity-critical links more frequently under a tunable communication budget.
Results
On CIFAR-100, MATCHA with Cb = 0.02 took 5× less wall-clock time than vanilla DecenSGD to reach training loss 0.1.
Takeaways & Limitations
MATCHA reduces communication delay while maintaining the same or improving error-versus-iterations convergence rate across the reported analyses and experiments.
Takeaways & Limitations
MATCHA separately optimizes activation probabilities and the mixing parameter because jointly optimizing them produces a non-convex problem that cannot be solved efficiently.

Abstract

from arXiv · show

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.

1 Introduction

Decentralized SGD must balance iteration-wise convergence against wall-clock communication costs in networked training without a central coordinator. MATCHA addresses this trade-off by sampling communication over graph matchings, emphasizing critical links while reducing redundant communication.

Motivation: Decentralized training distributes data and computation across worker nodes that exchange parameters or gradients only with neighbors.The setting is relevant to sensor networks, multi-agent systems, and federated learning on edge devices.
Error-Runtime Trade-off: Prior decentralized SGD analyses mainly count iterations or communication rounds, leaving topology-dependent wall-clock runtime insufficiently addressed.Dense networks can improve error convergence but increase communication delay per iteration.
Contribution: MATCHA is presented as a decentralized SGD method that tunes inter-node communication frequency to improve the error-runtime trade-off.The paper reports theoretical and empirical evaluation of the approach.
Core Idea: MATCHA decomposes the topology into disjoint links that communicate in parallel, then activates matchings with optimized probabilities.The probabilities favor connectivity-critical links while using other links less frequently, reducing communication time without sacrificing convergence objectives.
Relation to Prior Methods: MATCHA reduces transmitted data frequency rather than data size, unlike gradient compression and quantization methods.Its communication schedule is predetermined before training and can be combined with compression techniques.

2 Problem Formulation and Preliminaries

The paper models decentralized learning over a connected graph in which each worker accesses local data and exchanges information with neighboring nodes. Its communication model makes the maximum node degree the per-iteration bottleneck under an increasing delay rule.

Network Model: The communication network is an arbitrary sparse or dense undirected connected graph whose edges restrict which worker pairs can exchange parameters or gradients.Each node communicates only with its graph neighbors.
Learning Objective: Each worker accesses its own local data distribution, and training minimizes a joint objective built from local loss functions.The model parameters may include neural-network weights and biases.
Decentralized SGD: Decentralized SGD combines neighborhood consensus with each node’s stochastic local gradient update.A symmetric, doubly stochastic mixing matrix can ensure convergence of nodes toward the same stationary point.
Communication Time Model: Communication delay increases with node degree, so the highest-degree node bottlenecks synchronization time per iteration.The paper focuses on the linear rule t(∆) = ∆, while allowing extensions to other monotonically increasing delay functions.
Graph Preliminaries: The graph Laplacian’s second-smallest eigenvalue λ2 measures algebraic connectivity, with larger values indicating denser connectivity.The paper uses this quantity to characterize graph connectivity.

3 MATCHA: Proposed Matching Decomposition Sampling Strategy

MATCHA decomposes a base communication graph into matchings and probabilistically samples them to create sparse, parallel communication topologies. It chooses activation probabilities to preserve expected connectivity under a communication-time budget.

Matching Decomposition: MATCHA first decomposes the base graph into disjoint matchings, whose links can communicate in parallel.An edge-coloring algorithm can produce ∆(G) or ∆(G) + 1 matchings.
Matching Decomposition: A matching has effective node degree one, so its communication takes t(1) = 1 unit under the paper’s delay model.This minimizes effective degree while maximizing parallel exchanges within the selected subgraph.
Topology Sampling: Each matching receives an independent Bernoulli activation variable, and its links communicate only when that variable equals one.The resulting activated topology is sparse and may be disconnected in an individual iteration.
Communication Budget: The communication budget Cb constrains expected communication frequency, with Cb = 1 recovering vanilla decentralized SGD.For example, Cb = 0.1 targets expected communication time equal to 10% of vanilla decentralized SGD.
Probability Optimization: MATCHA optimizes activation probabilities to maximize algebraic connectivity of the expected graph under the communication constraint.Because λ2 is concave in the relevant formulation, this optimization is convex; larger λ2 generally indicates better connectivity.
Extensions: The framework extends to other delay functions, activation schemes, link costs, graph decompositions, and decentralized averaging algorithms.The communication constraint can be modified for a general increasing delay function t(∆(G)).
Comparison with Periodic DecenSGD: Periodic decentralized SGD reduces communication by activating the entire base topology less often, whereas MATCHA selectively samples matchings.The distinction is between reducing whole-topology synchronization frequency and prioritizing subsets of links.

4 Further Optimizing MATCHA For Decentralized SGD

MATCHA optimizes its time-varying consensus process by selecting activation probabilities and mixing parameters to control spectral norm under a communication budget. For any positive budget on a connected graph, an appropriate parameter choice guarantees convergence.

The mixing matrices are constructed as symmetric and doubly stochastic, with α controlling the weight assigned to neighbors during consensus.
A smaller spectral norm ρ yields a smaller optimization error bound, so controlling ρ is central to MATCHA's convergence analysis.
For any communication budget Cb > 0 on a connected base graph, MATCHA admits an α such that ρ < 1 and therefore converges to a stationary point.
The probability and α optimization problems are solved once before training, with the added computation described as negligible relative to total training time.
MATCHA jointly influences convergence through activation probabilities and the consensus weight α, but optimizes them separately because joint optimization is non-convex.The activation probabilities are optimized through an upper-bound formulation, while α is obtained separately through semidefinite programming.

5 Error Convergence Analysis

The analysis characterizes MATCHA's non-asymptotic convergence for smooth non-convex losses through averaged gradient norms and the spectral norm of its random mixing process. It shows that communication budgets can reduce runtime while preserving or improving the convergence bound relative to vanilla decentralized SGD.

MATCHA's convergence analysis measures the averaged squared gradient norm, which approaches zero when the algorithm reaches a stationary point.
The non-asymptotic guarantee assumes smooth local objectives, unbiased stochastic gradients, bounded gradient variance, and bounded deviation among local objective gradients.
ρ < 1 is guaranteed for arbitrary communication budget Cb, ensuring MATCHA's convergence under the stated conditions.
The optimization error upper bound differs from vanilla decentralized SGD through the spectral norm ρ, with smaller ρ producing a lower bound.
2–3× less communication time lets MATCHA preserve vanilla DecenSGD's spectral norm, while suitable budgets can produce an even lower ρ.
MATCHA can achieve linear speedup in the number of worker nodes when the learning rate is configured properly, matching vanilla decentralized and fully synchronous SGD rates.
For sufficiently large iteration counts, specifically K ≥ m^3, MATCHA's convergence is dominated by the first term in the bound.

6 Experimental Results

Experiments across image-classification and language-modeling tasks show that MATCHA reduces communication time while preserving or improving convergence. The benefit persists across communication budgets and graph topologies, with up to 5× lower wall-clock time for a target loss.

MATCHA was evaluated on CIFAR-10, CIFAR-100, and Penn Treebank, using evenly partitioned training data and a learning rate tuned for vanilla DecenSGD.
At communication budget Cb = 0.5, MATCHA achieved nearly identical training losses to vanilla DecenSGD while reducing expected communication time per iteration by 50%.
5× less wall-clock time was required by MATCHA with Cb = 0.02 than vanilla DecenSGD to reach training loss 0.1 on CIFAR-100.
With maximal degree 10, MATCHA at Cb = 0.4 reduced mean communication time per iteration by 2.5× and achieved lower error than vanilla DecenSGD.
On a denser topology, MATCHA reduced communication time per iteration by approximately 3.3× without hurting error convergence.
Across increasing base-graph density, MATCHA kept 200-epoch training near 11 minutes while vanilla DecenSGD increased from 13 to 22 minutes.
At fixed communication budgets, MATCHA consistently outperformed periodic DecenSGD by using different matchings at different communication frequencies.

7 Concluding Remarks

MATCHA reduces decentralized SGD communication delay by sampling matchings more often on connectivity-critical links. Theoretical and experimental results indicate that it maintains or improves error-versus-iterations convergence across arbitrary node topologies.

MATCHA reduces communication delay over arbitrary node topologies through matching decomposition sampling.
Connectivity-critical links are communicated over with higher probability, while convergence is maintained or improved in error-versus-iterations terms.

A.1 Detailed Experimental Setting

The experiments cover image classification and language modeling on GPU-equipped worker nodes connected by high-bandwidth Ethernet. Dataset-specific training schedules and model configurations are specified for reproducibility.

Image Classification Tasks: CIFAR-10 and CIFAR-100 each contain 60,000 color images, with 10 and 100 classes respectively; training uses batch size 64 per worker.
Image Classification Tasks: CIFAR training starts at learning rate 0.8, decaying by 10 after 100 and 150 epochs, with vanilla DecenSGD trained for 200 epochs.
Language Model Task: The PTB language-modeling task uses 923,000 training words and a two-layer LSTM with 1,500 hidden nodes per layer.
Language Model Task: PTB training uses batch size 10, embedding size 1,500, initial learning rate 40, and 40 epochs.
Machines: Each worker node has one NVIDIA TitanX Maxwell GPU and a 40 Gbps Ethernet interface; MATCHA uses PyTorch and MPI4Py.

A.2 More Results

Additional results compare MATCHA with periodic DecenSGD and examine test accuracy under reduced communication budgets. MATCHA preserves vanilla DecenSGD accuracy at half budget, while further reductions cause only slight degradation.

Figure 6: MATCHA had nearly identical error convergence to vanilla DecenSGD, whereas P-DecenSGD performed consistently worse despite equal average communication time per iteration.
Figure 7: At Cb = 0.5, MATCHA consistently reached the same test accuracy as vanilla DecenSGD across different training tasks.
Figure 7: Further reducing the communication budget caused only slight degradation in MATCHA's final test accuracy.

B Proof of Theorem 1

The proof establishes MATCHA’s topology and parameter choices by connecting expected-topology connectivity to spectral-norm contraction, then casting the parameter search as tractable optimization.

Proof structure: The proof has three parts: establish positivity of the expected topology’s connectivity, prove contraction for any communication budget, and obtain α through semidefinite programming.The argument first analyzes the expected activated topology, then derives ρ < 1, and finally computes α through optimization.
Semidefinite formulation: The direct spectral-norm optimization is N-P hard because it contains a bilinear matrix inequality constraint.Introducing β converts the constraints into linear matrix inequalities, yielding the standard form of a semidefinite program.
Relaxation equivalence: The resulting optimization solution must satisfy α^2 = β, establishing equivalence between the relaxed semidefinite formulation and the original problem.The proof derives this equality by contradiction from the assumed optimal solution.
Spectral-norm bound: The activation-probability optimization minimizes an upper bound on the spectral norm ρ rather than jointly optimizing probabilities and α.Joint optimization is non-convex, so MATCHA separates the two parameter choices.

C Proofs of Theorem 2 and Corollary 1

These proofs analyze decentralized SGD through matrix-form updates, stochastic mixing, smoothness, and bounded variance to control disagreement and establish convergence-related bounds.

Matrix-form dynamics: The decentralized SGD update is written in matrix form and then analyzed by separating the averaged model from local-model discrepancies.The proof uses the consensus projector J and bounds the disagreement term through products of mixing matrices.
Mixing assumptions: The analysis assumes an i.i.d. sequence of symmetric, doubly stochastic m × m matrices for the decentralized mixing process.These matrices preserve the averaging structure used in the matrix-form proof.
Stochastic optimization bounds: The proof bounds stochastic-gradient terms using Lipschitz smoothness and bounded variance before summing the resulting inequalities across iterates.Expectation is taken over random mini-batches and other random variables, followed by averaging over iterations.
Disagreement control: The disagreement analysis decomposes its terms into T1 and T2 and controls them using the mixing lemma and Young’s inequality.The resulting bounds are substituted into the update analysis and rearranged to obtain the convergence estimate.
Stepsize condition: The convergence argument requires ηL ≤ (1 − √ρ)/(4√ρ), linking the stepsize to the spectral contraction factor ρ.The proof substitutes the resulting bound on D into the main estimate before completing the argument.