FedSMU: Communication-Efficient and Generalization-Enhanced Federated Learning through Symbolic Model Updates

Question 2: FedLion seems to provide the relevant convergence rate for the Lion optimizer, even under weaker assumptions.

Response:

Please note that FedLion cannot be reduced to a standard Lion optimizer, because it merely parallelizes the execution of the Lion optimizer on the client side and incorporates multi-precision quantization for communication compression. Therefore, even when $K=1$ and $m=1$, it does not degrade to a standard Lion optimizer, and its convergence rate cannot be directly applied to the Lion optimizer.

In contrast, when $K=1$ and $m=1$ in our algorithm, it degenerates to the standard Lion optimizer, and its convergence rate can be applied to the Lion optimizer.

Question 3: The large model used a $30\%$ participation rate, whereas the other experiments used $10\%$ and $3\%$. Could you clarify why these inconsistent settings were used?

Response:

Please refer to the our response to Comment 3.

Question 4: The last sentence of Section 5.2.1 may not be accurate.

Response:

We will clarify this in the revised manuscript, as follows.

The results indicate that FedSMU demonstrates a strong performance on ResNet18 for both the CIFAR-10 and CIFAR-100 datasets, outperforming most baseline methods, though its accuracy remains slightly below Scaffold on the CIFAR-10 dataset.

Question 5: Could the authors include plots of SCAFFOLD in Figure 2?

Response:

Thanks for the suggestion and we will incorporate this in the revised manuscript.

Question 6: Which model was used in Section 5.2.2?

Response:

We used the small CNN network in Section 5.2.2, and we introduced its specific settings in Appendix A of the original manuscript.

Question 7: Why was FedAvg chosen in Section 5.2.3 for benchmarking on data heterogeneity? Would SCAFFOLD not have been a more appropriate comparison?

Response:

We have incorporated the experimental results of SCAFFOLD into Table 5 and show it in Table D3 here. The results continue to demonstrate that FedSMU is less impacted by the degree of data heterogeneity and achieves a high accuracy on the CIFAR-100 data set.

Table D3: Performance comparison under different datasets

Question 8: Could you elaborate on why FedSMU works well with low participation rates?

Response:

We would like to attribute this to the use of symbolic operations for client updates, which effectively leverages each client's update even at very low participation rates. Specifically, when the client participation rate is low, data heterogeneity may cause the update of certain clients to dominate due to larger magnitudes. Symbolic operations can mitigate this by normalizing the update amplitudes, ensuring that the contributions of all clients are fully considered.

Question 9: Could you explain these results? Are they possibly related to Lion optimizer?

Response:

We speculate that the primary reason lies in the symbolic operation of model updates in the Lion optimizer, as detailed in our response to Q8. These symbolic operations mitigate the impact of data heterogeneity by normalizing update amplitudes, ensuring that all clients' contributions are fully considered. Whether other structures of the Lion optimizer also play a significant role in mitigating the influence of data heterogeneity remains an open question and an interesting direction for future research.

Question 10: There are duplicate references for Chen et al. 2024a,b.

Response:

Thanks for your correction, and we will delete the duplicate reference in the revised manuscript.

Question 11: Typo: ``smay till'' should be corrected.

Response

Thank you for your correction, and we will correct it to "may still'' in the revised manuscript.

Question 12: In Algorithm 4, the client initialization of $e_0^i$ does not seem necessary. Instead, $M_t$ should be initialized.

Response:

Thank you for your correction, and we will correct it to initialize $M_{1}=0$ on the server side.

Question 13: In Algorithm 5, the client initialization of $m_0^i$ does not seem necessary. Instead, $M_t$ should be initialized. The superscript $i$ in $M_{t-1}^i$,$M_t^i$,$G_t^i$,$U_t^i$ may be typos.

Response:

Thank you for your correction, and we will correct it to initialize $M_{0}=0$ on the server side. The superscript $i$ in $M_{t-1}^i$,$M_t^i$,$G_t^i$,$U_t^i$ are indeed typos and we will delete it in the revised manuscript.

Comment 3: The experimental results are difficult to compare across different settings.

Response:

In most federated learning scenarios, the total number of clients is set to 100 with the participation rate of 0.1, which is a classical experimental setting, like what FedLion and FedAvg do. Therefore, with the simple CNN network, we set 100 clients with participation rates of 0.1 and 0.03 to verify the performance of our algorithm.

However, our computing resources (i.e., GEFORCE GTX 1080 Ti) are insufficient to support us to set 100 clients on the ResNet18 network, we thus can only select 10 clients and set the participation rate to 0.3.

To illustrate the relationship between model dimension and convergence rate, we have conducted additional experiments, as detailed in our response to Comment 2.

Comment 4: The definition of generalization and its corresponding performance metric are not clearly defined.

Response:

We appreciate this comment and will further clarify the definition of generalization in the revised manuscript. Specifically, generalization refers to an algorithm's ability to achieve top test accuracy, where the test dataset is different from the training dataset.

Furthermore, we consider an additional perspective on generalization to further evaluate the performance of our FedSMU algorithm. Here, generalization refers to a model's ability to achieve test performance at similar training error levels. Based on this definition, we compare the validation performance at similar training accuracy levels. The results in Table D2 show that on the CIFAR-10 and CIFAR-100 datasets, the FedSMU algorithm achieves the highest test accuracy and demonstrates the best generalization performance.

Table D2: Generalization performance comparison under various datasets. Each table entry gives the average test accuracy on different training accuracy levels. "/" means it cannot reach the training accuracy. Bold numbers indicate the best performance.

Comment 5: Fed-LocalLion and Fed-GlobalLion algorithms do not seem to provide meaningful insights into the proposed method.

Response:

Please note that we implemented these two variant algorithms in the ablation studies, and compared them with FedSMU to verify our motivation. Specifically, the symbolization of local client updates, which is introduced to balance the contribution of each client and prevent dominance by relatively large update values, significantly improves the overall generalization performance. Therefore, we designed Fed-LocalLion and Fed-GlobalLion to execute the Lion optimizer on the client and server sides, respectively. In these setups, the uploaded model updates maintain full precision rather than using the symbolization.

The comparison results, as shown in Figure 3, clearly illustrate that FedSMU outperforms both Fed-LocalLion and Fed-GlobalLion. This highlights that the improvement stems not solely from a direct application of the Lion optimizer in the federated settings, but also from the deliberately designed symbolization of all the client updates.

Question 1: What is the definition of generalization performance?

Response:

Please refer to our response to Comment 4.

We would like to thank the reviewer for the comments. In the following, we have provided our detailed responses to each of these comments.

Comment 1: The Assumption 4.3 is weak or even irrelevant to the context of sign-based methods.

Response:

We would like to acknowledge that this is a stronger assumption, ensuring that both the compressed targets and the momentum term (the moving averages of gradients) in our theoretical analysis are bounded. Moreover, this assumption has been adopted in other federated optimization and sign-based compression studies [D1, D2]. Specifically, in [D1], the authors demonstrate the convergence of distributed SIGNSGD with momentum under Assumption 4, which is also the bounded gradient assumption.

In contrast, while FedLion does not rely on this stronger assumption, it also introduces an additional stronger assumption (A.4 in the original manuscript of FedLion):

``There exists a constant $\alpha\leq\frac{1}{3}$, such that $\left\|\nabla f(x)-\nabla f_i(x)\right\|_1 \leq \alpha\|\nabla f(x)\|_1, \forall i, x .$''

And we will clarify these points in the revised manuscript.

[D1] Tao Sun, Qingsong Wang, Dongsheng Li, and Bao Wang. ``Momentum ensures convergence of signsgd under weaker assumptions.'' In International Conference on Machine Learning, pp. 33077–33099. PMLR, 2023.

[D2] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and H Brendan McMahan. ``Adaptive federated optimization.'' arXiv preprint arXiv:2003.00295 , 2020.

Comment 2: The theoretical and experimental results seem disconnected.

Response:

Thank you very much for your suggestion. We have done further analysis on the influence of model dimension and client participation rate on convergence speed in this reponse. This theoretical relationship is consistent with the conclusion made in other papers [D3].

Theoretically, a lower client participation rate (i.e., a larger $\tau_{max}$) leads to a slower algorithm convergence. Similarly, a higher model dimension $d$ also results in a slower algorithm convergence. To validate this, we have conducted the following experiments.

All of these experiments are done on CIFAR-10 dataset with Dirichlet-0.25. To illustrate the relationship between the model dimension and convergence rate, we use two different CNN models ($d1=797248$ and $d2=1723648$) to study the impact of model dimension. Note that here we modify the size of the convolutional layers, keeping the model depth constant. The number of clients is 100 with the participation ratio of 0.1. To illustrate the relationship between participation rate and convergence rate, We use the CNN network with $d1=797248$ and set the number of clients as 100 with different participation ratio ($\frac{n}{m}=0.03$ and $\frac{n}{m}=0.1$, represented in the table by L and H) to demonstrate the influence of client participation rate.

The experimental results in Table D1 show that when the participation rate is higher (i.e., the $\tau_{max}$ is smaller) and the dimension is smaller, the convergence speed can be faster, which matches with the Theory 4.4 and is intuitional.

[D3] McMahan, Brendan, et al. ``Communication-efficient learning of deep networks from decentralized data.'' In Artificial intelligence and statistics. PMLR, 2017.

Table D1: Number of communication rounds to achieve test accuracy. Each table entry gives the number of communication rounds necessary to achieve the test accuracy. d1 and d2 indicate small and large dimensions, while L and H indicate low and high participation rates. Bold numbers indicate the smallest rounds.

Comment 4: Given that Lion is an adaptive optimization strategy, it is important to discuss and compare it with other adaptive optimization methods, particularly those focused on communication efficiency.

Response:

Thank you for this suggestion. We have compared with the two adaptive algorithms as presented in the suggested literature [C1]: the optimization-based FedAMS and the compression-based FedCAMS. FedAMS is designed to accelerate the convergence using momentum, while FedCAMS extends FedAMS by further compressing the upload communication. Due to time limitation, our experiments are conducted only on CIFAR-10 and CIFAR-100 datasets. We use a total of 100 clients with a partial participation ratio of 0.1 and employ a Dirichlet distribution with a concentration parameter of 0.25. The experimental results are presented in the Table C2.

The experimental results demonstrate that on the CIFAR-10 dataset, FedSMU also outperforms FedCAMS but is slightly inferior to FedAMS, while FedSMU exhibits a superior performance compared to FedAMS and FedCAMS on the CIFAR-100 dataset. The results strongly demonstrate the superiority of FedSMU in complex image classification tasks, even comparable to the uncompressed federated adaptive algorithm, which may result from promoting the fair contribution of clients effectively to the global model update.

[C1] Wang, Yujia, Lu Lin, and Jinghui Chen. ``Communication-efficient adaptive federated learning.'' In International Conference on Machine Learning. PMLR, 2022.

Table C2: Performance comparison under different datasets. Bold numbers indicate the best performance.

Question 1: Authors assume $|\gamma_2 x_t^j\leq 1|$. This is an uncommon assumption in FL optimization (or even in general optimization). Could you provide more details or clarification regarding this assumption?

Response:

Though this is indeed a less common assumption, it has been demonstrated in literature [C2] (Equation 5 on Page 3). Literature [C2] clarifies in Abstract that ``Lion is a theoretically novel and principled approach for minimizing a general loss function f(x) while enforcing a bound constraint $||x||_{\infty}\leq \frac{1}{\gamma_2}$.'' Here $\gamma_2$ is the weight decay coefficient and $x_t$ is the model. Such an assumption has also been used in another algorithm based on Lion optimizer [C3] (Equation 7 on Page 4).

[C2] Chen, Lizhang, et al. "Lion secretly solves constrained optimization: As lyapunov predicts.'' ICLR, 2024.

[C3] Liu, Bo, et al. "Communication Efficient Distributed Training with Distributed Lion.'' arXiv preprint arXiv:2404.00438 (2024).

Question 2: Some formatting could be improved: for instance, the scaling of Figure 1, the presentation of $min$ in equation 1, and the $min$ and $max$ in Theorem 4.4.

Response:

Thank you for pointing these formatting issues. We will modify them in the revised manuscript, including adjusting the scaling of Figure 1, and correcting the presentation of $\min$ and $\max$.

Question 3: It would be helpful to specify the model (e.g., CNN or ResNet) in the captions or when describing figures/tables.

Response:

We appreciate this suggestion, and will specify the model used for each figure and table in the revised manuscript. Specifically, For Table 3, we use the ResNet18 network. In the rest of the tables and figures, we use the simple CNN network (i.e., Letnet).

We would like to thank the reviewer for the comments. In the following, we have provided our detailed responses to each of these comments.

Comment 1: In Section 3, the statement, “when the number of local update steps is set to $K=1$, the entire federated learning process reduces to the standard Lion algorithm,” is somewhat misleading.

Response:

We would like to thank the reviewer for pointing out this issue. A more precise expression would be: “when the number of local update steps and the number of clients are set to $K=1$ and $m=1$, respectively, the entire federated learning process reduces to the standard Lion algorithm.” This will be corrected in the revised manuscript.

Comment 2: Remark 4.5 is somewhat confusing.

Response:

First, we would like to acknowledge that for the general quantization-based compression algorithms, a higher precision quantization may often lead to a faster convergence. However, this may not hold for our FedSMU. This conclusion is based on the Lion optimizer and our previous analysis, as follows.

1) The original Lion manuscript demonstrated that 1-bit quantization (via the sign operation) in centralized learning enhances the algorithm's convergence and generalization compared to other optimization techniques. That is, the authors analyzed that the sign operation introduces noise into the updates, which serves as a form of regularization, thereby improving both convergence and generalization.

2) We also observe that in the federated learning setting, symbolizing client model updates (i.e., normalizing the magnitude of each model parameter at local clients) mitigates the model heterogeneity arising from data heterogeneity. This, in turn, enhances the overall performance of the globally aggregated model at the server.

Consequently, we conclude that in our optimized structure, 1-bit quantization outperforms higher-bit or even full-bit quantization, since multi-bit compression does not guarantee that the update amplitude of each client is consistent. Experimental results in Table C1 further validate that for our designed optimization algorithm, using a higher-bit compression does not enhance the algorithm's convergence or generalization.

Table C1: Number of communication rounds to achieve test accuracy. Each table entry gives the number of rounds of communication necessary to achieve the test accuracy. Bold numbers indicate the smallest rounds.

Comment 3: It is unclear to me why $\tau_{max}$ is used as an indicator for studying partial participation settings.

Response:

Please note that $\tau_{max}$ represents the maximum participation interval among all clients across the communication rounds. While it is true that $\mathbb{E}(\tau_{max})=\frac{m}{n}$ for scenarios with uniformly random participation and constant participation rates per round, we would like to consider a more general scenario here. In cases of non-uniform random participation or varying participation rates across rounds, $\mathbb{E}(\tau_{max})$ may not equal to $\frac{m}{n}$. Therefore, it is more appropriate to use $\tau_{max}$ in this context.

Question 3: Can you include compression for server-to-client communication as well? A comparison to some baselines can be helpful.

Response:

Thanks for this comment. Due to the partial participation characteristic of federated learning, the server must broadcast the new global model, rather than a simple global model update, to initialize newly participating clients. This limitation prevents the direct application of uploaded model update compression techniques in our FedSMU to the downloaded global model.

Following this advice, we will consider some model lightweight techniques, such as mixed-precision model compression, as a promising future research direction to compress the server-to-client communication in our FedSMU algorithm.

Question 4: Can the convergence bound improve with more number of local steps and more participation per round?

Response:

In the theoretical analysis of FedSMU, $\tau_{max}$ and $K$ control the client participation rate and the number of local updates, respectively. The convergence rate in Theorem 4.4 demonstrates that increasing the client participation rate and reducing the number of local updates can tighten the convergence bound.

It is intuitive that a increased participation rate can improve the model's convergence rate. A higher client participation ratio helps the global model gather more information from the clients, which reduces the overfitting and mitigates the impact of local data heterogeneity, thereby improving the convergence bound. This conclusion is also supported by Table 1 in reference [A2].

On the other hand, in the convergence upper bound of Theorem 4.4, the term $4K\sigma_l^2 + 4KG^2$ indicates that more local updates amplify both the local sampling variance $\sigma_l$ and the gradients accumulation $G$, resulting in a slower convergence. This aligns with our intuition. For the SGD-based local updates, as the number of local updates increases, the cumulative sampling variance $\sigma_l$ and gradients $G$ grows, also further leading to more divergent update directions caused by data heterogeneity. This negative effect is also experimentally demonstrated in Page 7 of literature [A2], where Figure 3 strongly states that ``for very large numbers of local epochs, FedAvg can plateau or diverge.''

[A2] McMahan, Brendan, et al. "Communication-efficient learning of deep networks from decentralized data.'' In Artificial intelligence and statistics. PMLR, 2017.

Question 5: Can this method improve over SCAFFOLD in CIFAR-10 and Shakespeare with more communication (more rounds or other variant like FedSMUMC)?

Response:

We sincerely appreciate the reviewer for this suggestion. On CIFAR-10 dataset, the performance of FedSMU can slightly improve with more communication rounds, while SCAFFOLD's performance has been converged already.

Here, specifically, we reconduct the experiment by increasing the number of rounds to 6000 and comparing FedSMUCS with SCAFFOLD on CIFAR-10 dataset, using a total of 100 clients with a partial participation ratio of 0.03 (represented in the Table A8 by L).

The experimental results are shown in the Table A8. It can be found that on the CIFAR-10 dataset with Dir (0.6)-L, FedSMU achieves a slightly higher accuracy compared SCAFFOLD when the number of communication rounds reaches 6000. We also find that when FedSMUMC is used at additional overhead of storing and communicating the momentum, it can perform better than SCAFFOLD over the same 4000 rounds.

However, it shoud be noted that there is a tradeoff between the training time and test accuracy. A larger number of communication rounds leads to a slight performance improvement. For example, with FedSMU on CIFAR-10 with Dir (0.6)-L, an accuracy of 81.96% is achieved after 4000 rounds in the original manuscript, and an improvement of 0.52% is obtained with 2000 more rounds (6000 rounds in total), which exceeds that of SCAFFOLD. Therefore, we currently set 4000 rounds as the maximum communication round for all the algorithms considering the training efficiency. We will incorporate this discussion into the revised manuscript.

Table A8: Performance comparison under different datasets

Comment 4: Experiments that explicitly measure generalization (e.g., by comparing validation performance at similar training error levels) are needed to substantiate this claim further.

Response:

Thank you for this comment. We will further evaluate the performance of our algorithm in terms of generalization mentioned. Based on this definition, we compare validation performance at similar training accuracy levels.

Due to time limitations, we conduct comparisons under the following settings: CIFAR-10 and CIFAR-100 datasets: 100 users, 0.1 participation rate, and Dirichlet = 0.25.

The experimental results are shown in the Table A5. The results show that on the CIFAR-10 and CIFAR-100 datasets, FedSMU achieves the highest test accuracy and demonstrates the best generalization performance.

Table A5: Generalization performance comparison under various datasets. "/" means it cannot reach the training accuracy. Bold numbers indicate the best performance.

Question 1: Can you plot the accuracy vs MU for different methods, checkpoints and dataset to better show the correlation between them?

Response:

Thank you for the suggestions. We will include the plots in the revised manuscript. Meanwhile, here, we provide Table A6 and Table A7 showing the correlation between Magnitude Uniformity (MU), data heterogeneity, and accuracy. The results indicate that with FedAvg, data heterogeneity significantly amplifies the differences in the magnitude of model updates across clients, leading to unstable global aggregation and poorer generalization performance. While SCAFFOLD reduces variance to address these differences, FedSMU directly ensures consistency across all model updates through symbolic operations. Those two approaches enhance Magnitude Uniformity among clients, ultimately improving accuracy.

Table A6: Accuracy (%) vs. data heterogeneity.

Table A7: MU vs. data heterogeneity

Question 2: How does your model compare to other methods in terms of wall-clock time?

Response:

We have tested the wall-clock time needed for each baseline to execute one communication round. Take CIFAR-100 and participation rate $\frac{n}{m}=0.1$ as an example, the average wall-clock time required to execute a round is as follows: FedSMU (10.43 seconds), FedAvg (10.15 seconds), FedEF-HS (10.46 seconds), FedLion (10.63 seconds), SCAFFOLD (10.38 seconds). Experiments demonstrate that in a single communication round, our algorithm introduces no significantly additional time overhead compared to other algorithms. As highlighted in the response to Comment 3, FedSMU does not require more communication rounds, ensuring no increase in overall training time compared to other algorithms.

Comment 2: Given the comparison with SCAFFOLD on CIFAR-10 and Shakespeare datasets, benchmarking on additional datasets and model architectures could strengthen the paper’s results.

Response:

Thanks for your suggestion, and we have compared our FedSMU with SCAFFOLD on new MNIST dataset. Additionaly, we also conducted another performance comparison scenario ($Dir = 0.6$) on CIFAR-100 using ResNet-18. The experimental results in Table A3 show that FedSMU outperforms SCAFFOLD on CIFAR-100. However, for the simpler MNIST dataset, FedSMU performs slightly worse than SCAFFOLD. This slight degradation on MNIST is likely due to the lower degree of heterogeneity in the dataset.

In a federated heterogeneous scenario with CIFAR-100, which consists of 100 categories compared to MNIST's 10 categories, each client typically handles a subset of 13-16 or 20-25 categories when $Dir = 0.25$ or $Dir = 0.6$, respectively. This high degree of heterogeneity in CIFAR-100 leads to greater deviations in model updates among clients, enabling FedSMU to achieve more significant improvements compared to MNIST. To further assess performance, we plan to explore a more complex dataset, Tiny ImageNet, for additional comparisons in future work.

Table A3: Performance comparison under different datasets. L and H indicate low and high participation rates. Bold numbers indicate the best performance.

Comment 3: Additional experiments comparing methods based on both communication cost and the number of rounds would provide clearer insights into practical efficiency.

Response:

Thank you for the suggestion. We will include other algorithms in the figures depicting convergence performance vs. the number of communication bits. Additionally, we will provide new figures depicting convergence performance vs. the number of communication rounds in the Appendix.

Here since we cannot show the figures directly, we compare the convergence rate using the number of communication rounds required to achieve the target accuracy. The results are presented in the Table A4. For CIFAR-100 and Shakespeare, our algorithm does not require more communication rounds compared to most algorithms. However, for CIFAR-10, it slightly exceeds the number of rounds needed by other algorithms. This may be attributed to the simplicity of the CIFAR-10 dataset, which has a lower degree of heterogeneity. In this case, our algorithm's strengths are not fully utilized, as the initial training process is already close to convergence.

Table A4: Number of communication rounds to achieve a preset target accuracy. "/" means it cannot reach the training accuracy.

We would like to thank the reviewer for the comments. In the following, we have provided our detailed responses to each of these comments.

Major Comment: Missing related work: FedSMU is really similar to the Distributed Lion Training.

Response:

Thank you for this comment. We will refer to the "Distributed Lion Training'' paper as [A1] in this response and the revised manuscript, and clarify the differences and advantages of our FedSMU compared to the D-Lion in [A1], as follows.

1) Motivation. Our FedSMU can simultaneously mitigate data heterogeneity and reduce communication compression through the symbolic operations. The analysis was carried out and verified by experiments (Figure 1). While D-Lion only consider to compress the communication.

2) Scope of application. Our FedSMU can deal with scenarios involving the partial client participation and multiple local updates, whereas D-Lion can not. Performing multiple local updates, in the federated settings, can effectively reduce the communication frequency and thus the overall traffic. Experimental results in Table A1 further demonstrate that D-Lion fails in such scenarios with low client participation rates and multiple local updates, whereas FedSMU remains robust and performs well under these conditions.

Table A1: Performance comparison under different datasets. F and P indicate full and partial participation rates, and K is the number of local updates. Bold numbers indicate the best performance.

3) Algorithms design. While both algorithms are based on the Lion optimizer, FedSMU fully leverages the structural advantages of the Lion optimizer, including weight decay in the global aggregation. In contrast, D-Lion primarily incorporates the momentum sliding averaging and symbolic operations at local update. Notably, when the number of local updates and clients is set to 1, our algorithm reduces to the standard Lion optimizer, whereas D-Lion does not. This comprehensive utilization of the Lion optimizer structure may explain why the experimental performance of our FedSMU surpasses that of D-Lion.

4) Compatibility with majority vote. We have further extended FedSMU with majority vote, as FedSMU-MV. Experimental results in Table A2 show that FedSMU-MV achieves an accuracy of 47.66% on CIFAR-100, slightly lower than FedSMU's 51.79% under the same settings (number of clients = 100, fraction = 0.1, Dirichlet = 0.25). This indicates that majority vote is compatible with our algorithm. The slight accuracy drop may result from FedSMU's symbolic model updates. Applying majority vote to the 1-bit results could further suppress some clients' model update information due to the dominant update direction.

Table A2: Performance comparison on CIFAR-100. Bold numbers indicate the best performance.

[A1] Liu, Bo, et al. "Communication Efficient Distributed Training with Distributed Lion.'' arXiv preprint arXiv:2404.00438 (2024).

Comment 1: FedSMU algorithm requires clients to maintain and track their momentum state, which may introduce practical limitations in scenarios with dynamic participation.

Response:

Our FedSMU algorithm requires each client to maintain and track its momentum state. In some extreme cases, where each client participates in the training only once during the entire training process, our algorithm may fail. And we will include this limitation in the revised manuscript.

In fact, in the original manuscript, we did analyze this limitation from two perspectives. First, we tested our algorithm at a lower client participation rate (i.e., where the momentum state of the clients is more stale). The results in Table 4 show that FedSMU still achieves a good accuracy in most cases. Additionally, we introduce a variant algorithm, FedSMUC, which additionally store and communicate the complete momentum at the server at the cost of communication overhead. The results in Table 6 demonstrate that appropriately completing the momentum can marginally improve the model performance. Overall, the experimental results indicate that, in most cases, our FedSMU algorithm remains effective and does not fail due to the stale momentum.

With these two modifications, we then present the additional experimental results in Table AA1 and Table AA2, with the following observations. Notably, since we have also fully tuned our FedSMU algorithm, we observe a slight improvement in its performance compared to the results in Table AA1 in our initial response.

• With full participation and one local update (i.e., $K=1$ with F), FedSMU performs slightly worse than D-Lion. However, in scenarios with a partial participation, FedSMU consistently outperforms D-Lion. This is intuitive, as D-Lion does not maintain a complete global model at the server and only aggregates the global model updates. Thus in the partial participation settings, asynchronous clients can only save a stale global model. As a result, these clients may receive the global model updates, which, however, cannot be leveraged to recover the exact global model of the current round.

• With multiple local updates (i.e., $K>1$), FedSMU consistently outperforms D-Lion. This performance improvement can be attributed to the different approaches to weight decay. Specifically, the hyperparameter $\gamma_2$ (denoted as $\lambda$ in D-Lion) controls the weight decay (or $L_2$ penalty) coefficient. In FedSMU, the regularization is applied to the global model $x_t$, potentially mitigating overfitting and thus enhancing generalization. In contrast, D-Lion applies this regularization to the local model $x_{t-1}^i$. As a result, when the local updates occur multiple times, D-Lion's regularization primarily affects the local model, and does not directly improve the generalization capability of the global model. Consequently, when finally evaluating the generalization performance of the global model, FedSMU demonstrates a significant advantage over D-Lion.

• In heterogeneous scenarios, the performance of both FedSMU and D-Lion is poorer than that of FedAvg, especially when $k$ is small. This is an interesting and somewhat unexpected finding, which we speculate is due to the data heterogeneity. In the heterogeneous settings, each client samples a mini-batch of data for training and performs only a single time of update, followed by the application of the sign operation to the model update. Since the local update occurs only once, it introduces a substantial sampling variance and inter-client variance. The sign operation, which normalizes the magnitude of updates, may inadvertently amplify this variance between clients, leading to an unstable or even divergent global model aggregation.

Finally, we would like to extend our heartfelt gratitude once again to the reviewer for the time, effort, and meticulous attention to detail in reviewing our paper. We kindly invite the reviewer to read our response, and look forward to further possible communication on the remaining issues.

Dear Reviewer 8rqU,

Thanks for your reply and concern on the further comparison with D-Lion.

Here, we would like to first make a correction to an ambiguity term that we might have incurred in our initial ``Response to Major Comment''. Specifically, instead of representing the expected meaning of number of local updates, the notation $K$ in Table A1 refers actually to the number of epoch updates in our experimental setup, where one epoch corresponds to a complete pass through the dataset. For example, if a client has 5000 samples and the minibatch size is set to 50, then it requires 100 updates within one epoch, and thus the actual $K$ in Table A1 should in fact correspond to 100 local updates. In this response, we have corrected this ambiguity term, and re-implemented the experiments accordingly to show a detailed comparison between our FedSMU and D-Lion.

On the other hand, in our initial response, we only took the default hyperparameter settings from the original manuscript [A1] for evaluating D-Lion due to the time constraint. In this response, we have further conducted an extensive grid search and fully tuned the hyperparameters of D-Lion. Below, we provide the details of the hyperparameters used in our experiments.

• To ensure a fair comparison, both algorithms are evaluated on the ClFAR-10 dataset (we will also provide the CIFAR-100 results before the response deadline)`, using non-llD and IID data, with a total of 10 clients anda batch size of 50.

• For FedSMU and FedAvg, we adopt the same parameter settings as outlined in Appendix A.

• For D-Lion, we performed a grid search. The learning rate ($\epsilon$) is selected from {0.00005, 0.0005, 0.005, 0.015}, the weight decay ($\lambda$) is chosen from {0.0005, 0.005, 0.001, 0.01}, and $\beta_1$, $\beta_2$ are selected from {0.9, 0.99}. For Table AA1, the selected values are $\epsilon=0.015$, $\lambda=0.01$, $\beta_1=0.9$, $\beta_2=0.9$. For Table AA2, the selected values are $\epsilon=0.0005$, $\lambda=0.001$, $\beta_1=0.9$, $\beta_2=0.99$.

Table AA1 (Corrections to Table A1 in our initial response): Performance comparison on CIFAR-10 dataset, where F and P indicate full and partial participation rates, and K is the number of local updates.

Table AA2: Performance comparison on CIFAR-10 dataset, where F and P indicate full and partial participation rates, and K is the number of local updates.

Question 3: Line 309: The three standard assumptions stated in the analysis are weak and not universally applicable to a range of non-convex objective functions.

Response:

Please note that Assumption 4.1 is a standard assumption in the convergence analysis of optimization algorithms. Similar assumptions can be found in MARINA ("Assumption 1.1'') and EF21 ("Assumption 1'').

For Assumption 4.2, it is fundamental for SGD-based optimization algorithms. In SGD, model updates are computed using mini-batch sampling rather than full-batch, under the assumption that the sampling process is unbiased and accounts for the variance introduced. However, MARINA bypasses this assumption by employing the Gradient Descent (GD) instead of Stochastic Gradient Descent (SGD), eliminating the variance caused by mini-batch sampling. EF21 discuss this stochastic gradient explicitly in Section ``F: Dealing with Stochastic Gradients (Details for Section 3.6)''.

For Assumption 4.3, we acknowledge that this is a stronger assumption, ensuring that both the compressed targets and the momentum term (the moving averages of gradients) in our theoretical analysis are bounded. Moreover, this assumption has been adopted in other federated optimization and sign-based compression studies [B7,B8]. Specifically, in [B7], the authors demonstrate the convergence of distributed SIGNSGD with momentum under Assumption 4, which is also the bounded gradient assumption.

Regarding the author's mention of $y = \frac{x^2}{2}$ over $\mathbb{R}$, it is true that the gradient does not have an upper bound for the domain $\mathbb{R}$. However, in neural networks, the input domain is typically bounded, ensuring the gradient is also bounded. For instance, gradient clipping is a commonly used technique to control the gradient's upper bound and prevent gradient explosion.

We will clarify these points in the revised manuscript.

[B7] Tao Sun, Qingsong Wang, Dongsheng Li, and Bao Wang. "Momentum ensures convergence of signsgd under weaker assumptions.'' In International Conference on Machine Learning, pp. 33077–33099. PMLR, 2023.

[B8] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and H Brendan McMahan. "Adaptive federated optimization.'' arXiv preprint arXiv:2003.00295, 2020.

Question 4: Theorem 4.4: While your rates in terms of $L_1$ norm square are inversely proportional to $\frac{1}{T}$ you have a dependency of $d^2$ , which becomes problematic. Please elaborate more on the dependency on dimension.

Response:

The convergence rate in terms of $L_1$ norm with a dependency of $d$ is common in sign-based method, like Theorem 4 in literature[B7], p.6, Theorem 1 in literature [B9], P.6, and Equation 35 in literature [B10], P.19. Their form of expression is similar to Theory 4.4. However, it is worth noting that the value of the learning rate $\gamma_1$ may be critical. In literature [B9] and [B10], the authors use $\gamma_1=\frac{1}{\sqrt{Td}}$ to reduce the power of $d$. In that way, if we take $\gamma_1=\frac{1}{L\sqrt{Td}}$, Theorem 4.4 can only depend on $\sqrt{d}$.

[B9] Chen, Xiangyi, et al. "Distributed training with heterogeneous data: Bridging median-and mean-based algorithms." In Advances in Neural Information Processing Systems 33 (2020): 21616-21626.

[B10] Jin, Richeng, et al. "Stochastic-sign SGD for federated learning with theoretical guarantees." arXiv preprint arXiv:2002.10940 (2020).

Question 5: To my knowledge, the state-of-the-art method for Top-K compression is Error Feedback 2021, not FedEF-TopK.

Response:

Thanks for this suggestion, and we have additionally conducted a comparison with the original EF21 algorithm. Due to the limited time, only experiments on CIFAR-10 and CIFAR-100 are conducted. We set a total of 100 clients with different participation rate (0.03% and 0.1%, represented in Table B1 by L and H) and use Dirichlet-0.25. The experimental results are shown in Table B1.

On CIFAR-100, FedSMU still shows a high performance. While on CIFAR-10, the accuracy of FedSMU can be higher than EF21 with a lower participation. These results strongly demonstrate the superiority of FedSMU in complex image classification tasks, especially under a low client participation rate, which may result from the sign operation promoting the fair contribution of clients effectively to the global model update.

Table B1: Performance comparison under different datasets. L and H indicate low and high participation rates. Bold numbers indicate the best performance.

Comments 7: I suggest that authors elaborate a bit on why ``sign'' information 1-bit can be useful for practice or imagine scenarios when it can be useful for society. 1 bit can not be transferred physically, only 1 byte (approximately). Even with transferring 1 byte you will need to transfer 54 bytes of headers.

Response:

We would like to clarify that the "sign operation'' refers to 1 bit per dimension, not a total of 1 bit for the entire model. In practice, the weights or gradients of each dimension in a model are typically stored as 32-bit floating-point values (float32). This means that each dimension requires 32 bits to upload. However, when applying the sign operation, each dimension only requires 1 bit to represent the sign, thus significantly reducing the communication overhead compared to using 32 bits per dimension.

In terms of the physical data transfer, the actual number of bits transmitted to the server can be calculated as: $\text{Total bits transferred} = (\text{bits per dimension} \times \text{the number of dimensions} \times \text{the number of participating clients})$ + the header size. For example, using a CNN model with $n = 10$ clients, FedSMU would transfer approximately 0.95MB. Given the large volume of transmitted data, the header size of 54 bytes is negligible in comparison.

Question 1: I can not find "Supplementary Material'' and I can not find "Link for code".

Response:

We provided an Appendix to the main text and thus have no additional supplementary material, and the code for evaluating our FedSMU has been provided in the following anonymous link https://anonymous.4open.science/r/fedsmu-400D.

Question 2: Line 102: The statement ``While biased compression with a certain degree of information loss may cause a slight decrease in model performance'' is incorrect.

Response:

Thanks for this comment, and we will make the following clarification in the revised manuscript.

A direct application of biased compression on gradient into federated learning, such as Top-k, can lead to a performance degradation and lower convergence speed due to bias accumulation [B2]. To address this, some studies have introduced optimization techniques to mitigate the negative effects of bias. For example, EF21 [B3] employs the error feedback, while MARINA[B5] and DIANA[B6] leverage the compression of gradient differences, both of which further enhance the model performance and convergence speed.

[B5] Gorbunov, Eduard, et al. "MARINA: Faster non-convex distributed learning with compression.'' In International Conference on Machine Learning. PMLR, 2021.

[B6] Mishchenko, Konstantin, et al. "Distributed learning with compressed gradient differences.'' In Optimization Methods and Software (2024): 1-16.

We would like to thank the reviewer for the comments. In the following, we have provided our detailed responses to each of these comments.

Comment 1: Line 60: The statement ``However, most of these algorithms will lose a certain amount of information due to compression, resulting in a decrease in accuracy'' needs clarification.

Response:

Thanks for this comment. We will clarify these points in the revised manuscript, as follows:

However, the direct use of compression methods will lose a certain amount of information, resulting in the problem of decrease in the accuracy [B1] and slower convergence or even divergence [B2]. On the other hand, some methods like Error Feedback [B3] have designed to solve these problems.

[B1] Yu, Enda, et al. "CP-SGD: Distributed stochastic gradient descent with compression and periodic compensation.'' In Journal of Parallel and Distributed Computing 169 (2022): 42-57.

[B2] Beznosikov, Aleksandr, et al. "On biased compression for distributed learning.'' In Journal of Machine Learning Research 24.276 (2023): 1-50.

[B3] Richtárik, Peter, Igor Sokolov, and Ilyas Fatkhullin. "EF21: A new, simpler, theoretically better, and practically faster error feedback.'' In Advances in Neural Information Processing Systems 34 (2021): 4384-4396.

Comment 2: Line 64: The phrase "mitigate the client variance'' lacks clarity.

Response:

Please note that the variance here refers to the variance between the uploaded client updates. Building on the SAGA algorithm in centralized learning, SCAFFOLD reduces the variance between the uploaded client updates (the sum of gradients) by employing control variates. As highlighted in the Abstract of the original SCAFFOLD manuscript: "As a solution, we propose a new algorithm (SCAFFOLD) which uses control variates (variance reduction) to correct for the ‘client-drift’ in its local updates." Furthermore, as mentioned in the Appendix of the original manuscript, "Our method can be viewed as seeking to remove the ‘client-variance’ in the gradients across the clients."

Comment 3: Line 68: The claim "Additionally, it remains unknown whether these optimization-based algorithms are compatible with the current compression techniques" is misleading.

Response:

Please note that integrating federated optimization techniques with federated compression algorithms poses significant challenges in achieving good convergence rates while simultaneously reducing communication overhead. For instance, SCALLION [B4] introduces variance-reduced optimization techniques to achieve a faster convergence and reduced upload communication. However, this comes at the cost of doubling the download communication overhead due to the transmission of control variables.

[B4] Huang, Xinmeng, Ping Li, and Xiaoyun Li. "Stochastic controlled averaging for federated learning with communication compression." arXiv preprint arXiv:2308.08165 (2023).

Comment 4: Line 85: The term "Lion optimizer'' is not properly referenced in the Introduction section.

Response:

Thanks for pointing out this out issue, and we will include the appropriate reference for the Lion optimizer in the revised manuscript.

Comment 5: Line 300: The statement lacks clarity regarding the necessity of momentum terms on the server side of Algorithm 1.

Response:

We would like to clarify that our FedSMU (Algorithm 1) does not need to store the momentum terms on the server side, and only tracks the momentum state on the client side. As a result, FedSMU only requires uploading the 1-bit model update after symbolization for each client. In contrast, FedLion requires to aggregate and store momentum on the server side. Consequently, FedLion necessitates the additional transmission of the full-precision momentum terms, along with the model update after quantization.

Comment 6: Can momentum terms be stored on the client side instead?

Response:

Please note that in our FedSMU algorithm, each client needs to maintain and track its momentum state, but does not upload it to the server. While these momentum states may become somewhat stale due to partial participation, their impact on the performance is minimal and acceptable, as demonstrated in Table 3 of the original manuscript.

I appreciate the authors' thorough rebuttal and commend them for addressing the majority of my concerns. I encourage them to revise the paper accordingly and integrate the new discussions into the camera-ready version. All your comments I believe is important to include in the extra discussion section in the Appendix for clarity. Thanks for your hard work.