Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.

Reply to Methods And Evaluation Criteria:

1. Thank you for your comment. Our work advances asynchronous federated learning (AFL) in the following key ways:

• Eliminating Data Heterogeneity Bounds in the Asynchronous Regime: While server-client momentum has been explored in some prior AFL works, all existing approaches rely on data dissimilarity bounds to address non-iid data. In this work, we introduce a novel two-level momentum technique, making our approach the first to eliminate the need for such heterogeneity bounds in AFL. Although variance reduction technique has been explored in methods such as SCAFFOLD, they operate in synchronous frameworks, thus their analyses are inherently simpler compared to our asynchronous approach.
• Tuning-Free AFL Approach: This paper also makes another significant contribution by introducing a completely tuning-free AFL approach, greatly simplifying algorithm deployment. As shown in Fig. 2, our method demonstrates exceptional robustness across varying levels of asynchrony. Based on the reviewer's suggestion, we have also included comparisons under different data heterogeneity levels and local training lengths ($K$). The results confirm that our method remains robust across diverse scenarios.

These contributions go beyond combining existing techniques and addressing key challenges in AFL.

2. We agree with the reviewer that AdaMasFL requires the communication of an additional variable, $\Delta$, as the cost of achieving a tuning-free AFL. To address this communication overhead, information compression techniques can be incorporated as a potential solution. We acknowledge this as an important future work.

Reply to Theoretical Claims:

1. Thanks for the comment. Using a $T$-dependent learning rate is standard in non-convex optimization to achieve theoretical guarantees. This predefined $T$ is reasonable since in real-world deployments, FL systems typically run for a pre-determined number of rounds due to resource constraints and practical considerations. The design also ensures momentum diminishes as $T$ increases, avoiding excessive staleness accumulation in asynchronous updates.

2. We sincerely thank the reviewer for pointing this out. We have removed the reference to the FedAvg algorithm in line 271.

Reply to Experimental Designs Or Analyses:

1. Thanks for the comment. We have included sensitivity experiments with different local training lengths ($K$) as shown in https://github.com/anonymouslinkforrebuttal/for4415/blob/main/4-1-k.pdf, and data heterogeneity levels as shown in https://github.com/anonymouslinkforrebuttal/for4415/blob/main/4-1-noniid.pdf. Additionally, an ablation study on the impact of varying delay durations has already been presented in Fig. 2 of our main paper. Detailed information about the asynchronous setting can be found in our response to "Weakness 2" of reviewer JC6K. The results demonstrate the robustness of our approaches across various hyperparameter settings.

2. Thanks for your suggestion. We have included an ablation study analyzing the benefits of normalization, momentum, and control variate in our algorithms, shown as https://github.com/anonymouslinkforrebuttal/for4415/blob/main/4-2-ablation.pdf.

3. Thanks for the comment. We have included performance comparisons under different values of $\beta$ and compared with the momentum-based method FADAS as in https://github.com/anonymouslinkforrebuttal/for4415/blob/main/4-3-beta.pdf.

4. Thanks for the comment. We have added a table to report the wall-clock time of all baseline methods (in seconds) achieving a certain accuracy (CIFAR-10: 80%, FMNIST: 75%). Regarding information compression, as it goes beyond the scope of this work and we assume perfect communication in our paper, we leave this as an important direction for future research. |Dataset |Heterogeneity|CA$^2$FL|FADAS|MasFL|AdaMasFL| |-|-|-|-|-|-| |CIFAR-10|iid|3485|4171|2033|2323| ||non-iid|12593|9372|6679|5333| |FMNIST|iid|1975|1238|832|394| ||non-iid|2311|1943|1067|514|

Reply to Questions For Authors:

1. Thanks for pointing this out! $\sigma_h$ should be $\sigma_g$ defined in eq. (1), which characterizes the level of data heterogeneity.
2. For a predetermined $T$, $\beta = \sqrt{SK/T}$ is a constant in our methods. As this momentum coefficient $\beta$ balances historical and fresh updates, it plays a crucial role in mitigating staleness in AFL. A larger $T$ results in a smaller $\beta$, ensuring stability and convergence by reducing the influence of stale updates. This design enables linear speedup by effectively balancing momentum and new gradient updates, ensuring strong theoretical guarantees and scalability.

Thank you once again for your thoughtful review and constructive feedback.

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.

Reply to Methods And Evaluation Criteria:

1. The asynchronicity of our method is reflected in the following two aspects:

• Server-Side Asynchronicity: In Line 4 of Algorithm 1, the server maintains a buffer to store the latest updates from each client. When a client $i$ is selected for global aggregation ($i\in\mathcal{S}_t$), the server updates its control variate using the buffered (outdated) update rather than waiting for the client’s most recent update. This ensures the server does not rely on synchronized updates, enabling asynchronous behavior.
• Client-Side Asynchronicity: On the client side (Algorithm 2), each client performs local updates continuously and uploads its results after $K$ iterations, then immediately begins the next update. Clients operate independently, and the global round index corresponds to the round when the client finishes its update, including a delay ($\tau_i^t$). This delay is reflected in the momentum term ($g^{t-\tau_i^t}$), capturing the asynchronicity.

Semi-Asynchronous Behavior: Although the server aggregates update from the selected set of clients ($i\in\mathcal{S}_t$), these updates are generated at different times due to the clients’ independent schedules, distinguishing our approach from fully synchronous methods. Such an asynchronous mechanism is adopted in almost all existing AFL work to our knowledge, such as CA2FL and FADAS.

2. (1) The unbiasedness property does not hold in our two-level momentum. However, we achieve state-of-the-art convergence for our algorithm by carefully controlling the bias throughout the iterations. (2) The unbiasedness holds for the participating client set $\mathcal{S}_t$ because we sample clients randomly and uniformly at each round.

3. We agree with the reviewer that our method requires extra memory to maintain the control variate $c$ (with the same dimensions as the learning model) on both the server and client sides. This memory overhead is inherent to all SCAFFOLD-based algorithms, including ours.

Reply to Theoretical Claims:

1. The differences in the left-hand sides of Theorem 3.1 and Theorem 4.1 arise from the distinct proof techniques used in each case:

• Theorem 3.1: This theorem adopts the widely used squared gradient norm metric, i.e., $||\nabla f(\theta^t)||^2$, which is standard in analyzing convergence rates for optimization algorithms.
• Theorem 4.1: To achieve problem-parameter-free convergence guarantees, we employ a novel proof technique that directly analyzes the gradient norm, i.e., $||\nabla f(\theta^t)||$. This direct analysis is essential for establishing problem-parameter-free results and requires a different approach compared to Theorem 3.1.

2. We agree with the reviewer that Theorem 3.1 suggests a sufficiently large $T$ such that $T \geq \Omega(\tau_{\max}^2)$. However, we would like to emphasize that imposing a lower bound on the number of iterations is a common practice in the literature. For example, the convergence bound of asynchronous SGD [1, Corollary 4] is established under a similar condition, $T \geq \Omega(\tau_{\max}^2)$. For AFL methods such as CA$^2$FL and FADAS, their asymptotic convergence rates of $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)$ are achieved when $T \geq \Omega(\tau_{\max}^2\tau_{\text{avg}}^2)$. Most importantly, we highlight that, unlike CA$^2$FL and FADAS, the unique contribution of Theorem 3.1 is that it does not impose any restrictions on data heterogeneity.

[1] Lian, Xiangru, et al. "Asynchronous parallel stochastic gradient for nonconvex optimization." NIPS 2015.

Reply to Experimental Designs Or Analyses:

1. Our implementation simulates practical asynchronous conditions using FedBuff's delay mechanism to account for varying client arrival times. Specifically:

• At any given time, there are $M_c$ clients perform local updates concurrently;

• Each client's execution time is sampled from a uniform distribution;

• These varying execution times naturally create different delays in global aggregation participation;

• Global aggregation occurs simultaneously with local updates.

  This design captures the realistic scenario of heterogeneous client completion times and asynchronous aggregation.

2. $M_c$ represents the number of clients performing local updates concurrently throughout the algorithm's runtime. Since the overall client participation rate remains fixed, a greater $M_c$ leads to larger system delays, and vice versa.

3. Thank you for this suggestion. An ablation study on the performance of our methods and all baselines under different asynchronous levels has already been presented in Fig. 2 of our original paper.

Thank you once again for your thoughtful review and constructive feedback.

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.

Reply to Essential References Not Discussed: We sincerely thank the reviewer for bringing this conference to our attention. We have added a detailed comparison of our work with [a] in the revised manuscript, as cited below.

In the synchronous setting, [a] showed that momentum helps remove data heterogeneity bounds (i.e., bound gradient dissimilarity) for nonconvex FL, marking a first in the literature.

However, integrating momentum into AFL introduces substantial challenges due to fundamental conflicts between momentum's historical gradient accumulation and the asynchronous nature of updates. In asynchronous settings, clients' delayed updates compromise the accuracy of momentum calculations, as stale gradients introduce biases into the optimization trajectory, as shown in [1]. To address this, we propose a two-level momentum mechanism: the server updates based on the latest global momentum, while each client performs local updates using an outdated global momentum. This inconsistency, while necessary to control bias, presents significant challenges in the theoretical analysis of our approach.

[1] Yu, T., Song, C., Wang, J., and Chitnis, M. Momentum approximation in asynchronous private federated learning. arXiv preprint arXiv:2402.09247, 2024.

Reply to Weekness 1: Thank you for pointing this out. We agree with the reviewer that different learning rates can influence the performance of our algorithm. However, we would like to clarify that the optimal learning rates for our algorithm can be directly calculated based solely on system-defined constants: the number of participating clients ($S$), local update iterations ($K$), and communication rounds ($T$). These are configuration parameters that are predetermined by the system administrator, rather than problem-specific factors that require estimation or tuning.

That said, we acknowledge the reviewer's suggestion to adopt a more tempered statement. In response, we have revised the manuscript to replace "tuning-free AFL approach" with "problem-parameter-free" or "simplify the algorithm tuning process" throughout, which we believe better reflects the practical implications of our work.

Reply to Weekness 2: Thank you for this important observation. We apologize for any confusion caused by not including the detailed experimental setup in the main paper. Due to space constraints, we placed the complete asynchronous implementation details in the supplementary material (page 29).

We would like to clarify that our implementation does simulate practical asynchronous conditions using FedBuff's delay mechanism, which accounts for varying client arrival times rather than assuming fixed delay rounds. Specifically:

• At any given time, there are a total of $M_c$ clients perform local updates concurrently;
• Each client's execution time is sampled from a uniform distribution;
• These varying execution times naturally create different delays in global aggregation participation;
• Global aggregation occurs simultaneously with local updates.

This design aligns with the virtual clock setting proposed in [b] to captures the realistic scenario of heterogeneous client completion times and asynchronous aggregation.

We appreciate this feedback and will incorporate these important implementation details into the main paper for better clarity.

Reply to Weekness 3: Thanks for pointing this out. The reference [a] has been properly cited in the revised manuscript, please refer to our response under "Reply to Essential References Not Discussed."

Thank you once again for your thoughtful review and constructive feedback.

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments.

Response to Comments Or Suggestions:

Thanks for the suggestion. We have already discussed the reference Yu et al. (2024) in the Related Work section of our original manuscript (see Line 95), as cited below:

Yu et al. (2024) identified that asynchrony introduces implicit bias in momentum updates and proposed momentum approximation for AFL, which optimally weights historical model updates to approximate synchronous momentum behavior.

In response to the reviewer's suggestion, we will include experimental comparisons of our work with [1] in the revised version.

Thank you once again for your thoughtful review and constructive feedback.