QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

Dan AlistarhDemjan GrubicJungshian LiRyota TomiokaMilan Vojnovic

article2016NeurIPS1,789 citations

Proposes Quantized SGD (QSGD), a communication-efficient gradient compression scheme with provable convergence guarantees that significantly accelerates distributed deep learning without sacrificing model accuracy.

Listen

Training modern machine learning models across multiple processors is essential for handling massive datasets and large neural network architectures. However, distributed training faces a major physical bottleneck: the high network bandwidth required to constantly transmit multi-million-dimensional gradient updates between nodes. As parallel hardware scales, communication delays increasingly dominate total training time. While heuristic compression methods exist to shrink gradient sizes, they frequently lack mathematical convergence guarantees and can cause optimization to diverge.

The article introduces Quantized Stochastic Gradient Descent (QSGD), a principled family of compression and encoding schemes designed to evaluate whether data transmission during parallel training can be drastically reduced without compromising mathematical convergence guarantees or baseline model accuracy.

To demonstrate this, the authors designed a framework combining unbiased randomized rounding with specialized integer encoding. They analytically proved its convergence rates across smooth convex, non-convex, and asynchronous optimization settings, including variance-reduced techniques. The authors then empirically validated the system using Microsoft Cognitive Toolkit on multi-GPU Amazon EC2 instances, testing various deep learning architectures across standard vision and speech recognition benchmarks.

The evaluation revealed several key findings. First, QSGD achieves significant bandwidth savings, enabling gradient transfers in roughly 2.8 bits per dimension (a 5.7-fold reduction compared to standard 32-bit floating-point values) with only a minimal two-fold increase in variance. Second, these communication savings translate into substantial end-to-end acceleration: multi-GPU training time decreased by 2.5 times for AlexNet on 16 GPUs, 2.7 times for speech recognition models on two GPUs, and approximately 1.8 to 2 times for computationally heavy vision models such as ResNet-152. Third, using 4-bit or 8-bit quantization reliably matches or slightly exceeds the final top-1 predictive accuracy of full-precision 32-bit baselines, acting as beneficial regularization noise during training. Fourth, communication savings scale favorably as processor counts increase, where standard 32-bit setups spend over 70 to 80 percent of training time merely waiting on network exchanges.

These findings imply that distributed machine learning workflows can achieve substantially higher computational throughput and lower cloud infrastructure costs without requiring architecture-specific hyperparameter retuning. Unlike existing sign-based heuristics, QSGD guarantees provable convergence without the memory overhead of local error-accumulation buffers.

Organizations training large-scale deep models should consider adopting 4-bit or 8-bit QSGD with gradient bucketing for distributed multi-GPU workloads to improve cluster utilization. Future implementations should explore native message-passing support for sparse data structures and evaluate the algorithm's scaling limits in high-performance supercomputing environments.

Decision-makers should note that the primary operational limitation lies in tuning quantization aggressiveness against network architecture sensitivity. Highly convolutional vision networks show performance degradation under aggressive 2-bit compression, requiring moderate 4-bit or 8-bit settings, whereas recurrent speech networks tolerate lower precision well. Overall confidence in the system's efficacy is high, as the analytical convergence bounds are directly supported by rigorous multi-GPU empirical benchmarks.

ETH Zurich Google Institute of Science and Technology Austria London School of Economics Massachusetts Institute of Technology Microsoft classification communication overheads compression methods communication-efficient SGD gradient quantization data-parallel SGD

arXiv: 1610.02132

Paper: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson et al. (2013). Learn how variance reduction stabilizes stochastic optimization, providing foundational convergence mechanics that motivate gradient compression schemes in stochastic gradient descent.
Paper: Deep Compression: Compressing Deep Neural Network with Pruning, Trained Quantization and Huffman Coding, Song Han et al. (2015). Understand the foundational techniques of neural network weight quantization and Huffman coding that directly inspire gradient quantization and encoding methods.
Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). Gain essential theoretical background on the convergence behavior and computational complexity trade-offs of stochastic gradient descent at large scale.
Paper: Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation, Yoshua Bengio et al. (2013). Explore stochastic gradient estimation through discrete operations, which underpins the design of unbiased stochastic rounding and quantization operators.
Paper: DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients, Shuchang Zhou et al. (2016). Examine how stochastic low-bitwidth gradient approximations are applied during neural network backpropagation to enable efficient training.

Paper: Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training, Yujun Lin et al. (2018). See how extreme gradient compression scales beyond quantization by combining aggressive sparsification with momentum correction and local gradient accumulation.
Paper: Federated Learning: Strategies for Improving Communication Efficiency, Jakub Konečný et al. (2016). Extend quantized communication concepts into federated learning frameworks using structured updates and sketched probabilistic quantization.
Paper: PyTorch Distributed: Experiences on Accelerating Data Parallel Training, Shen Li et al. (2020). Discover how production-grade data-parallel distributed training systems integrate communication overlapping and gradient bucketing.
Paper: Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour, Priya Goyal et al. (2017). Examine the scaling limits of distributed synchronous SGD and complementary learning rate schedules across hundreds of GPUs.
Paper: Deep Leakage from Gradients, Ligeng Zhu et al. (2019). Explore the privacy vulnerabilities inherent in exchanging gradients across distributed nodes and how gradient transmission can expose private data.

Cover for QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

Abstract

Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to excellent scalability properties of this algorithm, and to its efficiency in the context of training deep neural networks. A fundamental barrier for parallelizing large-scale SGD is the fact that the cost of communicating the gradient updates between nodes can be very large. Consequently, lossy compression heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always provably converge, and it is not clear whether they are optimal.

In this paper, we propose Quantized SGD (QSGD), a family of compression schemes which allow the compression of gradient updates at each node, while guaranteeing convergence under standard assumptions. QSGD allows the user to trade off compression and convergence time: it can communicate a sublinear number of bits per iteration in the model dimension, and can achieve asymptotically optimal communication cost. We complement our theoretical results with empirical data, showing that QSGD can significantly reduce communication cost, while being competitive with standard uncompressed techniques on a variety of real tasks.

In particular, experiments show that gradient quantization applied to training of deep neural networks for image classification and automated speech recognition can lead to significant reductions in communication cost, and end-to-end training time. For instance, on 16 GPUs, we are able to train a ResNet-152 network on ImageNet 1.8x faster to full accuracy. Of note, we show that there exist generic parameter settings under which all known network architectures preserve or slightly improve their full accuracy when using quantization.

Topics

classification communication overheads compression methods gpus image classification lossy compressions neural networks parallel implementations parallelizing stochastic

Keywords

communication-efficient SGD gradient quantization data-parallel SGD stochastic gradient descent stochastic quantization SVRG variance reduction parallel SVRG communication complexity convex optimization

1 Introduction
2 Preliminaries
3 Quantized Stochastic Gradient Descent (QSGD)
3.1 Generalized Stochastic Quantization and Coding
3.2 QSGD Guarantees
3.3 Quantized Variance-Reduced SGD
4 QSGD Variants
5 Experiments
6 Conclusions and Future Work
7 Acknowledgments
References
A Proof of Lemmas and Theorems
A.1 Proof of Lemma
A.2 A Compression Scheme for QsQ_{s} Matching Theorem
A.3 A Compression Scheme for QsQ_{s} Matching Theorem
B Quantized SVRG
C Quantization for Non-convex SGD
D Asynchronous QSGD
E Experiments
F Quantized Gradient Descent: Description and Analysis
G Quantized SVRG

Knowls

Knowl 1 — Generalized Stochastic Quantization Operator
definition
For any non-zero vector $v \in \mathbb{R}^n$ and an integer parameter $s \ge 1$ denoting the number of quantization levels, the stochastic quantization operator $Q_s(v)$ is defined coordinate-wise by:

$Q_s(v_i) = \|v\|_2 \cdot \operatorname{sgn}(v_i) \cdot \xi_i(v, s)$

where $\operatorname{sgn}(v_i) \in \{-1, +1\}$ denotes the sign of $v_i$ (with $\operatorname{sgn}(0) = 1$ ), and the random variables $\xi_i(v, s)$ are independent. For an integer $\ell$ satisfying $0 \le \ell < s$ such that $\frac{|v_i|}{\|v\|_2} \in \left[\frac{\ell}{s}, \frac{\ell+1}{s}\right]$ , $\xi_i(v, s)$ is distributed as:

$\xi_i(v, s) = \begin{cases} \frac{\ell}{s} & \text{with probability } 1 - p\left(\frac{|v_i|}{\|v\|_2}, s\right) \\ \frac{\ell+1}{s} & \text{with probability } p\left(\frac{|v_i|}{\|v\|_2}, s\right) \end{cases}$

where $p(a, s) = as - \ell$ for any $a \in [0, 1]$ . For $v = 0$ , the operator is defined as $Q_s(0) = 0$ .

For any vector $v \in \mathbb{R}^n$ , the stochastic quantization function satisfies three fundamental properties:
1. Unbiasedness: $\mathbb{E}[Q_s(v)] = v$ .
2. Variance Bound: $\mathbb{E}\left[\|Q_s(v) - v\|_2^2\right] \le \min\left(\frac{n}{s^2}, \frac{\sqrt{n}}{s}\right)\|v\|_2^2$ .
3. Expected Sparsity: $\mathbb{E}\left[\|Q_s(v)\|_0\right] \le s(s + \sqrt{n})$ , where $\|\cdot\|_0$ denotes the number of non-zero coordinates.
Knowl 2 — Lossless Elias Encoding Bounds for Quantized Gradients
theoretical result
A quantized gradient $Q_s(v) \in \mathbb{R}^n$ is uniquely represented by the tuple $(\|v\|_2, \sigma, \zeta)$ , where the $\ell_2$ -norm $\|v\|_2$ is stored as a single-precision float using $F = 32$ bits, $\sigma \in \{-1, +1\}^n$ is the coordinate sign vector, and $\zeta \in \{0, 1, \dots, s\}^n$ contains the quantized integer levels $\zeta_i = s \cdot \xi_i(v, s)$ . Coordinates and distance offsets between non-zero coordinates are encoded using recursive Elias omega integer coding, which encodes any positive integer $k$ in $|\operatorname{Elias}(k)| \le (1 + o(1))\log_2 k + 1$ bits.

The expected communication lengths under this encoding scheme satisfy:
1. General Sparse Regime ( $s \ge 2$ ): By encoding distances between non-zero coordinates, the expected number of transmitted bits for $Q_s(v)$ is at most:
$\left(3 + \left(\frac{3}{2} + o(1)\right)\log_2\left(\frac{2(s^2+n)}{s(s+\sqrt{n})}\right)\right)s(s+\sqrt{n}) + 32$
1. Extreme Sparse Regime ( $s = 1$ ): When quantizing coordinates to $\{-1, 0, 1\}$ , the expected bit length is at most $O(\sqrt{n}\log n)$ bits per vector, with a variance blowup factor of at most $\sqrt{n}$ .
2. Dense Regime ( $s = \sqrt{n}$ ): When encoding each coordinate sequentially with offset Elias coding $\operatorname{Elias}'(k) = \operatorname{Elias}(k+1)$ , the expected number of bits communicated per update is bounded by:
$\mathbb{E}\left[|\operatorname{Code}'_{\sqrt{n}}(Q_{\sqrt{n}}(v))|\right] \le 2.8n + 32$

In this regime, the multiplicative variance blowup factor $\min(n/s^2, \sqrt{n}/s)$ is at most $1$ , so $\mathbb{E}[\|Q_{\sqrt{n}}(v)\|_2^2] \le 2\|v\|_2^2$ .
Knowl 3 — Synchronous Parallel Quantized Stochastic Gradient Descent
algorithm
Synchronous parallel Quantized Stochastic Gradient Descent (QSGD) performs distributed data-parallel optimization across $K$ parallel worker processors. Each processor computes a local stochastic gradient on its local data partition, compresses the gradient vector via stochastic quantization and lossless Elias coding, exchanges compressed messages with all other workers, decodes the updates, and applies the averaged gradient step to its local copy of the parameter vector.
Input: Initial parameter vector $x_0 \in \mathbb{R}^n$ , total iterations $T$ , step sizes $(\eta_t)_{t=0}^{T-1}$ , number of quantization levels $s \ge 1$ , $K$ worker processors.
Output: Final parameter vector $x_T$ or iterate average $\frac{1}{T}\sum_{t=0}^{T-1} x_t$ .
for iteration $t = 0, 1, \dots, T-1$ do
    for each processor $i \in \{1, \dots, K\}$ in parallel do
        Compute local stochastic gradient $\tilde{g}_i(x_t)$ satisfying $\mathbb{E}[\tilde{g}_i(x_t)] = \nabla f(x_t)$
        Quantize and encode: $M_i \leftarrow \operatorname{Encode}(Q_s(\tilde{g}_i(x_t)))$
        Broadcast message $M_i$ to all peer processors
        for each peer processor $\ell \in \{1, \dots, K\}$ do
            Receive message $M_\ell$ from processor $\ell$
            Decode update: $\hat{g}_\ell \leftarrow \operatorname{Decode}(M_\ell)$
        Compute aggregate gradient: $\bar{g} \leftarrow \frac{1}{K} \sum_{\ell=1}^K \hat{g}_\ell$
        Update parameter: $x_{t+1} \leftarrow x_t - \eta_t \bar{g}$
Knowl 4 — Convergence Rate of QSGD for Smooth Convex Functions
theoretical result
Let $\mathcal{X} \subseteq \mathbb{R}^n$ be a convex set, and let $f: \mathcal{X} \to \mathbb{R}$ be a convex, $L$ -smooth objective function. Suppose $K$ parallel processors have access to independent stochastic gradients with second moment bounded by $\mathbb{E}[\|\tilde{g}(x)\|_2^2] \le B$ for all $x \in \mathcal{X}$ . Let $x_0 \in \mathcal{X}$ be the initial iterate and $R = \sup_{x \in \mathcal{X}} \|x - x_0\|_2$ .

When parallel QSGD is executed with $s$ quantization levels, step size $\eta_t = 1 / (L + \sqrt{K}/\gamma)$ with $\gamma = \frac{R}{B'} \sqrt{\frac{2}{T}}$ and effective second moment $B' = \min\left(\frac{n}{s^2}, \frac{\sqrt{n}}{s}\right)B$ , achieving an expected suboptimality gap:

$\mathbb{E}\left[ f\left( \frac{1}{T} \sum_{t=0}^T x_t \right) \right] - \min_{x \in \mathcal{X}} f(x) \le \epsilon$

requires a total iteration count of:

$T = O\left( R^2 \cdot \max\left( \frac{2 B'}{K \epsilon^2}, \frac{L}{\epsilon} \right) \right)$

In the dense regime with $s = \sqrt{n}$ , communication is at most $2.8n + 32$ bits per processor per iteration, and the variance bound satisfies $B' \le B$ , requiring at most $2\times$ the number of iterations of full-precision parallel SGD.
Knowl 5 — Convergence Rate of QSGD for Smooth Non-Convex Functions
theoretical result
Let $f: \mathbb{R}^n \to \mathbb{R}$ be an $L$ -smooth (possibly non-convex) function with global infimum $f^* = \inf_{x} f(x)$ , and let $x_1 \in \mathbb{R}^n$ be an initial candidate. Assume access to unbiased stochastic gradients $\tilde{g}(x)$ with second moment bounded by $\mathbb{E}[\|\tilde{g}(x)\|_2^2] \le B$ .

For any quantization level $s > 0$ and target iteration budget $N$ , QSGD with constant step size $\eta = O(1/L)$ guarantees the existence of a random stopping time $R$ uniformly supported on $\{1, \dots, N\}$ such that the expected squared gradient norm satisfies:

$\frac{1}{L} \mathbb{E}\left[ \|\nabla f(x_R)\|_2^2 \right] \le O\left( \frac{\sqrt{L(f(x_1) - f^*)}}{N} + \frac{\min(n/s^2, \sqrt{n}/s)B}{L} \right)$

The per-iteration communication cost is bounded by the same lossless Elias encoding bounds as in the convex case (at most $2.8n + 32$ bits per worker per step when $s = \sqrt{n}$ ).
Knowl 6 — Quantized Stochastic Variance-Reduced Gradient Method and Convergence
model/method
Quantized SVRG (QSVRG) extends stochastic variance-reduced gradient descent to communication-constrained distributed environments by quantizing both the snapshot full gradient and the individual stochastic updates using $Q(v, \sqrt{n})$ . Let $f(x) = \frac{1}{m} \sum_{i=1}^m f_i(x)$ be $\ell$ -strongly convex on $\mathbb{R}^n$ , where each component function $f_i$ is convex and $L$ -smooth. The data is partitioned across $K$ processors, where processor $i$ knows $h_i(x) = \frac{1}{m}\sum_{j=im/K}^{(i+1)m/K - 1} f_j(x)$ .

At the beginning of epoch $p$ , each processor broadcasts its snapshot gradient $H_{p,i} = Q(\nabla h_i(y^{(p)}), \sqrt{n})$ so that workers assemble $H_p = \sum_{i=1}^K H_{p,i}$ . In each iteration $t = 1, \dots, T$ of epoch $p$ , processor $i$ draws an independent random sample $j_{i,t}^{(p)} \in \{1, \dots, m\}$ and broadcasts:

$u_{t,i}^{(p)} = Q\left( \nabla f_{j_{i,t}^{(p)}}(x_t^{(p)}) - \nabla f_{j_{i,t}^{(p)}}(y^{(p)}) + H_p, \sqrt{n} \right)$

Processors aggregate $u_t^{(p)} = \frac{1}{K} \sum_{i=1}^K u_{t,i}^{(p)}$ , update $x_{t+1}^{(p)} = x_t^{(p)} - \eta u_t^{(p)}$ , and set the epoch checkpoint $y^{(p+1)} = \frac{1}{T} \sum_{t=1}^T x_t^{(p)}$ .

With step size $\eta = O(1/L)$ and epoch length $T = O(L/\ell)$ , QSVRG achieves linear convergence:

$\mathbb{E}\left[ f(y^{(p+1)}) \right] - f(x^*) \le 0.9^p \left( f(y^{(1)}) - f(x^*) \right)$

where $x^*$ is the unique minimizer of $f$ . Over $P$ epochs and $T$ iterations per epoch, each processor transmits at most $P(F + 2.8n)(T + 1)$ bits, where $F = 32$ is the bit width of the norm scaling factor.
Knowl 7 — Ergodic Convergence of QSGD in Asynchronous Parameter-Server Settings
theoretical result
Consider an asynchronous parameter-server architecture where worker nodes independently compute stochastic gradients, quantize them using $Q_s$ , and transmit updates to a central parameter server. Gradients are applied with a bounded staleness delay of at most $T$ iterations relative to the current master parameter vector.

Let $f: \mathbb{R}^n \to \mathbb{R}$ be $L$ -smooth with infimum $f^* = \inf_x f(x)$ . Let stochastic gradients have variance bounded by $\sigma^2$ , and define the effective quantized variance as $\sigma_s^2 = \left(1 + \min\left(\frac{n}{s^2}, \frac{\sqrt{n}}{s}\right)\right)\sigma^2$ . For $K$ total iterations and minibatch size $M$ , if the step size sequence $\{\gamma_k\}_{k=1}^K$ satisfies:

$LM \gamma_k + 2L^2 M^2 T \gamma_k \sum_{\kappa=1}^T \gamma_{k+\kappa} \le 1, \quad \forall k \ge 1$

then defining $\Gamma = \sum_{k=1}^K \gamma_k$ , the iterates generated by asynchronous QSGD satisfy:

$\frac{\sum_{k=1}^K \gamma_k \mathbb{E}[\|\nabla f(x_k)\|_2]}{\Gamma} \le \frac{2(f(x_1) - f^*) + \sum_{k=1}^K \left(\gamma_k^2 M L + 2 L^2 M^2 \gamma_k \sum_{j=k-T}^{k-1} \gamma_j^2 \right) \sigma_s^2}{M \Gamma}$
Knowl 8 — Variance Reduction via Gradient Bucketing and Max-Norm Scaling
model/method
In practical implementations of QSGD, two modifications to basic stochastic quantization control variance and maintain accuracy:
1. Gradient Bucketing: A gradient vector $v \in \mathbb{R}^n$ is divided into contiguous sub-vectors (buckets) of fixed dimension $d \le n$ , where the $i$ -th bucket is $v[(i-1)d + 1 : i \cdot d]$ . Quantization $Q_s$ is applied independently to each bucket, attaching an individual float scaling factor per bucket. This makes the variance blowup depend on the bucket dimension $d$ rather than the full parameter dimension $n$ :
$\mathbb{E}\left[ \|Q_s(v_{\text{bucket}}) - v_{\text{bucket}}\|_2^2 \right] \le \min\left(\frac{d}{s^2}, \frac{\sqrt{d}}{s}\right) \|v_{\text{bucket}}\|_2^2$

For example, using bucket size $d = 512$ with 4-bit quantization ( $s = 16$ ), the variance blowup factor is bounded by $\frac{\sqrt{512}}{16} \approx 1.41$ .
1. Max-Norm Scaling: Rather than scaling by the $\ell_2$ -norm $\|v\|_2$ , each bucket is normalized by its maximum coordinate magnitude $\|v\|_\infty = \max_i |v_i|$ . This preserves higher dynamic range and improves empirical convergence accuracy at the expense of coordinate sparsity.
Knowl 9 — Linear Convergence of Deterministic Quantized Gradient Descent
theoretical result
For standard (non-stochastic) gradient descent with communication constraints between computation and parameter storage nodes, a deterministic quantization operator $Q(v)$ is defined by selecting the smallest index set $I(v)$ of largest components such that $\sum_{i \in I(v)} |v_i| \ge \|v\|_2$ , setting $Q(v)_i = \|v\|_2 \operatorname{sgn}(v_i)$ for $i \in I(v)$ and $Q(v)_i = 0$ otherwise.

The deterministic quantization function satisfies:
1. $v^T Q(v) \ge \|v\|_2^2$ ,
2. Sparsity bound: $|I(v)| \le \sqrt{n}$ ,
3. Norm bound: $\|Q(v)\|_2^2 \le \sqrt{n} \|v\|_2^2$ ,
4. Bit length: $|\operatorname{Code}(Q(v))| \le \sqrt{n}(\log_2 n + 1 + \log_2 e) + F$ bits, where $F$ is the float bit width.
For an $\ell$ -strongly convex, $L$ -smooth function $f: \mathbb{R}^n \to \mathbb{R}$ with condition number $\kappa = L/\ell$ and unique minimizer $x^*$ , running quantized gradient descent $x_{t+1} = x_t - \eta Q(\nabla f(x_t))$ with step size $\eta \le O\left(\frac{\ell}{L^2 \sqrt{n}}\right)$ achieves linear convergence:

$f(x_T) - f(x^*) \le \exp\left( -\Omega\left( \frac{1}{\kappa^2 \sqrt{n}} \right) T \right) (f(x_0) - f(x^*))$

Knowl 10 — Multi-GPU End-to-End Training Accuracy and Speedup with QSGD

data/table

Distributed neural network training with QSGD was evaluated in Microsoft CNTK on Amazon EC2 p2.16xlarge instances (up to 16 NVIDIA K80 GPUs). Quantization was applied to all parameter matrices with $>10\text{K}$ elements (covering $>99\%$ of model parameters) while preserving standard full-precision hyperparameters.

Network	Dataset	Params	Init. Rate	Top-1 (32bit)	Top-1 (QSGD)	Speedup (8 GPUs)
AlexNet	ImageNet	62M	0.07	59.50%	60.05% (4bit)	2.05 $\times$
ResNet152	ImageNet	60M	1.0	77.00%	76.74% (8bit)	1.56 $\times$
ResNet50	ImageNet	25M	1.0	74.68%	74.76% (4bit)	1.26 $\times$
ResNet110	CIFAR-10	1M	0.1	93.86%	94.19% (4bit)	1.10 $\times$
BN-Inception	ImageNet	11M	3.6	–	–	1.16 $\times$ (projected)
VGG19	ImageNet	143M	0.1	–	–	2.25 $\times$ (projected)
LSTM	AN4	13M	0.5	81.13%	81.15% (4bit)	2.00 $\times$ (2 GPUs)

On communication-intensive models (AlexNet, VGG19, LSTM), 4-bit and 8-bit QSGD match or slightly improve upon full-precision top-1 test accuracy while delivering significant end-to-end acceleration. On 16 GPUs, 4-bit QSGD reduces AlexNet communication time by $4\times$ and epoch time by $2.5\times$ . On 2 GPUs for LSTM on AN4, communication time drops by $6.8\times$ and epoch time by $2.7\times$ . Computation-heavy architectures (ResNet-152) also experience end-to-end training speedups ( $1.56\times$ on 8 GPUs, $\approx 2\times$ on 16 GPUs) without loss of classification accuracy.

Coverage note — Proofs, intermediate algebraic bounds (such as Jensen's inequality bounds on Elias code length), and general lower-bound literature connections for distributed mean estimation were deliberately omitted in accordance with the extraction rules.

References

1.Martın Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467, 2016.
2.Alex Acero. Acoustical and environmental robustness in automatic speech recognition, volume 201. Springer Science & Business Media, 2012.
3.Amit Agarwal, Eldar Akchurin, Chris Basoglu, Guoguo Chen, Scott Cyphers, Jasha Droppo, Adam Eversole, Brian Guenter, Mark Hillebrand, Ryan Hoens, et al. An introduction to computational networks and the computational network toolkit. Technical report, Tech. Rep. MSR-TR-2014-112, August 2014., 2014.
4.Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-efficient SGD via gradient quantization and encoding. arXiv preprint arXiv:1610.02132, 2016.
5.Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In NIPS, 2015.
6.Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
7.Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
8.Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In OSDI, October 2014.
9.Cntk brainscript file for alexnet. https://github.com/Microsoft/CNTK/tree/master/Examples/Image/Classification/AlexNet/BrainScript. Accessed: 2017-02-24.
10.Christopher M De Sa, Ce Zhang, Kunle Olukotun, and Christopher Ré. Taming the wild: A unified analysis of hogwild-style algorithms. In NIPS, 2015.
11.Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, et al. Large scale distributed deep networks. In NIPS, 2012.
12.Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pages 248–255. IEEE, 2009.
13.John C Duchi, Sorathan Chaturapruek, and Christopher Ré. Asynchronous stochastic convex optimization. NIPS, 2015.
14.Peter Elias. Universal codeword sets and representations of the integers. IEEE transactions on information theory, 21(2):194–203, 1975.
15.Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013.
16.Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In ICML, pages 1737–1746, 2015.
17.Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 2015.
18.Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016.
19.Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735–1780, 1997.
20.Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In Advances in Neural Information Processing Systems, pages 4107–4115, 2016.
21.Forrest N Iandola, Matthew W Moskewicz, Khalid Ashraf, and Kurt Keutzer. Firecaffe: near-linear acceleration of deep neural network training on compute clusters. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2592–2600, 2016.
22.Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015.
23.Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, 2013.
24.Jakub Konečn`y. Stochastic, distributed and federated optimization for machine learning. arXiv preprint arXiv:1707.01155, 2017.
25.Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images, 2009.
26.Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097–1105, 2012.
27.Yann LeCun, Corinna Cortes, and Christopher JC Burges. The mnist database of handwritten digits, 1998.
28.Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In OSDI, 2014.
29.Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In NIPS. 2015.
30.Arvind Neelakantan, Luke Vilnis, Quoc V Le, Ilya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. arXiv preprint arXiv:1511.06807, 2015.
31.Cntk implementation of qsgd. https://gitlab.com/demjangrubic/QSGD. Accessed: 2017-11-4.
32.Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In NIPS, 2011.
33.Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400–407, 1951.
34.Richard Schreier and Gabor C Temes. Understanding delta-sigma data converters, volume 74. IEEE Press, Piscataway, NJ, 2005.
35.Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In INTERSPEECH, 2014.
36.Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
37.Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In INTERSPEECH, 2015.
38.Ananda Theertha Suresh, Felix X Yu, H Brendan McMahan, and Sanjiv Kumar. Distributed mean estimation with limited communication. arXiv preprint arXiv:1611.00429, 2016.
39.Seiya Tokui, Kenta Oono, Shohei Hido, CA San Mateo, and Justin Clayton. Chainer: a next-generation open source framework for deep learning. In Proceedings of workshop on machine learning systems (LearningSys), 2015.
40.John N Tsitsiklis and Zhi-Quan Luo. Communication complexity of convex optimization. Journal of Complexity, 3(3), 1987.
41.Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. arXiv preprint arXiv:1705.07878, 2017.
42.Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning. In International Conference on Machine Learning, pages 4035–4043, 2017.
43.Sixin Zhang, Anna E Choromanska, and Yann LeCun. Deep learning with elastic averaging sgd. In Advances in Neural Information Processing Systems, pages 685–693, 2015.
44.Yuchen Zhang, John Duchi, Michael I Jordan, and Martin J Wainwright. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. In NIPS, 2013.
45.Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. arXiv preprint arXiv:1606.06160, 2016.

Citation

MLA

Alistarh, D., et al. “QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding”. arXiv, 2016, http://arxiv.org/abs/1610.02132v4.

APA

Alistarh, D., Grubic, D., Li, J., Tomioka, R., & Vojnovic, M. (2016). QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding. arXiv. http://arxiv.org/abs/1610.02132v4

Chicago

Alistarh, D., D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. 2016. “QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding”. arXiv. http://arxiv.org/abs/1610.02132v4.

Harvard

Alistarh, D. et al. (2016) “QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1610.02132v4.

Vancouver

1. Alistarh D, Grubic D, Li J, Tomioka R, Vojnovic M (2016) QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding. arXiv

BibTeX

@article{alistarh2016qsgd,
  title = {QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding},
  author = {Alistarh, Dan and Grubic, Demjan and Li, Jerry and Tomioka, Ryota and Vojnovic, Milan},
  year = {2016},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1610.02132v4},
  eprint = {1610.02132}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Generalized Stochastic Quantization Operator

Knowl 2 — Lossless Elias Encoding Bounds for Quantized Gradients

Knowl 3 — Synchronous Parallel Quantized Stochastic Gradient Descent

Knowl 4 — Convergence Rate of QSGD for Smooth Convex Functions

Knowl 5 — Convergence Rate of QSGD for Smooth Non-Convex Functions

Knowl 6 — Quantized Stochastic Variance-Reduced Gradient Method and Convergence

Knowl 7 — Ergodic Convergence of QSGD in Asynchronous Parameter-Server Settings

Knowl 8 — Variance Reduction via Gradient Bucketing and Max-Norm Scaling

Knowl 9 — Linear Convergence of Deterministic Quantized Gradient Descent

Knowl 10 — Multi-GPU End-to-End Training Accuracy and Speedup with QSGD

References

Citation

BibTeX

Access the Paper