Year: 2021

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

heading: 1 INTRODUCTION
text: Deep neural network has achieved the state-of-the-art learning performance on numerous AI applications, e.g., computer vision (Goodfellow et al., 2014; He et al., 2016; Voulodimos et al., 2018), Natural Language Processing (Graves et al., 2013; Young et al., 2018; Zhang et al., 2018), Reinforcement Learning (Mnih et al., 2013; Silver et al., 2017) and recommendation systems (Covington et al., 2016; Wei et al., 2017). With the increasing sheet size of data observations 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 a long time — training is too slow. Many real-world applications can not even afford spending that much time on training.
• In many scenarios, data are stored in multiple servers, possibly at different locations, due to the storage constraints (massive user behavior data, Internet images, etc.) or privacy reasons (Chang et al., 2018). Hence, transmitting data among servers might be costly.
Distributed learning framework (Dean et al., 2012) has been a common training strategy to tackle the above two issues. Consider the distributed optimization task where n workers jointly solve a large finite-sum optimization problem in the form of
min θ f(θ) := min θ
1
n n∑ i=1 fi(θ) = 1 n n∑ i=1 Ex∼Xi [Fi(θ;x)], (1)
where the non-convex function fi represents the average loss over the local data samples for worker i ∈ [n], and θ ∈ Rd the global model parameter. Xi 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 (Xi’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 local nodes for subsequent gradient computation. The scenario where Xi’s are different gives rise to the recently proposed Federated Learning (FL) (McMahan et al., 2017) framework, which would not be the major focus of this work. As we 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 no 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 (Boyd et al., 2011; Nedic & Ozdaglar, 2009; Duchi et al., 2011; Goyal et al., 2017; Hong et al., 2017; Lu et al., 2019; Koloskova et al., 2019).
Gradient compression. Among many optimization strategies, SGD is still the most popular prototype in distributed training for its simplicity and effectiveness (Chilimbi et al., 2014; Agarwal et al., 2018; Mikami et al., 2018). Yet, when the deep learning model is very large, the communication between 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 on quantization, sparsification and other compression techniques of the local gradients are proposed, e.g., Alistarh et al. (2017); Wen et al. (2017); Wangni et al. (2018); Stich et al. (2018); Aji & Heafield (2017); Bernstein et al. (2018); De Sa et al. (2017); Yang et al. (2019); Ivkin et al. (2019). However, it has been observed both theoretically and empirically (Stich et al., 2018; Ajalloeian & 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 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, 2014) 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. However, 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 performance of standard SGD, one natural question is: is it also true for adaptive methods? In this work, we try to fill this gap formally, by analyzing COMP-AMS, a distributed adaptive optimization framework using the gradient averaging protocol, with communication-efficient gradient compression.
Our contributions. In this work, we study a simple algorithm design leveraging the adaptivity of AMSGrad and the computational virtue of local gradient compression. Our main contributions summarize as follows:
• We consider COMP-AMS, a synchronous distributed adaptive optimization framework based on global averaging with gradient compression, which is efficient in both communication and memory as no local moment estimation is needed. We consider the BlockSign and Top-k compressors, coupled with the error-feedback technique to compensate for the bias implied by the compression step for fast convergence.
• We provide the convergence analysis of distributed COMP-AMS (with n workers) in smooth non-convex optimization. In the special case of n = 1 (single machine), similar to SGD, gradient compression with error feedback in adaptive method achieves same convergence rateO( 1√
T ) as the standard full-gradient counterpart. Also, we show that with
a properly chosen learning rate, COMP-AMS achieves O( 1√ nT ) convergence, implying a linear speedup in terms of the number of local workers to attain O(δ)-stationary point.
• 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 matches the accuracy of full-precision AMSGrad with substantially reduced communication cost. Thus, it can serve as a convenient distributed training strategy in practice.

heading: 2 RELATED WORK

heading: 2.1 DISTRIBUTED SGD WITH COMPRESSED GRADIENTS
text: Quantization. As we mentioned before, SGD is the most commonly adopted optimization method in distributed training of deep neural nets. To reduce the expensive communication in large-scale distributed systems, extensive works have considered various compression techniques applied to the gradient transaction procedure. The first strategy is quantization. Dettmers (2016) condenses 32-bit floating numbers into 8-bits when representing the gradients. Seide et al. (2014); Bernstein et al. (2018); Karimireddy et al. (2019); Bernstein et al. (2019) use the extreme 1-bit information (sign) of the gradients, combined with tricks like momentum, majority vote and memory. Other quantization-based methods include QSGD (Alistarh et al., 2017; Wu et al., 2018; Zhang et al., 2017) and LPC-SVRG (Yu et al., 2019b), leveraging unbiased stochastic quantization. The saving in communication of quantization methods is moderate: for example, 8-bit quantization reduces the cost to 25% (compared with 32-bit full-precision). Even in the extreme 1-bit case, the largest compression ratio is around 1/32 ≈ 3.1%. Sparsification. Gradient sparsification is another popular solution which may provide higher compression rate. Instead of commuting the full gradient, each local worker only passes a few coordinates to the central server and zeros out the others. Thus, we can more freely choose higher compression ratio (e.g., 1%, 0.1%), still achieving impressive performance in many applications (Lin et al., 2018). Stochastic sparsification methods, including uniform and magnitude based sampling (Wangni et 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 k elements with largest magnitude), Deep Gradient Compression (Lin et al., 2018), but usually lead to biased gradient estimation. In Ivkin et al. (2019), the central server identifies heavy-hitters from the count-sketch (Charikar et al., 2002) of the local gradients, which can be regarded as a noisy variant of Top-k strategy. More applications and analysis of compressed distributed SGD can be found in Jiang & Agrawal (2018); Shen et al. (2018); Alistarh et al. (2018); Basu et al. (2019); Jiang et al. (2018), among others.
Error Feedback (EF). Biased gradient estimation, which is a consequence of many aforementioned methods (e.g., signSGD, Top-k), undermines the model training, both theoretically and empirically, with slower convergence and worse generalization (Ajalloeian & 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); Karimireddy et al. (2019) prove theO( 1T ) andO( 1√ T
) 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 works on the convergence rate of SGD with error feedback include (Zheng et al., 2019; Stich & Karimireddy, 2019), among other related papers.

heading: 2.2 ADAPTIVE OPTIMIZATION
text: In each SGD update, all the gradient coordinates share the same learning rate. This latter is either constant or decreasing through the iterations. Adaptive optimization methods cast different learning rates on each dimension. For instance, AdaGrad, developed in Duchi et al. (2010), divides the
Algorithm 1 AMSGRAD 1: Input: parameters β1, β2, , learning rate ηt 2: Initialize: θ1 ∈ Rd, m0 = 0 ∈ Rd, v0 = 0 ∈ Rd 3: for t = 1, . . . , T do 4: Compute stochastic gradient gt at θt 5: mt = β1mt−1 + (1− β1)gt 6: vt = β2vt−1 + (1− β2)g2t 7: v̂t = max(v̂t−1, vt) 8: θt+1 = θt − ηt mt√v̂t+ 9: end for
gradient elementwise by √∑T
t=1 g 2 t ∈ Rd, where gt ∈ Rd 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 magnitudes tend to move a larger step via larger learning rate. Other adaptive methods include AdaDelta (Zeiler, 2012) and Adam (Kingma & Ba, 2014), which introduce momentum and moving average of second moment estimation into AdaGrad hence leading to better performances. AMSGrad (Reddi et al., 2018), and potential improvements as in Wang et al. (2019), fix the potential convergence issue of Adam. In this paper, we will use AMSGRAD as the prototype, which is summarized in Algorithm 1.
In general, adaptive optimization methods in many cases exhibit faster convergence than SGD. Thus, they have been widely used in training deep learning models in language and computer vision applications, e.g., Choi et al. (2019); You et al. (2020); Zhang et al. (2020). In distributed setting, Nazari et al. (2019) proposes a decentralized system in online optimization, but communication efficiency is not considered. Mostly relevant to our work, Chen et al. (2020) proposed 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. We will present more detailed comparisons to these works in Section 3.

heading: 3 COMMUNICATION-EFFICIENT ADAPTIVE OPTIMIZATION

heading: 3.1 GRADIENT COMPRESSORS
text: In this paper, we mainly consider deterministic q-deviate compressors defined as below.
Assumption 1. The gradient compressor C : Rd 7→ Rd is q-deviate: for ∀x ∈ Rd, ∃ 0 ≤ q < 1 such that ‖C(x)− x‖ ≤ q ‖x‖.
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 x ∈ Rd, denote S as the size-k set of i ∈ [d] with largest k magnitude |xi|. The Top-k compressor is defined as C(x)i = xi, if i ∈ S; C(x)i = 0 otherwise. Definition 2 (Block-Sign). For x ∈ Rd, define M blocks indexed by Bi, i = 1, ...,M , with di := |Bi|. The Block-Sign compressor is defined as C(x) = [sign(xB1) ‖xB1‖1 d1 , ..., sign(xBM ) ‖xBM ‖1 dM
], where xBi is the sub-vector of x at indices Bi. Remark 1. It is well-known (Stich et al., 2018) that for Top-k, q2 = 1 − kd . For Block-Sign, by Cauchy-Schwartz inequality we have q2 = 1 − mini∈[M ] 1di where M and di 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 in different blocks, which, for neural nets, are usually set as the distinct network layers. The scaling factor in Definition 2 is to preserve the (possibly very different) gradient magnitude in each layer. In principle, Top-k would perform the best when the gradient is effectively sparse, while Block-Sign compressor is favorable by nature when most gradients have similar magnitude within each layer.

heading: 3.2 COMP-AMS: DISTRIBUTED ADAPTIVE TRAINING BY GRADIENT AGGREGATION
text: We present in Algorithm 2 the proposed communication-efficient distributed adaptive method in this paper, COMP-AMS. This framework can be regarded as an 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, line 7-8 depict the error feedback
Algorithm 2 Distributed COMP-AMS with error-feedback 1: Input: parameters β1, β2, , learning rate ηt 2: Initialize: central server parameter θ1 ∈ Rd ⊆ Rd; e1,i = 0 the error accumulator for each
worker; m0 = 0, v0 = 0, v̂0 = 0 3: for t = 1, . . . , T do 4: parallel for worker i ∈ [n] do: 5: Receive model parameter θt from central server 6: Compute stochastic gradient gt,i at θt 7: Compute g̃t,i = C(gt,i + et,i, k) 8: Update the error et+1,i = et,i + gt,i − g̃t,i 9: Send g̃t,i back to central server
10: end parallel 11: Central server do: 12: ḡt = 1 n ∑n i=1 g̃t,i 13: mt = β1mt−1 + (1− β1)ḡt 14: vt = β2vt−1 + (1− β2)ḡ2t 15: v̂t = max(vt, v̂t−1) 16: Update the global model θt+1 = θt − ηt mt√v̂t+ 17: end for
operation at local nodes. et,i is the accumulated error from gradient compression on the i-th worker up to time t − 1. This residual is added back to gt,i to get the “corrected” gradient. In Section 4 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.
Comparison with related methods. Next, we discuss the differences between COMP-AMS and two recently proposed methods also trying to solve the distributed adaptive optimization problem. Note that, the first important difference is that these two methods both are based on the Adam optimizer, while we use AMSGrad as the prototype.
• Comparison with Chen et al. (2020). Chen et al. (2020) develops a quantized variant of Adam (Kingma & Ba, 2014), called “QAdam”. In this method, each worker keeps a local copy of the moment estimates, commonly noted m and v, and compresses and transmits the ratio mv as a whole to the server. Thus, that method is very much like the compressed distributed SGD, with the exception that the ratio mv plays the role of the gradient vector g communication-wise. Thus, two local moment estimators are additionally required, which have same size as the deep learning model. In our COMP-AMS, the moment estimates m and v 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 of memory (space), which is feasible when training large-scale learners like BERT and CTR prediction models, e.g. Devlin et al. (2019); Zhao et al. (2020), to lower the hardware consumption happening in practice.
• Comparison with Tang et al. (2021) The recent work (Tang et al., 2021) proposes “1BitAdam”. They first run some warm-up training steps using standard Adam, and then store the second moment moving average v. Then, distributed Adam training starts with v frozen. Thus, 1BitAdam is actually more like a distributed momentum SGD with some pre-conditioned coordinate-wise 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, as no pre-training is needed. Also, 1BitAdam requires extra tensors for m locally, while COMP-AMS does not need additional local memory.

heading: 4 CONVERGENCE ANALYSIS
text: For the convergence analysis of COMP-AMS we will make following additional assumptions.
Assumption 2. (Smoothness) For ∀i ∈ [n], fi is L-smooth: ‖∇fi(θ)−∇fi(ϑ)‖ ≤ L ‖θ − ϑ‖.
Assumption 3. (Unbiased and bounded stochastic gradient) For ∀t > 0, ∀i ∈ [n], the stochastic gradient is unbiased and uniformly bounded: E[gt,i] = ∇fi(θt) and ‖gt,i‖ ≤ G. Assumption 4. (Bounded variance) For ∀t > 0, ∀i ∈ [n]: (i) the local variance of the stochastic gradient is bounded: E[‖gt,i − ∇fi(θt)‖2] < σ2; (ii) the global variance is bounded by 1 n ∑n i=1 ‖∇fi(θt)−∇f(θt)‖2 ≤ σ2g .
In Assumption 3, the uniform bound on the stochastic gradient is common in the convergence analysis of adaptive methods, e.g., Reddi et al. (2018); Zhou et al. (2018); Chen et al. (2019). The global variance bound σ2g in Assumption 4 characterizes the difference among local objective functions, which, is mainly caused by different local data distribution Xi in (1). In classical distributed setting where all the workers can access the same dataset and local data are assigned randomly, σ2g ≡ 0. While typical federated learning (FL) setting with σ2g > 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. Theorem 1. Denote C0 = √ 4(1+q2)3
(1−q2)2 G 2 + , C1 = β11−β1 + 2q 1−q2 , θ ∗ = arg min f(θ) defined as (1). Under Assumption 1 to 4, with ηt = η ≤
3C0 √ 2Lmax{2L,C1} , Algorithm 2 satisfies
1
T T∑ t=1 E[‖∇f(θt)‖2] ≤ 2C0 (E[f(θ1)− f(θ∗)] Tη + ηLσ2 n + 3η2LC0C 2 1σ 2 n 2
+ 12η2q2LC0σ 2 g
(1− q2)2 2 +
(1 + C1)G 2d
T √
+ η(1 + 2C1)C1LG
2d
T
) .
The LHS of Theorem 1 is the expected squared norm of the gradient from a uniformly chosen iterate t ∈ [T ], which is a common convergence measure in non-convex optimization. From Theorem 1, we see that the more compression we apply to the gradient vectors (i.e., larger q), 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 n = 1 naturally reduces to the single-machine (sequential) AMSGrad (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 a similar result. Corollary 1. When n = 1, under Assumption 1 to 4, setting the stepsize as η = min{
3C0 √ 2Lmax{2L,C1} , 1√ T }, Algorithm 2 satisfies:
1
T T∑ t=1 E[‖∇f(θt)‖2] ≤ O( 1√ T + σ2√ T + d T ).
Corollary 1 states that with error feedback, single machine AMSGrad with biased compressed gradients can also match the convergence rateO( 1√
T + dT ) of standard AMSGrad (Zhou et al., 2018) in
non-convex optimization. It also achieves the same rateO( 1√ T ) of vanilla SGD (Karimireddy et al., 2019) when T is sufficiently large. In other words, EF also fixes the convergence issue of using compressed gradients in AMSGrad.
Linear Speedup. In Theorem 1, the convergence rate is derived 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 as Theorem 1, set η = min{ 3C0 √ 2Lmax{2L,C1} , √ n√ T }. The COMP-AMS iterates admit
1
T T∑ t=1 E[‖∇f(θt)‖2] ≤ O( 1√ nT + σ2√ nT + n(σ2 + σ2g) T ). (2)
In Corollary 2, we see that the global variance σ2g appears in the O( 1T ) term, which says that it asymptotically has no impact on the convergence. This matches the result of momentum SGD (Yu et al., 2019a). When T ≥ O(n3) is sufficiently large, the third term in (2) vanishes, and the convergence rate becomes O( 1√
nT ). Therefore, to reach a O(δ) stationary point, one worker (n = 1)
needs T = O( 1δ2 ) iterations, while distributed training with n workers requires only T = O( 1
Nδ2 ) iterations, which is n times faster than single machine training. That is, COMP-AMS has a linear speedup in terms of the number of the local workers. Such acceleration effect has also been reported for compressed SGD (Zheng et al., 2019; Jiang & Agrawal, 2018) and momentum SGD (Yu et al., 2019a) with error feedback.

heading: 5 EXPERIMENTS
text: In this section, we provide numerical results on several real-world 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.

heading: 5.1 DATASETS AND MODELS
text: Our experiments are conducted on various image and text datasets. The MNIST (LeCun et al., 1998) contains 60000 training samples of 28 × 18 gray-scale hand-written digits from 10 classes, and 10000 test samples. We train MNIST with a 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 et al., 2009) consists of 50000 32× 32 RGB natural images from 10 classes for training and 10000 images for testing, which is trained by LeNet-5 (LeCun et al., 1998). Moreover, we also implement ResNet-18 (He et al., 2016) on this dataset. The IMDB movie review (Maas et al., 2011) is a popular binary classification dataset for sentiment analysis. Each movie review is tokenized by top-2000 most frequently appeared words and transformed into integer vectors, which is of maximal length 500. We train an Long-Short Term Memory (LSTM) network with a 32-dimensional embedding layer and 64 LSTM cells, followed by two fully connected layers before output. Cross-entropy loss is used for all the tasks. In each training iteration, data sample are randomly assigned to the workers.

heading: 5.2 GENERAL EVALUATION AND COMMUNICATION EFFICIENCY
text: We compare COMP-AMS with full-precision distributed AMSGrad, QAdam (Chen et al., 2020) 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, 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 β1 = 0.9, β2 = 0.999 and = 10−8, which are also used for QAdam and 1BitAdam. For 1BitAdam, 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 a fine grid and report the best results averaged over three independent runs. Our experiments are performed on a GPU cluster with NVIDIA Tesla V100 cards.
The training loss and test accuracy on MNIST + CNN, CIFAR-10 + LeNet and IMDB + LSTM are reported in Figure 1. On CIFAR-10, we deploy a decreasing learning rate schedule which 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 fullprecision AMSGrad. The 1BitAdam 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 generalization. This is because the IMDB text data is sparse (with many padded zeros), where Top-k is expected to work better than sign. The 1BitAdam converges slowly. We believe one possible reason is that 1BitAdam is quite sensitive to the quality of the warm-up training. For sparse text data, the estimation of second moment v is more unstable, making the strategy of freezing v by warm-up less effective.
Communication Efficiency. In Figure 2, 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 the full-precision gradient is represented using 32 bits. As we can see, COMP-AMS-Topk achieves around 100x communication reduction, to attain similar accuracy as the full-precision AMSGrad. The saving of Block-Sign is around 30x, but it gives slightly higher accuracy than Topk on MNIST and CIFAR-10. In all cases, COMP-AMS can substantially reduce the communication cost compared with full-precision distributed AMSGrad, without losing accuracy. Due to the space limitation, we provide more results on ResNet-18 in Appendix A.
5.3 LINEAR SPEEDUP OF COMP-AMS
Corollary 2 reveals the linear speedup of COMP-AMS in distributed training. In Figure 3, we present the training loss on MNIST and CIFAR-10 against the number of iterations, with varying number of workers n. We use COMP-AMS with Block-Sign on MNIST, and Top-k-0.01 on CIFAR. As suggested by the theory, we use 5×10−4 √ n as the learning rate. From Figure 3, we see the number of iterations to achieve a certain loss exhibits a strong linear relationship with n—it decreases by half whenever we double n, which justifies the linear speedup of COMP-AMS.

heading: 5.4 DISCUSSION
text: We provide a brief summary of our empirical observations. The proposed COMP-AMS is able to match the learning performance of full-gradient AMSGrad in all the experiments. In particular, for data/model involving some sparsity structure, COMP-AMS with the Top-k compressor could be more effective. Also, our results reveal that 1BitAdam with second moment pre-conditioning might have unstable performance on some tasks in practice.
We would like to emphasize that, the primary goal of the experiments is to show that COMP-AMS is able to match the performance of full-precision AMSGrad, but not to argue that COMP-AMS is “better than” other algorithms. This is because, different methods use different underlying optimization algorithms (e.g., AMSGrad, Adam, momentum SGD). Comparing COMP-AMS with other distributed training methods would be largely affected by the comparison among these optimization protocols, which typically depends on the specific data and model in practice. Our results says that: whenever one wants to use AMSGrad to train a deep neural network, he/she can simply employ the distributed COMP-AMS scheme to gain a linear speedup in training time with learning performance as good as the full-precision training, taking little communication cost and memory consumption.

heading: 6 CONCLUSION
text: In this paper, we study the simple, convenient, yet unexplored gradient averaging strategy for distributed adaptive optimization called COMP-AMS. Top-k and Block-Sign compressor are incorporated 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 AMSGrad, compressed gradient averaging with error feedback matches the convergence of full-gradient AMSGrad, and linear speedup can be obtained in 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-AMS to serve as a useful distributed adaptive optimization framework in practice.

heading: A MORE EXPERIMENTAL RESULTS ON RESNET-18
text: In this section, we provide more experimental results on CIFAR-10 dataset, trained with ResNet18 (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 is slightly worse. This experiment again confirms that the proposed COMP-AMS method can achieve satisfactory performance.
0 25 50 75 100
Epochs
0
0.5
1
1.5
T ra
in L
o s s
CIFAR
Dist-AMS COMP-AMS-TopK COMP-AMS-BkSign QAdam Dist-SGD
0 25 50 75 100
Epochs
40
60
80
100
T e s t A
c c u ra
c y
CIFAR
Dist-AMS COMP-AMS-TopK COMP-AMS-BkSign QAdam Dist-SGD
30 35 40 45
log(No. bits)
20
40
60
80
100
T e s t A
c c u ra
c y
CIFAR
Dist-AMS COMP-AMS-TopK COMP-AMS-BkSign QAdam Dist-SGD
Figure 4: Training loss and test accuracy of different distributed training methods on CIFAR-10 with ResNet-18 (He et al., 2016).

heading: B PROOF OF THE CONVERGENCE RESULTS
text: B.1 PROOF OF THEOREM 1 Theorem. Denote C0 = √ 4(1+q2)3
(1−q2)2 G 2 + , C1 = β11−β1 + 2q 1−q2 . Under Assumption 1 to Assump-
tion 4, with ηt = η ≤ 3C0 √ 2Lmax{2L,C2} , for any T > 0, COMP-AMS satisfies
1
T T∑ t=1 E[‖∇f(θt)‖2] ≤ 2C0 (E[f(θ1)− f(θ∗)] Tη + ηLσ2 n + 3η2LC0C1σ 2 n 2
+ 12η2q2LC0σ 2 g
(1− q2)2 2 +
(1 + C1)G 2d
T √
+ η(1 + 2C1)C1LG
2d
T
) .
Proof. We first clarify some notations. At time t, let the full-precision gradient of the j-th worker be gt,j , the error accumulator be et,j , and the compressed gradient be g̃t,j = C(gt,j + et,j). Denote ḡt = 1 n ∑n j=1 gt,j , g̃t = 1 n ∑n j=1 g̃t,j and ēt = 1 n ∑n j=1 et,j . The second moment computed by the compressed gradients is denoted as vt = β2vt−1 + (1− β2)g̃ 2 t , and v̂t = max{v̂t−1, vt}. Also, the first order moving average sequence
mt = β1mt−1 + (1− β1)g̃t and m′t = β1m′t−1 + (1− β1)ḡt.
By construction we have m′t = (1− β1) ∑t i=1 β t−i 1 ḡi.
Denote the following auxiliary sequences,
Et+1 := (1− β1) t+1∑ τ=1 βt+1−τ1 ēτ θ′t+1 := θt+1 − η Et+1√ v̂t + .
Then,
θ′t+1 = θt+1 − η Et+1√ v̂t +
= θt − η (1− β1)
∑t τ=1 β t−τ 1 g̃τ + (1− β1) ∑t+1 τ=1 β
t+1−τ 1 ēτ√
v̂t +
= θt − η (1− β1)
∑t τ=1 β
t−τ 1 (g̃τ + ēτ+1) + (1− β)βt1ē1√
v̂t +
= θt − η (1− β1)
∑t τ=1 β
t−τ 1 ēτ√
v̂t + − η m
′ t√
v̂t +
= θt − η Et√
v̂t−1 + − η m
′ t√
v̂t + + η( 1√ v̂t−1 + − 1√ v̂t + )Et
(a) = θ′t − η m′t√ v̂t + + η( 1√ v̂t−1 + − 1√ v̂t + )Et := θ′t − ηa′t + ηDtEt,
where (a) uses the fact that for every j ∈ [n], g̃t,j+et+1,j = gt,j+et,j , and et,1 = 0 at initialization. Further define the virtual iterates:
xt+1 := θ ′ t+1 − η β1 1− β1 a′t = θ ′ t+1 − η β1 1− β1 m′t√ v̂t + ,
which follows the recurrence:
xt+1 = θ ′ t+1 − η β1 1− β1 m′t√ v̂t +
= θ′t − η m′t√ v̂t + − η β1 1− β1 m′t√ v̂t + + ηDtEt
= θ′t − η β1m
′ t−1 + (1− β1)ḡt + β21 1−β1m ′ t−1 + β1ḡt√
v̂t + + ηDtEt
= θ′t − η β1 1− β1 m′t−1√ v̂t + − η ḡt√ v̂t + + ηDtEt
= xt − η ḡt√ v̂t + + η β1 1− β1 Dtm ′ t−1 + ηDtEt.
When summing over t = 1, ..., T , the difference sequence Dt satisfies the bounds of Lemma 5.
By Assumption 2 we have
f(xt+1) ≤ f(xt)− η〈∇f(xt), xt+1 − xt〉+ L
2 ‖xt+1 − xt‖2.
Taking expectation w.r.t. the randomness at time t, we obtain
E[f(xt+1)]− f(xt)
≤ −ηE[〈∇f(xt), ḡt√ v̂t + 〉] + ηE[〈∇f(xt), β1 1− β1 Dtm ′ t−1 +DtEt〉]
+ η2L 2 E[‖ ḡt√ v̂t + − β1 1− β1 Dtm ′ t−1 −DtEt‖2]
= −ηE[〈∇f(θt), ḡt√ v̂t +
〉]︸ ︷︷ ︸ I
+ ηE[〈∇f(xt), β1
1− β1 Dtm ′ t−1 +DtEt〉]︸ ︷︷ ︸
II
+ η2L 2 E[‖ ḡt√ v̂t + − β1 1− β1 Dtm
′ t−1 −DtEt‖2]︸ ︷︷ ︸
III
+ ηE[〈∇f(θt)−∇f(xt), ḡt√ v̂t +
〉]︸ ︷︷ ︸ IV ,
(3)
Bounding term I. We have
I = −ηE[〈∇f(θt), ḡt√
v̂t−1 + ]− ηE[〈∇f(θt), ( 1√ v̂t + − 1√ v̂t−1 + )ḡt〉]
≤ −ηE[〈∇f(θt), ∇f(θt)√ v̂t−1 + ] + ηG2E[‖Dt‖]. ≤ − η√ 4(1+q2)3
(1−q2)2 G 2 +
E[‖∇f(θt)‖2] + ηG2E[‖Dt‖1], (4)
where we use Assumption 3, Lemma 4 and the fact that l2 norm is no larger than l1 norm.
Bounding term II. It holds that
II ≤ η(E[〈∇f(θt), β1
1− β1 Dtm
′ t−1 +DtEt〉] + E[〈∇f(xt)−∇f(θt), β1 1− β1 Dtm ′ t−1 +DtEt〉])
≤ ηE[‖∇f(θt)‖‖ β1
1− β1 Dtm
′ t−1 +DtEt‖] + η2 LE[‖
β1 1−β1m ′ t−1 + Et√
v̂t−1 + ‖‖ β1 1− β1 Dtm ′ t−1 +DtEt‖]
≤ ηC1G2E[‖Dt‖1] + η2C21LG 2 √ E[‖Dt‖1], (5)
where C1 := β11−β1 + 2q 1−q2 . The second inequality is because of smoothness of f(θ), and the last inequality is due to Lemma 2, Assumption 3 and the property of norms.
Bounding term III. This term can be bounded as follows:
III ≤ η2LE[‖ ḡt√ v̂t + ‖2] + η2LE[‖ β1 1− β1 Dtm ′ t−1 −DtEt‖2]]
≤ η 2L E[‖ 1
n i∑ j=1 gt,j −∇f(θt) +∇f(θt)‖2] + η2LE[‖Dt( β1 1− β1 m′t−1 − Et)‖2]
(a) ≤ η 2L E[‖∇f(θt)‖2] + η2Lσ2
n + η2C21LG 2E[‖Dt‖2], (6)
where (a) follows from ∇f(θt) = 1n ∑n j=1∇fj(θt) and Assumption 4 that gt,j is unbiased of ∇fj(θt) and has bounded variance σ2.
Bounding term IV. We have
IV = ηE[〈∇f(θt)−∇f(xt), ḡt√
v̂t−1 + 〉] + ηE[〈∇f(θt)−∇f(xt), ( 1√ v̂t + − 1√ v̂t−1 + )ḡt〉]
≤ ηE[〈∇f(θt)−∇f(xt), ∇f(θt)√ v̂t−1 + 〉] + η2LE[‖ β1 1−β1m ′ t−1 + Et√ v̂t−1 + ‖‖Dtgt‖]
(a) ≤ ηρ 2 E[‖∇f(θt)‖2] + η 2ρ E[‖∇f(θt)−∇f(xt)‖2] + η2C1LG 2 √ E[‖Dt‖]
(b) ≤ ηρ 2 E[‖∇f(θt)‖2] + η3L 2ρ E[‖
β1 1−β1m ′ t−1 + Et√
v̂t−1 + ‖2] + η
2C1LG 2
√
E[‖Dt‖1], (7)
where (a) is due to Young’s inequality and (b) is based on Assumption 2.
Regarding the second term in (7), by Lemma 3 and Lemma 1, summing over t = 1, ..., T we have
T∑ t=1 η3L 2ρ E[‖ β1 1−β1m ′ t−1 + Et√ v̂t−1 + ‖2]
≤ T∑ t=1 η3L 2ρ E[‖ β1 1− β1 m′t−1 + Et‖2]
≤ T∑ t=1 η3L ρ [ β21 (1− β1)2 E[‖m′t‖2] + E[‖Et‖2] ]
≤ Tη 3β21Lσ 2
nρ(1− β1)2 +
η3β21L
ρ(1− β1)2 T∑ t=1 E[‖∇f(θt)‖2]
+ 4Tη3q2L
ρ(1− q2)2 (σ2 + σ2g) +
4η3q2L
ρ(1− q2)2 T∑ t=1 E[‖∇f(θt)‖2]
= Tη3LC2σ 2
nρ + 4Tη3q2Lσ2g ρ(1− q2)2 + η3LC2 ρ T∑ t=1 E[‖∇f(θt)‖2], (8)
with C2 := β21 (1−β1)2 + 4q2
(1−q2)2 . Now integrating (4), (5), (6), (7) and (8) into (3), taking the telescoping summation over t = 1, ..., T , we obtain
E[f(xT+1)− f(x1)]
≤ (− η C0 + η2L + ηρ 2 + η3LC2 ρ ) T∑ t=1 E[‖∇f(θt)‖2] + Tη2Lσ2 n + Tη3LC2σ 2 nρ + 4Tη3q2Lσ2g ρ(1− q2)2
+ (η(1 + C1)G 2 +
η2(1 + C1)C1LG 2
√
) T∑ t=1 E[‖Dt‖1] + η2C21LG2 T∑ t=1 E[‖Dt‖2.
with C0 := √ 4(1+q2)3 (1−q2)2 G 2 + . Setting η ≤
3C0 √ 2Lmax{2L,C2} and choosing ρ = 3C0 , we obtain
E[f(xT+1)− f(x1)]
≤ − η 2C0 T∑ t=1 E[‖∇f(θt)‖2] + Tη2Lσ2 n + 3Tη3LC0C2σ 2 n 2 + 12Tη3q2LC0σ 2 g (1− q2)2 2
+ η(1 + C1)G 2d√ + η2(1 + 2C1)C1LG 2d .
where the last inequality follows from Lemma 5. Re-arranging terms, we get that
1
T T∑ t=1 E[‖∇f(θt)‖2] ≤ 2C0 (E[f(x1)− f(xT+1)] Tη + ηLσ2 n + 3η2LC0C2σ 2 n 2
+ 12η2q2LC0σ 2 g
(1− q2)2 2 +
(1 + C1)G 2d
T √
+ η(1 + 2C1)C1LG
2d
T ) ≤ 2C0 (E[f(θ1)− f(θ∗)] Tη + ηLσ2 n + 3η2LC0C 2 1σ 2 n 2
+ 12η2q2LC0σ 2 g
(1− q2)2 2 +
(1 + C1)G 2d
T √
+ η(1 + 2C1)C1LG
2d
T
) ,
where C0 = √ 4(1+q2)3
(1−q2)2 G 2 + , C1 = β11−β1 + 2q 1−q2 . The last inequality is because θ ′ 1 = θ1,
θ∗ := arg minθ f(θ) and the fact that C2 ≤ C21 . This completes the proof.
B.2 INTERMEDIATE LEMMAS
Lemma 1. Under Assumption 1 to Assumption 4 we have: T∑ t=1 E‖m′t‖2 ≤ Tσ2 n + t∑ τ=1 E[‖∇f(θt)‖2].
Proof. Firstly, the expected squared norm of average stochastic gradient can be bounded by
E[‖ḡ2t ‖] = E[‖ 1
n n∑ i=1 gt,i −∇f(θt) +∇f(θt)‖2]
= E[‖ 1 n n∑ i=1 (gt,i −∇fi(θt))‖2] + E[‖∇f(θt)‖2]
≤ σ 2
n + E[‖∇f(θt)‖2],
where we use Assumption 4 that gt,i is unbiased with bounded variance. Let ḡt,i denote the i-th coordinate of ḡt. By the updating rule of COMP-AMS
E[‖m′t‖2] = E[‖(1− β1) t∑
τ=1
βt−τ1 ḡτ‖2]
≤ (1− β1)2 d∑ i=1 E[( t∑ τ=1 βt−τ1 ḡτ,i) 2]
(a) ≤ (1− β1)2 d∑ i=1 E[( t∑ τ=1 βt−τ1 )( t∑ τ=1 βt−τ1 ḡ 2 τ,i)]
≤ (1− β1) t∑
τ=1
βt−τ1 E[‖ḡτ‖2]
≤ σ 2
n + (1− β1) t∑ τ=1 βt−τ1 E[‖∇f(θt)‖2],
where (a) is due to Cauchy-Schwartz inequality. Summing over t = 1, ..., T , we obtain T∑ t=1 E‖m′t‖2 ≤ Tσ2 n + T∑ t=1 E[‖∇f(θt)‖2].
This completes the proof.
Lemma 2. Under Assumption 4, we have for ∀t and each local worker ∀i ∈ [n],
‖et,i‖2 ≤ 4q2
(1− q2)2 G2,
E[‖et+1,i‖2] ≤ 4q2
(1− q2)2 σ2 +
2q2 1− q2 t∑
τ=1
( 1 + q2
2 )t−τE[‖∇fi(θτ )‖2].
Proof. We start by using Assumption 1 and Young’s inequality to get
‖et+1,i‖2 = ‖gt,i + et,i − C(gt,i + et,i)‖2
≤ q2‖gt,i + et,i‖2
≤ q2(1 + ρ)‖et,i‖2 + q2(1 + 1
ρ )‖gt,i‖2
≤ 1 + q 2
2 ‖et,i‖2 +
2q2
1− q2 ‖gt,i‖2, (9)
by choosing ρ = 1−q 2
2q2 . Now by recursion and the initialization e1,i = 0, we have
E[‖et+1,i‖2] ≤ 2q2 1− q2 t∑
τ=1
( 1 + q2
2 )t−τE[‖gτ,i‖2]
≤ 4q 2
(1− q2)2 σ2 +
2q2 1− q2 t∑
τ=1
( 1 + q2
2 )t−τE[‖∇fi(θτ )‖2],
which proves the second argument. Meanwhile, the absolute bound ‖et,i‖2 ≤ 4q 2 (1−q2)2G 2 follows directly from (9).
Lemma 3. For the moving average error sequence Et, it holds that T∑ t=1 E[‖Et‖2] ≤ 4Tq2 (1− q2)2 (σ2 + σ2g) + 4q2 (1− q2)2 T∑ t=1 E[‖∇f(θt)‖2]. Proof. Let ēt,i be the j-th coordinate of ēt. Denote Kt,i := ∑t τ=1( 1+q2 2 ) t−τE[‖∇fi(θτ )‖2] and Kt,i = 0, ∀i ∈ [n]. Using the same technique as in the proof of Lemma 1, we have
E[‖Et‖2] = E[‖(1− β1) t∑
τ=1
βt−τ1 ēτ‖2]
≤ (1− β1)2 d∑ j=1 E[( t∑ τ=1 βt−τ1 ēτ,j) 2]
(a) ≤ (1− β1)2 d∑ j=1 E[( t∑ τ=1 βt−τ1 )( t∑ τ=1 βt−τ1 ē 2 τ,j)] ≤ (1− β1) t∑
τ=1
βt−τ1 E[‖ēτ‖2]
≤ (1− β1) t∑
τ=1
βt−τ1 E[ 1
n n∑ i=1 ‖eτ,i‖2]
(b) ≤ 4q 2
(1− q2)2 σ2 + 2q2(1− β1) (1− q2) t∑ τ=1 βt−τ1 ( 1 n n∑ i=1 Kτ,i),
where (a) is due to Cauchy-Schwartz and (b) is a result of Lemma 2. Summing over t = 1, ..., T and using the technique of geometric series summation leads to T∑ t=1 E[‖Et‖2] = 4Tq2 (1− q2)2 σ2 + 2q2(1− β1) (1− q2) T∑ t=1 t∑ τ=1 βt−τ1 ( 1 n n∑ i=1 Kτ,i)
≤ 4Tq 2
(1− q2)2 σ2 +
2q2
(1− q2) T∑ t=1 t∑ τ=1 ( 1 + q2 2 )t−τE[ 1 n n∑ i=1 ‖∇fi(θτ )‖2]
≤ 4Tq 2
(1− q2)2 σ2 +
4q2 (1− q2)2 T∑ t=1 E[ 1 n n∑ i=1 ‖∇fi(θt)‖2]
(a) ≤ 4Tq 2
(1− q2)2 σ2 +
4q2 (1− q2)2 T∑ t=1 E[‖ 1 n n∑ i=1 ∇fi(θt)‖2 + 1 n n∑ i=1 ‖∇fi(θt)−∇f(θt)‖2]
≤ 4Tq 2
(1− q2)2 (σ2 + σ2g) +
4q2 (1− q2)2 T∑ t=1 E[‖∇f(θt)‖2],
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 ∀t ∈ [T ], ∀i ∈ [d], v̂t,i ≤ 4(1+q 2)3 (1−q2)2 G 2.
Proof. For any t, by Lemma 2 and Assumption 3 we have ‖g̃t‖2 = ‖C(gt + et)‖2
≤ ‖C(gt + et)− (gt + et) + (gt + et)‖2
≤ 2(q2 + 1)‖gt + et‖2
≤ 4(q2 + 1)(G2 + 4q 2
(1− q2)2 G2)
= 4(1 + q2)3
(1− q2)2 G2.
It’s then easy to show by the updating rule of v̂t,
v̂t,i = (1− β2) t∑
τ=1
βt−τ2 g̃ 2 t,i ≤
4(1 + q2)3
(1− q2)2 G2.
Lemma 5. Let Dt := 1√ v̂t−1+ − 1√ v̂t+ be defined as above. Then,
T∑ t=1 ‖Dt‖1 ≤ d√ , T∑ t=1 ‖Dt‖2 ≤ d .
Proof. By the updating rule of COMP-AMS, v̂t−1 ≤ v̂t for ∀t. Therefore, by the initialization v̂0 = 0, we have
T∑ t=1 ‖Dt‖1 = T∑ t=1 d∑ i=1 ( 1√ v̂t−1,i + − 1√ v̂t,i + )
= d∑ i=1 ( 1√ v̂0,i + − 1√ v̂T,i + )
≤ d√ .
For the sum of squared l2 norm, note the fact that for a ≥ b > 0, it holds that
(a− b)2 ≤ (a− b)(a+ b) = a2 − b2.
Thus,
T∑ t=1 ‖Dt‖2 = T∑ t=1 d∑ i=1 ( 1√ v̂t−1,i + − 1√ v̂t,i + )2
≤ T∑ t=1 d∑ i=1 ( 1 v̂t−1,i + − 1 v̂t,i + )
≤ d ,
which gives the desired result.

Review summaries:
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.

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.

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.