Source-linked AI summary
Communication Compression for Decentralized Training
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, Ji Liu
TL;DR
The paper asks whether decentralization and communication compression can jointly support distributed training under both high latency and low bandwidth. It develops extrapolation and difference compression methods for decentralized SGD and proves convergence at O(1/sqrt(nT)). Experiments report significant superiority over other strategies in networks with both constraints.
Problem
The paper studies whether combining decentralization for high latency with compression for low bandwidth can produce robust distributed training.
Method
The paper develops compressed decentralized training with extrapolation compression and difference compression, using unbiased stochastic compression.
Results
O(1/sqrt(nT)) convergence is proved for both algorithms, and quantized decentralized training outperforms other strategies significantly under high latency and low bandwidth.
Takeaways & Limitations
The proposed framework combines quantization and decentralization for distributed training across varied network conditions.
Takeaways & Limitations
DCD-PSGD requires a compression bound tied to the spectral gap and can diverge under very aggressive compression.
Abstract
from arXiv · showhide
Optimizing distributed learning systems is an art of balancing between computation and communication. There have been two lines of research that try to deal with slower networks: {\em communication compression} for low bandwidth networks, and {\em decentralization} for high latency networks. In this paper, We explore a natural question: {\em can the combination of both techniques lead to a system that is robust to both bandwidth and latency?} Although the system implication of such combination is trivial, the underlying theoretical principle and algorithm design is challenging: unlike centralized algorithms, simply compressing exchanged information, even in an unbiased stochastic way, within the decentralized network would accumulate the error and fail to converge. In this paper, we develop a framework of compressed, decentralized training and propose two different strategies, which we call {\em extrapolation compression} and {\em difference compression}. We analyze both algorithms and prove both converge at the rate of $O(1/\sqrt{nT})$ where $n$ is the number of workers and $T$ is the number of iterations, matching the convergence rate for full precision, centralized training. We validate our algorithms and find that our proposed algorithm outperforms the best of merely decentralized and merely quantized algorithm significantly for networks with {\em both} high latency and low bandwidth.
1 Introduction
The paper targets distributed training over networks where decentralization addresses latency and compression addresses bandwidth, asking whether combining them can handle both constraints. It proposes two compressed decentralized methods with convergence matching centralized full-precision training.
- Motivation: High communication latency motivates decentralization, while low bandwidth or communication cost motivates compression through sparsification or quantization.The paper focuses on stochastically unbiased quantization, while noting that the techniques also apply to other unbiased compression schemes.
- Problem: Directly quantizing models exchanged during decentralized training is a natural but challenging combination of the two approaches.Decentralized methods typically exchange local models, whereas quantized methods commonly exchange quantized gradients and update unquantized models.
- Contributions: The proposed algorithms are extrapolation compression D-PSGD (ECD-PSGD) and difference compression D-PSGD (DCD-PSGD).Both are decentralized parallel stochastic gradient descent methods.
- Contributions: O(1/sqrt(nT)) convergence is established for both methods, consistent with centralized parallel SGD and decentralized SGD.Here n denotes the number of workers and T the number of iterations.
- Comparison: DCD-PSGD can be slightly better under large inter-node data variation, whereas ECD-PSGD is more robust to aggressive quantization.Extremely low precision can cause DCD-PSGD to diverge because it has a strict quantization constraint.
2 Related work
Related work covers stochastic gradient descent, compression, centralized parallel training, and decentralized optimization. These lines address large-scale computation, communication reduction, and network topology through different algorithmic designs.
- Stochastic gradient descent: SGD is a stochastic variant of gradient descent widely used for large-scale machine learning problems.The cited literature reports an optimal convergence rate O(1/sqrt(nT)) for SGD.
- Centralized algorithms: Centralized parallel methods use a central node to control leaf nodes, with prior work studying latency, asynchronous updates, and quantized SGD.Examples include TensorFlow, MXNet, and CNTK.
- Decentralized algorithms: Decentralized algorithms solve optimization over decentralized topologies and can avoid communication traffic through a central node.Prior work also reports that decentralized training can outperform centralized counterparts.
- D-PSGD: D-PSGD research analyzes convergence under varying topologies and establishes linear speedup for decentralized training.The related work includes results for general convex objectives and asynchronous D-PSGD.
- Compression: Compression research includes unbiased randomized quantization and randomized sparsification for reducing communicated information.The paper restricts its discussion to unbiased stochastic compression for convergence and correctness.
3 Preliminary: decentralized parallel stochastic gradient descent (D-PSGD)
D-PSGD lets nodes exchange local models with connected neighbors and combine them using graph weights before stochastic-gradient updates. Its global update uses weighted communication followed by a gradient step.
- Algorithm: Unlike centralized SGD, D-PSGD has no central averaging node; each node exchanges its local model with neighbors.Neighbor communication is restricted by the decentralized graph topology.
- Communication: Each node forms a weighted average of connected neighbors’ models using nonnegative matrix weights W_ij.W_ij = 0 indicates that nodes i and j are not connected.
- Iteration steps: At each iteration, nodes sample local data, query neighbors’ variables, average received models, and update using a stochastic gradient.The learning rate is denoted by γ_t.
- Global form: The global D-PSGD update is X_t+1 = X_tW − γ_tG(X_t; ξ_t).X stores node models, while G stores the corresponding stochastic gradients.
- Convergence: D-PSGD has a convergence rate without assuming convexity when the learning rate is chosen appropriately.The rate expression also depends on stochastic variance quantities σ and ζ.
4 Quantized, Decentralized Algorithms
The paper develops two compressed decentralized SGD algorithms that avoid the failure of naively compressing exchanged models. Difference compression exchanges model differences, while extrapolation compression estimates neighbors from extrapolated values and supports aggressive compression.
- ECD-PSGD and DCD-PSGD compress information exchanged between neighboring nodes while retaining decentralized stochastic-gradient updates.DCD-PSGD exchanges compressed differences between successive local models and stores neighbors’ previous model replicas.
- Naively compressing decentralized model exchanges fails to converge even with unbiased stochastic compression and diminishing learning rates.The accumulated compression error causes the failure described for the straightforward combination.
- DCD-PSGD requires bounded compression noise and restricts the compression level, while ECD-PSGD removes that restriction with a small computation-efficiency sacrifice.DCD-PSGD may diverge under very aggressive compression; ECD-PSGD is described as robust to aggressive compression or quantization.
- O(1/√(nT)) is the leading convergence rate established for the compressed decentralized algorithms.The rate is reported as consistent with centralized parallel SGD and supports linear speedup with respect to the number of nodes when T is large.
- ECD-PSGD sends an extrapolated z-value instead of the local model, allowing each node to estimate a neighbor’s value with diminishing estimate error.The extrapolation procedure is presented as the mechanism for robust neighbor estimation under compression.
5 Experiments
Experiments evaluate compressed decentralized training against centralized Allreduce across convergence, scale, and network conditions. The proposed methods preserve convergence while improving runtime when latency or bandwidth constrains communication.
- Experimental setup and convergence: Low-precision decentralized training speeds up training without hurting convergence across diverse network conditions.The evaluation compares the proposed algorithms with an Allreduce implementation under varied bandwidth and latency.
- Runtime under network conditions: Under high latency, decentralized implementations outperform Allreduce because they use fewer communications.Both full-precision and low-precision decentralized methods show this advantage in the reported runtime comparisons.
- Runtime under network conditions: Under very low bandwidth, low-precision decentralized training achieves the best performance among the compared implementations.Reduced data volume makes low precision faster, while full-precision decentralized training degrades as bandwidth declines.
- Scalability and aggressive compression: On 16 nodes with 8 bits, Algorithms 1 and 2 retain essentially the same convergence rate as Allreduce, demonstrating scalability.With 4-bit compression, neither matches Allreduce; Algorithm 1 continues reducing training loss, whereas Algorithm 2 diverges initially.
6 Conclusion
The paper combines quantization and decentralization for distributed stochastic gradient descent under imperfect network conditions. It develops and analyzes two algorithms, then finds that quantized decentralized training significantly outperforms other strategies when latency is high and bandwidth is low.
- Conclusion: The study addresses combining quantization and decentralization for distributed stochastic gradient descent under imperfect network conditions.These techniques target communication constraints associated with distributed training.
- Conclusion: The paper develops two quantized decentralized algorithms, analyzes their theoretical properties, and evaluates them across varied network conditions.The conclusion covers both theoretical analysis and empirical performance study.
- Conclusion: Under high latency and low bandwidth, quantized decentralized training significantly outperforms the other evaluated strategies.This is the paper’s stated conclusion for networks combining both adverse conditions.
Supplemental Materials: Proofs
The supplemental proofs establish general bounds for compressed decentralized SGD by separating optimization, consensus, and compression-noise effects. A coordinate transformation based on the communication matrix simplifies the analysis.
- General compressed update: Both proposed algorithms are reformulated using a common update rule with compression noise Qt.The proofs then specify Qt separately for extrapolation and difference compression.
- General bounds: The analysis proves general bounds for compressed D-PSGD that support the subsequent proofs of both algorithms.These bounds track the effect of compression on convergence efficiency.
- Consensus analysis: A central challenge is ensuring that every local model converges toward the network-wide average model Xt.The proof therefore separately analyzes consensus among local variables and optimization of the average iterate.
- Coordinate transformation: A coordinate transformation using the eigenvectors of the doubly stochastic communication matrix decomposes average and disagreement dynamics.The transformed coordinates expose decay of non-average components through the corresponding eigenvalues.
- Convergence inequalities: The proof combines optimization inequalities with bounds on compression noise and stochastic-gradient variance.The resulting inequalities relate objective decrease to gradient norms, compression error, and variance terms.
B Analysis for Algorithm 1
The analysis of Algorithm 1 bounds the disagreement and quantization-noise terms under the communication-matrix assumptions. It also imposes a condition on the step-size-related parameter α for the bound to hold.
- Disagreement bound: For Algorithm 1, the proof derives bounds on the transformed disagreement sequence using the communication matrix’s non-leading eigenvalues.The sequence is analyzed through the spectral structure introduced for the decentralized update.
- Quantization-noise bound: Quantization noise is analyzed through matrix elements, with off-diagonal expectations vanishing because node-wise compression noise is independent.The proof introduces τij to distinguish diagonal and off-diagonal terms.
- Assumption and bound: The bound requires α to be small enough that (1 − ρ)^2 − 4µ^2α^2 > 0.This condition ensures the denominator-like expression used in the subsequent bound remains positive.
Proof to Theorem 1
The proof combines previously established lemmas and inequalities to complete the convergence argument, under a step-size condition on γ.
- The proof combines Lemma 8 with equation (22) as a central step.
- A sufficient step-size condition is 1 − 3D1L2γ2 > 0.
- The argument summarizes both sides of equation (23) and applies equation (24).
- The proof concludes after these lemma combinations and inequality manipulations.
Proof to Corollary 2
The corollary proof simplifies the preceding inequality using a bound on D1 and removes a gradient-norm term from the left-hand side.
- The proof removes the ∥∇f(Xt)∥2 term from the left-hand side and replaces 1 − D3 with 1.
- The bound D1 = D2 1 −ρ2 + 1 (1 −ρ)2 ≤ D2 + 1 is used.
- The resulting inequality is obtained by combining the preceding bound with equation (26).
C Analysis for Algorithm 2
The analysis bounds compression-related quantities for Algorithm 2 and combines these bounds with earlier lemmas to establish convergence and consensus. It also identifies why directly compressing D-PSGD fails.
- C Analysis for Algorithm 2: The analysis proves an upper bound for compression noise using equations (3) and (4) in Algorithm 2.
- C Analysis for Algorithm 2: The convergence rate for Algorithm 2 follows by combining the established result with Lemmas 8 and 7.
- C Analysis for Algorithm 2: The analysis states that all nodes converge to the same value.
- C Analysis for Algorithm 2: Lemmas 12 and 13 provide bounds used in the convergence analysis of Algorithm 2.
- C Analysis for Algorithm 2: The compressed D-PSGD update adds random compression noise Qt to exchanged models Xt.
- C Analysis for Algorithm 2: Naive compression fails because its error does not diminish, unlike stochastic gradient variance controlled by γt.