A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning

Introduction

We consider distributed optimization problems of the form

Communication Bottleneck. In distributed training, model updates (or gradient vectors) have to be exchanged in each iteration. Due to the size of the communicated messages for commonly considered deep models (Alistarh et al., 2016), this represents significant bottleneck of the whole optimization procedure. To reduce the amount of data that has to be transmitted, several strategies were proposed.

One of the most popular strategies is to incorporate local steps and communicated updates every few iterations only (Stich, 2019a; Lin et al., 2018a; Stich & Karimireddy, 2020; Karimireddy et al., 2019a; Khaled et al., 2020). Unfortunately, despite their practical success, local methods are poorly understood and their theoretical foundations are currently lacking. Almost all existing error guarantees are dominated by a simple baseline, minibatch SGD (Woodworth et al., 2020).

Considering both practice and theory, compression operators can be split into two groups: biased and unbiased. For the unbiased compressors, ${\cal C}(g)$ is required to be an unbiased estimator of the update $g$. Once this requirement is lifted, extra tricks are necessary for Distributed Compressed Stochastic Gradient Descent (DCSGD) (Alistarh et al., 2016; 2018; Khirirat et al., 2018) employing such a compressor to work, even if the full gradient is computed by each node. Indeed, the naive approach can lead to exponential divergence (Beznosikov et al., 2020), and Error Feedback (EF) (Seide et al., 2014; Karimireddy et al., 2019b) is the only known mechanism able to remedy the situation.

Contributions. Our contributions can be summarized as follows:

$\bullet$ Induced Compressor. When used within the stabilizing EF framework, biased compressors (e.g., Top-$K$) can often achieve superior performance when compared to their unbiased counterparts (e.g., Rand-$K$). This is often attributed to their low variance. However, despite ample research in this area, EF remains the only known mechanism that allows the use of these powerful biased compressors. Our key contribution is the development of a simple but remarkably effective alternative—and this is the only alternative we know of—which we argue leads to better and more versatile methods both in theory and practice. In particular, we propose a general construction that can transform any biased compressor, such as Top-$K$, into an unbiased one for which we coin the name induced compressor (Section 3). Instead of using the desired biased compressor within EF, our proposal is to instead use the induced compressor within an appropriately chosen existing method designed for unbiased compressors, such as distributed compressed SGD (DCSGD) (Khirirat et al., 2018), variance reduced DCSGD (DIANA) (Mishchenko et al., 2019a) or accelerated DIANA (ADIANA) (Li et al., 2020). While EF can bee seen as a version of DCSGD which can work with biased compressors, variance reduced nor accelerated variants of EF were not known at the time of writing this paper.

$\bullet$ Better Theory for DCSGD. As a secondary contribution, we provide a new and tighter theoretical analysis of DCSGD under weaker assumptions. If $f$ is $\mu$-quasi convex (not necessarily convex) and local functions $f_{i}$ are $(L,\sigma^{2})$-smooth (weaker version of $L$-smoothness with strong growth condition), we obtain the rate ${\cal O}\left(\delta_{n}Lr^{0}\exp\left[-\frac{\mu T}{4\delta_{n}L}\right]+\frac{(\delta_{n}-1)D+\delta\nicefrac{{\sigma^{2}}}{{n}}}{\mu T}\right),$ where $\delta_{n}=1+\frac{\delta-1}{n}$ and $\delta\geq 1$ is the parameter which bounds the second moment of the compression operator, and $T$ is the number of iterations. This rate has linearly decreasing dependence on the number of nodes $n$, which is strictly better than the best-known rate for DCSGD with EF, whose convergence does not improve as the number of nodes increases, which is one of the main disadvantages of using EF. Moreover, EF requires extra assumptions. In addition, while the best-known rates for EF (Karimireddy et al., 2019b; Beznosikov et al., 2020) are expressed in terms of functional values, our theory guarantees convergence in both iterates and functional values. Another practical implication of our findings is the reduction of the memory requirements by half; this is because in DCSGD one does not need to store the error vector.

$\bullet$ Partial Participation. We further extend our results to obtain the first convergence guarantee for partial participation with arbitrary distributions over nodes, which plays a key role in Federated Learning (FL).

$\bullet$ Experimental Validation. Finally, we provide an experimental evaluation on an array of classification tasks with CIFAR10 dataset corroborating our theoretical findings.

Error Feedback is not a Good Idea when Using Unbiased Compressors

In this section we first introduce the notions of unbiased and general compression operators, and then compare Distributed Compressed SGD (DCSGD) without (Algorithm 1) and with (Algorithm 2) Error Feedback.

Unbiased vs General Compression Operators. We start with the definition of unbiased and general compression operators (Cordonnier, 2018; Stich et al., 2018; Koloskova et al., 2019).

The following lemma provides a link between these notions (see, e.g. Beznosikov et al. (2020)).

Distributed SGD with vs without Error Feedback. In the rest of this section, we compare the convergence rates for DCSGD (Algorithm 1) and DCSGD with EF (Algorithm 2). We do this comparison under standard assumptions (Karimi et al., 2016; Bottou et al., 2018; Necoara et al., 2019; Gower et al., 2019; Stich, 2019b; Stich & Karimireddy, 2020), listed next.

First, we assume throughout that $f$ has a unique minimizer $x^{\star}$, and let $f^{\star}=f(x^{\star})>-\infty$.

The stochastic gradient used in Algorithms 1 and 2 satisfies

Note that this assumption implies ${\rm E}\left[\frac{1}{n}\sum_{i=1}^{n}g_{i}^{k}\;|\;x^{k}\right]=\nabla f(x^{k})$.

where $f_{i}^{\star}$ is the minimum functional value of $f_{i}$ and $[n]=\{1,2,\dots,n\}$.

This assumption generalizes standard smoothness and boundedness of variance assumptions. For more details and discussion, see the works of Gower et al. (2019); Stich (2019b). Equipped with these assumptions, we are ready to proceed with the convergence theory.

where $r^{0}=\left\lVert x^{0}-x^{\star}\right\rVert^{2}$, $W^{T}=\sum_{k=0}^{T}w^{k}$, and $\operatorname{Prob}(\bar{x}^{T}=x^{k})=\nicefrac{{w^{k}}}{{W^{T}}}$.

If $\delta=1$ (no compression), Theorem 2 recovers the optimal rate of Distributed SGD (Stich, 2019b). If $\delta>1$, there is an extra term $(\delta_{n}-1)D$ in the convergence rate, which appears due to heterogenity of data ($\sum_{i=1}^{n}\nabla f_{i}(x^{\star})=0$, but $\sum_{i=1}^{n}{\cal C}(\nabla f_{i}(x^{\star}))\neq 0$ in general). In addition, the rate is negatively affected by extra variance due to presence of compression which leads to $L\rightarrow\delta_{n}L$ and $\nicefrac{{\sigma^{2}}}{{n}}\rightarrow\nicefrac{{\delta\sigma^{2}}}{{n}}$.

Induced Compressor: Fixing Bias with Error-Compression

To get some intuition about this procedure, recall the structure used in Error Feedback. The gradient estimator is first compressed with ${\cal C}_{1}(g)$ and the error $e=g-{\cal C}_{1}(g)$ is stored in memory and used to modify the gradient in the next iteration. In our proposed approach, instead of storing the error $e$, we compress it with an unbiased compressor ${\cal C}_{2}$ (which can be seen as a parameter allowing flexibility in the design of the induced compressor) and communicate both of these compressed vectors. Note that this procedure results in extra variance as we do not work with the exact error, but with its unbiased estimate only. On the other hand, there is no bias and error accumulation that one needs to correct for. In addition, due to our construction, at least the same amount of information is sent to the master as in the case of plain ${\cal C}_{1}(g)$: indeed, we send both ${\cal C}_{1}(g)$ and ${\cal C}_{2}(e)$. The drawback of this is the necessity to send more bits. However, Theorem 3 provides the freedom in generating the induced compressor through the choice of the unbiased compressor ${\cal C}_{2}$. In theory, it makes sense to choose ${\cal C}_{2}$ with similar compression factor to the compressor ${\cal C}_{1}$ we are transforming as this way the total number of communicated bits per iteration is preserved, up to the factor of two.

Remark: The $\mbox{rtop}_{k_{1},k_{2}}(x,y)$ operator proposed by Elibol et al. (2020) can be seen as a special case of our induced compressor with $x=y$, ${\cal C}_{1}=\mbox{Top-}k_{1}$ and ${\cal C}_{2}=\mbox{Rand-}k_{2}$.

Extensions

We now develop several extensions of Algorithm 1 relevant to distributed optimization in general, and to Federated Learning in particular. This is all possible due to the simplicity of our approach. Note that in the case of Error Feedback, these extensions have either not been obtained yet, or similarly to Section 2, the results are worse when compared to our derived bounds for unbiased compressors.

To prove convergence, we exploit the following lemma.

The following theorem establishes the convergence rate for Algorithm 1 with partial participation.

Obtaining Linear Convergence. Note that in all the previous theorems, we can only guarantee a sublinear ${\cal O}(\nicefrac{{1}}{{T}})$ convergence rate. Linear rate is obtained in the special case when $D=0$ and $\sigma^{2}=0$. The first condition is satisfied, when $f_{i}^{\star}=f_{i}(x^{\star})$ for all $i\in[n]$, thus when $x^{\star}$ is also minimizer of every local function $f_{i}$. Furthermore, the effect od $D$ can be removed using compression of gradient differences, as pioneered in the DIANA algorithm (Mishchenko et al., 2019a). Note that $\sigma^{2}=0$ if weak growth condition holds (Vaswani et al., 2019). Moreover, one can remove effect of $\sigma^{2}$ by either computing full gradients locally or by incorporating variance reduction such as SVRG (Johnson & Zhang, 2013). It was shown by Horváth et al. (2019b) that both $\sigma^{2}$ and $D$ can be removed for the setting of Theorem 2. These results can be easily extended to partial participation using our proof technique for Theorem 5. Note that this reduction is not possible for Error Feedback as the analysis of the DIANA algorithm is heavily dependent on the unbiasedness property. This points to another advantage of the induced compressor framework introduced in Section 3.

Acceleration. We now comment on the combination of compression and acceleration/momentum. This setting is very important to consider as essentially all state-of-the-art methods for training deep learning models, including Adam (Kingma & Ba, 2015; Reddi et al., 2018), rely on the use of momentum in one form or another. One can treat the unbiased compressed gradient as a stochastic gradient (Gorbunov et al., 2020) and the theory for momentum SGD (Yang et al., 2016; Gadat et al., 2018; Loizou & Richtárik, 2017) would be applicable with an extra smoothness assumption. Moreover, it is possible to remove the variance caused by stochasticity and obtain linear convergence with an accelerated rate, which leads to the Accelerated DIANA method (Li et al., 2020). Similarly to our previous discussion, both of these techniques are heavily dependent on the unbiasedness property. It is an intriguing question, but out of the scope of the paper, to investigate the combined effect of momentum and Error Feedback and see whether these techniques are compatible theoretically.

Experiments

In this section, we compare Algorithms 1 and 2 for several compression operators. If the method contains “ + EF ”, it means that EF is applied, thus Algorithm 2 is applied. Otherwise, Algorithm 1 is displayed. To be fair, we always compare methods with the same communication complexity per iteration. All experimental details can be found in the Appendix.

Failure of DCSGD with biased Top-$\mathbf{1}$. In this experiment, we present example considered in Beznosikov et al. (2020), which was used as a counterexample to show that some form of error correction is needed in order for biased compressors to work/provably converge. In addition, we run experiments on their construction and show that while Error Feedback fixes divergence, it is still significantly dominated by unbiased non-uniform sparsification(NU Rand-$1$), which works by only keeping one non-zero coordinate sampled with probability equal to $\nicefrac{{|x|}}{{\sum_{i=1}^{d}|x|_{i}}}$, where $|x|$ denotes element-wise absolute value, as can be seen in Figure 1. The details can be found in the Appendix.

Error Feedback for Unbiased Compression Operators. In our second experiment, we compare the effect of Error Feedback in the case when an unbiased compressor is used. Note that unbiased compressors are theoretically guaranteed to work both with Algorithm 1 and 2. We can see from Figure 2 that adding Error Feedback can hurt the performance; we use TernGrad (Wen et al., 2017) (coincides with QSGD (Alistarh et al., 2016) and natural dithering (Horváth et al., 2019a) with the infinity norm and one level) as compressors. This agrees with our theoretical findings. In addition, for sparsification techniques such as Random Sparsification or Gradient Sparsification (Wangni et al., 2018), we observed that when sparsity is set to be 10 %, Algorithm 1 converges for all the selected values of step-sizes, but Algorithm 2 diverges and a smaller step-size needs to be used. This is an important observation as many practical works (Li et al., 2014; Wei et al., 2015; Aji & Heafield, 2017; Hsieh et al., 2017; Lin et al., 2018b; Lim et al., 2018) use sparsification techniques mentioned in this section, but proposed to use EF, while our work shows that using unbiasedness property leads not only to better convergence but also to memory savings.

Unbiased Alternatives to Biased Compression. In this section, we investigate candidates for unbiased compressors than can compete with Top-$K$, one of the most frequently used compressors. Theoretically, Top-$K$ is not guaranteed to work by itself and might lead to divergence (Beznosikov et al., 2020) unless Error Feedback is applied. One would usually compare the performance of Top-$K$ with EF to Rand-$K$, which keeps $K$ randomly selected coordinates and then scales the output by $\nicefrac{{d}}{{K}}$ to preserve unbiasedness. Rather than naively comparing to Rand-$K$, we propose to use more nuanced unbiased approaches. The first one is Gradient Sparsification proposed by Wagni et al. (Wangni et al., 2018), which we refer to here as Rand-$K$ (Wangni et al.), where the probability of keeping each coordinate scales with its magnitude and communication budget. As the second alternative, we propose to use our induced compressor, where ${\cal C}_{1}$ is Top-$a$ and unbiased part ${\cal C}_{2}$ is Rand-$(K-a)$ (Wangni et al.) with communication budget $K-a$. It should be noted that $a$ can be considered as a hyperparameter to tune. For our experiment, we chose it to be $\nicefrac{{K}}{{2}}$ for simplicity. Figure 3 suggests that our induced compressor outperforms all of its competitors as can be seen for both VGG11 and Resnet18. Moreover, induced compressor as well as Rand-$K$ do not require extra memory to store the error vector. Finally, Top-$K$ without EF suffers a significant decrease in performance, which stresses the necessity of error correction.

Conclusion

In this paper, we argue that if compressed communication is required for distributed training due to communication overhead, it is better to use unbiased compressors. We show that this leads to strictly better convergence guarantees with fewer assumptions. In addition, we propose a new construction for transforming any compressor into an unbiased one using a compressed EF-like approach. Besides theoretical superiority, usage of unbiased compressors enjoys lower memory requirements. Our theoretical findings are corroborated with empirical evaluation.

As a future work we plan to investigate the question of the appropriate choice of the inducing compressor ${\cal C}$. Our preliminary studies show that there is much to be discovered here, both in theory and in terms of developing further practical guidelines to those already contained in this work. The question of (theoretically) optimizing for ${\cal C}_{1}$ and ${\cal C}_{2}$ is difficult, as it necessitates a deeper theoretical understanding of biased compressors, which is currently missing. An alternative is to impose some assumptions on the structure of gradients encountered during the iterative process, or to perform an extensive experimental evaluation on desired tasks to provide guidelines for practitioners.

References

Appendix

Appendix A Experimental Details

To be fair, we always compare methods with the same communication complexity per iteration. We report the number of epochs (passes over the dataset) with respect to training loss and testing accuracy. The test accuracy is obtained by evaluating the best model in terms of validation accuracy. A validation accuracy is computed based on $10$ % randomly selected training data. We tune the step-size using based on the training loss. For every experiment, we randomly distributed the training dataset among $8$ workers; each worker computes its local gradient-based on its own dataset. We used a local batch size of $32$. All the provided figures display the mean performance with one standard error over $5$ independent runs. For a fair comparison, we use the same random seed for the compared methods. Our experimental results are based on a Python implementation of all the methods running in PyTorch. All reported quantities are independent of the system architecture and network bandwidth.

Dataset and Models. We do an evaluation on CIFAR10 dataset. We consider VGG11 (Simonyan & Zisserman, 2015) and ResNet18 (He et al., 2016) models and step-sizes $0.1,0.05$ and $0.01$.

Momentum. In this extra experiment, we look at the effect of momentum on Algorithm 1 and 2. We set momentum to $0.9$. Similarly to Figure 2, we work with the unbiased compressor, concretely TernGrad (Wen et al., 2017) (coincides with QSGD (Alistarh et al., 2016) and natural dithering (Horváth et al., 2019a) with the infinity norm and one level), to see the effect of adding Error Feedback. We can see from Figure 4 that adding Error Feedback can hurt the performance, which agrees with our theoretical findings.

Appendix B Example 1, Beznosikov et al. (2020)

In this section, we present example considered in Beznosikov et al. (2020), which was used as a counterexample to show that some form of error correction is needed in order for biased compressors to work/provably converge. In addition, we run experiments on their construction and show that while Error Feedback fixes divergence, it is still significantly dominated by unbiased non-uniform sparsification as can be seen in Figure 1. The construction follows.

Consider $n=d=3$ and define the following smooth and strongly convex quadratic functions

where $a=(-3,2,2),b=(2,-3,2),c=(2,2,-3)$. Then, with the initial point $x^{0}=(t,t,t),\;t>0$

Repeated application gives $x^{k}=\left(1+\frac{11\eta}{6}\right)^{k}x^{0}$, which diverges exponentially fast to $+\infty$ since $\eta>0$.

As a initial point, we use $(1,1,1)^{\top}$ in our experiments and we choose step size $\frac{1}{L}$, where $L$ is smoothness parameter of $f=\frac{1}{3}(f_{1}+f_{2}+f_{3})$. Note that zero vector is the unique minimizer of $f$.

Appendix C Proofs

C.2 Proof of Theorem 2

We use the update of Algorithm 1 to bound the following quantity

Taking full expectation and $\eta^{k}\leq\frac{1}{2\delta_{n}L}$, we obtain

The rest of the analysis is closely related to the one of Stich (2019b). We would like to point out that similar results to Stich (2019b) were also present in (Lacoste-Julien et al., 2012; Stich et al., 2018; Grimmer, 2019).

We first rewrite the previous inequality to the form

where $r^{k}={\rm E}\left[\left\lVert x^{k}-x^{\star}\right\rVert^{2}\right]$, $s^{k}={\rm E}\left[f(x^{k})-f^{\star}\right]$, $a=\mu$, $c=(\delta_{n}-1)D+\frac{\delta\sigma^{2}}{n}$.

We proceed with lemmas that establish a convergence guarantee for every recursion of type (10).

Let $\{r^{k}\}_{k\geq 0}$, $\{s^{k}\}_{k\geq 0}$ be as in (10) for $a>0$ and for constant stepsizes $\eta^{k}\equiv\eta\coloneqq\frac{1}{d}$, $\forall k\geq 0$. Then it holds for all $T\geq 0$:

This follows by relaxing (10) using ${\rm E}\left[f(x^{k})-f^{\star}\right]\geq 0$,and unrolling the recursion

Let $\{r^{k}\}_{k\geq 0}$, $\{s^{k}\}_{k\geq 0}$ as in (10) for $a>0$ and for decreasing stepsizes $\eta^{k}\coloneqq\frac{2}{a(\kappa+k)}$, $\forall k\geq 0$, with parameter $\kappa\coloneqq\frac{2d}{a}$, and weights $w^{k}\coloneqq(\kappa+k)$. Then

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

We start by re-arranging (10) and multiplying both sides with $w^{k}$

where the equality follows from the definition of $\eta^{k}$ and $w^{k}$ and the inequality from $(\kappa+k)(\kappa+k-2)=(\kappa+k-1)^{2}-1\leq(\kappa+k-1)^{2}$. Again we have a telescoping sum:

$W^{T}=\sum_{k=0}^{T}w^{k}=\sum_{k=0}^{T}(\kappa+k)=\frac{(2\kappa+T)(T+1)}{2}\geq\frac{T(T+1)}{2}\geq\frac{T^{2}}{2}$,

and $W^{T}=\frac{(2\kappa+T)(T+1)}{2}\leq\frac{2(\kappa+T)(1+T)}{2}\leq(\kappa+T)^{2}$ for $\kappa=\frac{2d}{a}\geq 1$.

By applying these two estimates we conclude the proof. ∎

The convergence can be obtained as the combination of these two lemmas.

Let $\{r^{k}\}_{k\geq 0}$, $\{s^{k}\}_{k\geq 0}$ as in (10), $a>0$. Then there exists stepsizes $\eta^{k}\leq\frac{1}{d}$ and weighs $w^{k}\geq 0$, $W^{T}\coloneqq\sum_{k=0}^{T}w^{k}$, such that

For integer $T\geq 0$, we choose stepsizes and weights as follows

for $\kappa=\frac{2d}{a}$ and t_{0}=\bigl{\lceil}\frac{T}{2}\bigr{\rceil}. We will now show that these choices imply the claimed result.

We start with the case $T\leq\frac{d}{a}$. For this case, the choice $\eta=\frac{1}{d}$ gives

If $T>\frac{d}{a}$, then we obtain from Lemma 6 that

From Lemma 7 we have for the second half of the iterates:

Now we observe that the restart condition $r^{t_{0}}$ satisfies:

because $T>\frac{d}{a}$. These conclude the proof.

Having these general convergence lemmas for the recursion of the form (10), the proof of the theorem follows directly from Lemmas 6 and 8 with $a=\mu$, $c=\sigma^{2}$, $d=2\delta_{n}L$ . It is easy to check that condition $\eta^{k}\leq\frac{1}{d}=\frac{1}{2\delta_{n}L}$ is satisfied.

C.3 Proof of Theorem 3

We have to show that our new compression is unbiased and has bounded variance. We start with the first property with $\lambda=1$.

where the first equality follows from tower property and the second from unbiasedness of ${\cal C}_{2}$. For the second property, we also use tower property

where the first and second inequalities follow directly from (2) and (3).

C.4 Proof of Lemma 4 (Horváth & Richtárik, 2019)

For the first part of the claim, it was shown that ${\bf P}-pp^{\top}$ is positive semidefinite (Richtárik & Takáč, 2016), thus we can bound ${\bf P}-pp^{\top}\preceq n\mathbf{Diag}\left({\bf P}-pp^{\top}\right)=\mathbf{Diag}\left(p\circ v\right)$, where $v_{i}=n(1-p_{i})$, which implies that (8) holds for this choice of $v$.

Since by assumption we have ${\bf P}-pp^{\top}\preceq\mathbf{Diag}\left(p\circ v\right)$, we can further bound

To obtain (9), it remains to combine this with (13).

C.5 Proof of Theorem 5

Similarly to the proof of Theorem 2, we use the update of Algorithm 1 to bound the following quantity