Source-linked AI summary
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression
Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, Ji Liu
TL;DR
Large-scale distributed stochastic-gradient training is limited by communication, while prior error-compensated compression does not match the realistic two-pass parameter-server model. The paper analyzes DOUBLESQUEEZE, which compresses on both workers and the parameter server, and reports improved compression tolerance, linear speedup, and empirical validation.
Problem
Communication is a main bottleneck in distributed training, and prior error compensation addressed worker gradients but not the aggregated parameter-server gradient.
Method
DOUBLESQUEEZE performs error-compensated compression on both worker and parameter-server sides in the two-pass communication setting.
Results
The analysis reports better tolerance to compression than non-error-compensated approaches, linear speedup with the number of workers, and empirical validation.
Takeaways & Limitations
The proposed approach compresses all information exchanged over the network while retaining convergence guarantees for parallel error-compensated SGD.
Takeaways & Limitations
The compression restriction relies on a third assumption with parameter α, which is not required to be bounded in [0, 1).
Abstract
from arXiv · showhide
A standard approach in large scale machine learning is distributed stochastic gradient training, which requires the computation of aggregated stochastic gradients over multiple nodes on a network. Communication is a major bottleneck in such applications, and in recent years, compressed stochastic gradient methods such as QSGD (quantized SGD) and sparse SGD have been proposed to reduce communication. It was also shown that error compensation can be combined with compression to achieve better convergence in a scheme that each node compresses its local stochastic gradient and broadcast the result to all other nodes over the network in a single pass. However, such a single pass broadcast approach is not realistic in many practical implementations. For example, under the popular parameter server model for distributed learning, the worker nodes need to send the compressed local gradients to the parameter server, which performs the aggregation. The parameter server has to compress the aggregated stochastic gradient again before sending it back to the worker nodes. In this work, we provide a detailed analysis on this two-pass communication model and its asynchronous parallel variant, with error-compensated compression both on the worker nodes and on the parameter server. We show that the error-compensated stochastic gradient algorithm admits three very nice properties: 1) it is compatible with an \emph{arbitrary} compression technique; 2) it admits an improved convergence rate than the non error-compensated stochastic gradient methods such as QSGD and sparse SGD; 3) it admits linear speedup with respect to the number of workers. The empirical study is also conducted to validate our theoretical results.
1. Introduction
Distributed stochastic-gradient training is communication-intensive, motivating compressed and error-compensated methods. This paper studies DOUBLESQUEEZE for the realistic parameter-server setting, where both worker-to-server and server-to-worker communication require compression.
- Parallel SGD distributes data across workers, computes local stochastic gradients, aggregates them, and returns the result to each node.
- Communication cost is a main bottleneck in large-scale distributed training.
- Gradient quantization or sparsification reduces transmitted information, but compression can slow convergence by losing information.
- Parameter-server training requires compressing the aggregated gradient as well as local worker gradients because aggregation can make the result dense.
- DOUBLESQUEEZE applies error-compensated compression in this two-pass setting and is theoretically reported to tolerate compression better than non-error-compensated algorithms.
- The paper claims n rounds of communication per iteration, compression of all transmitted information, linear speedup with n workers, and acceleration in the non-convex case.
2. Related Work
Related work develops centralized, decentralized, asynchronous, and communication-efficient approaches to distributed learning, including compressed gradients and error compensation. Prior studies analyze compression and error compensation, but their guarantees and communication patterns differ.
- Parallel training designs: Centralized training aggregates local models or gradients, while decentralized training restricts communication to individual neighbors.Centralized systems include parameter-server implementations; decentralized algorithms may use fixed or changing network topologies.
- Other distributed-learning directions: Distributed learning research also studies privacy, adaptive optimization, nonsmooth objectives, proximal methods, and projection-free online learning.
- Compressed communication: Gradient compression reduces communication through quantization, sparsification, adaptive schemes, and compressed models, with QSGD analyzing the local-update–communication tradeoff.Many approaches use unbiased quantization to support convergence analysis.
- Compressed communication: 1Bit-SGD uses gradient signs, while later work studies its convergence and unbiased variants.The unbiased variant is reported to ensure convergence to a single minimum.
- Related extensions: Communication-efficient distributed learning also includes mean estimation, lazily aggregated gradients, atomic sparsification, and extensions to privacy, manifolds, and compressed PCA.
- Error compensation: Error compensation has been applied to compressed gradients and empirically limits accuracy loss, but prior theoretical work did not fully establish its advantage in all settings.Existing studies include AllReduce 1Bit-SGD, quadratic optimization, and worker-side gradient compression.
3. Parallel Error-Compensated Algorithms
DOUBLESQUEEZE applies error compensation on both workers and the parameter server in a two-pass compressed communication procedure. The framework supports biased or unbiased compression options while keeping exchanged information compressed.
- Algorithm overview: DOUBLESQUEEZE is a parallel error-compensated SGD algorithm designed for parameter-server training.The algorithm is introduced for a server and n workers, although the paper states it is not limited to that architecture.
- Server and worker updates: The parameter server averages received gradients, adds the global error, compresses the aggregate, updates that error, and sends the compressed result to workers.Workers then update their local models using the server’s compressed aggregate and learning rate γ.
- Worker operations: Workers compute local stochastic gradients from the global model and local samples, add local error compensation, and compress the resulting gradients before transmission.Worker indices identify nodes, and t identifies the iteration.
- Communication cost: All worker–server communication is compressed, potentially reducing required bandwidth to much lower than 10%, compared with prior schemes that save up to 50%.The comparison concerns methods that compress worker-to-server gradients but send a dense vector back from the server.
- Compression options: The method does not require an unbiased compressor, allowing randomized quantization, 1-Bit quantization, clipping, and top-k or randomized sparsification.The listed operators include both unbiased and biased compression techniques.
- Global formulation: The global model update uses the compressed aggregate together with stochastic-gradient and error terms in the DOUBLESQUEEZE update formulation.
4. Convergence Analysis
The convergence analysis establishes rates for DOUBLESQUEEZE under smoothness, bounded-variance, and bounded-compression-error assumptions. The reported results match parallel SGD asymptotically, provide linear speedup, and improve tolerance to compression variance or bias.
- Assumptions: The analysis assumes Lipschitz gradients, bounded stochastic-gradient variance, and bounded local and global compression errors.The compression-error bound is represented by a constant ϵ; the first two assumptions are standard for non-convex convergence analysis.
- Assumptions: α ∈[0, 1) is sufficient to keep the error vector δ_t bounded under the stated compression condition.The passage derives this from the bound involving any positive ρ.
- Main convergence results: Theorem 1 gives a convergence rate for DOUBLESQUEE under Assumption 1, followed by a learning-rate specialization in Corollary 2.The supplied passages introduce the theorem and corollary but do not include their full displayed formulas.
- Main convergence results: DOUBLESQUEE has asymptotical convergence rate O(1/(nT)), the same rate as Parallel SGD, implying averaged sample complexity O(1/(nϵ2)).The paper identifies this as the first analysis showing linear speedup for error-compensated algorithms.
- Comparison with compressed SGD: For non-error-compensated SGD, convergence is not generally guaranteed unless the compression operator is unbiased.The comparison discusses unbiased compressed SGD, including QSGD and sparse SGD.
- Compression tolerance: When compression variance ϵ dominates, DOUBLESQUEEZE has better dependence on ϵ in iteration number T and therefore better tolerance to compression variance or bias.The paper attributes this to delaying updates to portions of stochastic-gradient information rather than dropping them.
5. Experiments
Experiments compare DoubleSqueeze with compressed and uncompressed SGD implementations using 1-bit and top-k compression on CIFAR-10. DoubleSqueeze preserves convergence while reducing iteration time under limited bandwidth.
- Experiment setting: On CIFAR-10, the study trains ResNet-18 with approximately 44MB of model parameters using one parameter server and eight workers.Each worker uses batch size 256 and computes gradients on an Nvidia 1080Ti.
- Experiment setting: The experiments evaluate five SGD implementations, including DoubleSqueeze with worker- and server-side compression and compensation.The study uses 1-bit and top-k compression approaches.
- 1-bit compression: With 1-bit compression, DoubleSqueeze and MEM-SGD converge similarly to Vanilla SGD across epochs, whereas QSGD converges much slower.Testing accuracy shows similar results.
- 1-bit compression: Under limited network bandwidth, DoubleSqueeze is much faster than Vanilla SGD and the other evaluated algorithms.This result is reported for the 1-bit compression experiment.
- Top-k compression: With top-k compression at k = 300000, all methods converge similarly across epochs, although Top-k SGD is slightly slower.Training loss and testing accuracy are reported in Figures 4 and 5.
- Top-k compression: Under limited bandwidth, DoubleSqueeze is much faster than the other top-k compression algorithms.Per-iteration time costs are reported in Figure 6 across network environments.
6. Conclusion
The paper concludes that DoubleSqueeze compresses communication on both workers and the parameter server, enabling substantial bandwidth savings. Its theory establishes linear speedup and improved tolerance to compression bias and noise, while experiments validate the approach.
- Conclusion: DoubleSqueeze applies error-compensated compression on both workers and the parameter server, so all exchanged information is compressed.This differs from methods that leave the server-to-worker gradient dense.
- Conclusion: With top-k compression at k = 300000, testing accuracy is compared across DoubleSqueeze, Top-k SGD, Vanilla SGD, and MEM-SGD.Figure 5 reports testing accuracy with respect to epochs on CIFAR-10.
- Conclusion: Under different network environments, Figure 6 compares per-iteration time for DoubleSqueeze, Top-k SGD, MEM-SGD, and Vanilla SGD.The x-axis is inverse parameter-server bandwidth and the y-axis is seconds per iteration.
- Conclusion: The theoretical convergence result implies linear speedup with the number of workers and better tolerance to compression bias and noise than non-error-compensated approaches.The empirical study is presented as validation of the algorithm.
A. Proof to Theorem 1
The proof introduces an auxiliary sequence that transforms DoubleSqueeze’s update into a stochastic-gradient form. Smoothness and the theorem’s bounds are then combined to establish the convergence result.
- Proof: The proof begins from the established updating rule of DoubleSqueeze.This update is used as the starting point for the convergence derivation.
- Proof: An auxiliary sequence {y_t} is introduced to simplify the update analysis.Its update is derived algebraically from the original sequence.
- Proof: The auxiliary update becomes y_t − γ∇f(x_t) + γξ_t, separating the gradient term from the stochastic term.The displayed derivation cancels the intermediate compression-error terms.
- Proof: The argument concludes by completing the proof after combining the derived inequalities.The supplied proof passage states that the proof is complete.
A.1. Proof to Corollary 2
The corollary proof combines prior inequalities and treats f(x_0) − f* and L as constants to obtain the stated bound.
- Proof to Corollary 2: The proof invokes Theorem 1 as an ingredient for the corollary.This result is combined with another previously derived inequality.
- Proof to Corollary 2: The proof combines equations (9) and (10) to derive the corollary’s bound.The supplied text explicitly identifies this combination as the key step.
- Proof to Corollary 2: After treating f(x_0) − f* and L as constants, the resulting inequality gives the corollary statement.The supplied passage presents this simplification directly.
- Proof to Corollary 2: The proof concludes after obtaining the final inequality.The closing passage states that the proof is complete.