Locally Adaptive Federated Learning

We thank the reviewer for their evaluation of our manuscript. We did our best to understand and respond to their constructive criticisms, and provide detailed answers below:

• (W1) For convex and strongly convex functions (such as the ones in Example 1), the optimal local stepsizes can be calculated using the Polyak stepsize (PS). For the above example, we have $f_1(x) = \frac{a}{2}x^2$ and corresponding $\gamma_1^\star = \frac{\frac{a}{2}x_0^2 - 0}{\left(ax_0\right)^2} = \frac{1}{2a}$. Similarly, $f_2(x) = \frac{1}{2}x^2$ and corresponding $\gamma_2^\star = \frac{\frac{1}{2}x_0^2 - 0}{\left(x_0\right)^2} = \frac{1}{2}$. Since this analytical Example considers deterministic gradient descent (GD), we use the deterministic version of the Polyak stepsizie. For Figure 1, we consider the stochastic scenario (SGD) and hence use the SPS stepsize from Loizou et al., 2021.
• (W2) For Figure 1, SPS does converge. We had set an extremely small threshold error ($\epsilon = 10^{-6}$), beyond which we stop the algorithm. SPS achieves the desired error faster than the rest of the methods, as is obvious from Figure 1. The choice of $\sigma = 10$ to introduce stochasticity is arbitrary, and should not change the observation. Nevertheless, we would add some additional plots for different values of $\sigma$ in our potential camera-ready version, for the sake of completeness.
• (W3) $f^{\star}$ has been defined in the Introduction section at Equation (1), and refers to the global minimum of the finite sum. In the same paragraph, we also clarify that the global minimum $x^{\star}$ and the local minima $x_i^{\star}$ can be different.
• (W4) Proposition 1 makes it clear that $\sigma_f$ is a stronger assumption than ($\zeta_{\star}, \sigma_{\star}$). This is because any existing convergence rate for FedAvg using ($\zeta_{\star}, \sigma_{\star}$), will also hold for $\sigma_f$ due to Proposition 1. Moreover, it should also be obvious that uniformly bounded noise ($\zeta, \sigma$) is a stronger assumption than bounded noise at optimum ($\zeta_{\star}, \sigma_{\star}$). We would try to rephrase this comment in the more understandable way in our revised version.
• (W5) We would like to kindly draw the reviewer’s attention to the non convex experiments (Figures 4 and 5), where our proposed FedSPS in fact performs better than FedAMS.
• (W6) We do compare our method to FedADAM as claimed in our manuscript, and refer the reviewer to Figure 3(c). For the other experiments we chose to include the comparison to only FedAMS for the sake of brevity, since FedAMS [1] was already shown to empirically beat FedADAM [2]. Nonetheless, we will make sure to add the comparison to FedADAM in the remaining plots for the potential camera-ready version of our paper, to aid better understanding.
• (Q1) Please refer to the response to (W1) above.
• (Q2) Please refer to the response to (W2) above.

We believe that all the questions raised by reviewer e5wf have been satisfactorily answered in our response above. We shall take care to incorporate the clarifications and changes outlined above in the potential camera-ready version of our paper. If you feel there are no serious flaws in the theoretical claims kindly consider increasing the "Soundness" score. If you also agree that we managed to address all issues raised, please consider increasing your "Contribution" score, as well as the overall "Rating". If you believe this is not the case, please let us know so that we have a chance to respond further.

References:

• [1] Wang, Yujia, Lu Lin, and Jinghui Chen. "Communication-efficient adaptive federated learning." International Conference on Machine Learning. PMLR, 2022.
• [2] Reddi, S. J., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konecny, J., Kumar, S., and McMahan, H. B. Adaptive federated optimization. In International Conference on Learning Representations, 2021.

We thank the reviewer for their very thorough evaluation of our manuscript, positive remarks, as well as constructive criticism. We provide detailed answers to the concerns below:

• (W1) Algorithm: As explained in Remark 2, we experimented with various other algorithm design choices for incorporating SPS in FedAvg, such as FedSPS-Global and FedSPS-Normalized which are more complicated than our proposed FedSPS but did not offer any empirical benefits---hence our choice.
• (W2) Theory: The primary theoretical challenge in analysis of FedSPS was extending the error-feedback framework (that originally works for equal stepsizes) to work for fully un-coordinated local stepsizes, and we did this for the first time in our work.
• (W3) Experiments: Following are detailed answers to questions about experiments:
  • We beg to say the comment by the reviewer is a misinterpretation of what has been plotted in Figure 2(b). The plots do not show the SPS stepsize but a different statistic (SPS averaged both across clients and across the local steps). Therefore, it is possible that some client reaches the upper bound $\gamma_b$ in some local step---hence the difference in trajectories plotted in Figure 2(b).
  • The purpose of Figure 2(b) was to show that adaptivity sets in from $\gamma_b = 1$, even if it is stable. Moreover, the purpose of Figure 2(a) was to show that all values of $\gamma_b$ leads to convergence of FedSPS, while that is not the case for FedAvg. So, our method is less sensitive to $\gamma_b$ than FedAvg is to $\gamma$.
  • We are aware that in Figure 3(b), FedAMS shows a diverging behavior for non-i.i.d MNIST, but this is the plot obtained from our experiments. Note that the original paper on FedAMS [1] does not show any plot for non-i.i.d. data, and the original paper on FedADAM [2] has experiments for the EMNIST dataset and not MNIST. Nonetheless, we will verify this particular experiment regarding its correctness, for the potential camera-ready version.
  • We wished to convey that our proposed method has lesser dependence on problem dependent parameters than previous adaptive federated methods, and its sensitivity to the parameters involved is lower. We agree with the reviewer in this regard, and shall rephrase Remark 4 to clarify this in the revised version of our manuscript.
• (Q1) The term "adaptive methods" has a wide variety of connotations in the optimization literature: one of the earliest successful adaptive methods was AdaGrad, which is essentially just a stepsize. Adaptive methods can but do not necessarily have to involve gradient history and momentum. We chose our title to cater to the broader message that local adaptivity can be useful for Federated Learning.
• (Q2) Our proof is based on error feedback analysis, and we can use similar ideas from followup work [3, 4] considering partial participation to extend our convergence analysis to partial client participation setting. However, this seems non-trivial and might be a direction for future work. We shall add a brief statement regarding this, as well as the suggested reference in our potential camera-ready version.

References:

• [1] Wang, Yujia, Lu Lin, and Jinghui Chen. "Communication-efficient adaptive federated learning." International Conference on Machine Learning. PMLR, 2022.
• [2] Reddi, S. J., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konecny, J., Kumar, S., and McMahan, H. B. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
• [3] 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, 2021.
• [4] Fatkhullin, Ilyas, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294, 2021.

We believe that all the questions raised by reviewer vVZ6 have been satisfactorily answered in our response above. Overall, we should bear in mind to separately understand theoretical contributions and experimental insights. Many issues raised by the reviewer were quite interesting and thoughtful, and served to increase the standard of our manuscript, or can form the basis for interesting future work. We shall make sure to incorporate the clarifications and changes outlined above in the potential camera-ready version of our paper. If you agree that we managed to address all issues raised, please consider increasing your "Contribution" score, as well as the overall "Rating". If you believe this is not the case, please let us know so that we have a chance to respond further.

We thank the reviewer for their evaluation of our manuscript, and provide detailed answers to the concerns below:

• (W1) As explained in Remark 2, we experimented with various other algorithm design choices for incorporating SPS in FedAvg, such as FedSPS-Global and FedSPS-Normalized which are more complicated than our proposed FedSPS but did not offer any empirical benefits---hence our choice. Moreover, the primary theoretical challenge in analysis of FedSPS was extending the error-feedback framework (that originally works for equal stepsizes) to work for fully un-coordinated local stepsizes, and we did this for the first time in our work.
• (W2) It is indeed true that the notion of optimal objective difference $\sigma_f^2$ is a weaker notion of heterogeneity than the standard ones in Federated Learning (FL). However, one can note that such a quantity appears naturally in the analysis of SPS-type methods, and the purpose of our Proposition 1 was to show that $\sigma_f^2$ is comparable to the standard heterogeneity assumptions in FL.
• (W3) The existing algorithms for client-side adaptivity, such as Local-AdaAlter and Local-AMSGrad perform some form of aggregation of stepsizes during the communication round. Therefore, for these algorithms all the clients use the same stepsize for a particular round, and these methods are not fully locally adaptive as ours. Nonetheless, we agree with the reviewer that an empirical comparison with these methods would add value to the paper, and will include them in our potential camera-ready version.

We believe that all the questions raised by reviewer g1co have been satisfactorily answered in our response above. We shall take care to incorporate the clarifications and changes outlined above in the potential camera-ready version of our paper. If you agree that we managed to address all issues raised, please consider increasing your "Contribution" score, as well as the overall "Rating''. If you believe this is not the case, please let us know so that we have a chance to respond further.