DQSGD: DYNAMIC QUANTIZED STOCHASTIC GRADIENT DESCENT FOR COMMUNICATION-EFFICIENT DISTRIBUTED LEARNING
Authors: Guangfeng Yan
Shao-Lun Huang
Tian Lan
Linqi Song
Venue:  (2021)
Keywords: Distributed Learning
Communication
Gradient Quantization

Abstract: Gradient quantization is widely adopted to mitigate communication costs in distributed learning systems. Existing gradient quantization algorithms often rely on design heuristics and/or empirical evidence to tune the quantization strategy for different learning problems. To the best of our knowledge, there is no theoretical framework characterizing the trade-off between communication cost and model accuracy under dynamic gradient quantization strategies. This paper addresses this issue by proposing a novel dynamic quantized SGD (DQSGD) framework, which enables us to optimize the quantization strategy for each gradient descent step by exploring the trade-off between communication cost and modeling error. In particular, we derive an upper bound, tight in some cases, of the modeling error for arbitrary dynamic quantization strategy. By minimizing this upper bound, we obtain an enhanced quantization algorithm with significantly improved modeling error under given communication overhead constraints. Besides, we show that our quantization scheme achieves a strengthened communication cost and model accuracy trade-off in a wide range of optimization models. Finally, through extensive experiments on large-scale computer vision and natural language processing tasks on CIFAR-10, CIFAR-100, and AG-News datasets, respectively. we demonstrate that our quantization scheme significantly outperforms the state-of-the-art gradient quantization methods in terms of communication costs.

Under review as a conference paper at ICLR 2021
DQSGD: DYNAMIC QUANTIZED STOCHASTIC GRA- DIENT DESCENT FOR COMMUNICATION-EFFIIENN DISTRIBUTED LEARNING
Anonymous authors Paper under double-bling brind review
ABSTRACT
Gradient quantization is widely adopted to mitigate communication costs in dis- tributed learning systems. Existing gradient quantization algorithms often rely on design heuristics and/or empirical evidence to tune the quantization strategy for different learning problems. To the best of our knowledge, there is theoretical framework characterizing the trade-off between communication cost and model accuracy under dynamic gradient quantization strategies. This paper addresses this issue by proposing a novel dynamic quantized SGD (DQSGD) framework, which enables us optimize the quantization strategy for each gradient descent step by exploring the trade-off between communication cost and modeling error. In particular, we derive an upper bound, tight in some cases, of the modeling error for arbitrary dynamic quantization strategy. By minimizing this upper bound, we obtain an enhanced quantization algorithm with significantly improved modeling error under given communication overhead constraints. Besides, we show that our quantization scheme achieves strengthened communication cost and model accuracy trade-off in a wide range of optimization models. Finally, through exten- sive experiments on large-scale computer vision and natural language processing tasks on CIFAR-10, 10, CIFAR-100, and AG-News datasets, respectively. we demon- strate that our quantization scheme significantly outperforms the state-of-the-art gradient quantization methods in terms of communication costs.
INTRODUCTION
Recently, with the booming of Artificial Intelligence (AI), 5G wireless communications, and Cyber- Physical Systems (CPS), distributed learning plays increasingly important role in improving the efficiency and accuracy of learning. scaling to a large input data size, and bridging different wireless computing resources (Dean al. 2012; Bekkerman al. 2011 Chilimbi al.) 2014 Chaturapruek ett al. 2015: Zhu et al. 2020; Mills et al. 2019). Distributed Stochastic Gradient Descent (SGD) is the core in vast majority of distributed learning algorithms (c.g., various distributed deep neural networks), where distributed nodes calculate local gradients and an aggregated gradient is achieved via communication among distributed nodes and/or a parameter server.
However, due to limited bandwidth in practical networks, communication overhead for transferring gradients often becomes the performance bottleneck. Several approaches towards communication- efficient distributed learning have been proposed. including compressing gradients (Stich et al.)
2018 Alistarh et al. (017) or updating local models less frequently (MeMahan et al. 2017). Gradi- ent quantization reduces the communication overhead by using few bits to approximate the original real value, which considered to be one of the most effective approaches to reduce communication overhead (Seide al. 2014]] Alistarh et al., 2017; Bernstein et al.) 2018 Wu et al. 2018 Suresh (ct al., 2017). The lossy quantization inevitably brings in gradient noise, which will affect the con- vergence of the model. Hence, a key question is how effectively select the number of quantization bits to balance the trade-off between the communication cost and its convergence performance.
Existing algorithms often quantize parameters into fixed number of bits, which is shown to be inefficient in balancing the communication conettronnnneeeeeeneee trade-off (Seide et al. 2014) Alistarh et al.] 2017 Bernstein et al. 2018). An efficient scheme should be able dynamically adjust the number

---

Under review as a conference paper at ICLR 2021
of quantized bits according the state of current learning model in each gradient descent step to balance the communication overhead and model accuracy. Several studies try to construct adaptive quantization schemes through design heuristics and/or empirical evidence. However, they do not come up with a solid theoretical analysis (Guo et al., 2020; Cui et al. 2018 Oland & Raj 2015), which even results in contradicted conclusions. More specifically, MQGrad (Cui et al. [2018) and AdaQS (Guo et al.) (2020) suggest using few quantization bits in early epochs and gradually increase the number of bits later epochs; while the scheme proposed by Anders (Oland & Raj 2015) states that more quantization bits should be used for the gradient with larger root-mean-square
(RMS) value, choosing to use more bits in the early training stage and fewer bits in the later stage. One of this paper's key contributions is to develop theoretical framework to crystallize the design tradeoff in dynamic gradient quantization and settle this contradiction.
In this paper, we propose a novel dynamic quantized SGD (DQSGD) framework for minimizing communication overhead in distributed learning while maintaining the desired learning aceuracy. We study this dynamic quantization problem in both the strongly convex and the non-convex op- timization frameworks. In the strongly convex optimization framework, we first derive an upper bound on the difference (that we term the strongly convex convergence error) between the loss af- ter N iterations and the optimal loss to characterize the strongly convex convergence error caused by sampling, limited iteration steps, and quantization. In addition. find some particular cases and prove the tightness for this upper bound on part of the convergence error caused by quantiza- tion. In the non-convex optimization framework, we derive an upper bound on the mean square of gradient norms at every iteration step, which is termed the non-convex convergence error. Based on the above theoretical analysis, we design a dynamic quantization algorithm by minimizing the strongly convex/non-convee convergence error bound under communication cost constraints. Our dynamic quantization algorithm is able to adjust the number of quantization bits adaptively by taking into account the norm of gradients, the communication budget, and the remaining number of itera- tions. We validate our theoretical analysis through extensive experiments on large-scale Computer Vision (CV) and Natural Language Processing (NLP) tasks, including image classification tasks on CIFAR-10 10 and CIFAR- 100 and text classification tasks on AG-News. Numerical results show that proposed DQSGD significantly outperforms the baseline quantization methods.
To summarize, our key contributions are as follows:
We propose a novel framework to characterize the trade-off between communication cost and modeling error by dynamically quantizing gradients the distributed learning.
We derive an upper bound on the convergence error for strongly convex objectives and non-convex objectives. The upper bound is shown to be optimal in particular cases.
We develop dynamic quantization SGD strategy, which is shown to achieve smaller conver- gence error upper bound compared with fixed-bit quantization methods.
We validate the proposed DQSGD on variety of real world datasets and machine learning models, demonstrating that our proposed DQSGD significantly outperforms state-of-the-as gradient quanti- zation methods in terms of mitigating communication costs.
2 RELATED WORK
To solve large scale machine learning problems, distributed SGD methods have attracted a wide at- tention (Dean et al. 2012 Bekkerman al.] 201T Chilimbi al. 2014 Chaturapruek al. 2015). To mitigate the communication bottleneck in distributed SGD, gradient quantization has been inves- tigated. IBitSGD uses 1 bit to quantize each dimension of the gradients and achieves the desired goal in speech recognition applications (Seide et al.] 2014). TernGrad quantizes gradients to ternary levels (-1, 0, 1) to reduce the communication overhead (Wen et al. (2017). Furthermore, QSGD is considered in a family of compression schemes that use a fixed number of bits to quantize gradients, allowing the user to smoothly trade-off communication and convergence time (Alistarh et al.. 2017). However, these fixed-bit quantization methods may not be efficient in communication. To further reduce the communication overhead, some empirical studies began to dynamically adjust the quan- tization bits according to current model parameters in the training process, such as the gradient's mean to standard deviation ratio (Guo et al.) 2020), the training loss (Cui et al.) (018). gradient's moot-mean-squared value (Oland & Raj 2015). Though these empirical heuristics of adaptive quan-
2

---

Under review as a conference paper at ICLR 2021
tization methods show good performance in some certain tasks, their imprecise conjectures and the lack of theoretical guidelines in the conjecture framework have limited their generalization to a broad range of machine learning models/tasks.
3 PROBLEM FORMULATION
We consider to minimize the objective function F : Rdd - R with parameter x
mingER F(x) = (E-EEl((( E)
(I)
where the data point is generated from unknown distribution D, and loss function [(x; E) measures the loss of the model x at data point ç. Vanilla gradient descent (GD) will solve this problem by updating model parameters via iterations ((++1) = x(n) - 7, Fx(())) where x(x) is
the model parameter at iteration n;; 1) is the learning rate; VF(x(m) is the gradient of F(x(")). A modification the GD scheme, minibatch SGD, mini-batches of random samples with size K, Ак (Eo. { J. to calculate the stochastic gradient gxx) 1/ - Vi(x;
In distributed learning, to reduce the communication overhead, we consider to quantize the minibach stochastic gradients:
(n-1) x -,, (x((()))
where Qs., [-] is the quantization operation that works on each dimension of g(x(m)). The i-th com- ponent of the stochastic gradient vector g is quantized as
(g( = |llllp sgn(g:) ((g,,))
where ||dاا is the lp norm of gi (g. = {+1,-1 is the sign of gei is the quantization level; and ((g,, s) an unbiased stochastic function that maps scalar |9.l/1991 /lll/l/lpp one of the values in set {0, 1/s, 2/5 2/s.....66 s/s}: if / [/s,, (1 s)/s], we have
1//s,
with probability 1 p. 991
Cgg 8)
(1/8)/8, with probability p == |gll
Note that, the quantization level is roughly exponential the number of quantized bits. If use B bits to quantize 9t. we will use one bit to represent its sign and the other B 1 bits to represent C(g,, s), thus resulting in a quantization level 2 1. In total, we use Bpre dB bits for the gradient quantization at each iteration: a certain number of B Pre bits of precision to construct [| lp and dB bits to express the d components of g.
Given a total number of training iterations N and the overall communication budget C' to upload all stochastic gradients, we would like to design a gradient quantization scheme to maximize the learning performance. To measure the learning performance under gradient quantization, we follow commonly adopted
-ow--oooo-o----ceencceeee error 8(F, N, C*) (Alistarh et al. 2017):
F(x(M) C) F(x", C),
for strongly convex F,
8(F,N,C)
(5)
N-1 ( )|2 for non-convex F,
where the optimal point to minimize F. In general, this error 5(F, N, C`) is hard to determine; instead, we aim to lower and upper bound this error and design corresponding quantization schemes.
4 DYNAMIC QUANTIZED SGD
In this part, we derive upper bounds on the strongly convex/non-convex convergence error 5(F,N, C') and lower bounds the strongly convex-convergence error. By minimizing the up- per bound on this convergence error, we propose the dynamic quantized SGD strategies for strongly convex and non-convex objective functions.
3

---

Under review as a conference paper at ICLR 2021
4.1 PRELIMINARIES
We first state assumptions follows.
Assumption (Smoothness). The objective finccionnnn F(x) L-smooth, if R [[F
Fy()) & L||x yl12-
implies that Vx, y R., we have
Fly) S F VF(x)" - -x) 2122 l x112
(6)
|VF( S 2L(F(x) F(x")!
(7)
Assumption (Strongly convexity). The objective function F ((x) is p-strongly convex, 3f 0,
F(x)
2 xTxx is convex function.
From Assumption have: VX,y R.d.
Fly) F(x) F(X)+ -x) + fly x -x)
Assumption (Variance bound). The stochastic gradient oracle gives independent unbiased estimate Vl(x;E) with a bounded variance:
Bg~D[V(((x =VF(()
B BE-D||| V
(10)
From Assumption for the minibatch stochastic gradient g(x) = EM K-1 Vl(x;&)1/KK we have
Eş~D[g(x)] = (F(x)
(11)
< V (x) + o²/K.
(12)
We have the relationship gradients before and after quantization: Q=(g(x)] = g(x) + é, where
represents the quantization noise, following the probability distribution that be shown in Propo- The proof of Proposition is given in Appendix A
sition] 1
Proposition 1 (Quantization Noise magnitude). For the stochastic gradient vector if the quanti- zation level is s, then the i-th component of quantization noise follows as:
0 0<85 $
p(E:)=
1glpp
gg
5
(13)
I é, S 0.
Following Proposition we can get E,, [Q]]]] = and E., 1e. a1 d 1912 This 6-
indicates that the quantization operation is unbiased, and the variance bound of Q.[g] is directly proportional Ig|] and inversely proportional to s², which means that gradients with a larger norm should be quantized using more bits to keep EEllQ, [g] gllžl below a given noise level. Therefore, we have the following lemma to characterize the quantization noise Q=(9).
Lemma 1. For the quantized gradient vector [g), have
[[ VF(x)
(14)
E|||Q.[|11 < [VF() + K
2g2 11 |
(15)
4

---

Under review as a conference paper at ICLR 2021
We can see that the noise various of Qs [g]
contains two parts: the first part is the sampling noise
K
the second part is the quantization noise
65 9
4.2 CONVERGENCE ERROR OF STRONGLY CONVEX OBJECTIVES
Firstly, we consider a strongly convex optimization problem. Putting the QSGD algorithm (2) on smooth, strongly convex functions yield the following result with proof given in Appendix B
Theorem 1 (Convergence Error Bound of Strongly Convex Objectives), For the problem in Eq.
under Assumption | and Assumption 2 with initial parameter x using quantized gradients in Eq. 2 for iteration, we can upper and lower bound the convergence error by
Lyjo or
E[F(x(N) F(x"]] a (F( - F(x*)]
2K (1 a) -N-l-n
Ldn
N-1
N
α
12
n=0
1111 0² - 3.4)
B[F(x! - F(xx)] B [F(x(()) - F((x)]]
2K(1 (1 B)
μdh
N-1
3N-1-
1-n
12
==
where a 1- 2pm B =1 2Ln + Lum7. The convergence error consists of three parts: the error of the gradient descent method, which which tends to 0 as the number of iterations N increases and also depends on the learning rate 7) (from the expression of a, we can see that when S I/L, with the increase of 1), decrease, and the convergence rate of the model is accelerated); the sampling error, which can be reduced by increasing the batch size K or decaying the learning rate; and the convergence error due to quantization, which we want to minimize. Note that there a positive correlation between the upper bound of convergence error due to quantization and the variance of the quantization noise. The contribution of quantization noise the error is larger the late stage of training. Therefore, noise reduction helps improve the accuracy of the model. In other words, more quantization bits should be used in the later training period.
In addition, we can show that the upper and lower bound matches each other in some particular cases. As simple example, the Hessian matrix is isotropic H Al, A E Ed and B is constant. Clearly, L μ. the upper is equal to the lower bound.
consider quadratic problem: F(x) Hx + A T + B, where
B and
Theorem 2 (Convergence Error of Quadratic Functions). For a quadratic optimization problem F(x) x" "HH A + B, we consider Gaussian noise case
x (n+1) = xx(") -VVF(x(()) ()) (()) (N(0
(16)
We achieve
E[
)
--1xx(00
1
(xx(0)
N Hp (xx10) -x')
112 N
(17)
-11- ) Hip (
+ 2 n=0
where p = I HH and H is the Hessian matrix.
Detailed proof is in Appendix C
5

---

Under review as a conference paper at ICLR 2021
4.3 DQSGD FOR STRONGLY CONVEX OBJECTIVES
We will determine the dynamic quantization strategy by minimizing the upper bound of convergence error due quantization. The optimization problem is:
N-1
1 (2 1)2 ()2ll(((()))) (x)))
min B
a N-1-n
N-1 (dB, + Bpre) = C.
By solving this optimization problem, we can get
[ka Bn loga [ka (N (N-)/22 (gg0 (1( + 11
(18)
where k depends on the total communication overhead C, and is related to the convergence rate of the model. The larger the total communication cost C is, the greater i is; the faster the model's convergence rate is, the smaller is. In Appendix we prove that our scheme outperforms the fixed bits scheme in terms of the convergence error.
4.4 DQSGD FOR NON-CONVEX OBJECTIVES
In general, if consider non-convex smooth objective functions, can get the following theorem with proofs given in Appendix D
Theorem 3 (Convergence Error Bound of Non-Convex Objectives). For the problem in Eq. under Assumplion with initial parameter x x0)), using quantized gradients in Eq. for iteration, can upper bound the convergence error by
N-1 Σ
2 2N 1N
Lno²
EIIVE (1)
[( F(X")] (2 Ln)K
(19)
Ldn
N-1
(x)
6(2 Lm)
m=0
Similarly, the convergence error consists of three parts: the error of the gradient descent method, which tends to 0 as the number of iterations N increases; the sampling error, which can be reduced by increasing the batch size or decaying the learning rate; and the convergence error due to quantization, which we want to minimize. Thus, the optimization problem is:
min B.
(1)( >12
N
(dB, + Bpre) C
By solving this optimization problem, we can get
B, = logg [t [1|g (m) 11 +1,
(20)
where t depends on the total communication overhead C. In Appendix E comparison of our scheme's the upper bound of convergence error compared with fixed-bit schemes.
we also give detailed
4.5 DQSGD IN DISTRIBUTED LEARNING
Next, we consider the deployment of our proposed DQSGD algorithm in the distributed learning setting. We have set of W workers who proceed in synchronous steps, and each worker has complete copy of the model. In each communication round, workers compute their local gradients and communicate gradients with the parameter server, while the server aggregates these gradients

---

Under review as a conference paper at ICLR 2021
from workers and updates the model parameters. If (x(x") is the quantized stochastic gradients
in the (-th worker and x(") is the model parameter that the workers hold in iteration n, then the updated value of x by the end of this iteration is: x(*+1) x(*) r)((x())), where G(x(*))
El g' (x((x)) The pseudocode is given in Algorithm 2 Appendix
5 EXPERIMENTS
this section, we conduct experiments on CV and NLP tasks on three datasets: AG-News (Zhang et al. 2013), CIFAR-IO, and CIFAR-100 (Krizhevsky al. 2009), to validate the effectiveness of our proposed DQSGD method. We use the testing accuracy to measure the learning performance and use the compression ratio to measure the communication cost. We compare proposed DQSGD with the following baselines: SignSGD (Seide et al. 2014), TernGrad (Wen et al.) 2017), QSGD (Alistarh et al.) 2017), Adaptive (Oland & Raj] 2015). AdaQS (Guo et al. (020). We conduct periments for W workers and use canonical networks to evaluate the performance of different algorithms: BiLSTM the text classification task the AG-News dataset, Resnet18 on the im- age classification task on the CIFAR-I0 dataset, and Resnet34 on the image classification task on the CIFAR-100 dataset. detailed description of the three datasets, the baseline algorithms, and experimental setting is given in Appendix F
Test Accuracy vs Compression Ratio. Table we compare the testing accuracy and com- pression ratio of different algorithms under different tasks. We can see that although SignSGD, TernGrad, QSGD (4 bits) have compression ratio greater than 8, they cannot achieve more than 0.8895, 0.8545, 0.6840 test accuracy for AG-News, CIFAR-10, 10, CIFAR-100 100 tasks, respectively. In contrast, QSGD (6 bits), Adaptive, AdaQS, and DQSGD can achieve more than 0.8986, 0.8785, 0.6939 test test accuracy. Among them, our proposed DQSGD can save communication cost by 4.11% - 21.73%, 22.36% 25%, 11.89% 24.07% than the other three algorithms.
Table I: Accuracy vs. compression ratio.
AG-News
CIFAR-10
CIFAR-100
Top-1
Compression
Top-1
Compression
Top-1
Compression
Accuracy
Ratio
Accuracy
Ratio
Accuracy
Ratio
Vanilla SGD
0,9016
0.8815
0.6969
SignSGD
0.8663
32
0.5191
0.3955
TernGrad
0.8480
16
0.7418
16
0.6174
16
QSGD (4 bits)
0.8894
8
0.8545
8
0.6837
QSGD (6 bits)
0.9006
5.33
0.8803
5.33
0.6969
Adaptive
0.8991
6.53
0.8787
5.52
0.6943
5.93
AdaQS
0.9001
6.53
0.8809
5.35
0.6960
5.11
DQSGD (Ours)
0.8997
6.81
0,8793
7.11
0.6959
6.73
Fixed Bits vs. Adaptive Bits. Figure I shows the comparison results of fixed bit algorithm QSGD and our proposed DQSGD on CIFAR-TO. Figure (a) and Figure (b) show the testing accuracy curves and the training loss curves, respectively. Figure (c) shows the bits allocation of each iteration of DQSGD, and Figure (d) represents the communication overhead used in the training process of different quantization schemes. From these results, we can see that although QSGD (2 bits) and QSGD (4 bits) have less communication cost, they suffer up to about 14% and 2.7% accuracy degradation compared with Vanilla SGD. The accuracy QSGD (6 bits) and DQSGD is similar to that of Vanilla SGD, but the communication overhead of DQSGD is reduced up to 25% compared with that of QSGD (6 bits). This shows that our dynamic quantization strategy can effectively reduce the communication cost compared with the fixed quantization scheme. Figure 2 shows the accuracy of QSGD and DQSGD under different compression ratios. can be seen that DOSGD achieve higher accuracy than QSGD under the same communication cost.

---

Under review as a conference paper at ICLR 2021
0.9
(5c012bit)
0.8
QsCDMbbt)
OSCD1ebit)
Testing Accuracy
0.7
2.0
Vanilla SGD
Training Loss
0.6
1.5
0.5
Q6GD(26it)
1.0
OSCD(1bit)
CSGD(6bit)
0.5
DQSGD
0.0
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
3000
6000
Iterations
Iterations
(a) Testing accuracy
(b) Training loss
2000
7-
(GB)
1750
0.50
1500
0,8003
0,8253
Testin 1g Accuracy
1250
0.65
Bits
3000
4
750
500
250
3000 Iterations
056012 bi50060044 MIsiSSSDIS
Quantization Schemes
(c) Bits allocation
(d) Communication overhead
Figure 1: The comparison results of QSGD and DQSGD on CIFAR-10.
0.88
Q5GD DQSGD
0.86
Testing Accuracy
0.84
0.82
0.80
0.78
0.76
0.74
16
Compression Ratio
Figure 2: Testing accuracy of QSGD and DQSGD under different compression ratios on CIFAR-10.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li. Ryota Tomioka, and Milan Vojnovic. QSGD:
Communication-lliciennt SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar, SIGNSGD: Compressed optimisation for non-convex problems. arXiv preprint arXiv: 802.0444..44 2018
Sorathan Chaturapruek, John Duchi, and Christopher Ré. Asynchronous stochastic convex op- timization: the noise is in the noise and SGD don't t care. In Advances in Neural Information Processing Systems, pp. 1531-1539, 2015.
Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman, Project adam: Building efficient and scalable deep learning training system. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 571-582, 2014.
Guoxin Cui, Jun Xu, Wei Zeng, Yanyan Lan, Jiafeng Guo, and Xueqi Cheng. MQGrad: Rein- forcement learning of gradient quantization in parameter server. In Proceedings of the 2018 ACM SIGIR International Conference on Theory of Information Retrieval, pp. 83-90, 2018
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et Large scale distributed deep networks. In Advances in Neural Information Processing Systems, pp. 1223-1231, 2012.
Jinrong Guo, Wantao Liu, Wang Wang, Jizhong Han, Ruixuan Li, Yijun Lu, and Songlin Hu. Ac- celerating distributed deep learning by adaptive gradient quantization. IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 1603-1607. IEEE, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--ficiie learning deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR. 2017.
Jed Mills, Jia Hu, and Geyong Min. Communication-effiee federated learning for wireless edge intelligence in loT. IEEE Internet of Things Journal, 2019.
Anders Oland and Bhiksha Raj. Reducing communication overhead in distributed learning by an order of magnitude (almost). In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2219-2223, 2015.
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. Conference of the International Speech Communication Association, pp. 1058-1062, 2014.
Sebastian U Stich, Tean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, pp. 4447-4458, 2018.
Ananda Theertha Suresh, Felix X Yu, Sanjiv Kumar, and H Brendan Memahan. Distributed mean estimation with limited communication. International Conference on Machine Learning, pp- 3339-3337, 2017. 2017.
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TemGrad: Ternary gradients to reduce communication in distributed deep learning. Advances in Neural Information Processing Systems, pp. 1508-1518, 2017.

---

Under review as a conference paper at ICLR 2021
Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. arXiv preprint arXiv:1806.0883 180544 2018.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. In Advances in Neural Information Processing Systems, pp. 649-657, 2015.
Guangxu Zhu, Dongzhu Liu, Yuqing Du, Changsheng You, Jun Zhang, and Kaibin Huang. Toward an intelligent edge: wireless communication meets machine learning. IEEE Communications Magazine, 58( 58(1):19-25, 2020.
10

---

Under review as a conference paper at ICLR 2021
A
PROOF OF PROPOSITION 1
9i U
1+1 1
9i
1
Suppose
||
8. 8
and let 6
=
C(g,, 8), for 0 < c0 <
we have:
pla co} pl
91
1
+
co)
pl 1 91
co
|
8
[g]
1
60
8 g
E0
Similarly, for
< < 0, we have:
91
1+1
1+1 9:
1+1 1
ple, = 60} = pl
11911
8
+
50]
pl
8 1gll
+
8
+
Considering that (9.): = ||او|p sgn((g) ((g,, s) and let é; = - Q2( so we have:
0<& s
p(E.)
|lg 1p
||g 1
5
llg1le
8
S S 0
l1g lp
| 1
B PROOF THEOREM
Considering function Fis L smooth, and using Assumption [ we have:
F(x((+1)) < F(x(")) (n)) - (x(x(") - x())) - " -x((t)))x(1)
xx1)
For QSGD, x (m+1)) = (n) - n9... [9(((())]] so:
F(x(a+1)) F(x(m)) VP 1/, 10xxxxx0,))))) (x(x("))) マ 1 [x(x
- - ) + Ln²
2 -1Q 110,,,9(x()) (1)
Taking total expectations, and using Lemma
I this yields:
Lnp²
LI Ladd
E [((((())) s (") + (-n+ +
V (1)
|
1g (m)
2
2K
12s
11

---

Under review as a conference paper at ICLR 2021
Considering that function F is f strongly convex, and using Assumption 2 so:
Inp 0²
B[F(x(++1))) < F(x(!)) (2 L F(x")] +
2K
Lafd
(x(x("))1}
+ 12x
Subtracting F(x") from both sides, and let = 1 2p07 + Lum², so:
LIi
Lnj'
( - F(xx)] S - F(x')]
((xx(1))13
2K
12s
Applying this recursively:
(170 - -
F(x')]
2K (1 a)
Ldh2 2-1
Σ
N-1-n [1g(x(1)1111
+
12
n1
Similarly, let 3 = 1 - -2L + LIun²
1 02 (1 3
()) - F(x")] 3d (F(x (0) - F(x"]]
2K (1 3)
pddp
N-1
B BN-1-
1-
19((x(1)))
12
n=0
C PROOF OF THEOREM? 2
Both SGD and QSGD can be considered general kind of optimization dynamics, namely, gradient descent with unbiased noise. Based on the central limit theorem, it is assumed that the noise caused by sampling and quantization obeys Gaussian distribution, that is, Qsn, [xxx("))] (x) +
e(n), c(m)) NoO0, E(x(")). Therefore,
consider Equation ( as the discrimination of the
Gaussian process:
x (++1) = (n) - Fx((1" - (n) ((r) ~ N(0, I(x!"))
(21)
The error for general Gaussian processes is hard to analyze due to the intractableness of the integrals, we only consider quadratic problem:
(m+1) x(m) - f)xFF((()) - 7/8 (n)
x(()) - -//Hx((0 (n) + A] - (n)
(I r)H)x(()) 7A (1))
Considering VF(x") yields:
7/A + H| 0, subtracting x" from both sides, and rearranging, this
((++1) x" = =[ ())) (n) 11A x" (n) (I (x(1)) xx) 1 nHHx* (n(
(I (x() -x") - (n)
(n)
12

---

Under review as a conference paper at ICLR 2021
Applying this recursively, let p I - n/H, we have:
x(M) x² p>"((x(0) x*)
Σ [pp N (
Considering that ((n) ~N(0. E(x(m))), then:
N-1
N
hp 1
Ipp (
W(n+1) W(n))
T(N)
where, W a standard d dimensional Wiener process, and I(N) is an Ito integral. Hence x(N
x + p (xx1) - -x*) - ([V). then:
F(x(N)) = x
1
(N) T
(N)
+ (x( + B
2
2 (x(0)
1
-x') Hp (x(0) (0) x*) + 2
((N)
(x x*) + A] H F(x*)
Subtracting Fxx*) from both sides, taking total expectations, and rearranging, this yields:
E[F(x! - F(x")] = 1 _ (p=) HH (x(0) xx) + [E(I(N)
-xp"(x(00 x') +x* A (HE[[(N)
The property of Ito integral I(N) is:
B[[(N)] = 0
N-1
HI(V))
Σ 1- (1))
n=0
Using this property, we have:
B[F(x(N) - F(x")]
2 -(x(0) -xx) -xxx00xxx)))
) HHp (x - -x")
172
Trip Tr/p 11
2
n=0
D PROOF OF THEOREM
Considering function F is L smooth, using the result of Appendix
we have:
Lnf²
LIPa²
Lade
E (((((())))) s (")
(n) + (-n+ +
V (n)
112
(1)
2
2K
12s
13

---

Under review as a conference paper at ICLR 2021
Subtracting F(x(")) from both sides, then applying it recursively, this yields:
Laf N-1
LN12002
B[F(x(N)) F(x -nn
2K
2dy N-1
Σ
1[((x(10)
12 n=0
s
Considering that ((x(N)) 2 F(x*), SO:
2
Taj'
[X S 2N - LN [x F(xx))
(2 Ln)
Ldh
N
E (
+ 6(2 - Ln) N
n=0
E ALGORITHM
Algorithm Dynamic quantized SGD)
1: Input: Learning rate 1). Initial point x (0) E IRd Hyperparametric k,
2: for each iteration n = 1, 0,.,..,, N 1: do
3: ((x(1)) + compute gradient of a batch of data
4: (lg(x(n) (m) || + calculate the norm of g(x("))
5: B, determine the quantization bits
6: j(x(1)) quantize ()(x(1)), Ba)
7: Update the parameter: (m+1) x()) (x()))))
8:
end for
We make an assumptions as follows.
Assumption 4. (Second moment bound). If F(x) is smooth, so the Lp norm of the minibach stochastic gradient g(x) satisfied:
lgx()) < - F(x*)]
-
(22)
It is noted that Assumption 4 is a generalization of Equation
Based this quantization scheme 18 and Assumption 4
get the quantization error:
L 2 da N- ((F(()))))) F[ (1N
DDSGD S
(23)
6 x (CC322 dNYyNN
Accordingly, if we fix the bits, the quantization error is:
1P F(x ) N-1
Oixed
Σ
(24)
6 41CC-2NN-N))/L
m=0
Comparing (23) and 24
we can see that our scheme reduces the error bound about:
1.2 do F(x*)] )1
6ixed HDOSOD
(25)
14

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Dynamic QSGD in Distributed Learning
1: Input: Learning rate 7). Initial point x( IR, Hyperparametric k,
2: for each iteration π = 0, ..., N 1: do
3: On each worker = 1..., W:
4: g'(x(") + compute gradient w.r.. a batch data
5: g' (x(*) t quantize (g' (x(("), B.)
6: send (x(x()) server
7: receive ((x(1)) and Bn41 from server
8: On server:
9: collect all W gradients g' (x(()) from workers
10:
average: G(x(m)) w (x("))
11:
[[((x())| + calculate the norm of g(x( ())
12: Bn-1 + Determine the quantization bits for the next iteration (x))()))
13:
send ((x(")) and B to workers
end for
where A N-1 ((-1)) (a(1-1)(N11)2 is the difference between arithmetic mean and geometric mean. When 7 1, If 1, A1 O.
Based on quantization scheme (20) and Assumption 4 the quantization error is:
L'nd(F(xx(0) - F(x")
3N(2 In) x (1C-32N-dN)/an x Na
(26)
Accordingly, if we fix the bits, the quantization error is:
N-1
Σ n
(27)
3N(2 Ln) 3CN-32N dN)/aN
Comparing (26) and 27
that our scheme reduces the error bound about:
L'nd - F(x')
!!|
Fixed DOSGD
(28)
3N Ln) x 4CC-32N dNN/
where A22 >N nm NN> the difference between arithmetic mean and geometric mean. Consider that 7 # 0, so A > 0.
F EXPERIMENTS
F.1 DATASETS AND BASELINE
We evaluate method DQSGD three datasets: AG-News, CIFAR-10, and C0FAR-100. AG- News dataset (Zhang et al. 2015) contains four categorized news articles, and the number of training samples for each class is 30000 and testing 1900. CIFAR-10/100 (Krizhevsky et al. 2009 dataset are all contain 60,000 32 x 32 RGB images, which are divided into 10 and 100 classes, respectively. We compare DQSGD with the following gradients quantization methods:
SignSGD (Seide et al.
2014): To take the sign of each coordinate of the stochastic gradient vector.
TernGrad
Wen et al.
2017 Quantizes gradients ternary levels {-1;0;1}
15

---

Under review as a conference paper at ICLR 2021
QSGD (Alistarh al. 2017): It is family of compression schemes. The specific quantization In our experiments, we replace the llgll2 in the original text with
operation shown in equation 3
2013:: This dynamic scheme considers that for the gradient with larger root-mean-squared (RMS) value, more quantization bits used.
Adaptive (Oland & Raj
2020 It an adaptive quantization scheme that using few quantization bits in the early epochs and gradually increase bits in the later epochs.
AdaQS (Guo et al.
Table 2: Baselines
Unbiased
Basis for determining bits
SignSGD (Seide et al.
2014)
No
Fixed bits
TernGrrad Wen et al.
2017)
Yes
Fixed bits
QSGD Alistarr ct al.
2017)
Yes
Fixed bits
Adaptive Oland & Raj
2015
Yes
Gradient's poot-men-sqqaate value
Gradient's mean to standard deviation ratio, Iteration number
AdaQS (Go al.
2020
Yes
F.2 EXPERIMENTAL SETUP
We conduct simulations for W workers. For AG-News, 300-dim embeddings pre-traines treitrained on Glove; then, each word can be further encoded sequentially using two layers bidirectional LSTM (BiLSTMM) Furthermore,
the self-attention mechanism obtain the sentence embedding. The classifier is two fully connected layers of size 128 and 4 neurons, respectively. We training CIFAR-10 on Resnet18 (He et al. (0166) and CIFAR-100 on Resnet34 (He et al., (0166), respectively. Other parameters information is shown in Table 3
All results were the average of four random runs.
Table 3: Parameters
Dataset
Net
Learning rate
Batchsize
Interations
Hyperparameters in DQSGD
AG-News
BiLSTM
0.005
32
1000
k = 5,, 0.991
CIFAR-10
Resnet18
0.1
32
6000
k k= 20, a = 0.999
CIFAR-100
Resnet34
0.01
64
6000
k 10, = 0.999
16


Reviews:
[{"review_id": "hF6gXS_asmk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "-It is known that Assumption 3 equation (10) (bounded variance) with Assumption 2 (strong convexity) leads to a contradiction. Thus having these two assumptions together is strong.\nThere are some recent works that overcome Assumption 3 by a different assumption known as the expected smoothness like in the following work: Gower,  R.  M.,  Richtarik,  P.,  and  Bach,  F.    Stochastic quasi-gradient methods: Variance reduction via Jacobian sketching.arxiv:1805.02632, 2018.\nThe authors may revise their strongly convex results part using this kind of assumption.\n\n-In proposition 1 equation (13), it is not clear what the authors mean by the probability of a random variable. I checked the proof but I did not understand it either. \n\n-Some reported results are already known in the literature and the paper gives the impression that these results are new, especially that the authors give the proofs.\nExamples of such results: the unbiasedness of the quantization, its bounded variance, and the first part of theorem 1...\n\n-Page 5, concerning the quadratic example: this is a trivial case and the only case where one can hope the lower bound to match the upper bound. In fact, alpha = beta iff L=mu and from Assumptions 1 & 2 we get that F is quadratic with mu=L which implies H = mu I.\n\n- Equation (20): for me this one of the main results of the paper. But I did not see its proof anywhere?", "extra_scores": {}, "extra_text": {}}, {"review_id": "WTD5dU1wCRQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1.\tThe authors considered uniform upper bound of the stochastic gradients g_i. The authors may argue that \"The classical theoretical analysis of SGD assumes that the stochastic gradients are uniformly bounded\". But one can even strongly argue that this bound is actually $\\infty$. Moreover, an even stronger argument can be made that the above assumption is in contrast with strong convexity. Please see [\"SGD and Hogwild! Convergence Without the Bounded Gradients Assumption\" by Nguyen et al.] as one of the instances. Please understand there are relaxed assumptions such as Strong growth condition on a stochastic gradient as in Assumption 4 of [1]. \n2.\tThere is work [2] that proposes we propose a flexible framework which adapts the compression level to the true gradient at each iteration, maximizing the improvement in the objective function that is achieved per communicated bit. How is work different from theirs? I suggest the authors mention this work and make connections with their present results. \n3.\tPlease check Theorem 3.4. and 3.5 in QSGD paper. There is a count of bits communicating in each round for QSGD which depends on s, the quantization level. Moreover, you also mentioned that “quantization level is roughly exponential to the number of quantized bits”. In light of your formulation how the results in QSGD paper are relevant? Additionally, in Section 3, equations (3) and (4) are not your contributions. Therefore, please adequately cite their sources. \n4.\tWhat is the idea behind Proposition 1? \n5.\tWhat is the point of Theorem 2? On the other hand, where are the derivations/proofs of Equations (18) and (20)? Those are the main results of this paper if I am not wrong. \n6.\tIn terms of experimental results, I had a hard time interpreting Table 1 and associated text in the paragraph “Test Accuracy vs Compression Ratio”. Especially, I do not know how do I understand the last sentence in the abovementioned paragraph. To do proper experiments by using compression techniques, the authors can check a very elaborative work and codebase by [Hang Xu et. al, Compressed Communication for Distributed Deep Learning: Survey and Quantitative Evaluation]. In that case, I would encourage the authors to plot relative data-volume vs. test accuracy similar to Figures 6 and 7 therein. In the present papers, the experiments and their presentations are substandard. \n\nAdditional comments:\n1.\t“Recently, with the booming”---Please refrain from using these types of words. You are preparing a scientific document, not a sci-fi novel. \n2.\tI have some reservations on this statement: “Existing algorithms often quantize parameters into a fixed number of bits, which is shown to be inefficient in balancing the communication-convergence trade-off (Seide et al., 2014; Alistarh et al., 2017; Bernstein et al., 2018). “ In my opinion, QSGD is robust and stable, For 1-bit SGD (both Seide and Bernstein), the proposed solution is to use error-feedback. \n3.\t“show good performance in some certain tasks”---bad sentence.\n\n\n\n[1] Dutta et al. AAAI 2020, On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning.\n[2] Khirirat et al., 2020, A flexible framework for communication-efficient machine learning: from HPC to IoT.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Gi-VG7ccX3a", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers distributed learning using SGD and aims at improving the convergence rate of the quantized SGD. To this purpose, it theoretically characterizes the trade-off between communication cost and the model accuracy in training with quantized stochastic gradients.\nBased on the theoretical analysis, the authors proposed a dynamic quantized SGD framework to optimize the quantization strategy to be analyzing the trade-off between communication and model error.\nIn addition to the theoretical analysis, the performance of the proposed communication scheme is evaluated extensively in computer vision tasks on CIFAR10/100, and NLP on AG-News dataset, and is shown to outperform the other considered quantization techniques.\n\n\nStrengths:\nAlthough the idea of changing the number of quantization bit during training has been proposed and studied before, but this paper looks at it from a new angle and by analyzing the convergence rate under different assumptions for the loss function, it computes the required number of bits to minimize the upper bound of the convergence error.\n\nWeaknesses and questions:\n1. In the proof of proposition 1, it is explicitly assumed that the SGs are uniformly distributed in each quantization bin. Although this might be true for sufficiently small quantization bins (large bits), for low bits (which is the interested region in distributed training) this assumption is not valid. This should be mentioned in the body of the claims (although this assumption is not true in general). To be more accurate, the distribution of error for example for $e>0$ can be written as $P(e)=(1-se) \\sum_l P(g_i/\\|g\\|_p = e+l/s)$, ...\n2. Theorem 2 assumes Gaussian noise, while the quantization noise is non-Gaussian, and prop. 1 assumes it is uniform. It seems that this assumption is not in line with the previous assumptions and practical cases.\n3. The experiments section is not satisfactory. The QSGD and TernGrad methods are relatively old and better quantization methods based on dithering, transforming, ... has already been proposed. Compared to Adaptive and AdaQS, both these methods achieve higher accuracy with a lower compression ratio. On the other hand, QSGD(4 bits) with a higher compression ratio achieves a comparable accuracy. Moreover, the convergence rate plots (Fig. 1) shows that all methods converge almost at the same rate, despite the theoretical analysis and the motivation of the dynamic bt allocation\nFor a fair comparison, the compression ratio of all methods should be fixed to the same value and the convergence rate as in Fig. 1(a),(b) (in addition to the final accuracy) should be evaluated. The limited experiments and not appropriate comparison setups are major shortcomings of the paper. \n\nMinor:\nTheorem 1 uses assumption 3, not stated in the body.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5kBE4C--4aH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed an adaptive quantized method which is derived by minimizing a constrained quantization error bound. The theoretical analysis suggests adjusting the quantization level according to the gradient norm, convergence rate of the model, and the current iteration number. Theoretical results show that the dynamic bits leads to better error bound than the fixed bits. The result is intuitive. Overall, the paper is clearly written. But the improvement is not significant enough to warrant a publication at ICLR.\n\n1. In the proof of Proposition 1, it is assumed that $\\frac{g_i }{ \\|g\\|_p} \\in U(\\frac{l}{s}, \\frac{l+1}{s})$. Is this empirically supported? And, the final result looks wrong to me. For example, $p(\\frac{g_i}{\\|g\\|_p} = \\frac{l}{s} + \\epsilon_0)$ should be $1/s$ and $s - s^2\\epsilon_0$ can be much larger than 1.\n\n2. B_n in (18) depends on \\alpha and k. How can we estimate them in practice? On the other hand, (18) shows that more bits may need to be used in the later stage of training (due to exponent $N - n$), while (20) suggests a smaller number of bits in later iterations (as gradient norm typically has a trend of decreasing during training). They are contradictory to each other.\n\n3. In the experiment, (18) or (20) is used? \n\n4. As the proposed method uses dynamic number of bits, how do we compute its compression ratio? Is it averaged compression ratio across iterations.\n\n5. From Table 1, we can see that though the proposed method has slightly higher compression ratio than QSGD, its accuracy is worse. Since the compression overhead is nontrivial in practice and there is no report on training time, it is not clear if the proposed method is faster in terms of CPU wall-clock time.\n\n6. The baseline looks weak. There are a number of papers showing that error feedback can fix the poor performance of signSGD (Karimireddy 2019; Tang 2019; Zheng 2019). And, is momentum used in the experiment?\n\nKarimireddy, Sai Praneeth, et al. \"Error feedback fixes signsgd and other gradient compression schemes.\" ICML 2019.\n\nTang, Hanlin, et al. \"Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression.\" ICML 2019.\n\nZheng, S., Huang, Z., Kwok, J. \"Communication-efficient distributed blockwise momentum SGD with error-feedback.\" NeurIPS 2019.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have a strong consensus towards rejection here, and I agree with this consensus , although I think some of the reviewers' concerns are misplaced. For example, the paper does not appear to use a magnitude upper bound that would be vacuous together with a strong convexity assumption (although variance bounds + strong convexity do cover only a small fraction of strongly convex learning tasks, these assumptions aren't vacuous).  Some feedback I have that perhaps was not covered by the reviewers:

Pros:

 - Studying the setting where the number of bits varies dynamically is very interesting (although, as Reviewer 3 points out, not entirely novel). There is significant possibility for improvement from this method, and your theory seems to back this up.

Cons:

 - The experimental setup is weak, and is measuring the wrong thing. When we run SGD to train a model, what we really care about is when the training finishes: the total wall clock time to train on some system. For compression methods with fixed compression rates, it's fine to use the number of bits transmitted as a proxy, because (when the number of bits transmitted is uniform over time) this will be monotonic in the wall-clock time. However, when the bits transmitted per iteration can change over time, this can have a difficult-to-predict effect on the wall-clock time, because of the potential for overlap between communication and computation (where below a certain number of bits sent, the system is not communication-bound). Wall-clock time experiments comparing against other more modern compression methods would significantly improve this paper.
Decision: Reject