Towards Faster Decentralized Stochastic Optimization with Communication Compression

Authors: Rustem Islamov, Yuan Gao, Sebastian U Stich
Primary area: optimization
Keywords: Optimization, Decentralized Learning, Federated Learning, Communication Compression

Abstract:
Communication efficiency has garnered significant attention as it is considered the main bottleneck for large-scale decentralized Machine Learning applications in distributed and federated settings. In this regime, clients are restricted to transmitting small amounts of compressed information to their neighbors over a communication graph. Numerous endeavors have been made to address this challenging problem by developing algorithms with compressed communication for decentralized non-convex optimization problems. Despite considerable efforts, current theoretical understandings of the problem are still very limited, and existing algorithms all suffer from various limitations. In particular, these algorithms typically rely on strong, and often infeasible assumptions such as bounded data heterogeneity or require large batch access while failing to achieve linear speedup with the number of clients. In this paper, we introduce MoTEF, a novel approach that integrates communication compression with $\textbf{Mo}$mentum $\textbf{T}$racking and $\textbf{E}$rror $\textbf{F}$eedback. MoTEF is the first algorithm to achieve an asymptotic rate matching that of distributed SGD under arbitrary data heterogeneity, hence resolving a long-standing theoretical obstacle in decentralized optimization with compressed communication. We provide numerical experiments to validate our theoretical findings and confirm the practical superiority of MoTEF.

Decision: accept (poster)
Reviewer scores: 5, 6, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1730031745413

thread_type:
official_review

<thread_object>
creator: reviewer_tejt

<content>
summary:
The authors propose new algorithms for decentralized nonconvex optimization with heterogeneous functions, communication compression, and calls to stochastic gradients.

strengths:
As far as I know, the state of the art as summarized in the paper and Appendix A is correctly presented. The contributions are important, as nonconvex decentralized optimization is a timely topic with a wide range of applications.

weaknesses:
My main concern is the following. In Table 1, it is stated that convergence is established with respect to E[||nabla.f(x_out)||] for an appropriately chosen x_out, which as its name suggest should be constructed and output by the algorithm. However, the main result, Theorem 1, is established for x_out = bar{x}_t for a random t. The problem is that bar{x} is the average of the local variables x_i, which is not available! So you only prove one half of a valid convergence statement. The second half is that the method achieves a consensus, which in your case corresponds to Omega_3 converging to zero. Reasoning on bar{x} violates the conditions of decentralized optimization, where communication is assumed to be possible only through the network edges, and with compression.

Is x_out = bar{x}_t used in the experiments? In that case this is clearly unfair to the other methods which do not use this unaccessible oracle.

Minor comments on the state of the art:
* The paper about LEAD by Liu et al. "Linear convergent decentralized optimization with compression" has been published at ICLR 2021.
* The title "Randcom: Random communication skipping method for decentralized stochastic optimization" of the paper arXiv:2310.07983 has changed

questions:
Does it follow from Lemma 1 that in the conditions of Theorem 1, Phi^{t+1} <= Phi^t? This would imply that all quantities in (8) remain bounded (ideally, they would be proved to tend to zero).
</content>
</thread_object>

</thread>
<thread>
creation date:
1730216466822

thread_type:
official_review

<thread_object>
creator: reviewer_dzjc

<content>
summary:
Compression has become a key technique in federated learning to address the primary bottleneck of communication efficiency. This paper introduces a new algorithm, MoTEF, designed for decentralized federated learning with communication compression. The distinctive features of MoTEF include integration with model compression, moment tracking and error feedback altogether.

The authors provide a convergence analysis showing that MoTEF achieves some of the best expected results, notably without requiring heterogeneity assumptions. They discuss convergence for general non-convex functions and for functions that satisfy the PL condition (a broader condition than convexity). Additionally, they present a moment-based variance reduction variant of MoTEF.

Theoretical insights into the algorithm are explored through comparisons with existing bounds, as well as through numerical experiments.

strengths:
It is impressive that the authors prove a convergence bound for such a complex algorithm without assuming a specific degree of data heterogeneity. Their other assumptions are also reasonable. Although the bound has a suboptimal dependence on \rho, their experiments demonstrate that the algorithm’s sensitivity to \rho can actually be much lower, offering valuable insights to the community.

The presentation is excellent, with comprehensive discussions that thoroughly compare their results to existing work.

weaknesses:
More explanation to what Algorithm MoTEF actually does can improve the paper. From what is is written, it seems the algotihm just puts togther all the previous tricks into one place.  

One minor suggestion: while the authors say "The codes to reproduce our synthetic experiment can be accessed here", the URL is provided at the end of page 9.

questions:
Can you elaborate which of the three trick (GT, moment, error feedback) helps remove the data heterogeneity of the paper?   

Can you simplify the bounds in (11)? In particular, there seems to be a tradeoff on \alpha among the second term, third term, fourth term. In other words, can you provide a unifying bounds that incorporates these three terms?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730262155288

thread_type:
official_review

<thread_object>
creator: reviewer_szmb

<content>
summary:
This paper proposes MoTEF which achieves faster asymptotic convergence rate on decentralized optimization with communication compression, without using strong assumptions such as bounded gradient, bounded heterogeneity or unbiased compression. A variance-reduction version called MoTEF-VR is also introduced. Ablation studies show that MoTEF enjoys linear speed-up and is robust to network topology. Numerical experiments show that MoTEF performs better than Choco-SGD and BEER.

strengths:
1. This work achieves the fastest asymptotic convergence rates with weakest assumptions.
2. The presentation is neat and clear.

weaknesses:
1. The improvement on theoretical convergence result is not significant. Compared to CEDAS, it seems that the only improvement is removing the need for an additional unbiased compressor. To better illustrate this improvement, it is expected to validate whether using contractive compressors are more efficient than using unbiased ones. Otherwise, maybe the authors can compare the full convergence complexity (instead of the asymptotic one only) to address the theoretical improvement.
2. The numerical experiments are not persuasive enough. The compared baselines are Choco-SGD and BEER, which are in 2022 or earlier, and their convergence rate is clearly worse than SOTA as illustrated in Table 1. In contrast, CEDAS that seems closer to SOTA convergence rate is not compared. Maybe the authors can make the experimental results more solid by adding more baselines like CEDAS and DeepSqueeze.

questions:
1. Can the authors better illustrate the advantage of MoTEF against CEDAS both theoretically and empirically? For example, in what sense using contractive compression is better than unbiased compression, and whether MoTEF can perform better than CEDAS?
2. The result for CNN seems missing. Please make sure to include both the results and the implementation details.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730479965708

thread_type:
official_review

<thread_object>
creator: reviewer_dwbg

<content>
summary:
This paper studies decentralized stochastic optimization with communication compression. It introduces the momentum tracking technique with error feedback, and achieves the first linear speedup convergence rate under the standard assumptions. Numerical experiments are conducted to validate the theoretical findings.

strengths:
1. It combines momentum tracking and error feedback to attain an effective compressed decentralized algorithm.

2. It achieves the first linear speedup convergence rate for decentralized algorithms with contractive compressors.

weaknesses:
1. The novelty seems a little bit limited. The main idea and analysis techniques seems to be a direct extension of the centralized algorithm EControl (Gao et.al., 2024) to decentralized settings. 

2. The insight behind the proposed algorithm is not well clarified. Why does the combination of the momentum tracking and error feedback result in the linear speedup rate? It is encouraged to discuss how the algorithms are developed and highlight the insight.

3. The dependence on the network topology, as the authors have discussed, is much worse than decentralized algorithms without compression.

questions:
1. Please highlight the challenges in analysis and algorithmic developments compared to the EControl algorithm (Gao et.al., 2024).

2. Please have an in-depth discussion on how the algorithm is developed. Why does the combination of the momentum tracking and error feedback result in the linear speedup rate?   

3. If there is no communication compression and error feedback, does your algoithm reduce to the pure momentum tracking algorithm? How does this momentum tracking algorithm compare with the well-known gradient tracking algorithm in convergence rate?

4. In your Theorem 1, if the network is fully connected, i.e., rho=1, how does your algorithm compare with state-of-the-art centralized compressed algorithm such as EControl, Error-feedback with momentum, and NEOLITHC?

5. The numerical studies are a little bit trivial. In your MLP task, what dataset did you use? Can you evalaute your algorithm over more realistic tasks, such as ResNet on Cifar10?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730703898445

thread_type:
official_review

<thread_object>
creator: reviewer_raxz

<content>
summary:
This paper proposes a novel approach MoTEF to achieve an asymptotic rate matching that of distributed SGD under arbitrary data heterogeneity by adding momentum tracking and error feedback technique, solving a theoretical obstacle in decentralized optimization with compression. This paper conducts numerical experiments to illustrate the effectiveness of MoTEF.

strengths:
1. MoTEF achieves the convergence rate matching distributed SGD without strong assumptions, such as bounded gradient or global heterogeneity bound. It is an important improvement in distributed optimization with compression.
2. MoTEF supports arbitrary contractive compressors (variance-bounded estimate) without unbiasedness.
3. Extension MoTEF to the stochastic setting can achieve an improved rate with variance reduction.
4. This paper proposes theoretical analysis under the PL condition.

weaknesses:
1. The comparison needs to be more clarified and detailed. Especially, the total communication complexity is important in optimization with compression. Most compression algorithms can only reduce the communication overhead of single-step iteration, but cannot reduce the total communication overhead required for convergence. It is necessary to discuss it in detail.
2. Though the numerical experiments are enough to illustrate the effectiveness of MoTEF, more evidences in practical problems are necessary. For example, a lightweight training on transformers instead of only MLP.

questions:
1. Though the proof is clear enough, I am interested in the insight of the construction of the  Lyapunov function. Adding an overview of the technique before the theoretical results is better.
2. It is a valuable study. If the author explains my concerns, I would like to improve my score.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732051136524

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response to all reviewers

comment:
We thank the reviewer very much for their dedication to the review process and for taking the time to carefully study our manuscript. We provide detailed responses to all raised concerns. Moreover, we made several changes to the paper and highlighted them in blue color. In particular, $(i)$ we simplified the convergence rate of MoTEF and MoTEF-VR algorithms by removing non-dominant terms; see (10, 11, 13); $(ii)$ we fixed the section D.5 that contains experiments in the training CNN model on MNIST dataset. Now we provide the correct plots of convergence; $(iii)$ we added a comparison against CEDAS in section D.6; $(iv)$ we tightened the analysis of MoTEF algorithm. In section B.1.1 we provide a more accurate analysis that demonstrates that the consensus error $\Omega_3^t = \mathbb{E}[\\|\mathbf{X}^t - \bar{\mathbf{x}}^t\mathbf{1}^\top\\|\_{\mathrm{F}}^2]$ converges to zero. This implies that the local models $\\{\mathbf{x}\_i^t\\}_{i=1}^n$ also converge; see the derivations in Section B.1.2.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733302349169

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of the discussion period

comment:
Dear reviewers,

As the discussion period comes to an end, we would like to summarize it now.

1) All reviewers highlighted the importance of our theoretical contribution. In particular, convergence under arbitrary data heterogeneity and arbitrary contractive compression (reviewers rAXz, DZJC, SzmB).
2) We provided a detailed comparison of biased and unbiased compressors in the response to reviewer SzmB where we highlight that biased compression schemes are superior in practice, achieve smaller variance both theoretically and practically, and are known to match the lower bound with distortion $\alpha$ and $b$ encoding bits. This is particularly important in the comparison with decentralized algorithms that rely on unbiased compression (e.g., CEDAS). To support these claims empirically, we added the comparison against CEDAS algorithm on non-convex logistic regression.
3) We improved the convergence of MoTEF by demonstrating that the consensus error $\Omega_3^t = \mathbb{E}[\\|\mathbf{X}^t - \bar{\mathbf{x}}^t \mathbf{1}^\top \\|^2_{\mathrm{F}}]$. This implies that not only the average models converges, but each local models as well.
4) We demonstrated that MoTEF matches the asymptotic and deterministic rates of state-of-the-art centralized algorithms if we set the spectral gap $\rho=1$. Moreover, we showed that MoTEF improves the communication complexity in the asymptotic regime.
5) We acknowledge the importance of providing the comparison of MoTEF algorithm against other baselines in training larger models. We work on extending the empirical comparison against other baselines.

Best regards,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposed a decentralized stochastic optimization algorithm with communication compression with momentum tracking and error feedback. While the algorithmic ingredients are not new per se, the assembly and analysis that leads to a state-of-the-art convergence rate for an important problem is worth acceptance.