On Biased Compression for Distributed Learning

Introduction

In order to achieve state-of-the-art performance, modern machine learning models need to be trained using large corpora of training data, and often feature an even larger number of trainable parameters (Vaswani et al. 2019; Brown et al. 2020). The data is typically collected in a distributed manner and stored across a network of edge devices, as is the case in federated learning (Konečný et al. 2016; McMahan et al. 2017; Li et al. 2019; Kairouz and et al 2019), or collected centrally in a data warehouse composed of a large collection of commodity clusters. In either scenario, communication among the workers is typically the bottleneck.

Motivated by the need for more efficient training methods in traditional distributed and emerging federated environments, we consider optimization problems of the form

with ${\cal P}_{i}$ being the distribution of training data owned by worker $i$. In federated learning applications, these local distributions can be very different and we do not impose any similarity assumption for them.

A fundamental baseline for solving problem (1) is (distributed) gradient descent (GD), performing updates of the form

where $\eta^{k}>0$ is a stepsize. Due to the communication issues inherent to distributed systems, several enhancements to this baseline have been proposed that can better deal with the communication cost challenges of distributed environments, including acceleration (Nesterov 2013; Beck and Teboulle 2009; Allen-Zhu 2017), reducing the number of iterations via momentum, local methods (McMahan et al. 2017; Khaled et al. 2020a; Karimireddy et al. 2019a), reducing the number of communication rounds via performing multiple local updates before each communication round, and communication compression (Seide et al. 2014; Alistarh et al. 2017; Zhang et al. 2017; Lim et al. 2018; Alistarh et al. 2018; Lin et al. 2018; Safaryan and Richtárik 2021), reducing the size of communicated messages via compression operators.

2 Contributions

In this paper we contribute to a better understanding of the latter approach to alleviating the communication bottleneck: communication compression. In particular, we study the theoretical properties of gradient-type methods which employ biased gradient compression operators, such as Top-$k$ sparsification (Alistarh et al. 2018), or deterministic rounding (Sapio et al. 2019). Surprisingly, current Here we refer to the initial online appearance of our work on February of 2020, after which several enhancements were developed. See Section 1.3 for more details. theoretical understanding of such methods is very limited. For instance, there is no general theory of such methods even in the $n=1$ case, only a handful of biased compression techniques have been proposed in the literature, we do not have any theoretical understanding of why biased compression operators could outperform their unbiased counterparts and when. More importantly, there is no good convergence theory for any gradient-type method with a biased compression in the crucial $n>1$ setting.

In this work we address all of the above problems. In particular, our main contributions are:

We then proceed to give a long list of new and known biased (and some unbiased) compression operators which belong to the above classes in Section 2.2. A summary of all compressors considered can be found in Table 3.

In Section 3 we analyze compressed GD in the $n=1$ case for compressors belonging to all three classes under smoothness and strong convexity assumption. Our theorems generalize existing results which hold for unbiased operators in a tight manner, and also recover the rate of GD in this regime. Our linear convergence results are summarized in Table 1.

We ask the question: do biased compressors outperform their unbiased counterparts in theory, and by how much? We answer this question by studying the performance of compressors under various synthetic and empirical statistical assumptions on the distribution of the entries of gradient vectors which need to be compressed. Particularly, we quantify the gains of the Top-$k$ sparsifier when compared against the unbiased Rand-$k$ sparsifier in Section 4.

Finally, we study the important $n>1$ setting in Section 5 and argue by giving a counterexample that a naive application of biased compression to distributed GD might diverge. We then show that distributed SGD method equipped with an error-feedback mechanism (Stich and Karimireddy 2019) provably handles biased compressors. In our main result (Theorem 24; also see Table 2) we consider three learning schedules and iterate averaging schemes to provide three distinct convergence rates. Our analysis provides the first convergence guarantee for distributed gradient-type method which provably converges for biased compressors, and we thus solve a major open problem in the literature.

3 Related work

There has been extensive work related to communication compression, mostly focusing on unbiased compressions (Alistarh et al. 2017) as these are much easier to analyze. In particular, it was shown (Gorbunov et al. 2020a) that both the classical method with unbiased compression (Alistarh et al. 2017) and more advanced modifications (Mishchenko et al. 2019; Horváth et al. 2019b) can be considered as special versions of SGD. Subsequently, the results of (Gorbunov et al. 2020a) for strongly convex problems were transferred to general convex (Khaled et al. 2020b) and non-convex (Li and Richtárik 2020) target functions. In the meantime, works concerning biased compressions show stronger empirical results but with limited or no analysis (Vogels et al. 2019; Lin et al. 2017a; Sun et al. 2019). There have been several attempts trying to address this issue, e.g., Wu et al. 2018 provided analysis for quadratics in distributed setting, Zhao et al. 2019 gave analysis for momentum SGD with a specific biased compression, but under unreasonable assumptions, i.e., bounded gradient norm and memory. The first result that obtained linear rate of convergence for biased compression was done by Karimireddy et al. 2019b, but only for one node and under bounded gradient norm assumption, which was later overcome by Stich and Karimireddy 2019.

After the initial online appearance of our work, there has been several enhancements in the literature. In particular, Ajalloeian and Stich 2021 developed theory for non-convex objectives in the single node setup, Gorbunov et al. 2020b designed a novel error compansated SGD algorithm converging linearly in a more relaxed setting with the help of additional unbiased compressor, Horváth and Richtárik 2021 proposed a simple trick to convert any biased compressor to corresponding induced (unbiased) compressor leading to improved theoretical guarantees. Recently, a new variant of error feedback mechanism was introduced in (Richtárik et al. 2021; Fatkhullin et al. 2021) showing an improved rates for distributed non-convex problems.

4 Basic notation and definitions

We say that it is $\mu$-strongly convex if

Biased Compressors

We instead focus on understanding biased compression operators, or “compressors” in short. We now introduce three classes of biased compressors, the first two are new, which can be seen as natural extensions of unbiased compressors.

As we shall show next, the second inequality in (3) implies ${{\rm E}}\left[\left\|{\cal C}(x)\right\|_{2}^{2}\right]\leq\beta^{2}\left\|x\right\|_{2}^{2}$.

If ${{\rm E}}\left[{\cal C}(x)\right]\neq 0$, this implies $\left\|{{\rm E}}\left[{\cal C}(x)\right]\right\|_{2}\leq\beta\left\|x\right\|_{2}$. Plugging this back into (5), we get (4). If ${{\rm E}}\left[{\cal C}(x)\right]=0$, then from (3) we see that ${{\rm E}}\left[\left\|{\cal C}(x)\right\|_{2}^{2}\right]=0$, and (4) holds trivially. ∎

In the second class, we require the inner product between uncompressed $x$ and compressed ${\cal C}(x)$ vectors to dominate the squared norms of both vectors in expectation.

Finally, in the third class, we require the compression error $\left\|{\cal C}(x)-x\right\|_{2}^{2}$ to be strictly smaller than the squared norm $\left\|x\right\|_{2}^{2}$ of the input vector $x$ in expectation.

This last definition was also considered by Stich et al. 2018; Cordonnier 2018. All three definitions require the compressed vector ${\cal C}(x)$ to be in the neighborhood of the uncompressed vector $x$ so that initial information is preserved with some accuracy. We now establish several basic properties and connections between the classes. We first show that the three classes of biased compressors defined above are equivalent in the following sense: a compressor from any of those three classes can be shown to belong to all three classes with different parameters and after possible scaling.

Let $\lambda>0$ be a free scaling parameter.

Let us prove this implications for each class separately.

Let us choose any $x\neq 0$ and observe that (3) implies that ${{\rm E}}\left[{\cal C}(x)\right]\neq 0$. Further, from (3) we get the bounds

where the second inequality is due to Cauchy-Schwarz, and the last inequality follows by applying Jensen inequality.

Minimizing the above expression in $\lambda$, we get $\lambda=\frac{1}{\beta}$, and the result follows.

where the first and third inequalities follow from (6) and the third and the last from Cauchy-Schwarz inequality with Jensen inequality.

If we choose $\lambda=\frac{1}{\beta}$, then we can continue as follows:

Pick $x\neq 0$. Since $0\leq{{\rm E}}\left[\left\|{\cal C}(x)-x\right\|_{2}^{2}\right]\leq\left(1-\frac{1}{\delta}\right)\left\|x\right\|_{2}^{2}$ and we assume $\delta>0$, we must necessarily have $\delta\geq 1$.

Next, we show that, with a proper scaling, any unbiased compressor also belongs to all the three classes of biased compressors.

Given any $\lambda>0$, consider the scaled operator $\lambda{\cal C}$. We have

Given any $\lambda>0$, consider the scaled operator $\lambda{\cal C}$. We have

Given $\lambda>0$ such that $\lambda\zeta<2$, consider the scaled operator $\lambda{\cal C}$. We have

2 Examples of biased compressors: old and new

For $k\in[d]\coloneqq\{1,\dots,d\}$, the unbiased random (aka Rand-$k$) sparsification operator is defined via

Let $S\subseteq[d]$ be a random set, with probability vector $p\coloneqq(p_{1},\dots,p_{d})$, where $p_{i}\coloneqq\Prob(i\in S)>0$ for all $i$ (such a set is called a proper sampling (Richtárik and Takáč 2016)). Define biased random sparsification operator via

Adaptive random sparsification is defined via

Greedy (aka Top-$k$) sparsification operator is defined via

where coordinates are ordered by their magnitudes so that $|x_{(1)}|\leq|x_{(2)}|\leq\cdots\leq|x_{(d)}|$.

Notice that $\zeta$ is minimizing for exponential roundings $a_{k}=b^{k}$ with some basis $b>1$, in which case $\zeta=\tfrac{1}{4}\left(b+\nicefrac{{1}}{{b}}+2\right)$.

In the special case of exponential rounding $a_{k}=b^{k}$ with some base $b>1$, we get

Natural compression operator ${\cal C}_{nat}$ of Horváth et al. 2019a is the special case of general unbiased rounding operator (12) when $b=2$. So,

For $b>1$, define general exponential dithering operator with respect to $l_{p}$-norm and with $s$ exponential levels $0<b^{1-s}<b^{2-s}<\dots<b^{-1}<1$ via

where the random variable $\xi(t)$ for $t\in[b^{-u-1},b^{-u}]$ is set to either $b^{-u-1}$ or $b^{-u}$ with probabilities proportional to $b^{-u}-t$ and $t-b^{-u-1}$, respectively.

Natural dithering introduced by Horváth et al. 2019a without norm compression is the spacial case of general exponential dithering (14) when $b=2$.

Ternary quantization of Wen et al. 2017 is the extreme case of general exponential dithering (14) with $s=1$ levels and $b=1$.

Top-$k$ combined with exponential dithering. Let ${\cal C}_{top}$ be the Top-$k$ sparsification operator (11) and ${\cal C}_{dith}$ be general exponential dithering operator (14) with some base $b>1$ and parameter $\zeta_{b}$ from (15). Define a new compression operator as the composition of these two:

Gradient Descent with Biased Compression

As we discussed in previous section, compression operators can have different equivalent parametrizations. Next, we aim to investigate the influence of those parametrizations on the theoretical convergence rate of an algorithm employing compression operators. To achieve clearer understanding of the interaction of compressor parametrization and convergence rate, we first consider the single node, unconstrained optimization problem

Superiority of Biased Compressors Under Statistical Assumptions

Here we highlight some advantages of biased compressors by comparing them with their unbiased cousins. We evaluate compressors by their average capacity of preserving the gradient information or, in other words, by expected approximation error they produce. In the sequel, we assume that gradients have i.i.d. coordinates drawn from some distribution.

We now compare two sparsification operators: Rand-$k$ (8) which is unbiased and which we denote as ${\cal C}_{rnd}^{k}$, and Top-$k$ (11) which is biased and which we denote as ${\cal C}_{top}^{k}$. We define variance of the approximation error of $x$ via

Expectations in these expressions are taken with respect to the randomization of the compression operator rather than input vector $x$. Clearly, there exists $x$ for which these two operators incur identical variance, e.g. $x_{1}=\dots=x_{d}$. However, in practice we apply compression to gradients $x$ which evolve in time, and which may have heterogeneous components. In such situations, $\omega_{top}^{k}(x)$ could be much smaller than $\omega_{rnd}^{k}(x)$. This motivates a quantitative study of the average case behavior in which we make an assumption on the distribution of the coordinates of the compressed vector.

We first consider the case of uniform and exponentially distributed entries, and quantify the difference.

(b) If they follow standard exponential distribution, then

Now we compare these two sparsification methods on an empirical bases and show the significant advantage of greedy sparsifier against random sparsifier. We assume that coordinates of to-be-compressed vector are i.i.d. Gaussian random variables.

First, we compare the savings $s_{top}^{k}$ and $s_{rnd}^{k}$ of these compressions. For random sparsification, we have

where $\mu$ and $\sigma^{2}$ are the mean and variance of the Gaussian distribution. For computing ${{\rm E}}\left[s_{top}^{k}(x)\right]$, we use the probability density function of $k$-th order statistics (see (31) or (2.2.2) of (Arnold et al. 1992)). Table 4 shows that Top-$3$ and Top-$5$ sparsifiers “save” $3\times$–$40\times$ more information in expectation and the factor grows with the dimension.

Next we compare normalized variances $\frac{\omega_{top}^{k}(x)}{\left\|x\right\|_{2}^{2}}$ and $\frac{\omega_{rnd}^{k}(x)}{\left\|x\right\|_{2}^{2}}$ for randomly generated Gaussian vectors. In an attempt to give a dimension independent comparison, we compare them against the average number of encoding bits per coordinate, which is quite stable with respect to the dimension. Figure 1 reveals the superiority of greedy sparsifier against the random one.

We obtained various gradient distributions via logistic regression (mushrooms LIBSVM dataset) and least squares. We used the sklearn package and built Gaussian smoothing of the practical gradient density. The second moments, i.e. energy “saving”, were already calculated from it by formula for density function of $k$-order statistics, see Appendix A.4 or (Arnold et al. 1992). We conclude experiments for Top-5 and Rand-5, see Figure 2 for details.

2 New compressor: Top-kk combined with dithering

Distributed Setting

We now focus attention on a distributed setup with $n$ machines, each of which owns non-iid data defining one loss function $f_{i}$. Our goal is to minimize the average loss:

Perhaps the most straightforward extension of CGD to the distributed setting is to consider the method

where $D\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}\left\|\nabla f_{i}(x^{\star})\right\|_{2}^{2}$ (Gorbunov et al. 2020a). In particular, in the overparameterized setting when $D=0$, the method converges to the exact solution, and does so at the same rate as GD as long as $\zeta={\cal O}(n)$. These results hold even if a regularizer is considered, and a proximal step is added to DCGD. Moreover, as shown by Mishchenko et al. 2019 and Horváth et al. 2019b, a variance reduction technique can be devised to remove the neighborhood convergence and replace it by convergence to $x^{\star}$, at the negligible additional cost of ${\cal O}((\zeta-1)\log\frac{1}{\epsilon})$.

2 Failure of DCGD with biased compressors

However, as we now demonstrate by giving some counter-examples, DCGD may fail if the compression operators are allowed to be biased. In the first example below, DCGD used with the Top-1 compressor diverges at an exponential rate.

where $a=(-3,2,2)$, $b=(2,-3,2)$ and $c=(2,2,-3)$. Let the starting iterate be $x^{0}=(t,t,t)$, where $t>0$. Then

Using the Top-1 compressor, we get ${\cal C}(\nabla f_{1}(x^{0}))=\frac{t}{2}(-11,0,0)$, ${\cal C}(\nabla f_{2}(x^{0}))=\frac{t}{2}(0,-11,0)$ and ${\cal C}(\nabla f_{3}(x^{0}))=\frac{t}{2}(0,0,-11)$. The next iterate of DCGD is

Since $\eta>0$, the entries of $x^{k}$ diverge exponentially fast to $+\infty$.

The above counter-example can be extended to the case of Top-$d_{1}$ when $d_{1}<\left\lceil\frac{d}{2}\right\rceil$.

Fix the dimension $d\geq 3$ and let $n=\binom{d}{d_{1}}$ be the number of nodes, where $d_{1}<\left\lceil\frac{d}{2}\right\rceil$ and $d_{2}=d-d_{1}>d_{1}$. Choose positive numbers $b,\;c>0$ such that

where sets $I_{j}\subset[d],\;j\in[n]$ are all possible $d_{1}$-subsets of $[d]$ enumerated in some way. Define

and let the initial point be $x^{0}=te,\;t>0$, where $e=\sum_{i=1}^{d}e_{i}$ is the vector of all $1$s. Then

Since $|2(-b)+1|>|2c+1|$, then using the Top-$d_{1}$ compressor, we get

Since $\eta>0$ and $b>1$, the entries of $x^{k}$ diverge exponentially fast to $+\infty$.

Finally, we present more general counter-example with different type of failure for DCGD when non-randomized compressors are used.

Consider the distributed optimization problem (17) with $n=m$ devices and with the following strongly convex loss functions

Then $\nabla f_{i}(x)=v_{i}+x$ and $\nabla f(x)=\frac{1}{n}\sum_{i=1}^{n}v_{i}+x$. Hence, the optimal point $x^{*}=-\frac{1}{n}\sum_{i=1}^{n}v_{i}\neq 0$. However, it can be easily checked that, with initialization $x_{0}=0$, we have

Thus, when initialized at $x_{0}=0$, not only DCGD does not converge to the solution $x^{*}\neq 0$, it remains stuck at the same initial point for all iterates, namely $x^{k}=x^{0}=0$ for all $k\geq 1$.

Condition (18) can be easily satisfied for specific biased compressors. For instance, Top-$1$ satisfies (18) with $v_{1}=\left[\begin{smallmatrix}1\\ 4\end{smallmatrix}\right]$, $v_{2}=\left[\begin{smallmatrix}-1\\ -2\end{smallmatrix}\right]$, $v_{3}=\left[\begin{smallmatrix}1\\ -2\end{smallmatrix}\right]$.

The above examples suggests that one needs to devise a different approach to solving the distributed problem (17) with biased compressors. We resolve this problem by employing a memory feedback mechanism.

3 Error Feedback

We show that distributed version of Distributed SGD wtih Error-Feedback (Karimireddy et al. 2019b), displayed in Algorithm 1, is able to resolve the issue. Moreover, this algorithm allows for the computation of stochastic gradients. Each step starts with all machines $i$ in parallel computing a stochastic gradient $g_{i}^{k}$ of the form

where $\nabla f_{i}(x^{k})$ is the true gradient, and $\xi_{i}^{k}$ is a stochastic error. Then, this is multiplied by a stepsize $\eta^{k}$ and added to the memory/error-feedback term $e_{i}^{k}$, and subsequently compressed. The compressed messages are communicated and aggregated. The difference of message we wanted to send and its compressed version becomes stored as $e_{i}^{k+1}$ for further correction in the next communication round. The output $\overline{x}^{K}$ is an ergodic average of the form

4 Complexity theory

We assume the stochastic error $\xi_{i}^{k}$ in (19) satisfies the following condition.

Stochastic error $\xi_{i}^{k}$ is unbiased, i.e. ${{\rm E}}\left[\xi_{i}^{k}\right]=0$, and for some constants $B,C\geq 0$

Note that this assumption is much weaker than the bounded variance assumption (i.e., ${{\rm E}}\left[\left\|\xi_{i}^{k}\right\|_{2}^{2}\right]\leq C$) and bounded gradient assumption (i.e., ${{\rm E}}\left[\left\|g_{i}^{k}\right\|_{2}^{2}\right]\leq C$). We can now state the main result of this section. To the best of our knowledge, this was an open problem: we are not aware of any convergence results for distributed optimization that tolerate general classes of biased compression operators and have reasonable assumptions on the stochastic gradient.

Let $\{x^{k}\}_{k\geq 0}$ denote the iterates of Algorithm 1 for solving problem (1), where each $f_{i}$ is $L$-smooth and $\mu$-strongly convex. Let $x^{\star}$ be the minimizer of $f$ and let $f^{\star}\coloneqq f(x^{\star})$ and

${\cal O}(\frac{1}{k})$ stepsizes & ${\cal O}(k)$ weights. Let, for all $k\geq 0$, the stepsizes and weights be set as $\eta^{k}=\frac{4}{\mu(\kappa+k)}$ and $w^{k}=\kappa+k$, respectively, where $\kappa=\frac{56(2\delta+B)L}{\mu}$. Then

where $A_{1}\coloneqq\frac{L^{2}(2\delta+B)^{2}}{\mu}\left\|x^{0}-x^{\star}\right\|_{2}^{2}$ and $A_{2}\coloneqq\frac{C\left(1+\nicefrac{{1}}{{n}}\right)+D\left(\nicefrac{{2B}}{{n}}+3\delta\right)}{\mu}$.

${\cal O}(1)$ stepsizes & ${\cal O}(e^{-k})$ weights. Let, for all $k\geq 0$, the stepsizes and weights be set as $\eta^{k}=\eta$ and $w^{k}=(1-\mu\eta/2)^{-(k+1)}$, respectively, where $\eta\leq\frac{1}{14(2\delta+B)L}$. Then

where $A_{3}\coloneqq L(2\delta+B)\left\|x^{0}-x^{\star}\right\|_{2}^{2}$ and $A_{4}\coloneqq\frac{28L(2\delta+B)}{\mu}$.

${\cal O}(1)$ stepsizes & equal weights. Let, for all $k\geq 0$, the stepsizes and weights be set as $\eta^{k}=\eta$ and $w^{k}=1$, respectively, where $\eta\leq\frac{1}{14(2\delta+B)L}$. Then

where $A_{5}\coloneqq\sqrt{C\left(1+\nicefrac{{1}}{{n}}\right)+D\left(\nicefrac{{2B}}{{n}}+3\delta\right)}\left\|x^{0}-x^{\star}\right\|_{2}$.

Let us make a few observations on these results. First, Algorithm 1 employing general biased compressors and error feedback mechanism indeed resolves convergence issues of DCGD method by converging the optimal solution $x^{*}$. Second, note that the choice of stepsizes $\eta^{k}$ and weights $w^{k}$ leading to convergence is not unique and several schedules are feasible. Third, all the rates are sublinear and based on the second rate (ii) above, linear convergence is guaranteed if $C=D=0$. Based on (24), one setup when the condition $C=0$ holds is when all devices compute full local gradients (i.e., $g_{i}^{k}=\nabla f_{i}(x^{k})$). Furthermore, the condition $D=0$ is equivalent to $\nabla f_{i}(x^{\star})=0$ for all $i\in[n]$, which is typically satisfied for over-parameterized models. Lastly, under these two assumptions (i.e., devices can compute full local gradients and the model is over-parameterized), we show that distributed SGD method with error feedback converges with the same ${\cal O}\left(\delta\frac{L}{\mu}\log\frac{1}{\epsilon}\right)$ linear rate as single node CGD algorithm. To the best of our knowledge, this was the first regime where distributed first order method with biased compression is guaranteed to converge linearly.

Experiments

In Sections 6.1–6.4, we present our experiments, which are primarily focused on supporting our theoretical findings. Therefore, we simulate these experiments on one machine which enable us to do rapid direct comparisons against the prior methods. In more details, we use the machine with 24 Intel(R) Xeon(R) Gold 6146 CPU @ 3.20GHz cores and GPU GeForce GTX 1080 Ti. Section 6.5 is devoted to real experiments with a large model and big data. For these experiments, we use a computational cluster with 10 GPUs Tesla T4. We implement all methods in Python 3.7 using Pytorch Paszke et al. 2019.

Motivated by our theoretical results in Section 4, we show that similar behaviour can be seen in the empirical variance of gradients. We run 2 sets of experiments with Resnet18 on CIFAR10 dataset. In Figure 6, we display empirical variance, which is obtained by running a training procedure with specific compression. We compare unbiased and biased compressions with the same communication complexities–deterministic with classic/unbiased ${\cal C}_{\rm nat}$ and Top-$k$ with Rand-$k$ with $k$ to be $\nicefrac{{1}}{{5}}$ of coordinates. One can clearly see, that there is a gap in empirical variance between biased and unbiased methods, similar to what we have shown in theory, see Section 4.

2 Error-feedback is needed in distributed training with biased compression

The next experiment shows the need of error-feedback for methods with biased compression operators. Based on Example 1, error feedback is necessary to prevent divergence from the optimal solution. Figure 4 displays training/test loss and accuracy for VGG19 on CIFAR10 with data equally distributed among $4$ nodes. We use plain SGD with a default step size equal to $0.01$ for all methods, i.e. Top-$5$ with and without error feedback, Rand-$5$ and no compression. As suggested by the counterexample, not using error feedback can really hurt the performance when biased compressions are used. Also note, that performance of Rand-$5$ is significantly worse than Top-$5$.

3 Top-kk mixed with natural dithering saves in communication significantly

Next, we experimentally show the superiority of our newly proposed compressor–Top-$k$ combined with natural dithering. We compare this against current state-of-the-art for low bandwidth approach Top-$k$ for some small $k$. In Figure 5, we plot comparison of $5$ methods–Top-$k$, Rand-$k$, natural dithering, Top-$k$ combined with natural dithering and plain SGD. We use $2$ levels with infinity norm for natural dithering and $k=5$ for sparsification methods. For all the compression operators, we train VGG11 on CIFAR10 with plain SGD as an optimizer and default step size equal to $0.01$. We can see that adding natural dithering after Top-$k$ has the same effect as the natural dithering comparing to no compression, which is a significant reduction in communications without almost no effect on convergence or generalization. Using this intuition, one can come to the conclusion that Top-$k$ with natural dithering is the best compression operator for any bandwidth, where we adjust to given bandwidth by adjusting $k$. This exactly matches with our previous theoretical variance estimates displayed in Figure 3.

4 Theoretical behavior predicts the actual performance in practice

In the next experiment, we provide numerical results to further show that our predicted theoretical behavior matches the actual performance observed in practice. We run two regression experiments optimized by gradient descent with step-size $\eta=\frac{1}{L}$. We use a slightly adjusted version of Theorem 19 with adaptive step-sizes, namely

Note that this is the direct consequence of our analysis. We apply this property to display the theoretical convergence. In the first experiment depicted in Figure 7, we randomly generate random square matrix $A$ of dimension $100$ where it is constructed in the following way: we sample random diagonal matrix $D$, which elements are independently sampled from the uniform distribution $(1,10)$, $(1,100)$, and $(1,1000)$, respectively. $A$ is then constructed using $Q^{\top}DQ$, where $P=QR$ is a random matrix and $QR$ is obtained using QR-decomposition. The label $y$ is generated the same way from the uniform distribution $(0,1)$. The optimization objective is then

For the second experiment shown in Figure 8, we run standard linear regression on two scikit-learn datasets–Boston and Diabetes–and applied data normalization as the preprocessing step.

Looking into Figures 7 and 8, one can clearly see that as predicted by our theory, biased compression with less empirical variance leads to better convergence in practice and the gap almost matches the improvement.

5 Transformer training

In the last experiment, we work with a real big model. In particular, we train ALBERT-large (Lan et al. 2020) (18M parameters) with layer sharing on a combination of Bookcorpus (Zhu et al. 2015) and Wikipedia (Devlin et al. 2018) datasets. We use the same optimizer (LAMB) and the same tuning for it as in the original paper (Lan et al. 2020). Our goal is to find an unbiased and biased operators such that we maximize the improvement in terms of communication cost without losing much in terms of training quality. In this case, we include in the communication cost both the time to perform the communication round and the time to perform the compression and decompression operations. It is important to note that we do not compress packages with gradients corresponding to LayerNorm scales, but this is less than $1$ percent of the whole package. Among unbiased compressors, we try natural compression (Section 2.2 (g)) and random sparsification (Section 2.2 (a)). The best result is shown by natural compression, which compresses the packages by a factor of $4$. The Rand-$25$ operator (which also compresses the information by a factor of $4$) performs much worse even with the use of the error feedback technique. For communications with natural compression, we use the classical allreduce procedure. Among unbiased compressors, we try Top-$k$ sparsification (Section 2.2 (d)) and Power compression (Vogels et al. 2019). The best result is shown by Power compression with the rank parameter $r{=}8$ and the error feedback. The organization of communications (allreduce procedures) occurs as in the original paper (Vogels et al. 2019). We measure how the training loss changes (Figure 9) as well as at the end of training we evaluate the final performance for each model on several popular tasks from (Wang et al. 2018) (Table 5). The results show that the use of biased compression can significantly reduce the communication time cost compared to uncompressed and even unbiased compression setups. At the same time, the quality of the training does not drop much.

Appendix

A.2 Smoothness

If convexity is assumed as well, then the following inequalities hold:

A.3 Useful inequalities

A.4 Facts from order statistics

For i.i.d. samples $x_{1},x_{2},\ldots,x_{d}$ from an absolutely continuous distribution with probability density function $\phi$ and cumulative distribution function $\Phi$ let $x_{(1)}\leq x_{(2)}\leq\dots\leq x_{(d)}$ be the order statistics obtained by arranging samples in increasing order of magnitude. Then the following expressions give the density function of $x_{(i)}$ ($1\leq i\leq d$)

and the joint density function of all $d$ order statistics

Appendix B Proofs for Section 2.2

From the definition of $k$-nice sampling we have $p_{i}\coloneqq\Prob\left(i\in S\right)=\tfrac{k}{d}$. Hence

B.2 Proof of Lemma 9: Biased Random Sparsification

Let $S\subseteq[d]$ be a proper sampling with probability vector $p=(p_{1},\dots,p_{d})$, where $p_{i}\coloneqq\Prob(i\in S)>0$ for all $i$. Then

Letting $q\coloneqq\min_{i}p_{i}$, we get

B.3 Proof of Lemma 10: Adaptive Random Sparsification

From the definition of the compression operator, we have

whence $\beta=1$. Furthermore, by Chebychev’s sum inequality, we have

B.4 Proof of Lemma 11: Top-kk sparsification

Clearly, $\left\|{\cal C}(x)\right\|_{2}^{2}=\sum_{i=d-k+1}^{d}x_{(i)}^{2}$ and $\left\|{\cal C}(x)-x\right\|_{2}^{2}=\sum_{i=1}^{d-k}x_{(i)}^{2}$. Hence

B.5 Proof of Lemma 12: General Unbiased Rounding

The unbiasedness follows immediately from the definition (12)

Since the rounding compression operator ${\cal C}$ applies to each coordinate independently, without loss of generality we can consider the compression of scalar values $x=t>0$ and show that ${{\rm E}}\left[{\cal C}(t)^{2}\right]\leq\zeta\cdot t^{2}$. From the definition we compute the second moment as follows

Checking the optimality condition, one can show that the maximum is achieved at

which being the harmonic mean of $a_{k}$ and $a_{k+1}$, is in the range $[a_{k},a_{k+1}]$. Plugging it to the expression for variance we get

Thus, the parameter $\zeta$ for general unbiased rounding would be

B.6 Proof of Lemma 13: General Biased Rounding

From the definition (13) of compression operator ${\cal C}$ we derive the following inequalities

It can be easily checked that $\left(1-\frac{a_{k}}{t}\right)^{2}$ is an increasing function and $\left(1-\frac{a_{k+1}}{t}\right)^{2}$ is a decreasing function of $t\in[a_{k},a_{k+1}]$. Thus, the maximum is achieved when they are equal. In contrast to unbiased general rounding, it happens at the middle of the interval,

Given this, the parameter $\delta$ can be computed from

B.7 Proof of Lemma 15: General Exponential Dithering

The proof goes with the same steps as in Theorem 4 of Horváth et al. 2019a. To show the unbiasedness of ${\cal C}$, first we show the unbiasedness of $\xi(t)$ for $t\in$ in the same way as (33) was done. Then we note that

To compute the parameter $\zeta$, we first estimate the second moment of $\xi$ as follows:

Then we use this bound to estimate the second moment of compressor ${\cal C}$:

where $r=\min(p,2)$ and Hölder’s inequality is used to bound $\|x\|_{p}\leq d^{\nicefrac{{1}}{{p}}-\nicefrac{{1}}{{2}}}\left\|x\right\|_{2}$ in case of $0\leq p\leq 2$ and $\|x\|_{p}\leq\left\|x\right\|_{2}$ in the case $p\geq 2$.

B.8 Proof of Lemma 16: Top-kk Combined with Exponential Dithering

From the unbiasedness of general dithering operator ${\cal C}_{dith}$ we have

from which we conclude $\langle{{\rm E}}\left[{\cal C}(x)\right],x\rangle=\langle{\cal C}_{top}(x),x\rangle=\left\|{\cal C}_{top}(x)\right\|_{2}^{2}$. Next, using Lemma 15 on exponential dithering we get

which implies $\beta=\zeta_{b}$. Using Lemma 11 we show $\gamma=\tfrac{k}{d}$ as $\langle{{\rm E}}\left[{\cal C}(x)\right],x\rangle=\left\|{\cal C}_{top}(x)\right\|_{2}^{2}\geq\tfrac{k}{d}\left\|x\right\|_{2}^{2}$. Utilizing the derivations (34) and (35) it can be shown that ${{\rm E}}\left[\left\|{\cal C}_{dith}(x)\right\|_{2}^{2}\right]\geq\left\|x\right\|_{2}^{2}$ and therefore

Hence, $\alpha=\tfrac{k}{d}$. To compute the parameter $\delta$ we use Theorem 6, which yields $\delta=\tfrac{\beta}{\gamma}=\tfrac{d}{k}\zeta_{b}$.

Appendix C Proofs for Section 3

Letting $g=\nabla f(x)$, we have Alternatively, we can write $\displaystyle{{\rm E}}\left[f\left(x-\eta{\cal C}(g)\right)\right]$ $\displaystyle\leq$ $\displaystyle f(x)-\eta\langle{{\rm E}}\left[{\cal C}(g)\right],g\rangle+\frac{\eta^{2}L}{2}{{\rm E}}\left[\left\|{\cal C}(g)\right\|_{2}^{2}\right]$ $\displaystyle\overset{\eqref{eq:alpha-beta}}{\leq}$ $\displaystyle f(x)-\frac{\eta}{\beta}{{\rm E}}\left[\left\|{\cal C}(g)\right\|_{2}^{2}\right]+\frac{\eta^{2}L}{2}{{\rm E}}\left[\left\|{\cal C}(g)\right\|_{2}^{2}\right]$ $\displaystyle=$ $\displaystyle f(x)-\frac{\eta}{\beta}\left(1-\frac{\eta\beta L}{2}\right){{\rm E}}\left[\left\|{\cal C}(g)\right\|_{2}^{2}\right]$ $\displaystyle\overset{\eqref{eq:alpha-beta}}{\leq}$ $\displaystyle f(x)-\frac{\alpha}{\beta}\eta\left(1-\frac{\eta\beta L}{2}\right)\left\|g\right\|_{2}^{2}.$ Both approaches lead to the same bound.

Since $f$ is $\mu$-strongly convex, $\left\|\nabla f(x^{k})\right\|_{2}^{2}\geq 2\mu(f(x^{k})-f(x^{\star}))$. Combining this with Lemma 25 applied to $x=x^{k}$ and $g=\nabla f(x^{k})$, we get

Since $f$ is $\mu$-strongly convex, $\left\|\nabla f(x^{k})\right\|_{2}^{2}\geq 2\mu(f(x^{k})-f(x^{\star}))$. Combining this with Lemma 26 applied to $x=x^{k}$ and $g=\nabla f(x^{k})$, we get

Subtracting $\left\|g\right\|_{2}^{2}$ from both sides, and multiplying both sides by $\frac{\eta}{2}$ (now we assume that $\eta>0$), we get

Assuming that $\eta L\leq 1$, we can combine this with (37) and the lemma is proved.

Since $f$ is $\mu$-strongly convex, $\left\|\nabla f(x^{k})\right\|_{2}^{2}\geq 2\mu(f(x^{k})-f(x^{\star}))$. Combining this with Lemma 27 applied to $x=x^{k}$ and $g=\nabla f(x^{k})$, we get

Appendix D Proofs for Section 4

(a) As it was already mentioned, we have the following expressions for $\omega_{rnd}^{k}$ and $\omega_{top}^{k}$:

The expected variance ${{\rm E}}\left[\omega_{rnd}^{k}\right]$ for Rand-$k$ is easy to compute as all coordinates are independent and uniformly distributed on $$:

In order to compute the expected variance ${{\rm E}}\left[\omega_{top}^{k}\right]$ for Top-$k$, we use the following formula from order statistics (see (31), (32) or (2.2.2), (2.2.3) of Arnold et al. 1992) see also https://en.wikipedia.org/wiki/Order_statistic, https://www.sciencedirect.com/science/article/pii/S0167715212001940

Combining (39) and (41) completes the first relation. Thus, on average (w.r.t. uniform distribution) Top-$k$ has roughly $\left(1-\nicefrac{{k}}{{d}}\right)^{2}$ times less variance than Rand-$k$.

For the second relation, we use (38) and (40) for $i=d$ and get

Clearly, one can extend this for any $k\in[d]$.

(b) Recall that for the standard exponential distribution (with $\lambda=1$) probability density function (PDF) is given as follows:

Both mean and variance can be shown to be equal to $1$. The expected saving ${{\rm E}}\left[s^{1}_{rnd}\right]$ can be computed directly:

To compute the expected saving ${{\rm E}}\left[s^{1}_{top}(x)\right]={{\rm E}}\left[x^{2}_{(d)}\right]$ we prove the following lemma:

Let $x_{1},\,x_{2},\,\dots,\,x_{d}$ be an i.i.d. sample from the standard exponential distribution and

where $x_{(0)}\coloneqq 0$. Then $y_{1},\,y_{2},\,\dots,\,y_{d}$ is an i.i.d. sample from the standard exponential distribution.

The joint density function of $x_{(1)},\ldots,x_{(d)}$ is given by (see (32))

Next we express variables $x_{(i)}$ using new variables $y_{i}$

Then the joint density $\psi_{y_{1},\ldots,y_{d}}(u)=\psi_{y_{1},\ldots,y_{d}}(u_{1},\dots,u_{d})$ of new variables $y_{1},\ldots,y_{d}$ is given as follows

Notice that $\sum\limits_{i=1}^{d}u_{i}=\sum\limits_{i=1}^{d}(Au)_{i}$ and $|\textrm{det}\,A|=\nicefrac{{1}}{{d!}}$. Hence

which means that variables $y_{1},\ldots y_{d}$ are independent and have standard exponential distribution. ∎

Using this lemma we can compute the mean and the second moment of $x_{(d)}=\sum_{i=1}^{d}\frac{y_{i}}{d-i+1}$ as follows

In this section, we include our analysis for the Distributed SGD with biased compression. Our analysis is closely related to the analysis of Stich and Karimireddy 2019.

We start with the definition of some auxiliary objects:

The sequence $\{a^{k}\}_{k\geq 0}$ of positive values is $\tau$-slow decreasing for parameter $\tau$:

The sequence $\{a^{k}\}_{k\geq 0}$ of positive values is $\tau$-slow increasing for parameter $\tau$:

Taking the conditional expectation conditioned on previous iterates, we get

Given the unbiased stochastic gradient (${{\rm E}}\left[\xi_{i}^{k}\right]=0$):

Using that $\xi_{i}^{k}$ mutually independent and ${{\rm E}}\left[\xi_{i}^{k}\right]=0$ we have:

All $f_{i}$ are $L$-smooth and $\mu$-strongly convex, thus $f$ is $L$-smooth and $\mu$-strongly convex. We can rewrite $\frac{1}{n}\sum\limits_{i=1}^{n}\left\|\nabla f_{i}(x^{k})\right\|_{2}^{2}$:

Using definition of $D=\frac{1}{n}\sum_{i=1}^{n}\left\|\nabla f_{i}(x^{*})\right\|_{2}^{2}$:

Using (28) with $\xi=\nicefrac{{1}}{{2L}}$ and $L$-smothness of $f$ (27):

The lemma follows by the choice $\eta^{k}\leq\frac{1}{4L\left(1+\nicefrac{{2B}}{{n}}\right)}$ and $L\geq\mu$. ∎

$\eta^{k}\leq\frac{1}{14(2\delta+B)L}$, $\forall k\geq 0$ and $\{(\eta^{k})^{2}\}_{k\geq 0}$ – $2\delta$-slow decreasing. Then

Furthermore, for any $4\delta$-slow increasing non-negative sequence $\{w^{k}\}_{k\geq 0}$ it holds:

We prove the first part of the statement:

Here we have taken into account that the operator of full expectation is a combination of operators of expectation by the randomness of the operator and the randomness of the stochastic gradient, i.e. ${{\rm E}}\left[\cdot\right]={{\rm E_{C}}}\left[{{\rm E_{\nabla}}}\left[\cdot\right]\right]$. Given the unbiased stochastic gradient (${{\rm E}}\left[\xi_{i}^{k}\right]=0$):

Using the recurrence for $\frac{1}{n}\sum\limits_{i=1}^{n}\left\|e_{i}^{k}\right\|_{2}^{2}$ , and let $\xi=\frac{1}{2(\delta-1)}$, then $(1+1/\xi)\leq 2\delta$, and $(1-1/\delta)(1+\xi)=(1-\nicefrac{{1}}{{2\delta}})$ we have

For $2\delta$-slow decreasing $\{(\eta^{k})^{2}\}_{k\geq 0}$ by definition (42) we get that $(\eta^{j})^{2}\leq(\eta^{k})^{2}\left(1+\frac{1}{4\delta}\right)^{k-j}$. Due to the fact that $(1-\nicefrac{{1}}{{2\delta}})(1+\nicefrac{{1}}{{4\delta}})\leq(1-\nicefrac{{1}}{{4\delta}})$, we have:

As the last step, we use formula for geometric progression in the following way:

By observing that the choice of the stepsize $\eta^{k}\leq\frac{1}{14(2\delta+B)L}$:

which concludes the proof of (54). For the second part, we use the previous results. Summing over all $k$:

For $2\delta$-slow decreasing $\{(\eta^{k})^{2}\}_{k\geq 0}$, it holds $(\eta^{k-1})^{2}\leq(\eta^{k})^{2}\bigl(1+\frac{1}{4\delta}\bigr)$ which follows from (42) and $\eta^{k-1}\leq\eta^{k}\bigl(1+\frac{1}{4\delta}\bigr)$ and for $4\delta$-slow increasing $\{w^{k}\}_{k\geq 0}$ by (43) we have $w^{k}\leq w^{k-j}\bigl(1+\frac{1}{8\delta}\bigr)^{j}$. Then

Observing $\sum_{j=0}^{\infty}(1-\nicefrac{{1}}{{8\delta}})^{j}\leq 8\delta$ and using $\nicefrac{{\delta-1}}{{2\delta+B}}\leq\nicefrac{{1}}{{2}}$ concludes the proof. ∎

For decreasing stepsizes $\bigl\{\eta^{k}\coloneqq\frac{2}{a(\kappa+k)}\bigr\}_{k\geq 0}$, and weights $\{w_{k}\coloneqq(\kappa+k)\}_{k\geq 0}$ for parameters $\kappa\geq 1$, it holds for every non-negative sequence $\{r^{k}\}_{k\geq 0}$ and any $a>0$, $c\geq 0$ that

where $W^{K}\coloneqq\sum_{k=0}^{K}w^{k}$.

By plugging in the definitions of $\eta^{k}$ and $w^{k}$ in $\Psi^{K}$, we end up with the following telescoping sum:

The lemma now follows from $(\kappa-1)^{2}\leq\kappa^{2}$ and $W^{K}=\sum_{k=0}^{K}(\kappa+k)=\frac{(2\kappa+K)(K+1)}{2}\geq\frac{K(K+1)}{2}\geq\frac{K^{2}}{2}$. ∎

For every non-negative sequence $\{r^{k}\}_{k\geq 0}$ and any parameters $d\geq a>0$, $c\geq 0$, $K\geq 0$, there exists a constant $\eta\leq\frac{1}{d}$, such that for constant stepsizes $\{\eta^{k}=\eta\}_{k\geq 0}$ and weights $w^{k}\coloneqq(1-a\eta)^{-(k+1)}$ it holds

By plugging in the values for $\eta^{k}$ and $w^{k}$, we observe that we again end up with a telescoping sum and estimate

where we used the estimate $W^{K}\geq w^{K}\geq(1-a\eta)^{-K}\geq\exp[a\eta K]$ for the last inequality. The lemma now follows by carefully tuning $\eta$. ∎

For every non-negative sequence $\{r^{k}\}_{k\geq 0}$ and any parameters $d\geq 0$, $c\geq 0$, $K\geq 0$, there exists a constant $\eta\leq\frac{1}{d}$, such that for constant stepsizes $\{\eta^{k}=\eta\}_{k\geq 0}$ it holds:

For constant stepsizes $\eta^{t}=\eta$ we can derive the estimate

We distinguish two cases: if $\frac{r^{0}}{c(K+1)}\leq\frac{1}{d^{2}}$, then we chose the stepsize $\eta=\sqrt{\frac{r^{0}}{c(K+1)}}$ and get

on the other hand, if $\frac{r^{0}}{c(K+1)}>\frac{1}{d^{2}}$, then we choose $\eta=\frac{1}{d}$ and get

Substituting (55) and summing over $k$ we have:

First, when the stepsizes $\eta^{k}=\frac{4}{\mu(\kappa+k)}$, it is easy to see that $\eta^{k}\leq\frac{1}{14(2\delta+B)L}$:

Not difficult to check that $\{(\eta^{k})^{2}\}_{k\geq 0}$ is $2\delta$ slow decreasing:

Furthermore, the weights $\{w^{k}=\kappa+k\}_{k\geq 0}$ are $4\delta$-slow increasing:

The conditions for Lemma 32 are satisfied, and we obtain the desired statement. For the second case, the conditions of Lemma 33 are easy to check (see the previous paragraph). The claim follows by this lemma. Finally, for the third claim, we invoke Lemma 34. ∎

References