Source-linked AI summary
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, Ji Liu
TL;DR
Centralized distributed learning can bottleneck on communication at its central node, motivating the question of whether decentralized PSGD can be faster. The paper analyzes D-PSGD theoretically and empirically, finding comparable computational complexity to C-PSGD and potential speedups under unfavorable network conditions.
Problem
The paper asks whether decentralized PSGD can outperform centralized PSGD despite existing analyses showing no advantage and centralized communication bottlenecks.
Method
The paper theoretically analyzes D-PSGD and validates the analysis empirically across frameworks, network configurations, and computation platforms.
Results
D-PSGD achieves the same convergence rate as C-PSGD while avoiding centralized communication traffic, and can be up to 10× faster on low-bandwidth or high-latency networks.
Takeaways & Limitations
Decentralized algorithms can admit linear speedup and outperform centralized algorithms in supported network regimes rather than serving only as a compromise.
Takeaways & Limitations
D-PSGD’s potential limitation is the cost of synchronization; removing the synchronization barrier requires more complicated analysis and is left for future work.
Abstract
from arXiv · showhide
Most distributed machine learning systems nowadays, including TensorFlow and CNTK, are built in a centralized fashion. One bottleneck of centralized algorithms lies on high communication cost on the central node. Motivated by this, we ask, can decentralized algorithms be faster than its centralized counterpart? Although decentralized PSGD (D-PSGD) algorithms have been studied by the control community, existing analysis and theory do not show any advantage over centralized PSGD (C-PSGD) algorithms, simply assuming the application scenario where only the decentralized network is available. In this paper, we study a D-PSGD algorithm and provide the first theoretical analysis that indicates a regime in which decentralized algorithms might outperform centralized algorithms for distributed stochastic gradient descent. This is because D-PSGD has comparable total computational complexities to C-PSGD but requires much less communication cost on the busiest node. We further conduct an empirical study to validate our theoretical analysis across multiple frameworks (CNTK and Torch), different network configurations, and computation platforms up to 112 GPUs. On network configurations with low bandwidth or high latency, D-PSGD can be up to one order of magnitude faster than its well-optimized centralized counterparts.
1 Introduction
The introduction asks whether decentralized PSGD can outperform centralized approaches despite centralized systems’ communication bottleneck. It motivates D-PSGD and presents theoretical and empirical evidence for such an advantage.
- Centralized PSGD uses a parameter server that aggregates gradients, but concurrent communication can congest the central node and degrade performance on low-bandwidth networks.
- Decentralized methods let nodes communicate only with neighbors, avoiding a single central communication node.
- The paper addresses the open question of whether decentralized methods can outperform centralized algorithms when both communication patterns are feasible.
- D-PSGD has similar total computational complexity to C-PSGD while requiring less communication for the busiest node.
- The paper theoretically identifies cases where decentralized algorithms can be faster than centralized counterparts, reporting an asymptotically linear speedup as more nodes are used.
- Empirical results across CNTK, Torch, varied networks, and platforms up to 112 GPUs found D-PSGD up to 10× faster than C-PSGD on low-bandwidth or high-latency networks.
2 Related work
Related work covers centralized PSGD, decentralized stochastic optimization, and consensus-oriented algorithms. Prior decentralized methods lacked a demonstrated speedup as node counts increased, motivating the paper’s D-PSGD analysis.
- Centralized parallel SGD: Centralized parameter-server PSGD evaluates n stochastic gradients per iteration and has convergence rate O(1/(Kn)).
- Decentralized parallel stochastic algorithms: Prior decentralized stochastic algorithms reported complexities such as O(n/ϵ^2) for convex objectives and O(n/ϵ) for strongly convex objectives.
- Decentralized parallel stochastic algorithms: Existing decentralized stochastic-gradient methods were not proved to achieve speedup when the number of nodes increased.
- Decentralized parallel stochastic algorithms: Earlier decentralized algorithms differed from D-PSGD in allowing no simultaneous communication and computation, or required restrictive convexity and bounded-domain assumptions.
- Other decentralized algorithms: Consensus research studies decentralized methods for computing means across distributed data in control, privacy, and wireless-sensing settings.
3 Decentralized parallel stochastic gradient descent (D-PSGD)
D-PSGD distributes optimization across a connected decentralized network, where nodes compute local stochastic gradients, average variables with neighbors, and update locally in synchronized iterations.
- Network model: D-PSGD represents the decentralized topology as an undirected graph with a symmetric doubly stochastic weight matrix W.W_ij specifies how much node j affects node i, while zero weights indicate disconnected nodes.
- Protocol: Each node maintains its own local variable and runs the synchronous protocol concurrently.The algorithm is organized around synchronized iterations and a local variable at every node.
- Protocol: At each iteration, every node computes a stochastic gradient using its current local variable.The gradient uses the node-specific iterate x_k,i and a random sample.
- Protocol: After synchronization, nodes exchange local variables with neighbors and average received values with their own.Communication is restricted to neighboring nodes rather than a central aggregator.
- Protocol: Each node updates its local variable using the neighbor average and its local stochastic gradient.The global view concatenates local variables, samples, and stochastic gradients into matrix and vector representations.
4 Convergence rate analysis
The analysis shows that D-PSGD can match centralized PSGD’s convergence rate while reducing per-node communication, yielding asymptotic computational speedup under sufficiently large iteration counts. The result depends on standard smoothness, spectral-gap, and variance assumptions, and the speedup has explicit iteration and topology limits.
- Convergence comparison: D-PSGD has a convergence rate similar to C-PSGD while avoiding the parameter server’s communication traffic jam.This comparison motivates analyzing convergence and communication together.
- Assumptions: The convergence analysis assumes Lipschitzian gradients, spectral gap ρ < 1, and bounded stochastic-gradient variance.These are stated as the paper’s common assumptions for the convergence results.
- Speedup: D-PSGD achieves asymptotically linear computational speedup as the number of nodes increases.The analysis states that total computational complexity remains unaffected by the number of nodes while each node bears a smaller share.
- Communication cost: D-PSGD matches C-PSGD’s rate but reduces each node’s maximum communication from O(n) to O(the degree of the network).For a ring, the degree can be O(1), substantially smaller than the centralized per-node communication burden.
- Limits: The linear speedup requires sufficiently large K, with ring-network bounds restricting the number of nodes to K^1/9 or K^1/13 in different scenarios.The paper notes that these upper bounds may potentially be improved.
5 Experiments
Experiments across frameworks, network configurations, and platforms validate that D-PSGD can outperform centralized SGD when communication is limiting. D-PSGD maintains comparable convergence while reducing communication bottlenecks and scaling effectively across machines and GPUs.
- End-to-end performance: Under slow-network conditions, D-PSGD converges faster in wall-clock time to the same solution quality as centralized SGD.Its convergence rate by epochs remains similar to centralized SGD, including with 112 nodes.
- Network sensitivity: When bandwidth is low or latency is high, D-PSGD can be one order of magnitude faster than centralized competitors.Balanced communication helps against parameter-server congestion, while fewer communications help against AllReduce latency.
- Scaling: D-PSGD reaches up to 5× speedup on seven GPUs, with near-linear speedup through four GPUs.Beyond four GPUs, synchronization and shared PCIe bandwidth limit scaling on the tested machine.
- Bandwidth-constrained training: On inexpensive Gigabit Ethernet, D-PSGD shows better scalability than centralized approaches when network bandwidth becomes a constraint.The experiments observe congestion for centralized parameter-server training even with a relatively small ResNet-32 model.
- Scaling: D-PSGD’s per-epoch training time increases only 3% over single-machine SGD, while reaching training loss 0.2 in 5 epochs on 16 machines.The corresponding epoch counts are 80, 20, 10, and 5 for 1, 4, 8, and 16 machines.
- Accuracy: After 160 epochs, D-PSGD test errors are 0.0715, 0.0746, and 0.0735 on 4, 8, and 16 machines, respectively.These values are below the reported 0.0751 error for the same 32-layer residual network.
6 Conclusion
The paper concludes that D-PSGD matches C-PSGD in convergence rate while avoiding centralized communication congestion. It identifies synchronization cost as a limitation and proposes evaluation beyond 112 GPUs as future work.
- D-PSGD achieves the same convergence rate, or computational complexity, as C-PSGD.
- D-PSGD can outperform C-PSGD by avoiding communication traffic jams.
- The conclusion presents linear speedup and improved performance over centralized algorithms as the paper’s main decentralized-algorithm result.
- The potential limitation of D-PSGD is the cost of synchronization.
- Future work includes deploying D-PSGD to clusters beyond 112 GPUs and exploring mobile environments.
Supplemental Materials: More Experiments
The supplemental experiments compare centralized and decentralized SGD on Joule and Yelp workloads using Torch and multiple GPUs. On Joule, both methods show similar convergence and test error.
- Methodology: The evaluation uses Joule and Yelp datasets on an IBM Power server equipped with 8 K80 GPUs.Joule has 2.5K training samples, 1K test samples, and 311 classes; Yelp has 500K training samples, 2K test samples, and 5 classes.
- Methodology: The experiments compare centralized SGD through Torch’s DataParallelTable with the authors’ decentralized SGD implementation.DataParallelTable is described as an NCCL-based centralized parallel SGD implementation.
- Convergence results and test accuracy: On Joule, centralized and decentralized SGD reach similar training loss of 0.96 at roughly the same convergence rate.
- Convergence results and test accuracy: On Joule, centralized and decentralized SGD achieve similar testing error of 43%.
- Convergence results and test accuracy: The supplemental figures report training loss and test error comparisons for the Joule and Yelp datasets.
Supplemental Materials: Proofs
The supplemental materials prove the paper’s theoretical results by bounding disagreement, averaged optimization quantities, and error terms under stated assumptions. The proofs conclude by combining these bounds and applying the relevant parameter conditions.
- The proof section states that it provides proofs for all theoretical results in the paper.
- Several proof steps rely on the stated assumptions, geometric-series summation, and the identity 2⟨a, b⟩ = ∥a∥2 + ∥b∥2 − ∥a − b∥2.
- The proof derives bounds for intermediate terms T1, T2, and T3, including auxiliary terms T4 through T7.
- The analysis bounds the squared distance Qk,i between a local optimization variable and the average across nodes.
- The analysis then bounds the average quantity Mk across nodes and the accumulated error over iterations k = 0 to K − 1.
- The final theoretical bounds are obtained by selecting parameter conditions and substituting the prescribed step size into earlier theorems and corollaries.