Towards Faster Decentralized Stochastic Optimization with Communication Compression

W1: This is a good question! We indeed do not have access to the averaged model $\bar{\mathbf{x}}^t$, however, there are several reasons to consider the expected gradient norm at the averaged iterate. First, we highlight that using the average iterate $\bar{\mathbf{x}}^t=$ $\frac{1}{n}\sum_{i=1}^n \mathbf{x}\_{i}^t$ in the convergence metric is a standard technique and was done in many previous works [1-4]. Second, from practical considerations, to obtain an averaged model after the end of MoTEF, we can perform a gossip averaging with compression (e.g., Choco-Gossip [2]) that converges linearly, i.e. adds only logarithmic terms in the convergence rate. Therefore, obtaining the average can be done in practice without hurting the rate. Next, in the revised version of the paper, we strengthened our convergence guarantees of MoTEF. In section B.1.1, we provide detailed derivations that show that the consensus error term $\Omega_3^t = \mathbb{E}\left[\\|\mathbf{X}^t -\bar{\mathbf{x}}^t \mathbf{1}^\top\\|^2\right]$ converges to zero as well. Together with the convergence of $\mathbb{E}[\\|\nabla f(\mathbf{x}_{\rm out})\\|^2]$ we ensure that all local models $\mathbf{x}_i^t$ also converge to stationarity. We refer to Corollary A.6 in [5] for derivations of this claim. We also add the derivations in Section B.1.2.

W2: We thank the reviewer for this comment. We adjusted the references accordingly.

Q1: We do not obtain the monotonic decrease of the Lyapunov function. It is only possible if the workers use full gradients, i.e. the variance $\sigma^2=0.$ In the stochastic regime, the decrease of the Lyapunov function is done up to the error term which scales with $\sigma.$ Therefore, the current analysis does not automatically imply the convergence of each of the terms in the Lyapunov function. Nonetheless, in the response to W1 we demonstrate that the consensus error term $\Omega_3^t$ converges to zero.

[1] Koloskova, Anastasia and Lin, Tao and Stich, Sebastian U and Jaggi, Martin, Decentralized deep learning with arbitrary communication compression, ICLR, 2020.

[2] Koloskova, Anastasia and Stich, Sebastian and Jaggi, Martin, Decentralized stochastic optimization and gossip algorithms with compressed communication, ICML, 2019.

[3] Zhao, Haoyu and Li, Boyue and Li, Zhize and Richtàrik, Peter and Chi, Yuejie, BEER: Fast $O(1/T)$ Rate for Decentralized Nonconvex Optimization with Communication Compression, NeurIPS, 2022

[4] Huang, Kun and Pu, Shi, Cedas: A compressed decentralized stochastic gradient method with improved convergence, IEEE Transactions on Automatic Control, 2024.

[5] Koloskova, Anastasia and Lin, Tao and Stich, Sebastian U and Jaggi, Martin, Decentralized deep learning with arbitrary communication compression, arXiv preprint arXiv:1907.09356, 2019.

W1: Even though the mechanisms we used in the design of MoTEF algorithm are known in the literature, combining them is a challenging task and requires careful investigation. For example, we highlight that the order of steps in the algorithm plays a crucial role. In [1] they have similar mechanisms in the algorithm. They use two tracking steps: one is inside the momentum term (line 10 in Alg. 1 [1]) and another one in the update of gradient estimators (line 12 in Alg. 1 [1]). Afterward, the gradient estimators' differences are compressed and aggregated among neighbors. Their algorithm design leads to suboptimal asymptotic convergence. In our algorithm, the gradient tracking step is involved in the update of gradient estimator $V$ only (line 8) involving the averaging from the previous step. Then, new gradient estimators' differences are compressed. Based on the discussion above, we believe that combining contractive compression and stochastic gradients with gradient tracking and Error Feedback in decentralized training is a challenging task as it requires proper algorithm design to overcome all difficulties simultaneously without imposing strong assumptions on the problem.

To improve the writing, we aim to add the following discussion about the algorithm design which is also reported in Section A.1:

Designing an algorithm with strong convergence guarantees without imposing assumptions on the problem or data is complicated. In MoTEF we incorporate three main ingredients to make it converge faster under arbitrary data heterogeneity. In particular, the combination of EF21-type Error Feedback and Gradient Tracking mechanisms is the key factor in getting rid of the influence of data heterogeneity. We emphasize that not using any one of them would lead to restrictions on the data heterogeneity. Indeed, EF21 is known to remove such dependencies in centralized training [2] while the GT mechanism is essential in decentralized learning [3]. Nonetheless, EF21 does not handle the error coming from stochastic gradients and momentum is known to be one of the remedies to it [4].

W2: In fact, it was a hyperlink in the text. In the revised version, we changed it to the footnote for visibility. The link on page 9 is to experiments with real data (logistic regression and neural networks).

Q1: This is a great question! First, note that EF21 [2] Error Feedback mechanism removes the data heterogeneity assumption in the centralized setting. GT mechanism is needed in the decentralized training (without compression) as vanilla decentralized SGD is affected by the data heterogeneity [3]. Therefore, we believe that these two mechanisms are essential to designing an algorithm whose convergence is not affected by data heterogeneity in the decentralized training.

Q2: We thank the reviewer for bringing this comment. After carefully checking the derivations, we found several minor typos in the calculations and fixed them. Moreover, we provide a simplified convergence rate in both non-convex and PL regimes. Indeed, one of the middle terms dominates the other two, and therefore, the rate can be simplified. Similarly, we provide the simplified convergence rate of MoTEF-VR in the revised version of the paper.

Here are the explicit references. We apologise for the accidental omission in our previous response.

[1] Chung-Yiu Yau and Hoi-To Wai. Docom: Compressed decentralized optimization with near-optimal sample complexity. arXiv preprint arXiv:2202.00255, 2022.

[2] Richtàrik, Peter and Sokolov, Igor and Fatkhullin, Ilyas, EF21: A new, simpler, theoretically better, and practically faster error feedback, NeurIPS, 2021.

[3] Koloskova, Anastasia and Loizou, Nicolas and Boreiri, Sadra and Jaggi, Martin and Stich, Sebastian, A unified theory of decentralized sgd with changing topology and local updates, ICLR, 2020.

[4] Fatkhullin, Ilyas and Tyurin, Alexander and Richtàrik, Peter, Momentum provably improves error feedback!, NeurIPS, 2024.

W1: First, MoTEF provably converges with contractive compressors (e.g., Top-K) while CEDAS converges only with unbiased compressors (e.g., Random-K). The class of contractive compression operators is more general and contains operators such as Top-K that do not have unbiased property. Many earlier works demonstrated that contractive compressors are superior in practice [3-5], known to be near-optimal in theory [1], achieve smaller variance both theoretically and empirically than their unbiased cousins [2]. Moreover, combining unbiased compressor with contractive one improves the practical performance [6]. Second, MoTEF uses momentum mechanism which is known to accelerate the performance both theoretically [7] and practically [8-9] in training deep models.

W2: We provide the empirical comparison of MoTEF and CEDAS algorithms on the logistic regression with non-convex regularization in section D.6. We demonstrate that MoTEF achieves smaller gradient norm in most of the cases that showcase its practical superiority as well.

Q1: we refer to the responses to W1 and W2

Q2: We thank the reviewer for pointing out the typo. In the revised version of the paper, Figure 6 contains the empirical results in training CNN model on MNIST dataset and Section D.5 describes the training details and results.

[1] Albasyoni, Alyazeed and Safaryan, Mher and Condat, Laurent and Richtárik, Peter, Optimal gradient compression for distributed and federated learning, arXiv preprint arXiv:2010.03246, 2020

[2] Beznosikov, Aleksandr and Horváth, Samuel and Richtárik, Peter and Safaryan, Mher, On biased compression for distributed learning Journal of Machine Learning Research, 2023

[3] Lin, Yujun and Han, Song and Mao, Huizi and Wang, Yu and Dally, William J, Deep gradient compression: Reducing the communication bandwidth for distributed training, arXiv preprint arXiv:1712.01887, 2017.

[4] Haobo Sun and Yingxia Shao and Jiawei Jiang and Bin Cui and Kai Lei and Yu Xu and Jiang Wang, Sparse Gradient Compression for Distributed SGD, International Conference on Database Systems for Advanced Applicationsl 2019.

[5] Vogels, Thijs and Karimireddy, Sai Praneeth and Jaggi, Martin, PowerSGD: Practical low-rank gradient compression for distributed optimization, NeurIPS, 2019.

[6] Horváth, Samuel and Richtárik, Peter, A better alternative to error feedback for communication-efficient distributed learning, ICLR, 2021.

[7] Cutkosky, Ashok and Mehta, Harsh, Momentum improves normalized sgd, ICML, 2020.

[8] Choi, Dami and Shallue, Christopher J and Nado, Zachary and Lee, Jaehoon and Maddison, Chris J and Dahl, George E, On empirical comparisons of optimizers for deep learning, arXiv preprint arXiv:1910.05446, 2019.

[9] Fu, Jingwen and Wang, Bohan and Zhang, Huishuai and Zhang, Zhizheng and Chen, Wei and Zheng, Nanning, When and why momentum accelerates sgd: An empirical study, arXiv preprint arXiv:2306.09000, 2023.

2. Additional experimental results.

   • In Figure 7, we compare MoTEF and CEDAS in terms of gradient norm vs. bits. We increased the parameter set for the step sizes; please see the description in Section D.6. We took into account that the communication of one step of MoTEF is two times larger since workers exchange messages twice per iteration. We observe that MoTEF either matches CEDAS or outperforms it in terms of communication complexity.

   • We would like to emphasize that we demonstrate the best performance that is achievable by setting the parameters from the corresponding set. From the empirical observations, we observe that CEDAS requires smaller step-size parameters $\gamma$ and $\eta$ to achieve the same gradient norm as MoTEF. However, choosing too small step-sizes $\gamma$ and $\eta$ leads to a significantly slower convergence speed of CEDAS.

1. Thank you for your response. We would like to address the remaining concerns. The lower bound (also called uncertainty principle for communication compression) presented in [1] shows that a compression scheme with a distortion $\alpha$ and $b$ encoding bits (in the worst case) satisfies $b \approx \frac{d}{2}\log\frac{1}{\alpha},$ where we ignore $\mathcal{O}(\log d)$ terms. [1] shows that there is an example of biased compressor which matches the lower bound. For the unbiased $Q$ compressor with parameter $\omega > 0$ (for example, for Rand-k $\omega = \frac{d}{k}-1$) we have that $\frac{1}{1+\omega}Q$ is the biased compressor with parameter $\alpha=\frac{\omega}{1+\omega}$. Plugging this number in the lower bound we get that for the unbiased compressor it matches the lower bound if $b \approx \frac{d}{2}\log(1+1/\omega).$ Particularly, in the case of Rand-k compressor we have $\omega=\frac{d}{k}-1$, and therefore we should have $b \approx \frac{d}{2}\log(d/(d-k)).$ However, for Rand-k compressor we have $b = 32k \log d$ which is larger than $\frac{d}{2}\log(d/(d-k))$ if $k$ is sufficiently small than $d$. Therefore, Rand-k compressor does not satisfy the lower bound. This is also illustrated in [10], Figure 1 where the authors demonstrate that biased compressors are closer to the lower bound than unbiased ones. Moreover, we also refer to Lemma 20 in [2] where the authors analyze the difference in the compression error of Top-k and Rand-k compressors, In particular, they demonstrate that if the entries of the input follow the standard exponential distribution then Top-K compressor's error is much smaller than that of Rand-k. In Figure 1 they also demonstrate that Top-k compressor in average requires less bits to encode one entry than Rand-k with the same normalized variance. Finally, Figure 2 in [2] showcases that Top-k compressor saves "more information" about the input than Rand-k for practical gradient distributions.

   These observations demonstrate the superiority of biased compressors both theoretically and practically.

   [1] Albasyoni, Alyazeed and Safaryan, Mher and Condat, Laurent and Richtárik, Peter, Optimal gradient compression for distributed and federated learning, arXiv preprint arXiv:2010.03246, 2020

   [2] Beznosikov, Aleksandr and Horváth, Samuel and Richtárik, Peter and Safaryan, Mher, On biased compression for distributed learning, Journal of Machine Learning Research, 2023

   [10] Safaryan, Mher and Shulgin, Egor and Richtarik, Peter, Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor, A Journal of the IMA, 2022.

2. We will provide further experiments soon with a larger grid search in terms of gradient norm vs transmitted bits.

W1: We would like to clarify the main differences between MoTEF and EControl. First, MoTEF incorporates EF21/CHOCO-style Error Feedback while EControl uses a more classical Error Compensation mechanism [9]. Having different error mechanisms leads to significantly different analysis techniques (e.g., analysis via virtual iteration vs. a more direct proof, and the design of the Lyapunov function: their Lyapunov function has only 3 terms while ours has 6, i.e. it requires much more involved and technical analysis). Next, EControl archives linear speedup by properly balancing the error term $e^t$, and the error carried from the gradient estimator. In our work, this is done by incorporating momentum which reduces the variances. Finally, in our work we provide the convergence guarantees under PL condition and the convergence of MoTEF-VR that was not done in EControl paper.

W2: Designing an algorithm with strong convergence guarantees without imposing assumptions on the problem or data is complicated. In MoTEF we incorporate three main ingredients to make it converge faster under arbitrary data heterogeneity. In particular, the combination of EF21-type Error Feedback and Gradient Tracking mechanisms is the key factor in getting rid of the influence of data heterogeneity. We emphasize that not using one of them would lead to restrictions on the data heterogeneity. Indeed, EF21 is known to remove such dependencies in centralized training [1] while the GT mechanism is essential in decentralized learning [2]. Nonetheless, EF21 does not handle the error coming from stochastic gradients and momentum is known to be one of the remedies for it [3]. Without the momentum term, EF21 is known to converge only with large enough batches in the centralized stochastic regime [3]. Moreover, we emphasize that earlier work [10] incorporates similar ideas but fails to achieve optimal asymptotic rate due to the incorrect order of mechanisms in their algorithm.

With appropriately chosen parameters, the momentum technique reduces the variance (between the momentum and the gradient) as the algorithm proceeds. On a more technical level, this variance-reduction property enables us to do a descent analysis on $\hat G^t$, the variance between the averaged momentum and the local gradients. Being able to reason with the averaged momentum is crucial for achieving the linear speedup because it enables us to analyze the averaged noises (whose variance is reduced linearly in $n$), instead of the individual noises, at each iteration.

Q1: we refer to the response to W1

Q2: we refer to the response to W2

Q3: This is a great question. Indeed, if we set the compression operator to be identity, momentum parameter $\lambda = 1- \beta$, and slightly modify the variables in MoTEF, then the momentum tracking algorithm from [1] is almost identical to our method. The main difference comes from the fact we also use a mixing step with stepsize $\gamma$ which is needed because of the use of compression (see [5], for instance). [4] also obtain optimal asymptotic rate as we do, but their deterministic rate has slightly better dependency on the spectral gap $\rho:$ $\rho^{5/2}$ instead of $\rho^3$ in our work. However, we highlight that combining momentum tracking and compression is a challenging task as naive use of contractive compressors might lead to divergence [6]. Therefore, the Error Feedback mechanism is needed to tackle this issue. This translates into more involved and technical proofs. The convergence rate of GT has $\mathcal{O}(\frac{\sigma^2}{n\varepsilon^4} + \frac{\sigma}{(\rho^{3/2} + \rho\sqrt{n})\varepsilon^{3}} + \frac{1}{\rho^2\varepsilon})$ [7]. We observe that both MoTEF and GT achieve optimal asymptotic rate, but GT has slightly better dependency on the spectral gap in the deterministic regime: $\rho^2$ instead of $\rho^3.$

Q4: If we set $\rho=1$ in the convergence rate of MoTEF, we obtain the asymptotic $\frac{LF^0\sigma^2}{n\varepsilon^4}$ and deterministic $\frac{LF^0}{\alpha\varepsilon^2}$ rates that match those of EControl, EF21-SGDM, and Neolithic. The difference between algorithms is in the middle term(s) in the rate. Neolithic does not have this term since the analysis is performed under a more restricted assumption of the bounded gradient dissimilarity and performing an impractical multi-stage compression mechanism (i.e., several communication rounds per iteration). The middle term in the convergence rate of EControl has a worse dependency on $\alpha:$ $\alpha^2$ instead of $\alpha$ in our work. The convergence rate of EF21-SGDM has two middle terms. The worst of them scales scales with $\alpha^{1/2}$ while it is $\alpha$ in the convergence of MoTEF.

Q5: In the experiments with MLP model, we use MNIST dataset. Moreover, we point out that we provide the experiments with CNN model on MNIST dataset in the appendix. The main contribution of our work is a novel MoTEF and MoTEF-VR algorithms with their convergence analysis. We provide convergence guarantees in general non-convex and PL regimes. We support our theoretical findings in training logistic regression with non-convex regularization as well as training of MLP and CNN (in the appendix) models. In all the cases, the empirical results demonstrate the superiority of MoTEF algorithm. Moreover, we provide the experiments that showcase the robustness of MoTEF algorithm to the changes of the network topology. For a more comprehensive experimental study with more complex models and real-life decentralized training hardware, we defer them to a more experiment-focused work in the future due to resource constraints.

[1] Richtàrik et al., EF21: A new, simpler, theoretically better, and practically faster error feedback, NeurIPS, 2021.

[2] Koloskova et al., A unified theory of decentralized sgd with changing topology and local updates, ICLR, 2020.

[3] Fatkhullin et al., Momentum provably improves error feedback!, NeurIPS, 2024.

[4] Y. Takezawa et al., Momentum tracking: momentum acceleration for decentralized deep learning on heterogeneous data, TMLR, 2023.

[5] Koloskova et al., Decentralized stochastic optimization and gossip algorithms with compressed communication, ICML 2019, 2019.

[6] Beznosikov et al., On biased compression for distributed learning, JMLR, 2023.

[7] Koloskova et al., An improved analysis of gradient tracking for decentralized machine learning, NeurIPS, 2021.

[8] Di et al., Double Stochasticity Gazes Faster: Snap-Shot Decentralized Stochastic Gradient Tracking Methods, ICML, 2022.

[9] Seide et al., 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs, Interspeech, 2014.

[10] Yau & Wai. Docom: Compressed decentral- ized optimization with near-optimal sample complexity. arXiv preprint arXiv:2202.00255, 2022

W1: We thank the reviewer for this valuable comment. In this work, we consider the general contractive compression with the parameter $\alpha$ which quantifies the compression quality instead of the compression ratio directly. This definition covers many popular compressors in practice, for which we can discuss the total communication complexity. Below we provide a comparison of total communication complexity based on Top-$K$ compressor which is a contractive compressor with $\alpha =K/d$. In each round of communication, a client sends data of size proportional to $K$ (up to $\log(K)$ terms) to its neighbor, instead of the dimension $d$. Therefore, the total communication complexity of the algorithm with Top-$K$ compressor is proportional to $K \times \text{ number of iterations }$, while for the non-compressed methods, the total communication complexity is $d \times \text{ number of iterations }$. Now plugging our complexity bound in the paper, we have that the total communication complexity of MoTEF with Top-$K$ becomes:

while the uncompressed decentralized SGD with gradient tracking has:

In the deterministic regime, i.e. when $\sigma^2=0$, our method obtains a $\frac{d}{\rho^3\varepsilon^2}$ rate, which is slightly worse than the rate of the uncompressed method by a factor of $1/\rho$. This is however negligible when the graph is moderately well-connected. More importantly, in the noisy regime which is more typical in the modern machine learning setting, the asymptotically dominant term for MoTEF is $\mathcal{O}(\frac{\sigma^2 K}{n\varepsilon^4})$ which has a $K/d$ factor of improvement over the uncompressed method, $\mathcal{O}(\frac{\sigma^2 d}{n\varepsilon^4})$.

W2: The main contribution of our work is a novel MoTEF and MoTEF-VR algorithms with their convergence analysis. We provide convergence guarantees in general non-convex and PL regimes. We support our theoretical findings in training logistic regression with non-convex regularization as well as training of MLP and CNN (in the appendix) models. In all the cases, the empirical results demonstrate the superiority of MoTEF algorithm. Moreover, we provide the experiments that showcase the robustness of MoTEF algorithm to the changes of the network topology. For a more comprehensive experimental study with more complex models and real-life decentralized training hardware, we defer them to a more experiment-focused work in the future due to resource constraints.

Q1: We appreciate the interest of the reviewer in the design of the Lyapunov function. First, the term $F^t$ typically appears in the Lyapunov-type analysis in the non-convex regime. Second, two terms $\Omega_1^t$ and $\Omega_2^t$ are consensus errors that are present in the Lyapunov function as we consider the decentralized training, and local models and gradient estimators eventually should be close to each other. Next, due to presence of the compression there are additional terms $\Omega_3^t$ and $\Omega_4^t$ to control the compression error. Finally, the terms $\hat{G}^t$ and $\tilde{G}^t$ are there to control the difference between full gradient $\nabla F(X^t)$ and momentum $M^t$, i.e. to showcase that $M^t$ is a good enough approximation of the true gradient. We emphasize that even though the convergence can be shown without using $\hat{G}^t$ but this term is crucial for proving the linear speedup with $n$ in the asymptotic term $\frac{\sigma^2}{n\varepsilon^4}$. Therefore, it is important to have both terms in the Lyapunov function. The coefficient next to each term are chosen to balance the descent rates of all the terms.