Efficient-Adam: Communication-Efficient Distributed Adam

Introduction

However, it could be impossible to train a deep neural network with a large number of parameters over a large-scale dataset within a single machine. Fortunately, we have some promising approaches to tackle this problem. One of them is to extend the stochastic gradient descent (SGD) method to \changea distributed version [li2014efficient]. Then using the distributed SGD method, we train a deep learning model with multiple machines in a distributed mode [goyal2017accurate, you2019large]. However, for the vanilla SGD method, how to tune a suitable learning rate for different tasks remains challenging. This dilemma is more serious for distributed SGD methods since there are multiple learning rates needed to be tuned for multiple machines. Moreover, the communication overhead is another issue in distributed methods. How to reduce the communication cost among multiple machines is also challenging. Recently, Hou et al.[hou2018analysis] proposed a distributed Adam [kingma2014adam] with weights and gradients being quantized to reduce the communication cost between the workers and the server. However, their theoretical analysis \changeis merely restricted to the convex setting, and they didn’t provide the bit-communication complexity either, which hampers the potential applications. In addition, both the weights and gradients quantization techniques will introduce additional errors, which may degrade the performance of the vanilla Adam optimizer. On the other hand, distributed Adam has already been built in several deep learning platforms, such as PyTorch [paszke2019pytorch], TensorFlow [abadi2016tensorflow], and MXNet [chen2015mxnet], and it has since been broadly used for training deep learning models. However, its communication complexity under the distributed mode has rarely been analyzed in either convex or nonconvex settings.

In this work, we propose a communication-efficient distributed adaptive stochastic gradient descent method by incorporating a two-way quantization of updates and a two-way error feedback strategy, dubbed Efficient-Adam, to solve the nonconvex stochastic problem (1). As it is illustrated in Figure 1, the architecture of Efficient-Adam belongs to a Parameter-Server [smola2010architecture, li2014scaling] distributed system. For each worker, in each iteration, we first sample a stochastic gradient of problem (1). Then, we calculate the updates with the Adam optimizer. Next, we quantize the updates based on a specifically designed quantization mapping and an error term and send the quantized updates to the server. \changeAfter that, we update the local error terms using the updated quantization mapping and the new error terms. At last, we receive the averaged updates from the server and update local iterates. On the other hand, in the server, we first gather and average the compressed updates from each worker. Then, we quantize the average updates and broadcast them to each worker. Next, we update iterates and error feedback terms. From the workflow of Efficient-Adam in Figure 1, it can be seen that communicated bi-directional information is all quantized in advance. With the proper quantization mapping, communication costs can be reduced largely. In addition, error terms in the workers and server can compensate for errors that are introduced by the two-way quantization steps between all the workers and the server, which \changehelps accelerate the convergence of Efficient-Adam for problem (1).

Moreover, we explore the iteration complexity for Efficient-Adam with a class of quantization operators when an $\varepsilon$-stationary point is achieved. For a carefully designed quantization mapping, we further characterize its overall communication complexity in terms of bits between the server and workers. On the other hand, when the quantization mapping is generalized to a compressor as [stich2019error, stich2018sparsified, zheng2019communication], Efficient-Adam can enjoy the same convergence rate as \changethe full-precision Adam in Zou et al. [zou2019sufficient] and Chen et al. [chen2022towards]. Experimentally, we apply Efficient-Adam to train deep learning models on computer vision and natural language processing tasks to demonstrate its efficacy. To the end, we summarize our contribution in four-fold:

We propose a communication-efficient distributed Adam to solve stochastic problem (1). We dub it Efficient-Adam which utilizes a two-way quantization scheme to reduce the communication cost and a two-way error feedback strategy to compensate for quantization errors.

We characterize the iteration complexity of Efficient-Adam in the non-convex setting. Under proper assumptions, we further characterize its overall communication complexity in terms of bits between the server and workers via a specifically designed quantization mapping.

We show the convergence rate of Efficient-Adam can further be improved to the same order of vanilla Adam, i.e., $\mathcal{O}(1/\sqrt{T})$, once we generalize the quantization mapping in Efficient-Adam to a compressor mapping as [stich2019error, stich2018sparsified].

We conduct experiments on computer vision and natural language processing tasks to demonstrate the efficacy of the proposed Efficient-Adam, as well as the related two-way quantization and two-way error feedback techniques.

Related Work

Optimizing a large-scale stochastic non-convex function has been studied for many years, in which distributed SGD method has been widely explored. For distributed SGD, its convergence rate has been established \changeboth in the Parameter-Server model [agarwal2011distributed] and decentralized model [lian2017can]. To reduce the communication cost, compression on the communication has been added into the distributed stochastic methods, such as QSGD [alistarh2017qsgd] and Sign SGD [bernstein2018signsgd]. However, due to the error introduced by compression, most distributed methods will fail to converge with compressed communication. Several works [jiang2018linear, wangni2018gradient, wen2017terngrad] have tried to use unbiased compressors to remove errors brought by compression and provide related convergence analyses. However, with some biased compressors (e.g. SignSGD), SGD methods empirically achieve good \changesolutions, which cannot be explained by those works. To deal with biased compression, Karimireddy et al. [karimireddy2019error] first introduced error feedback into SignSGD method and established its convergence. However, their analysis only focuses on the setting in a single machine. In addition, there exist several decentralized SGDs that try to utilize error feedback to reduce compression errors, such as ChocoSGD [koloskova2019decentralized] and DeepSqueeze [tang2019texttt].

Further, for the parameter-server model, Zheng et al. [zheng2019communication] introduced a two-way error feedback technique into SGD with momentum and showed its convergence in the nonconvex setting. Moreover, they used a block-wise compressor to meet the compressor assumption. However, even with the block-wise compression, their assumption still does not hold when the gradient goes to . Besides, the learning rate for each worker may be hard to tune when the number of workers is large. On the other hand, Hou et al. [hou2018analysis] adapted the distributed Adam with quantized gradients and weights to reduce the communication overhead and gave the convergence bound for the convex case. However, in their work, they considered an unbiased quantization function and did not consider error feedback terms, which may limit the use of the analysis. Besides, Chen et al. [chen2021quantized] proposed Quantized Adam, but they only consider error feedback in one direction, and in the other direction, weight quantization is used. Wang et al. [wang2022communication] compressed and communicated with gradients, then they performed an AMSGrad algorithm. \changeThe update equation can be encapsulated as $x_{t+1}=x_{t}-\alpha_{t}m_{t}/\sqrt{v_{t}+\epsilon}$. The theoretical analysis conducted by Chen et al. [chen2021quantized] and Wang et al. [wang2022communication] significantly depends on the constant $\epsilon$, which must be sufficiently large. However, a larger value of $\epsilon$ can lead to it dominating the denominator of the equation, thereby causing the algorithm to regress to a simple stochastic gradient descent mechanism. Further, Doostmohammadian M et al. [doostmohammadian2022distributed, doostmohammadian2022fast] and Magnusson et al. [magnusson2018communication] present algorithms that solve constrained optimization problems when the communication network experiences heterogeneous time-delays. Moreover, when considering transmitting bits among devices, the compression assumption used in previous work does not hold (e.g. with finite bits arbitrary small \changevalues can not be represented). Therefore, we will give a practical assumption on the compression of the communication. To distinguish from the previous assumption, we denote the function satisfying the new assumption as a quantizer, and the function satisfying the previous assumption as a compressor. \secchangeAmong the research we’ve looked at, the work by Chen et al. [chen2021quantized] is the most similar to ours. However, they tried to reduce how much information the server sends to the workers by using shorter representations for the model’s weights which further introduces additional quantization bias. Since it’s tough to represent these weights accurately with just a few bits, we took a different path in our study. We try to send compressed updates for the weights instead. This way, we’re able to lower the communication needed even more.

Different from these existing works, we propose an adaptive distributed stochastic algorithm with a two-way quantization/compressor and a two-way error feedback strategy, dubbed Efficient Adam. We also establish its iteration complexity and communication complexity in terms of bits under some specialized designed quantization mappings in the non-convex setting. In the following Table 1, we summarize the differences between our proposed Efficient-Adam and several existing communication-efficient distributed SGD methods in the parameter-server model.

Preliminaries

Below, we define a class of quantization mappings which are used to quantize the communicated information between the workers and server in Figure 1 to reduce the communication.

We give a few quantization mappings that satisfy the above definition.

Let $M=\{2^{k},2^{k+1},\cdots,2^{K}\}$ for some integer numbers $k$ and $K>k$. Define the quantization function $\mathcal{Q}$ as $\mathcal{Q}(x)=sign(x)\arg\min_{y\in M^{d}}\||x|-y\|$.

There exist several works that utilize compressor mappings [stich2018sparsified, stich2019error] to reduce the communication cost for distributed SGD in the Parameter-Server model, in which compressor mapping is formally defined as follows:

Most quantization mappings do not belong to the above class of compressors, since, with a finite set as range, quantization mapping cannot achieve the condition of compressors for arbitrarily small \changeparameters $x$. Therefore, we cannot find any quantization function that satisfies the definition of the compressor in Definition 3. Moreover, when $\delta^{\prime}$ is much smaller than the precision which we want to achieve, we can ignore it and reduce the condition to the compressor condition. Meanwhile, we have an additional condition $\|Q(x)\|\leq(2-\delta)\|x\|$, which can be easily achieved by replacing rounding to flooring. Therefore, we give a more practical condition for analyzing the communication complexity. Moreover, the convergence of Efficient-Adam with quantization can be easily extended to compressors.

Efficient-Adam

In this section, we describe the proposed Efficient-Adam, whose workflow has already been displayed in Figure 1. To make the presentation clear, we split Efficient-Adam into two parts: parameter server part (Algorithm 1) and $N$-workers part (Algorithm 2). To reduce the communication overhead among the server and workers, we introduce a two-way quantization mapping. We denote the quantization function in the parameter server as $\mathcal{Q}_{s}(\cdot)$ and the quantization function in the workers as $\mathcal{Q}_{w}(\cdot)$, respectively. The detailed iterations of Efficient-Adam are described in Algorithm 1 and Algorithm 2.

In the parameter server (see Algorithm 1), the initial value of $x$ will be broadcast to each worker at the initialization phase. Then in each iteration, the server gathers the update from each worker, calculates the average of these updates, and then broadcasts this average after a quantization function.

In each worker (see Algorithm 2), at the initial phase, the initial value of $x$ will be received. In each update iteration, a worker will sample a stochastic gradient $g_{t}$ and calculate the update vector $\delta_{t}$. Then it will send the update vector to the server with a quantization mapping and receive the average update vector from the server. Finally, the worker will update its local parameters.

For the above two algorithms, we use the error-feedback technique to reduce the influence of errors introduced by quantization shown in line 6 of Algorithm 1 and line 8 in Algorithm 2. \changeThe error-feedback technique can be viewed as delaying updating values for $x$, while without error-feedback the algorithm discards \changea few updating values on $x$ which losses information during the optimization process. Therefore, the error-feedback technique can help the algorithm by preserving information discarded by the quantizer.

In this subsection, we give iteration complexity analysis and bit communication complexity analysis in order to obtain an $\varepsilon$-stationary solution of problem (1) in Definition 1, i.e.,

We denote $\delta_{s}$ and $\delta_{s}^{\prime}$ as the constants defined in Definition 2 for $\mathcal{Q}_{s}(\cdot)$, and $\delta_{w}$, $\delta_{w}^{\prime}$ for $\mathcal{Q}_{w}(\cdot)$. In addition, we further make another assumption on hyperparameters $\theta_{t}$ and $\alpha_{t}$.

For a given maximum number of iterations $T$, we define the exponential moving average parameter $\theta_{t}=1-\frac{\theta}{T}$, and base learning rate $\alpha_{t}=\frac{\alpha}{\sqrt{T}}$. Besides, we define $\gamma=\beta/(1-\frac{\theta}{T})$.

Below, we characterize the iteration complexity of Efficient-Adam to achieve an $\varepsilon$-stationary solution of problem (1). In the corollary, we characterize the overall bit communication complexity of Efficient-Adam with the quantization mapping defined in Example 2.

Let $\{x_{t}\}$ be the point generated by Algorithm 1 and Algorithm 2. In addition, assume that all workers work identically and independently. Let $x_{\tau}^{T}$ be the random variable $x_{\tau}$ with $\tau$ taking from $\{1,2,\cdots,T\}$ with the same probability. For given $\varepsilon$, when $T\geq\frac{4(G^{2}+\epsilon d)}{(1-\beta)^{2}\alpha^{2}\varepsilon^{2}}\left(F(x_{1})-F^{*}+C_{2}\right)^{2}$, it always holds that

where $C_{1}=\left(\frac{\beta/(1-\beta)}{\sqrt{(1-\gamma)\theta_{1}}}+1\right)^{2}$, $C_{2}\!=\!\frac{d}{1-\sqrt{\gamma}}\left(\frac{(2-\delta_{w})(2-\delta_{s})\alpha^{2}L}{\theta(1-\sqrt{\gamma})^{2}\delta_{w}\delta_{s}}\!+\!\frac{2C_{1}G\alpha}{\sqrt{\theta}}\right)\left[\log\left(1+\frac{G^{2}}{\epsilon d}\right)\!+\!\frac{\theta}{1\!-\!\theta}\right]$, and $C_{3}=\sqrt{\frac{d}{\theta(1-\sqrt{\gamma})^{4}}\left[\log\left(1+\frac{G^{2}}{\epsilon d}\right)+\frac{\theta}{1-\theta}\right]}.$

In comparison to the work of Chen et al. [chen2021quantized] and Wang et al. [wang2022communication], we have an order of $\mathcal{O}(\log^{2}(1+\frac{1}{\epsilon d}))$ with respect to the constant $\epsilon$, which pertains to numerical issues. Conversely, they demonstrate an order of $\mathcal{O}(\frac{1}{\epsilon})$. In practical applications, $\epsilon$ is typically configured to be a small value. Therefore, our algorithm is capable of achieving significantly faster convergence compared to theirs. \secchange Additionally, because Chen et al. [chen2021quantized] compress the weights instead of the updates, when we let the value of $T$ go to infinity, their method can’t reach the exact stationary point. Instead, it gets really close to some stationary point, even when we use the compressor in Definition 3. On the other hand, our approach can reach the stationary point with $T$ going to infinity and compressors in Definition 3.

With the quantization function in Example 2, when we want to get an $\varepsilon$-stationary solution we need at most $C_{5}$ bits per iteration on the workers and the server. Besides, to achieve an $\varepsilon$-stationary point, we need $\frac{16(G^{2}+\epsilon d)}{(1-\beta)^{2}\alpha^{2}\varepsilon^{2}}\left(F(x_{1})-F^{*}+C_{4}\right)^{2}$ iterations, where $C_{4}=\frac{d}{1-\sqrt{\gamma}}\left(\frac{9\alpha^{2}L}{\theta(1-\sqrt{\gamma})^{2}}+\frac{2C_{1}G\alpha}{\sqrt{\theta}}\right)\left[\log\left(1\!+\!\frac{G^{2}}{\epsilon d}\right)+\frac{\theta}{1-\theta}\right]$, $C_{5}=d\left(1\!+\!\log\left(\log(\frac{\alpha}{(1\!-\!\gamma)\theta})\!+\!\log\left(\frac{24Ld\sqrt{G^{2}\!+\!\epsilon d}C_{3}}{\varepsilon(1-\beta)}\right)\!+\!1\right)\right)$, and $C_{1},\ C_{3}$ are defined in Theorem 1.

From the above theorem and corollary, we can reduce the bits of communication by two-way quantization and error feedback. In addition, the bit communication complexity and iteration complexity are $O(d\log\log\frac{d^{2}}{\varepsilon})$ and $O(\frac{d^{3}}{\varepsilon^{2}})$, respectively. Moreover, it can be seen that adding compression in both sides can converge to an arbitrary $\varepsilon$-stationary point when we have large enough communication bandwidth and sufficient iterations. There is a limited influence when we add quantization into communication if we can have a small additional error $\delta_{w}^{\prime}$. Below, we show that if we replace the quantization mapping in Definition 2 as Compressor in Definition 3 in Algorithms 1-2, Efficient-Adam can attain the same order of iteration complexity as original Adam without introducing additional error terms.

From the above corollary, it can be shown that the convergence rate of Efficient-Adam matches the convergence rate of the vanilla Adam. Thanks to the two-way error feedback techniques employed in Efficient-Adam, the convergence rate will not be hurt by the introduced bi-direction compressor as defined in Definition 3, which merely affects the speed of convergence at the constant level. \secchangeHowever, Chen et al. [chen2021quantized] adopt the compression on the weights which merely converges to the neighborhood of the stationary point.

Experiments

For simplicity, we use the abbreviation for all compared algorithms in the figures in this section. The abbreviations are summarized in the following Table 2.

In this subsection, we first optimize the following toy stochastic convex optimization problem:

The detailed comparisons are illustrated in Figure 2. It shows that when full-precision algorithms achieve similar performance, the Terngrad quantizer \secchange and Chen et al. [chen2021quantized] will give worse results than Zheng et al. [zheng2019communication] and ours. We can achieve similar results as Zheng et al. [zheng2019communication], or even better results when using Example 2. Even when using Example 2, it can achieve a slighter better result than the full precision version. In addition, as it is shown in the third subfigure and the fourth subfigure in Figure 2 when we consider communication bits, the quantizer introduced in Example 1 gives the smallest total number of bits. On the other hand, even if Example 2 uses twice more bits than Example 1 does in one communication iteration, with our algorithm it can still converge faster than Terngrad.

As it refers to the error-feedback technique, shown in Figure 3, with quantizer in Example 1, error-feedback can help the algorithm get a better result. It helps a little when using Example 2 as the quantization function during communication. This may be because the Example 2 is accurate enough for solving this problem.

2 Image Classification

The detailed results are shown in Figure 4, 5, and 6, where training loss has been smoothed for better presentation. Figure 5 shows the convergence speed and test accuracy with respect to the optimization iterations. It shows that even if we quantize the communication our algorithm and Zheng et al. [zheng2019communication] can achieve similar performance as the full communication version. Meanwhile, because Terngrad [wen2017terngrad] introduces extra noise, it gives the worst results. \secchangeAnd because Chen et al. [chen2021quantized] quantized weights instead of the updates that introduce the irreducible errors, they can not approach the optimal point as close as the other methods. Thus it results in poor generalizations compared with our proposed Efficient-Adam. When we consider the training loss and test accuracy with respect to communication bits, which is shown in Figure 4, Zheng et al. [zheng2019communication] achieves the best result. This may be because sgd-based methods are much more suitable for image classification tasks compared with adaptive stochastic gradient type methods [wilson2017marginal]. Moreover, our results are similar to Zheng et al. [zheng2019communication]’s results. Still, it can be shown in Figure 4 that with Example 2 as a quantizer, our algorithm is still better than Terngrad [wen2017terngrad].

Besides, we check whether the error-feedback technique is helpful to train the image classification task. The results are shown in Figure 6. When quantization functions introduce “large” error where Example 1 is used, the error-feedback technique helps a lot. Similarly, when the quantizer is accurate enough, where Example 2 is used as the quantization function, error-feedback has limited effect for improving its accuracy.

3 Binary Sentiment Classification

In addition, we apply our method to the sentiment classification task. We train a GRU [cho2014properties] network on the dataset IMDB [maas-EtAl:2011:ACL-HLT2011]. The dataset contains 50,000 movie reviews which are labeled as positive or negative. Besides, the dataset has been split into two sets: one is a training set that contains 25,000 reviews and the other is a test set containing the rest 25,000 reviews. For the network part, we use a bidirectional GRU with 2 layers. In each layer, we set the hidden unit dimension as 256. Moreover, we use pertained Bert [devlin2018bert] encoding to encode the text before it goes into GRU. During the training phase, we set iterations as 2000, parameter $\beta=0.9$, and parameter $\theta_{t}=0.999$ for Adam-based algorithms, and the momentum coefficient for sgd-based algorithm is 0.9. The learning rate for each algorithm is selected from $\{1e-1,5e-2,1e-2,5e-3,1e-3,5e-4,1e-4\}$ via grid search approach. The batch size is 16 and 8 workers are involved in the training phase. No regularization terms or learning rate decay are used in the training phase. The hyper-parameters for the quantization function are the same as it in Section 5.1.

The experimental results are shown in Figures 7, 8, and 9, where training loss has been smoothed for better presentation. In Figure 8, sgd-based algorithms perform worse than Adam-based algorithms. Still, the quantization of communication affects a little on our algorithm. Besides, Efficient-Adam with the quantizer in Example 2 even achieves the highest test accuracy among all compared algorithms. When considering training loss and test accuracy vs. communication, shown in Figure 7, Efficient-Adam with Example 1 can achieve lower training loss and comparable high test-accuracy as Distributed Adam with Terngrad, while Efficient-Adam with Example 2 can achieve the highest test accuracy after 500MB communication.

Moreover, Figure 9 shows the influence of the error-feedback technique. Still, without error-feedback, Efficient-Adam with quantizer in Example 1 achieves much worse performance than the algorithm with error-feedback, and Efficient-Adam with quantizer in Example 2 achieves a slightly bad test accuracy or achieves even better training loss than the algorithm with error-feedback. Results can be concluded similarly as it is in Section 5.1 and 5.2, where the more error quantization function will introduce, the more helpful error feedback is.

Conclusion

We proposed a communication efficient adaptive stochastic gradient descent algorithm for optimizing the non-convex stochastic problem, dubbed Efficient-Adam. In the algorithm, we used a two-side quantization to reduce the communication overhead and two error feedback terms to compensate for the quantization error to encourage convergence. With the more practical assumptions, we established a theoretical convergence result for the algorithm. Besides, we established the communication complexity and iteration complexity under certain quantization functions. On the other hand, when the quantization operators are generalized to compressors, Efficient-Adam can achieve the same convergence rate as full-precision Adam. Lastly, we applied the algorithm to a toy task and real-world image and sentiment classification tasks. The experimental results confirm the efficacy of the proposed Efficient-Adam. However, we merely established the convergence of the Efficient-Adam. \changeTo demonstrate the linear-speedup characteristic of Efficient-Adam in a distributed environment, alternative assumptions, such as bounding the variance of stochastic gradients, may be necessary. We identify this as a potential area for future exploration. Additionally, the algorithm could potentially be adapted into an asynchronous version, which would involve assessing the impact of delays on the algorithm’s performance. We also earmark this aspect for future investigation.

Proof of Efficient-Adam

To prove Theorem 1, more notations and lemmas are needed. Below, we introduce several notations and lemmas.

Using the above notations, it is not hard to check that the following two equations hold:

By using Notation 1 and the iteration scheme of algorithm 2, $\forall\ t\geq 1$ and $i=1,2,\cdots,N$, the following inequality holds:

By using the definitions of $m_{t}^{\left(i\right)}$ and $v_{t}^{\left(i\right)}$ in Algorithm 2, it directly holds that

With arithmetic inequality, it holds that

Let $e^{\left(i\right)}_{t}$ be the noisy term defined in Algorithm 2 and $\Delta^{\left(i\right)}_{t}$ be the term defined in Notation 1. Then it holds that

Using the definition of the noisy term $e_{t}$, the following holds:

Then, by taking expectations on both sides of the above inequality, we get the desired result.

Let $e_{t}$ be the noisy term defined in Algorithm 1 and $\Delta^{\left(i\right)}_{t}$ be the term defined in Notation 1. Then, it holds that

By the definition of $\hat{\delta_{t}}$ in Algorithm 1 and Algorithm 2, it holds that

With the definition of $e_{t}$, we obtain that

Plugging $\|e_{t}\|$ into the left-hand-side and summing over $T$ and $N$, we obtain that

Then we simplify the above summation terms, for the first term, it holds that

Combining inequalities (5), (6), (7) and (8), it holds that

Then, by taking expectations on both sides of the above inequality, we get the desired result.

By using Notation1, for any $i=1,2,\cdots,N$, the following inequality holds:

By the definition of $m_{t}^{\left(i\right)}$, we can obtain

Because $v_{t}^{\left(i\right)}\geq\theta^{\prime}v_{t-1}^{\left(i\right)}$, we can easily obtain that $v_{t}^{\left(i\right)}\geq\left(\theta^{\prime}\right)^{t-k}v_{k}^{\left(i\right)}$.

By using the definition of $\Delta_{t}^{\left(i\right)}$, we can obtain

For all $i=1,2,\cdots,N$, the following estimate holds:

Let $W_{0}=1$ and $W_{t}=\prod_{i=1}^{t}\theta_{i}^{-1}$. Let $w_{t}=W_{t}-W_{t-1}=\left(1-\theta_{t}\right)W_{t}$. Therefore, we have $\frac{w_{t}}{W_{t}}=1-\theta_{t}$, and $\frac{W_{t-1}}{W_{t}}=\theta_{t}$. By observing that $W_{0}v_{0}^{\left(i\right)}=\epsilon$ and $W_{t}v_{t}^{\left(i\right)}=W_{t-1}v_{t-1}^{\left(i\right)}+w_{t}\left(g_{t}^{\left(i\right)}\right)^{2}$, then we can obtain $W_{t}v_{t}^{\left(i\right)}=\epsilon+\sum_{k=1}^{t}w_{k}\left(g_{k}^{\left(i\right)}\right)^{2}$.

By plugging the equality into the left-hand side, we obtain

Considering each dimension respectively, for each $j=1,2,\cdots,d$, we obtain

By the definition of $\Delta_{t}^{\left(i\right)}$, the following inequality always holds:

Because of the concavity of function $\sqrt{x}$, we have $\sum_{t=1}^{T}\|\Delta_{t}\|\leq\sqrt{T\sum_{t=1}^{T}\|\Delta_{t}\|^{2}}$. Hence, using Lemma 7.7 and Lemma 7.9, we obtain the desired result.

With the definition of $M_{t}$, it holds that

Using the definitions of $v_{t}^{\left(i\right)}$ and $\hat{v}_{t}^{\left(i\right)}$, we obtain

Meanwhile, with the definition of $\mathcal{Q}_{s}$ and $\mathcal{Q}_{w}$, it holds that

Combining with $\|\Delta_{t-1}\|\leq\frac{1}{N}\sum_{i=1}^{N}\|\Delta_{t-1}^{(i)}\|$, it holds that

where the inequality holds with the following equalities and inequalities:

Let $C_{1}\!=\!\left(\frac{\beta/\left(1-\beta\right)}{\sqrt{\left(1-\gamma\right)\theta_{1}}}+1\right)^{2}$, we can obtain $|A_{t}^{\left(i\right)}|\!\leq\!\frac{\sqrt{C_{1}}\left(1-\beta\right)}{\sqrt{1-\theta_{t}}}$.

Then we obtain the upper bound of the third term:

For the fourth term, by using similar inequalities we have $\small{|B_{t}^{\left(i\right)}|\leq\frac{\left(1-\beta\right)\sqrt{C_{1}}}{\sqrt{1-\theta_{t}}}.}$

then with induction, we can find the upper bound for $M_{t}$.

Besides, as for the bound of the first term $M_{1}$, we have

Hence, with inequality (9), and definition of $M_{1}$, it holds that

By combining lemma 7.3, 7.5, 7.7 and definition of $N_{t}$, we have

Then, using lemma 7.9 and 7.11 it holds that

With the inequalities (10), (11), we obtain the desired result.

Let $\tau$ be randomly chosen from $\{1,2,\cdots,T\}$ with equal probabilities $p_{\tau}=1/T$. We have the following estimate:

Note that for any $i=1,2,\cdots,N$, $\|\hat{v}_{t}^{\left(i\right)}\|_{1}=\theta_{t}\|v_{t-1}^{\left(i\right)}\|_{1}+\left(1-\theta_{t}\right)\|\sigma_{t}\|^{2}$ and $\|g_{t}^{\left(i\right)}\|\leq G$.

Then, it is straightforward to prove $\|v_{t}^{\left(i\right)}\|_{1}\leq G^{2}+\epsilon d$.

Then, by using the definition of $x_{\tau}$, we obtain

By using the gradient Lipschitz continuity of $f$, it holds that

For fixed T, by summing up $t$ from $1$ to $T$, we can obtain

we obtain $\small{\frac{2\sqrt{G^{2}+\epsilon d}}{\left(1-\beta\right)\alpha\sqrt{T}}\left(f\left(x_{1}\right)-f^{*}+C_{2}\right)\leq\varepsilon,}$ which gives that

By solving $\left(\frac{\delta_{s}^{\prime}}{\delta_{s}}+\frac{(2-\delta_{w})\delta_{w}^{\prime}}{\delta_{s}\delta_{w}}\right)\frac{2L\sqrt{G^{2}+\epsilon d}C_{3}}{\left(1-\beta\right)}\leq\frac{\varepsilon}{2}$, and setting $K$ to be the same in both directions, we obtain that when $k\leq-\log\left(\frac{24L\sqrt{d}\sqrt{G^{2}\!+\!\epsilon d}C_{3}}{\varepsilon(1-\beta)}\right)$, this equality always holds.

Besides, as it is shown in Lemma 1, $\|\delta_{t}\|\leq\alpha/((1-\gamma)\theta)$. With assumption that $\|Q(x)\|\leq 3/2\|x\|$, when $K\geq\log\left(\alpha/((1-\gamma)\theta)\right)$ we can get a quantizer satisfying Definition 1.

Besides, using Theorem 1, with inequality

we have $T\geq\frac{16\left(G^{2}+\epsilon d\right)}{\left(1-\beta\right)^{2}\alpha^{2}\varepsilon^{2}}\left(f\left(x_{1}\right)-f^{*}+C_{4}\right)^{2}$.

Meanwhile, we transmit $\small{d\log(K-k+1)}$ bits per iteration.

Because when compressor satisfies Definition 3, where $\|Q(x)-x\|\leq(1-\delta)\|x\|$, it holds that $\|Q(x)\|\leq(2-\delta)\|x\|$. Therefore, by setting $\delta^{\prime}=0$, we obtain the desired result.

[]Congliang Chen received the B.S degree in computer science and technology from Peking University, China in 2018. He is working towards a Ph.D. degree of the Computer Information and Engineering at the School of Science and Engineering in the Chinese University of Hong Kong (Shenzhen). His research interest includes distributed optimization, federated learning and machine learning algorithms.

[]Li Shen received his Ph.D. in school of mathematics, South China University of Technology in 2017. He is currently a research scientist at JD Explore Academy, China. Previously, he was a research scientist at Tencent AI Lab, China. His research interests include theory and algorithms for large scale convex/nonconvex/minimax optimization problems, and their applications in statistical machine learning, deep learning, reinforcement learning, and game theory.

[]Wei Liu (M’14-SM’19) is currently a Distinguished Scientist of Tencent and the Director of Ads Multimedia AI at Tencent Data Platform. Prior to that, he has been a research staff member of IBM T. J. Watson Research Center, USA. Dr. Liu has long been devoted to fundamental research and technology development in core fields of AI, including deep learning, machine learning, reinforcement learning, computer vision, information retrieval, big data analytics, etc. To date, he has published extensively in these fields with more than 270 peer-reviewed technical papers, and also issued 27 US patents. He currently serves on the editorial boards of IEEE TPAMI, TNNLS, IEEE Intelligent Systems, and Transactions on Machine Learning Research. He is an Area Chair of top-tier computer science and AI conferences, e.g., NeurIPS, ICML, IEEE CVPR, IEEE ICCV, IJCAI, and AAAI. Dr. Liu is a Fellow of the IAPR, IMA, BCS, RSA, and AAIA, and an Elected Member of the ISI.

[]Zhi-Quan Luo received the B.S. degree in applied mathematics from Peking University, China, and the Ph.D. degree in operations research from MIT in 1989. From 1989 to 2003, he held a faculty position with the ECE Department of McMaster University, Canada. He held a tier-1 Canada Research Chair in information processing from 2001 to 2003. After that, he has been a full professor at the ECE Department, University of Minnesota and held an endowed ADC Chair in digital technology. Currently, he is the Vice President (Academic) of the Chinese University of Hong Kong (Shenzhen) and the director of Shenzhen Research Institute of Big Data (SRIBD). Prof. Luo is a Fellow of IEEE and SIAM. He was elected to Fellow of Royal Society of Canada in 2014 and a Foreign Member of the Chinese Academy of Engineering (CAE) in 2021. He received four best paper awards from the IEEE Signal Processing Society, one best paper award from EUSIPCO, the Farkas Prize from INFORMS and the prize of Paul Y. Tseng Memorial Lectureship in Continuous Optimization as well as some best paper awards from international conferences. In 2021, he was awarded 2020 ICCM Best Paper Award by International Consortium of Chinese Mathematicians. He has published over 350 refereed papers, books and special issues. Prof. Luo has served as an Associate Editor for many internationally recognized journals and the Editor in Chief for IEEE Transactions on Signal Processing. His research mainly addresses mathematical issues in information sciences, with particular focus on the design, analysis and applications of large-scale optimization algorithms. (Email: luozq@cuhk.edu.cn)