Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Authors: Wenjing Yan
Xiangyu Zhong
Xiaolu Wang
Ying-Jun Angela Zhang
Venue: ICML 2025 poster (2025)
Keywords: asynchronous federated learning
arbitrary data heterogeneity
tuning-free
parameter-free
momentum
gradient normalization
Primary area: optimization

Abstract: Asynchronous federated learning (AFL) has emerged as a promising solution to address system heterogeneity and improve the training efficiency of federated learning. However, existing AFL methods face two critical limitations: 1) they rely on strong assumptions about bounded data heterogeneity across clients, and 2) they require meticulous tuning of learning rates based on unknown system parameters. In this paper, we tackle these challenges by leveraging momentum-based optimization and adaptive learning strategies. We first propose MasFL, a novel momentum-driven AFL framework that successfully eliminates the need for data heterogeneity bounds by effectively utilizing historical descent directions across clients and iterations. By mitigating the staleness accumulation caused by asynchronous updates, we prove that MasFL achieves state-of- the-art convergence rates with linear speedup in both the number of participating clients and local updates. Building on this foundation, we further introduce AdaMasFL, an adaptive variant that incorporates gradient normalization into local updates. Remarkably, this integration removes all dependencies on problem-specific parameters, yielding a fully tuning-free AFL approach while retaining theoretical guarantees. Extensive experiments demonstrate that AdaMasFL consistently outperforms state-of-the-art AFL methods in run- time efficiency and exhibits exceptional robustness across diverse learning rate configurations and system conditions.

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated
Learning
Wenjing Yan
Xiangyu Zhong'
Xiaolu Wang?
Ying-Jun Angela Zhang'
Abstract
1. Introduction
Recent years have witnessed an explosive growth in edge computing and mobile applications, leading massive amounts of data being generated on distributed devices. Federated learning (FL) has emerged as transformative paradigm that enables model training across these decentral- ized data sources while preserving privacy and addressing data sovereignty concerns (McMahan et al., 2017; Kairouz et al., 2021; Li al., 2020). By keeping data locally and sharing only model updates, FL has become increasingly crucial in numerous applications, from mobile services to smart cities (Abreha et al., 2022; Pandya et al., 2023).
Asynchronous federated learning (AFL) has emerged as a promising solution to address sys- tem heterogeneity and improve the training effi- ciency of federated learning. However, existing AFL methods face two critical limitations: they rely strong assumptions about bounded data heterogeneity across clients, and 2) they require meticulous tuning of learning rates based on un- known system parameters. In this paper, we tackle these challenges by leveraging momentum- -based optimization and adaptive learning strategies. We first propose MasFL, novel momentum-driven AFL framework that successfully eliminates the need for data heterogeneity bounds by effec- tively utilizing historical descent directions across clients and iterations. By mitigating the staleness accumulation caused by asynchronous updates, we prove that MasFL achieves state-of-the-ar convergence rates with linear speedup in both the number of participating clients and local up- dates. Building on this foundation, we further introduce AdaMasFL, an adaptive variant that incorporates gradient normalization into local up- dates. Remarkably, this integration removes all de- pendencies on poobemm-peeiffe parameters, yield- ing fully problem-parameter--ee parameter-free AFL approach while retaining theoretical guarantees. Extensive experiments demonstrate that AdaMasFL consis- tently outperforms state-of-the thr AFI. methods in runtime efficiency and exhibits exceptional ro- bustness across diverse learning rate configura- tions and system conditions.
However, the practical deployment of FL faces significant challenges due to system heterogeneity among participat- ing clients. Devices vary substantially in their computing capabilities, network conditions, and availability patterns (Assran et al., 2020; Zhong et al., 2022). Traditional syn- chronous FL protocols, such as the well-known FedAvg (McMahan et al., 2017; Karimireddy et al., 2020b). which re- quire all clients to complete their updates before proceeding to the next round, suffer from the "straggler effect" where the system's progress bottlenecked by the slowest par- ticipants. This synchronization barrier severely impacts training efficiency and system scalability.
Asynchronous federated learning (AFL) has emerged as promising solution to address the system heterogeneity chal- lenge by allowing clients to communicate with the server independently other participants (Xie et al., 2019; Chen et al., 2020; Zakerinia et al., 2022: Nguyen et al., 2022; Wang et al., 2023; Fraboni et al., 2023; Wang al., 2024c;a; Leconte al., 2024a:b). Despite its effectiveness in miti- gating the straggler effect, existing AFL approaches face two critical challenges: 1) Data Heterogeneity: In AFL, faster clients contribute updates more frequently than slower ones, resulting in a biased global model dominated by the data distributions of those faster clients. This bias is exac- erbated by local training. where clients perform multiple updates before communicating with the server, leading to the phenomenon of "client drift" (Karimireddy et al., 2020b). To address this issue, existing AFI. methods often rely on strong assumptions of bounded data heterogeneity, restrict- ing their applicability real-world scenarios with highly
'Department of Information Engineering, The Chinese Uni- versity of Hong Kong. Hong Kong SAR: "Software Engineering Institule, East China Normal University. China. Correspondence to: Xiangyu Zhong <xyzhong@e we.cuhk..du..bbss Xiaolu Wang <xiaoluwang& sci.ecnu.cdu.cm>.
Proceedings of the 4 International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Momentum-Drivee -rriie Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
diverse and arbitrary client distributions. 2) Algorithm Tun- ing: The theoretical convergence of AFL. algorithms relies heavily on the correct selection of hyperparamettess such as learning rates. However, in existing AFL approaches, these hyperparameters are often functions of multiple un- known parameters, including problem-speciffe constants (e.g., smoothness constants), algorithmic variables (e.g., initial suboptimality gap, gradient variance bounds), and system-dependent factors (e.g., client staleness). Since these parameters are typically unavailable a priori, tuning learn- ing rates becomes highly challenging task. Furthermore, the problem-specific learning rate configurations limit the adaptability of these approaches to diverse and dynamic AFL environments.
parameters, eliminating the need for tedious hyperparam- eter tuning.
We conduct comprehensive empirical evaluations on deep learning tasks using real-world datasets. The numerical results demonstrate that our approaches consistently out- perform state-of-the-art AFL algorithms in runtime effi- ciency, even when their hyperparameters are well-tuned. This improvement can be attributed to the acceleration provided by our two-level momentum mechanism and the per-step adaptation of our effective stepsizes. No- tably, AdaMasFL exhibits exceptional robustness across a wide range of learning rates and asynchrony levels, maintaining nearly consistent performance despite vary- ing degrees of delays. In contrast, the performance of state-of-the-arr baselines deteriorates significantly under the same conditions.
In light of the key challenges associated with AFL, it is erucial to address the following questions:
(i) Can we design an AFI. algorithm that removes the re- strictive bounded heterogeneity assumption while preserv- ing theoretical convergence guarantees?
1.2. Related Work
(ii) Building upon such a framework, can we further elimi- nate the need for manual hyperparameter tuning by intro- ducing adaptive mechanisms that automatically adjust to diverse system characteristics and data distributions?
Our approaches extend the buffered asynchronous aggre- gation mechanism introduced by FedBuff (Nguyen et al., 2022) to enhance training efficiency and mitigate the adverse effects of outdated gradients. To address the "client drift" problem caused by data heterogeneity in FedBuff, Wang et al. (2023) proposed CA3FL, which maintains cached up- dates for each client to calibrate global aggregation. These cached updates function similarly to the control variates in our methods. However, CA2 still relies on the bounded data heterogeneity assumption to ensure convergence. To accommodate arbitrary heterogeneous data in asynchronous learning, a recent study (Wang et al., 2024b) proposed DuDe-ASGD, which reuses the most recent gradients from all clients in each round of global aggregation. While ef- fective, DuDe-ASGD does not account for multiple local updates. In contrast, our MasFL. framework eliminates the need for data heterogeneity bounds while achieving the best- known communication efficiency, demonstrating an efficient utilization of distributed resources.
These questions form the foundation of our systematic effort to develop more robust and practical AFL methods.
1.1. Main Contributions
In this paper, we provide affirmative answers to the above two questions by exploring the effects of momentum-based optimization and adaptive learning strategies. Our main contributions are summarized as follows:
We develop two novel training approaches for AFL: MasFL and AdaMasFL. MasFL. incorporates two- level (both client- and server-side) momentum into the AFL framework to mitigate client drift and accelerate convergence, effectively addressing the challenges posed by data heterogeneity. Building on this, AdaMasFL fur- ther integrates local gradient normalization with local momentum, enabling automatic adaptation to diverse sys- tem characteristies and data distributions without manual hyperparameter tuning.
Yu al. (2024) identified that asynchrony introduces im- plicit bias in momentum updates and proposed momentum approximation for AFL, which optimally weights histori- cal model updates to approximate synchronous momentum behavior. FedAC (Zang et al., 2024) addresses both model staleness and client drift through adaptive server updates and corrective client training. Although these works demon- strate empirical improvements. their algorithms lack theoret- ical convergence guarantees. FADAS (Wang et al., 2024c) introduces a global adaptive AFL framework by applying adaptive optimization techniques at the server-side aggre- gation while supporting asynchronous client updates. How- ever, FADAS relies on stringent assumptions on bounded data heterogeneity and bounded gradient norms. Moreover, it still requires careful hyperparameter tuning. In contrast,
We establish strong theoretical guarantees for both al- gorithms, achieving state-of-the-art convergence rates with linear speedup with respect to the number of par- ticipating clients and local updates per round. Notably, MasFL eliminates the restrictive bounded data hetero- geneity assumption commonly required in existing AFL approaches, making it applicable to scenarios with arbi- trarily heterogeneous data distributions. Beyond this the- oretical advancement, AdaMasFL achieves convergence without relying on any unknown system or algorithmic
2

---

Nomentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
our method AdaMasFL. integrates adaptive stepsizes with two-level momentum, eliminating these constraints while maintaining theoretical convergence guarantees without problem-speciff hyperparameter tuning. Recent progress in parameter-free FI. algorithms has been marked by the development of PAdaMFed (Yan et al., 2025), a pioneer- ing algorithm that eliminates the need for manual tuning of moblem-speeiffe parameters. While PAdaMFed represents significant breakthrough, it is designed for the synchronous setting and cannot be directly extended to address the AFL problem studied in this work. A comprehensive literature review is presented in Appendix A.
In this paper, we aim address these challenges by lever- aging momentum-based optimization and adaptive learning strategies. Our theoretical analysis relies only on the follow- ing assumptions,
Assumption 2.1 (L-Smoothness), For any i the local loss function fi is L-smooth that
.N),
V (0) f (0') < L| 0'Il, 00, 0' Rd.
Assumption 2.2 (Stochastic Gradient). The stochastic gra- dients are unbiased estimators with bounded variance o², such that
2. Problem Setup
RE VV (0: V.((0). E RE VF (0: - V.((0)) so², V..
Consider distributed learning system consisting of N clients (edge devices) jointly optimizing model param- eterized by 0 E Thd under the coordination of central server. Each client i maintains a local dataset character- ized by a distribution D; from which samples &, are drawn. The local objective at client is defined as the expected loss: fi( == EED,D, [F (0: E.)]. The global optimization problem is formulated as:
Assumption 2.3 (Bounded Delay). Let Tf represent the delay of client i at the tth global round. Specifically, of is defined as the time interval between the current global round and the global round when client i began its local updates. We assume that the maximum update delay is bounded, i.e.,
Tmax = max,, of < 0C. Correspondingly, the average delay is also bounded, i.e., = NT Σ., of < 20.
N
min f(0) =
Σ 7()),
3. Momentum-Drivee AFL
BERd
3.1. Algorithm Design
where each client's raw data remains localized, inherently preserving data privacy.
Momentum techniques have demonstrated remarkable effec- tiveness in mitigating data heterogeneity and accelerating convergence in synchronous FL. In the synchronous set- ting, (Cheng et al., 2024) showed that momentum helps remove data heterogeneity bounds (i.e., bound gradient dis- similarity) for nonconvex FL,, marking a first in the liter- ature. However, integrating momentum into AFL poses significant challenges due to fundamental conflicts between momentum's 's historical gradient accumulation and the in- herent staleness of asynchronous updates. In asynchronous settings, clients' delayed updates compromise the integrity of momentum calculations, as stale gradients introduce bi- ases into the optimization trajectory, demonstrated in Yu al. (2024). This issue is further exacerbated by the heterogeneity of client data distributions, where the global model may become biased toward the data distributions of faster clients. Moreover, asynchronous updates disrupt the maintenance of a coherent global momentum across all clients, making it challenging to accurately capture the true collective optimization trajectory of the distributed system.
In rorldworld federated learning (FL) environments, clients' data distributions often exhibit significant heterogeneity (De Dj for i * j) due to factors such as diverse user be- haviors, geographical disparities, and device-specific char- acteristics. This heterogeneity manifests across multiple dimensions, including feature distributions, label spaces, and variations in local dataset sizes and qualities, leading to substantially different optimization landscapes across clients. Conventional approaches handle this heterogeneity by imposing the following gradient dissimilarity bounds:
VAOI) < BIVS +
(1)
However, such bounded heterogeneity assumptions are of- ten restrictive and fail to capture real-world scenarios. In practice, client gradient norms can vary significantly, and the degree of heterogeneity may fluctuate unpredictably dur-
ing training. Moreover, existing nonconvex FL methods rely on precise knowledge of system parameters (e.g., L, o², B, a²) for stepsize tuning. Accurate estimation of these param- eters, especially smoothness constants and heterogeneity bounds, requires global data access a process that contra- dicts the fundamental privacy principles of FL and becomes increasingly intractable as data distributions evolve.
To unlock the potential of momentum in asynchronous envi- ronments, we propose Morvenum-driven asynchronous Federated Learning (MasFL) framework, which effectively harnesses the benefits of momentum while systematically managing staleness accumulation. The complete server- side and client-side procedures of MasFl. are presented in
3

---

Momentum-Driven Adaptivity: Towards Juning-Free Asynchronous Federated Learning
Algorithm 1 MasFL: Procedures at Central Server
Algorithm 2 MasFL. Procedures Client
1: Require: Initial model 0º, control variates cf = K Ek=o -K-IVA VF ,, for any i, c. E. momentum gd = c., global learning rate 7, local learn- ing rate 7), and momentum parameter 3
1: Receive O and Bet + +11 -3)gg- of from server.
Set 0:000 0'
2: for l = 0,... K do
3: Compute
2: for = 0.... TT- do
g, - V 0 (2. + -1-
3: Randomly selected set of clients S.
4: Update
Update local model 0 0.:²t -ngg
++1
C
i St otherwise
5: end for
6: Send -
2 VF (0t c to the server
5: Aggregate momentum
chances of client participation. In contrast, our scheme maximally leverages clients' parallel computing capabil- ities while maintaining the uniformity of client selection. When M, = N and the uniform arrival assumption holds, both schemes achieve equivalent effects. Nevertheless, we emphasize that our asynchronous algorithm design is com- patible with both buffer schemes.
g 1+ = 3
(c
+++ cc) + +cd + (11-93 B)g
S iES,
6: Update global model 0*+1 0¹ -
7:
Aggregate control variate
d+1
c+1 = c'
1 N
Σ
(c ++1 -c))
Stale Control Variates. MasFL adopts a local control vari- ate cf to track the gradient information of each client i. At each round f. if client i is selected for global aggregation, c is updated using its latest buffered value C, wise, it retains its previous value. The global control variate, c'+1 is computed as the aggregation of all local control vari- ates (Line 7, A Algorithm 1), ensuring ci+1 = N Σ cf+1 throughout the algorithm iteration. The difference between global and local variates, cf c' (Line 5, Algorithm 1), serves as a correction term to mitigate "client drift" caused by data heterogeneity. This design extends the control vari- ate mechanism introduced in SCAFFOLD (Karimireddy et al., 2020b), but it is specifically adapted for asynchronous settings. On the client side, this correction term becomes टi - c' where the global control variate c' is out- dated due to system asynchrony. This inconsistency between the client- and server-side quantities introduces additional challenges in our theoretical analysis.
VESi
8: Send 0++1 and 31 + - B)ggtt
+1 to all clients
2++1 Other-
9: end for
Algorithms I and 2, respectively. To address system asyn- chrony and data heterogeneity, MasFL introduces several key innovations, described as follows.
Asynchronous Local Training. Unlike synchronous FL where the system waits for all participating clients to com- plete their local updates before proceeding to the next round, MasFL allows the server and clients operate asynchronously, with the server maintaining a buffer for each client to store their latest updates. At each global round I,, the server ran- domly selects a subset of clients, S,, to participate in global model aggregation. The aggregation uses the buffered up- dates, ensuring that it is independent of the current progress of the selected clients. Simultaneously, all clients performs local updates at their own pace. Upon completing K local iterations, clients send their updates, 2!-1, to the server and immediately begin the next round of local updates based on the latest global model. This design naturally accommodates variations in client computational speeds and communica- tion delays while maintaining overall learning efficiency.
Tee-Level Momentum. MasFL employs both global and local momentum to effectively handle asynchronous up- dates: i) Global Momentum (Line 5, Algorithm 1). The server maintains a momentum g which aggregates client updates with a parameter (3. This term stabilizes the global optimization trajectory by incorporating historical informa- tion. The difference in control variates, e/ ct, captures the progress of each client i. Since the participating clients at each round are selected uniformly, for any t, we have
Our asynchronous training is inspired by the FedBuff scheme proposed in (Nguyen et al., 2022), where the server randomly selects an active client set of size M, to perform local updates simultaneously and accumulates the fastest 5 clients for the global model update. This scheme assumes uniform arrivals of gradient computation to ensure equal
Es,
(++ cf)+
+
1
c
c 1+1
N
iES.
Thus, g" +1 represents a weighted average of the global
4

---

Nomentum-Driven Adaptivity: Towards Tuning-Free Free Asynchronous Federated Learning
Algorithm 3 AdaMasFL: Procedures Central Server
Algorithm 4 AdaMasFL.: Procedures at Client i
1: Require: Initial model 0º, control variates cf K Ek=o -ERIVP VF E, for any i, c. E. momentum gd = <.,, global learning rate 7, local learn- ing rate 7), and momentum parameter 3.
Receive O and Bct + (1 3)g² o from server.
Set 0:000 0'-
2: for l = 0, 0, K do
3: Compute
2: for = 0.... TT- do
g, = 3 0 15 - +c - +(1-3)9'
3: Randomly selected set of clients S.
4: Update
Update local model
++
C
i St otherwise
(3)
0 =
g
t.k
1.k
g
5: Aggregate local updates g' Eies, A
end for
6: Update global model 0++1 0¹ 7
6: Send
A
1
(0- 0 and c++
7: Aggregate momentum
nk
k * k
VF
(0% c.k
to the server
( Σ
g 0+ 3
(c +
+ +11- B)g
5
iES,
VT WSKT-SSKSS then it holds that AVBeKLVT
satisfied, i.e., S
8: Aggregate control variate
(LA+0 VSKT + T NKT
0² L²0z²
c+I = c¹
1
Σ
(ct+1 c))
T Σ EIV
N
VES.
for sufficiently large T, where e denotes Euler's 's number and A = f(0") -f" represents the initial optimality gap with ming ( X.
9: Download 0++1 and 1ec++++(1) (1-3)g ++1 to all clients
10: end for
Theorem 3.1 demonstrates that MasFl. achieves conver- in terms of E (0) I|² for suf-
gence rate of O VSKT ficiently large T. This rate matches the convergence rates of traditional synchronous FL baselines (Karimireddy et al., 2020b), demonstrating that the delays inherent in asyn- chronous training do not degrade the asymptotic conver- gence guarantees.
control variate ci-1 and its previous value g". ii) Local Momentum (Line 3, Algorithm 2). Each client computes its local momentum 9; i.k at every step of its local training. This local momentum combines the client's current gradient with the control variate correction, mitigating client drift and pro- moting alignment with the global objective. This two-level structure isolates all staleness representations on the client side, ensuring that the global momentum is computed based on the latest accumulators (c' and g'), which is critical for our theoretical analysis.
To maintain the convergence order of (+) as in the synchronous case, MasFL. requires the number of global rounds to satisfy T 2 ( This condition is less re- strictive than that required by CA (Wang et al., 2023) and FADAS (Wang et al., 2024c), which impose T 2 ( (since the convergence rates of both papers are Tmax
3.2. Theoretical Analysis of MasFL
Following the standard definition (Arjevani et al., 2023), a point 0 E Rd said to be an e-stationary point of function f R + [ (0) < e. Under this definition, MasFL finds an e-stationary point expectation within O (S global rounds, indicating linear speedup with respect to both the number of participating clients S and the number of local steps K. Notably, this convergence guarantee holds with- out requiring bounded gradient dissimilarity assumptions, such as (1), benefit from the carefully designed two-level momentum structure.
The following Theorem 3.1 presents the convergence rate of MasFI., whose proof is deferred to Appendix C.
Theorem 3.1. Suppose that Assumptions 2.2 and 2.1 holds. ]T_ be the global iterates generated by MasFl. Set
Let {0'TT
3 / SK and = / /SK Define a == maxe f2 +
20c2 K?L?. If the condition 1 - 4a
SK > 0 is
5

---

Nomentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
4. Adaptive Momentum-Drivee AFL
formulation ensures bounded global progress that
Although MasFL effectively leverages momentum in AFL accelerate convergence while eliminating data heterogene- ity bounds, it requires careful tuning of the learning rates that theoretically dependent on the unkonwn smooth- ness parameter L. and delay bound -atimmattn these parameters poses significant challenges and compromises the fundamental privacy guarantees of FL. To address this limitation, we further propose Adaptive Momentum-drivee asynchronous Federated Learning (AdaMasFI.), which pre- serves the benefits of MasFL while achieving problem- parameter-free convergence.
Ing''l Σ
=
7 S SES.
! =
S 7-
SK
9; LK
Nevertheless, the global momentum is still retained in AdaMasFL accelerate local model updates. These designs collectively enable AdaMasFI. achieve both normalization-indueed stability and momentum-driven ac- celeration.
4.2. Theoretical Analysis of AdaMasFL
The following Theorem 4.1 presents the convergence rate of AdaMasFL, whose proof is deferred to Appendix D.
4.1. Algorithm Design
AdaMasFL builds upon the framework of MasFL by seam- lessly integrating momentum with adaptive learning rates. The complete procedures of AdaMasFL are presented in Al- gorithms 3 and 4. Compared to MasFl,, the key innovation of AdaMasFL lies in its adoption of momentum-driven gra- dient normalization with a different server-side aggregation.
Theorem 4.1. Suppose that Assumptions 2.1 and 2.2 holds. Ler (0 ] be the global iterates generated by L and B
Set (SK) that
T3/4 11
KVT
v
SK T
then it holds
E [S((')||
Sonnentuu-Drivee Adaptivity. AdaMasFL. retains the momentum design of MasFL while introducing normalized gradients for local model updates (Line 4, Algorithm 4). This gradient normalization mitigates sensitivity to learning rate choices by automatically adjusting the effective step- sizes based on local optimization landscape. Normalized gradients ensure constant- maastanntmmgnitude updates regardless of gradient scales, satisfying
+ Lo
SK
VLTTmax
0o
+oV T Ti(SK)
+
(SKT)
S tTo T mmax L
(SK)* T
(SK)
+ FV VO
LOTmax
T
for sufficiently large T.
!7
9;
= ktt.
Theorem 4.1 demonstrates that AdaMasFL. achieves a con- vergence rate of O [SKTJ47 in terms of E f (0)].. Under the definition of e-stationarity, AdaMasFL finds an e-stationary point within O ( global rounds, which aligns with the communication complexity of MasFL. No- tably, Theorem 4.1 explicitly determines all hyperparam- eters, 1), 7. and / based solely on algorithm-specifi con- stants: the number of participating clients S, local update iterations K, and communication rounds This eliminates the need for trial-and-erroo tuning or problem- -aalameeer es- timation, resulting in completely AFL approach.
9.
By adapting the stepsize to gradient magnitudes, AdaMasFL eliminates the need for problem-dependent tuning based on unknown quantities such the smoothness constant T.
However, gradient normalization alone is insufficient achieve convergence in stochastic optimization, it dis- cards magnitude information. Recent studies (Hazan et al., 2015; Yang et al., 2023) have shown that normalized gra- dients can hinder convergence due to the randomness of stochastic gradient directions, even in simpler centralized convex settings. This issue is further exacerbated in AFL, where clients face heterogeneous gradient noise and delays. To address this, the momentum term plays a critical role by preserving consistent descent directions across clients and iterations.
5. Comparisons with Existing AFL Methods
We now compare MasFL and AdaMasFL with several rep- resentative AFL approaches using various metries, listed in Table Prior AFL algorithms face different theoretical and practical limitations. FedBuff (Nguyen et al., 2022), CA (Wang et al., 2023), and DeFedAvg-nIID (Wang et al., 2024a) all require careful stepsize tuning based on the maximum delay Tmax- While CA and DeFedAvg-nIID improve upon FedBuff by achieving a better convergence
Server-Side Aggregation. Unlike MasFL, where the server updates the global model based on the momentum g (Line 6, Algorithm 1), AdaMasFL updates the global model using the aggregation of local update directions (Line 6,
Algorithm 3) that T' 7SK Eies, (0'-7i 0²²²) This
6

---

Monnntuum-Driee Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Table I: Comparisons of AFL algorithms for handling heterogeneous data. (Convergence Rate = The convergence rate of different algorithms in terms of T Σ E [[ Additional Assump-
tions Additional assumptions aside from Assumptions 2.1-2.3; BDH = Bounded data heterogeneity define in (1); BG
Bounded gradient that [ - G, 0.)
Convergence
Additional
Stepsize-related
Algorithms
Stepsize Restrictions
Rate
Assumptions
Problem-Parametee
FedBuff (Nguyen al., 2022)
O
(ST)1/0 &
Ki/4ag og
+ Impaz
BDH
1/y S
4 37
Tmax
CA (Wang al., 2023)
o (SKT)1/3
Zuyu
BDH
S 36 may
_ 17 3ök v
Tmaxx L
DefedAvg-nIID (Wang et al., 2024a)
(SKT)/7
VKT
BDH, BG
mn Tmar 1) S AV3LK
Tmax- L
- 1800g N(N-NNN 5)) KT.'
m S min
FADAS (Wang et al., 2024c)
177
Imao?
BDH, BG
Tmaxi L, G
(P
12 S) KL "1 VaeaCo T KL
MasFL
VR (7KT)
SK
SZ. 11
VT VT VSKT 48K
AVBKKIVT
Tmax. L
AdaMasFL
(SK7)174
/Tuax 7:3/5
3K B 7
(SK)
7374
KVT
For the convergence rate defined in terms of + Ei= ['' we can readily obtained the corresponding rate with respect to
T-
T-1 ((')ll by taking square root on both sides of the associated bound. This operator verified by the following fact:
ET EVIVJO'' S 1 E VEIB S V E(V/(") where the first and second inequalities utilizes Jensen's 's inequality as the square root function is concave.
E E [(
2 Cg = KG + e and é > 0 is an adaptive optimization parameter.
3 3- and == T + 20e n k2
1- la /S/TT
rate of O (SKT)/s and linear speedup with respect to
6. Numerical Experiments
S and K, they still rely on bounded data heterogeneity as- sumptions and knowledge of the smoothness parameter L. FADAS (Wang al., 2024c) employs the AMSGrad opti- mizer at the server-side to enable adaptive stepsize in AFL. However, its convergence guarantee relies on both bounded gradients and bounded data heterogeneity assumptions, and fails to achieve linear speedup with respect to local steps K.
We evaluate the performance of our algorithms on the image classification task using two real-world datasets: CIFAR- -0 (Li et al., 2017) and FMNIST (Xiao al., 2017). For FM- NIST, we utilize a convolutional neural network (CNN) con- sisting of three convolutional layers and two fully connected layers. For CIFAR-10, 10, we adopt ResNet- 18 architecture (He et al., 6). We compare our algorithms against two state-of-the-aat AFL baselines: CA (Wang et al., 2023) and FADAS (Wang et al., 2024c). We simulate the practical asynchronous conditions using FedBuff's delay mechanism. Specifically, at any given time, there are a total of M, clients performing local updates concurrently. The execution times of all clients are sampled randomly from uniform dis- tribution. These varying execution times naturally create different delays in global aggregation participation. Detailed experimental setups and additional simulation results are provided in Appendix E.
In contrast, our algorithms achieve substantial improve- ments over existing approaches. Specifically, MasFL elimi- nates the bounded data heterogeneity assumption while at- taining state-of-the-art communication efficiency. Building on this foundation, AdaMasFL maintains the best-known communication complexity while operating in completely problem-parameter free manner, with all learning rates ex- plicitly determined by aggrrthm-speccnn and T. Collectively, these advancements mark significant step forward in achieving robust and adaptive AFL.
constants S, K,
Figure I compares the test accuracy of various algorithms versus the number of communication rounds on both the CIFAR-10 10 and FMNIST datasets. For both datasets, we pro-
7

---

Mamientum-Drivere Adaptivity: Towards Tuning-Free Freng Asynchronous Federated Learning
0.7
2..9
0.4
CATL
Gh7LL
CL7TL
CRT
MED4
19045
MD45
Maatt
Nertt
350
540
270
CoMEONLL.MMIO rouned
Conrenamical 1AAr)
Camman round
Getmmnnkaaien round
Li.d. CIFARIO
(b) Non-i.i.d. CIFARIO
(c) Li.d. FMNIST
(d) Non-i.i.. FMNIST
Figure 1: Test accuracy versus communication round on different datasets with i...d/non-i.idd. data (M. 20).
20.9
0.4
0.0
HADAS
FADAS
0.2
300
435
300
102
200
300
250
420
802
210
390
Iound
Communiccl HARR
M
30
(b) M 40
(c) M. 60
(d) M. 100
Figure 2: Test accuracy on the non-i.idd FMNIST dataset under varying levels of asynchrony.
vide results for i.i.d and non-i.id. data distributions. The learning rates of our algorithms, MasFL and AdaMasFL. are derived based the theoretical guidance provided in Theorem 3.1 and Theorem 4.1, respectively. To ensure fair comparisons, the hyperparameters of the baseline methods, CA2FL and FADAS, are optimally selected according to the recommendations in their respective papers. The results show that our proposed methods, MasFL and AdaMasFL. significantly outperform the baselines, CA2FL. and FADAS, in both convergence speed and test accuracy. This im- provement can be attributed to our two-level momentum design, which accelerates optimization progress at each up- date. Additionally, the momentum mechanism stabilizes the optimization trajectory by accumulating historical gra- dients, as evidenced by the results the non-i.i.d. setting. Notably, the advantages of our algorithms are particularly pronounced in the more challenging task, CIFAR-10 with non-i.i.d data, as shown in Figure 1b.
0.9
Accurady
0.7
0.6
0.5
CA
FADAS
AdaMasFL
0.4
Learning Rate
(a) Non-i.i.d CIFAR-10
0.9
0.8
0.7
Accuracy
0.5
0.4
Figure 2 illustrates the test accuracy of various algorithms on the non-i.id. FMNIST dataset under different asyn- chronous settings. Here, M, denotes the number of clients performing local updates concurrently. Since the server updates the global model only after collecting total of S client updates, larger M. enables more frequent global aggregations, resulting in greater asynchronous delays. In Figure 2, we fix the learning rate settings of all algorithms to those used in Figure 1 and evaluate their performance as M, increases. We observe that AdaMasFL demonstrates ex- ceptional robustness to varying levels of asynchrony, main- taining nearly consistent performance despite increasing
0.2
CA
FADAS
0.1
AdaMasFL
10
10
10
Learning Rate
(b) Non-i.id. FMNIST
Figure 3: Test accuracy versus learning rate with no.-i.i.d. data.
8

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
delays. In contrast, the performance of other algorithms deteriorates significantly, requiring reconfiguration to adapt to changing environments. Similarly, Figure 3 illustrates the test accuracy of various algorithms versus learning rate on both the CIFAR-10 10 and FMNIST datasets with non-i.i.d data distributions. It is evident that AdaMasFL consistently outperforms the baselines, CA2FL and FADAS, across the displayed learning rate regions.
ceedings of the 12th International Conference on Learn- ing Representations.. 2024.
Cutkosky, A. and Mehta, H. Momentum improves normal- ized SGD. In Proceedings of the 37th International Con- ference on Machine Learning, pp. 2260-2268. PMLR, 2020.
Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
7. Conclusions
This paper proposed two novel training approaches for AFL: MasFL and AdaMasFL. Specifically, MasFL introduced a two-level momentum mechanism that eliminates the re- quirement for data heterogeneity bounds in non-i.i.d. set- tings while achieving the best-known communication effi- ciency. Building on this foundation, AdaMasFL incorpo- rated momentum-driven gradient normalization, removing all dependencies on problem-speciffe parameters in algo- rithm tuning while preserving the theoretical guarantees. Ex- tensive numerical experiments demonstrated that our meth- ods consistently outperform state-of-the AFL algorithms in runtime efficiency and exhibit exceptional robustness across a wide range of learning rates and asynchrony levels.
Even, M., Koloskova, A., and Massoulié, L. Asynchronous SGD on graphs: A unified framework for asynchronous decentralized and federated optimization. In Proceed- ings of the 27th International Conference on Artificial Intelligence and Statistics, pp. 64-72. PMLR, 2024.
Fraboni, Y., Vidal, R., Kameni, L., and Lorenzi. M. A gen- eral theory for federated optimization with asynchronous and heterogeneous clients updates. Journal of Machine Learning Research, 24(1 ( 10):1-43, 2023.
Hazan, E., Levy, K., and Shalev-Shwartz, S. Beyond con- vexity: Stochastic quasi- optimization. Advances in Neural Information P Processing Systems 28, 2015.
Impact Statement
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Hsu, T.-M. H., Qi, H., and Brown, M. Measuring the effects of non-identical data distribution for federated visual clas- sification. arXiv preprint 1rXiv:190900633 2019.
References
Abreha, H. G., Hayajneh, M., and Serhani, M. A. Federated learning in edge computing: systematic survey. Sensors, 22(2):450, 2022.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M. Bhagoji. A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. Foundations and Trends@ Machine Learning, 14(1-2):1-210, 2021.
Arjevani, Y., Carmon, Y. Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165-214, 2023.
Karimireddy, S. P., Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprini arXiv:2008. 036006 2020a.
Assran, M., Aytekin, A., Feyzmahdavian, H. R., Johansson, M., and Rabbat, M. G. Advances in asynchronous parallel and distributed optimization. Proceedings of the IEFF, 108(1 108(11):201322311 2020.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference Machine Learning, pp. 5132-5143. PMLR, 2020b.
Chen, Y., Ning, Y., Slawski, M., and Rangwala, H. Asyn- chronous online federated learning for edge devices with non-III data. In Proceedings of the 2020 IEEE Interna- tional Conference on Big Data, pp. 15-24. IEEE, 2020.
Koloskova, A., Stich, S. U., and Jaggi. M. Sharper conver- gence guarantees for asynchronous SGD for distributed and federated learning. In Advances in Neural Informa- tion Processing Systems 35, pp. 17202-17215 2022.
Cheng, Z., Huang, X., and Yuan, K. Momentum benefits non-IlI) federated learning simply and provably. In Pro-

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Leconte, L.,, Nguyen, V. M., and Moulines, E. FAVANO: Federated averaging with asynchronous nodes. arXiv 2023.
Sohom Mukherjee, Nicolas Loizou, S. U. S. Locally adap- tive federated learning. arXiv preprint arXiv:330.006:06 2024.
preprint arXiv:2305.
Leconte, L.,, Jonckheere, M., Samsonov, S., and Moulines, E. Queuing dynamies of asynchronous federated learn- ing. In Proceedings of the 27th International Conference Artificial Intelligence and Statistics, pp. 1711-1719. PMLR. 2024a.
Wang, S., Tuor, T., Salonidis, T., Leung, K. K., Makaya, C., He, T., and Chan, K. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 37(6):
1225-1 2019.
Wang. X., Li, Z.. Jin, S., and Zhang, J. Achieving linear speedup in asynchronous federated learning with hetero- geneous clients. IEEE Transactions on Mobile Comput- ing. 24(1):435 448, 2024a.
Leconte, L., Moulines, E.,, et al. FAVANO: Federated averag- ing with asynchronous nodes. In Proceedings of the 2024 IEEE International Conference Acoustics, Speech and Signal Processing, pp. 5665-5669. IEEE, 2024b.
Wang, X., Sun, Y., Wai, H.-T., and Zhang, J. Dual- delayed asynchronous sgd for arbitrarily heterogeneous data, arXiv preprint arXiv:2405. 16966, 2024b.
Li, H., Liu, H., Ji, X., Li, G., and Shi, Cifar10-dvs: an event-stream dataset for object classification. Frontiers in neuroscience, 11:309, 2017.
Wang, Y., Cao, Y., Wu, J., Chen, R., and Chen, J. Tackling the data heterogeneity in asynchronous federated learning with cached update calibration. In Proceedings of the 12th International Conference on Learning Representations, 2023.
Li, J., Huang. F., and Huang, H. Fedda: Faster framework of local adaptive gradient methods via restarted dual av- eraging. arXiv preprint arXiv:2302.06103 2023.
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Feder- ated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-66 2020.
Wang, Y., Wang, S., Lu, S., and Chen, J. FADAS: Towards federated adaptive asynchronous optimization. In Pro- ceedings of the 4 International Conference on Machine Learning, 2024c.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and learning of deep
Arcas, B. A. Communication-effccie
networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. pp. 1273 1282. PMLR, 2017.
Wu, X., Huang, F., Hu, Z., and Huang, H. Faster adaptive federated learning. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 37, pp. 10379- 10387, 2023.
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. E. Asynchronous SGD beats minibatch SGD under arbitrary delays. In Advances in Neural Information Processing Systems 35, pp. 420 1000-433.220 2022.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnis a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 170.0007777 2017.
Nguyen, J., Malik, K., Zhan, H., Yousefpour, A., Rabbat, M., Malek, M., and Huba, D. Federated learning with buffered asynchronous aggregation. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics. pp.
Xie, C., Koyejo, S., and Gupta, I. Asynchronous federated optimization. arXiv preprint arXiv: 2019.
Yan, W. Zhang, K., Wang. X., and Cao, X. Problem- freee federated learning. In The Thirteenth International Conference on Learning Representations, 2025.
PMLR, 2022.
Pandya, S., Srivastava, G., Jhaveri, R., Babu, M. R., Bhat- tacharya, S., Maddikunta, P. K. R., Mastorakis, S., Piran, M. J., and Gadekallu, T. R. Federated learning for smart cities: A comprehensive survey. Sustainable Energy Tech- nologies and Assessments, 55:102987, 2023.
Yang. J., Li, X., Fatkhullin, I., and He, N. Two sides of one coin: the limits of untuned SGD and the power of adaptive methods. Advances in Neural Information Processing Systems 36, 2023.
Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S., and McMahan, H. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
Yu, T., Song, C., Wang, J., and Chitnis, M. Momentum approximation in asynchronous private federated learning. arXiv preprint
2024.
Zakerinia, H., Talaci, S., Nadiradze, G., and Alistarh, D. QuAFL: Federated averaging can be both asyn- chronous and communication-cffiiie arXiv preprint arXiv:2266.000: 2022.
Reddi, S. J., Kale, S., and Kumar, S. On the convergence of Adam and beyond. In Proceedings of the 6th Interna- tional Conference on Learning Representations, 2018
10

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Zang, Y., Xue, Z., Ou, S., Chu, L.,, Du, J., and Long, Y. Effi cient asynchronous federated learning with prospective momentum aggregation and fine-grained correction. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 38, pp. 16642-16650, 2024.
Zhong, L.,, Chen, X., Xu, C.,, Ma, Y., Wang, M., Zhao, Y., and Muntean, G.-M. A multi-user cost-efficient crowd- assisted VR content delivery solution in (c--and-beyone heterogeneous networks. IEEE Transactions on Mobile Computing, 22()):4455444211 2022.

---

Monnntuum-rrvee Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
A. Related Works
Our work draws inspiration from and contributes to several active research areas in FL, including asynchronous optimization, momentum techniques, and adaptive stepsize methods.
Asynchronous Training Paradigms. Traditional asynchronous SGD methods (Mishchenko al., 2022; Koloskova et al., 2022; Even et al., 2024) have established theoretical foundations for distributed optimization, particularly in addressing client synchronization challenges. While these methods have demonstrated linear speedup convergence under independent and indentically distributed (iid) settings and various objective functions, their effectiveness in non-iid scenarios has been limited. Moreover, these approaches typically focus on immediate gradient computation without local iterations, leading to increased communication overhead. Our work extends beyond these limitations by incorporating local training while maintaining theoretical guarantees in non-iid settings. Recent AFL frameworks like FedBuff (Nguyen et al., 2022), DeFeeAvg-nIID (Wang et al., 2024a), and DuDe-ASGD (Wang et al., 2024b) have shown promising empirical results in handling heterogeneous data distributions. Methods such as QuAFL (Zakerinia et al., 2022) and FAVANO (Leconte et al., 2023) have explored different asynchrony models, including client interruption strategies, but face limitations in theoretical guarantees or practical implementation. Our framework distinguishes itself by achieving linear speedup without requiring bounded heterogeneity assumptions, while simultaneously providing robust performance across diverse learning rate configurations.
Momentum- Based Techniques. Momentum has emerged as a powerful technique for addressing data heterogeneity in FL. Various approaches, such FedAvgM (Hsu et al., 2019) and SlowMo (Wang et al., 2019), have incorporated server-side momentum to enhance convergence rates. More sophisticated methods like MIME (Karimireddy et al., 2020a) and FAFED (Wu et al., 2023) have explored the combination of client- and server-side momentum with adaptive techniques. While these methods have achieved improved convergence properties, they generally require careful tuning of nultiple hyperparameters. Recent work like FedSPS (Sohom Mukherjee, 2024) has attempted to minimize hyperparameter dependence but still relies on restrictive assumptions about gradient bounds and data heterogeneity. Yu et al. (2024) identify that asynchrony introduces implicit bias in momentum updates and propose momentum approximation for AFL, which finds optimal weights for historical model updates approximate synchronous momentum behavior. FedAC (Zang et al., 2024) addresses both model staleness and client drift issues through adaptive server updates and corrective client training, though its empirical improvements lack theoretical convergence guarantees. Our approach advances this line of research by providing a fully adaptive framework that operates asynchronously without bounded heterogeneity assumptions or the need for problem-specific parameter tuning.
Adaptive Learning Schemes. Adaptive learning rates have been extensively studied and proven highly successful in mingle-machine learning scenarios (Duchi et al., 2011; Hazan et al., 2015; Reddi et al., 2018; Cutkosky & Mchta, 2020; Yang et al., 2023), where they effectively address the challenges of learning rate tuning and gradient scaling. In recent years, the critical need for hyperparamettr--fficceen training in federated learning has led to growing interest in extending these adaptive methods to FL. settings. Server-side adaptive methods, such as FedOpt (Reddi et al., 2020) and its variants (FedAdaGrad, FedAdam, and FedYo have demonstrated enhanced convergence properties compared to traditional fixed learning rate approaches. Recent developments in local adaptive methods, including FAFED (Wu et al., 2023) and FedDA (Li et al., 2023), have explored client-side adaptation strategies. FADAS (Wang et al., 2024c) introduces a global adaptive AFL. framework that applies adaptive optimization techniques at the server-side aggregation while supporting asynchronous client updates, and further proposes delay-adaptive learning rate adjustment strategy to enhance resilience against large client delays. While these approaches have shown promise, they typically require bounded data heterogeneity assumptions and careful calibration of various hyperparameters. In contrast, our method integrates adaptive stepsizes with client-side momentum in an asynchronous setting, eliminating these restrictions while maintaining theoretical convergence guarantees.
B. Technical Lemmas
Throughout the analysis, we use the following notation for summations:
Σ; denotes summation over all clients i NN:
Eies, denotes summation over selected clients in multiset Sy;
Σx denotes summation over local steps k E {0..... .....,, K - 1):
Σe denotes summation over global rounds E {O...., T 1}.
12

---

Momentum-Driven Adaptivity: Towards Tuning-Free Free Asynchronous Federated Learning
Lemma B.I. Given vectors E Rd and # Ei= Wa if sample S (1,-.. N uniformly randomly
such that [S] = S, then it holds that
Σ wi xES
Σ wi w|
SN
Proof. Letting 1(2 E S} be the indicator for the event i E S, we prove this lemma by direct calculation as follows:
N
1
E
w
=
w 1 (iES)
S
S
iES
1=1
Σ || 1| 1fi S) + E (Ton)iiieE )
E
52
1
N
|
+ 52 N(N -1) 2
1 S(S 1)
-1),
Σ w.Twj
SN
1=1
1
Σ
N
||0/||
+
1 S(S -011 1)
Σ Wi
N
|w 1?
SN
22 N(N - 1)
N-S 1
N
N(S 1)
Σ
|w.11
[ ?
S(N - 1) N
5(N 1)
N
N - 5 1
||:s 1 + 3 2
=
S(N - 1) N
1 N
Σ
|w
3 1
|
SN
where the last inequality uses the fact that
N-8 N-1
< for any nonempty set S.
Lemma B.2. For any i, t, define Φ = E fi (0--))= - c
8' =
of
0²
r²-r! 2
and
w/ = N ΣS w.. We have
T T-1
2N
A1.200
402
41. R-1
+ T Σ w
+
+
T
SKT
T
K
t=
t=
2 L T-1
Σ
(E||E")
2 + E
V (0')
S2T
where E = V/(00' +1
Proof. Since for any i, the 8 elements in S, are uniformly sampled from (1,.... ,N), we have
d
if S, (w.p. )
1 E
VF
00
if S, (w.p. $).
13

---

Momentum-Drivee Driieen Adaptivity; Towards Tuning-Free Asynchronous Federated Learning
Using Young's 's inequality repeatedly, we have
1
5
E
V
f
0 +)
+
S N
E
0 0')
1 K
Σ
VF
(0%
N
S
E
f
7! (
F Vfi (0-
c
2
+
25
0²
+ L
N
N
K
S N
E
(1+ +
S
$5- 111 +
|
2N
L2
0'
0² 0' 1
18] |
+ N
2$ 0²
+ L.Wo
2N
5
K
S
0
+
4N
2
||
2
+ E
V f
0 - 1²)
+
25
0²
+ L'ww!
2N
s
N
K
Summing up the above inequality over i and t yields
S 1 T-
2N T-1
Σ
E 181891 + B (
2N T
T
ST
1=0
2So²
+ 2SL²
Σ wt
(4)
NK
NT
1=0
Since for any i, i. =
1 K- K k==
VF
(0": IMM)
1.
and cf = k Ekso
VF ( . Then, we have
$ =
1
S
E f (6") - el1 + N
E V (09) - c: ?
N/
20
2$
w! Vi.
K
N
20t Thus, 8¹ N E, 0 S
K +
25
L2
Plugging this incquality into (4) completes the proof.
N
Lemma B.3. For any i, L,k, define w = 5 0 0² r² || we 1/4 E, w/ Φf E V (0-
Φ'= 1/2 E, Φ and c = Bl0 1 -n (3 (v.i (0.+)) ट + cr
+ (1 ))/²=()
We have
w' $5n 2 x² 2n0KL 22,3222.22 + 27 ) +1 Σ
E 11 + E [ 1²)
1 T-1 T
+ 10n2 2n
Σ
(L'w' + +a) + 210KL + +22
w
+ (1+ + +33 83 Lo²
T
where w <312 21 || [0') 112 + 2 (32 + +) + B2) K7"0² + (1+ (3
Proof. From the definition of S we have
E c. - S.² -.. 2 = 3 f
(0:) - Vii (0) ||
S 3 L2B
0 0 0/A-112
22
EE
1 1
2
+ B28
Vife (0/+)= - VF (
< 12
18
2
+ 72 8282
14

---

Saaientuu-Drivver Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
E 1 | 2 1
E 5 - - --- + (1 + nBL)B
1).T.)
( | + (1 + 1/31)11
|< + (1 + 11LL)
S 1)81111 (1 + 1181.) E
= (1+ n1)) B || | + (1 3
S (1 + 1) 23 B ||c +1(1 + 30 Lo²
s L E |c:001
+ +1(1 + m) LO²
where we use (1 n1L) पमक S e. Then, we have
k-
E 00.k 0¹ 00-
S 2E
Σ
+ 0202
k-1
2
$ 2k
+ 2km)2 3²02
< 2k
2
(,.0 1
j(1 + BBL))n + +2h72 8202
11 + +1 + n3L)) Lo² + 2kn22300²
S 2k 2n
Summing up the above inequality over k yields
1 E
Σ
k 0¹ 01 s K2 22222 ( 2 + +11+n311)) 1 + K22
(5)
K
Based on the definitation of c: c.:0 = -n (3 (v (0- ( c
- +
+ (1 - -)))))))))) Then, we have
5 2 = 1172111 3 f 00' ) F V.f (0 (0- - ( + 3 - Vf -V (0)+
2/ (0 -1---11 -
+(1 - ()) (9) -: / (0 (0~
32 L2B @ +: 0
E
Vf 0 (/- - -=|
+B V
|f (0 (i) - -d-r((²
+ +5n7(1 - 3) | 5
||
/
(6)
We know that E 10 0r ,0-- =|² < 22² E
|
2 E v -
Additionally, for any i, t, we have
E f (0-
- -2-11 )
=E f.f (0)
F 1 K
VVF
VF
(0:4)
1 Σ
VF (0.* (
KKI
k
20 K
< 221
15

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Further, for any I, we have
E Vf (0') - 1| = E
V F N Σ Vi (0-Ti)
1
Σ
c
N
I 2 N
Σ
E
Vfi (0)) 1 (0--x) ||²
+ +20
2L
Σ
E gatt 0¹1 || + +20
- N
d=
B1EEd12 + | V. (0)
S 47 T
Taax
+ +20
Plugging the above results into (6), we have
E
2
I5n 32
22,212 E
18
-1
2
+ Vf (0- + 2 + 20²²
K
Tnax + 3
EI 12 + E Vs (04) (0) + 3²0
N
dmt
Tmax
+ 5 gt -/2
5 f (0 11
Plugging the above inequality into (5) and summing over i, I yields
Σ
2
(282 + 2T ) +1) T 0=
B1|E9122 E [ 1²)
T 0=
+ K2n 2n 1
(I'w' + +0) + (106208KL + +1)
T
w
+ +1++ 3 Lo 3
T
Since c.- = 1 Ikko VF 000: : for any i, 0 = 1 Σ, ci, and 9" = c², we have
N
E
00.0 2
= n 3 f. (0 +C) + +(1 - 0)
= =1²E 3
VI. (89)
1 Σ VF (8) (0): K
1
Σ VF
(0::5, (V((0':5)
F FV (09)
NK
i.
18202
0²
S 317²
+
+
|/ 109)
K
NK
w/t < 2
Σ
EE 1 + +1 3LL KKP
N
$ 3772 122 2n3KL
| ||
+ (3c28Kk ( (8+ (8+NN + 882)
KnP0² + (1 (1+ (2 LO?
16

---

Ceinentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning C. Proof of Theorem 3.1
Based on the L-smoothness f()) in Assumption 2.1 and Line 6 in Algorithm we have
1(0 - f(0') (Vi(0') 0t 0¹) + T. 0 - 0011
-VVV + (V) V5(0") - ( + 7 |19 T V/(0')]
S ((L ||2 + |//0') 9 411 4 |V - - + > [
= -1- 2 + 2 + 2, (0') - 1|²
Define = = -f(0")--g" and A = -((0)) ) f", where f mine f(0) -00. Then, - s s(00) -m yields
A. Summing the above inequality over / = 0, 0,,, T
[V)(01112
2A 7(1 L)T
1 + 2
|09|3
2 T
t=
From the update rule of g +1 given in Line 5 in Algorithm 1, we have
B E (1- 3) (Vi(0') - g") + Vi(0") -c 1 Σ (ct+1 ci)
S
iES.
=²¹
(1 -3)8 | ) 0²12² + 1 23E ((1 B) (V)(0') - -9') v²)
@ (1-3)
g/'l²
3E o'1 2 + 2BE 3) (VS(0') (6) ()((0))) 1
NK Σ A.c (0:.0)
Σv
$ (1 8)²
(1+
3 2
E
V
-0'l² + 3 |2+ 2 |/5 $1,
(8)
where (a) is based on the fact that
B[o' = Eyee" In ((
vs(0") -c' 1 Σ
0 g5 d.)
= =B(g! Jvsik
VF
NK
i,k
= =v((0')
NK Σ V. (0! = 2
i.k
17

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
To upper bound (1 - 3)²
(1 + 2
E V f(0') 90ll 2 in (8), we have
(1-
1+
9 2
E \ - -l'l
I (1- 3)8
(1+
8
E
( 1 ++ 2
8
|| + (1+ 2) - (0-
2
< - M)E | + 21
100 0¹ 112
B
4L3g²
S (1 - 3)E ||-
+
(B18-~11²
(E
+ |
B
4L222)
4L332
= +
B|
E
+
3 E (0-1)
B
Define Φf = E
f
(
(0)
0
+ -
. 8' = = क w
=
k
Σ E
0
0 00
and w' = =" w/: To
upper bound B 1| in (8), it follows from Lemma 1.1 that
E 0
< E
(((0') - N
1 Σ
1 E
Σ
(c (c+t1 -
- Σ ( +
SNL
< E
(
1
Σ
VF
00% <
SSN Σ E
K Σ VF 00 (,++ -c²
NK i
2E 1/
20
NK +
Σ E
1
Σ
VF
VV. (0%+t) = v (o-Ti) = =Vii (0- - c/
SN
K
2E| ||
602
4L2
w²
4L?
0
-'
0
+ -1?
5 /h
4
SK
S
SN
< <B
4L2
w/
8-2
Σ
E E
2 +
00 ( + -00-
SK
SN
Plugging the above results into (8), we have
4L22²
4L222
00 )1 + 23 + 1) 1|66111 6.
11 - 1 3+
E
B1
V.
B
B
SK
L2
w'=
8
Σ
E 1
1|
+
E
4s (0- 1P)
+ 482
5 65-
5
SN
Additionally, for any t, we have
E
11 = R
(((0")
F N
1 Σ V.. Σvi. (0'
1
Σ S. So (05+t)
NK
6
< 2E
N Σ
(0') - Vfj (0-T:)
+ 2'
2T1 N Σ マ
t-1
B gdt+ 0d| 2
+ 2' '
d=t-r!
< 44mmxx² x 1
B1 + E
V (**) (00) + 2'
d= Tmux
18

---

Momentum- Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Thus,
4L377
4
[1 3 + 3 5
E E| < 1 3 +
E B| +
B E
V
+ 48L² 10'
w
B
+
2
E 18
||
+ V
0 ( + 4
S 8
SN
| 4. (00) (1) + 63302
+ max 3y21,
B1IEd|2+ + k
SK
d=t- Tiax
Summing up the above inequality over t yields
2
1
1
B2
E1EE912 12
2
T-1 1
+4L2 1 + 3+ +
T-1 1
43 T-1
E |
Σ w
3T
32T
T
ST
1=0
1=
1=
3 +
1
6,80²
+ +8-2
27
+
5
T
SK
t=0
From Lemma B.2, we know that
1
T
2No
4T2w0
402
4I. T-1
Σ ~
+
+
+
T
SKT
T
K
T
t=
1=
4N2 T-1
SeT
From Lemma B.3, we know that
T-1 1
Σ of K2
(282 + 2T
+1) T t=
BIE8912 + E \/((0)) I²)
T 0=0
+ 2nBKL 1
(T'w' Φ0) + (10c2 + 1)K 8322
T
w T
+ (1 + 13) Lo²
Plugging the bound of $ ET= Φ' into $ I wt yields
1
Σ
2ōn K K2 218KL (2825213
1 2 max +
1N2)
+1
1
EIE 12 + +EE"+EEIVSSON) =
T t=0
S2
T
+ 12 kn 1
w¹ (0KK2 + 1)K
T
w
1N SKT
41.2w0)
+ +11 3 +
+ 32 22
T
3 Set 3= 13=0011)) (+4). - ar. and KT < 0 (1). Then, 2n0KL < e². Thus, we have
T Σ ns w5n K2
2 +E [=(0"))) + 50c² Knn3333
w
T
T
19

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
where X means "less than or asymptotically equal to" in order sense.
Similarly, plugging the above bound back into
1. T 2 Φ', we have
T-1
8L
4a² wh and + Eiz Φ² into (9), we have
N
+ 41,
Kn +
s ~²n² T
Σ
R
T D=
T
K
Plugging the above bounds on +
2t=
31 T-1
E
1
T-1
+ 2230²
+ w1,ww0
12
+ 200
4TH
3T
4T
SK
+ max B2 + 20n7 K2 1.2e²)
Σ [ (T
Since cq. = K 0k= F
: 1.M) for any i, c.0 = 1
N Σi c. and 9" = c., we have
E B 00 2 E
V f0 -3
5550 Σ (c: c.) + c - -(1 --)9g00
1
S
1ES0
E
V
Σ
VF
NK
+
8
Σ
VF
ET - 1.6)
F V.. (0%) F VVF. (0 VF (0%*t -.aa)) ))
SK
iESg.k
2
8,32
+ g2
Lwi. w
$
+
NK
SK
iESo
From Lemma B.3, we know that, for any i,
1 1)) + ) Kn"0² + (B+ 82
w S 31 K2 2
| f [1 + 36 302K
(82 + N
V (09) 1| + 3e² Kn²0²
S 22
N
Thus, we have
+ 11
3T Σ
1 T
E B|
(2 3T
+ 118
802
800
64L2
3SK
3K
3NKT
m 3
2
32 + 20n K2
|
+
+
V 1²))
Denote by a == 7 T 32+ + K22 2,, We require a < 1.2 Then, we have
Σ
T-1
E|E*1 12
1+
[ +
BT + 113
2
402
+
400c23202
1
T 1=
3 4a
T
SK
K
NKT
1=
where we use
4a 2 2. Plugging the above bound into (7) yields
T-1
24
1 1+ 2 1 + 4a 1
E V f( (00)) 2
<
E
V [1
T
7(1 - LTT
1- 27 3 4a T
1=
1=0
1 T7
((
2
402
400g
2
16T202
+ 113
+
+
1 1 2
3T
SK
K
NKT
20

---

Momentum-Driver Adaptivity: Towards Juning-Free Asynchronous Federated Learning
(L+ (1+ 4a)
2A
1 ++20
2yL
2
4 SK
B B /
+ 113
[1 (1 4a)
T t=0
7(1 - -2
1-2y
BT
+ 1 2,
/400c² 820
161.a²2
+
1- 1-27L
K
NKT
When 2 8a- 8y1. 2 0 holds, let 1 v SK
T
and 7 =
4I
9
IL
1
V
SK T
Then, we have
(3 - 1-44) + 2602)
3 - 4a
200c So²
81.20²
4a
SK T
VSKT
4a V
SK
T
NKT
T
Note that we require 4a
SK T
i.e. a
SK - max
K2
5 1 1-
SK
D. Proof of Theorem 4.1
We first present the following inequalities that are frequently used in our analysis.
Lemma D.1. For any i, t, we have
0 0¹ 00::||= 3 k and
K2
1 K k
Σ 10
g
2 n.
K
Proof. From the update rule of local model, for any i, ks and t, we have
00.ht1 0%.6|
g.
I
9. 1.
Then,
2
k-1
0²
0
0.0)
< k
Σ
0
-0%01 n7b62.
Summing the above inequality over and le yields
Σ 100
0-~
n1² K
k2
1²² 6K
(K 1)K(2K - 1) S 1
K
K
Similarly, we have
1
Σ
-
g
1 K
1
Σ
(1007* of
001²)
$ "
K-1
Σ kニ nK
K
Moreover, we have
1
||00 - 11-
g;
g
< %
SK
2.k
SK
1.
9
S
9
and correspondingly 1|0¹ 0-- Σ. E
10 -0-11
< T/C.
21

---

Momentum- Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
From the L-smoothness of [(+) in Assumption 2.1, we have
-
I <V((O') (0e
+ -
00')
L
|
0¹12
(10)
2
-VV
1
Σ
9:
t.k
SK
iES.,k
[
L2
- (AS(0') - 9(th1)
(g
9;
+
SK
1.k
SK
1.
2
KESt,k
9i
iES,
99
9i 1
g++11
22L L
<> ( g 7 (g ()=+))
7 >
SK
f,k
g 1+1
gi
(0)
3 27 (7/14 11 |({'')|| + ||g
1
9 f.k
g g++1
7²L
+
SK
9 1.k
11 +1
2
iES,
x 27 ( 11 |/ +
24
9:
G
++1
L
(11)
SK
2
where (a) is based on 7 /V
-7 1 ||
> (00
g
and (b) is based on the following result.
9, 1.k
g 1+1
||
SK k
1.k:
1
9,
g-+1
= =||g*|||
Σ
9;
SK
1,k
l1g 1 11
1
|1
iES
9
|
Σ
9: t
9: 1
+
||g
+1|
1
g 1,k
SK
g
SK
g
9
KES..k
9;
iES.,k
||
||9
1g++1|]
9
9 1.
9 t
1+1
SK
S
11g +1+ ||
g
SK
SeS.
|9 ||
||
9
A
Σ
g - ++1
SK
93
SK
iESt.k
5 SK
9
++1
k
Summing up (11) over & yields
E
S
A
2 T
Σ
E
( - -
+ 7h
E
Σ
9
r.k
g 41
SKT
2
1=0
22

---

Coonntuum-rriver Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
D.I. Analysis of + - E (0') 1
Define & == v g u²= = v (0' - ( and v' = (VS(0')- - -c' - -$EEss (c - c)). From the
update rule of g given in Step 9 of Algorithm 3, we have
33 (1- - B) (Vf(0") -g') + 3 V.((0) -d' - Σ (c, c))
1ES:
-(1 - B)8-11 + (1 - -B)"² + 30²
=(1 - ") + Σ l1 3)+11d + Σ
g B)
d=1
Based on the triangle inequality of l norm and the concavity of the square root (-) we have
12) 1/2 3)
E E||Ea| <(1
|| + Σ || (1 3)
E
Σ d (1
(12)
Since - =
~K11 VF
for any i, c - E. c. and g" = c., we have
0k=0
E 10
(
ΣVF
VF 00: :. (A) SK
Σ
VFF 0%: (.)) VF (00 0.
NK
i,
SeSo
B
VF (PPETTTM)) F F.. (0.) F v.f. (DnAh) AF (0 c
+E
VNK
SK
iESo.k
30
B
E
Σ
VJ (09) Jt. (0.0et
Bo VSK
VNK
VSK
SK
iESo.k
BL
E 110000
0%1|
30
+
NK
VSK
i
1
30
n +
(13)
2
VSK
Additionally, for any t, we have
Iu' || [
-
L L 0 0'll 14L
1
g t
< Z7L.
(14)
SK
1gg
1,k
veS..k
Further, have
E
Bod (1 -3)0-0
Σ g 12 (1 (3)
1=1
d=1
Σ
E
(Bedi (1 30-dh,30000 dd))
Idd
23

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Since ct = 1 R Ex= VF for E St and c' = + Ei= 1 ct, for any t, we have
F[01IF9 = -E(e J S (00))
[R(e Jvsk
Vi((") - c²'
1
Σ
VF
ot)
NK
k,
= =VS(0') NK Σ Vii (0!*t) = $
i
E 1 = N Σ E
1
V F Vs
(0L
Σ
fi
(0%.h)
NK
L N Σ E
L
0² o
E
0 1 0
NK
f
2
N + TN
S Tma L 1 ZnKL.
We also have
E
VI(0')
1
Σ Vf: (0!..)
SK
iES,,k
2
Σ E Vf(0") - Vf (0+
21
Σ
E 0 +5 - 0:.
+
S
SK
iES,
ieS,.k
< 27 2
mux L + 17² R2L
1 NK Eip Vfi (0!*) I|
Similarly, we have E |/ E (5(0')
I 2 max 1!? + 12?
For any 0 S t1 < 1/2 S - 1, we have
E B ul2) = E (0', E [
= E
V (0'))
Σ
V (0.1itt,
,86// + Es, c¹ - S Σ of
: .8613
SK
iES..t
iES,
+E
1
Σ
(v/) (0/:.t)
VF -,.s) 16/22
SK
1
E
Vif (0tr)
1
Σ Vff (otict)
+ B |6/²11 1|
+ VSK 1|
2
SK
SES
Lo
< 22
La + 172 k2222
(TTmxxx + 2²1k)
VSK
24

---

Momentum-Driver Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Further, based on Lemma B.I, we have
E
E
V f(()
-c'
S Σ
1
(c
di)
iES
<
VS(0') 1
N Σ dt+
1 1
Σ
E
(ctt]
Σ
(c
c
S N
N
< Vf(0') N Σ ctt1
+
1
Σ b
| +1
SN
Note that ct = K
>n V : i.e. client i is selected in the 4th round. We have
1
Evr
(0 E..
E
NK
V Ji (0') F V (0!=))
F V (0.+h) - VF
00 el.
c
NK
i.
< 3 110¹
0¹ Tmmxx 1|²
+
3L
Σ E
0 0² 1
30
NK
NK
i,k
3
3 2 max
1,2 + 12?
NK' Vl.
From Lemma D.2, we know that
E c 2/1 <
280
28
"PK2"2+47222
(1+25²
(1+
4N2
K
52
Thus, we have
E| El|ba11 S 2 I.2 m. x +
302 +
280²
+ "3s"
28
"
T2 + 1721.
(1+
4N2
NK
SK
S
S2
4
4N3
310²
28
ST²12 37 max
+ 1
?2
5
53
SK
38
Then, we have
2
E
Σ 30 (1 -)
1311110012 + (0 )de)
53 1212
37 +
4
+
4N3
310²
+ 1+
28
172 x2k213)
5
S3
SK
35
La
+ 2n 2 max
12 +
111
k22
XTmax + {Пイk)
VSK
2) $
B Si7 (V2+ + //3) Tmax =21/
NvN
3130²
E
Σ
30 (1 -
1+
5
s
SK
+ +nKL (
28/3
Lo (2 + +nk)
1 +++/++
(15)
35
2VSK
25

---

Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Plugging (13), (14) and (15) into (12), have
30 VSK
1 8 \v2+v33) / max + 21
NVN
E ||| 5(1 -
-B)
2 ZnBKL+ +
+ B
+7L
+
14
8
31302
288
Lo (2 + +nk)
1+ 3B+
V
+
(16)
SK
35
2VSK
Summing up the above incquality over yields
1
E
S
KLL
+
30
+
B +4 [v22+ 3 Tmax + 22 3
1+
N NNN))
))
T
2T
3TVSK
S
s
3130²
28,3
(2 + +nK))
+
+
nKL
1 / B +
V
+
SK
35
2VSK
D.2. Analysis of डKT Eiese l.. -g
Recall that J'" t.k and g gh+l are respectively updated by Di 3 (Vr (0%%)
ह + + (1 -1))grr and
ge+1 = 33 Eies, (cf-1 - ct) + ce) (1 - 3)g' Then, we have
9 t. g g"+l =B VF @0:- 5 - -c,
3 Σ
(ct - -c,)
S iEs,
+ 3 ( - d - (1 - B) - g6
9 1.8 g
23 A k </ - +
3 Σ
||c
5 iES.
+ 3
d
+ (1 (1-3) 3) g g g'
33 VF
g/
ह + 3
Σ
1|0 4+ cil
i65.
+ 3 Σ
| cill +
1 d+1 - 99
(17)
N
d=
d=
For any i, i, we have
E
gh.
gg - -
c(.k)
K
A
Σ K
E
VF
th g. R
F fé (0R:t) f (0'~))
Ffi
(
F K
1
Σ
VF
0
-|- -1-) )
1 K
Σ VF (
-
1,k :
k
k
< + K Σ 0 0 r²~ri| (Timax + 111 +
L
I
Σ
0
11
+ VK
K
< 20 + nKL + (Tmax + 1)74.
(18)
26

---

Momentum- Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
Moreover, have
B g (+ g'll 3E
Σ
- v -g¹
SES.
Σ
| (0'-1) 3
B
11 + BBI
(19)
$
YES.
From Lemma D.2, for any i E St, have
7
3nKT,+ 27/1 (1+ 2N
E B|lctt1 - c!'l
S 2
+2
(20)
K
3
E V (0') - c s 20
6 K
27
Σ
+
2N 5
+ +2V2nKTT.
(21)
N
Plugging (18), (19), (20), and (21) into (17), we have
1
E
gi k
g ++|
33(20 + nKL (Fmax + 1)L)
K
21 o + 3  + 27 (1+ 2M
7
77
s ))
+ (1 + 22T))
+ 8T4 20
2
_td Σ
+
2N
+2V2nKL + 11;
N
S
SKT E
++1
7 2 K +
-N 2/
GK + 27 (1+ s 2))
$ 3(20 + nnL + r(Tmax + 1]L + (1 + 27)
6 + BF 20
+ 2 Tmax + S
2NV
+ 2222kK
+ NT
Σ - -1--
K
where == 1
NT T..
From (16), we have
7 E
FTmax T
E 3)¹ 1
[ +
30
+ BBTLL
(V22+ /33) Tmax + 2/
1+
NVN
NT
VSK
5
S
31,002
28/3
La (2 + +nK)
+ L + BFV
+ BqFKL
1 1+v/++
+ 1,3g
SK
3S
2VSK
Tmax BnKL +
3Tmaxo TVSK
+ 7B7L
(V2+ + / Fiax + +21
B
1+
NVN
2
S
S
31,02 SK
283
L2(2 + +nK)
+ 7 BF BFV
+ BnFKL
1+ 1Vv+++
+ BT
38
2VSK
27

---

Drrretttu---ivenn Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
D.3. Combination
Let 3
v
SK T
7=
(SK)
and
KVT we have
T
T-1 1
S 7h B
31,8²
Lo (2yTxxx + (()
T t=
Σ
E
+
2 +
SK
+
2VSK
mmax T(SK)*
VI.TTmux + VTa (SK))
(SKT)
73
(SKT)
(SKT)
Similarly, we have
E
9
t.k
g"
SKT
iES
Bo
1
7
+
B
Σ
B
VK
NT
7
SK
(SK)
F(SK)*
(SK) $
max
L
(
VTa)
LoTmax
K
T
T
T
T
Then, we have
Σ
|1
77 T Σ
A
+
2 T-1
B B|
2
Σ E
9i
1.k
9
1-1
+ 7L
SKT
t=
iES..k
+ L VLo
SK
5
+oV
+
+ +
(SKT))
T
(SK)
T
+ Tmax L (SK)#
(SK)
+ FTmax L (SK)
+ TV LoTTaxx
T
T
T
Lemma D.2. Assume that the delay of client at the lth round is Th. For any 1, E S₁ we have
i) E Bl|cttt c!(1² s
28a² K
+
12 + + (1+ 4N² 52
28
3
ii El|ctt
- cfll s 2 tor + 2 / + 22 (1+ +N);
i ( ct+1|| < 20 v _ + 2 (2, N +
2N 5
+ 2V22KL
Proof. Define : = E V. (t
- -cttil??
Since for any t, the elements in S, are uniformly sampled from
(1,... N}, we have
c
if S, (w.p. 1 ) if S, (w.p. $).
1
E. VF
28

---

Momentum-Drivee Adaptivity; Towards Tuning-Free Asynchronous Federated Learning
Using Young's 's inequality repeatedly, we have
0. - 1
S
E
V fe
0 (0~
of +
S E N
Vi (0-T)) VF
K
1
S
E
V.
0 7! (0
F Vli 00 (0-
c 2
+ N
S
20²
+
21.²
Σ
0
0z 11)
N
K
K
IA
S
E
1
+
5
$ $1-1 +
1+
2N
2²12
+
25
02
+
3
N
2N/
S
N
K
S
2N
2 2T?
2$
0²
3" 1k
+
2N
S
N
K
S
1N
TT,
+
25
0²
3"
1
Σ
1-1
1
S
2N
S
N
K
2N
0=
S
NN2
+ 0²
Φ +
+4
L22
+ 3"
2N
5
K
Since c.- R 2k=
1
AF (00 (TTT)) we have
1
S
E
f (0)) - <011² + N
S
f (0
- 1 Σ
VF
(0 5
N
K
k
S
0²
25
L''B 00 - 0g + 0²
1
K + N
N
K
S
0²
28
|+
+
22322
N)
K
3N
20 +
25
"²² T2
K 3N
Then, we have
202
28
n 12 ) (1- S
N2
0²
+
+4
L2
+
+
K
3N
2N
K
60²
4N2
2n 12L2
22 Vi,t.
(22)
K
52
Since i E St, we have c+11
Σn
VF k Then,
K
E
Ellct +1
=
E
Σ
VF
F Vii (0!+)) F Vi (D-TT) F VVJ (0- - ct
K
<
40² 2
412
Σ
E
+ 41,2 01-
| - _ . + 4F 7. (//
K
K
2
4
<
23 + 4,2 + -
(23)
K
Plugging (22) into (23), we have
2
E
F
0 c(+))
-c(
280²
+ "
28
L2 +47212
(1+
4N2
K
K
3
5²
52
29

---

Nomentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
which proves i). Moreover, based the concavity of function (+)2, taking square root the both sides of x) directly yields ii that
22 1
E
V 0 (0,= -.
c/
I E
VF
(0 g/.))
)
cf
K k
7
z + 27 (1+ 2N
s 2
+ 2/ 3
K
5
Further, we have
-0'0
5
1 N
Σ
E
V (00) - I
2
Σ
E vf. (0") V. (0'
ΣE Vf. 0 (0 c, 1+1
N
2
Σ
+
+
2 N
Σ / /
N
2 K
6
2
Σ
+
2N
+
+222nKK.
N
5
E. Additional Numerical Results
E.1. Simulation Setup
Tasks and Networks. We evaluate the performance of our algorithms on the image classification task with two real- world dateset: CIFAR-10 (Li et al., 2017) and FMNIST (Xiao et al., 2017). For FMNIST, utilize convolutional neural network (CNN) consisting of three convolutional layers and two fully connected layers. For CIFAR-10, we adopt ResNet-18 architecture.
Federated Setting. Our experiments consider a federated learning system with N = 100 clients cooperating to train a shared model. At each global communication round, a fraction of 0.1 clients are randomly selected to participate, resulting in S = 10 active clients per round. Each selected client trains locally for epochs with a batch size of 100 using stochastic gradient descent (SGD) as the optimization algorithm. These settings are consistent across all experiments unless otherwise stated.
Data Heterogeneity. To evaluate the robustness of our algorithms under varying data distributions, we consider both i.i.d. and non-i.i.d. data settings. For the i.i.d. case, data samples are uniformly distributed across the clients. For the non-i.i.d case, we simulate realistic data heterogeneity using a Dirichlet distribution Dir(a). Specifically, we set a = 0.5, where smaller a values correspond to higher degrees of non-i.i.d distribution.
Asynchronous Setting. We simulate asynchronous environments using FedBuff (Nguyen et al., 2022) as the baseline framework. The concurrency level set to M. 200 meaning that the server can aggregate results from up to 20 clients concurrently. The delay time for each client is sampled from uniform distribution (100, Tmax). where Tmax 20 seconds by default. The delayed communication round correlates with the concurrency M Specifically, when M. = 20, the average delay Tave 0.9184, and the maximum delay Tmax = 4, as analyzed in CA'FL. We run all experiments for a total of T 600 global communication rounds.
Baselines. We compare our proposed algorithms against two state-of-the- asynchronous federated learning baselines: CA3FL (Wang et al., 2023) and FADAS (Wang et al., 2024c). For the main results, we adopt the hyperparameter settings recommended by their respective papers. In cases where these settings fail under challenging asynchronous conditions, we adjust them appropriately to ensure functionality.
E.2. Additional Results
30

---

Momentum-Driie Adaptivity: Towards Tuning-Free Asynchronous Federated Learning
2.5
CA'FL RADAS
2.5
CA-RL
FADAS
MasFl
2.0
AdaMasFL
AdaMasiL
1.5
1.5
L05
1.0
1.0
0.5
200
500
100
200
Communiication round
Communication round
(a) Li.d. CIFAR-10 dataset
(b) Non-i..d. CIFAR-10 dataset
2.5
CMFFL
2.5
CAHIL
2.0
MasFL
2.0
MasFL
AdaMasFI
AdaMasFF
0.5
0.5
0.0
0.0
100
200
300
400
500
600
100
200
300
400
500
600
Communication round
Communication round
(c) Li.d. FMNIST dataset
(d) Non-i.i.d. FMNIST dataset
Figure Test loss versus communication round different datasets with i. i.i.d/non-i.i.d. data.
2.5
CA-FL
2.5
CA-FL
FADAS
FADAS
MasFL
MasFL
AdaMassL
AdaMasFL
1.5
1.5
1055
Loss
1.0
1.0
200
300
200
500
Communication round
Communication round
(a) M₁ = 30
(b) M. = 40
2.5
CA/FL
2.5
CA'FL
FADAS
FADAS
2.0
MasFL
MasFL.
AdaMasFL
AdaMasFL
1.5
1.5
Lo5s
Loss
1.0
1.0
0.5
200
300
200
560
Communication round
Communication round
(c) M, = 60
(d) M, = 100
Figure 5: Test loss versus communication round non-i.i.d FMNIST dataset under varying levels of asynchrony.
31

---

Momentum-Dricee Adaptivity: Towards Juning-Free Asynchronous Federated Learning
0.9
0.9
0.8
0.8
0.7
0.7
Accuracy
Accuracy
0.5
0.5
0.4
AdaMasFL
0.4
AdaMasFL
MasFL (AdaMasFL w/o norm)
MasFL (AdaMasFL w/o norm)
0.3
AdaMasFL w/o control variate
0.3
AdaMasFL w/o control variate
MasFL w/o control variate
MasFL w/o control variate
0.2
0.2
MasFL w/o momentum
MasFL w/o momentum
100
200
300
400
500
600
100
200
300
400
500
600
Communication round
Communication round
(a) CIFAR-10 10 dataset
(b) FMNIST dataset
Figure 6: Test accuracy versus communication round for ablation studies on non-i.i.d CIFAR-IO/MNIIST dataset.
0.95
0.95
0.90
0.85
0.85
Accuracy
Accuracy
0.80
0.80
0.75
0.75
0.70
0.70
0.65
FADAS
0.65
FADAS
AdaMasFL
AdaMasFL
0.60
0.60
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Momentum parameter &
Momentum parameter B
(a) Non-i.i.d CIFAR-10 10 datasct
(b) Non-i.id. FMNIST dataset
Figure 7: Test accuracy compared with baselines using momentum under different momentum parameter 3.
32


Reviews:
[{"review_id": "sl495L5Czv", "reviewer": "Reviewer_3Kyd", "summary": "Previous works on asynchronous federated learning put strong assumptions (like bounded gradient assumption) in order to get theoretical guarantees. However, these assumptions are usually not realistic. In this paper, the authors propose a new asynchronous FL algorithm which novelly combines with global and local momentum. Due to the use of momentum, the authors remove the needs of strong assumptions in convergence analysis. Furthermore, they also design an adaptive version, which allows auto learning rate tuning. Experiments validate the effectiveness of proposed algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments.**\n\n**Response to Comments Or Suggestions:** \n\nThanks 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:\n\n> 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.\n\nIn response to the reviewer's suggestion, we will include experimental comparisons of our work with [1] in the revised version.\n\n\n\n**Thank you once again for your thoughtful review and constructive feedback.**", "claims_and_evidence": "The authors claimed that they propose two novel training approaches MasFL and AdaMasFL. These algorithms incorporates two-level momentum. They provide not only theoretical guarantees with weaker assumptions but also experimental results to show advantages. Overall I think these claims are solid and well supported.", "methods_and_evaluation_criteria": "The authors provide a standard convergence analysis to analyze their proposed method.\n\nThe benchmark datasets in experiments are cifar and fmnist, which are relatively small.", "theoretical_claims": "I didn't check full details.", "experimental_designs_or_analyses": "Yes, the designs and analyses look good.", "relation_to_broader_scientific_literature": "This paper may make asynchronous FL algorithm to be more practical and powerful. The analysis technique of two-level momentum may be also interesting to some readers.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "In the paper \"Yu et al. Momentum approximation in asynchronous private federated learning.\" they also propose a method to improve async FL. The authors should also compare experiments with this paper.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sEJACPE72I", "reviewer": "Reviewer_jC6k", "summary": "This paper addressed the data heterogeneity and staleness in asynchronous federated learning (AsycnFL). The authors propose MasFL that introduces the control variates into AsyncFL to stabilize the model updates during local training and global aggregation. Further, they normalize the momentum-averaged gradients in local model training to eliminate the need for trial-and-error tuning or problem-parameter, e.g., the number of participating clients $S$, local update iterations $K$, and communication rounds $T$. The theoretical analysis is thorough, and the experimental results are promising, showing improvements over the state-of-the-art methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.**\n\n**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.\n> 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.\n\nHowever, 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.\n\n[1] Yu, T., Song, C., Wang, J., and Chitnis, M. Momentum approximation in asynchronous private federated learning. arXiv preprint arXiv:2402.09247, 2024.\n\n**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.\n\nThat 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. \n\n\n**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).\n\nWe 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:\n\n- At any given time, there are a total of $M_c$ clients perform local updates concurrently;\n- Each client's execution time is sampled from a uniform distribution;\n- These varying execution times naturally create different delays in global aggregation participation;\n- Global aggregation occurs simultaneously with local updates.\n\nThis design aligns with the virtual clock setting proposed in [b] to captures the realistic scenario of heterogeneous client completion times and asynchronous aggregation.\n\nWe appreciate this feedback and will incorporate these important implementation details into the main paper for better clarity.\n\n**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.\"\n\n\n**Thank you once again for your thoughtful review and constructive feedback.**", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "One highly-related work [a] was missing. \n\n[a] Cheng Z, Huang X, Wu P, et al. Momentum benefits non-iid federated learning simply and provably[J]. arXiv preprint arXiv:2306.16504, 2023.", "other_strengths_and_weaknesses": "**Strength**\n- **High Writing Quality**. The manuscript is well-organized and easy to read.\n- **Technical Advantage**. The authors first introduce the control variates into AsyncFL to tackle the challenges of data heterogeneity, gradient staleness,  and complex hyperparameter tuning. Compared with another similar technique Scaffold, the authors additionally consider the global momentum to stabilize the model updates during model aggregation, improving the FL system's robustness to the stale clients in the context of asynchronous aggregation. Both theoretical and experimental results confirm the effectiveness of this strategy.\n- **Theoritical Contribution**. The paper provides strong theoretical guarantees for both MasFL and AdaMasFL. The convergence analysis is detailed, and the authors successfully prove that their methods achieve state-of-the-art convergence rates with linear speedup concerning the number of participating clients and local updates.\n\n**Weakness**\n- **Overstatement**. The claim that AdaMasFL \"completely eliminates the need for tuning-free convergence\" might be overstated. While the theoretical framework provides explicit hyperparameter settings, practical implementation might still require adjustments based on system-specific factors.  In addition, the claim \"tuning-free AFL approach\" also suffers the risk of overclaiming since tuning the learning rate led to different empirical results as evidenced by the experiments. The authors should temper this claim and discuss the practical implications of their theoretical results.\n- **Issues on Experiment Settings**. The authors conducted experiments by directly assuming the degree of round-wise delaying of clients, which eliminated the necessity to consider the aggregation addition of clients (e.g., every $K$ arrivals in FedBuff). This issue also prevents a more practical setting that uses a virtual clock [b] to conduct asynchronous experiments. It's recommended to clarify the practical aggregation conditions of the proposed methods.\n- **Missing Related Work**. One important related work was missing. Although this work conducted the convergence of synchronous FL, **they are the first to remove the dependency on the assumption of bounded data heterogeneity (i.e., bound gradient dissimilarity)** and also confirm the impact of control variate in Scaffold. Since the main theoretical contribution of this work lies in removing the dependency of convergence on bounded data heterogeneity assumption and uses similar control variates, the authors should discuss their contributions and the relationship of this work to it. \n\n\n[a] Cheng Z, Huang X, Wu P, et al. Momentum benefits non-iid federated learning simply and provably[J]. arXiv preprint arXiv:2306.16504, 2023.\n\n[b] Lai F, Dai Y, Singapuram S, et al. Fedscale: Benchmarking model and system performance of federated learning at scale[C]//International conference on machine learning. PMLR, 2022: 11814-11827.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please see the weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ps5PuyW3Qv", "reviewer": "Reviewer_uM33", "summary": "This paper studies asynchronous federated learning and proposes a novel momentum-driven asynchronous FL framework that eliminates the need for data heterogeneity bounds. The authors provide theoretical analysis and conduct experiments to verify the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.**\n\n**Reply to Methods And Evaluation Criteria:**\n\n1. The asynchronicity of our method is reflected in the following two aspects:\n- **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. \n- **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.\n\n**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. \n\n2. (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.\n\n3. 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. \n\n**Reply to Theoretical Claims:**\n\n1. 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: \n- 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. \n- 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.\n\n2. 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.\n\n[1] Lian, Xiangru, et al. *\"Asynchronous parallel stochastic gradient for nonconvex optimization.\"* NIPS 2015.\n\n**Reply to Experimental Designs Or Analyses:** \n\n1. Our implementation simulates practical asynchronous conditions using FedBuff's delay mechanism to account for varying client arrival times. Specifically:\n- At any given time, there are $M_c$ clients perform local updates concurrently;\n- Each client's execution time is sampled from a uniform distribution;\n- These varying execution times naturally create different delays in global aggregation participation;\n- Global aggregation occurs simultaneously with local updates.\n\n    This design captures the realistic scenario of heterogeneous client completion times and asynchronous aggregation.\n\n2. $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.\n\n3. 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. \n\n**Thank you once again for your thoughtful review and constructive feedback.**", "claims_and_evidence": "I think the claims in the submission are mostly clear.", "methods_and_evaluation_criteria": "1. I am wondering how asynchronicity is reflected in the proposed algorithm. In line 3 of Algorithm 1, the server randomly selects a set of clients  $S_t$ , and in line 7, the aggregation also happens within this set  $S_t$. This suggests that the clients in  $S_t$  participate in the update within the same round, which seems to contradict the asynchronous scheme where clients update at their own pace. Although Algorithm 2 includes notations related to delay  $\\tau_i^t$, I believe this represents a semi-asynchronous approach. While clients may start from different global models, the server still waits for all aggregated information before proceeding.\n\n2. Moreover, I am wondering whether the unbiasedness of the two-level momentum still holds when the correction term includes asynchronous delay (a similar issue arises regarding the sampling set $S_t$). \n\n3. I think the proposed methods incur extra implicit memory on both the server and clients, i.e., the server need to maintain each clients' correction term $c$, and the client also need to maintain one copy of correct term $c$.", "theoretical_claims": "I have reviewed all the theoretical results in the main paper and briefly examined the theoretical results in the appendix. I have several questions regarding this:\n\n1. Why is the left-hand side of Theorem 3.1 different from that of Theorem 4.1? What is the reason for using both $||\\nabla f(\\theta^t))||^2$ and $||\\nabla f(\\theta^t))||$ when presenting the convergence rate?\n\n2. I think the constraint on the learning rate  $\\eta$  in Theorem 3.1 is not convincing. When the delay is large, e.g., $\\tau_{\\max} \\geq \\sqrt{T}/\\sqrt{SK}$, the numerator in the constraint on $\\eta$, i.e., $T - 4SK\\tau_{\\max}^2 < 0$ becomes negative, making the square root term undefined. Moreover, other related theoretical analyses on asynchronous FL, such as CA2FL and FADAS, do not include such a \"minus term\" in their learning rate conditions.", "experimental_designs_or_analyses": "1. How was the asynchronous delay simulated/achieved in the experiments? \n2. What does $M_c$ represent in the experiments? Does $M_c$ control the asynchronous delay, and does it share a similar concept with  $S$ in your experiments?\n3. I think providing more ablation studies on how the degree of asynchronous delay affects the proposed method would be helpful in verifying its effectiveness.", "relation_to_broader_scientific_literature": "This paper may contribute to the privacy-preserving related machine learning applications.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: \n1. The empirical results seem convincing.\n2. The paper is well structured and easy to follow. \n\nMost Weaknesses have been discussed in previous sections, particularly about the theoretical claims, the method, and the motivation.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please refer to previous sections. Addressing the issues in previous part would help me better understand and potentially change my evaluation of the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fmKIYjizjF", "reviewer": "Reviewer_mYF9", "summary": "This paper propose to adopt the server-client momentum with variance reduction technique in the Async FL framework. By using VR technology, the proof eliminates the heterogeneity assumption while maintaining the same efficiency as sync FL such as SCAFFOLD. The experiments validate the algorithm's efficiency in terms of test accuracy.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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.**\n\n**Reply to Methods And Evaluation Criteria:**\n\n1. Thank you for your comment. Our work advances asynchronous federated learning (AFL) in the following key ways:\n\n- **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.\n- **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.\n\nThese contributions go beyond combining existing techniques and addressing key challenges in AFL.\n\n2. 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. \n\n**Reply to Theoretical Claims:**\n\n1. 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. \n\n2. We sincerely thank the reviewer for pointing this out. We have removed the reference to the FedAvg algorithm in line 271.\n\n**Reply to Experimental Designs Or Analyses:**\n1. 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.\n\n2. 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.\n\n3. 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. \n\n4. 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.\n|Dataset  |Heterogeneity|CA$^2$FL|FADAS|MasFL|AdaMasFL|\n|-|-|-|-|-|-|\n|CIFAR-10|iid|3485|4171|2033|2323|\n||non-iid|12593|9372|6679|5333|\n|FMNIST|iid|1975|1238|832|394|\n||non-iid|2311|1943|1067|514|\n\n**Reply to Questions For Authors:**\n\n1. Thanks for pointing this out! $\\sigma_h$ should be $\\sigma_g$ defined in eq. (1), which characterizes the level of data heterogeneity. \n2. 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.\n\n**Thank you once again for your thoughtful review and constructive feedback.**", "claims_and_evidence": "The theoretical proofs are complete, but the experiments are insufficient, lacking sensitivity studies on multiple variables and comprehensive ablation experiments. There is also no use of methods such as changing random seeds to verify robustness. For specific details, refer to 'Experimental Designs Or Analyses‘.", "methods_and_evaluation_criteria": "1. The approach has some originality, but its novelty is not high. Both server-client momentum and variance reduction techniques like scaffold have been widely studied. The approach adopts in this paper combines these two methods within the asynchronous FL framework without making significant modifications.\n\n2. AdaMasFL requires to communcate an extra variable $\\Delta$, this will increase the communication overhead.", "theoretical_claims": "1. In theorem 3.1, the selection of momentum coefficient $\\beta=\\sqrt{SK/T}$ is not a constant. This usually does not occur in previous algorithms, because the number of training rounds $T$ can approach infinity, which also means that $\\beta$ will consequently approach 0. This condition is stronger than previous methods.\n\n2. The description in line 271 is inaccurate. On the general assumptions, the original FedAvg cannot achieve the full acceleration bound under partial participation, as discussed in reference [1]. The full acceleration bound $O(1/\\sqrt{SKT})$ depends on variance reduction or additional bounded gradient assumptions. The related description needs to be revised and further discussed.\n\n[1] Achieving linear speedup with partial worker participation in non-iid federated learning", "experimental_designs_or_analyses": "1. The experiments are partially tested on FMNIST and CIFAR10 on ResNet-18, with some improvements on the test accuracy, but there is a lack of systematic experiments to validate the findings. There is insufficient experimental validation for related variables, such as different local length $K$, data heterogeneity levels, and the duration of delay $\\tau_i$. According to the description on page 29, most of the hyperparameters are selected as fixed values without additional sensitivity experiments, etc. I recommend that the authors conduct further extensive ablation experiments to determine the robustness of the proposed algorithm.\n\n2. An experiment for a core variable is missing. One of the core contributions of this paper is the use of momentum-based weighting at both the server and client ends. Therefore, ablation experiments related to this scheme are essential. Necessary experiments, such as the benefits brought by only local momentum, global momentum, or variance reduction, should be included in the main text.\n\n3. The experiments related to $\\beta$ are missing. As an important hyperparameter, $\\beta$ should be tested to determine the range in which it is effective. Although the theory sets it to be related to $T$, the practical role of $\\beta$ in the experiments is still unclear.\n\n4. The authors need to include a table to report the communication bits and wall-clock time of all methods in the baselines.", "relation_to_broader_scientific_literature": "It is helpful for the design of asynchronous federated learning frameworks.", "essential_references_not_discussed": "The discussion is sufficient.", "other_strengths_and_weaknesses": "Other strengths:\n\nTable 1 presents the convergence complexity and detailed conditions, which is great as it allows one to easily see the source of theoretical progress and the additional assumptions. Although the choice of $\\beta$ depends on $T$ rather than being a constant, which makes the theory somewhat thin, the corresponding conclusions are still very clear in the comparison shown in Table 1.", "other_comments_or_suggestions": "see above for more details", "questions_for_authors": "Main issues seen above.\n\n1. What's the meaning of variables in line 153, e.g. $\\sigma_h$? I did not see the relevant definition.\n\n2. Can $\\beta$ be set as a constant? If so, what effect does it have?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel algorithm for federated learning with asynchronous adaptive updates. The algorithm integrates local and global momentum, along with control variates, giving convergence results in the asynchronous setting that do not rely on data heterogeneity-related bounds. After rebuttal, all the reviewers are on the positive side. 

A weakness of this work is that it appears to be a combination of multiple known techniques. It would be helpful if the final paper can highlight the novel and non-obvious technical and mathematical steps that are key to obtaining the solution.
Decision: Accept (poster)