Communication-Efficient Heterogeneous Federated Learning with Generalized Heavy-Ball Momentum

We thank the reviewer for the feedback. In the following, we address the reviewer’s remarks on the weaknesses (W).

• W1: In our initial analysis of the second term in Eq. (5), we drew parallels with the concept presented in [1], perceiving it as a variance reduction mechanism due to observed similarities. We appreciate the Reviewer's keen observation regarding the distinction between these two terms. This insight has led us to a more accurate interpretation and, consequently, a revision in our manuscript. We now clarify that this term in our formulation is intended to penalize the direction of the last updates at round $t - \tau_i$ ​, in contrast to the progressive update of local steps at the current round $t$. Although at the moment we cannot formally prove that this term acts as variance reduction, we investigated its importance in the ablation study section, specifically in Figure 2, where it is evident that it provides additional speedup w.r.t Local-GHB and reaches better accuracy (see fig. 3 and table 10).
• W3: Thanks for spotting the typo, we fixed it.
• W4: In the first part of section 4.3 we discuss how both FedCM and FedADC are equivalent formulations of GHB with fixed $\tau=1$ (and hence, extra communication): this is shown analytically in table 1, but also experimentally in figure 3, where the performance of GHB $\tau=1$ and FedCM are shown to be equivalent. This is the reason why we didn’t include them in the main results, as we specified in the first paragraph of section 4.1. However, since this may not be immediately obvious to the reader, we added the values of FedCM and FedADC in the main tables, as you suggested, to dispel any doubts about the completeness of our experimental validation.
• W5: The reason why we did not adopt a learning rate decay is because we considered that this would have caused unfair comparison since algorithms have very different convergence speeds. Please notice that this way of conducting the experiments is in line with most existing well-established works in FL [3,4,5,6,7]. However, to demonstrate that our findings hold even when adopting learning rate decay, we added in the supplementary an additional section showing the accuracy curves for the iid and non-iid training of CIFAR-100 with ResNet-20, with full hyperparameter search the learning rate decay and algorithm-specific hyperparameters. For ease of comparison, we also added in Table 10 the results for iid training of CIFAR-10/100 without learning rate decay.

Thanks for the feedback. About the remaining concerns:

1. We appreciated your observation, and the rebuttal version provides a different intuition about that term. The current version does not claim that the term is equal to the algorithm previously mentioned or a variance reduction term.
2. About constant learning rate: as the reviewer suggested in its initial review, we added these extra experiments in our revision (in both iid and non-iid scenarios, in appendix B.4, figure 8). As suggested and following the practice mentioned in FedDyn and FedCM, we used an exponential learning rate decay by decreasing the local learning rate by a $0.9999$ factor at each round. This value has been searched to be the optimal one among $\\{0.999, 0.9992, 0.9995, 0.9999\\}$.
   Our results are clear in proving that adopting a learning rate decay does not change the comparisons between algorithms in the setting tested ($\alpha=0$ and $\alpha=10000$) and showing that our method outperforms all the baselines.
   We remark that all the works considered in our evaluation represent the state-of-the-art methods generally used as baselines in all the Federated Learning papers.

Given the requested experiments, it is unclear to us what is missing to fully convince the reviewer that our results are valid and our method has been fairly and extensively compared against the baselines.

We thank the reviewer for the feedback. In the following, we address the reviewer’s remarks on the weaknesses (W) and questions (Q).

• W1: First, let us restate the novelty of our approach. The generalization we claim is based on the fact that, while standard momentum and its declinations in FL use the updates that occurred in the last round, we consider a larger window (GHB) across multiple rounds. While this modification results in a simple implementation, we showed that enlarging this window to a length $\tau>1$ is crucial to developing the robustness against extreme heterogeneity (see fig. 3). On top of this idea, we developed communication-efficient variants of GHB, namely Local-GHB and our proposed FedHBM, which self-control the window length according to client participation and this is optimal both in terms of window length and communication costs (see again Fig 3). As an additional point, we frame existing momentum FL algorithms inside this generalization, and show how they are special cases (see Table 1): in this sense, our work brings some order to the literature on momentum in FL, which is part of our contribution.

• W2: We acknowledge that a formal proof could strengthen our paper. However, we also argue that theoretical convergence rates may only render an incomplete picture, whereas extensive experiments may reveal more than an elaborate yet very specific proof. As a matter of fact, in our experiments, empirical evidence demonstrated that in extreme cases state-of-art algorithms, despite being supported by formal guarantees, happen to actually fail (e.g. see Table 4).
  Motivation behind a window $\tau > 1$.
  The main intuition behind our method is that the trajectory of the server updates over a window $\tau>1$ provides a better estimate for the momentum term in a federated setting. Intuitively, as $\tau$ increases, the momentum term increasingly incorporates information from a broader range of clients. A key observation is that when $\tau$ equals the average period length (e.g. $\tau = \frac{1}{C}$), under uniform client sampling, the momentum term contains the information on the global distribution and hence is optimal. We experimentally verified this hypothesis, demonstrating its validity in practice as we showed by purposely varying $\tau$ in Figure 3. We revised the manuscript to better describe these details.
  Is it always beneficial?
  Yes. According to our experiments, in FL this is always beneficial since it improves even in the iid scenario, where the simple FedAvgM is often a strong baseline. However, its effect is most noticeable in extreme non-iid scenarios where computing the momentum over a larger window mitigates the effects of heterogeneity and partial participation (see Fig. 2 and 3)..

• W3: We take reproducibility into great consideration since we provided a precise algorithmic description in Algorithm 1 and accurately reported the datasets, the split procedures, the hyperparameters, and the framework used (see section B and in particular table 7). We did not attach the code to the original submission, but following your suggestion we are attaching it now, we hope this may dispel your concerns.

• W4: Thanks for reporting to us these works we were not aware of, we will take the time to go into details and we will include them in our revision of the related works.

• Q1: The formula reported is correct, but the term C is not the total number of clients. Rather, it is the participation ratio, i.e., the portion of clients that participate in each round (i.e., $0<C\leq1$). In practice, $\frac{1}{\tau_i}$ term has the meaning of an averaging factor, and so it fits the number of contributions it averages. This is perhaps clearer by looking at the GHB row in Table 1 (right), which contains the expansion for a fixed $\tau$. Let us remark that in Local-GHB and FedHBM, $\tau_i$ is not hand-tuned, but it is instead determined stochastically by client participation: in practice, under uniform sampling, on average each client automatically considers a window of length $\tau_i \approx \frac{1}{C}$. We showed the optimality of $\tau_i$ under uniform client sampling in figure 2, which also crucially allows us to be communication-efficient, whereas hand-tuning $\tau$ requires an overhead of $1.5\times$ w.r.t. FedAvg.

We hope that our answer addresses your concerns and that you consider revising your rating of our work for an “accept” decision.

We thank the reviewer for the feedback, we are pleased to notice that the reviewer appreciated our work. In the following, we address the reviewer’s remarks on the weaknesses (W).

• W1: We acknowledge that a formal proof could strengthen our paper. Certainly, a theoretical proof of convergence is one way to support the claims of a method, but it is not the only way. Here we chose to have an empirical approach, where we test extensively FedHBM and existing methods in a wide range of tasks, extreme scenarios, and real-world cases, as we are pleased you appreciated. By doing so we provide evidence that our method consistently outperforms existing methods which are supported by articulated formal proofs [1,2]. We also argue that theoretical convergence rates may only render an incomplete picture, whereas extensive experiments may reveal more than an elaborate yet very specific proof. As a matter of fact, in our experiments, empirical evidence demonstrated that in extreme cases state-of-art algorithms, despite being supported by formal guarantees, happen to actually fail (e.g. the case of FedDyn diverging already known in the literature, and SCAFFOLD and MimeMom in our table 4).

• W2: We agree that our algorithm is actually simple to implement, and we consider it as a strength. In fact, more often than not, very complex and articulated methods require careful tuning, which may be case-specific, and are prone to introducing coding errors. On the contrary, we think that simplicity is the ultimate sophistication [Leonardo Da Vinci]. We also believe that simplicity should not be considered as an indication of a lack of novelty. To the best of our knowledge, we are the first to propose a generalization of the heavy-ball momentum computed over a period $\tau>1$, and we showed that it has a significant impact on performance in FL (figure 3). Within this framework (GHB), FedHBM allows to capture locally (i.e., on the client side) global information that encompasses more than one round, without communication overhead. We analyzed its practical advances under a wide range of scenarios, to support our claims of FedHBM being superior to the state-of-the-art FL methods. These results, as well as the practical demonstration of the failure of well-established FL algorithms in extreme non-iid cases, are themselves a novelty that adds to the knowledge base of the community, and points to new problems to be considered.

• W3: Results in Table 4 use the formulation proposed in algorithm 1, and nonetheless our method is in most cases the best, so the practical variation is not strictly necessary to achieve good performance. Our point is that, although our algorithm is primarily designed for cross-silo scenarios, it can still be used for cross-device scenarios, as the variation we proposed can help obtain a speedup earlier (see Figure 4).

• W4: Table 2 reports the number of rounds to reach a target accuracy w.r.t the accuracy of centralized training (reported in table 6), hence the lower the number the faster the algorithm. In a cross-device scenario, FedDyn reaches 90% of the accuracy reached by centralized training in 7600 rounds, which is worse than our FedHBM, which needs only 6510 rounds to reach the same result. Namely, table 2 reports the speed while Tables 3 and 4 report the final performance of the algorithms. Together, these results show that our algorithm is the most communication efficient and that it yields the best model quality.

• W5: Thank you for your suggestion, we updated the manuscript accordingly.

• Minor issues: Thanks for spotting the typos, we fixed them. On page 6, par. 4, $k$ simply stands for $\times1000$. As we understand it can generate confusion, we replaced it with $\alpha=10.000$ We hope that our answer addresses your concerns and that our revision will contribute positively to the evaluation of our work.

[1] Scaffold: Stochastic controlled averaging for federated learning, PMLR 2020
[2] Breaking the centralized barrier for cross-device federated learning, NeurIPS 2021

We thank the reviewer for the feedback, we are pleased to notice that the reviewer appreciated our work. In the following, we address the reviewer’s remarks on the weaknesses (W) and questions (Q).

• W1-W2-Q1: For clarity, let us restate the hyperparameters involved in our method. $\eta$ is the server learning rate, $\eta_l$ is the client learning rate, $\hat{\beta_i}$ is our momentum factor, defined as $\frac{\beta C}{J_i}$, where $J_i$ is the number of local steps and $C$ is the participation ratio ($0<C\leq1$). The hyperparameters to be tuned are $\eta$, $\eta_l$, and $\beta$. For each method, the hyperparameters have been searched via a grid search. As we take into great consideration reproducibility, in Table 7 we reported our extensive hyperparameter search for all the algorithms, indicating in bold the best values.

• W3-Q2: We assumed the computational cost per round to be equal for all algorithms, as usually, communication cost is the bottleneck. By doing so, we acted conservatively, as Mime, MimeMom, and MimeLiteMom actually require multiple forward and backward passes on the local dataset, and so require much more computations (we refer to [1] for additional details on their algorithm). All the other algorithms (including ours) have similar computational costs since they just require addition/subtraction to model parameters, which are not expensive. As a matter of fact, this is reflected in the wall-clock training time of our simulations, as indicated in section B.2, under the paragraph “Implementation details and practicality of experiments”.

• W3-Q4: Regarding the non-iid setting, we followed the practice in [2], which is common in FL works. In practice, it consists of drawing class probabilities for each client using a Dirichlet distribution with parameter $\alpha$. The lower the value of $\alpha$, the higher the class imbalance we introduce into local datasets. We acknowledge your suggestion, and we added some more words in the supplementary B.1 to better explain the procedure in [2].

• Q3: final model quality means the top-1 accuracy over the last 100 rounds of training, averaged over 5 independent runs. The number of rounds depends on the dataset and the model used, and it is equal to all the algorithms. For example, for the CIFAR-10 dataset and LeNet, the round budget is fixed at 10.000 rounds (for more details, see Table 8) We hope that our answer addresses your concerns and that our revision will contribute positively to the evaluation of our work. Please let us know if there are any remaining concerns and if our answers clarify your doubts.

[1] Breaking the centralized barrier for cross-device federated learning, NeurIPS 2021
[2] Federated Visual Classification with Real-World Data Distribution, ECCV 2020