Source-linked AI summary
D$^2$: Decentralized Training over Decentralized Data
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, Ji Liu
TL;DR
The paper addresses decentralized SGD’s sensitivity to large data variation across workers, which conflicts with settings where workers hold unique data. It proposes D², a variance-reduced extension of D-PSGD, and reports improved convergence and stronger image-classification performance under highly nonuniform data.
Problem
Existing decentralized SGD analyses assume bounded cross-worker data variation, despite practical settings in which workers’ data may be unique and substantially different.
Method
D² extends D-PSGD with a variance-reduction component that linearly combines current and previous stochastic gradients and local models.
Results
D² significantly outperforms D-PSGD on image classification when workers access only limited sets of labels.
Takeaways & Limitations
D² is designed to remain robust under high data variance and removes dependence on the global outer-variance bound ζ.
Takeaways & Limitations
The paper leaves decentralized handling of batch information for batch-normalized modern neural networks as future work.
Abstract
from arXiv · showhide
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.
1 Introduction
Decentralized learning lets workers communicate only with neighbors, which is useful when centralized communication is costly or unavailable. D² targets the resulting sensitivity to large data differences across workers by adding variance reduction to D-PSGD.
- Motivation: Decentralized learning uses neighbor-only communication to train toward a common model without centralizing all data.This setting is useful when centralized communication is expensive or impossible, or when network latency is high.
- Motivation: Existing decentralized analyses assume bounded variation across workers, although practical applications may require workers’ data to be unique and substantially different.Large cross-worker variation can make existing approaches converge slowly both theoretically and empirically.
- D² contribution: D² combines standard D-PSGD with a variance-reduction component that stores each worker’s previous stochastic gradient and local model.The stored quantities are linearly combined with the current stochastic gradient and local model.
- D² contribution: D² removes the convergence-rate dependence on global outer variance ζ.The paper identifies ζ² as data variation among workers and σ² as variance within each worker.
- Empirical validation: D² significantly outperforms D-PSGD on image classification when each worker accesses only a limited set of labels.The optimization problem is decentralized, with workers connected by a graph and exchanging information only with neighbors.
2 Related work
Related work covers centralized and decentralized stochastic optimization, decentralized algorithms for constrained and networked problems, and variance-reduction methods. It highlights that many variance-reduction techniques were designed for centralized settings, while decentralized SGD faces cross-worker variance.
- Stochastic gradient descent: Centralized parallel SGD uses a central worker to aggregate gradients from leaf workers and has been applied in major deep-learning frameworks.The cited examples include CNTK, MXNet, and TensorFlow.
- Stochastic gradient descent: C-PSGD can achieve linear speedup with respect to the number of leaf workers.The passage identifies this as a consequence of its convergence rate.
- Decentralized algorithms: Decentralized algorithms operate over connected networks using information exchange between neighboring workers rather than a central server.They are especially useful under limited bandwidth or high latency and may be favorable when data privacy is sensitive.
- Decentralized algorithms: Prior decentralized SGD theory can require diminishing or iteration-dependent stepsizes because of variance between workers’ data.The paper calls this cross-worker variation outer variance.
- Decentralized SGD: Prior work analyzed D-PSGD and established a convergence rate with linear speedup similar to centralized parallel SGD.The cited analysis includes settings with bounded gradients and general convex objectives.
- Variance reduction: Variance-reduction methods such as SVRG and SAGA were mostly designed for centralized approaches, with DSA representing a decentralized example.The cited centralized methods also include SAG, MISO, and mS2GD.
3 Preliminary: decentralized stochastic gradient descent
D-PSGD maintains local models, averages them with neighbors using a mixing matrix, and then performs stochastic-gradient updates. Its convergence analysis characterizes variation within workers and among workers, while D² is introduced to remove dependence on the latter.
- D-PSGD: D-PSGD lets every worker maintain a local variable and perform iterative stochastic-gradient updates.Each worker samples data from its local distribution D_i.
- D-PSGD: Each worker queries neighbors and takes a weighted average of its own and its neighbors’ local variables.The weight W_ij is zero when workers i and j are not connected.
- D-PSGD: D-PSGD’s global update can be viewed as a stochastic-gradient update followed by network mixing.The paper states that this update admits the rate given in its convergence theorem.
- Convergence analysis: The convergence theorem distinguishes σ and ς as variation within each worker and among all workers, respectively.The network property is represented by ρ, with additional quantities D1 and D2 defined in the theorem’s surrounding analysis.
- D² motivation: D² improves the convergence rate by removing dependence on the global bound of outer variance ζ.This is the stated motivation for moving beyond the standard D-PSGD guarantee.
4 The D2 algorithm
D² augments decentralized SGD with information from consecutive iterations. Its intuition is that, near a solution, successive stochastic gradients can reduce the effect of cross-worker variation that affects D-PSGD.
- Algorithm: D² updates each worker using its current local model and information from the preceding iteration.The algorithm stores local models and stochastic gradients from both the current and previous iterations.
- Algorithm: D² exchanges local models when the synchronization barrier is met and uses the resulting decentralized update.The complete procedure is summarized in Algorithm 1.
- Intuition: The mean model in D² is updated in the form of standard stochastic gradient descent.This provides the global perspective used to explain the algorithm’s intuition.
- Intuition: Near the optimum, D-PSGD is affected by the expected squared norm of the stochastic gradient at the optimum.The paper introduces this comparison to explain why D² can improve D-PSGD.
- Intuition: Near the optimum, D² instead depends on the expected squared norm of the difference between consecutive stochastic gradients.The paper states this quantity as the basis of D²’s convergence behavior near a solution.
5 Theoretical guarantee
Under assumptions on smoothness, stochastic-gradient variance, the mixing matrix, spectral properties, and initialization, D2 has a convergence guarantee whose leading term is independent of cross-worker data variance. The analysis also reports linear speedup and a better dependence than D-PSGD.
- Assumptions: D2’s guarantee assumes Lipschitzian gradients, bounded stochastic-gradient variance within each worker, a symmetric confusion matrix, spectral conditions, and zero initialization.These assumptions define the setting for Theorem 2 and its corollary.
- Convergence guarantee: Theorem 2 establishes a convergence rate for Algorithm 1 under the stated assumptions and a constant steplength satisfying 1 −24C2γ2L2 > 0.The corollary specializes the steplength to obtain the stated order of convergence.
- Convergence guarantee: The corollary emphasizes convergence order rather than optimized constants, which can be improved through different parameter choices and tighter inequalities.The paper explicitly notes that its main result is the order of convergence.
- Linear speedup: The leading convergence term is consistent with C-PSGD, indicating linear speedup with respect to the number of nodes.The speedup claim is based on the leading term of the reported convergence rate.
- Superiority over D-PSGD: Compared with D-PSGD, D2’s convergence rate depends only on inner stochastic-gradient variance, whereas D-PSGD also requires a bound on global variance across workers.The paper states that this yields a much better convergence rate than D-PSGD.
6 Experiments
The experiments compare D2 with centralized and decentralized SGD under highly varied and shuffled worker data. D2 is especially effective in the unshuffled setting, while all strategies converge similarly after shuffling.
- Experiment Settings: D2 is evaluated against centralized and decentralized SGD in TransferLearning and LeNet experiments.The study uses ImageNet-derived features for TransferLearning and CIFAR10 for LeNet.
- Experiment Settings: Each worker exclusively accesses a subset of classes, maximizing data variation in the default unshuffled setting.TransferLearning uses 16 workers with one class each; LeNet uses 5 workers with two classes each, using a ring topology.
- Experiment Settings: Convergence rate, rather than wall-clock speed, is the primary metric because D2 makes only a minor change to D-PSGD.The paper states that D2 and D-PSGD have almost the same per-epoch speed and are no slower than the centralized algorithm.
- Unshuffled Case: In the unshuffled case, D2 converges much faster than D-PSGD and reaches almost the centralized algorithm’s loss.For LeNet, D-PSGD does not converge with learning rate 0.05; a 50x smaller rate enables convergence but causes a long initial stagnation.
- Shuffled Case: In the shuffled case, all strategies have similar convergence rates when worker data variation is small.This comparison supports D2’s effectiveness under larger data variation between workers.
7 Conclusion
The paper proposes D2, which combines D-PSGD with variance reduction to improve convergence under large worker-to-worker data variance. Experiments report robustness to this variance while retaining decentralized advantages over centralized training.
- 7 Conclusion: D2 integrates D-PSGD with variance reduction to improve its convergence rate.The variance reduction technology differs from centralized methods such as SVRG and SAGA.
- 7 Conclusion: D2 converges at a rate similar to centralized SGD when data variance is large, whereas D-PSGD does not reach comparable solution quality.The reported advantage is validated experimentally.
- 7 Conclusion: D2 retains D-PSGD’s performance benefit over the centralized strategy while remaining robust to large worker data variance.
Supplemental Materials
The supplemental material develops the convergence analysis using spectral decomposition of the symmetric communication matrix and supporting lemmas. It also identifies a lower-bound condition on the matrix spectrum for convergence.
- Spectral Analysis: The proof analyzes the communication matrix through the decomposition W = PΛP⊤, with orthogonal eigenvectors and ordered eigenvalues.This transforms the iteration into spectral components for the subsequent analysis.
- Spectral Analysis: The consensus eigenvalue is λ1 = 1 with eigenvector v1 = 1/√n(1, 1, · · · , 1)⊤.
- Spectral Analysis: The analysis shows that components associated with 1/3 < λi < 1 decay to zero, explaining the role of the confusion matrix.
- Convergence Proof: The convergence proof uses bounds on local-model disagreement, stochastic-gradient variance, and a sufficiently small stepsize.The analysis explicitly requires 1 − 24C2γ^2L^2 > 0 for one bound.
- Convergence Boundary: The algorithm fails to converge when the smallest eigenvalue condition is violated, establishing −1/3 as the infimum of λn.