MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, Soummya KararXiv 2019 · arXiv

Abstract

Decentralized Stochastic Gradient Descent (SGD) is a promising alternative to centralized architectures, mitigating the risk of a single parameter server bottleneck. However, it introduces a fundamental trade-off: dense connectivity improves convergence per iteration but increases communication delays, while sparse connectivity reduces delays but slows convergence. We introduce MATCHA (Matching Decomposition Sampling), an algorithm that breaks this bottleneck by decomposing the network into parallelizable matchings and sampling them based on their importance to global connectivity. Our results demonstrate that MATCHA can achieve up to a 5.2x wall-clock time speedup over vanilla decentralized SGD without compromising accuracy.

Introduction

In distributed machine learning, decentralized SGD allows nodes to communicate only with their immediate neighbors. While this avoids the central bottleneck of a parameter server, the communication overhead remains a significant challenge. Dense networks converge in fewer iterations but suffer from high communication delays per iteration. Conversely, sparse networks are fast per iteration but require many more iterations to converge.

MATCHA addresses this "no free lunch" scenario by providing a mechanism to achieve the fast convergence of dense networks with the low communication overhead of sparse ones.

The Communication Bottleneck

Standard decentralized SGD focuses on iteration complexity—the number of steps to reach a target error. However, in practice, wall-clock time is the critical metric. The time per iteration is often dominated by the node with the highest degree. A densely connected graph might converge in 1,000 iterations, but if each iteration takes 10 seconds due to communication congestion, it is outperformed by a sparse graph that takes 5,000 iterations at 1 second each.

The MATCHA Algorithm

MATCHA (Matching Decomposition Sampling) employs a three-step strategy to optimize communication:

  1. Matching Decomposition: The base network topology is decomposed into several "matchings"—sets of edges where no two edges share a vertex. This allows for parallel communication across links in a matching, reducing the effective delay to a single unit of time.
  2. Importance-Based Sampling: Not all links are equally vital for network connectivity. MATCHA assigns activation probabilities to each matching by solving a convex optimization problem that maximizes the algebraic connectivity ($\lambda_2$) of the expected graph for a given communication budget.
  3. Random Topology Sequence: During training, MATCHA randomly selects a subset of matchings to activate in each iteration based on these optimized probabilities. Critical "bridge" links are used frequently, while redundant links are sampled sparingly.
The base network topology used for decomposition into parallelizable matchings.

Experimental Results

The authors evaluated MATCHA on standard benchmarks, including CIFAR-10/100 (using WideResNet and ResNet-50) and language modeling on the Penn Treebank corpus.

Wall-Clock Speedup

On the CIFAR-100 dataset, MATCHA reached the target training loss 5.2x faster than vanilla decentralized SGD in terms of wall-clock time. This speedup is primarily due to the reduction in communication overhead at high-degree nodes and the strategic sampling of critical links.

Training curves for CIFAR-100 showing a 5.2x wall-clock time speedup for MATCHA compared to vanilla decentralized SGD.

Communication Efficiency

MATCHA maintains the same convergence rate as vanilla SGD while utilizing a significantly lower communication budget (2.2x to 3.1x less). It consistently outperforms periodic averaging methods because it intelligently identifies and prioritizes bottleneck links rather than treating all connections equally.

Key Insights

  • Spectral Norm as a Proxy for Convergence: The convergence rate of decentralized SGD is tied to the spectral norm of the mixing matrix. By optimizing for algebraic connectivity, MATCHA ensures the network behaves like a dense graph even when it is sparse on average.
  • Exploiting Parallelism: By focusing on matchings, MATCHA naturally leverages hardware capabilities for simultaneous disjoint communications.

Conclusion and Future Work

MATCHA effectively breaks the communication bottleneck in decentralized learning. Future research directions include extending the framework to directed graphs, handling dynamic or time-varying topologies, and exploring adaptive communication budgets that change throughout the training process.

This paper summary is based on "MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling" by researchers from Carnegie Mellon University and Bosch AI.

Summary updated

Abstract

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.
BibTeX
@misc{wang2019matcha,
  author = {Jianyu Wang and Anit Kumar Sahu and Zhouyi Yang and Gauri Joshi and Soummya Kar},
  title = {{MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling}},
  year = {2019},
  eprint = {1905.09435},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.09435},
}
Figure