Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity

Thank you for your review and for acknowledging the contributions of our research. We will now address each of your comments and provide clarifications.

Weaknesses

The main weakness of the paper is the assumption of data homogeneity. While I understand that this assumption is necessary, it would be interesting to include experimental evidence in the main text showing how MARINA-P performs with heterogeneous data.

The assumption of data homogeneity is not necessary, and we do not assume it! While it is true that MARINA-P and M3 perform exceptionally well in the close-to-homogeneous regime, all our main results hold for arbitrarily heterogeneous clients. The only requirement is that the functional $(L_A,L_B)$ inequality holds. Importantly, for this to be true, the local functions do not need to be homogeneous. In fact, the functional $(L_A,L_B)$ inequality is weaker than the $L_i$-smoothness of the local functions $f_i$, which can clearly hold in heterogeneous scenarios.

The following might be erroneous, but to me seems like that the overall number of coordinates sent in the uplink is $d$. From the discussion in subsection 4.5 it seems like that the parameter vector is permuted and divided into non-overlapping chunks, and each chunk is sent to a different client. As such, it looks like that the overall number of coordinates sent to the server is $d$.

Yes, it is true that each client receives $\approx d/n$ coordinates, so the total number sent by the server is $d$ (as is the case for any sparsifier with the same sparsification level). Notice that without compression, the server would send $d$ coordinates to each worker, resulting in a total of $n \times d$ instead of $d$ coordinates sent.

Questions

Related to my previous point, how many coordinates are sent into the uplink at each round from the server to all users? i.e. what is the support of $\sum \mathcal{C}_i(x)$?

As mentioned previously, the server sends $K \approx d/n$ (distinct) coordinates to each client in the case of the permutation compressors, and $\sum \mathcal{C}_i(x) = x$.

Is MARINA-P compatible with client selection? Meaning, is it possible to apply MARINA-P if, at each round, the number of users varies or a different subset is chosen?

Such behavior can be modeled using a specific compressor that satisfies Definition 1.4, and hence our theory applies. Specifically, let us define a compression operator $\mathcal{C}$ via $\mathcal{C}(x) = \mathcal{\bar{C}}(x)$ with probability $p$, and $0$ otherwise, where $\mathcal{\bar{C}} \in \mathbb{U}(\bar{\omega})$. It can easily be shown that $\mathcal{C} \in \mathbb{U}(p\bar{\omega}+1-p)$. In this model, the case when $\mathcal{C}(x) = 0$ can be interpreted as a worker not participating in this step.

Would it be possible to compare MARINA-P to other state-of-the-art schemes that use masking to reduce communication (e.g., SPARSE RANDOM NETWORKS FOR COMMUNICATION-EFFICIENT FEDERATED LEARNING)?"

First, [5] focuses on training sparse networks, whereas our objective is the optimization of a general objective function. More importantly, the method in [5] does not address communication reduction in the downlink direction. The primary goal of the proposed FedPM algorithm is to train a probability mask to find the optimal sparse random network within the original random one, aiming to reduce the uplink communication cost. In contrast, this paper targets both downlink and uplink communication directions. MARINA-P specifically targets the downlink communication direction. Since these two algorithms address different goals, a direct comparison is not evident.

[5] Isik, B., Pase, F., Gunduz, D., Weissman, T., & Zorzi, M. (2022). Sparse random networks for communication-efficient federated learning. arXiv preprint arXiv:2209.15328.

---

We hope that the explanations provided adequately address the reviewer’s comments. Should any additional clarifications be required, we are happy to provide them.

Thank you for your review and appreciating the strengths of our work. We would like to address your concerns and provide additional explanations.

Weaknesses

The authors use the lower bound on the rounds communication to claim a lower bound on the communication load....

As far as we understand, the reviewer is pointing to a possible gap in our first contribution from Section 3. We believe that there may have been a misunderstanding, and there are no gaps in our argument.

First of all, we are careful with our claims and only provide the lower bound $\Omega\left( \frac{(\omega + 1) L \delta_0}{\varepsilon} \right)$ for the number of iterations/rounds. We have never provided a lower bound on the communication load, and never claimed that the overall communication load is lower bounded by $d$ times that function, given that the full gradient contains $d$ entries. Once again, we only proved the lower bound $\Omega\left( \frac{(\omega + 1) L \delta_0}{\varepsilon} \right)$ for the number of iterations/rounds, where $\omega$ is the variance from Definition 1.4.

We are on the same page with the reviewer that in order to determine the communication complexity, we have to multiply the number of iterations/rounds by the number of entries/coordinates of a compressor. For simplicity, let us consider the Rand$K$ compressor, which sends $K$ random coordinates and has variance $\omega = \frac{d}{K} - 1.$ Assuming that the server uses Rand$K$ in every iteration/round, the lower bound on the communication complexity is $K \times \Omega\left( \frac{(\omega + 1) L \delta_0}{\varepsilon} \right) = K \times \Omega\left( \frac{d L \delta_0}{K \varepsilon} \right) = \Omega\left( \frac{d L \delta_0}{\varepsilon} \right),$ because, as the reviewer noted, we have to multiply by $K$ (not $d,$ as both we and the paper agree upon). Hence, we get the communication complexity $\Omega\left( \frac{d L \delta_0}{\varepsilon} \right)$ of GD. This argument leaves us no hope to improve the $\Omega\left( \frac{d L \delta_0}{\varepsilon} \right)$ communication complexity without an extra assumption.

It is worth noting that we do not prove a lower bound for the communication complexity $\Omega\left( \frac{d L \delta_0}{\varepsilon} \right)$ in general. Instead, we establish a lower bound $\Omega\left( \frac{(\omega + 1) L \delta_0}{\varepsilon} \right)$ for the number of iterations/rounds, and then, assuming that the server uses, for instance, Rand$K$ in every iteration, we get the $\Omega\left( \frac{d L \delta_0}{\varepsilon} \right)$ communication complexity. Even this result provides strong evidence that we need an extra assumption to get further theoretical improvement.

We believe that this clarification addresses the reviewer's concerns and explains that there are no mathematical gaps in our argument. We hope that the reviewer will reconsider the score. In case of any additional questions or if further clarification is needed, please let us know.

The concept of functional ($L_A, L_B$) inequality can be simplified since only $L_A$ is used in the main results. It can be stated such as the functions satisfy an $L_A$ condition, if we can find $L_B$ such that ineq. (9) is satisfied.

It is true that $L_B$ does not appear in the result from Theorem 4.6 and Corollary 4.7. This is a particular strength of MARINA-P with permutation compressors.

Let us look at the general results in Theorem D.1. (plus Theorem D.2 and Corollary D.4). The upper bound on the stepsize depends on $L_B^2\theta$, where $\theta$ is a compression parameter from Definition A.3. The reason why this term does not appear in Theorem 4.6 and Corollary 4.7 is that for permutation compressors, very conveniently one obtains $\theta=0$, which ultimately translates into superior complexity bound. However, the $L_B$ term is necessary for comparing this result with different compression schemes where $\theta>0$. Moreover, both $L_A$ and $L_B$ appear in the complexity bounds of M3 (Theorem 5.1), so their introduction in the main part of the paper is necessary.

Overall, the functional $(L_A,L_B)$ inequality enables us to capture the intricate structure of the objective function and obtain superior complexity results for certain objective functions (those satisfying the assumption with small $L_A$). This would not be possible without introducing both the $L_A$ and $L_B$ terms. While the second term on the right-hand side of (9) (the $L_B$ term) can be bounded by the first term using Jensen's inequality, reallocating mass from $L_B$ to $L_A$ results in worse theoretical guarantees. Therefore, keeping $L_A$ as small as possible is beneficial, as smaller values yield better complexity results. Hence, the possibility that $L_B > 0$ is critical for obtaining the enhancements we present. On the other hand, since in general $L_A\neq0$, requiring that the $(L_A,L_B)$ holds with $L_A=0$ would limit the applicability of our results.

We hope this clarifies why both terms are needed. Please let us know if there are any further questions.

Questions

Is there any connection between and the Hessians of the individual functions, similar to the smoothness parameter $L$, which can be interpreted as the largest eigenvalue of the Hessian of $f$?

Yes, there is such a connection! In fact, this result is already included in the paper. Please, see Theorem 4.8, where we derive $L_A$ and $L_B$ based on the Hessians of the functions $f_i$.

---

We hope that the explanations provided adequately address the reviewer's comments, and we kindly ask for a reconsideration of the score. Please let us know if more details or clarifications are needed.

\textstyle O\left(\frac{\delta^0 L}{\varepsilon} + \frac{\delta^0 L_A (\omega + 1)}{\varepsilon} + \frac{\delta^0 L_B (\omega + 1)}{\varepsilon \sqrt{n}}\right).

\textstyle O\left(\frac{d \delta^0 L}{n \varepsilon} + \frac{d \delta^0 L_A}{\varepsilon}\right).

\textstyle O\left(\frac{d \delta^0 L_{\max}}{n^{1/3} \varepsilon} + \frac{d \delta^0 L_A}{\varepsilon}\right).

We appreciate your comments and are grateful for highlighting the positive aspects of our work. We will now proceed to address the concerns you raised and provide clarifications.

Weaknesses

The compressor model (Definition 1.4), while standard in the federated learning literature, is somewhat contrived. It is primarily defined in its current form to facilitate analysis.

As in all mathematical theories, we need some assumptions about compressors to prove theorems and develop theory. Definition 1.4 is particularly useful because it not only facilitates analysis but also captures a wide variety of compressors.

It remains unclear whether the main conclusions derived under this model can be directly translated to the information-theoretic setting (quantization plus entropy coding), where compression efficiency is measured in terms of bits per sample.

In Tables 1 and 2, we compare the compression efficiencies of the algorithms based on the total number of coordinates sent to find a $\varepsilon$-stationary point. The formulas we compare there do not involve parameters and notations from Definition 1.4. Following the convention in virtually all papers in computer science published at NeurIPS, we ignore the fact that all computations use float32/64 instead of real numbers. With this simplification, sending one coordinate is equivalent to sending 32/64 bits. We acknowledge that addressing the errors arising from floating-point arithmetic is an important problem.

Questions

The role of $L_B$ is not completely clear, as it does not prominently affect communication complexities compared to $L_A$. Is it that by isolating $L_B$ from $L_A$, one can effectively reduce $L_A$ and, consequently, the communication complexities as well? Moreover, the class of functions for which $L_B$ is known to be positive is quite restricted (Theorem 4.5). It would be beneficial to find more general examples.

Thank you for your comment. We agree that a more detailed discussion of this point (currently in the appendix), would benefit the paper, and we are happy to include it in the revised version. Let us clarify the results.

Theorem 4.5 serves as an illustration of a case when $L_A=0$. However, please note that we do have much more general results with $L_B>0$ - see, for example, Theorem 4.8 (where we derive the constants $L_A$ and $L_B$ in terms of Hessians of the local functions $f_i$).

It is true that $L_B$ does not appear in the result from Theorem 4.6 and Corollary 4.7. However, this is not a disadvantage but rather a particular strength of MARINA-P with permutation compressors. To explain this, let us refer to a more general result in Theorem D.1. (along with Theorem D.2 and Corollary D.4). The upper bound on the stepsize depends on $L_B^2\theta$, where $\theta$ is a compression parameter from Definition A.3. The reason why this term does not appear in Theorem 4.6 and Corollary 4.7 is that for permutation compressors, we very conveniently obtain $\theta=0$, which ultimately translates into a superior complexity bound.

The functional $(L_A,L_B)$ inequality enables us to capture the intricate structure of the objective function and achieve superior complexity results for certain objective functions (particularly those satisfying the assumption with small $L_A$). This would not be possible without introducing both the $L_A$ and $L_B$ terms. While the second term on the right-hand side of (9) (the $L_B$ term) can be bounded by the first term using Jensen's inequality, reallocating mass from $L_B$ to $L_A$ results in worse theoretical guarantees. Therefore, keeping $L_A$ as small as possible is beneficial, as smaller values yield better complexity results, and hence the possibility that $L_B > 0$ is critical for obtaining the enhancements we present. Furthermore, in general $L_A\neq0$, so requiring that the $(L_A,L_B)$ inequality holds with $L_A=0$ would limit the applicability of our results.

Lastly, both $L_A$ and $L_B$ appear in the complexity bounds of M3 (Theorem 5.1), making their introduction in the main part of the paper necessary.

We hope this clarifies the topic. Please let us know if there are any further questions.

---

We appreciate your constructive feedback and trust that our responses have satisfactorily addressed the questions. Should any additional clarifications be required, we are happy to provide them.

Thank you for your feedback and for recognizing the strengths of our work. We will now address each of your comments in detail.

Weaknesses

The lack of any empirical results is the main weakness of the paper.

We thank the reviewer for the suggestion. We would like to highlight that our empirical results are presented in Section F.

Our primary focus in this paper was on the theoretical aspects, rather than extensive experimental validation, which is why we placed the empirical section in the appendix. The experiments included are intended to demonstrate that our theoretical results closely align with practical observations, highlighting the robustness of our theoretical framework. In the camera-ready version, having an extra page, we are happy to include the highlights of experiments in the main part of the paper.

Only sparsification type compression methods are considered. What about quantization? Can the arguments be easily extended to the case with quantization?

Yes, of course, our theory already covers quantization. Our general theoretical results (Theorems D.1, D.2, E.1) rely on Definition 1.4, which encompasses a wide range of compression operators. These operators include not only sparsification, but also, for example, natural compression and natural dithering [1], general exponential dithering (a generalization of ternary quantization), general unbiased rounding, and unbiased exponential rounding [2]. Various combinations of these compression methods are also covered. Naturally, our theory also applies to quantization. More information can be found in the references in Section 1.1 of the paper.

In some theoretical results, we specialize in sparsification to highlight the superiority of permutation compressors. However, the aforementioned theorems demonstrate that our approach is applicable to a variety of other compression schemes as well (all compression techniques satisfying Definition 1.4).

We agree that we can clarify this point further in the paper and will make the necessary revisions to ensure this.

[1] Horvath, S., Ho, C. Y., Horvath, L., Sahu, A. N., Canini, M., & Richtárik, P. (2022, September). Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning (pp. 129-141). PMLR.

[2] Beznosikov, A., Horváth, S., Richtárik, P., & Safaryan, M. (2023). On biased compression for distributed learning. Journal of Machine Learning Research, 24(276), 1-50.

Questions

While the authors have covered most of the relevant literature, as far as I'm aware, one missing paper that I am aware of is the following: M. Mohammadi Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor, "Federated Learning With Quantized Global Model Updates" arXiv preprint arXiv:2006.10672, Jun 2020. Here, not only the authors consider downlink communication, but they actually transmit different updates to different clients. Instead of compressing the difference with rest to the previous global model, here the authors compress the difference with respect to the model updated by the client. This way the gap to the new global model is potentially lower. I can't say how the convergence rates compare, but I would like the authors to comment on the pros/cons of this approach compared to their own.

Thank you for pointing out this reference, we will add this work to the references. We would like to provide our comments on it.

First, the statement that they actually transmit different updates to different clients is incorrect. While it is true that the updates transmitted from the devices are different, the server sends the same message $Q(\theta(t) - \hat{\theta}(t-1), q_1)$ to all clients (line 2 of Algorithm 1).

Regarding the theoretical comparison between the proposed LFL and our MARINA-P/M3, a crucial difference lies in the underlying assumptions. Most importantly, the results of [3] rely on the strong convexity of the local loss functions, whereas MARINA-P and M3 operate in the non-convex setting. Additionally, the theory in [3] assumes the boundedness of the stochastic gradients, which is a very restrictive assumption and, in fact, contradicts the strong convexity assumption (see, e.g., [4]). Therefore, the constant $G$ in Theorem 1 can be arbitrarily large, potentially making the upper bound infinite.

We hope this clarifies the matter.

[4] Nguyen, L., Nguyen, P. H., Dijk, M., Richtárik, P., Scheinberg, K., & Takác, M. (2018, July). SGD and Hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning (pp. 3750-3758). PMLR.

How limiting is the assumption that the calls to the compressor are independent? There are some works in the literature that consider time-correlated sparsification, and show improved results (which also makes sense as the sparsity pattern should not change drastically from one iteration to the next). Please provide some comments in the paper if this may be a significant limitation on the practical performance of the considered class of compressors.

There exist various classes of compressors, each of them coming with some benefits and potentially some drawbacks. The assumption of time-independence is not a limitation. The class of compressors we consider is very wide, as a result of which the theoretical framework we developed covers a broad range of compression operators. Most importantly, the use of permutation compressors enables us to obtain superior complexity results, resulting in the first downlink compression algorithms whose complexities can provably improve with the number of workers.

We are not aware of any work with theoretical evidence that the sparsity pattern should not change drastically from one iteration to the next. We would be grateful if the reviewer could provide such references.

---

We are grateful for the feedback and believe that we have resolved the issues identified. If further information or explanations are required, please do not hesitate to ask.