D$^2$: Decentralized Training over Decentralized Data

TLDR

Decentralized training of machine learning models often assumes workers’ data are similar, yet in practice each worker may collect unique, heterogeneous data. The study aims to develop a decentralized SGD algorithm that remains effective despite high data variance across workers. D$^2$ extends D-PSGD with a variance‑reduction mechanism that reduces the convergence bound to $O(σ/√{nT})$ by mitigating inter‑worker data variance. Experiments show D$^2$ is robust to data variance and significantly outperforms standard D-PSGD on image‑classification tasks with label‑restricted workers.

Abstract

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({σ\over \sqrt{nT}} + {(nζ^2)^{\frac{1}{3}} \over T^{2/3}}\right)$ to $O\left({σ\over \sqrt{nT}}\right)$ where $ζ^{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.