MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling

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

182 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “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.”
rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, neutral): “SGD methods [1], [3]–[15], as well as other fundamental contributions to distributed first-order [16]–[20] and secondorder [21]–[25] optimization procedures.”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “The recent independent work MATCHA [45] makes communication only among a random small portion of work nodes at each round1.”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “…focus on the generalization performance (on the test-set) on standard machine learning benchmarks, hereby departing from previous work such as e.g. (Tang et al., 2018; Wang et al., 2019; Tang et al., 2019; Reisizadeh et al., 2019) that mostly considered training performance (on the train-set).”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, methodology): “MATCHA + relies on the knowledge of the underlay—probably an unrealistic assumption in an Internet setting—while our algorithms only require information about the connectivity graph.”
FetchSGD: Communication-Efficient Federated Learning with Sketching (2020, unknown): “However, carrying out too many local steps risks model drift due to the non-IID nature of local datasets (Wang et al., 2019a; Karimireddy et al., 2019a).”
Federated Learning with Compression: Unified Analysis and Sharp Guarantees (2020, background): “Another interesting direction for the purpose of reducing the communication complexity is to exploit the sparsity of communication network as explored in [12,22,50].”