D2: Decentralized Training over Decentralized Data

By Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, Ji Liu. 2018

401 citations recorded by the source corpus.

While training a machine learning model using multiple workers, each of which collects data from their own data sources, it would be most useful when the data collected from different workers can be {\em unique} and {\em different}. Ironically, recent analysis of decentralized parallel stochastic gradient descent (D-PSGD) relies on the assumption that the data hosted on different workers are {\em not too different}. In this paper, we ask the question: {\em Can we design a decentralized parallel stochastic gradient descent algorithm that is less sensitive to the data variance across workers?} In this paper, we present D$^2$, a novel decentralized parallel stochastic gradient descent algorithm designed for large data variance \xr{among workers} (imprecisely, "decentralized" data). The core of D$^2$ is a variance blackuction extension of the standard D-PSGD algorithm, which improves the convergence rate from $O\left({\sigma \over \sqrt{nT}} + {(n\zeta^2)^{\frac{1}{3}} \over T^{2/3}}\right)$ to $O\left({\sigma \over \sqrt{nT}}\right)$ where $\zeta^{2}$ denotes the variance among data on different workers. As a result, D$^2$ is robust to data variance among workers. We empirically evaluated D$^2$ on image classification tasks where each worker has access to only the data of a limited set of labels, and find that D$^2$ significantly outperforms D-PSGD.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Federated & Distributed Learning, 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 Computational Theory and Mathematics

In Federated & Distributed Learning

In ML Systems & Hardware

Citations in the corpus

Privacy Amplification by Decentralization (2020, background): “cal analysis of (non-private) decentralized algorithms [37, 51, 35, 45, 40], owing to its simplicity and good empirical performance.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “Further, it is important to note that we do not assume a uniform bound on the variance (as many prior work, such as Li et al., 2019; Tang et al., 2018b; Lian et al., 2017; Assran et al., 2019) but instead allow the bound on the noise and the diversity to grow with the gradient norm (similar…”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “However, communication-efﬁciency for decentralized optimization has not been intensively studied, except for a few papers [20, 15, 41, 44, 45].”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “As most training data are generated in a decentralized manner, prior work proposes communication-efﬁcient algorithms (e.g., (Hsieh et al., 2017; McMahan et al., 2017; Shokri & Shmatikov, 2015; Lin et al., 2018; Tang et al., 2018)) for ML training over decentralized datasets.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “Most of the previous work used unbiased quantizing operation (Jiang & Agrawal, 2018; Tang et al., 2018a; Wangni et al., 2018; Zhang et al., 2017a) to ensure the convergence of the algorithm.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “These ideas have recently been introduced also to the decentralized setting by Tang et al. (2018a).”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “In this work, we focus on fully decentralized learning, which has recently attracted a lot of interest (Duchi et al., 2012; Wei and Ozdaglar, 2012; Colin et al., 2016; Lian et al., 2017; Jiang et al., 2017; Tang et al., 2018; Lian et al., 2018).”
Distributed Learning over Unreliable Networks (2018, background): “In Tang et al. (2018b), a new approach that admits a better performance than decentralized SGD when the data among workers is very different is studied.”
COLA: Decentralized Linear Learning (2018, background): “They further extend it to the asynchronous setting [17] and to deal with large data variance among nodes [36] or with unreliable network links [35].”
Variance Reduced Local SGD with Lower Communication Complexity (2019, methodology): “We bound the expected squared gradient norm of the average model, which is the commonly used metric to prove the convergence rate for non-convex problems [Ghadimi and Lan, 2013, Tang et al., 2018, Yu et al., 2019a].”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, background): “A current trend [104, 18, 100, 95, 7, 49, 53] is then to replace communication with the orchestrator by peer-to-peer communications between individual silos, which perform local partial aggregations of model updates.”
The Effect of Network Width on the Performance of Large-batch Training (2018, background): “In practice, these gains usually saturate beyond a few tens of compute nodes [6, 10, 11].”