Stochastic Controlled Averaging for Federated Learning with Communication Compression

Dear Reviewer 17jD:

Thanks for your valuable feedback and support.

We have cited and discussed the paper https://arxiv.org/pdf/2310.07983.pdf in the section of related works in the updated manuscript. However, since this method does not support communication compression, we do not compare our methods with it directly.

We tried our best to look for the typo you pointed out. However, we did not find the location. Could you please kindly inform us of the location where $L^2$ is missing?

Thanks again for your feedback on our work.

Dear Reviewer fdME:

Thanks for your valuable feedback. All questions have been clarified as best as we can and all the revisions in the updated manuscript are highlighted with the red color.

• Softening the claim. Thanks for the suggestion and for mentioning the related papers. We have modified the claim in our updated manuscript with the additional references by saying ``In the literature, none of the existing algorithms have successfully achieved this goal in non-convex FL, despite a few studies in the strongly convex scenarios (Grudzie ́n et al., 2023; Youn et al., 2022; Condat et al., 2023; Sadiev et al., 2022)''. We hope this addresses your question.

• Clarification for the inequality. We highly appreciate your efforts in carefully reading through the proofs. There is indeed a miscalculation here in our earlier manuscript. We have fixed it and highlighted the revision with the red color on page 25. Note that this minor miscalculation does not affect the soundness of our theories as we essentially only need $\eta_l^2 K^2L^2 \lesssim \alpha (1+\omega)/N$. The existence of numerical numbers does not affect the final convergence rate.

• Clarification for $x^{-1}=x^{0}$. We use $x^{-1}:=x^{0}$ notationally in our proofs instead of $x^1=x^{0}$. We think reviewer fdME meant to ask the clarification regarding $x^{-1}=x^{0}$. The variable $x^{-1}:=x^0$ is introduced to simplify the notations in telescoping and does not appear in our algorithmic iterations which indeed start with $t=0$. Specifically, our proof frequently uses the term $\mathbb{E}[\\|x^t-x^{t-1}\\|^2]$, which typically emerges from breaking $\mathbb{E}[\\|c_i^t-\nabla f_i(x^{t})\\|^2]$ and $\mathbb{E}[\\|c^t-\nabla f(x^{t})\\|^2]$ for $t\geq 1$ as

$\mathbb{E}[\\|c_i^t-\nabla f_i(x^{t})\\|^2]\lesssim \mathbb{E}[\\|c_i^t-\nabla f_i(x^{t-1})\\|^2]+L^2\mathbb{E}[\\|x^t-x^{t-1}\\|^2]$

and $\mathbb{E}[\\|c^t-\nabla f(x^{t})\\|^2]\lesssim \mathbb{E}[\\|c^t-\nabla f(x^{t-1})\\|^2]+L^2\mathbb{E}[\\|x^t-x^{t-1}\\|^2],$ see, e.g., Lemma 4, 5, 6. By hypothetically letting $x^{-1}=x^0$, the above inequalities hold trivially for $t=0$. We hope this notation is clear now.

Thanks again for your feedback on our work.

Dear Reviewer aALW:

Thanks for your valuable feedback on our work. All questions have been clarified as best as we can and the revisions in the updated manuscript are highlighted with the red color.

1. Comparison with MARINA

We did not compare our algorithms with MARINA in the original manuscript for a couple of reasons. (i) MARINA does not support local updates, the fundamental characteristic of federated learning algorithms. (ii) MARINA lacks the guarantee of supporting partial client participation and stochastic gradients simultaneously. Specifically, VR-MARINA supports stochastic gradients but not partial participation while PP-MARINA supports partial participation but not stochastic gradients. (iii) MARINA requires the averaged smoothness (see Assumption 3.2 therein), which is beyond the scope of our manuscript. Nevertheless, we are happy to cite the paper and add some discussions.

We have supplemented the complexities of MARINA in Table 1 in the updated manuscript. We observe that SCAFCOM outperforms MARINA in terms of computation complexity but is inferior in terms of communication complexity. Despite the comparison of theoretical rates, we again would like to emphasize that the problem setups are different, and SCALLION and SCAFCOM can be advantageous in the practical federated learning setup where local updates, stochastic gradients, and partial participation are entangled together.

2. Specifications of learning rates and scaling factors

We have specified the choices of $\eta_l$, $\eta_g$, $\alpha$, and $\beta$ in the updated manuscript (in red color).

3. No provable improvement compared to a single larger gradient step

To our knowledge, the shrinkage of the learning rate due to local updates is customary in non-convex and stochastic FL literature. The main focus of this work is to address the entanglement of local updates, stochastic gradients, partial participation, compression, and data heterogeneity that appears naturally in practical FL.

We remark that the provable benefit of local updates is a long-standing problem particularly in the stochastic and non-convex scenarios, without a bounded-similarity-type condition being imposed over $\\{f_i\\}_{i=1}^N$. While there is a stream of works demonstrating the benefit as mentioned by Reviewer fdMe in strongly convex scenarios, we are not aware of any existing work achieving this goal in the stochastic and non-convex scenarios. We thus intend to leave this ambitious goal for future work.

Please kindly let use know if there are any further questions. Thanks again for your review of our work.

We are delighted that your concerns have been resolved, and we sincerely appreciate your positive feedback. We will incorporate your suggestions to streamline the choices of parameters in our later revisions. Thank you again for your valuable input.