2Direction: Theoretically Faster Distributed Training with Bidirectional Communication Compression
We consider distributed convex optimization problems in the regime when the communication between the server and the workers is expensive in both uplink and downlink directions. We develop a new and provably accelerated method, which we call 2Direction, based on fast bidirectional compressed communication and a new bespoke error-feedback mechanism which may be of independent interest. Indeed, we find that the EF and EF21-P mechanisms (Seide et al., 2014; Gruntkowska et al., 2023) that have considerable success in the design of efficient non-accelerated methods are not appropriate for accelerated methods. In particular, we prove that 2Direction improves the previous state-of-the-art communication complexity $\widetildeΘ\left(K \times \left(\frac{L}{αμ} + \frac{L_{\max} ω}{n μ} + ω\right)\right)$ (Gruntkowska et al., 2023) to $\widetildeΘ(K \times (\sqrt{\frac{L (ω+ 1)}{αμ}} + \sqrt{\frac{L_{\max} ω^2}{n μ}} + \frac{1}α + ω))$ in the $μ$-strongly-convex setting, where $L$ and $L_{\max}$ are smoothness constants, $n$ is # of workers, $ω$ and $α$ are compression errors of the Rand$K$ and Top$K$ sparsifiers (as examples), $K$ is # of coordinates/bits that the server and workers send to each other. Moreover, our method is the first that improves upon the communication complexity of the vanilla accelerated gradient descent (AGD) method (Nesterov, 2018). We obtain similar improvements in the general convex regime as well. Finally, our theoretical findings are corroborated by experimental evidence.
Paper
Similar papers
Peer review
Summary
This paper proposes 2Direction, a new GD-based distributed training algorithm for convex optimization problems. The improvement of 2Direction over previous works that target communication complexity in the convex case is that 2Direction is both accelerated and allows for bi-directional compression. 2Direction is proven to offer better communication complexity than previous works in certain regimes and not being worse otherwise.
Strengths
1. The scope of the paper and the main problem are well-defined and clear. 2. The paper considers bi-directional compression. SO far, bi-directional compression received less attention in the literature that mostly considers only compressing uplink communication. 2. The paper’s theoretical analysis and results are mostly clear and solid. The paper theoretically compares 2Direction to several SOTA alternatives. 3. The design choices of 2Direction are well articulated.
Weaknesses
1. The communication complexity analysis and its optimization are not fully clear. Specifically, there is dependency between the round cost and the number of communication rounds (i.e., via K and w). 2. 2Direction (Algorithm 1) requires more memory and compute resources in comparison to some previous methods such as DG, AGD and EF21-P + DIANA (e.g., 2Direction requires arrays for storing h, v and solving (11)-(12)-(23)). This overhead and its consequences, especially in federated learning contexts, are not discussed. 3. The experimental part is somewhat weak (appears in the supplementary material and contains a single logistic regression problem with two datasets). 4. The presentation can be improved. In particular, the paper is not self contained and relies on the supplementary material to convey main ideas. Notably: (i) Section 4 points to Sections B and C to articulate design choices; (ii) Section 5.2 points to equations 58 and 63
Questions
1. Can the authors comment on weaknesses (1)(2)(3)? 2. Can the authors shed more light on why with small probability exact values must be sent? Clearly the proof requires this, but more intuition on whether this is inherent or just an artifact of the proof technique would be helpful. 3. The comparison/analysis is done with TopK (downlink) and RandK (uplink) as example compressors. However, these compressors have weaker worst-case MSE guarantees in comparison to SOTA compression techniques that provide asymptotically better worst-case tradeoffs between communication and MSE. Can the authors shed light on that? In particular, if compressors with stronger guarantees are used, can that affect the communication complexity analysis? E.g., since line 10 in algorithm 1 can be viewed as an instance of the distributed mean estimation problem, can the usage of techniques such as [1]-[3] lead to better communication complexity or alter the conclusions? (this also relates to weakness (1)) 4. Assumption 2.4 – while the independence between the workers in the uplink direction is indeed desired, why independence with the downlink direction is important? [1] Suresh, Ananda Theertha, et al. "Distributed mean estimation with limited communication." International conference on machine learning. PMLR, 2017. [2] Davies, Peter, et al. "New Bounds For Distributed Mean Estimation and Variance Reduction." International Conference on Learning Representations, 2021. [3] Vargaftik, Shay, et al. "Eden: Communication-efficient and robust distributed mean estimation for federated learning." International Conference on Machine Learning. PMLR, 2022.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
The authors clearly stated a limitation of their work in Section 8. I do have few additional suggestions about the memory/computational efficiency aspect. Moreover, since federated learning (FL) is mentioned as motivation, it worth discussing whether 2Direction can be potentially extended to common FL scenarios with partial participation and stochastic gradients. I did not recognized potential negative broader impact.
Summary
This paper proposes a new distributed convex optimization problems with bidirectional compression. This algorithm, named as 2Direction, is claimed to be the first that improves upon the communication complexity of the vanilla accelerated gradient descent.
Strengths
1. The 2Direction method seems novel 2. The studied problem is well-motivated
Weaknesses
1. The proof of the algorithm is rather complicated. I cannot verify the solidness of the established theorem given the very tight review timeline. The appendix I, J, K, L and O are very scary given the symbolically computed expressions. It is basically a computer-aided proof. I will discuss with other reviewers and chairs on how to check this proof. 2. In table 2, some terms are associated with $\Omega$ while the others are not. Please clarify the reason. 3. 2Direction uses a unbiased compressor and a contractive compressor in algorithm design. Can 2Direction use unbiaed compressors for both w2s and s2w compression? Can 2Direction use contractive compressors for both w2s and s2w compression? 4. Does 2Direction have the smallest communication complexity when r = 0 compared with existing uni-directional compression algorithms? Since I cannot verify the correctness of the established theorem, I would recommend borderline reject at this stage.
Questions
See above
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
N/A
Let us have some deep discussion here
To Reviewer: Thanks for the questions. Could you check if the author answered your concerns? To Authors: a followup question for 3. Can you explain why the biased compression cannot be allowed, given it is allowed for analyzing the stochastic algorithms such as DoubleSqueeze [Tang et. al. 2019]?
> To Authors: a followup question for 3. Can you explain why the biased compression cannot be allowed, given it is allowed for analyzing the stochastic algorithms such as DoubleSqueeze [Tang et. al. 2019]? Note that the biased compression *is allowed* on the *server's side*. Let us discuss the compression on the *workers' side*. First, notice that our goal was to design a method that will get the communication complexities guarantees that are not worse than AGD (that does not compress). Our work showed that it is possible to accomplish with unbiased compressors on the *workers' side*. However, the design of a method that will use biased compressors both on the *server's side* and on the *workers' side* is a very challenging task if we care about obtaining strong theoretical guarantees. Indeed, the theoretical communication guarantees of such methods are much worse than the communication guarantees of AGD (that does not compress). In particular, consider DoubleSqueeze [Tang et. al. 2019]. It requires stronger assumptions (Assumption 1.3 or the bounded gradients assumption) than our work and AGD. Next, the worst-case theoretical communication complexity of this work is $\frac{d^2}{K} \times \frac{1}{\varepsilon^3}$ to find an $\varepsilon$-stationary point with Top$K.$ Another recent work \[1\] with only biased compressors guarantees the communication complexity $\frac{d^2}{K} \times \frac{L_{\max}}{\mu} \log\frac{1}{\varepsilon}.$ The same reasoning applies to Dore \[2\]. The communication complexities of such methods are clearly worse than the communication complexity $d \times \sqrt{\frac{L}{\mu}} \log \frac{1}{\varepsilon}$ of AGD (that does not compress!). In other words, we do not allow biased compression on the workers' side because we do not know how to design a method that will have communication guarantees not worse than in AGD. As far as we know, nobody knows how to solve this challenging task. Our work can be a starting point to solve it. Another orthogonal motivation behind using the *unbiased compressors* is their scaling with the number of nodes $n$. The larger $n,$ the smaller the effect of the noises from the *unbiased compressors.* It can be seen in the complexities of EF21-P + DIANA and 2Direction in Table 1. The noise from the *biased compressors* does *not* decrease with the number of nodes $n.$ \[1\]: Fatkhullin I. EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback \[2\]: Liu et al A double residual compression algorithm for efficient distributed learning, 2019
Summary
This paper studies 2Direction, a new method for compressed communications for the centralized distributed convex optimization problem, in the case where both worker-to-server and server-to-worker communications are compressed. Compared to previous work EF21-P+DIANA, it guarantees a total communication complexity no worse than Nesterov's accelerated gradient methods.
Strengths
* The paper introduces a new objective of minimizing the *total communication complexity*, which is well defined through equation 4 and clearly explained with the problematic lines 118-122. * To alleviate some of the burden of understanding the seemingly cumbersome algorithm and proof, efforts were made to describe some of the steps of the research/thought process that led to the final method in Section 4, and to provide a sketch of the proof in Section 7. * For reproducibility purposes, I appreciated the presence of the SymPy code used for the symbolic computation part of the proof. * The final result is original, seems to have required more than a *"small tinkering"* of previous methods (Section 4), and displays both theoretical and practical improvements over previous state of the art algorithms.
Weaknesses
* While efforts were made to ease the understanding of the general ideas behind the algorithm and proof, they seem so cluttered that it deters from delving into the technical details.
Questions
* line 130 claims a *"new error feedback mechanism"* but only compares it to the EF21-P method. What is the difference between equation 9 and other mechanisms such as MEM-SGD [1] ? * In the experiments part (appendix Q), why use a single value of $K$ ? Would it be possible to display the evolution of the convergence rate at different degrees of compression ? * line 1033, the stepsize $\bar L$ is said to be finetuned. However, if we assume $L = L_{\max}$ (which we can find for logistic regression), wouldn't equation 44 give a closed form expression of $\bar L$ ? **Typos :** * The order of Equations 6 and 7 seems to have been reversed. * line 195: a *"and"* seems to have been left between *"general analysis"*. **References :** [1] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. *Sparsified SGD with memory*. In NeurIPS, 2018.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
*
Summary
The authors considered a distributed convex optimization setting where both uplink and downlink communications should be considered. In this setting, the authors proposed an accelerated method called 2Direction which generalizes AGD into the bidirectional compressed communication setting and prove its convergence rate and communication complexity. Finally, empirical results are provided.
Strengths
For this new setting, the authors propose new strategies to make the adaption of AGD possible, which is nontrivial. Meanwhile, the bounds seem OK to me and can be applicable in the smooth transition from uplink to downlink.
Weaknesses
Such a generalization for the bidirectional case fills an important gap, but it lacks enough motivational examples for why such settings deserve study. The algorithm name 2Direction is confusing as we don't really know what it means. It is better to follow the tradition and use the abbreviation of the full algorithm name. The authors show the motivation of the new strategy is the existing approaches failed in the bidirectional case but don't show the concrete reason why failed. Is the failure superficial or essential? The experiments should be included in the main body.
Questions
See Weaknesses
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
No
Thank you for your answers. *W1:* based on your answer, is it correct that the reduction in communication complexity comes at the expense of more training rounds? For example, is it right that if K=1, 2Direction requires asymptotically more rounds (and by that gradient computations) than AGD? If this is the case, this should be discussed and conveyed as a legitimate tradeoff (at least for some reasonable choices of K). *W2:* Having previous works doing the same is evidence of a common difficulty in these sorts of algorithms, but it does not shed any light on whether this is an artifact of the proof method or the problem itself. *W3:* How to properly choose K or how different compressors with different guarantees affect the converge rate (and not only the communication complexity) is not discussed but left for the reader to deduce. This also relates to *W1*. *W4:* If I understand your answer correctly, is this assumption required to complete the proof? In that case, is there a simple example where dependence only in the downlink direction prevents convergence or asymptotically slows it down?
> W1: based on your answer, is it correct that the reduction in communication complexity comes at the expense of more training rounds? For example, is it right that if K=1, 2Direction requires asymptotically more rounds (and by that gradient computations) than AGD? If this is the case, this should be discussed and conveyed as a legitimate tradeoff (at least for some reasonable choices of K). > W3: How to properly choose K or how different compressors with different guarantees affect the converge rate (and not only the communication complexity) is not discussed but left for the reader to deduce. This also relates to W1. Yes, if we take $K = 1,$ then our method will theoretically require more communication rounds than if $K$ was equal to $d$. **However, this is the case of all methods that reduce communication complexity,** just like every analysis of SGD with minibatch size equal to 1 will require more iterations than the full batch case. This is normal, and to be expected. What matters is the total complexity. In our case, it is the product of the number of communication rounds and the bits transferred in each round. We discuss this at length in the paper. Indeed, it turns out that $K = 1$ may not the best choice if we *also* care about the number of gradient computations. We can ask ourselves what is the maximum $K$ we can take that preserves the best complexity. Let us consider our complexity with the Rand$K$ and Top$K$ compressors. Then the communication complexity equals $$K \times \left(\sqrt{\frac{d}{K}}\sqrt{\frac{L}{\mu \alpha}} + \frac{d}{K}\sqrt{\frac{L_{max}}{\mu n}} + \frac{1}{\alpha} + \omega\right) = O\left(\sqrt{d K}\sqrt{\frac{L}{\mu \alpha}} + d\sqrt{\frac{L_{max}}{\mu n}} + d\right).$$ From the last formula, it is clear that we should take $K \leq d \alpha \min\left\[\frac{L_{max}}{L n}, \frac{\mu}{L}\right\]$ in order to preserve the best communication complexity. So instead of $K = 1,$ one can take $K = d \alpha \min\left\[\frac{L_{max}}{L n}, \frac{\mu}{L}\right\].$ We agree that it is not obvious how to calculate this formula in practice. However, we can try to find some reasonable bound for it. For instance, we can know that our problem is well-conditioned: $L / \mu \ll n.$ Thus we can take $K = \frac{d \alpha}{n}.$ In practice, the parameter $\alpha \approx 1$ in the Top$K$ compressor, thus the reasonable choice is $K = \frac{d}{n}.$ With this choice, the number of rounds equals $$\left(\sqrt{\frac{d}{K}}\sqrt{\frac{L}{\mu \alpha}} + \frac{d}{K}\sqrt{\frac{L_{max}}{\mu n}} + \frac{1}{\alpha} + \omega\right) = \sqrt{\frac{n L}{\mu \alpha}} + \sqrt{\frac{L_{max}}{\mu}} + \frac{1}{\alpha} + n.$$ Assume that $\alpha \approx 1,$ then the number of rounds is not greater than $\sqrt{\frac{n L}{\mu}} + n.$ Unfortunattely, this number is greater than the number of rounds $\sqrt{\frac{L}{\mu}}$ of AGD (In all previous methods from Table 1, this gap is even worse). However, our method reduces the communication complexity! The same derivation one can do with other compressors instead of Rand$K$ and Top$K$. We believe that we answered the reviewer's question. We agree that this is an interesting discussion; we will be happy to add it to the paper. However, the main scope of our paper is communication complexity. > W2: Having previous works doing the same is evidence of a common difficulty in these sorts of algorithms, but it does not shed any light on whether this is an artifact of the proof method or the problem itself. If this comment related to "Can the authors shed more light on why with small probability exact values must be sent?", then we tried to explain it in as much detail as possible. The same problem was in many related works; the problem appears in our work. This is just the nature of accelerated variance-reduced methods. **Note that we show that this does not have an adverse effect on the communication complexity.** This is clearly not a weakness of our paper. > W4: If I understand your answer correctly, is this assumption required to complete the proof? In that case, is there a simple example where dependence only in the downlink direction prevents convergence or asymptotically slows it down? Notice that this assumption was considered in all previous papers on bidirection compression. We do not assume anything additional here. This is a standard assumption in the literature. Returning back to the question, the reviewer can look at Lines 528-529. In order to use Definition 2.2, we have to use that the fact $C^P$ is independent of $u^{t+1}$ and $q^{t+1}.$ For instance, the vector $u^{t+1}$ depends on $C^{D,y}_i$ and on the realization of $C^P$ from the previous iteration. In this place, the independence of compressors helps us to finish the proof. If you have more questions, we will happy to answer them.
I respectfully disagree with crucial parts of the response as described below. **W1+W3:** The analogy to GD vs. SGD is misleading. SGD often exhibits many benefits in practice, such as faster convergence, noise regularization, memory efficiency, and the ability to handle large datasets. 2Direction was not shown to provide such benefits. On the contrary, in a balanced setup where networking and compute resources exhibit balanced utilization (which is desired), 2Direction may severely degrade the convergence time; 2Direction may force the participants to a significantly longer training procedure even though the total communication complexity is reduced. Moreover, the new analysis shows that even for the best choice of K proposed by the authors, 2Direction requires a factor of $\sqrt n$ more training rounds than AGD (this increases with n!). **W2+W4:** The reviewer understands that the same ingredients are present in previous works and does not consider them a weakness. It is, however, somewhat weakening not having evidence or intuition as to whether these are an artifact of the proof methods or inherently required to improve communication complexity (both outcomes are fine). The reviewer appreciates the difficulty in constructing the proof and the careful design of the algorithm that allows for that proof and understands that the contribution of the paper is theoretical. But the paper draws motivation from distributed/federated learning. Thus, there is an expectation that the theory will reflect inspiration from realistic setups and that the solution to the theoretical problem can be used to design better solutions for such setups. On that front, the paper needs evidence that 2Direction can be used for such a purpose. This makes it hard to appreciate the significance of the theoretical result. I strongly encourage the authors to present evidence (e.g., more evaluation) that 2Direction can improve convergence time or clearly and explicitly address/discuss all aspects of the work, including its practical limitations.
Reply to "Official Comment by Reviewer AqDA", part 1
> W1+W3: The analogy to GD vs. SGD is misleading. We believe the analogy is in fact, nearly perfect. Indeed, in W1 you wrote "W1: based on your answer, is it correct that the reduction in communication complexity comes at the expense of more training rounds? For example, is it right that if K=1, 2Direction requires asymptotically more rounds (and by that gradient computations) than AGD? If this is the case, this should be discussed and conveyed as a legitimate tradeoff (at least for some reasonable choices of K)." Based on our knowledge, just like - all variants of SGD we know of require more iterations than GD in the same regime, but have cheaper per-iteration cost (= computation cost of forming the gradient estimator), and the product of the two (= gradient evaluation complexity) is what matters, - all variants of compressed gradient methods we know of require more iterations (= communications), but have cheaper per-iteration cost (= cost of communication, which is equal to w2s communication in the one-directional setup, and w2s + s2w communication in the bi-directional setup; also notice that virtually all of these works assume the computation cost is zero when providing bounds), and the product of the two (= communication complexity) is what matters. This analogy is indeed nearly perfect in our view. Notice that many variants of compressed gradients methods can be formally be viewed as variants of SGD in which compression replaces subsampling as the source of stochasticity; further strengthening this analogy; see [P1] [P1] Gorbunov et al, A unified theory of SGD: variance reduction, sampling, quantization and coordinate descent, AISTATS 2020. As all analogies go, our also needs to be understood in the limits in which it was intended to apply. When you subsequently say that "The analogy to GD vs. SGD is misleading. SGD often exhibits many benefits in practice, such as faster convergence, noise regularization, memory efficiency, and the ability to handle large datasets. 2Direction was not shown to provide such benefits.", you bring new considerations into the discussion which were not intended to be covered by our analogy. We think that this is not fair. Our brief response to these new considerations follows: - In theory, "faster convergence" of SGD refers to the product of the number of iterations and the minibatch size. Indeed, SGD is faster than GD in this sense; this is well known, and can be seen very clearly in, e.g., Gower et al, SGD: general analysis and improved rates, ICML 2019. However, in a very precise sense (in terms of communication complexity defined above), unidirectionally compressed gradient descent methods were shown to be faster than GD (see the complexity of DIANA in [P1], and in the original paper it refers to, for example). - Compressed gradient methods also enjoy some level of noise regularization -- from the noise inherent in the compressors. This is well known. - Unlike traditional SGD, which is designed to work in the single-machine regime, compressed gradient descent methods are designed to work in the distributed regime, where communication efficiency is more typically seen as more important than memory efficiency. Having said that, there are variants of SGD (e.g., SAG, SAGA, SVRG) which work with control variates which require more memory, and in the same manner there are variants of compressed gradient methods (e.g., DIANA, ADIANA, PAGE, MARINA) which require more memory for the exact same reason. Just likes these methods, our 2Direction method requires a bit of extra memory. However, what we gain is a method with vastly improved communication complexity. - Re "ability to handle large datasets" - we study the distributed setup precisely because single node methods are unable to do so. So, 2Direction is in principle better suited to handling large datasets. Because of what we say above, we do not see how what we said was misleading.
Reply to "Official Comment by Reviewer AqDA", part 2
> On the contrary, in a balanced setup where networking and compute resources exhibit balanced utilization (which is desired), 2Direction may severely degrade the convergence time; 2Direction may force the participants to a significantly longer training procedure even though the total communication complexity is reduced. In virtually all theoretical works on communication efficient distributed optimization, communication complexity is the key quantity of interest, and local computation time is not taken into consideration (in the associated theory). We know about a couple of exceptions only, including [P2] Malinovsky et al, Variance reduced ProxSkip: algorithm, theory and application to federated learning, NeurIPS 2022 (see Section 5). This is because these works assume that the system is communication bound, i.e., communication is much more expensive than computation, and the algorithms in this genre, including 2Direction, cater to this setup. Therefore, your criticism "in a balanced setup where networking and compute resources exhibit balanced utilization" does not apply to our work - our method is not designed to deal with this regime since indeed in this case compressing communication does not make sense. This is the situation with all methods employing communication compression. So, your criticism is generic and applies to the whole field of compressed communication, and not merely to our paper. However, it is also trivial since these methods are not designed to handle this balanced regime. So, we believe that this criticism is not appropriate. Having said that, we are most happy to include a discussion of this (obvious) limitation of all works on compressed communication. > Moreover, the new analysis shows that even for the best choice of K proposed by the authors, 2Direction requires... In communication-bound settings, communication complexity is what matters. *All* methods that perform communication compression try to achieve this by an optimal balance of the number of communication rounds (which is a nondecreasing function of the compression ratio), and the compression ratio -- optimal in the sense of communication complexity. As we have remarked before, in practice it is often possible to obtain a certain limited compression ratio without the need to increase the number of comm. rounds at all. Once this limit is reached and exceeded, the number of required comm rounds increases, but the comm complexity may still decrease, up to some optimal compression ratio, after which deterioration of comm complexity starts. > W2+W4: The reviewer understands that the same ingredients are present in previous works and does not consider them a weakness. It is, however, somewhat weakening not having evidence or intuition as to whether these are an artifact of the proof methods or inherently required to improve communication complexity (both outcomes are fine). We do not know if such an increase in memory is necessary to obtain our superior comm complexity bounds, but we certainly think so, since the kinds of bounds we obtain seem to require the use of control variates (this was the case in all previous research in other domains we know of). We do not have a proof that a different method can't be constructed whose comm complexity would match that of 2Direction, but one that would need less memory. This can be a difficult problem to solve on its own if a definitive answer is sought. Having said that, we believe the mere fact that we obtain a new SOTA theoretical comm complexity (the first that always matches AGD and can beat it in some scenarios) for optimization with bi-directional communication compression is a breakthrough on its own, in a strongly contested area of research. > The reviewer appreciates the difficulty in constructing the proof and the careful design of the algorithm that allows for that proof and understands that the contribution of the paper is theoretical. Thank you! > But the paper draws motivation from distributed/federated learning. Thus, there is an expectation that the theory will reflect inspiration from realistic setups and that the solution to the theoretical problem can be used to design better solutions for such setups. On that front, the paper needs evidence that 2Direction can be used for such a purpose. This makes it hard to appreciate the significance of the theoretical result. We believe that our theory stands on its own - if one believes that theory has intrinsic value. Having said that, we perform some illustrative experiments which indicate that the theoretical benefits indeed translate to benefits in practice. Of course, more work needs to be done in this direction. We view our work as pioneering in this direction, and hence do not expect it's reasonable to expect that a single work will resolve all these issues.
Reply to "Official Comment by Reviewer AqDA", part 3
> I strongly encourage the authors to present evidence (e.g., more evaluation) that 2Direction can improve convergence time or clearly and explicitly address/discuss all aspects of the work, including its practical limitations. We can do so; this is easy to do. But we believe that our work is a theoretical breakthrough as it is, despite the fact that it can be somewhat strengthened by the inclusion of more experiments, and a more detailed account of limitations. We take these suggestions seriously, but we view them as minor. For all of the above reasons, we certainly think the score 4 is unjustified. **If you agree that we designed a new method which attains the current SOTA theoretical communication complexity rate in the important field of communication efficient distributed training with bi-directional compression, why would such a low score be appropriate? Empirical works with SOTA practical results routinely obtain very high scores despite not including any theory. We believe that theory and practice should be valued equally.**
My concerns, which I repeatedly point out, are about the **practicality and applicability** of 2Direction rather than about the validity of the theoretical results or the assumptions. 1. Take, for example, our discussion about the analogy of SGD vs. DG. In that regard, the authors made convincing arguments from a theoretical point of view, where my concerns are pointed out from a practical point of view where this analogy is far from perfect. SGD is known to offer practical improvements in metrics of interest, such as training time and cost. No such improvements were shown to be achieved by 2Direction; moreover, there is no evidence that they can be achieved or that 2Direction can lead to a similar solution that can. 2. Regarding the assumption that computation has zero cost, then why does limiting the algorithm to a single local gradient step make sense? Why even use first-order approximation and not, e.g., Neuton's method? Clearly, in any practical setup, this cost is not zero. Let me emphasize this point further. There are three main setups the paper may apply for (i) distributed learning in a cluster or cross-silo FL. Here the zero computation cost is not justified, as all entities are expected to have a lot of data. (ii) Cross-device FL. Here partial participation is not addressed. Again, I am not suggesting that 2Direction should address all these considerations, but without clarity about the assumptions and what they actually mean (i.e., the resulting limitations), it is difficult to appreciate the importance of the result. 3. Stating that communication compression makes no sense in a balanced system is wrong and goes against standard practice. Making more than a single local gradient step or increasing batch size (e.g., via gradient accumulation) to produce higher-quality updates that essentially require **less** communication rounds to converge in practice is one of the motivations behind algorithms such as federated averaging. Namely, one can achieve balance by making more local computations and compressing communication - in other words, compression is an important ingredient in achieving this. 4. I strongly agree that theory has intrinsic value. However, the fact that something is hard to prove does not mean it is important or interesting. I am not suggesting that 2Direction is not important or interesting, just that the paper does an insufficient job of making that clear or being explicit about what was actually achieved that has practical value or offers new high-level insights that were missed by previous works. 5. I do not find my criticism generic. Generally, the fact that previous works assumed something does not mean that these assumptions should be accepted without any hesitation or criticism today or in the future. In fact, reexamining assumptions is at the very heart of progress. Therefore, stating that something critical is assumed because it was assumed by previous works and not convincing why this assumption makes sense today can be viewed as generic. 6. To conclude, the authors stated in their response: **.. So, your criticism is generic and applies to the whole field of compressed communication, and not merely to our paper. However, it is also trivial since these methods are not designed to handle this balanced regime. So, we believe that this criticism is not appropriate. Having said that, we are most happy to include a discussion of this (obvious) limitation of all works on compressed communication. ** I find everything in this sentence to be wrong: (1) I have concerns regarding 2Direction. I have not reviewed the entire field of compressed communication, and I do not think that 2Direciton represents the entire field. (2) There is nothing trivial about the zero-computation assumption, and there are papers that address the practically common balanced regime where an improvement of even a few percent in networking or compute time may be important (e.g., [1] and reference therein). (3) The limitations are not obvious and are easy to miss, as the connection to practical scenarios in the paper is vague. To conclude, I appreciate the time the authors spent addressing my concerns. Considering **all** the arguments made by the authors (where with some of them I disagree), I am raising my score from 4 to 6 based on my understanding that the theoretical result achieved in this paper is important and can encourage further progress and lead to more practical solutions with reduced communication complexity. I hope that the authors will discuss explicitly in the paper the assumptions and their resulting practical limitations and encourage future research to address these limitations. [1] Wang, Z., Lin, H., Zhu, Y. and Ng, T.E., 2023, May. Hi-Speed DNN Training with Espresso: Unleashing the Full Potential of Gradient Compression with Near-Optimal Usage Strategies. In Proceedings of the Eighteenth European Conference on Computer Systems (pp. 867-882).
It is worth to discuss the relationship with [10, 9, 3]
How is the 2Dicrection compression approach different from the "error compensated" compression in double directions in [3, 9, 10]?
From the theoretical point of view, we can get substantially better theoretical guarantees. The works [9,10] consider only the non-convex setting and obtain the convergence guarantees of the norm of gradients, so their result is much weaker in the convex case. Also, [9,10] require stronger assumptions (e.g., Assumption 3.3. in [9] and Assumption 1.3 in [10]). In the convex case, [3] is not ignored in Table 1 (Dore method in Table 1). This work requires $\frac{\omega}{\alpha n} \frac{L_{\max}}{\mu} \log \frac{1}{\varepsilon}$ rounds to converge. This complexity is strictly higher (= worse) than our guarantees (see 2Direction in Table 1). For example, the theory in [9] is strictly worse than the previously best-known theory for bi-directional compressed methods provided in [12] (also, there is a mistake in their proof - their final complexity is worse in its dependence on the contraction factor of the compressor). Their paper is in this sense not interesting from the theoretical point of view. However, it's an excellent empirical work. Our work massively improves on the previous theoretical SOTA from [6], which provides much better guarantees than [12]. So, in brief, **our theory >> theory from [6] > theory from [12] > theory from [9].** Such comparisons can be made with all other previous results., including [3], [8], [10], [11]... From the design's view, we discuss the difference between our approach and the previous approaches in detail in Section 4. Let us briefly repeat it here: *On the workers' side*, we do *not* use the "error compensated" compression. Our compression technique is based on works of \[5\], which is very different and only works with unbiased compressors. *On the server's side*, our compression technique is new. The difference of designs we discuss in Lines 167-176. Algorithmically, our approach and the "error compensated" compression are different. One can compare the formulas (8) and (9). [12] Fatkhullin et al, EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback, 2021
Decision
Accept (poster)