On Distributed Adaptive Optimization with Gradient Compression
Authors: Xiaoyun Li
Belhal Karimi
Ping Li
Venue: ICLR 2022 Poster (2022)

Abstract: We study COMP-AMS, a distributed optimization framework based on gradient averaging and adaptive AMSGrad algorithm. Gradient compression with error feedback is applied to reduce the communication cost in the gradient transmission process. Our convergence analysis of COMP-AMS shows that such compressed gradient averaging strategy yields same convergence rate as standard AMSGrad, and also exhibits the linear speedup effect w.r.t. the number of local workers. Compared with recently proposed protocols on distributed adaptive methods, COMP-AMS is simple and convenient. Numerical experiments are conducted to justify the theoretical findings, and demonstrate that the proposed method can achieve same test accuracy as the full-gradient AMSGrad with substantial communication savings. With its simplicity and efficiency, COMP-AMS can serve as a useful distributed training framework for adaptive methods.

Published as a conference paper at ICLR 2022
ON DISTRIBUTED ADAPTIVE OPTIMIZATION WITH GRADIENT COMPRESSION
Xiaoyun Li, Belhal Karimi, Ping Li
Cognitive Computing Lab Baidu Research
10900 NE 8th St. Bellevue, WA 98004, USA
berpopaaiiii.llllaaariiiiiiii wtwp:aaaiiiiiiiiiiniiniee lipingl1; @ba du. com.
ABSTRACT
We study COMP-AMS, a distributed optimization framework based on gradient averaging and adaptive AMSGrad algorithm. Gradient compression with error feedback is applied to reduce the communication cost in the gradient transmission process, Our convergence analysis of COMP-AMS shows that such compressed gradient averaging strategy yields same convergence rate standard AMSGrad, and also exhibits the linear speedup effect w.r.t the number of local work- Compared with recently proposed protocols distributed adaptive methods, COMP-AMP AMS is simple and convenient. Numerical experiments are conducted justify the theoretical findings, and demonstrate that the proposed method achieve same test accuracy as the full-gradient AMSGrad with substantial com- munication savings. With its simplicity and efficiency, COMP-AMS can serve useful distributed training framework for adaptive gradient methods.
INTRODUCTION
Deep neural network has achieved the state-of-the-art learning performance on numerous Al ap- plications, e.g., computer vision and natural language processing (Graves et al., 2013; Goodfellow et al., 2014; He et al., 2016; Young et al., 2018; Zhang et al., 2018), reinforcement learning (Mnih al., 2013; Levine al., 2016; Silver al., 2017), recommendation systems (Covington et al., 2016), computational advertising (Zhao et al., 2019; 9; Xu et al., 2021; Zhao et al., 2022), etc. With the increasing size of data and growing complexity of deep neural networks, standard single-machine training procedures encounter at least two major challenges:
Due to the limited computing power of a single-machine, processing the massive number of data samples takes long time- training too slow. Many real-world applications cannot afford spending days or even weeks on training.
In many scenarios, data are stored on multiple servers, possibly at different locations, due to the storage constraints (massive user behavior data, Internet images, etc.) privacy reasons (Chang et al., 2018). Hence, transmitting data among servers might be costly.
Distributed learning framework has been commonly used tackle the above two issues. Consider the distributed optimization task where workers jointly solve the following optimization problem
1 Σ E [F((0:))] min f(0) == min Σ f((0) = n2 0
n
(I)
where the non-convex function f. represents the average loss over the local data samples for worker i E [r]]. and 0 E dd the global model parameter. X; is the data distribution on each local node. In the classical centralized distributed setting, in each iteration the central server uniformly randomly assigns the data to n local workers (X''s 's are the same), at which the gradients of the model are computed in parallel. Then the central server aggregates the local gradients, updates the global model (e.g., by stochastic gradient descent (SGD)), and transmits back the updated model to the

---

Published as a conference paper at ICLR 2022
local nodes for subsequent gradient computation. The scenario where X 's are different gives rise to the recently proposed Federated Learning (FL) (McMahan et al., 2017) framework, which will not be the major focus of this work. As can see, distributed training naturally solves aforementioned issues: 1) We use n computing nodes to train the model, so the time per training epoch can be largely reduced; 2) There is need to transmit the local data to central server. Besides, distributed training also provides stronger error tolerance since the training process could continue even one local machine breaks down. As a result of these advantages, there has been a surge of study and applications on distributed systems (Nedic & Ozdaglar, 2009; Boyd et al., 201 1; Duchi et al., 2012; Goyal et al., 2017: Hong et al., 2017; Koloskova et al., 2019; Lu et al., 2019).
Gradient compression. Among many optimization strategies, SGD is still the most popular proto- type in distributed training for its simplicity and effectiveness (Chilimbi et al., 2014; Agarwal al,, 2018; Mikami et al., 2018). Yet, when the deep learning model is very large, the communication be- tween local nodes and central server could be expensive, and the burdensome gradient transmission would slow down the whole training system. Thus, reducing the communication cost in distributed SGD has become an active topic, and an important ingredient of large-scale distributed systems (e.g., Seide et al. (2014)). Solutions based quantization, sparsification and other compression techniques of the local gradients have been proposed, e.g., Aji & Heafield (2017); Alistarh et al. (2017); Sa et al. (2017); Wen et al. (2017); Bernstein al. (2018) 1); Stich et al. (2018); Wangni al. (2018); Ivkin et al. (2019); Yang et al. (2019); Haddadpour et al. (2020). However, it has been ob- served both theoretically and empirically (Stich al., 2018; Ajallocian & Stich, 2020), that directly updating with the compressed gradients usually brings non-negligible performance downgrade in terms of convergence speed and accuracy. To tackle this problem, studies (e.g.. Stich et al. (2018); Karimireddy et al. (2019)) show that the technique of error feedback can to a large extent remedy the issue of such gradient compression, achieving the same convergence rate as full-gradient SGD.
Adaptive optimization. In recent years, adaptive optimization algorithms (e.g., AdaGrad (Duchi et al., 2010), Adam (Kingma& Ba, 2015) and AMSGrad (Reddi et al., 2018)) have become popular because of their superior empirical performance. These methods use different implicit learning rates for different coordinates that keep changing adaptively throughout the training process, based on the learning trajectory. In many cases, adaptive methods have been shown to converge faster than SGD, sometimes with better generalization as well. Nevertheless, the body of literature that extends adaptive methods to distributed training is still fairly limited. In particular, even the simple gradient averaging approach, though appearing standard, has not been analyzed for adaptive optimization algorithms. Given that distributed SGD with compressed gradient averaging can match the perfor- mance of standard SGD, one natural question is: is it also true for adaptive methods? In this work, we fill this gap formally, by analyzing COMP-AMS, a distributed adaptive optimization framework using the gradient averaging protocol, with communication-efficii method has been implemented in the PaddlePaddle platform (www. paddlepaddee e org. cn).
gradient compression. Our
Our contributions. We study simple algorithm design leveraging the adaptivity of AMSGrad and the computational virtue of local gradient compression:
We propose COMP-AMS, a synchronous distributed adaptive optimization framework based on global averaging with gradient compression, which is efficient in both communi- cation and memory as no local moment estimation is needed. We consider the BlockSign and Top- compressors. coupled with the -eoor-ced technique to compensate for the bias implied by the compression step for fast convergence.
We provide the convergence analysis of distributed COMP-AMS (with workers) in smooth non-convex optimization. the special case of n = 1 (single machine), similar to SGD, gradient compression with error feedback in adaptive method achieves the same convergence rate O vT:) as the standard bull-gradient counterpart. Also, we show that with
a properly chosen learning rate, COMP-AM achieves O(
convergence, implying a linear speedup in terms of the number of local workers to attain a stationary point.
VnT
Experiments are conducted on various training tasks on image classification and sentiment analysis to validate our theoretical findings on the linear speedup effect. Our results show that COMP-AMS has comparable performance with other distributed adaptive methods, and approaches the accuracy of full- aall-precision AMSGrad with a substantially reduced com- munication cost. Thus, it can serve as convenient distributed training strategy in practice.
2

---

Published as a conference paper at ICLR 2022
2 RELATED WORK
2.1 DISTRIBUTED SGD WITH COMPRESSED GRADIENTS
Quantization. To reduce the expensive communication in large-scale distributed SGD training systems, extensive works have considered various compression techniques applied the gradient transaction procedure. The first strategy is quantization. Dettmers (2016) condenses 32-bit float- ing numbers into 8-bits when representing the gradients. Seide al. (2014); Bernstein et al. (2018; 2019); Karimireddy et al. (2019) use the extreme 1-bit information (sign) of the gradients, com- bined with tricks like momentum, majority vote and memory. Other quantization- baaded methods include QSGD (Alistarh et al., 2017; Zhang et al., 2017; Wu et al., 2018) and LPC-SVRG (Yu et al., 2019b), leveraging unbiased stochastic quantization. Quantization has been successfully applied to industrial-level applications, e.g., Xu et al. (2021). The saving in communication of quantization methods is moderate: for example, 8-bit quantization reduces the cost to 25% (compared with 32-bit full pilecicccisoo). Even in the extreme 1-bit case, the largest compression ratio is around 1/32 N 3.1%.
Sparsification. Gradient sparsification is another popular solution which may provide higher com- pression rate. Instead of commuting the full gradient, each local worker only passes few coordi- nates to the central server and zeros out the others. Thus, we can more freely choose higher compres- sion ratio (e.g.. 1%,0 1)), still achieving impressive performance in many applications (L.in al., 2018). Stochastic sparsification methods, including uniform and magnitude based sampling ( (Wangni al., 2018), select coordinates based on some sampling probability, yielding unbiased gradient compressors with proper scaling. Deterministic methods are simpler, e.g., Random-k, Top-k (Stich et al., 2018; Shi et al., 2019) (selecting i elements with largest magnitude), Deep Gradient Com- pression (Lin et al., 2018), but usually lead to biased gradient estimation. More applications and analysis of compressed distributed SGD can be found in Alistarh et al. (2018); Jiang & Agrawal (2018); Jiang et al. (2018); Shen et al. (2018); Basu et al. (2019), among others.
Error Feedback (EF). Biased gradient estimation, which is consequence of many aforementioned methods (e.g.. signSGD, Top-k), undermines the model training, both theoretically and empirically, with slower convergence and worse generalization (Ajallocian & Stich, 2020; Beznosikov et al., 2020). The technique of error feedback is able to "correct for the bias" and fix the convergence issues. In this procedure, the difference between the true stochastic gradient and the compressed one is accumulated locally, which is then added back to the local gradients in later iterations. Stich et al. (2018); 8); Karimireddy et al. (2019) prove the O (++) and O / convergence rate of EF-SGD in strongly convex and non-convex setting respectively, matching the rates of vanilla SGD (Nemirovski et al., 2009; Ghadimi & Lan, 2013). More recent works on the convergence rate of SGD with error feedback include Stich & Karimireddy (2019); Zheng et al. (2019); Richtárik et al. (2021), etc.
2.2 ADAPTIVE OPTIMIZATION
In each SGD update, all the coordinates share the same learning rate, which is either constant
Algorithm 1 AMSGRAD (Reddi et al., 2018)
or decreasing through the iterations. Adap-
1: Input: parameters 31, 32, c, learning rate m
tive optimization methods cast different learn-
2: Initialize: 0g E IR my = 2/- = 0 E Rd
ing rates on each dimension. For instance, Ada- Grad, developed in Duchi et al. (2010), divides
T' 3: for t= t= ,,..., do
4: Compute stochastic gradient gr at 0g
the gradient clementwise by / / of e Rd,
5:
m, = B B,m,-1 + (1 3 )
where Se E IRd is the gradient vector at time t and d is the model dimensionality. Thus, it intrinsically assigns different learning rates to different coordinates throughout the training elements with smaller previous gradient magni- tudes tend to move larger step via larger learn- ing rate. Other adaptive methods include AdaDelta (Zeiler, 2012) and Adam (Kingma & Ba, 2015), which introduce momentum and moving average of second moment estimation into AdaGrad hence leading to better performances. AMSGrad (Reddi et al., 2018) (Algorithm 1, which is the prototype in our paper), fixes the potential convergence issue of Adam. Wang al. (2021) and Zhou et al.
6:
Vt- = B2u,_ 1 - (1 B=
7:
0. mmx((;;)) (0:x(0;-1,0) Ut)
8:
ft+1 = 0r Vorte
my
9: end for
3

---

Published as a conference paper at ICLR 2022
(2020) improve the convergence and generalization of AMSGrad through optimistic acceleration and differential privacy.
Adaptive optimization methods have been widely used in training deep learning models in language, computer vision and advertising applications, c.g., Choi et al. (2019); You et al. (2020); Zhang et al. (2021); Zhao et al. (2022). In distributed setting, Nazari al. (2019); Chen et al. (2021b) study decentralized adaptive methods, but communication efficiency was not considered. Mostly relevant our work, Chen al. (2021a) proposes a distributed training algorithm based on Adam, which requires every local node to store a local estimation of the moments of the gradient. Thus, one has to keep extra two more tensors of the model size on each local worker, which may be less feasible in terms of memory particularly with large models. More recently, Tang et al. (2021) proposes an Adam pre-conditioned momentum SGD method. Chen et al. (2020); Karimireddy et al. (2020); Reddi et al. (2021) proposed local/global adaptive FI. methods, which can be further accelerated via layer-wise adaptivity (Karimi al., 2021).
COMMUNICATIONEFFFIER ADAPTIVE OPTIMIZATION
3.1 GRADIENT COMPRESSORS
In this paper, we mainly consider deterministic q-deviate compressors defined as below.
Assumption 1. The gradient compressor C IRdd + Rdd is q-deviate: for Va E Rd. 20594 such that [|C(z) - x1| S q ||=||]
Larger q indicates heavier compression, while smaller q implies better approximation of the true gradient. q = 0 implies C(x) = x, i.e., no compression. In the following, we give two popular and efficient q-deviate compressors that will be adopted in this paper.
Definition 1 (Top-k). For Rd, denote S as the size-k set of E [d] with largest l magnitude [o.]. The Top-k compressor is defined as C(x); = 24 if E S; C(x); = 0 otherwise.
Definition 2 (Block-Sign). For x Rd, define M blocks indexed by B, i = I,.,, M, with d; == [B.). The Block-Sign compressor is defined C(x)= [sign(xE, | 1l1 : ..... sign (xgg( where TB, is the sub-vector of x at indices B..
| Ila da
Remark 1. It well-known (Stich al., 2018) that for Top-k, =2=10 1 B. For Block-Sign, by Cauchy-Schwarts inequality we have q²
minte[M] d, where M and d, are defined in
Definition 2 (Zheng et al., 2019).
The intuition behind Top-k is that, it has been observed empirically that when training many deep models, most gradients are typically very small, and gradients with large magnitude contain most information. The Block-Sign compressor is a simple extension of the 1-bit SIGN compressor (Seide et al., 2014; Bernstein et al., 2018), adapted to different gradient magnitude which, for neural nets, are usually set as the distinct network layers. The scaling factor in Definition is to preserve the (possibly very different) gradient magnitude in each layer. In principle. Top-k would perform the best when the gradient effectively sparse, while Block-Sign compressor favorable by nature when most gradients have similar magnitude within each layer.
different blocks,
3.2 COMP-AMS: DISTRIBUTED ADAPTIVE TRAINING BY GRADIENT AGGREGATION
We present in Algorithm the proposed caamunncatioo-effcieeee distributed adaptive method in this paper, COMP-AMS. This framework can be regarded as analogue to the standard synchronous distributed SGD: in each iteration, each local worker transmits to the central server the compressed stochastic gradient computed using local data. Then the central server takes the average of local gradients, and performs an AMSGrad update. In Algorithm 2, lines 7-8 depict the error feedback operation local nodes. 6t is the accumulated error from gradient compression on the i-th worker up to time - 1. This residual is added back to gt.; to get the "corrected" gradient. In Section and Section 5, we will show that error feedback, similar to the case of SGD,, also brings good convergence behavior under gradient compression in distributed AMSGrad.
4

---

Published as a conference paper at ICLR 2022
Algorithm 2 Distributed COMP-AMS with error feedback (EF)
Input: parameters 31. $2, e, learning rate 1/: 2: Initialize: central server parameter 01 E I S Rd e1, the error accumulator for each
worker; mo = 0, Up = 0, 0g
3: for = 1,..., do
4: parallel for worker i E [n] do:
5:
Receive model parameter 8, from central server
6:
Compute stochastic gradient It.i at 0g
7:
Compute the compressed gradient Gt,i Cgg, + et,i) Update the error 1t+ εz + gt.i Jt.i
8:
9:
Send 9t.s back to central server end parallel
11: Central server do:
ft -- St.
13:
my 8im--1 + (1 B1 B1)0t
14:
Tt = 12 1 + B2)gE
15:
& max(U;, 1t-1)
16:
Update the global model 01t1 = 0: Voi+E
m.
17:
end for
Comparison with related methods. Next, we discuss the differences between COMP-AMS and two recently proposed methods also trying solve compressed distributed adaptive optimization.
Comparison with Chen et al. (2021a). Chen al. (2021a) develops quantized variant of Adam (Kingma & Ba, 2015), called "QAdam". this method, each worker keeps a local copy of the moment estimates, commonly noted m and v, and compresses and transmits the ratio m as whole to the server. Their method is hence very much like the compressed distributed SGD, with the exception that the ratio plays the role of the gradient vector Communication-wiss Thus, two local moment estimators are additionally required, which have same size as the deep learning model. In our COMP-AMS, the moment estimates and are kept and updated only at the central server, thus not introducing any extra variable (tensor) on local nodes during training (except for the error accumulator). Hence, COMP-AMS is not only effective in communication reduction, but also efficient in terms memory (space), which is feasible when training large-scale learners like BERT and CTR prediction models, e.g., Devlin al. (2019); Xu et al. (2021), consumption in practice. Additionally, the convergence rate Chen et al. (2021a) does not improve linearly with n, while we prove the linear speedup effect of COMP-AMS.
lower the hardware
Comparison with Tang et al. (2021) The recent work (Tang et al., 2021) proposes "IBitAdam". They first run some warm-up training steps using standard Adam, and then store the second moment moving average Then, distributed Adam training starts with u frozen. Thus, 1BitAdam actually more like a distributed momentum SGD with some pre-conditioned coordinate-wis learning rates. The number of warm-up steps also needs to be carefully tuned, otherwise bad pre-conditioning may hurt the learning performance. Our COMP-AMS is simpler, pre-training is needed. Also, BitAdam requires extra tensors for m locally, while COMP-AME does not need additional local memory.
CONVERGENCE ANALYSIS
For the convergence analysis of COMP-AMS will make following additional assumptions.
Assumption 2. (Smoothness) For Vi E [n), Jt is L-smooth: [:) - v)((O)) < L 1|0 Ø1]-
Assumption 3. (Unbiased and bounded stochastic gradient) For Vt > 0, vi E [n], the stochastic gradient is unbiased and uniformly bounded: E[gr,)] -Vf((0,) and || < G.
Assumption 4. (Bounded variance) For Vt > O, Vi E [n]: (i) the local variance of the stochas- tic gradient bounded: Elllgr, (1.)).) < a²; (ii) the global variance bounded by Dn V (((.)) (0.)) S So²
5

---

Published as a conference paper at ICLR 2022
In Assumption the uniform bound on the stochastic gradient is common in the convergence anal- ysis of adaptive methods, e.g., Reddi et al. (2018); Zhou et al. (2018); Chen et al. (2019). The global variance bound og in Assumption 4 characterizes the difference among local objective functions, which, is mainly caused by different local data distribution X; in (1). In classical distributed setting where all the workers can access the same dataset and local data assigned randomly, of 0. While typical federated learning (FL) setting with og 0 is not the focus of this present paper, we consider the global variance in our analysis to shed some light on the impact of non-i.i.d data distribution in the federated setting for broader interest and future investigation.
We derive the following general convergence rate of COMP-AMS in the distributed setting. The proof is deferred to Appendix B.
Theorem 1. Denote Co = V (1-4"²-
40 G2 + Ci =
I-31
91
+
I-q"
24
0 = arg min 5(0) defined as Algorithm 2 satisfies
(1). Under Assumptions I to 4, with TJt 3Co 3CoV2LL max (2L,C1)
B [[[))(1) 2Co( B[f(0;) f((0)
nLo?
3n LC
T"
ME
ne²
92 + (1 g2)222
(1+ TVe
11L + 2C1)C Te
The LHS of Theorem is the expected squared norm of the gradient from a uniformly chosen iterate t E [T), which is common convergence measure in non-convex optimization. From Theorem 1, we see that the more compression we apply the gradient vectors (i.e., larger 9). the larger the gradient magnitude is, i.e., the slower the algorithm converges. This is intuitive as heavier compression loses more gradient information which would slower down the learner to find a good solution.
Note that, COMP-AMS with (Algorithm 1) with compressed gradients instead of full-precision ones. Karimireddy et al. (2019) specifically analyzed this case for SGD, showing that compressed single-machine SGD with error feedback has the same convergence rate as vanilla SGD using full gradients. In alignment with the conclusion in Karimireddy et al. (2019), for adaptive AMSGrad, we have similar result.
naturally reduces to the single-machine (sequential) AMSGrad
Corollary 1. When n 1, under Assumption I to Assumption 4, setling the stepsize T] 3Co 2/o/2L m2x VT }. Algorithm 2 satisfies
minf
1
T
0²
d T
B[ O T
VT
VT
Corollary states that with error feedback, single machine AMSGrad with biased compressed gra- dients can also match the convergence rate O / + T: of standard AMSGrad (Zhou et al., 201 8) in non-convex optimization. It also achieves the same rate O ( of vanilla SGD (Karimireddy et al., 2019) when T' is sufficiently large. In other words, error feedback also fixes the convergence issue of using compressed gradients AMSGrad.
Linear Speedup. In Theorem the convergence rate is derived by assuming constant learning rate. By carefully choosing a decreasing learning rate dependent on the number of workers, we have the following simplified statement.
Corollary 2. Under the same setting Theorem set 1
min 3C 22. max (2
V The
COMP-AMS iterates admit
T Σ
d²
n(o² + +o
00- VnT
+
VnT
In Corollary 2, we see that the global variance o2 appears the O(+) term, which says that asymptotically has no impact the convergence. This matches the result of momentum SGD (Yu

---

Published as a conference paper at ICLR 2022
et al., 2019a). When T& 2 O(n²) is sufficiently large, the third term in (2) vanishes, and the con- vergence rate becomes O VnT Therefore, to reach an (6) stationary point, one worker (n 1) needs T ( (aa iterations, while distributed training with n workers requires only T = O nda iterations, which is n times faster than single machine training. That is, COMP-AME has linear speedup in terms of the number of the local workers. Such acceleration effect has also been reported for compressed SGD (Jiang & Agrawal, 2018; Zheng et al., 2019) and momentum SGD (Yu et al., 2019a) with error feedback.
EXPERIMENTS
In this section, provide numerical results several common datasets. Our main objective is to validate the theoretical results, and demonstrate that the proposed COMP-AMS can approach the learning performance of full-precision AMSGrad with significantly reduced communication costs.
5.1 DATASETS, MODELS AND METHODS
Our experiments are conducted on various image and text datasets. The MNIST (LeCun et al., 1998) contains 60000 training samples of 28 x 18 gray-scale hand-written digits from 10 classes, and 10000 test samples. We train MNIST with Convolutional Neural Network (CNN), which has two convolutional layers followed by two fully connected layers with ReLu activation. Dropout is applied after the max-pooled convolutional layer with rate 0.5. The CIFAR- 10 dataset (Krizhevsky & Hinton, 2009) consists of 50000 32 x 32 RGB natural images from 10 classes for training and also 10000 images for testing, which is trained by LeNet-5 (LeCun et al., 1998). Morcover, implement ResNet-18 (He et al., 2016) on this dataset. The IMDB movie review (Maas et al., 2011) popular binary classification dataset for sentiment analysis. Fach movie review is tokenized by top-2000 most frequently appeared words and transformed into integer vectors, which is of maximal length 500. We train a Long-Shon Term Memory (LSTM) network with a 32-dimensional embed- ding layer and 64 LSTM cells, followed by two fully connected layers before output. Cross-entropy loss is used for all the tasks. Following the classical distributed training setting, in each training iteration, data samples are uniformly randomly assigned to the workers.
We compare COMP-AMS with full- full-precision distributed AMSGrad, QAdam (Chen et al., 2021a) and 1BitAdam (Tang et al., 2021). For COMP-AMS, Top-k picks top 1% gradient coordinates (i.e., sparsity 0.01). QAdam and 1BitAdam both use 1-bit quantization to achieve high compression. For MNIST and CIFAR-10, 10, the local batch size on each worker is set to be 32. For IMDB, the local batch size is 16. The hyper-parameters in COMP- AMS are set as default 31 = 0.9, Bg = 0.999 and 10-8 which are also used for QAdam and BBitAdam. For IBitAdam, the epochs for warm-up training is set to be 1/20 of the total epochs. For all methods, we tune the initial learning rate over fine grid (see Appendix A) and report the best results averaged over three independent runs. Our experiments are performed on a GPU cluster with NVIDIA Tesla V100 cards.
5.2 GENERAL EVALUATION AND COMMUNICATION EFFICIENCY
The training loss and test accuracy on MNIST + CNN, CIFAR-IO LeNet and IMDB LSTM are reported in Figure 1. We provide more results on larger ResNet-18 model in Appendix A. On CIFAR-10 10. we deploy a popular decreasing learning rate schedule, where the step size rj is divided by 10 at the 40-th and 80-th epoch, respectively. We observe:
On MNIST, all the methods can approach the training loss and test accuracy of full- precision AMSGrad. The BBitAdam seems slightly better, but the gap is very small. On CIFAR-10, COMP-AMS with Block-Sign performs the best and matches AMSGrad in terms of test accuracy.
On IMDB, COMP-AMS with Top-k has both the fastest convergence and best generaliza- tion compared with other compressed methods. This is because the IMDB text data is more sparse (with many padded zeros), where Top-k is expected to work better than sign. The 1BitAdam converges slowly. We believe one possible reason that BitAdam is quite sen- sitive to the quality of the warm-up training. For sparse text data, the estimation of second moment is more unstable, making the strategy of freezing by warm-up less effective.
7

---

Published as a conference paper at ICLR 2022
1.5
0.8
AMS
AMI
-Dist AMS
COMP AMS Topk
COMP AMS-ToTT Topk COMP-AMS, BuSign
COMP AMS Topk
Train Loss
CAdam
COMP AMS BiSigg
Train Loss
OAdam
Train Loss
DAcam
COMP-AMA AMS BxSign
1itiddamm
18itAdam
1Bit/iam
0.4
CIFAR
0.2
MNIST
IMDB
10
15
20
0
25
50
75
100
10
15
20
Epochs
Epochs
Epochs
99
80
90
Test Accuracy
Test Accuracy
Test Accuracy
98
MNIST
70
CIFAR
80
IMDB
Dist-AMS
AMS
97
COMP AMS BXSIgn
COMP AMS- Topk
60
COMP-AMS-BKSUO
COMP-AMS-TOR Took
70
COMP-AMS AMS--kSiig
COMP-A COMP--MS-- TooK
DAdam
OAdam
OAdim
1B1Adam
1B4/dam
1BtAdam
96
50
60
0
5
10
15
20
25
50
75
100
0
5
10
15
20
Epochs
Epochs
Epochs
Figure 1: Training loss and test accuracy vs. epochs, on MNIST + CNN, CIFAR- + LeNet and IMDB LSTM with n 16 local workers.
Communication Efficiency. In Figure we plot the training loss and test accuracy against the number of bits transmitted to the central server during the distributed training process, where we assume that the prec-iciiisoon gradient is represented using 32 bits per floating number. As we can see, COMP-A AMM-TTT--..00 achieves around 100x communication reduction, to attain similar accuracy as the full-precision distributed AMSGrad. The saving of Block-Sign is around 30x, but it gives slightly higher accuracy than Top-0.01 on MNIST and CIFAR-10. 10. In all cases, COMP- AMS can substantially reduce the communication cost compared with full-precision distributed AMSGrad, without losing accuracy.
0.15
0.8
Dist-AMS
DistAMS
DIILANS
COMP-ANS-TOOK
COMP-AMS-TopK
COMP-AMSS-TpR
COMP-AMS Bkiigg
COMP-AMS-BKSig
0.6
COMP-AMS-BASip
Train Loss
OAdam (BrAsam
Train Loss
1.5
QAdam
Train Loss
QAdaa
1BiAdam
(BrAdam
0.4
CIFAR
MNIST
0.2
0.05
IMDB
0.5
20
30
25
30
40
20
25
30
INg(No. bits)
log(No. bits)
Iog(No. bits)
99
80
90
Test Accuracy
MNIST
Test Accuracy
70
Test Accuracy
800
98
CIFAR
IMDB
60
70
Chstt-AiS
Dist-AMS
-Dist AMS
COMP-AMS-Touke
COMP SAMIP--M-TTore TopK
COMP-AMS-TORE
97
COMP-AMS-BRR AMI-BBkigg
50
QAdam
COMP-AMS BkSign
60
COMP AMS BkSign
GAddam
1B:Adam
18itAckam
1BrAdam
50
20
25
30
25
30
35
40
20
25
30
log(No. bits)
log(No. bits)
log(No. bits)
Figure 2: Train loss and Test accuracy vs. No. bits transmitted, on MNIST CNN, CIFAR- 10 LeNet and IMDB + LSTM with 16 local workers.
8

---

Published as a conference paper at ICLR 2022
5.3
LINEAR SPEEDUP OF COMP-AMS
0.12
1.4
0.1
8
Train Loss
Train Loss
1.2
0.08
MNIST
CIFAR
0.06
0.04
0.6
5000
10000
0
5000
10000
15000
Iterations
Iterations
Figure 3: The linear speedup of COMP-AMS with varying n. Left: MNIST with Block-Sign compressor on CNN. Right: CIFAR-10 with Top-k-0.01 compression on LeNet.
Corollary 2 reveals the linear speedup of COMP-AMS in distributed training. In Figure 3, we present the training loss on MNIST and CIFAR-I0 10 against the number of iterations, with varying number of workers n. We use COMP-AMS with Block-Sign on MNIST, and Top-k-0001 on CIFAR. As suggested by the theory, we use x 10 /n as the learning rate. From Figure we see the number of iterations to achieve a certain loss exhibits strong linear relationship with n n-it it (approximately) decreases by half whenever we double n, which justifies the linear speedup of COMP-AMS.
5.4 DISCUSSION
We provide a brief summary of our empirical observations. The proposed COMP-AMS able to match the learning performance of full full-gradient AMSGrad in all the presented experiments. In par- ticular, for data/model involving some sparsity structure, COMP-AMS with the Top-k compressor could be more effective. Also, our results reveal that IBitAdam might be quite sensitive to the pre-conditioning quality, while COMP-AMS can more easily tuned and implemented practice.
We would like to emphasize that, the primary goal of the experiments is to show that COMP-AMS able to match the performance of full-precision AMSGrad, but not to argue that COMP-AMS is always better than the other algorithms. Since different methods use different underlying opti- mization algorithms (e.g., AMSGrad, Adam, momentum SGD), comparing COMP-AMS with other distributed training methods would be largely determined by the comparison among these optimiza- tion protocols, which is typically data and task dependent. Our results say that: whenever one wants use AMSGrad to train deep neural network, she/he can simply employ the distributed COMP- AMS scheme to gain linear speedup in training time with learning performance as good as the full full-precision training, taking little communication cost and memory consumption.
6 CONCLUSION
In this paper, we study the simple, convenient, yet unexplored gradient averaging strategy for dis- tributed adaptive optimization called COMP-AMS. Top-k and Block-Sign compressor are incorpo- rated for communication efficiency. whose biases are compensated by the error feedback strategy. We develop the convergence rate of COMP-AMS, and show that same as the case of SGD, for AMS- Grad, compressed gradient averaging with error feedback matches the convergence of full-gradient AMSGrad, and linear speedup can be obtained the distributed training. Numerical experiments are conducted to justify the theoretical findings, and demonstrate that COMP-AMS provides comparable performance with other distributed adaptive methods, and achieves similar accuracy as full precision AMSGrad with significantly reduced communication overhead. Given the simple architecture and hardware (memory) efficiency, we expect COMP-AM. shall be able to serve as a useful and conve- nient distributed adaptive optimization framework in practice.

---

Published as a conference paper at ICLR 2022
REFERENCES
Naman Agarwal, Ananda Theertha Suresh, Felix X. Yu, Sanjiy Kumar, and Brendan McMahan. cpSGD: Communication-effiicant and differentially-privatt distributed SGD. Advances in Neu- ral Information Processing Systems (NeurlPS), pp. 7575-7586, Montréal, Canada, 2018.
Ahmad Ajallocian and Sebastian U Stich. Analysis of SGD with biased gradient estimators. arXiv
preprint arXiv:2008. 00051, 2020.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the 2017 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 440-445, Copenhagen, Denmark, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD:
communicattinn-effcceett SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pp. 1709-1720, Long Beach, CA, 2017.
Dan Alistarh, Torsten Hoefter, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), pp. 5977-5987, Montréal, Canada, 2018.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas N. Diggavi. Qsparse-local-sgd: Distributed SGD with quantization, sparsification and local computations. In Advances Neural Information Processing Systems (NeurIPS), pp. 14668-14679, Vancouver, Canada, 2019.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Arizzadeneshelli and Animashree Anandkumar. SIGNSGD: compressed optimisation for non-convex problems, In Proceedings of the 35th Inter- national Conference on Machine Learning (ICML), pp. 559-568, Stockholmsmässan, Stockholm, Sweden, 2018.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, 2019.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compres- sion for distributed learning. arXiv preprint arXiv:2002.122110 2020.
Stephen P. Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 1122 1.1
Ken Chang, Niranjan Balachandar, Carson K. Lam, Darvin Yi, James M. Brown, Andrew Beers, Bruce R. Rosen, Daniel L. Rubin, and Jayashree Kalpathy-Cramer. Distributed deep learning networks among institutions for medical imaging. Am. Medical Informatics Assoc., 25(8): 945-954, 2018.
Congliang Chen, Li Shen, Hao-Zhi Huang, and Wei Liu. Quantized adam with error feedback. ACM Trans. Intell. Syst. Technol., 12(5):56:1-566:3 1-62:66, 2021a.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of A class of adam-type algorithms for non-convex optimization. In Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, 2019.
Xiangyi Chen, Xiaoyun Li, and Ping Li. Toward communication efficient adaptive gradient method. In Proceedings of the ACM-IMS Foundations of Data Science Conference (FODS), pp. 119-128, Seattle, WA, 2020.
Xiangyi Chen, Belhal Karimi, Weijie Zhao, and Ping Li. On the convergence of decentralized adaptive gradient methods. arXiv preprint a1Xiv:2109.03194, 2021b.
Trishul M. Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building efficient and scalable deep learning training system. In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 571-582, Broomfield, CO, 2014.
10

---

Published as a conference paper at ICLR 2022
Dami Choi, Christopher J Shallue, Zachary Nado, Jachoon Lee, Chris J Maddison, and George Dahl. On empirical comparisons of optimizers for deep learning. arXiv preprint arX1v:1910.05446. 2019. 2019.
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM Conference Recommender Systems, pp. 191-198, Boston, MA, 2016.
Tim Dettmers. 8-bit approximations for parallelism in deep learning. In Proceedings of the 4th International Conference on Learning Representations (ICLR), San Juan, Puerto Rico, 2016.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter the Association for Computational Linguistics: Human Language Technologies (NAACI-HLT), pp. 4171-44 -186, Minneapolis, MN, 2019.
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Proceedings of the 23rd Conference on Learning Theory (COLT), pp. 257-269, Haifa, Israel, 2010.
John C. Duchi, Alckh Agarwal, and Martin J. Wainwright, Dual averaging for distributed optimiza- tion: Convergence analysis and network scaling. IEEE Trans. Autom. Control., 57(3):592-606, 2012.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 23(4):2341 2268,, 2013.
Ian J. Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Montreal, Canada, 2014.
Information Processing Systems (NIPS), pp.
Priya Goyal, Piotr Dollár, Ross Girshick, Picter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint 17X.v:/706.0267,,22 2017.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey E. Hinton. Speech recognition with deep recurrent neural networks. In Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6645 6649, Vancouver, Canada, 2013.
Farzin Haddadpour, Belhal Karimi, Ping Li, and Xiaoyun Li. Fedsketch: Communication and private federated learning via sketching. arXiv preprint arXiv:2008.0 04975, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings the 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, Las Vegas, NV, 2016
Mingyi Hong, Davood Hajinezhad, and Ming-Min Zhao. Prox-pda: The proximal primal-dus algo- rithm for fast distributed nonconvex optimization and learning over networks. In Proceedings of the 34th International Conference Machine Learning (ICML), pp. 1529-1538, Sydney, Aus- tralia, 2017
Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, and Raman Arora. Communication-effican distributed SGD with sketching. In Advances in Neural Information Processing Systems (NeurIPS). pp. 13154-13154, Vancouver, Canada, 2019.
Jiawei Jiang, Fangcheng Fu, Tong Yang, and Bin Cui. Sketchml: Accelerating distributed machine learning with data sketches. In Proceedings of the 2018 ACM International Conference on Man- agement of Data (SIGMOD), pp. 1269-1284, Houston, TX, 2018.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2530-2541 Montréal, Canada, 2018
11

---

Published as a conference paper at ICLR 2022
Belhal Karimi, Xiaoyun Li, and Ping Li. Fed-LAMB: Layerwise and dimensionwise locally adaptive optimization algorithm. arXiv preprint arXiv:2110.00532, 2021.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 3252-3261, Long Beach, CA, 2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebas- tian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008. 03606, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Represenlutions (ICIR), San Diego, CA, 2015.
Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 3478-3487, Long Beach, CA, 2019.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science University of Toronto, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11) (1((1))2278-32222 1998.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuo- motor policies. J. Mach. Learn. Res., 17:39:1-39:40, 2016.
Yujun Lin, Song Han, Huizi Mao. Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In Proceedings of the 6th International Conference on Learning Representations (ICLR), Vancouver, Canada, 2018.
Songtao Lu, Xinwei Zhang, Haoran Sun, and Mingyi Hong. GNSD: gradient-tracking based nonconvex stochastic algorithm for decentralized optimization. In Proceedings of the 2019 IEEE Data Science Workshop (DSW), pp. 315-321, 2019.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Lunguage Technologies (NAACL-HLT), pp. 142-150, Portland, OR, 2011.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficeeee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1273- 1282, Fort Lauderdale, FL, 2017.
Hiroaki Mikami, Hisahiro Suganuma, Yoshiki Tanaka, and Yuichi Kageyama. Massively distributed SGD: Imagenet/resnet-50 training in a flash. arXiv preprint arXiv: 1.X0233, 2018.
Volodymyr Mnih, Koray Kavukcuoglu. David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 13,55602, 2013.
Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Dadam: consensus- based distributed adaptive gradient method for online optimization. arXiv preprint 190ivv1901.09)) 2019.
Angelia Nedic and Asuman E. Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Trans. Autom. Control., 54(1):48-61, 2009.
Arkadi Nemirovski, Anatoli B. Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 19(4):174-1669, 2009.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In Proceedings of the 6th International Conference on Learning Representations (ICLR), Vancouver, Canada, 2018
12

---

Published as a conference paper at ICLR 2022
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In Proceedings of the 9th International Conference Learning Representations (ICLR), Virtual Event, 2021.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2021.
Christopher De Sa, Matthew Feldman, Christopher Ré, and Kunle Olukotun. Understanding and op- timizing asynchronous low-precision stochastic gradient descent. In Proceedings of the 44th An- nual International Symposium on Computer Architecture (ISCA), pp. 561-574, Toronto, Canada, 2017.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application Bata-paralles distributed training of speech dnns. In Proceedings of the 15th Annual Conference of the International Speech Communication Association (ISCA), pp. 1058- 1062, Singapore, 2014.
Zebang Shen, Aryan Mokhtari, Tengfei Zhou, Peilin Zhao, and Hui Qian. Towards more efficient stochastic decentralized learning: Faster convergence and sparse communication. In Proceed- ings of the 35th International Conference on Machine Learning (ICML), pp. 4631-4640, Stock- holmsmässan, Stockholm, Sweden, 2018
Shaohuai Shi, Kaiyong Zhao, Qiang Wang. Zhenheng Tang, and Xiaowen Chu. A convergence anal- ysis of distributed SGD with conmuuication-ellicient gradient sparsification. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 3411-3417, Macao, China, 2019.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillierap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Master- ing the game of go without human knowledge. Nat., 550(7676):354-355 2017.
Sebastian U Stich and Sai Praneeth Karimireddy. The frror-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv: 190.00000 2019.
Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS), pp. 4447-4458, Montréal, Canada, 2018
Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Ji Liu, Ce Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale training with adam's convergence speed. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 10118-10129 Virtual Event, 2021.
Jun-Kun Wang, Xiaoyun Li, Belhal Karimi, and Ping Li. An optimistic acceleration of amsgrad for nonconvex optimization. In Proceedings of Asian Conference on Machine Learning (ACML), volume 157, pp. 422-437, Virtual Event, 2021.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang, Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1399-1309, Montréal, Canada, 2018
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Tergrad: Temnry gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems (NIPS), pp. 1509-1519, Long Beach, CA, 2017.
Jiaxiang WU, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. In Proceedings of the 35th Interna- tional Conference on Machine Learning (ICML), pp. 13219932,, Stuckholmsmässan, Stockholm, Sweden, 2018
13

---

Published as a conference paper at ICLR 2022
Zhiqiang Xu, Dong Li, Weijie Zhao, Xing Shen, Tianbo Huang, Xiaoyun Li, and Ping Li. Agile and accurate CTR prediction model training for massive-scale online advertising systems. In Proceedings of the International Conference Management of Data (SIGMOD), pp. 2404-2409, Virtual Event, China, 2021.
Guandao Yang. Tianyi Zhang, Polina Kirichenko, Junwen Bai, Andrew Gordon Wilson, and Christo- pher De Sa. SWALP: Stochastic weight averaging in low precision training. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 7015-7024, Long Beach, CA, 2019.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsich. Large batch optimization for deep learning: Training BERT in 76 minutes. Proceedings of the 8th International Conference on Learning Representations (ICLR), Addis Ababa, Ethiopia, 2020.
Tom Young, Devamanyu Hazarika, Soujanya Poria, and Erik Cambria. Recent trends in deep learn- ing based natural language processing. IEEE Comput. Intell. Mag., 13(3):55-755 2018.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient mo- mentum SGD for distributed non-convex optimization. Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 7184-7193, Long Beach, CA, 2019a.
Yue Yu, Jiaxiang Wu, and Junzhou Huang. Exploring fast and communication-efficii algorithms in large-scale distributed networks. In Proceedings of the 22nd International Conference on Arti- ficial Intelligence and Statistics (AISTATS), pp. 674-683, Naha, Okinawa, Japan, 2019b.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5700. 2012.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipMI:: Training linear models with end-to-end low precision, and a little bit of deep learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 4035-4043, Sydney, Australia, 2017.
Lei Zhang, Shuai Wang, and Bing Liu. Deep learning for sentiment analysis: survey. Wiley Interdiscip. Rev. Data Min. Knowl. Discov, 8(4), 2018.
Tianyi Zhang, Felix Wu, Arzoo Katiyar, Kilian Q. Weinberger, and Yoav Artzi. Revisiting few- sample BERT fine-tuning. In Proceedings of the 9th International Conference on Learning Rep- resentations (ICLR), Virtual Event, 2021.
Weijie Zhao, Jingyuan Zhang. Deping Xie, Yulei Qian, Ronglai Jia, and Ping Li. AlBox: CTR pre- diction model training on single node. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM), pp. 319-328, Beijing, China, 2019.
Weijie Zhao, Xuewu Jiao, Mingqing Hu, Xiaoyun Li, Xiangyu Zhang, and Ping Li. Communication- efficient terabyte-scale model training framework for online advertising. arXiv preprint arXiv:2201.05500, 2022.
Shuai Zheng, Ziyue Huang, and James T. Kwok. Communication-effiienn distributed blockwise momentum SGD with error-feedback. In Advances in Neural Information Processing Systems (NeurIPS), pp. 11446-11456. Vancouver, Canada, 2019.
Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint 1e08v:1808.050 05671, 2018.
Yingxue Zhou, Belhal Karimi, Jinxing Yu, Zhiqiang Xu, and Ping Li. Towards better generalization of adaptive gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
14

---

Published as a conference paper at ICLR 2022
A TUNING DETAILS AND MORE RESULTS ON RESNET-18
The search grids of the learning rate of each method can be found in Table 1. Empirically, Dist- AMS, COMP-AMS and IBitAdam has similar optimal learning rate, while QAdam usually needs larger step size to reach its best performance.
Table 1: Search grids for learning rate tuning.
Learning rate range
Dist-AMS
0.00001, O. 00003, O. 0.00005, O. 0.0001, 0.0003, 0.0005, 0.001, 0.003, 0.005, 0.01
Comp- 1Mmp-AMS
0.00001,, 0.00003, O. 0.00005, 0.0001, 0.0003, 0.0005, 0.001, 0.003, 0.005, 0.01]
QAdam
[0.0001, O. 0.0003, 0.0005, 0,001, 0.003, 0.005, 0.01, 0.03, 0.05, 0.1, 0.3, 0.5)
IBitAdam
0.00001, 0.00003, 0. 0.00005, O. 0.0001, 0.0003, 0.0005, 0.001, 0.003, 0.005, 0.01]
We provide more experimental results CIFAR-10 dataset, trained with ResNet-18 18 (He et al., 2016). For reference, we also present the result of distributed SGD. As we can see from Figure 4, again COMP-AMS can achieve similar accuracy as AMSGrad, and the Top-k compressor gives the best accuracy, with substantial communication reduction. Note that distributed SGD converges faster than adaptive methods. but the generalization error slightly worse. This experiment again confirms that COMP-AMS can serve as simple and convenient distributed adaptive training framework with fast convergence, reduced communication and little performance drop.
1.5
100
100
Cist AMS
COMP-AMS-Toppe
CIFAR
COMP-AMS-EKSSp
Test Accuracy
Test Accuracy
QAdam
Dist SGD
CIFAR
Train
60
Dist AMS
-Clst-MS AMS
0.5
CIFAR
60
COMP-AMS-Teal
COMP Tapk
COMP-ANS -kSign
COMP-AMS-BASgn
QAzam
Dist SGD
Dist SGD
0
50 Epochs
75
100
25
50
75
100
30
35
45
Epochs
log(No. bits)
Figure 4: Training loss and test accuracy of different distributed training methods on CIFAR-10 with
ResNet- 18 (He et al., 2016).
15

---

Published as a conference paper at ICLR 2022
B PROOF OF CONVERGENCE RESULTS
In this section, we provide the proof of our main result.
B.1 PROOF OF THEOREM 1
Theorem. Denote Co V (1-9)'
41t G2 + + = 0r + 1--2. Under Assumption I to Assump- 1-9,
tion 4, with T/: = 1j S 3CD / (2x
> for any T> 0, COMP-AMS satisfies
B)f(0s) f(
nyOL² ne
3112 LCOC90
B [[())) 200
2C1(
T7
ne2
(1+ TVE
n 201)C,
(1 91-02)226
Te
Proof. We first clarify some notations. At time t. let the full-precision gradient of the i-th worker be 9t.s. the error accumulator be Ct,i, and the compressed gradient be J., = C(g..s + et,i). Slightly different from the notations in the algorithm, we denote Dt = A/2 E It.i Dz = Σi= It. and
& 1. Em=1 Er,i. The second moment computed by the compressed gradients is denoted as 12- 2
820-1 + (1 (2)ge: and 0g = max( 0t). Also, the first order moving average sequence
m, m, (1 B,)3; and mi 3, m (1 3,)
where my represents the first moment moving average sequence using the uncompressed stochastic gradients. By construction we have my = (1 31) Σt 87 gr.
Our proof will use the following auxiliary sequences,
E+1 = (1 (1- -1)) Σ a
E1+1
4/0 = 01+1 1) Vū, +
Then, can write the evolution of 0, as
E1+1
0 0(+1 - Vūz +E
0, (1 B1) E1
B - 9, + (1 311 1 g-+1-1
--
CT
Vor +
B1) E1= 87- 0 + (++1) (1 -1888a8
0 11
V0 +e
(1 31) -=1
BTTer Cr
m/
0 1
VoL +e
V0z +
E,
mf
0
1)
17{
Vox + E
Vo-++ +E
Vor+ +
10-11
+
m4
1
1
+ m1(
E
00r +e
/0-1+c
Vo+te
m
8
+ n,DE
0, +
where (a) uses the fact that for every E [m]. Ht,5 + e441, St. + Cr and 6x,1 0 at initialization. Further define the virtual iterates:
31
m
F++1 == 8,41
-11 11 81
0z +
16

---

Published as a conference paper at ICLR 2022
which follows the recurrence:
81
m4
14+1 0/41 11 - B1 V i1 +
B1
mf
8
7) 11 +
"1 1 1-33 31 V +
+ t
32
Bim/-1 + +(1 - B1)g: + I-3,
m4-1 + B10t
8 7
+ n,D
Vūe +E
8 1)
31
$1 Vū. +
m4-1
11
Vū, +
9t.
+ n,D
3t
1)
9t
+ "
B1
Dem'u1 + n,DE
01 +
31
When summing over / = 1,.,. T, the difference sequence D, satisfies the bounds of Lemma 5.
By the smoothness Assumption 2, we have
L [z++1) S f(x)) + (Vf(2)), - x1) + 11 - xell?
Taking expectation w.r.t. the randomness time obtain [[ - f(x)
gt )]
81
-n
Dom + DrEi))
Vū,
B1
+
17
L
B|ll
9t
B1
Dymm - -
2
Vūr +E
1-
--BB(V)(0.)
9t
+
mE (x+1,
B1
Demi-1 DrEi)l
V0 +
B1
1
g:
B1
9t
E|I
Demi_1 DrEa +BkK(((0))) - (.x)),
2
Vū
1- B1
Vo,
111
(3)
In the following, we bound the terms separately. Bounding term I. We have
-= E KV ((:),
St
- nE (V(())()))))
1
1
+
Vo,
Vūr-ite
(0,).)
(VS(((
+ 1 DiIl
E (f()) + [.llbl
(4)
40 (1- G +e
where we use Assumption 3, Lemma and the fact that l2 norm is no larger than 4 norm.
Bounding term II. By the definition of &,, know that ||ε&|| || I (1
B1) Et Et (
s
I-qx G. Then we have
31 Dem4_ + D.E,) (V((()))) - vf(O),
B
1I < (B(()())) I
Dem4_1 + DrE,))
I 31
1- 31
31
m/ + E,
31
< +
Dem'_ + D.E, + + LE
||||
Dem + D
3,
//-11 +
1-
R2ORLG2
< D.
El|l
D.]li,,
(5)
Ve
17

---

Published as a conference paper at ICLR 2022
where C1
8,
24 The second inequality is because of smoothness of f()), and the last
I-91
1-g2.
inequality is due to Lemma 2, Assumption 3 and the property of norms.
Bounding term 111. This term can bounded as follows:
31
TIT S 1² [E|[
1 + 1/ [1
Dam4-1 1rE
B1
1
n
B1 31 Me,i - ((())) + V.( + (
Bill
m
Ex)11
(0) 1 BIIV f(0)) Lo + L
(6)
where (a) follows from ( = 1 E ((,(0,)) and Assumption 4 that Drs is unbiased of ((() and has bounded variance o².
Bounding term IV. We have
VV (() V)(x)),
9t
) + + - V)(e)), (
Voe+c V + )b))
Vo.-1 +
v.((.))
1-31 m4-1 +
91
< < Vf(a)),
1) LE[I
|||
f0-1 +e
V +E
C
"P EEIV
"
B1IV f(0.) [xx)1)]]
2e
2p
Ve
m/ + & Vo-++
C2 BiI
"P EEI]V +
Bll
1-
117t
2E
2p
Ve
where (a) due to Young's ss inequality and (b) is based on Assumption 2.
Regarding the second term in (7), by Lemma 3 and Lemma 1, summing over /. 1,..., T we have
T
81 91 + & ||
m
2p
01-1
+E
T
L
B1
Eil
m/-1 + Edl1
2pe
B1
1=1
L
B7
Elll
PE
(1-
t=1
T
BLL
+
E [(
up(1
P(
- 2.
p(1 22)2 (0² 02+0') + 4n7'g2 L M( 92)
B
(()))
LC202
2 Lo
17 LC2
(
(8)
npe
p(1 22
pe
with C2 = 1I- +
(1- Now integrating (4), (5), (6), (7) and (8) into (3), taking the tele-
2g²
scoping summation over ..., T. we obtain
E[f(oT+1) - f((1)]
77 +
L
np
+
1 LC
T Σ
E B
Top
Trp
4T Lo
Co
2e
pe
npe
p(1 2()-
1=1
P(1+G))CGG
T
(((11 + C +
B|l + CfLG
El E|||D,
Ve
18

---

Published as a conference paper at ICLR 2022
with Co == /
401 9 (1 q2y
G + Setting S
and choosing p 30 we further
3Co 22x (2.,,,
arrive at
B[ ((()))
T
Lo²
12TT)" LC
S 7
Σ /
2Co
ne2
(1 12222
(11 +
+ 2
Ve
where the inequality follows from Lemma 5, Re-arranging terms, get that
Blf(z1) f(pr-1))
nLo?
3n 3 LCo2202
Σ [[ 2Co(
T
Tn
nE
nE²
(1+C))G2d n(1
201)C
+ (1 q2)222
TVE
Te
[() f(0r)
+ nnI +
s 2C0
Tn
ne
ne²
12n rp LC
n1(1 + 20, (1+ TVe
+ (1 92)2
Te
where Co
41 11-921- G c, C1 1-8 + 24 The last inequality is because 21
1-gz.
o1
0 == arg ming (0) and the fact that C2 < Cf. This completes the proof.
B.2 INTERMEDIATE LEMMATA
The lemmas used in the proof of Theorem are given as below.
Lemma 1. Under Assumption to Assumption 4 we have:
mlll
S G, Vt.
To²
T
Σ
ml 2
+
E
Proof. For the first part, is easy to see that by Assumption 3,
|m&|l (1 B1)1 Σ T S.
For the second claim, the expected squared norm of average stochastic gradient can be bounded by
||1ا
Ell Σ
91,e v (f.))
1=1
Ei]l
(gr.s
+
1=1
+
19

---

Published as a conference paper at ICLR 2022
where Assumption 4 that It.; is unbiased with bounded variance. Let It.j denote the j-th coordinate of 9r. By the updating rule of COMP-AMS we have
E m||
E11((1 B1)
81
11
T=1
d S (1- 31)
E
)
j=1
(1 - 8,)² Σ E
Σ -
<1 - B1) Σ B
T=1
+ (1- B1) Σ o
T=1
where (a) is due to
inequality. Summing
1,.... T, obtain
To²
T
E mm S
+Σ
E
This completes the proof.
Lemma 2. Under Assumption 4, we have for VL. and each local worker Vi E [n].
4q²
||e,,il? $ (1 - 22)2 G², G²,
4q²
20²
+ d )
Bllle+1, S (1 - q2)
0²
1 q²
2
Proof. We start by using Assumption and Young's inequality to get
||e+1,<||2 = ll + et, - -C(gt, + ex,:)l?
S 12ll + el,
S (1 p))lle,,i12
+ + 11
< 1 q²
2q²
I- q² 11
where (9) is derived by choosing p = 1-9² 24
and the fact that < 1. Now by recursion and the
initialization e1,; = O, we have
Blllet1,,
2q
Σ
1
92
q²
2
4q²
2q
+ d
Σ
22)2
q2 r=1
2
which proves the second argument. Meanwhile, the absolute bound ||ea,,l1 directly from (9).
4g² (1-
G follows
Lemma 3. For the moving average error sequence E,, it holds that
T
4Tq²
4q
T
Σ
1
< (1 (1- qo
-1-
(02 + +oz) +
Σ
20

---

Published as a conference paper at ICLR 2022
(f( Using the same technique as in the proof of Lemma 1, denoting Et,j as the j-th coordinate of ét, it follows that
( Proof. Denote K Σr=1(
E||l, |2] = [Il - B1) Σ
d
(1- 31)²
EI
B
E
})
J=1
T=1
(0)
S (1 - 81)²
j=1
S (1 - 31) B|
S <1 B1) Σ 81 3
||e,,111
17
(4)
(1 q2)2 27 (1)
49 2
1 n
Σ
Kr,);
(1 ( q²)
n
where (a) is due to and using the technique of geometric series summation leads to
and (b) is a result of Lemma 2. Summing over = 1,...? T
T
2
21 - 31)
Blll&
K
(1 22)2
1=1==1
2
20²
< 0² +
E
[+(00)1113]
(1 92)2
(1-
2
t=1
4T
4q²
T
+
E
(1 2)
(1 11-9- 92)
1
(a)
4T
4g²
T
1 Σ IVS((0)) - (
+
E
(1 222
(1 (1-92) q2)²
4
4q
T
0g) +
E
22)
where (a) is derived by the variance decomposition and the last inequality holds due to Assumption 4. The desired result is obtained.
Lemma 4. It holds that Vt E [T), Vi [d], dz. S (1- G².
21
Proof. For any 1, by Lemma 2 and Assumption 3 we have |[[( + ell < [[C(g: + et) (g: + et) + (ge + +
| 2
S 2(g² + +1)lla+ + ell
49²
$ 34g2 + 1)( + (1 - 922 G9)
4(1 + 92) G2.
(1 q2)2
It's then easy show by the updating rule of êt, there exists j [4] such that ú. Uj. Then
4(1 + )3) G²
02.5 (1 1--3a (B2) 1=1
3 gr. -
(1 22)²
21

---

Published as a conference paper at ICLR 2022
which concludes the claim.
Lemma 5. Let D2 =
be defined as above. Then,
Vee-ite
Vhi+e
d 1=1 Ve'
T
d
Dilla
S
Σ
D
1=1
Proof. By the updating rule of COMP-AMS, iz-1 S it for Vt. Therefore, by the initialization 8g O, we have
D +0
VoL.t +c
d
00,i +
Vor,ite
V
For the sum of squared le norm, note the fact that for a 2 b > 0, it holds that
(a (a s (a b) = a² - b².
Thus,
T
T d
1 =
00-11+
Voss +
t=1 i=1
1
01 +
t=1
d
which gives the desired result.
22


Reviews:
[{"review_id": "uRCA2qPuG06", "reviewer": "Reviewer_ou6Y", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths\n- The topic considering communication efficiency for adaptive distributed optimization is of timeliness and importance.\n- Theoretical results look promising and the numeral results efficiently supports the validity of the theoretical results in practice.\n- The paper is well-organized and contains the introduction of related studies with a fairly enough coverage. \n\nWeaknesses:\nMinor comments\n- Is there any systematic ways to choose the parameters $\\beta_1, \\beta_2, \\epsilon$ in the proposed algorithm (Algorithm 2)?\n- Page 4, \"In Section 4 & 5\" --> \"In Sections 4 and 5\"\n- How do we define the \"data heterogeneity\" in page 2? Does this mean different $\\chi_i$ on each local node? It would be better if the authors could clearly state this.\n- Page 6, \"under Assumption 1 to Assumption 4\" --> \"under Assumptions 1 to 4\"\n", "summary_of_the_paper": "This paper suggests a gradient averaging strategy for distributed adaptive optimization. Gradient compression is used for reducing the communication costs in transmission of gradients, and the tool of error feedback is used for correcting bias injected by the compression step. Convergence analysis results demonstrates that the proposed strategy has a linear speedup as the number of workers increases while the same convergence rate as standard AMSGrad. The experimental results on real-world datasets successfully validate the theoretical results.", "summary_of_the_review": "Overall, I believe that this paper could be a meaningful add to the theories behind the distributed optimization. Numerical results also look solid enough to support the theoretical results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oOBBlDcioD", "reviewer": "Reviewer_7SPd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strength:\nThe authors extend the adaptive optimization framework to distributed approach with a compressed gradient averaging. The convergence analysis implies a linear speedup in terms of the number of workers, and shows that in the single-machine case, it can achieve the same convergence rate as the standard full-gradient SGD. The paper is well-written and easy to follow.\n\nWeakness:\nI have some concerns as follows.\n1. The authors do not assume the finite-sum of $f_i(\\theta)$ to be convex, then how to avoid converging to a local optimal? \n2. If data heterogeneity exists for local workers, is it possible that the local gradient may drag others back when taking the gradient averaging in the central server?\n3. In Algorithm 2, how to determine parameters $\\beta_1, \\beta_2$ and $k$? Is it possible that $k$ differs for different local workers?\n4. In the algorithm, when applying EF technique to reduce the bias, each local worker still needs extra storage for the error term $e_t$, which is the same dimension as the local gradient. Why such an approach can be efficient in terms of the memory space when training large-scale learners?\n5. In the experiments, how many workers are considered? Since data samples are randomly assigned to the workers, it can be regarded as the non-data heterogeneous case, it could be better if the authors can add the results for cases with data heterogeneity, e.g., workers with different sample sizes/ different class distributions.\n6. There seem to be some typos. For example, in algorithm 1, line 8, I suppose the numerator should be $m_t$ instead of $\\theta_t$; in theorem 1, corollary 1 and 2, what is $C_2$ in the denominator of the constrain for $\\eta$? \n\n", "summary_of_the_paper": "The authors propose the COMP-AMS algorithm for a distributed optimization framework. The algorithm is based on gradient averaging and adaptive algorithms. The application of gradient compression helps to reduce the communication complexity, and the tool of error feedback is used for the bias correction. The authors study the convergence rate of the proposed algorithm. The theoretical results are justified by the numerical experiments.", "summary_of_the_review": "I believe the paper has its value in extending the adaptive optimization framework to distributed approach with compressed gradient averaging. I mainly have concerns about the assumption on convexity and the impact on the performance brought by data heterogeneity.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MRQE5Zhxh2c", "reviewer": "Reviewer_c4KT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "Major strengths are listed as follows:\n(1) The paper is easy to follow and provides sufficient background on compressed gradients and adaptive optimization. Comparisons with two related works are important and clear. \n(2) The proposed error-feedback strategy is interesting in the distributed optimization scenario. \n(3) Empirical results on some benchmark data sets are supportive and convincing. \n\nIn addition, there are several minor issues that the authors could address to improve the clarity and quality of the paper:\n1. In Sec 2.2, it seems there is no problem description for Algorithm 1, which may cause confusion for first-time readers. The paragraph in the beginning of Sec 3 could be moved here or even before Sec 2.2. Also, the parameter space could be explained or detailed with an example. \n2. In Sec 2.2., \"different learning rate\"->\"different learning rates\", \"element-wisely\"->\"elementwise\", \"previous gradient magnitude\"->\"previous gradient magnitudes\".\n3. In Definition 2, $sign(x_{\\mathcal{B}_1})$ is not defined. \n4. In Theorem 1, \"Under Algorithm 1 to Algorithm 4\" -> \"Under Algorithms 1-4\".", "summary_of_the_paper": "The paper proposes a new distributed optimization framework-COMP-AMS-based on gradient averaging and compression with convergence guarantee. In particular, theoretical discussions have shown that the proposed algorithm shares the same convergence rate as AMSGrad with linear speedup effect. Numerical experiments on several real-world data sets have demonstrated the proposed method can significantly reduce the communication costs while reaching comparable performance with full-precision AMSGrad.", "summary_of_the_review": "Overall, the proposed work is important and interesting, and the paper deserves publication. The compressed gradient averaging technique with error feedback and its related convergence discussions could shed lights on other related works. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the setting of distributed optimization and proposes an adaptive gradient averaging and compression scheme to reduce the communication cost. The proposed scheme is shown to achieve the same convergence rate as full-gradient AMSGrad algorithm, but due to the reduced cost, it exhibits linear speedup as the number of workers grows.

The reviews appreciated the clear presentation of the results, technical soundness, and convincing numerical experiments. The paper is a solid contribution to distributed optimization. Thus, I recommend acceptance.
Decision: Accept (Poster)