FedQS: Optimizing Gradient and Model Aggregation for Semi-Asynchronous Federated Learning
Authors: Yunbo Li
Jiaping Gui
Zhihang Deng
Fanchao Meng
Yue Wu
Venue: NeurIPS 2025 poster ()
Keywords: Semi-Asynchronous Federated Learning
Aggregation Strategies
Convergence Analysis
Primary area: general_machine_learning

Abstract: Federated learning (FL) enables collaborative model training across multiple parties without sharing raw data, with semi-asynchronous FL (SAFL) emerging as a balanced approach between synchronous and asynchronous FL. However, SAFL faces significant challenges in optimizing both gradient-based (e.g., FedSGD) and model-based (e.g., FedAvg) aggregation strategies, which exhibit distinct trade-offs in accuracy, convergence speed, and stability. While gradient aggregation achieves faster convergence and higher accuracy, it suffers from pronounced fluctuations, whereas model aggregation offers greater stability but slower convergence and suboptimal accuracy. This paper presents FedQS, the first framework to theoretically analyze and address these disparities in SAFL. FedQS introduces a *divide-and-conquer strategy* to handle client heterogeneity by classifying clients into four distinct types and adaptively optimizing their local training based on data distribution characteristics and available computational resources. Extensive experiments on computer vision, natural language processing, and real-world tasks demonstrate that FedQS achieves the highest accuracy, attains the lowest loss, and ranks among the fastest in convergence speed, outperforming state-of-the-art baselines. Our work bridges the gap between aggregation strategies in SAFL, offering a unified solution for stable, accurate, and efficient federated learning. The code and datasets are available at https://github.com/bkjod/FedQS_.

FedQS: Optimizing Gradient and Model Aggregation for Semi-Asynchronous Federated Learning
Yunbo Li", Jiaping Gui't, Zhihang Deng, Fanchao Meng, Yue Wu', School of Computer Science, Shanghai Jiao Tong University, Shanghai, China (li-yun-bo, jgui, dzh1227, mactavishmeng, wuyue) edu, on
Abstract
Federated learning (FL) enables collaborative model training across multiple par- ties without sharing raw data, with cemi-asynchronos FL (SAFL) emerging as a balanced approach between synchronous and asynchronous FL. However, SAFL faces significant challenges in optimizing both gradient-base based (e.g.. FedSGD) and model-base based (e.g., FedAvg) aggregation strategies, which exhibit distinct trade-offs in accuracy, convergence speed, and stability. While gradient aggregation achieves faster convergence and higher accuracy, it suffers from pronounced fluctuations, whereas model aggregation offers greater stability but slower convergence and sub- optimal accuracy. This paper presents FedQS. the first framework theoretically analyze and address these disparities in SAFL. FedQS introduces divide-ane iivide-and--a conquer strategy handle client heterogeneity by classifying clients into four distinct types and adaptively optimizing their local training based on data distribu- tion characteristics and available computational resources. Extensive experiments computer vision, natural language processing, and real-world tasks demonstrate that FedQS achieves the highest accuracy, attains the lowest loss, and ranks among the fastest in convergence speed, outperforming state-of-the-ar baselines. Our work bridges the gap between aggregation strategies SAFL, offering a unified solution for stable, accurate, and efficient federated learning. The code and datasets are available at Ihttts: //tthtttttuut//ee/ com/bkjod/Feddp
Introduction
Federated learning (FL) has emerged as promising paradigm for enabling multiple parties to collaboratively train a shared model without sharing their raw local data
5 6
7
FL
has found widespread applications in domains such as healtheare B
9 10 and finance
B
Among various FI. communication modes, semi-asynchronous FL. (SAFL) strikes balance between synchronous FI. and fully asynchronous FI., offering flexible trade-off between model consistency, training latency, and resource utilization [14] 16 17]. In SAFL, devices operate independently with
partial coordination, for instance, through buffered updates [16] or clustered synchronization [18), making it adaptable to heterogeneous network conditions and device capabilities in real-world
deployments [19
FedSGD
FedAvg
Despite its advantages, designing an effective SAFL sys- tem presents significant challenges. particularly in select- ing an appropriate aggregation strategy. Recent empirical studies (21 reveal that gradient-based aggregation (e.g., FedSGD 1 in SAFL achieves higher accuracy and faster convergence but suffers from severe fluctuations, whereas
231
40
llpech
Epech
Figure FedSGD vs. FedAvg in SAFL.
'Equal contribution. Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

model-based aggregation (e.g., FedAvg ( offers stability at the cost of slower convergence and reduced accuracy. Figure T shows the distinet performance of these strategies when training ResNet- 18 on CIFAR-10 in SAFI. While existing SAFI. research has focused on straggler mitigation [22], client drift 23),, resource heterogeneity [19], and client selection (24] the critical differences between aggregation strategies remain understudied.
Optimizing both gradient and model aggregation in SAFL faces three key challenges: 1) Lack of Theoretical Understanding: Current analyses of aggregation discrepancies (2l] are empirical, lacking theoretical foundations to guide solution design. 2) Inherent Aggregation Disparity: In neural network training, the loss function defines a mapping [25 26 from the parameter space to the loss space. Gradient aggregation computes first-order derivatives of this mapping, capturing both the direction and magnitude of the local updates in the loss space. In contrast, model aggregation operates directly on the parameter space, which hardly maintains clear correspondence with the loss space due to the lack of linearity or convexity conditions in loss functions-assunpiee assumptions rarely satisfied in deep neural networks. 3) Server- or Client-Centric Limitations: Existing approaches are predominantly server-centric, relying on a single aggregation method, while client-centric methods struggle with insufficient global information.
To address these challenges, we propose FedQS, the first framework that optimizes both gradient and model aggregation in SAFL. Our key insight that stale updates and data heterogeneity empir- ically induce distinct continuity in the optimization trajectories of different aggregation strategies. Building on this observation, we introduce a divide-and-con and-conquer strategy that classifies clients into Setttntl--riasseee
Fast-and- Bast-and-Weakly Weakly-Biased, Straggling-bur Seng-but-Waaad four types Strongly Strongly-Biased) and adapts their training strategies dynamically. We provide a Straggling-ang Sangling--nn-Strooeee formal convergence analysis of FedQS, proving that it achieves exponential convergence rates under both aggregation strategies. Our theoretical results demonstrate that FedQS addresses two key limita- tions in SAFL: the convergence instability of gradient aggregation and the suboptimal convergence capability of model aggregation.
and
We evaluate FedQS on computer vision (CIFAR-10), natural language processing (Shakespearee, and real-world data (UCI Adult) tasks. Results show that FedQS consistently outperforms ofth-atft baselines. Compared to the foovern- model aggregation and gradient aggregation baselines, FedQS improves average accuracy by 38. 98% and 5.65%, respectively, while reducing training time by 58.85% and 3.68%. Against the highest-precision baselines, FedQS achieves 15.74% and 12.93% faster convergence (in rounds) and reduces training time by 72.63% and 48.04%, respectively. Ablation studies validate the impact of each module, while hyperparameter and system setting analyses demonstrate FedQS's robustness. Our work bridges the gap between theory and practice in SAFL, offering a principled approach to harness the strengths of both aggregation strategies.
2 Background & Motivation
Limitations in Existing SAFL Aggregation Methods. Existing studies in Semi-Asynchronous Federated Learning (SAFL) predominantly focus on optimizing either gradient aggregation or model aggregation, but not both. For gradient aggregation, prior work has addressed challenges such as
model convergence [5] techniques (e.g., momentum
15
optimal aggregation frequency (28] 29). and advanced optimization
For model aggregation, solutions target the straggler problem [31 32 incorporates both gradients and models, it ultimately adopts model
18 19]. While AAFL
aggregation, using gradients only as auxiliary validation signals. To our knowledge, only [21] empirically compares gradient and model aggregations but offers no mitigation for their performance gap. In contrast, we propose unified optimization framework with theoretical guarantees.
Federated Learning Basics. FL involves a server S and clients C = (Ci, C2,..., CN The server S maintains global model Wg. while each client C, trains local model wy on its dataset De (with n; samples). The goal is to minimize the global loss: min F F(wy) A 1 E (w;). where F;(.) is the local objective. Clients access stochastic gradients [F Ex.j) for each data sample εx,- E D,.
N
Synchronous vs. Semi-AAyynchoonus FL. Synchronous FL is based on server-coordinated training where only activated clients upload their local updates in one global epoch with others idling. In contrast, clients in SAFI. train autonomously and push updates asynchronously, with aggregation triggers upon conditions (c.g., sufficient updates (15)) at the server.
2

---

Aggregation Strategies. In Synchronous FL, for gradient aggregation, during the (t + 1)-th global epoch, the server updates w' by gradient descent via aggregated gradients from activated client set S: w w/J ng Eies 2s V (w.)), where (w,) & Σe= Fu D,) and represents n local training epochs. For model aggregation, the server averages local parameters directly: w/tt Eies Th wt. However, SAFL, staleness arises in the local updates as client C2 may use an outdated global model w (rf S t) for local training, leading to divergent optimization trajectories.
Key Observations. Inspired by empirical re- sults (1,, we identify two factors that cause per- formance gaps in SAFL.: Stale Updates (Factor 1) and Data Heterogeneity (Factor 2). Staleness affects the continuity of global optimization tra- jectories differently in gradient and model aggre- gation. Gradient aggregation preserves continu- ity by performing gradient descent on the latest global model w ? where stale gradients only influence the current update direction and mag- nitude. In contrast, model aggregation averages stale parameters directly, resetting the trajectory and disrupting the optimization continuity the loss landscape. However, under Independent and Identically Distributed (IID) settings, stale updates exhibit limited divergence all clients optimize identical local objectives derived from the identical data distributions. Conversely, non-lID data distributions exacerbate this issue, since increased local training rounds amplify local-global deviation (33] and semi-asynchronous updates bias the server toward frequent updaters [15] in such distributions. In gradient aggregation, this bias leads to over-optimization on dominant clients' data distribution; in model aggregation, the global model retains more information from frequent clients, restarting optimization from a skewed initial point. These dynamics exacerbate the performance gap between the two strategies in SAFL.
Table I: The average best accuracy and correspond- ing differences between two aggregation strategies under varying influencing factors.
Activated Factors
Average Best Acc. (%)
Gradient Aggregation
Model
Gap (%)
Factor
Factor 2
Aggregation
90.93
91.05
0.12
90.73
90.51
0.22
86.79
87.29
0.50
82.63
71.11
11.52
All experiments involve training ResNet- 18 CIFAR: 10 across three independent runs. Q indicates the absence of factor, while indicates presence.
Empirical Validation. We conducted experiments training ResNet-18 on CIFAR-10 with 100 clients. The results show that when both factors are active (i.e., SAFL + non-IlI)), the accuracy gap between gradient aggregation and model aggregation surges to 1 11.52%. Table shows detailed results.
This paper proposes FedQS, novel framework that enables clients to select optimal local training modes autonomously by quantifying staleness (by update speed) and heterogeneity (by update similarity), compatible with two aggregation strategies.
Design of FedQS
3.1 System overview
As shown in Figure 2 Fedos consists of three modules: the global aggregation estimation module (Mod@), the local training adaptation module (Modı)), and the global model aggregation module (Mod@). The first two modules are deployed on clients, while Mod is deployed on centralized server. The goal of Mod@ to empower each participant to ascertain the approximate gradient update of the global model, which is utilized to compute the gradient update similarity between the server and the client. Since Mod@ operates independently of the transmitted data required for global model updates, it facilitates the integration of various aggregation strategies. The goal of Mod is to adapt each client to different training mechanisms based on its data distribution and available training resources. This module alleviates the impact of local heterogeneity on the global model, addressing issues such as unstable convergence and sluggish convergence speed. Meanwhile, the goal of Mod is to selectively weigh local updates for global aggregation through feedback mechanism, thereby tackling the challenge of low accuracy under the model aggregation strategy.
'QS denotes Quadrant Selection. We also use the meaning of QS rankings to refer to the sell-evaluation mechanism in FedQS.
3

---

Modiy
M Local Training Adaption
Modg
Glsbal Agpregation Estimation
Global Medel Agarogation
Eoraet Sorte Iekeuuke
Server
Clika Markd
Chass
Fedktnck Sanal Stadirrty inlemate
pplate Aggargarrnnnn Aagrggiiin Statin Takl
A
Weightdd Appregatios
*
Excdl Grodied
Trokiing
(Habd or Credens))
Leculanndall
Bisuiisate Inforatiin
Thet Bher Stiten Ithenatenn New
Figure 2: Workflow of FedQS, featuring clients with diverse resource capabilities. In FedQS, during a global training round, Mod first utilizes the global model distributed by Mod to compute pseudo- global gradients and sends them to Mod Then, Mod employs the information disseminated by Mod as input when determining a local training strategy and leverages the global model from Mod as the starting point for local training. Finally, Mod uses the local update data from Mod for global aggregation and leverages the similarity information from Mod to update the global state table.
3.2 Global aggregation estimation (Mod@)
Existing SAFL solutions typically leverage information (e.g., from historical local gradients [15] uploaded by clients to facilitate global model aggregation. A key problem within these solutions is that they are proposed from the server's perspective, resulting in a design tightly coupled to a specific aggregation strategy. To address this problem, we introduce Mod@ within FedQS to ensure compatibility with both aggregation strategies. Specifically, Mod@ enables each participant to acquire global aggregation information during the local training phase from the perspective of local clients. To do it, M first stores the latest two global models locally and then adopts the existing approach [16 20 to derive a pseudo-global gradient T.g (wi) by comparing two consecutive global models, i.e., (wy) = w/ w
This pseudo-globas gradient contains information about the global update within the current round. We then compute the local-globe gradient update similarity st on each client by comparing the latest local update gradient and the derived pseudo-ge global gradient, utilizing a similarity function such as cosine similarity. A larger of suggests that this client's 's updates in the current round are more aligned with the global update and vice versa.
3.3 Local training adaptation (Mod@)
Mod aims orchestrate heterogeneous clients and enable each client to adaptively train its local model, facilitating the optimization of global model aggregation in Mod A key strength of Mod lies in its ability to enable clients to dynamically adjust their local training strategies. There are two key benefits associated with it: (1) During the initialization phase, the server does not require prior knowledge (e.g.. performance distribution) of clients. This contrasts with existing algorithms (e.g., FedAT [18] and FedMDS [9)), which rely on such prior knowledge for hierarchical client classification. (2) Given that the local information is processed and shared with the server in real-time, Mod@) can handle dynamic FL. environments where the performance (e.g., available resources) of individual clients may vary during training.
(L.I
SWBC
FWBC
7 Ff
&
SSBC
FSBC
ft < J' Rst < ft J &
Figure 3: Categorization of clients in Mod
Specifically, @od adopts a divide-and-conquer strategy to categorize clients into four types, cor- responding to the four quadrants in Figure 3 Mod leverages the local update speed f and the local-globe goooal gradient update similarity sf for categorization. Besides the aforementioned two in- dicators, the server also calculates the average value of all clients' local speeds (f*) and gradient update similarities (3'), respectively, which serve as the dividers. Equations and demonstrate the calculation formulas for these indicators.
nii) = (n()), (n(1)+ +1, if (0(1)
ifi S
(i),
f
if S
f ni())
f
Σ N N
2i=
ft
z
Σ (1) N
(2)
ΣN nii)

---

where n(()) is the total number of times client C2 participates in the global model aggregation, sy(i) the latest local-global gradient update similarity that C2 shares with the server, and N is the total number of clients.
Below, we explain the training strategy employed for each of the four types of clients.
Fast- buu-Suttoglyy-iiiiee -Biased Clients (FSBC): This type of client exhibits a rapid update speed (i.e., f > f!) but produces biased local gradient updates that deviate from the global model (i.e., of < 5)). We attribute this phenomenon to the heterogeneous local data distribution, whose features the server may not fully extract. Due to these biased updates, reducing the local learning rates could hinder the global model's 's ability to learn sparse features from local data. Therefore. Mod maintains the local learning rates of these clients unchanged. To facilitate the learning of the missing information from local data, Mod instructs the server to assign appropriate (typically higher) aggregation weights to these clients through feedback mechanism (see Mod in Section 3.4).
Fast-and- Past-and-Weakly Weakly-Biasee Biased Clients (FWBC): For such clients, the server has effectively extracted their local information for global model aggregation. However, due to their fast local update speed (i.e., f > f*), the global aggregation may become biased towards their local models. To mitigate this effect, Mod reduces the learning rate of these clients (i.e., off = 7 f-1 aF, where a the change rate and F f to slow down their update speed. A potential side effect of this operation is that it may decrease the convergence speed local model training. To address this issue, we introduce a momentum term during the local training phase, as shown in Equation 3
Momentum Term
whe w Whee-1
where mf is the momentum rate and has the relationship: m = mo + k() - 1), where mi, k are hyperparameters, and G
Straggling-but Soant-Weakl-BBeee -Basse Clients (SWBC): Despite effectively utilizing local information for global model aggregation (i.e., st > 5²), this type of client experiences slow update speed (i.e., f < f'), suggesting limited local computational resources. Therefore, Mod@2 increases its learning rate (i.e., ni} of + a.F) to compensate for these resource constraints. However, an excessive increase in the learning rate may hinder the optimization of the local model. To address this issue, Mod employs the same momentum term used for FWBC to expedite the extraction of local data information and facilitate model convergence.
Sangllin-and-Stronng Biased Clients (SSBC): To address the problem posed by these clients' limited computational resources (i.e., f < f`), Mod increases the local learning rate (i.e., nf 1/ 1-1 1-1+af) To tackle the issue of local update bias diverging from the global model update direction (i.e., of < 8²), we leverage a local validation set on each of these clients to assess the running environment. If the global model performs similarly on each label of the local validation dataset, we consider the issue to be a straggling problem (Situation 1) and adopt a strategy akin to that used for SWBC, enabling momentum optimization algorithms to mitigate the impact of outdated models. Conversely, if the global model exhibits significant performance differences across labels in the validation dataset, we consider the issue to be a dispersed distribution problem (Situation 2) and utilize feedback mechanism similar to that employed for FSBC to alleviate the effects of heterogeneous data distribution.
Notably, the momentum term in FedQS is not primarily a speed accelerator but a trajectory stabilizer for clients whose updates align well with the global model (high sf). For these clients, momentum mitigates oscillations while accelerating convergence speed (Fquation 33. In contrast, for high- bias clients (FSBC and SSBC in Situation 2), premature momentum application could amplify the divergence between their local updates and the global one, as their updates are not yet globally beneficial.
3.4 Global model aggregation (Mod()
This module aims to facilitate the central server weighing the local models for the aggregation of the global model. Specifically, upon receiving new local update data from client C₁, the server
5

---

first calculates the average speed f', average similarity s", and the local update speed fi, and then updates the aggregation status table accordingly using Equations [ and 2 Then, the server will persistently wait and start aggregation once it receives K available local updates. For each client that has uploaded its local update data, the server assigns an initial weight parameter pi = 2s and then iterates through these clients. If a client has triggered the feedback mechanism (SSBC with Situation .xp(o-FF (1+9)²
2 or FSBC), the server updates its weight parameter via p; = _
K where exp(-) is
2
the natural exponential function and ø = K. server normalizes these weight parameters (i.e.. p; = Eies P. Vi S) before proceeding with the
N: otherwise, the weights remain unchanged. Next, the P:
global aggregation process. The term exp(o-F) addresses the effect of outdated weights (inspired 2
by 34 15 while (1+g)² accounts for the quadratic relationship between the convergence bound and the model weight difference, as outlined in Theorem 4.2 and Theorem
Given that FedQS optimizes both aggregation strategies, we denote the gradient aggregation strategy- based implementation as FedQS-SGD and the model aggregation-bact based as FedQS-Ave in this paper. For
Mod incorporates the momentum term as part of the update data and calculates
the pseudo-gradiens
[6 20 as A
T.e Σi=1 (m J'V --) V.ie (w 1). Then,
Mod aggregates the new global model using w/ = w/y1 Eies Pill Ee AFT For FedQS-
i,e"
Avg. Mod performs the weighted aggregation by w/ Eies P.
4 Convergence analysis of FedQS
In this section, we present the theoretical convergence guarantees for FedQS, demonstrating its ability to effectively optimize both gradient and model aggregation strategies within the SAFL framework. Complete theoretical details are provided Appendix due to space constraints.
4.1 Assumptions
We begin by stating our key assumptions, which are standard in the federated learning literature. The following conditions hold:
(1) For Vi, the loss function F; is L-smooth [35 36).
The expected squared norm of local stochastic gradients V (ww() is uniformly bounded by
Ge 35 16
(3) The degree of heterogeneity in the training task is bounded by 15
Remark 4.1. Assumption 2)) is introduced solely to simplify the interpretation of convergence bounds by providing deterministic upper bound for the gradient variation term W (see Theorems[A.4 and A.5 in the appendix). Crucially, it is not used in proving our core convergence theorems (Theorems 4.2 and 4.3), which rely only on Assumptions (. and (3). The convergence guarantees and heterogeneity analysis in Section 4.2 remain fully valid without this condition.
4.2 Convergence guarantees
Our convergence analysis employs the expected function value gap, E F(F( F the primary performance metric, following established SAFL literature [18] 28 37]. This choice is motivated by its direct quantification of solution quality relative to the ideal optimum F*, its unique ability to reveal stability dynamics (e.g., oscillations and transient regressions under semi-asynchronous updates that gradient norms often obseure), and its alignment with theoretical and practical SAFL conventions for assessing convergence behavior and aggregation-strategy efficacy, thereby providing more comprehensive evaluation of FedQS's performance under dual aggregation strategies. We present our main convergence results below.
Theorem 4.2 (Gradient Aggregation Convergence). Under Assumptions 4.1 let B max,, (nt ny
with मύK B V 2nk-3 where R Eg- E 02 -
3
In Rts R's formula, E is the maximum
(1-9)"
local epoch, and maxi, [m;) Let K be defined in Section 3.4 then FedQS-SGD satisfies:
[((((W))] F" S LV"B(I w 112 u + W,

---

(0,1) controls the convergence rate, U O(62) captures the data heterogeneity. and W = O(G), bounds gradient variations. Notice that W S [ALE² + 4LRQ(t) + (3 1+L+22200++333 B where Q(t) denotes the maximum number of clients that execute the 2 R-222 momentum update at global round
where V (3
R 3-+1
Theorem 4.3 (Model Aggregation Convergence). Under Assumptions 4. let 1er0squ 1. < PSL 1,
for KR+E--I <B< < 2RK +2E-3 Let K be defined in Section 3.4 then FedQS-Avg satisfies:
( F' S (3LpK² + L)V'Blluu
w 1I + u WW
(5)
with V.U, W having similar interpretations as in Theorem 4.2 4.2
Remark 4.4. The exponentially decaying V term accelerates convergence within the sublinear regime characteristic of non-convex FL., yielding a rate strictly faster than the standard ((1/t) while maintaining the overall ((1/t=) + U + W) bound. Unlike the linear convergence under strong conditions, this confirms that V enhances practical performance without altering the fundamental sublinear convergence landscape.
Remark 4.5. The V term highlights the impact of data heterogeneity (6²), while W captures gradient norm effects (G The non- non-vanishing terms + W reflect fundamental limitations inherent to semi- asynchronous FL systems [28] 37). capturing unavoidable convergence errors from non-simultancous aggregation and irreducible data heterogeneity.
Remark 4.6. Theorem 4.2 demonstrates that FedQS- SGD limits the gradient variation amplification in W through controlled momentum updates since the momentum term is only applied to subset of clients (i.e.. FWBC, SWBC, and SSBC with Situation 1). thereby improving convergence stability.
Remark 4.7. Theorem 4.3 shows that FedQS-Avg achieves comparable convergence with FedQS- SGD, with the V" term guaranteeing asymptotic convergence, alleviating the slow convergence speed and suboptimal convergence utility inherent to model aggregation strategies in SAFL.
Evaluation
5.1 Experimental setup
We evaluate FedQS on three task types SAFL: Computer Vision (CV) using ResNet- 18 [38 on CIFAR-10 (39], Natural Language Processing (NLP) with LSTM [40 on Shakespeare [1. and Real-World Data (RWD) using FCN on UCI Adult [4]. Resource constraints limited our experiments to moderate-scale models, though our approach remains model-agnostic as FL is infrastructure independent of models or datasets. We simulate a heterogeneous federated system with clients having uniformly distributed computing resources (default: 100 clients, resource ratio 1:50, i.e., the fastest client exhibiting a training speed 50 times that of the slowest). The default similarity function in Mod is cosine similarity.
All experiments were conducted on a Linux system (Ubuntu 22.04 LTS) using an Intel Xeon Platinum 8468 Processor and an NVIDIA H100 80GB HBM3 GPU, with system memory capped at 20 GB per run. The software stack included Python 3.8.0, Py 2.0.0, and Torchvision O. 16.0, all within a Conda environment. Due to space constraints, comprehensive details datasets, model architectures, client resource distributions, hyperparameters, baseline algorithms, and additional results are provided in Appendix D
5.2 Performance evaluation
As the first solution optimizing both gradient and model aggregation strategies in SAFL, we compare
FedQS against four model aggregation (FedAvg [1, SAFA [II] FedAT (18), M-step (37)) and
four gradient aggregation (FedSGD M FedBuff [16], WKAFL 15), FedAC [20], DeFedAvg 12]
FADAS 43 FA (44) baselines. To our best, there is no related work that supports both strategies. We employ the same metries as those in [21] to evaluate the performance of FedQS and baselines: 1) Accuracy and loss performance, which reflect the prediction capabilities of the trained global model on the test dataset. 2) Convergence speed, determined by the number of epochs (denoted as T2) required to achieve the target accuracy for the first time (21) 3) Runtime, recorded as the duration from the initiation to the completion of the T-th (T being the maximum global training epoch) rounds of global aggregation.
7

---

Table 2: Accuracy and convergence speed of FedQS and the baselines.
Algorihbms
Metries
Tasks
FedQu (Avg)
FedBuff WKAFL FodAC DeFedAvg FADAS C.A FL. Fed
FedAvg
SAFA
FodAT
M M-step
FodSGD
(SGD)
0.1
56.05
56.15
28.15
62.17
63.91
65.71
64.43
64.66
56.52
52.33
65.34
42.29
68.88
x
0.5
73.71
58.31
45.65
80.49
80.26
83.87
80.73
85.14
82.65
83.51
82.2
63.79
86.11
47.58
82.46
82.74
85.42
81.43
85,94
86.17
84.21
70.16
86.79
Accuracy (%)
It
200
47.04
43.65
37.13
49.38
50.43
48.04
48.37
50.49
50.43
40.19
46.83
25.36
52.22
R
600
45.52
40,90
36.35
12.122:
50.08
47.42
51.62
48.95
Gender
77.10
77.05
77.01
78.20
78.94
77.15
76.37
78.96
77.69
77.82
78.04
76.09
78.74
Ethnicity
77.25
77.07
77.26
78.01
78.85
78.33
78.71
76.97
77.71
78.
78.54
66.68
79.24
= 0.1
304
162
317
329
276
281
334
277
243
307
255
272
239
x = 0.5
295
344
304
276
234
264
293
255
232
257
220
256
213
Conv. speed (At epochs)
244
163
119
259
200
n7 200
288
342
357
264
231
234
278
221
243
256
220
2.59
188
R 600
336
375
275
249
248
277
238
272
216
Gender
43
57
63
46
35
29
66
51
17
59
25
59
18
Ethnicity
55
61
44
33
36
76
54
27
20
24
325
In the "Tisks" column, represents the parameter of the Ditichlet distribution within CV tasks; R denotes the number of roles within tusks; Gender and Ethnicity are the data types within RWD lasks.
The convergence accurncy measured the average global accuracy the last munds. The turget accuracy for convergence speed is sei to 95% of convergence accuracy in CV and NLP tasks and 98% of the convergence accuracy in RWD tasks.
Table 3: Runtime of FedQS and the baselines.
Algorithms
Tasks
FedAve
(SFL)
FodAvg
SAFA
FodAT M-stop
FedQS
(Avg)
FodSGD (SFL)
FedSGD FedBuff WKAFL FedAC DeFedAvg FADAS
CA4FL
FedQS
(SGD)
2'
0.1
78,048
24.204
204,588
66.851 49,971
32,827
76,392
24.184
25,054
34,862
30,329
30.776
32,580
108.097
32,784
0.5
77,956
24.214
144,371
66,746
49,953
33,254
76,822
23,921
25.720
35,286
28.721
31,754
32,966
109.635
33,656
x
79,095
24.208
142,594
66,851
46,859
33,477
79,816
24.108
25,513
32,707
29,152
30,280
31,471
108.756
33,400
R 200
22,417
4,925
27.642
21,089
116:906
22,118
5,096
32,849
8,340
4,989
5,118
36,441
5,248
R
600
53,784
7,358
39,475
33,300
171.965
9,528
53,590
7,211
8,320
$9,277
12,982
8,720
9,002
36.548
9.135
30.149
5,508
10,413
6,338
12,469
5,701
30,088
6,164
13,420
5,423
4,841
5,476
19,650
5,523
Ethnicity
33,275
5,513
9,127
6,437
12,389
5,665
32,787
5,148
6,037
14,215
5,711
4,827
5,299
19,370
5,465
Shudowed columns represent evaluations under synchronous (SFL).
Table 2 presents the experimental results. FedQS attains the overall highest accuracy and fastest convergence speed across almost all tasks. Specifically, for model aggregation, FedQS's s average accuracy is 68%. 1.71% 1% higher than that of the best baseline (i.e., M-step), and for gradient aggregation it is 72.06%, 2.51% higher than the best baseline (i.e., WKAFL). SAFA, FedAT, and FedBuff do not perform as well as their corresponding foundational algorithms, FedAvg and FedSGD. This is because these three algorithms sacrifice the accuracy of the global model for more stable training process (see Table and Figure 10 in the appendix for the analysis of convergence stability). Figure 4 depicts the loss function curve of representative tasks for both model and gradient aggregations. This figure illustrates that FedQS achieves the minimum loss as training progresses, implying FedQS's capability converge the model to its optimum.
Table 3 shows the runtime performance results. FedQS achieves comparable efficiency to the top- performing baselines, demonstrating its fcasibility for real-world deployment. For reference, we include the runtime measurements of FedAvg and FedSGD under synchronous settings. When compared to these synchronous baselines, FedQS-Avg and FedQS-SGI achieve average runtime reductions of 70.34% and 70.91%, %, respectively, highlighting SAFL's superior resource efficiency over synchronous configurations. Meanwhile, evidenced by Figures 8 and [ (in the appendix), FedQS maintains substantially lower time latency between global aggregation rounds than other SAFL optimization algorithms, further validating its operational efficiency.
5.3 Effectiveness of FedQS under different system settings
In this section, we evaluate the impact of different numbers of clients and resource distributions on the performance of FedQS. We vary the number of clients (50 or 200) and the resource distribution ratio (1:20 or I: 100), conducting experiments with 0.1, 0.5, 1 in CV tasks under both aggregation strategies and reporting average values. Table shows representative results of FedQS compared to two foundational algorithms in SAFL (with complete results in Table i0 the appendix). FedQS
AWKAFL's overfitting curve in Figure 41 is due to the large learning rate and WKAFL's adaptive learning rate adjustment module.
8

---

52X
10
26 Epock
400
380
40
24
203
4%0
230
Speda
CV Task
(h) NI.P Task
(c) Task
(d) Task
Task
Figure 4: Loss of FedQS and the baselines under a representative CV task (x = 0.5), an NLP task (R 600), and an RWD task (gender). The left three subfigures are based on model aggregation, while the right three are based on gradient aggregation.
Table Robustness of FedQS.
Table 5: Ablation study results in CV tasks.
Scenario
Method
Metrics
Metrics
Cony, speed # Oxcillations
Cony, speed
FedAvg
70.1
224
0.0
Module
Method
Accuracy (%)
(4 epachs)
Oscillations
N=50
FodQS-Avg
79.2
179
3,0
Avg
SGD
Avg SGD
Ave
SGD
(1:20)
FedSGD
77.4
193
37.0
Cosine
74.14
80.59
251
230
4.0
7.6
FedQS: SGD
80.7
152
26.3
Mod
Euclidcan
75.69
79.55
244
232
5.6
11.3
FedAvg
49.4
Manhattan
76.56
9.6
N=200
FedQS Avg
64.7
256
0.3
Mod
wio momentum
73.21
78.88
269
242
4.3
9.6
(1:100)
FedSGD
74.4
248
7,3
with momentum
74.14
80.59
251
230
4.0
7.6
FedQS-SGD
80.1
203
3.0
feedback
5.6
Mod
50 means the task has 50 clients, and 1:20 means the
with feecihuck
74.14
80.59
251
230
4.0
7.6
fastest client exhibits training speed 20 times that the slowest one. The threshold used to calculate the number of oscillations is The target accuracy for convergence speed set
Avg and represent FedQS Avg FedQQ SGD, respecttiil
Fach result is an average value corresponding to z 0.1, 0.5, I.
The threshold used calculate the number of oscillations set
95% of convergence accuracy
15. The target accuracy for convergence speed is set 95% convergence accuracy
Each result an average value three experiments correpoond
ing 0.1, 0.5, in CV tasks.
consistently outperforms both FedAvg and FedSGD across all three metrics, aligning with the results in Table 2
To further validate the robustness of FedQS in dynamic environments, we conduct additional CV experiments under three scenarios where client resources vary during training: (1) Dynamic Resource
Scale (Scenario 1): the speed ratio shifts from 1:50 to 1:100 at round 200; (2) Unstable Resource per Client (Scenario 2): each client's resource fluctuates within [-10, +10] unit times per update, bounded between and 50 units: (3) Client Dropout (Scenario 3): 50% of clients randomly churn at
round 100. As shown in Table 6 FedQS maintains stable convergence across all dynamic scenarios.
These results demonstrate that FedQS is effective under various system settings and maintains robustness in dynamic environments. We further discuss the scalability of FedQS in Appendix C
Table Performance comparison of different algorithms under dynamic scenarios
Dynamic
x=0.1
x=0.5
x=I
Sccnario
Algorithm
Accuracy (%)
Cony. Speed
Runtime (8)
Accuracy (%)
Cony, Speed
Runtime (s)
Accuracy (%)
Cony, Speed
Runtime (s)
FodAvg
52.77
322
46488
77.29
288
47732
76.79
227
48003
FodQS-Avg
66.47
264
53986
82.90
235
54575
83.22
55529
Scenario
FeaSCD
68.29
244
47443
85.66
211
47728
87.86
147
48280
FedQS
76.17
206
54095
55268
FedAAg
52.12
310
47397
76.74
294
47156
79.90
286
47788
Secuario
FodQS-Avg
64,52
268
55535
83.53
241
55816
84.35
252
56253
FedSGD
268
85.37
47096
47634
FedQS SGD
69.65
223
55037
87.96
185
55201
89.14
133
55808
HodAvg
44.39
343
58993
68.44
332
59362
72.47
296
59447
FodQS-Avg
53.22
297
62623
79.33
272
63308
$1,08
253
63776
Scenario
FedSGD
58.40
292
58345
81.73
288
59487
84.43
262
$9732
FedQS-SGD
60.08
83.39
245
63992
86.18
64703
5.4 Hyperparameter analysis
This section presents hyperparameter analysis of FedQS. Using a grid search, we fine-tune four key hyperparameters within the adaptive module (Mod@): the initial learning rate yo (where 1/0 & n/. Vi), the learning rate change rate the initial momentum mg, and the momentum change speed k.

---

FedSGD
FedQS-SGD
FedAvg
FedQS-Avg
Accurcy
Accuroy
Accuarr
70
70
93
0.15
01
3.05
0.1
60011
1641
5o4
[t5]
10-]
3653
0.01
0.0
6,1
62
83
0.4
0.01
0.05
0.1
0.2
0.3
0.
m7g
Coro, Speed
125-
Spoed
Coans Spood
125
Loek
100
100
100
2.15
6000
18.4
56-4
16.3
56-3
162
0.2
Figure 5: Impact of different hyperparameters on FedSGD, FedAvg, and FedQS's performance in CV tasks. The target accuracy of convergence speed set to 80% of convergence accuracy.
Figure summarizes the results for CV tasks (with detailed results provided in Appendix Tables II 14. Our findings indicate that an excessively large or small 17o leads reduced accuracy and slower convergence, trend also observed in FedSGD and FedAvg. However, FedQS's adaptive learning both metrics over these baselines. Furthermore, we observe that overly large values of a, mg. and A can adversely affect FedQS's 's performance in both modes. Among these, a has the most pronounced impact on accuracy, while & has the least.
strategy yields significant improvements
Crucially, FedQS exhibits robust performance across broad hyperparameter ranges (e.g., E [0.001, 0.005] and E [0.001, 0.2)), achieving strong results with default settings = 0.1, k = 0.2) as shown in our main experiments. The adaptive mechanisms in Mod inherently mitigate sensitivity hyperparameter selection, while Mod(f and Mod remain hyperparameter- free. This design sub substantially reduces tuning overhead and facilitates practical deployment in real-world federated learning scenarios.
0.002,
5.5
Ablation studies
In this section, we conduct ablation studies on FedQS's modules, with the results presented in Table
Similarity Function (Mod@). We evaluate three similarity measures: Cosine Function (CF), Eu- clidean Distance (ED), and Manhattan Distance (MD). While MD achieves slightly higher accuracy, CF exhibits better stability with fewer oscillations. The comparable performance across measures validates FedQS's robustness to different similarity metrics.
Momentum (Mod@). Removing momentum terms degrades performance significantly. with aver- age accuracy dropping by 4.3% and convergence requiring 6% more epochs. This demonstrates momentum's crucial role in both optimization efficiency and final model quality.
Feedback Mechanism (Mod3). Disabling the feedback mechanism causes substantial accuracy degradation (7.81% 81% for FedQS-Avg. 18% for FedQS-SGD), highlighting its importance for main- taining model performance. The feedback mechanism proves particularly valuable for averaged models, where its absence leads to more pronounced performance drops.
6 Conclusions
In this paper, we presented FedQS, novel framework that jointly optimizes gradient and model aggregation in SAFL. FedQS employs divide-and-conge strategy that dynamically categorizes clients into four types and adaptively adjusts their local training schemes. Thcoretical analysis estab- lishes that FedQS achieves convergence under both aggregation paradigms, effectively addressing the instability gradient-based methods and the suboptimality model-based ones. Experiments across diverse settings demonstrate that FedQS achieves accurate predictions, rapid convergence, and stable training. consistently outperforming state-of-the. baselines. Future work will integrate differential privacy for stronger security and evaluate under more realistic conditions (e.g., non-IID data and limited client-side data volumes) to further validate practical utility.
10

---

Acknowledgments and Disclosure of Funding
This work was partly supported by the National Key R&D Program of China (No. 2023YFB2704903), Research and Development Program of the Department of Industry and Information Technology in Xinjiang Autonomous District (No. SA0304173), the Natural Science Foundation of Shanghai (No. 23ZR1429600), and Huawei research grant (No. (C20250717058),
References
[1] B. McMahan, E. Moore, D. Ramage, Hampson, and B. A. Arcas, "Communication-fficee learning of deep networks from decentralized data," in Artificial intelligence and statistics. PMLR, 2017, pp- 1273-1282
[2] X. Li, M. Jiang, X. Zhang, M. Kamp, and Q. Dou, "Fedbn: Federated learning on non-iid features via local batch normalization," " arXiv preprint arXiv:2102.07622. 2021.
[3] S. P. Karimireddy. S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh, "Scaffold: Stochastic controlled averaging for federated learning," International conference on machine learning. PMLR, 2020, pp. 5132-5143.
[4] N. Wu, X. Yuan, S. Wang, H. Hu, and M. Xue, "Cardinality counting in" alcatraz": privacy-aware federated learning approach," " in Proceedings of the ACM on Web Conference 2024, 2024, pp. 3076-3084.
X. He, S. Liu, Keung, and J. He, "Co-clustering for federated recommender system," in Proceedings the ACM on Web Conference 2024, 2024, pp. 3821-3832.
[6] Q Chen, Z. Wang, J. Hu, H. Yan. J. Zhou, and X. Lin, "Page: Equilibrate personalization and generalization in federated learning," " Proceedings of the ACM on Weh Conference 2024, 2024, pp. 2955-2964.
[7] B. Yan, Y. Cao, H. Wang. W. Yang. J. Du, and C. Shi, "Federated heterogeneous graph neural network for sewaacypreserving recommendation." " in Proceedingy of the ACM on Web Conference 2024, 2024, pp. 3919-3929.
[8] Q Wu, X. Chen, Z. Zhou, and J. Zhang, "Fedhome: Cloud based personalized federated learning in-home health monitoring," IEEE Transactions on Mobile Computing, vol. 21, no. 8. pp. 2818 2832, 2020.
[9] T. A. Khoa, D.-V. Nguyen, M.-S. Dao, and K. Zettsu, "Fed xdata: A federated learning framework for enabling contextual health monitoring in cloud-edge network," " 2021 IEFE International Conference on Big Data (Big Data). IEEE, 2021, pp. 4979-4988.
[10] R. S. Antunes, C. André da Costa, A. Küderle, I. A. Yari, and B. Eskofier, "Federated learning for healthcare: Systematic review and architecture proposal," ACM Transactions on Intelligent Systems and Technology (TIST), vol. 13, no. 4, pp. 1-23, 2022.
[11] G. Long, Tan, J. Jiang, and C. Zhang, "Federated learning for open banking," Federated Learning: Privacy and Incentive. Springer, 2020, pp. 240-254.
[12] T. Suzumura, Y. Zhou, R. Kawahara. Baracaldo, and H. Ludwig. "Federated learning for collaborative linancial crimes detection," in Federated learning: A comprehensive overview of methods and applications. Springer, 2022, pp. 455-466.
[13] T. Liu, Z. Wang, H. Hc, Shi, L.. Lin, R. An, and C. Li, "Efficient and secure federated learning for financial applications." Applied Sciences, vol. 13, no. 10, 1977,2023
[14] R. Hannah and W. Yin, "More itcrations per second, same quality- why asynchronous algorithms may drastically outperform traditional ones," arXiv preprint 1108.077..055 2017.
[15] Z. Zhou, Y. Li, X. Ren, and S. Yang, "Towards efficient and stable k-asynchronous federated learning with unbounded stale gradients on non-iid data," IEEE Transactions on Porallel and Distributed Systems, vol. 33, no. 12, pp. 33305, 2022.
[16] Nguyen, K. Malik, Zhan, A. Yousefpour, M. Rabbat, M. Malek, and D. Huba. "Federated learning with buffered asynchronous aggregation." in International Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 3581-3607.
[17] N. Singh and M. Adhikari, "A hybrid semi-asynchronous federated lcarning and split learning strategy in edge networks," IEEE Transactions on Network Science and Engineering, 2025.
[18] Z. Chai, Y. Chen, Anwar, Zhao, Y. Cheng, and H. Rangwala, "Fedat: A high- performance and cetruuniiaaionefffciinee federated learning system with asynchronous tiers." in Proceedings of the in- ternational conference for high performance computing, networking, storage and analysis, 2021, pp. 1-16.
11

---

[19] Y. Zhang, D. Liu, M. Duan, L. Li. X. Chen, A. Ren, Y. Tan, and C. Wang, "Fedmds: An efficient model discrepancy-awart semi-asynchronous clustered federated learning framework," IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 3. pp. 1007-1019, 2023.
[20] Y. Zang. Z. Xue, S. Ou, L. Chu, J. Du, and Y. Long. "Efficient asynchronous federated learning with prospective momentum aggregation and fine-grained correction," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 15, 2024, pp. 16 642--1665..
[21] Y. Li, J. Gui, and Y. Wu." "An experimental study of different aggregation schemes in semi-asynchronous federated learning." " arXiv preprint M.Xi::2405.16088 2024.
[22] M. Yu, J. Choi, J. Lec, and S. Oh, "Staleness aware assnhhhynchoooouss federated learning," Journal of Parallel and Distributed Computing, vol. 193, p. 104950, 2024.
[23] R. Xie, C. Li. X. Zhou, and Z. Dong, "Asynchronous federated learning for real-time multiple licence plate recognition through semantic communication." in ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2023, pp. 1-5,
[24] C.-H. Hu, Z. Chen, and E. G. Larsson, "Scheduling and aggregation design for asynchronous federated learning over wireless networks," TEEE Journal Selected Areas Communications, vol. 41, no. 4, pp. 874-886, 2023.
[25] L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio, "Sharp minima can generalize for deep nets." in Interna- tional Conference on Machine Learning. PMLR. 2017, pp. 1019-1028.
[26] H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein, "Visualizing the loss landscape of neural nets," Advances in neural information processing systems, vol. 31, 2018.
[27] Q. Zhang, B. Gu, C. Deng, and H. Huang, "Secure bilevel asynchronous vertical federated learning with backward updating." in Proceedings of the AAAI Conference Artificial Intelligence, vol. 35, 12, 2021. pp. 10 10896-10900 1044..
[28] Q. Ma, Y. Xu, H. Xu, Z. Jiang, L. Huang, and H. Huang, "Fedsa: A semi-asynchronous federated learning mechanism heterogeneous edge computing," IEEE Journal on Selected Areas in Communications, vol. 39, no. 12, pp. 3654-3672, 2021.
[29] H. Zhu, Y. Zhou, H. Qian, Y. Shi, X. Chen, and Y. Yang. "Online client selection for asynchronous federated learning with faimess consideration," IEEE Transactions on Wireless Communications, vol. 22, no. 4. pp. 2293-2222020 2506, 2022.
[30] S. Reddi, 7. Charles, Zaheer, Z. Garrett, K. Rush, J. Konečný, S. Kumar, and H. B. McMahan, "Adaptive federated optimization," " arXiv preprint arXiv:2003.0029. 2020.
[31] W. Wu, L. He, W. Lin, R. Mao. C. Maple, and S. Jarvis, "Safa: A semi-asynchronous protocol for fast federated learning with low overhead," IEEE Transactions on Computers. vol. 70, no. 5, pp. 655-668, 2020.
[32] J. Cheng, Luo, N. Xiong, and J. Wu, "Aafl: Asynchronous adaptive federated learning in edge-based wireless communication systems for countering communicable infectious diseasess," " IEEE Journal on Selected Areas in Communications, vol. 40, no. 11, pp. 3172-3190, 2022.
[33] S. Wang. T. Tuor, Salonidis, K. K. Leung, Makaya, T. He, and K. Chan, "Adaptive federated learning in resource constrained edge computing systems," IEEE journal on selected areas in communications, vol. 37, no. 6. pp. 1205-12211 2019.
[34] Y. Chen, X. Sun, and Y. Jin, "Communication-effenee efffccitnn federated deep learning with layerwise asynchronous model update and temporally weighted aggregation," JEEE transactions on neural networks and learning systems, vol. 31, no. 10, pp. 4229-4238. 2019.
[35] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, "On the convergence of fedavg on non-iid data," arXiv preprint 19Xiv:1907.022
2019.
[36] Z. Guo and T. Yang, "Communication-effice"
federated group distributionally robust optimization," " in Advances in Neural Information Processing Systems, A. Globerson, L.. Mackey, D. Belgrave,
A. Fan, U. Paquet, J. Tomczak, and C. Zhang, Eds., vol. 37. Curran Associates, Inc., 2024. pp. 23 040-040033 077. [Online]. Available: httpss//proceeddings.. http://wwwccccnni.euuuuu....epee www.siis.cccc/papeeeeeeeeeeeeeee files/paper/2024/tte// DM22106aliakeeeeee445s4eeeeeeee Peppaa- Conference.p
[37] X. Wu and C.-L. Wang, "Kafl: achieving high training efficiency for fast-k asynchronous federated lcarning." in 2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS). IEEE, 2022, pp. 873-883.
[38] K. He, Z.Zanng, Ren, and J. Sun, "Deep residual learning for image recognition." in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770-778.
[39] A. Krizhevsky, G. Hinton et al., "Learning multiple layers of features from tiny images." 2009.
12

---

[40] S. Hochreiter and J. Schmidhuber, "Long short-term memory," Neural computation, vol. 9, no. 8, pp. 1735-1780, 1997.
[41] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, "Membership inference attacks against machine learning models," in 2017 IEEE symposiun security and privacy (SP). IEEE, 2017, pp. 3-18.
[42] X. Wang, 7- Li, S. Jin, and Zhang. "Achieving linear speedup in asynchronous federated learning with heterogeneous clients," IEEE Transactions on Mobile Computing, 2024.
[43] Y. Wang, S. Wang, S. Lu, and J. Chen, "Fadas: Towards federated adaptive asynchronous optimization." arXiv preprint arXiv:2407. 18365, 2024.
2024.
[44] Y. Wang. Y. Cao, J. Wu, R. Chen, and Chen, "Tackling the data heterogeneity asynchronous federated learning with cached update calibration." in Federated learning and analytics in practice: algorithms, systems, applications, and opportunities, 2023.
[45] C. Xic, S. Koyejo, and I. Gupta, "Asynchronous federated optimization." arXiv preprint arvi: arxii:/:003 1903.03934, 2019.
[46] D. Zeng, S. Liang, X. Hu, Wang, and Z. Xu, "Fedlah: A flexible federated learning framework," Journal of Machine Learning Research, vol. 24, no. 100, pp. 1-7, 2023. [Online]. Available:
[47] S. Caldas, S. M. K. Duddu, P. Wu, T. L., Konečný, H. B. McMahan, V. Smith, and Talwalkar, "Leaf: benchmark for federated settings." arXiv preprint 1112:0/812.01097, 2018.
[48] G. Pólya and G. Szegö, "Aufgaben und lehrsätze aus der analysis, vol. 1, berlin 1925," Zbl0060, vol. 12307, 1925.
[49] S. S. Dragomir, Reverses of Schwarz, triangle and Bessel inequalities in inner product spaces. Citeseer,
2018.
[50] Z. Otachel, "Reverse schwarz inequalities and consequences in inner product spaces," Journal of Mathematical Analysis and Applications, vol. 458, no. pp. 1409-1426, 2018.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the contributions and scope of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We give the justifications of the assumptions' reasonability in Appendix A We further give the discussions of FedQS's scalability, FedQS's broader impact, and FedQS's limitations in Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
13

---

The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only lested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide brief assumption in Section 4.1 and make it detailed in Ap- pendix A Proofs are shown in detail in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We fully disclose all the information needed to reproduce the main experi- mental results this paper. We also release the source code https: com/ bkjod/Fedqs_it facilitate further research. We convinced that the obtained results can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
14

---

If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided our source code Anonymous GitHub com/bkjode jod/FedSS
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
15

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We discuss the details in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We diseuss the impact of different system settings, hyperparameters, and tasks of FedQS in Section 5 Experiments are repeated multiple times, and we provide the average results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided the experiment setting and hardware details in Section 5.1 and Appendix D We further discuss the runtime performance of FedQS and baselines in Section 5.2 with experimental results provided in Table
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///aaaaaassccc//u/////aaaaa
Answer: [Yes]
Justification: We have read and conformed the NeurIPS Code of Ethics. We confirm that this paper does not incorporate any ethic concerns of NeurIPS.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have discussed the broader impact Appendix C
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not release any new data models
Guidelines:
17

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our paper publicly available datasets (CIFAR-10. Shakespeare, and UCI Adult), which are all properly cited and introduced in Appendix [.] For the baseline methods, have give proper citations and introductions Appendix D.4
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
We provided our source code and dataset in the GitHub at htttss///githttt http//jjodFFFDDD with a documentation named "README.md" provide details in the repository.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.LM policy hato:e//nearrps.cc//ooffeeeeeeee for what should or should not be described.
19

---

A Convergence analysis details
We first provide the detailed descriptions of Assumption 4.1 which are also adopted in related works. Assumption A.1 (L-smooth [35 36]). We assume that for Vi, the loss function Pi is L-smooth, i.e. for all z, y as input, we have:
L 11y x213 Fi(v) - (z(x) S (VF((z), (v -))) + 2
where L > 0 is constant.
Assumption A.2 (Bounded Gradient B5 16]). We assume that the expected squared norm of local stochastic gradients (w(( is uniformly bounded, i.e.,
E F Go.
where Ge > 0 a constant.
Assumption A.3 (Bounded Heterogeneous Degree geneity in the training task is finite, i.c.,
3
15
We assume that the degree of hetero-
E F[IVF(( - VF =*,
(8)
where 8 0 is a constant and (- is the ideal global gradient, which is defined in detail in Appendix E This also implies that the discrepancy between the gradients of each individual client and the ideal global gradient is bounded.
We then give the justifications of the reasonability for these assumptions.
Justification of Assumption A.I Assumption A. is reasonable because loss functions (e.g.. sigmoid) in neural networks are generally smooth. The L-smoothness assumption aligns with differentiable loss function requirements, enabling gradient computation via backpropagation. The convergence analyses of FL typically rely on this assumption to facilitate simplified mathematical analysis. We avoided the convexity assumption our analysis for a more general analysis, because convexity relates to the difficulty of optimization problems. While convexity properties hold in simpler models like logistic regression or SVMs, deep neural networks generally operate in non-convex loss landscapes.
Justification of Assumption A.2 Assumption A.2 is reasonable because, in SAFL, gradient clipping employed to alleviate the accuracy degradation issue caused by non-lII data distribution. As long as clients apply gradient clipping, this assumption naturally stands. Violating this assumption implies that there exists client whose gradient is unbounded, leading to the gradient explosion and potentially causing the training to fail completely. This assumption also has wide application in 16 233. Meanwhile, since gradient clipping is commonly adopted in SAFL [55, the local gradient magnitudes during training remain bounded by the clipping threshold. Consequently, the gradient clipping threshold can be directly utilized as the upper bound for gradients our theoretical assumptions. In our experiments, we set the bound G. as 20.
FL 45 18
Assumption A.3 holds since data distribution heterogeneity is constrained due to limited training data. The heterogeneity of data distribution is determined once participating clients are selected for aggregation. Violating this assumption indicates either an infinite amount of data, which is impractical, or the data distribution would be constantly changing, making impossible to capture its exact values and ultimately leading to training failure.
Justification of Assumption A.3
Based on these assumptions, we rewrite Theorems 4.2 and 4.3 to give the complete theoretical results.
Theorem A.4 (The convergence of defined therein. Let T/. be defined Section 2 and K be defined in Section 3.4 maxi, ( n
Let Assumption A.7. A.3
hold and L, 8, G. be
and
AK <
2nk 3 where E is the maximum local epoch, 0 maxs, and
R- E8- E8² _82 1842
Then, we have the following convergence results:
(1-032
E| E[F(w F* < LV'Bil 3 w" w01 + W.
(9)
(3 where U 12
1 v= (3
28 3=+1
and
2--
20

---

E
W ==4LB m
V
(w) -DI
4LEIIn
E
WALEII
(w) (w (11
Fi
(10)
V22LE1111
(m) 10--111 Fi (1
j=0
S |ALE + ALRQ(() ( ()(Q((()) + 33E2) 2 2,3 -2
JBP.2.
Notice that the value of V is in (0, 1) and Q(t) denotes the maximum number of occasions upon which all participating nodes execute the momenium update module global round
Proof. See Appendix
Theorem A.5 (The convergence of (aadQS-Avg) Let Assumption A.2.A.2 A.3 hold and L, 8, Ge be
defined therein. Let Tf be defined Section 2 and K be defined in Section 3.4 Denoted E as the
maximum local epoch and assume the aggregation weight parameter ps satisfies 0 S P: < S 1.
Let (3 = m ng} and / KR+EE-I < V
22"-2E"-3" where EO E 62 + In
3
(1-07
R's formula, max;, (m])). Then, we have the following convergence results:
B[F(W(]] - F* s (3Lpk² L)V"B(Ilu w w"113 W,
(11)
where Q(t) defined in Theorem A.4 833032+1(0PP 32 E and
(3
20 (R+E#)
E (0, u = [3 KL
g2+
28 28 R - 23
22
E (F +2
E Fi
W (3L'" K + L)
Σ
WE
j=1
+ +
V ( (11) (3Lp L) Σ
WBIl Σ
(m
(m
+ +3p² KLE(In)
(m)) I'n''ve V'
c=1m=1
(3p"K + 1) + (00
< 122K(222 +3RQ()))))())
2 F2) -,32
(12)
Proof. See Appendix E.2
B Different communication and aggregation strategies in FL
Synchronous vs. Semi-Asynchronous FL. The primary difference between Synchronous FL and Semi-Asynchronous FL (SAFL) is that the former is based on cerver-controlled coordinated training, while the latter involves fully autonomous client execution with cndditional-tigggenn global aggregation. Specifically, in Synchronous FL, the server initiates each global round by selecting a subset of clients activated clients. These activated clients are required to complete local training using the latest global model and submit their updates, while inactive clients remain idle until this round concludes. The server performs aggregation through designated aggregation strategies after
21

---

receiving all activated clients' updates, then broadcasts the modified global model. In contrast, SAFL eliminates centralized coordination, where the server passively awaits client updates and triggers global aggregation immediately upon meeting specific triggering conditions (e.g.. sufficient accumulated updates [5 [6]). Each client autonomously executes local training its own pace. Upon completing local training, clients immediately transmit local updates to the server and verify the availability the new global model. If is available, they synchronize their local models accordingly; otherwise, they persist with existing parameters while continuing local training.
Gradient aggregation vs. Model aggregation. There are two foundational aggregation strategies in FL: gradient aggregation and model aggregation. The key difference between these two strategies that the former enables the server train the global model by aggregating gradients and then performing gradient descent on the original one, whereas the latter allows the server to construct the global model based on local model parameters directly.
In Synchronous FI., due to the server-enforced synchronization requirement, each activated client restricted to uploading a single update per global round, which is derived from training on the latest global model. Consequently, during the (t+ 1)-th global aggregation round, given the index set (without duplicates) of activated clients in this round as S, each client Vi S performs local training within E. local epochs according to w! = un - "/i De VFi(w D:), where wf,o - weg
Denoted fy as the global learning rate and n - EiEs 14, the gradient aggregation strategy can be shown as u g 7g Exes nh (u,)), where (F((w)) A EE_ (F
n Remark B.I. In FedSGD M. the local epoch parameter E is typically set to When E > 1. this
aggregation paradigm is commonly referred as model difference aggregation [16 37 23 where
clients transmit parameter differences calculated through multiple local epochs as Aw! = w w
M) Σe VF((w :D.) The server then performs aggregation using w wy Eies n: Awf.
For conciseness and without loss of generality, we collectively refer to scenarios with F. > 1 as the gradient aggregation strategy. This unified terminology is justified since both FedSGD
(E = 1) and model difference aggregation (E > 1) fundamentally utilize local gradient information V (w D,) during global aggregation processes.
In contrast, the model aggregation strategy requires each activated client to transmit its local model parameters to the server instead of the local gradients. The server then uses w = =ies 7 Wf to form the new global model.
In SAFL, due to the autonomously local training across all clients, updates from clients with constrained computational resources may exhibit parameter staleness. Specifically, during the + 1)-th global round, client C, might complete its local training using the global model from the -/hth round as w w.g Ee Vii(w D:), where wf,o - wg.
Therefore, given the index list (possibly with duplicates) of the clients participating in aggregation as at the (t + 1)-th global round, the gradient aggregation strategy and the model aggregation strategy in SAFL can be denoted as w w/ Ng Eies 24 ( and w Eies n
us w
respectively, where VF((w?)) & Ee VFi(w,,-11 D,) with w/o = w
C Discussion
C.1 Superiority of SAFL.
The SAFL framework introduces an asynchronous federated learning paradigm that eliminates the necessity for synchronization among participants, enabling autonomous execution of local model updates and seamless parameter/gradient transmission to the server. This architecture fundamen- tally differs from conventional Synchronous FL implementations, where frequent idling occurs for inactivated clients to await completion of all activated clients' local training during synchronized global epoch, as well as from Asynchronous FL's aggregation mechanism that processes individual updates immediately upon reception. SAFL's superiority emerges through its conditional aggregation protocol, which employs dynamic triggering criteria based on predefined system conditions (e.g., resource availability thresholds, update quality metrics, or temporal constraints) to optimize both computational efficiency and model convergence characteristics. The framework's 's trigger-driven
22

---

aggregation mechanism concurrently addresses Synchronous FL's inherent resource under-utilization during prolonged waiting periods and Asynchronous FL's susceptibility update volatility caused by premature aggregations, thereby achieving enhanced training throughput while maintaining model stability in dynamic network environments.
C.2 Scalability of FedQS.
FedQS demonstrates strong scalability to large-scale networks comprising thousands of clients, as introduces only minimal overhead. From the client-side perspective, each client performs only one additional similarity calculation and two numerical comparisons compared to baseline methods, with no inter-client communication required. Therefore, increasing the number of clients does not compromise client-side scalability. From the communication perspective, FedQS adds 1-bit signal and one floating-pon poating--ponttttt value to the upstream channel (client + server), and three floating-pon -pinnt values the downstream channel (server client). These additions constitute only small fraction of the total transmitted data, which typically includes gradients or model parameters. Hence, the communication overhead introduced by FedQS remains negligible. The additional metadata increases the total communication volume by less than 1%, consisting of a 1-bit signal and one float uplink (4 bytes). and three floats downlink (12 bytes). For model such ResNet- 18 (~>3.77 MB), this represents an increase of only 0.000037% over FedAvg/FedSGI. This overhead requires no additional synchronization steps and scales linearly with the number of clients, yet is substantially outweighed by the significant improvements in accuracy and convergence offered by FedQS. From the server-side perspective, the server maintains only simple state table containing two integer-fload key-value pairs compared to baseline approaches. Operations on this table execute in O(1) time, ensuring that server-side scalability remains unaffected as the number of clients grows. Thus, even with large-scale client participation in federated tasks, FedQS maintains efficient performance on the server side.
C.3 System Efficiency Analysis
This section details the efficiency analysis of FedQS's each module and discusses the potential optimizations to enhance the computational and communication efficiency.
C.3.1 Breakdown Analysis
Table 7 provides a comprehensive breakdown of the computational latency, communication overhead, and memory footprint induced by FedQS's s core mechanisms. These measurements represent averages over 400 global rounds, with consistent patterns observed across various experimental scenarios and client populations. The computation overhead remains minimal, with similarity scoring and feedback processing introducing only about 4s of additional latency per global round. In terms of communication, each client transmits merely 4B uplink (similarity score) and 1 1-bit feedback, while the server broadcasts 12B downlink (averaged thresholds). Memory footprint also negligible: client-side storage for scores and feedback totals under 5B, and server-side state tables require only about 7. 7.8KB for 100 clients.
Table 7: Computational latency, communication overhead, and memory footprint of FedQS compo- nents (averaged over 400 global rounds).
Computational
Communication
Memory
Operation
Cost
Cost
Footprint
Calculating pseudo global gradient (Mod(D)
13.73s
42.8 42.8MB
Calculating similarity scores (Mod
2,23s
0
4B
Feedback signal calculation (Mod@)
1.97s
0
bit
Feedback signal communications (Mod@ Mod3)
0
Uplink: 1 bit
0
Updating aggregation status table (Mod()
0.27s
0
7,8KB
Uplink: <4B
Status table communications
Downlink: 122B
C.3.2 Computational Overhead of Divide-and-Conquer Strategy
We conducted disaggregated experiments to rigorously quantify the detailed additional runtime introduced by FedQS's divide-and-conquee strategy. The procedure is partitioned into three critical
23

---

phases: pseudo-gradient computation in Mod client classification in Mod@; and state-table updating Mod Table shows the average time consumed per global round for each step FedQS when training ResNet- 8 on CIFAR-10, 10, where "Average ratio for Mod@" represents the ratio of the time spent calculating the sneudo-gradiem in Mod() to the average time required to complete one global round.
Table 8: Computational overhead breakdown of FedQS components when training ResNet- on CIFAR-10 under different distributions.
# Chient
Data Dist.
Total Time
Rod'E Time (5)
Nod Ratio
Rod Time (8)
Mod Ratio
Nod Time
Modial Ratio
x=0.1
44.98
6.69
14.87%
2.17
4.82%
0.13
0.29%
50
x=0.5
46.59
7.43
15.94%
2.89
6.20%
0.14
0.30%
x=1
43.79
7.02
16.03%
2.33
5.32%
0.09
0.21%
x=0.1
80.97
14.14
17.46%
4.51
5.57%
0.23
0.28%
100
x=0.5
83.41
13.93
16.70%
4.22
5.06%
0.26
0.31%
x-l
82.77
13.11
15.84%
3.96
4.78%
0.33
0.39%
x=0.1
200
x-0.5
152.05
27.80
18.28%
9.51
6.25%
0.47
0.31%
X=1
153.93
17.34%
8.97
5.82%
0.45
0.29%
Average
16.21%
5.41%
0.30%
C.3.3 Potential Optimization
FedQS employs GPU-accelerated training with streaming aggregation to handle large models effi- ciently. This design overlaps communication and computation, boosting throughput for resource- constrained clients. Computationally, optimizations are available for the client-state table (caching scores, low-rank approximations) and the primary overhead of pseudo-gradies computation. Stag- gered client reclassification (i.e., reducing the frequency of client reclassification every 5 rounds) reduces overhead by 63.6-72.7% (1.4-5.2% accuracy drop). while stratified sampling of clients (i.e., 20% of clients per round re-evaluates the role) reduces by 53.2-57.5%% (2.2-4.1% performance loss). These strategies offer configurable tradeoffs within FedQS's modular design.
C.4 Limitations of FedQS.
Although FedQS mitigates both the instability of gradient-based methods and the suboptimal con- vergence model-based approaches, introduces a few oscillations in model aggregation mode. Mcanwhile, we introduce three hyperparameters a, mo, k in SAFL to propose FedQS. Despite the discussions in Section 5544, this raises more difficulties in implementation and reproduction. A poten- tial future work involves the automatic adjustment of these hyperparameters, therefore enhancing the flexibility and accessibility of the FedQS.
Broader Impact. This work proposed FedQS, a comprehensive and versatile optimization tool that enhances the performance of gradient aggregation and model aggregation strategies across multiple metrics. Additionally, we conduct a theoretical analysis of FedQS to demonstrate its superiority. We have identified no potential ethical impacts noticeable negative social impacts associated with this work. On the contrary, FedQS serves as compatible framework capable of optimizing both aggregation strategies in diverse scenarios, leading significant performance improvements. This contribution advances the field by offering a practical and theoretically grounded solution for enhancing SAFL systems.
D Evaluation details & More evaluation results
D.1 Details of the dataset
CIFAR-10 (39 CIFAR-10 is widely used benchmark dataset for image classification tasks in machine lcarning. This dataset consists of ten labeled classes of images. Each class corresponds to 6,000 images, with 5,000 training samples and 1,000 test samples. In our FL scenario,
pursued benchmark [46), assuming that all participant data distributions follow the distribution Dir& (x) based categories, which can be represented by Equation 13 Each participant
will split their local dataset into training and validation sets with an 8:2 ratio.
N N
x% II
Dire(x)
-
(13)
I1
P(x))
k.
24

---

where k represents the k-th client, 2 is a parameter controlling the distribution, Pk.; represents the probability of having data from the i-th class and r(x)) the Caamma-functoon We primarily considered three levels of data distribution heterogeneity in our experiments: x = 0.1, 0.5, and 1.
Shakespeare M.. The Shakespeare dataset is text corpus used for natural language processing tasks, comprising excerpts from The Complete Works of William Shakespeare. We embedded 80 unique characters, consisting of 26 uppercase English letters, 26 lowercase English letters, 10 numeric digits, and 18 special characters, into corresponding labels. Notably, we referenced benchmark 47 and modeled the dialogues of distinct roles in various scripts within Shakespeare as a heterogeneous distribution. Each participant was assigned data drawn from dialogue lines of different characters across diverse scripts, and the roles used by different participants do not overlap. Each participant will split their local dataset into training and validation sets with a 9:1 ratio. We primarily considered two levels of data distribution heterogeneity in our experiments: each client has roles (i.e., 200) and 6 roles (i.e., R = 600).
UCI Adult (Census Income) 41 We refer to paper [1] utilize the US Adult Income Dataset, a real-world benchmark dataset, to evaluate the efficacy of each algorithm in practical task. The dataset comprises 48,842 records and 14 attributes, including age, gender, education level, marital status, occupation, working hours, etc.. We primarily predict whether an individual's 's annual income exceeds $50,000 based on demographic attributes from the census, assuming that each participant is associated with specific demographic characteristics (gender or ethnicity) corresponding to their income data. The distribution of data quantity among clients with the same characteristics follows a log-normal distribution Log- NN(0, )) Each participant will split their local dataset into training and validation sets with an 8:2 ratio. For the heterogeneous distribution based on gender, we primarily considered = in our experiments. For the heterogeneous distribution based on ethnicity, we primarily considered a = 0.9 in our experiments.
D.2 Details of the models
ResNet-18 (38]. We employ the Residual Network (ResNet) architecture, a class of neural networks introduced by He et al. (38), which incorporates residual blocks to alleviate vanishing gradients. Specifically, we utilize ResNet-18, a compact variant within the ResNet family, comprising 18 layers and four residual blocks. Each residual block consists of two convolutional layers with 3x3 kernels and stride of 1, enabling efficient feature extraction and propagation through the network.
LSTM [40]. We employ the Long Short-Term Memory (LSTM) network architecture, a subtype of Recurrent Neural Network (RNN) optimized for processing and learning sequential data. In our experimental setup, we employ a straightforward LSTM model comprising an embedding layer, an LSTM recurrent layer, and fully connected dense layer.
FCN. We employ a Full Connection Neural Network (FCN), a canonical deep learning architecture. The FCN utilized in this paper comprises two fully connected dense layers, each enabled by the ReLU activation function to introduce non-linearity and improve feature extraction capabilities. Additionally, we incorporate a dropout layer to mitigate overfitting and enhance the robustness of our model.
D.3 Details of hy perparameessss and resource distributions
To ensure reproducibility, we provide comprehensive summary of the default hyperparameter configurations for FedQS, which are used across most experiments in this study. The default settings in our experiments are as follows: number of participants N 100, initial local learning rate Noo = 0.1, learning rate bounds a = 0.001 and 3 = 0.2, learning rate adaptation rate a = 0.002, initial momentum mg 0.1, momentum adaptation parameter
0.2, global epochs T 400, local epochs E = 2, minimum number of updates for aggregation K 10, gradient clipping threshold G. 20, and momentum clipping threshold 0 0.9. FedQS introduces three additional hyperparameters 0, My, and w-hhich is comparable to the number used in recent state-ofe the art methods 18 [5] These parameters control the adaptation rate of the learning rate, the initial momentum value, and the momentum adjustment rate, respectively. As illustrated in Figure 5 the method demonstrates stable performance across wide ranges of these hyperparameters (a E [0.001, 0.005], mo E [0.01, 0.1), l [0.001, substantially reducing the need for extensive
25

---

tuning. This behavior aligns with common federated learning practices and improves the practical usability of FedQS.
Notice that the simulation of poor communication quality and weak training performance is inde- pendent of the dataset and model selection/size. Instead, it is governed by actual client-specific configurations that determine resource demands and execution time. Our base experiments emulate SAFL heterogeneity with 50x speed differentials between the fastest and slowest participants, later extended it through additional tests under 1:20 and 1:100 resource ratios to comprehensively validate FedQS's s robustness across diverse environments.
D.4 Details of baselines
In this section, we will introduce the details of the baseline algorithms.
FedAvg and FedSGD (. These baseline algorithms the basic aggregation algorithms im- plemented into the Synchronous and Semi-Asynchronous FL framework, without any additional optimization or improvement.
SAFA (31]. This baseline algorithm employs caching mechanism to store updated models for each client. At the beginning of each aggregation round, the server updates the cache by incorporating the frequency local update data uploads from each client. Subsequently, the server performs an aggregation operation on all the cached models and updates the cache once again after completing the aggregation process, taking into account the usage pattern of the latest local updates.
FedAT [18]. This baseline algorithm is a hierarchical SAFL framework, which synchronizes local model parameters within each layer and asynchronously updates the global model across layers. FedAT proposes a new weighted aggregation heuristic optimization target, where FL servers update different tiers' aggregation weights based on the statistics of different tiers' model aggregation frequencies, thereby balancing different tiers' model parameters.
M-step-FeeAAsne (37.. This baseline algorithm introduces novel metric, model deviation degree, which is computed as the inner product between local model parameters and global model parametens. This metric serves key component in the aggregation process, where it used in conjunction with local update frequency to determine the weights assigned to different model parameters during aggregation.
FedBuff [6]. This baseline algorithm employs a differential aggregation method, a variant of gradient aggregation, which assigns weights to each updated data. If the staleness of the difference update is high, the corresponding weight becomes smaller.
WKAFL 15
This baseline algorithm extracts effective information from outdated gradients by leveraging recently updated gradients. calculates the weighted aggregated parameters by calculating the cosine value between the unbiased gradient and the locally updated gradient to accelerate aggregation and stabilize the convergence process.
FedAC [20]. This baseline algorithm uses temporal gradient evaluation to assess client weights, employs proactive weighted momentum for adaptive server updates, incorporating ane-gnaieed gradient correction functionality designed by SCAFFOLD 3 to address the issue of client drift caused by heterogeneous data.
In non-lID scenarios, DeFedAvg employs uniform sampling with replacement to select clients. Each client continuously receives the latest global model from the server and overwrites its reception buffer with the incoming model. Regardless of participation in global iterations, every client continuously performs local training. The server accepts delayed updates without waiting for participating clients to complete training based on the latest global model.
AvF [42].
This algorithm treats the differences in client model updates pseudo-gradients and employs an Adam-like update scheme to adjust the global model. Building upon FedBuff's 's local asynchronous training mechanism, FADAS retains the design philosophy of concurrency and buffer size to enable flexible control over the number of active clients and the frequency of global model updates.
FADAS 43).
FL 44 This study confirms that asynchronous delay effects are amplified by highly non-III) data distributions and addresses the resulting client drift issue by employing a server-side mechanism
26

---

that retains the most recent updates from clients and reuses these cached updates to calibrate the global model.
D.5 More experimental results
Table shows the discrepancy (T, -Ty) results, representing the convergence stability. Table T0 shows the results of FedQS and two foundational algorithms, FedAvg and FedSGD, under different SAFL system settings. Table presents the average experimental results of FedSGD. FedAvg, and FedQS under various learning rates. Tables 12 and 14 present the average results of FedQS under various settings of hyperparameter a, mo, and k, respectively.
4000
2000
100
200
300
400
In the RWD task (Figure 41.. WKAFL exhibits extreme overfitting loss function curve, indicating poor adaptability of WKAFL to the RWD task when the local learning rate is set to 0.1. The adaptive learning rate adjustment module of WKAFL also contributes to the overfitting of the learning task. Figure shows the experiment results of WKAFL under various local learning rates. We can see that when the local learning rate is reduced 0.001, WKAFL no longer exhibits overfitting behavior.
Epoch (Avg)
Ir-led
In-led
Im-le2
Ir-1c4
Figure The impact of learn- ing rate WKAFL's loss in an RWD task (Gender).
Figure 7 shows the loss of FedQS and baselines under other tasks, which is supplement of Figure 4 Figures 8 and 9 show the comparison of the accuracy and time latency between FedQS and each baseline within model aggregation and gradient aggregation strategies, respectively.
Oscillation a metric to measure the occurrences when the accuracy of the global model in round is below that of the previous round f 1 by specific threshold (21). Figure 10 shows the number of total oscillations under different thresholds when using ResNet- to train CIFAR-10.
Figure 1 depicts the performance comparison of FedQS between with and without momentum
terms. Figure 12 depicts the performance comparison of FedQS between with and without feedback mechanisms.
Fediog
PeGAT
SABA
M-etip
Fudgg
F-RSGD
WKKFF
FedBaIT
FaIAC
Fw00
0.55
0.50
0,50
200
300
300
Loss
200
400
400
200 Epoch (SGD)
400
200 Epoch (SGD)
400
Epoch (Arg)
Epoch (Avg)
(a) CV Tisk (z = 0.1)
(b) CV Task (2 = 1)
(e) CV Task (2 0.1)
(0 CV Task (2 =
4000
5000
Loss
Luns
2000
Po-g
300
Loss
1.50
200
sún
22500-
200
300
01
0:
200
400
200
400
200
400
200
400
Epoch (Avg)
Epoch
Egoch (SGD)
Epoch (SGD)
(6) NLP Task (R 200)
(d) Real-world Task (Ethnicity)
(g) NLP Task (R 200)
(h) Real-world Task (Ethnicity)
Figure 7: Loss of FedQS and the baselines under other tasks. The left four subfigures ((a)-dd) based on model aggregation, while the right four ((c)-(h)) are based on gradient aggregation.
E
Proof details
We will first give some basic notations the FL tasks. Note that in the following part, all || symbols represent Lg norms and < <..>> symbols represent inner products. In order to simplify and save space, have denoted that V VFg.e VF, (w V.F.s
FF,e( (wff-r)= & V.(W(.)))
27

---

Laberry Camparaen.
Accorary: Time Larey Comparteon
191
26
250
Teig5 Time
(a) FedQS-Ave Avg FedAvg 0.5)
(b) FedQS SAFA 0.5)
Comparion
Accurncy Time Larmay Campasisen.
Avg vs. FedAT
FedQS-Arg vs. M-step (ir
Accuray/Tine Lakeney Comparisnn.
190
150
203
250
300
Twigt Souwsray
Bodking Aumrnnyy
bedgh Tian
Fwiteg
Pwigs
Tixe
(c) FodQS-Avg vs. FodAvg (o = 1)
(f) FedQS-Avg vs. SAFA (x
1)
Accamee/ Lafenc' Compatison.
Accurscy Time Larmcy Camparisen.
130
150
200
259
300
350
25
200
3.5
28
250
300
350
2o135 Accessy
Phall Accenry
Tolib Tene
Po Time
Mtdley Accenuy
1esk5 Time
Korp Ubee
(g) FodQS-Avg vs. FodAT (z 1)
(b) FedQS-Avg vs. M-stop (2 1)
Figure& 8: The comparison of accuracy and time latency between FedQS-Avg and the baselines with model aggregation strategy under CV tasks.
Table 9: Convergence stability comparisons between FedQS and baselines.
Algoritims
Metrics
Tasks
FedAvg FedAvg (SFL. (SAFL)
FeSGGD FedsOD
FedAT M-step FedQS- Avg
FedBuff WKAFL, FedAC FedQs-
(SFL) (SAFL)
259
0.5
22
33
29
40
20
20
45
5
45
322
24
T', T'
27
0
31
17
5
40
11
110
14
epoch)
R 200
0
11
7
23
25
0
R
600
0
4
15
0
39
7
Gender
12
0
128
48
202
26
Ethnicity
24
151
114
0
45
77
27
251
178
48
31
In column "Tasks", ", is the parameter of the Dirichlet distribution within CV tasks; N is the number of roles within NLP tasks; Gender and Ethnicity are the data types within RWD tasks.
The target accuracy of convergence stability is to 80% of convergence accuracy in CV and NLP tasks and 95% convergence accuracy RWD tasks.
28

---

100
155
200
250
1000
203
250
Fallgs Aucuauy
Fadgo
TuDGO Tax
FudgsAscaag
Faggs
WEATL Tix
(a) FedQS-SGD vs. FodSGD (o 0.5)
(b) FedQS-SGD vs. WKAFL (2 = 0.5)
Accurncy Timee Laiency Comparion.
Accuracs Time Latency Comparion.
Opech
Tpech
(c) FedQS-SGD vs. FedBuff (i 0.5)
(d) FedQS-SGD vs. FedAC (z 0.5)
Accuragy Labeay Comparison
Aecrra//Tle Latency Comparion
24
100
300
250
100
225
255
Fmighh Aveunay
Fedli Auenaiy
Fubbi Tam
Fuilgh Taigg-Aaeeee
WILAF Aueuaay
Failh
WEAFL Ta
(c) FedQS-SGD vs. FedSGD (ar = I)
( FedQS-SGD vs. WKAFL (o. I)
Acceracy/Tine Comparison
Accurace Temer Latency Comparison
122
200
Fedlict Avcuutyy
Todgs Tims
FLANC Accessyy
Faays Tims
TeatC Tlma
(g) FedQS SGD vs. FedBall (z 1)
(h) FedQS SGD vs. FedAC (2 1)
Figure 9: The comparison of accuracy and time latency between FedQS- SGD and the baselines with gradient aggregation strategy under CV tasks.
Table 10: Average performance of FedQS, FedAvg, and FedSGD w.r.t. the number of clients and resource distributions.
Tasks
50
200
Metrics
1:20
1:50
1:100
1:50
Fed
FedQS
Fed
FedQS
Fed
FedQS
Fed
FedQS
Avg
SGD
Avg
SGD
Avg
SGD
Avg
SGD
Avg
SGD
Avg
SGD
Avg
SGD
Avg
SGD
M1
70.1 77.4
79.2
80.7
80.6 81.1
83.7
84.8
49.4
74.4
64.7
80.1
61.3
77.7
65.9
82.9
M2
123
57 118
44
108
57
102
50
190
158
182
123
183
145 138
104
M3
0.0
37.0 3.0
26.3
1.0
15.0 4.3 5.0 0.0
7.3
0.3
3.0
0.7
4.0 1.66
3.0
In Metrics, MI means Accuracy (%), M2 means Conv. speed (# epochs), and M3 means # Oscillatioos.
In the table, N 200 means the task has 200 clients, and 1:50 means the fastest client exhibits a training speed 50 times that of the slowest one. "Fed + Avg" means FedAvg. The threshold used calculate the number of oscillations is set to 15. The target accuracy of convergence stability is set to 80% of convergence accuracy.
Each result is an average value of three experiments corresponding to r 0.1, 1 in CV tasks.
29

---

If Oxcillations
18 Oscillttonn
17.5
15.0
12.3 10.0
Feshin
FRAKT
Mesipp
Oscillations
10-
12-
M--tep
SAPA
7.5
SAFA
5.0
30
20
30
Threshold
Threshold
Threshold
(8) Avg (or 0.1)
(b) Avg (e = 0.5)
(c) Avg (e
# Oscillations
100
Ossillations
PedBUp Prebbuf
I Oscillations
Fad9CD
Pedtlit
60
FolBull
8
FadAC
WKATT
40x
FedAC
20
PolAC
Fedgs
FoltS
To
30
30
20
30
Threshold
Threshold
Threshold
(d) SGD 0.1)
(0) SGD (2r
0.5)
(1) SGD (cr
Figure 10: Statistics of oscillations under various thresholds when applying the ResNet-18 model to the CIFAR-10 dataset with 0.1, 0.5, 1.
FedQS-Arg with Momentum
PedQGi-Ag wio Momentum
FudQS-SGI with Momentum
FeeQS-SGD wi Momsatum
Acoureyy
303
3.00
369
Epoch
(a)
0.1
(b)
Figure 11: Accuracy and Loss of FedQS with without Momentum terms under CV tasks.
Arcimsy
100
200 Ezech
300
45c
Eyocch
Specch
TAICS
Pakch
Tubeeca
(a) Accuracy 0.1)
(b) Accuracy Car 0.5)
(c) Accuracy (ar
10-
2
Thindool
Paliig
Palie
(d) Oscillation (2 = 0.1)
(e) Oscillation (2 0.5)
(0 Oscillation (ar =
Figure 12: The impact of feedback mechanism global accuracy and oscillations in CV tasks (x = 0.1, 0.5, 1).
30

---

Table 11: Impact of different learning rates on FedSGD, FedAvg, and FedQS's performance in CV task (r 0.5) and NLP task (R 600).
Algorithms
Metrics
Task
Learning Rate
FedSGD
FedQS-SGD
FedAvg
FedQS-Ar
170 0.1
83.9
86.1
73.7
80.3
= 0.05
84.9
85.6
72.8
77.1
0.01
81.5
82.9
58.1
67.1
Accuracy
170 0.001
61.1
80.7
40.9
61.4
1/o 0.1
49.6
52.5
45.3
50.1
NLP
0.05
46.3
51.6
44.7
46.9
0.01
35.9
48.7
30.3
41.8
T/o 0.1
86
82
144
109
CV
T/0 0.01
78
149
90
84
157
121
Convergence Speed
0.001
131
129
161
123
(# epoch)
0.1
67
50
99
78
NLP
T/0 0.05
68
102
170 0.01
128
145
Table Impact of different changing rates of the learning rate on FedQS's performance in CV and NLP tasks.
Metries
Algorithms
Tasks
Value
Convergence Speed epoch)
Accuracy (%)
# Oscillations
0.001
74.02
110
6,9
0.002
74.14
108
7.6
CV
0.005
73.88
113
8.2
71.65
124
10.3
FedQS-Avg
0.001
49.88
93
3.6
0.002
49.75
91
3.5
NLP
0.005
49.56
95
3,9
0.01
43.25
103
3.6
0.001
80.63
84
4.3
0.002
80.59
81
4.0
0.005
80.44
83
4.7
0.01
74.83
92
6.3
FedQS-SGI SGD
0.001
50.88
46
8.3
0.002
50.76
48
8.5
NLP
0.005
50.13
53
8.8
0.01
48.36
56
9.4
Table 13: Impact of different initial momentum mo on FedQS's performance in CV and NLP tasks.
Metrics
Algorithms
Tasks
Value
Convergence
Accuracy (%)
# Oscillations
Speed (# epoch)
0.1
74.14
108
0.2
73.26
112
7.9
CV
0.3
72.48
116
7.6
0.4
70.69
123
7.8
FedQS-Avg
0.1
49.75
91
3.5
0.2
49.44
93
3.6
NLP
0.3
49.03
96
4.1
0.4
48.46
113
5.3
0.1
80.59
81
0.2
80.43
82
4.3
CV
0.3
80.34
82
4.6
0.4
80.06
86
3.8
FedQS-SGI SGD
0.1
50.76
48
8.5
50.43
46
NLP
0.3
50.22
49
8.9
0.4
50.13
48
8.8
31

---

Table 14: Impact of different changing rates of the momentum k on FedQS's performance in CV and NLP tasks.
Metrics
Algorithms
Tasks
Value
Convergence
Accuracy (%)
# Oscillations
Speed (ff epoch)
0.1
74.25
108
4.3
74.14
108
4.0
CV
0.3
74.03
116
4.6
0.4
74.09
123
4.9
FedQS-Avg
0.1
49.65
93
3.6
0.2
49.75
91
3.5
NLP
0.3
49.76
100
3.4
0,4
49.66
112
3.8
0.1
80.77
83
9.4
0.2
80.59
81
7.6
CV
0.3
79.85
92
7.1
0.4
79.33
116
8.4
FedQS-SCO SGD
0.1
50.99
46
8.3
0.2
50.76
48
8.5
NLP
50.41
53
9.1
0.4
49.87
66
9.6
Additionally, when performing theoretical analysis, we also refer to the classic paper 355 and assume that the server uses an ideal dataset (based on balanced, independent, and identically distributed data from all participants) to train an ideal global model (which is just used to theoretical analysis and does not exist in reality), with the training process defined by Equation 14
W 9,e-1 V F' (wi
g.e-1).
(14)
g.c
where we define wp - wg. Fg satisfies Assumption A.1 and F. satisfies Assumption A.2
It's evident that we have the following relation between the ideal global model and the real global model:
mt E
Wg 9.0
(15)
Then, based on the Assumption A.2 and A.3 we can give the following lemma:
Lemma E.1. Let 0; := (w)) (w == FF(W)) Given the Assumption A.7 and A.3
then any one of the following conditions is sufficient to guarantee FIIVF, (wt < 8 (1) Global Optimum: F g (m)')
(2) Locaa--prrmmeter closeness: there exist constants en and 8 (W( < 32, and the following numerical
such that El[w / 112 2, E.
relation holds: 82 + e G < 3. (3) Negative correlation: The cross-term satisfies Blo;, b.) S
- |B|bb]|2, which may occur local minima/saddle points under extreme data heterogeneity.
Proof. Items (1) is immediate from algebra. We briefly show (2) and (3).
For (2): First use the triangle inequality
IVF (w
| F (w VF, + (F(( - + VF VF - (F((4))++ (VF
| F, (
V
Square both sides and apply the inequality (u+u+w) < 33
+ w²):
(VF.(WW)) 11 < - V -FF + +I[F(((())))
Take expectation over clients/data randomness and use the assumed bounds. By definition of 8 have VF VF( By L-smoothness and the bound on parameter deviation.
EIVE((
wi L
L3
< L 2
32

---

Finally use B| (() S G. Combining these yields
V =3 + 1. Co).
Thus if 8" 12 C S 82/3, the claimed inequality F ( ) v 8 holds.
For (3): By definition,
IV |1 = ||a, bell ||a.11= |b: 2(a bz)-
Taking expectation and using |||a:|| 2 8 and the assumed cross-term bound gives
E| ( v 8² + Elbb.l1 + (- =b)b)))))) = =
Remark F.2. Condition (2) decomposes the sources that contribute to the magnitude of V ( (i)
heterogeneity the ideal point (6²) ), (ii) parameter drift of local models (I.2e and (iii) the intrinsic size of local gradients (. This decomposition is useful in practice for designing communication or correction mechanisms.
E.1 Proof of Theorem A.4
Denoted (() as the maximum number of clients that execute the momentum update at global round we begin the proof with two lemmas:
Lemma E.3 (Ideal global model difference). Given V =
and the ideal global model trained in global epoch t, the difference between the optimal can be bounded by:
28 8²41
6B8
+ +1)
Blllig w" w01 S V'
311
+
F2282
2
2,32
E
+
WE((
(m
y'v 71
(16)
j=1
T
V
(w
Proof. By the definition of the ideal global model, add term and get:
1
w/
E
<
|lu
11
F
g.c)
1=1
VF(WW,e 1-1
w
+
P1
7
1=1
e=1
Pt
11
V.
1gg
VF wit 2
K
E
K
E
E
+ 2(w
1)g
Fr (w
Σ
P:
17
Viil
nl Σ
v
(wt
(,
1=1
(17)
33

---

Consider the relationship between w/y1 and 20 1, we have:
K
w=1
=
1100g
72
Fg g 1 (1 w Σ
Pi
K
+ (w ie I|I?
P1
m
1=1
K
E
E + -1g
Pi
v F g
1=1
6=1
K
E
+ +2(mg
P1
(m)
yVVi( (e + V.i }}.
1=1
e=1
P=l
K
Σ
p6
T
V.WWw ) + 11
F i (,,
E
K
+ +111g
TF ( - -w" - >
P1
Σ m
(F )
c=1
i=1
e=1
K
E
E
1 VF ) ++1 11
V
g. 11 g.c)).
1=1
c=
c=0 1
Therefore,
||00 w21
K Σ
||00 -w-"'" 12111 + +111gg
F
(
(1))-1
Pr
1/
m
c=1
1=1
e=1
E
+ +2(mg 9
w,, 119
g 9.6
Pi Σ 1
m
E
E
+1
Pt
1h
V.
1.0
) + 1
F
(i 112
(18)
1=1
K
E
+ 2(
w"
pi
F
+ 1a
V Fg (w) g,
1=1
e=1
e=1
+ 2(1
VF g
(W--1)
Σ P:
1
(m,
D'VF. (w.oo)))
i=1
K
> P4
7:11
) }+ 17g
VF (Fg(Wt ((
For the 2nd term:
E
K
E
||7g
VF
11
Pi
11
y
1=1
c=1
<
8a1
g.e
+
P1
1/
m
IV
(19)
E
K
- 232
9
g.c
Pi
(m
VV )))
1=1
34

---

Based on B5|. we have:
E
K
E
V g
(T0gee)
- Σ
112
(m, -
)
i=1
e=1
r=1
E
S S +
m
K
2,3
g,
pi
m
I'VF(W
(20)
E
I 5000060" + Ellm
mm
YVF
E
K
- 2,3
m
(VF, (1)
F=
m
(VR
For the 3rd term, using a variant of reversed Cauchy-Schwarz inequality 4 49 50 T= 1 and 7 3
with 7 = B and
< 1, we have:
E V
K
E
2(10 w², F7
W (1-1
P4
71
(m)
eml
km1
cml
ym
E
2(
w³, 77
g.
2(
9
w²
Pc
(mg ) (VF
E
2,82 R
< ||00 w1 + ||
Fg
W
(--11 - 1|1
n.c
,3 +1
9
w
11
e=1
28²R R
E
S1
||
w01 + ||
F
(w)
g.e 112
82 +1
g
(21)
Then.
B
w² :1g
gl g.e
Σ
Pt
1/1
(m; -
(22)
282R R
$ (1
E 1 w
1111 F382288
B2 +1
For the 4th term:
35

---

11g 2
g (1 g,0)
Pi
7/
K
E
P:
1/3
I|1 + 11
Fg 2
e=1
e=1
K
E
E ),
VF
VF, y 15 (,c)))
e=1
e=1
s
n
W
+ )11
Σ
%/
:-1
( )11 + >>
(P. FFg
c=1
<=1r=1
(23)
Then based on
35
K
E
Pi
1
) }+ 11g
V F (T g.c) )1
2=1
eml
S 0=000 Ellmm
(w
Σ M
Σ
PEE ). [Fg
E
= EE
(w 0113).
1,e
(24)
For the 5th term, using AM-GM inequality and Souchy-Schwarr inequality, we have:
E
2 9
w
Pi
1)
) +1g
V F (e))))
E
E
< 1000
1
w01l
+
1
Fi 111 + 11
V n g.e )1
(w:
K
F Mgg
Pi
11
F.
VF
g (ūtt (w))
(25)
1=1
6=1
e=1
E
|100 9
w011
+
F (W )112 +11m
F
- 1-1
K
E
E V. ) 11 Σ
+
Ps
Fg ()))))
1=1
c=1
e=1
Then, taking expectation, we have,
36

---

K
E
E|2
Pj
--1
) 1
11 Σ
FF Ti g.,)))l
i=1
c=1
e=1
2 Blll 1g
- w"
w01 + 3 E²
v VF
(w 11
||1
(26)
E
E
Pb
17
V
) 1,
F. 1
E
=
Bl|
20
- w0
11 3 E28 + E1| Σ
( ).
For the 6th term:
K
E
(1g
Fg
g.e
1-11
Pi
+ fly Σ
V
F (T
im 1
eml
eml
-1
9.0
Pi
7/
VFi(w,,e )} 2
Fg 11 (g Tl Σ
Fg (6 ()))))
K
E
E
<
2m,
VE )} + 2 Σ
g.
g
g.c
(27)
Then, based on 335
we have:
E E[2 m 9,0
K
E
F
Th
VR
+ nl Σ
F
y (it ))
e=1
e=1
e=1
E
E
(28)
< 2m
P
3 3( (1
VFL + B
V F
[ g,e
)|
e=1 Y=1
1=0
6=1
< F
For the 7th term:
K
E
E ) nl Σ
2(-
Ps
1
m
Σ Pi
Σ
7
VF(
VF
Ff (e))
1=1
1=1
r=1
t=1
K
E
K
E
'VFR(W
VVR.(1 )}
2
mm
Th
1=1
e=1
6=1
K
E
2
P4
11g
VF (tt,e))
VF
1=1
e=1
K
E
-2
Pi
11
m
(F
1=0
E
E
+ 11m
(m:
/VF M| + ll
V (i ie )|2
r=1
e=1
(29)
37

---

Then we have:
E
2
Pi
11
(
i=1
c=1
r=
Σ
P4
Fi
+ 73
K
E
E
- 2
P4
m
(VVF
V (
(30)
i=1
1=0
E
+ 1
(m)
y'
VV
( + Bl
V F 11
S Bilm
ΣΣ
(m)
yVR(W??
+ Bll
V P. f )11).
To sum up, have:
E 1 11a1
E
< E 10-- w" 11 + B1I
VV (IP
mm
e=1 r=1
2,32 R
+ +(1
EE T6
w
100] +1 38 + E28
B2 +1
E
E Ell w 1 E28 + +E||
+ +
(1 1.
F
[w
||?
e=m
F
+ 228
(w 11 + Blll
ΣΣ
(m,
y'V
(e
).
e=1r=1
(31)
Combining like terms:
2,5 R
B - "" 1131 < (3
EE 1 - w
w0'13 13
g2 +1
E
E
+ 3E In
(m)
I'V
(w)
V
F
(w)
e=1
(32)
3 Take summarizing with V H-1 < 3
2H-3 we have:
(B2 + 1)
B||ly w" || < b'
w/ 101 +
2.
2 - 2322
E e
+
w WEll
(m)
) 'VF (V (1
(33)
j=1
+
Σ
y E
V
j=1
1=1
38

---

where V= (3
2 R
11+1
Lemma E.4 (global model one-step difference in gradient aggregation). Given the real global model w and its one-step nearby global model w/- the expected square norm of the difference can be described below:
E Σ 7h
|/06g '12
S 2
Σ (m))
(n))"VF(( (34)
Proof. From the Equation 3
we know:
K
E
w
m
V
V.
+ (F
(35)
1=1
e=1
1=1
Therefore, we have:
K
w w
1
Pi
m +V
(36)
Therefore, it's easy to get the following equation since we normalize pæ such that Et= P:
1 w
112
g
g
K
E
=|1
V V. (w
VF
1=1
e=1
1=1
K
E
Σ
F (w
11
11
P/
1
i=1
6=1
t=1
t=1
K
P:
1
V
(w
+
Σ
Pt
1
T
m
m
(1) 1
(w)
E
K
E
(37)
2
111
(w
Pi
(m V Fi( (w)
e
E
(m))
V V (w,
1=1
e=1
+ 2
Pi
Pj
mm)) )r(
VF,
(w he-m))
E
E
< 22
VF
(
+
2|
V
Then, based on the Lemma E.3 and E.4
we can easily proof the Theorem A.4 as following:
Proof. Based on Assumption 1, we have:
39

---

L
F( - F* S (VF', F(w())
+
2 Ellug - w w11
(38)
Since F* is the global optima, we have V 0, therefore:
F(w() - F
L
x 2
|/0 - w0
L
$
|mu g
(w)
w |
2
(39)
L
E
1uug w
1 + 11
V Fg (1 g,e) - -wig -
2
S 2L|l|/
112 2L mg
F Tit 911 + Li1
w" w01
Then, based on Lemma E.1
E.3 and E.4
we have:
B[F(w()] FM
s
22| w/ wy +191 2L Mg
V F W )19)
LIE
w w=113
LVVBIllu w² 1191 W,
(40)
where 4 [2
63
F282 = (3
2 KR 3+1 and
20
W = 4L
(w 1) 4LE 17
(m
(F
E
W3LE
V
Fi
( (
(41)
j=0
+
2L
mm
0=0
Based on Assumption
A.2
we can further bound the gradient expectation term W by:
W s 4L3 + 4L3 A Σ V'3LS + Σ 222233RQ(1)))
3=0
1=
(42)
(8 L)(RQ(() + 3E²)
[ALE + 4LRQ(())
232R 232-3
E.2 Proof of Theorem A.5
Denoted Q(1) as the maximum number of clients that execute the momentum update at global round t and 0 < g P S S 1, we begin the proof by two lemmas:
40

---

(R+ aadd the ideal global model 4²+1
Lemma E.5 (Ideal global model difference). Given V= trained in global epoch t, the difference between the optimal can be bounded by:
Bl -w-wwwlp 112] S V 2/ - w= ]1²]
1 D
8,3 E²8
1 v
E
WE
V (w ( !
(43)
Σ
WBilmn
1-1
Σ
m
(VF
e=1r=1
Proof. Based on the momentum update equation
we have:
E
+
w
W1,0
17
c=1
(44)
E
W
'V he-p) + V.((W + 7g
[w
V F (Wg.e..
e=1
We add zero term:
100
201
n7
F
( g,e) 11
c=1
E
Pow
1/g
g
(w) gie)
E
(m) 1- V +
Pa (1g
1k
(45)
11g
9 (igie
))
13g
V ( w1
e=1
Pi(Wy
m
(m)
V
V
(W )])
K
E
E ng Σ
K Σ
(11g
V g.
(Wgi
(w)
1=1
1=1
e=1
1=1
Therefore,
41

---

w" 112
K
K
E
Pi 12
-1 +1 Σ
p.
mm) VV + (
im1
km1
cml
2
Pi Piligg Wig
1-1
w. Σ pitk
(V V (.(
E
+
Σ
pi (Tg
F (gg.c
- 110
V (w ())
e=1
e=1
K
K
E
(46)
+
2()
Pi(Ug
-w)),
Ping
F Wgic
1=1
t=1
e=1
K
E
2()
Pe
-w"),
Pidg
F g w g,,))
i=1
i=1
E
Pills
m
(W
VFi(w
K
E
E
(1
(igle
- "19
V
Fg ( )))
For the 2nd term, we bound it by the AM-GM inequality:
K
E
Ped
(mg
( (10---1)) + VF((W
1=1
(47)
E
1| 1-1
(m) (
1-1 || + 11
V
(u
e=1r=1
Therefore,
K
E
P:m.
mm
WW + VEW 21
1=1
e=1
1=1
(48)
(m
( |P + ElIl
>
FV (111)
e=1==1
For the 3rd term, using variant of reversed Cauchy- -Shhhyy inequality --11
48
49 50
with 7 B and
I= 1/2 and m
< 1, we have:
42

---

K
PilWig
w²)
Poll
ΣD
(m
"
(F(("
i=1
1=1
K
K
E
2
Pi(w0 10g
-w0),
pilki
(m)
VV
1=1
==1
6
K
2
Pi(Wig
w²)
Σ
Pilli
1-1
(u )}
(49)
i=1
==1
e=1
2
Pi
PilWy
w0)11
p² 2,8 E²
Wg' w0')) )|2
cut 1-1
32+1
82 +
28
+ E2)
K
Pi(wg
- w0
+1
For the 4th term, using AM-GM inequality:
E 11 Σ Fg (ugle
Pi (1 Mg
Wit )112
(50)
< 2|
Ps (11g
VF g (igie
)|1 + 22
F F (w) )112
< 2ng E
VF g.ee
)112 + +n E 1 (. 11
Therefore:
E Pr Σ
Σ
V
(
Ugge ) -
F 1)
E=1
e=1
(51)
F
2 ))
E32
For the 5th term:
K
K
E
2
Pe (
- -w"),
Σ
V
Fg
Wgie )))
1=1
1=1
e=1
K
K
E
Pc P:(Wg To 1-1
=1 +
Σ
Pil
V F m
(wgie
))1
(52)
1=1
1=1
p:(Wi 1-1
-w0)11 2n E 1|
E
(Wgee 4-1
)|(
Therefore,
43

---

K
K
E
2
-w"), Σ
Pi
FF y
Wgge ))
1=1
pi Wig
-="")) -w + 2n B||
VF
Wgic )11²]
(53)
Pe (Wg
w* E282
The 6th term is as same as the 5th term:
K
K
E
2E
pi (Wg
=0),, Σ
(fg
VF
( 9. ))}]
i=1
|[[]
(
-²)]l3] + 2n F. E|| V Fg (w) )|
(54)
B||
Σ
Pe (
- 2,3² E²
For the 7th term:
K
E
2(-
Pr
(m; 1 (V + (.((((()))
i=1
K
E
E
Σ (1
V g
VF (ūt (),
1=1
c=1
=2(-
Σ
Pr(mi
(m)
+ }|
Σ Pi
v
F (Wgiee ))
i=1
K
E
2(
Σ
Pe
(m)
VV + vF Ag Σ
VF (w (,)))) ))}-
(55)
Therefore, we can easily get:
K
E
E[2(-
(1
(m
Del-ll'VVFF F: + (F((W(
1=1
c=1
(56)
K
E
Pe(1g
V g
(
- 7g
V g
(itt
))}} = 0.
To sum up, have:
44

---

E 11
w" 11
|||
Pi
Wg
)|[]
E1ll
E
E
K
+ Bllln
m
E3 B|| > Pr(Wg - -w") (57)
+ 225 + B(1
Pilggg w²
) 2
i=
2 + E
E
-13)
B2 +1
Combining like terms:
2 + E
K
B[|lg =w1
w=113]] (3
EE[1
pa (Tgg))
- +3] 18322
B2 +1
1=1
BlIl
V
mm) VV |13]
(58)
Although the sequence W w011 is not monotonically increasing, the tracing process from t is less than steps. Therefore, we can accumulate it for steps and still maintain the inequality. Then, take summarizing with V KR+E < 3
JRK step by step, we have:
Bll T w0' 311
K
< V'
|m w0 w011 + Σ
V
BB
v F.
(w 11
J=1
i=1
/=1 i=1
E M Blll ΣΣ>
im 1 V
11
==1
e=1
1- 1
". 11| +
8,32 E28
PE
v
F
(w 1- 111
1
E
[E (174
(mg
- V F, (w0
(59)
where V= ) - (R+
3441
Lemma E.6 (global model and ideal model difference in model aggregation). Given the real global model wi and its ideal global model itt at the same global epoch I, the expected square norm of the difference can be described below:
45

---

B Billiig
w - p² K (31E - + E382
E
B
(w ]11 E Σ
(60)
e=1
E
+
(m)) V (F 119
Proof. We have that:
K Σ
1|2 = Σ
Pc (ü) - 1 - -w;
(61)
1=1
1=1
Based on Equation
we have:
|1
E
E + +777 DD
||0y
W9
V Fg
Wg
(
VF + VFF(W,
c=1
E
E V Fi (w. (e,re)))1111 +13++1mm
1|00g
W
(m))
(W((
fl9
V
F g (1 1|?
c=1
e=1
2
Wg
+ m
(m)) V (e-r))) T7
V (W
7g
VF Wg.e))
E
1|00
w= 1|2 + ||09"
w" 1|2 + ||
1lg
VF (Wg.e ( )11
1| Σ
(m²)
(F
E
E
+ |
VF, 011 + 2( w,, ,77
(m²) V F (
(w.
-2
w., mi
(m!) m')'V (w (w)
e=1
+2(00 w", Mh
(F( 77
V Fg, (gie))
-2(WT)
w", 17
V (w
79
F (giee)
2(m
(m)) F 11
[F(
E
E
2(
(V
Og
Fg (wgie))
(62)
For the 3th term:
E
- 7 Σ
F Wg.e |1
S n
E (mg:e) )1?
(63)
46

---

Therefore, we have:
E fl
E
V
)
E ( S B28..
(64)
For the 6th term, using AM-GM inequality and Cauchy- Sauchy-Schwarz inequality, have:
E
( wn,
1/
m ) V Fi
(w (,,-))
(65)
S B|| 33 w w011
+
E( m
(m)) " VF (w)
e=1r=1
Similarly, the 8th term satisfies:
E
2 9
w", 178 2
ng Σ
E
E
< B 17 w 11 + E(| 173
(
"79
V F
|
(66)
e=1
e=
< Blll w
V (
S Bi| w/ 8
For the 7th term, based on the reversed Cauchy-Schwazd inequality T= 3 and m,
48
49
50
with y 3 and
< 1:
E
25 R
2 w", m
E
-w"113
(67)
82 +
+1
Similarly, the 9th term satisfies:
E
E 21-2(116 w² m
118
V
F Wgie))
e=1
2E m6g
w² m
V
(w
23 (w
w² 11 Σ
F (wgie)
(68)
23
E 10
[ El
w011
F (
32
2 E²
1)
3
- w01 222
32 +1
For the 10th term, we use AM-GM inequality and
incquality to bound it:
m VF
17 Σ v (((
(69)
E
V vi(
47

---

For the 1tth term, based on 35 we have:
E
E
2(n Σ
(m))"VF)
V Fg ((g:e)) = 0.
(70)
aml
To sum up, we have:
||| B|| 5 - 11'l
- p² KB w ||9
- p² (B
- w w1
+ Ell Wy w²11 + 33 E28
F
F
- B 1n Σ
+
e=
e=1
(71)
wn |13]
(m))' V )1 B Bl
c=1
2 R
2.32 F2
w= 119
1)
"" 11 -
E28
32 +
32 +1
E
(m)) (
B
Combining like terms, we have:
B Bllligg w
2,3 + E
< p² 533K(3
w/ 11
2) m
" ||3] + B(lln]
v
B +1
E
+ E28 + 3Eil
Σ>
(m)) (. Elln Σ (
(72)
Since when
V K2+
< B <
2RK ARK+2F4-33 we have
<
28 < 3, therefore 0 <
52-1
2 (R+
< 1. Since
||
w11 2 0, we know ( (28
2) 1 w
x11 2 0.
6"+1
3441
Then, we have:
E V
B||l"r g - w111 $ p² K(3[I - w01 E382 + +Ellmn
F((
(73)
+ E|llm
+ 3E
Then, based on Lemma E.5 and E.6
we can easily proof the Theorem A.5 as following:
Proof. Based on Assumption 1, we have:
48

---

F(u()) - F I (VF", {(FF,,(ug))
L +
マ/2 "llu'g - w w11
(74)
2
Since F* is the global optima, we have V 0, therefore:
F(w()) - F
L
L / leg i 5
$ 2 !uug -=11
(wi 9 w' w0
E
$ (3Lp² K + L)B - w" |13] + L3 E88 + Bill
V Fi (w
(75)
E + +3Billn
F. w
[ee (13)))
e=1r=1
Then, based on Lemma E.1
R..5 and E.6
we have:
B[F(ua))- - F"
1- V
E
< (3Lp² + L) -
- w²1
8,3
+
WBIl (-1 Dilll---Evvei "
1- v
3=1
E
WE
(m
+ +BIll
V (w ( +B
( E Σ
V F
(w
(19)
e=1r=1
< (3Lpk² + L) w +1
(76)
13 where u = 13p2KL+ KLL
813pk*
22 V= == (3 1
(R+
and
28 F2 22
B²+1
E VF 1111 + KB n
= (3Lp² K + L)
WE
V Fl
E + ElIl
E
V. (( (3LP3) + L)
DIBIIA -1
Σ
(m;
(V
e=1
r=1
+ 3y KLE(IV]
c=1
(77)
Based on Assumption A.2
we can further bound the gradient expectation term W by:
W (3p2 K + 1)
2 + -2) F.C. + K..
(3p² + +1)+P++++)+
+ 2 + E2) -882- 32RQ(() + KL3
(78)
< 1KL(2E2=33QUUU (3p²K +
+QQ(I)
132
28 + -
49


Reviews:
[{"review_id": "Anxr120NZy", "reviewer": "Reviewer_pMVS", "summary": "This paper introduces FedQS, a novel framework for optimizing both gradient and model aggregation strategies in Semi-Asynchronous Federated Learning (SAFL). FedQS classifies clients into four types based on update speed and gradient similarity and dynamically adapts local training accordingly. The approach addresses limitations of gradient aggregation and model aggregation in SAFL. Theoretical convergence proofs and extensive experiments on vision, NLP, and real-world tasks demonstrate that FedQS outperforms existing baselines in accuracy, convergence speed, and runtime efficiency.", "questions": "The authors should clarify the expected additional communication overhead from sharing similarity information and feedback signals in large networks.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nNovelty and significance: The paper is the first to propose a unified framework for simultaneously optimizing gradient and model aggregation in SAFL, addressing a clear gap in the literature.\n\nTechnical soundness: Provides rigorous theoretical convergence analysis under standard FL assumptions, with separate proofs for both aggregation strategies.\n\nComprehensive experiments: Evaluations cover diverse tasks, client heterogeneity settings, and ablation studies that convincingly support the claimed benefits.\n\nWeaknesses\n\nHyperparameter sensitivity: Though there is some analysis, FedQS introduces several hyperparameters that may require careful tuning in practice, potentially limiting usability.\n\nCommunication overhead: it may introduce additional communication overhead due to the need to transmit extra data.\n\nDynamic environments: In the experimental evaluation, although the resource heterogeneity is simulated using a predefined static ratio, client resources are fixed throughout training. While FedQS theoretically supports dynamic adaptation, the absence of experiments under dynamic resource changes limits the empirical validation of its robustness and effectiveness in truly dynamic environments.", "was_revised": true, "final_justification": "I read the rebuttal, and I will raise my score accordingly.", "rebuttal": "We thank Reviewer pMVS for the constructive feedback. In the following, we would like to answer the concerns individually.\n\n**[Hyperparameter sensitivity]** \n\nWe appreciate the reviewer's insightful comment regarding hyperparameter tuning in FedQS. While FedQS does introduce new hyperparameters (e.g., learning rate change rate $a$, initial momentum value $m_0$, and momentum change speed $k$), our design ensures robust performance across a wide range of values, minimizing the need for exhaustive tuning. Here, we clarify the practical usability of FedQS:\n- **Default Robustness:**\n\t- As shown in Section 5.4 (Table 2), FedQS achieves competitive performance with default hyperparameters (e.g., $a$ = 0.002, $m_0$ = 0.1, $k$ = 0.2). \n\t- The adaptive mechanisms in Mod② (e.g., dynamic learning rate adjustment) inherently mitigate sensitivity to suboptimal hyperparameter choices.\n    - In large-scale experiments (Table 4), FedQS consistently outperforms baselines under varying client counts (50–200) and resource ratios (1:20–1:100), demonstrating robustness to real-world conditions *without* per-scenario tuning.\n\n- **Interpretability and Guidance:**\n\t- The hyperparameters are intuitive (e.g., $a$ controls learning rate adaptation speed) and align with standard FL practices (e.g., the hyperparameter for momentum terms). \n\t- Figure 5 (the impact of different hyperparameters) demonstrates that FedQS maintains stable performance across a broad range of $a$ (0.001–0.005) and $k$ (0.01–0.2), reducing tuning overhead.\n\n- **Comparable Tuning Effort:**\n\t- The hyperparameter tuning overhead introduced by FedQS is also comparable to existing state-of-the-art SAFL techniques. For example:\n        1. FedAT [1] needs the following hyperparameters: local constraint parameter $\\lambda$, the number of tiers $M$, and the response latencies boundaries {$tier_1, tier_2,...,tier_M$}.\n        2. WKAFL [2] needs the following hyperparameters: gradients adjustment parameter $B$, learning rate adjustment parameter $\\gamma$, clip-bound parameter $CB$, weighted parameter $\\beta$, and constant $\\alpha$.\n        3. FADAS [3] needs the following hyperparameters: delay threshold $\\tau_c$, adaptive optimization parameters $\\beta_1, \\beta_2, \\epsilon$.\n\n    - The design of FedQS minimizes tuning complexity by confining hyperparameters exclusively to Mod②. Meanwhile, Mod① and Mod③ remain entirely hyperparameter-free, thereby substantially reducing the configuration burden.\n\nWe will clarify this more specifically in the final version to further simplify adoption. FedQS’s benefits (accuracy, convergence, and stability) far outweigh its modest tuning requirements, which are comparable to (or simpler than) those of existing SAFL methods. Thank you for the opportunity to clarify this point.\n\n**[Communication overhead]** \n\nWe appreciate the reviewer's insightful comment regarding communication overhead. While FedQS does introduce additional communication for gradient similarity metrics and client state updates, we emphasize that this overhead is carefully minimized and justified by significant performance gains:\n\n- **Lightweight Payload:** The additional data transmitted (gradient similarity scores and client state indicators) are scalar values, adding negligible bandwidth compared to model/gradient updates. Our experiments show the overhead constitutes <1% of total communication volume.\n- **Adaptive Frequency:** Communication occurs only during aggregation rounds, with no extra synchronization steps. The pseudo-global gradient in Mod① is derived from existing model transmissions, requiring no additional uploads.\n- **Flexible Deployment:** For extreme resource constraints or large-scale scenarios, FedQS's communication load scales linearly with the number of clients while maintaining the effectiveness (see Section 5.3). Therefore, this marginal overhead remains negligible for practical deployment while delivering substantial scalability and flexibility, empowering users to balance performance requirements against communication costs.\n\n|Method|Uplink Payload|Downlink Payload|Extra Overhead|Notes|\n|-|-|-|-|-|\n|**FedAvg/FedSGD**|Model parameters (43.7 MB) or Gradients (~43.7 MB)|Model parameters (43.7 MB)|0%|Upload/download model directly|\n|**Ours (FedQS)**|43.7 MB + 1-bit + 1 float (~4 B)|43.7 MB + 3 floats (~12 B)|~0.000037%|Extra metadata adds ~16 bytes total; negligible compared to 43.7 MB|\n\nFor intuitive illustration, we quantitatively compare the communication disparity between FedQS and FedAvg/FedSGD in the table above using ResNet-18 (model size ≈43.7MB) – consistent trends hold across other scenarios and model architectures. We will explicitly discuss the communication overhead in the revised manuscript. Thank you for highlighting this important aspect!\n\n**[Dynamic environments]**\n\nWe sincerely appreciate the reviewer's insightful feedback regarding the evaluation of dynamic environments. We acknowledge that while our theoretical design supports dynamic adaptation, the current experiments primarily simulate static resource heterogeneity. To address this limitation and further validate FedQS’s robustness in truly dynamic settings, we have conducted additional experiments on the CV task, where client resources vary during training. The following summarizes the key results (detailed in the table below):\n\n- **Dynamic Resource Scale (Scenario 1):** We modified the resource distribution during training (e.g., switching the speed ratio from 1:50 to 1:100 at $T = 200$ (i.e., 50% of the total training round)). FedQS consistently outperformed baselines, achieving:\n\t- an average of 77.53% (+8.58% than FedAvg) and 84.36% (+3.76% than FedSGD) accuracy under model and gradient aggregation, respectively, while achieving 15.96% and 17.82% faster convergence than FedAvg/FedSGD on average, respectively.\n\n- **Unstable Resource per Client (Scenario 2):** We modified each client's training speed to fluctuate within [−10, +10] unit times after uploading one local update, where we define the 1 unit time as the train time of the fastest client in the static experiments (in Section 5). We ensured that no client's training speed falls below 1 unit time or exceeds 50 unit times. The results show that FedQS achieves:\n    - an average of 77.46% (+7.54% than FedAvg) and 82.25% (+2.54% than FedSGD) accuracy under model and gradient aggregation, respectively, while achieving 14.49% and 14.59% faster convergence than FedAvg/FedSGD on average, respectively.\n\n- **Client Dropout Scenarios (Scenario 3):** We simulated dynamic participation (random 50% client churn at $T = 100$). FedQS maintained stable convergence, with:\n\t- an average of 71.21% (+9.44% than FedAvg) and 76.55% (+1.70% than FedSGD) accuracy under model and gradient aggregation, respectively, while achieving 15.34% and 10.96% faster convergence than FedAvg/FedSGD on average, respectively.\n\nWe will incorporate experimental results demonstrating FedQS's effectiveness in dynamic settings and expand our discussion accordingly in our revision. We sincerely appreciate your invaluable insights!\n\n|Dynamic Scenario|Algorithm|x=0.1|||x=0.5|||x=1|||\n|-|-|-|-|-|-|-|-|-|-|-|\n|||Accuracy|Conv. Speed|Runtime|Accuracy|Conv. Speed|Runtime|Accuracy|Conv. Speed|Runtime|\n|Scenario 1|FedAvg|52.77|322|46488|77.29|288|47732|76.79|227|48003\n|Scenario 1|FedQS-Avg|66.47|264|53986|82.90|235|54575|83.22|201|55529\n|Scenario 1|FedSGD|68.29|244|47443|85.66|211|47728|87.86|147|48280\n|Scenario 1|FedQS-SGD|76.17|206|54095|88.12|177|55268|88.8|115|55257\n|\n|Scenario 2|FedAvg|53.12|310|47397|76.74|294|47156|79.9|286|47788\n|Scenario 2|FedQS-Avg|64.52|268|55535|83.53|241|55816|84.35|252|56253\n|Scenario 2|FedSGD|65.13|268|47613|85.37|207|47096|88.63|159|47634\n|Scenario 2|FedQS-SGD|69.65|223|55037|87.96|185|55201|89.14|133|55808\n|\n|Scenario 3|FedAvg|44.39|343|58993|68.44|332|59362|72.47|296|59447\n|Scenario 3|FedQS-Avg|53.22|297|62623|79.33|272|63308|81.08|253|63776\n|Scenario 3|FedSGD|58.40|292|58345|81.73|288|59487|84.43|262|59732\n|Scenario 3|FedQS-SGD|60.08|263|62870|83.39|245|63992|86.18|241|64703\n\n\n**Reference**\n\n[1] Z. Chai, et al. Fedat: A high-performance and communication-efficient federated learning system with asynchronous tiers. SC, 2021.\n\n[2] Z. Zhou, et al. Towards efficient and stable k-asynchronous federated learning with unbounded stale gradients on non-iid data. IEEE TPDS, 2022.\n\n[3] Y. Wang, et al. FADAS: Towards Federated Adaptive Asynchronous Optimization. ICML, 2024."}, {"review_id": "IEBdtq5lwt", "reviewer": "Reviewer_aRTH", "summary": "This paper addresses three key challenges in semi-asynchronous federated learning – lack of theoretical understanding, inherent aggregation disparity and client-centric limitations. The authors propose the first FL framework FedQS with a divide-and-conquer strategy that classifies clients into four types and adapts their training strategies dynamically to optimize both gradient and model aggregation in SAFL.", "questions": "How much impact does the divide-and-conquer strategy have on the experiment’s runtime? Are there any ways to speed up the averaging operation across all clients?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n\n1. FedQS is a novel SAFL framework that simultaneously optimizes gradient and model aggregation, effectively targeting the accuracy–stability trade-off originated from FedSGD and FedAvg.\n\n2. Solid theoretical analysis is provided to guarantee the convergence of the proposed method.\n\nWeakness\n\n1. The divide-and-conquer strategy needs to compute and aggregate some extra variables, i.e., update speeds and similarities. This step could be time-consuming when the number of clients is large.", "was_revised": true, "final_justification": "My concerns are addressed. I will keep my score of 5.", "rebuttal": "We thank Reviewer aRTH for the constructive feedback. In the following, we would like to answer the concerns individually.\n\n**[Computational Overhead of Divide-and-Conquer Strategy]**\n\nWe sincerely appreciate the reviewer’s insightful question regarding the computational overhead of FedQS's divide-and-conquer strategy. Below, we address the concerns and provide additional clarifications:\n\n- **Impact on the Local Runtime:**\n\t- Table 3 (Section 5.2) demonstrates that FedQS achieves **comparable runtime** to top-performing baselines (e.g., FedQS-SGD introduces 4.18% more training time than FedAC while improving accuracy by 5.09%). The overhead of computing update speeds ($f_i^t$) and similarities ($s_i^t$) is minimal because:\n\t\t-  **Efficient Computation:** $f_i^t$ is derived from historical participation counts (Equation 2) on the server, requiring only *O*(1) updates per client.\n\t\t- **Similarity Calculation:** $s_i^t$ uses lightweight pseudo-gradients (Section 3.4), with cosine similarity computed efficiently on model deltas (complexity linear in model dimensions).\n\t- Implementing the divide-and-conquer strategy requires each client to compute a pseudo-gradient in Mod① to facilitate similarity calculation in Mod②. This computation scales linearly with the depth of the model, constituting the primary computational overhead introduced by FedQS. Nevertheless, it remains comparatively low relative to total per-round runtime (16.21% on average).\n- **Scalability Optimization on the Server:**\n\t-  **Parallelization:** The averaging of $\\bar{f}^t$ and $\\bar{s}^t$ (Equation 2) is performed asynchronously during client-server communication, overlapping with model transmission.\n\t- **Paritial Aggregation:** For large-scale deployments, the divide-and-conquer strategy selectively refreshes state tables and weights solely for clients engaged in global aggregation (e.g., $N=100$ total clients with $K=10$ active participants per round), thereby maintaining computational efficiency regardless of system scale, reducing computational costs without sacrificing performance (empirically validated for $N = 200$ in Tables 4 and 7).\n    \n- **Trade-off Justification:** The slight runtime increase (e.g., FedQS-Avg is 1.3× slower than FedAvg but 7.27% more accurate) is justified by significant gains in accuracy and convergence speed (Table 2). The divide-and-conquer strategy’s adaptive training also reduces convergence rounds (e.g., 22.35% faster than FedSGD), offsetting per-round overhead.\n\nWe conducted disaggregated experiments to rigorously quantify the detailed additional runtime introduced by FedQS's divide-and-conquer strategy. The procedure is partitioned into three critical phases: pseudo-gradient computation in Mod①; client classification in Mod②; and state-table updating with weight aggregation in Mod③.\n\nThe table below shows the average time consumed per global round for each phase in FedQS when training ResNet-18 on CIFAR-10. We will incorporate these quantitative measurements in the revision to visually demonstrate the additional computational overhead attributable to FedQS.\n\n|# Clients|Data Distribution|Average time for completing one global round (s)|Time for calcultating pesudo-gradient in Mod① (s)|Average ratio for Mod①|Time for categorizing clients in Mod② (s)|Average ratio for Mod②|Time for updating status table in Mod③ (s)|Average ratio for Mod③|\n|-|-|-|-|-|-|-|-|-|\n|50|x=0.1|44.98|6.69|14.87%|2.17|4.82%|0.13|0.29%\n||x=0.5|46.59|7.43|15.94%|2.89|6.20%|0.14|0.30%\n||x=1|43.79|7.02|16.03%|2.33|5.32%|0.09|0.21%\n|100|x=0.1|80.97|14.14|17.46%|4.51|5.57%|0.23|0.28%\n||x=0.5|83.41|13.93|16.70%|4.22|5.06%|0.26|0.31%\n||x=1|82.77|13.11|15.84%|3.96|4.78%|0.33|0.39%\n|200|x=0.1|165.83|22.33|13.47%|8.11|4.89%|0.49|0.30%\n||x=0.5|152.05|27.80|18.28%|9.51|6.25%|0.47|0.31%\n||x=1|153.93|26.69|17.34%|8.97|5.82%|0.45|0.29%\n|Average| | | |16.21%| |5.41%| |0.3%\n\n\"Average ratio for Mod①\" represents the ratio of the time spent calculating the pseudo-gradient in Mod① to the average time required to complete one global round.\n\n**[Speeding Up Averaging Operations]** \n\nWe sincerely appreciate the reviewer's insightful suggestion regarding optimizing the averaging operation in FedQS. Below, we clarify our current design choices and propose actionable enhancements to address this concern:\n\n- **Hardware-Accelerated Aggregation:** The global averaging in FedQS loads and processes model updates directly on GPU devices. It adopts a streaming aggregation approach to handle large-scale model parameters, mitigating memory pressure during parameter synchronization. This design efficiently overlaps network transmission with on-device computation, achieving significant throughput improvements for federated scenarios with resource-constrained participants. Future work could further exploit parallelized aggregation protocols to enhance aggregation efficiency.\n\n- **Space-Time Trade-offs:** While FedQS's current client-state table (Equation 1) requires lightweight updates, we acknowledge that caching similarity scores or adopting low-rank approximations for similarity scores (e.g., via incremental SVD) could reduce computation. Our ablation study (Table 5) shows robustness to similarity metric choices, suggesting such approximations are viable.\n\n- **Algorithmic Simplifications:** Since FedQS's primary overhead originates from pseudo-gradient computation, its operational efficiency can be enhanced by reducing execution frequency as:\n\t- **Staggered Updates:** Client reclassification (Figure 3) can occur every $\\Delta_T$ rounds (e.g., $\\Delta_T$ = 5), reducing the additional overhead by 63.6–72.7% with a 1.4-5.2% reduction on the accuracy in preliminary tests.\n\t- **Sampling-Based Estimation:** Substituting full-client similarity checks with stratified sampling (e.g., 20% per round) substantially reduces computational demands (53.2-57.5% reduction) while avoiding significant performance degradation (2.2-4.1% reduction).\n\n\tHowever, such optimization compromises fine-grained real-time client classification in FedQS, potentially degrading model accuracy. Therefore, it is a context-aware balancing between granular control and efficiency: for latency-sensitive deployments, the aforementioned strategy trades marginal accuracy reduction for efficiency; whereas accuracy-critical scenarios benefit from default FedQS configurations for optimal utility.\n\nThese optimizations align with FedQS's modular design and could be seamlessly integrated. We will expand this discussion in the revision, including empirical validation of trade-offs."}, {"review_id": "Zl2LsLKVE5", "reviewer": "Reviewer_6F15", "summary": "This paper introduces FedQS, a framework for optimizing both gradient and model aggregation in semi-asynchronous federated learning, addressing challenges like client heterogeneity, staleness, and data distribution disparities. FedQS uses a divide-and-conquer strategy to classify clients into four types and adapt their training dynamically, achieving exponential convergence rates and balancing the trade-offs between accuracy, convergence speed, and stability. Extensive experiments demonstrate the performance of FedQS across tasks in computer vision, natural language processing, and real-world datasets.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The paper presents a strong experimental design with detailed settings and comprehensive numerical results, enabling reproducibility and validation of claims.\n\n- It provides a clear discussion of limitations and broader impacts, demonstrating transparency and awareness of the practical challenges in implementing FedQS.\n\nWeaknesses:\n\n- My major concern lies in the convergence guarantees in Section 4.2. Theorems 4.2 and 4.3 show that the function value does not converge exactly to the global optimum, leaving a non-vanishing gap $\\mathcal{U} +\\mathcal{V}$. This deviates from standard convergence results commonly found in the literature, where gradient norm convergence is typically used as a metric for nonconvex problems. Furthermore, the claimed *linear* convergence rates are questionable, as these are generally unattainable for *L*-smooth functions without additional regularity conditions (e.g., strong convexity).\n\n- While I understand the rich body of literature in federated learning, the paper still lacks a discussion of or comparison with more recent works in asynchronous federated learning. Below is a non-exhaustive list of closely related studies:\n\n   [1] Yan W. et al. A. Momentum-Driven Adaptivity: Towards Tuning-Free Asynchronous Federated Learning. In Forty-second International Conference on Machine Learning, 2025.\n   \n   [2] Wang, X., et al. Achieving linear speedup in asynchronous federated learning with heterogeneous clients. IEEE Transactions on Mobile Computuing, 2024.\n\n   [3] Yu T. et al. M. Momentum Approximation in Asynchronous Private Federated Learning. arXiv preprint arXiv:2402.09247, 2024.\n\n   [4] Wang, Y. et al. FADAS: Towards Federated Adaptive Asynchronous Optimization. In International Conference on Machine Learning, 2024.\n\n   [5] Wang, Y. et al. Tackling the data heterogeneity in asynchronous federated learning with cached update calibration. In Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities, 2023.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns.", "rebuttal": "We thank Reviewer 6F15 for the constructive feedback. In the following, we would like to answer the concerns individually.\n\n**[Convergence Guarantees]**\n\nWe sincerely appreciate the reviewer's insightful comments regarding our convergence analysis in Section 4.2. Below, we provide a detailed response addressing the three major concerns:\n\n- **Non-vanishing Terms ($\\mathcal{U}+\\mathcal{W}$):** The residual terms $\\mathcal{U}+\\mathcal{W}$ in our convergence bounds reflect fundamental limitations inherent to semi-asynchronous FL systems:\n\t- **Theoretical Justification:** These terms capture unavoidable convergence errors from (a) non-simultaneous model/gradient aggregation in SAFL and (b) irreducible data heterogeneity ($\\delta^2$ and $G_c^2$ bounds). Their presence aligns with established SAFL literature. For example:\n\t\t1. The theoretical results of FedSA [7] (Theorem 1) include a constant error term $\\delta$ with global round $K$:\n\t\t$\\mathbb{E}[F(w_K)] - F(w^\\*) \\leq \\rho^K(F(w_0)-F(w^*))+\\delta$.\n\t\t2. The theoretical results of WKAFL [8] (Theorem 5.1 and Remark 5.2) include a constant term $G^2$ with global round $J$:\n\t\t$\\mathcal{O}(\\frac{1}{\\sqrt{KJ}}+\\frac{1}{J}+G^2)$.\n\t\t3. The theoretical results of AAFL-RC [9] (Theorem 1) include an increasing error term $\\frac{D\\eta\\mathcal{Z}}{2}$ with global round $D$:\n\t\t$\\mathbb{E}[F(\\hat{w}^D)-F(w^\\*)]\\leq(1-\\eta\\vartheta)^D[F(w^0)-F(w^*)]+\\frac{D\\eta\\mathcal{Z}}{2}$.\n\t- **Empirical Validation:** Our experiments on CIFAR-10 (Non-IID) empirically validate these bounds, showing consistent accuracy degradations that align with the theoretical predictions (see Tables 1 and 2 in the paper). The residual terms precisely quantify the performance gap between SAFL and idealized synchronous FL.\n\n- **Convergence Metric Choice (Function Value vs Gradient Norm):** We selected function value difference $\\mathbb{E}[F(w_g^t)] - F^*$ as our primary metric for several important reasons that align with both the practical and theoretical objectives of our work:\n\t- **Optimization Stability in SAFL Context:** This metric better reveals optimization stability issues (e.g., oscillations and regressions). This proves crucial for understanding interactions among semi-synchronous updates, non-IID data, and aggregation strategies, particularly when analyzing instability in gradient-based SAFL methods. Whereas averaged gradient norms quantify convergence rates, they may obscure these critical dynamics since highly unstable processes can also exhibit deceptively small average norms, which is a significant limitation.\n\t- **Theoretical and Practical Relevance:** This metric directly measures proximity to the optimal solution (i.e., $w*$ or $F^\\*$), which is meaningful for SAFL applications to assess solution quality, whereas the averaged gradient norm provides limited visibility into this distance. The function value difference reveals how FedQS's componentized architecture enables the final model to achieve closer proximity to the theoretical optimum $F^*$ of centralized training under both model and gradient aggregation strategies. Our analysis also explicitly disentangles the impacts of staleness ($\\mathcal{V}^t$), data heterogeneity ($\\mathcal{U}$), and gradient variation ($\\mathcal{W}$), delivering actionable insights for SAFL system design.\n\t- **Alignment with SAFL Literature:** Our approach follows recent SAFL works that use function value differences for convergence analysis. For example:\n\t\t1. The convergence analysis of FedSA [7] (Theorem 1):\n\t\t$\\mathbb{E}[F(w_K)] - F(w^\\*) \\leq \\rho^K(F(w_0)-F(w^*))+\\delta$.\n\t\t2. The convergence analysis of AAFL-RC [9] (Theorem 1):\n\t\t$\\mathbb{E}[F(\\hat{w}^D)-F(w^\\*)]\\leq(1-\\eta\\vartheta)^D[F(w^0)-F(w^*)]+\\frac{D\\eta\\mathcal{Z}}{2}$.\n\t\t3. The convergence analysis of AiFed [10] (Theorem 1):\n\t\t$\\mathbb{E}[J(w_R)] - J(w^\\*) \\leq\\mathcal{K}^R(J(w_0)-J(w^*))+\\delta$.\n\t\t4. The convergence analysis of EAFL [11] (Theorem 1):\n\t\t$\\mathbb{E}[F(w^T)-F(w^\\*)]\\leq[2N\\cdot M\\cdot(1-\\mu\\cdot\\eta)^Q]^T\\cdot[F(w^0)-F(w^*)]+\\frac{[1-(2N\\cdot M\\cdot(1-\\mu\\cdot\\eta)^Q)^T]Q\\cdot\\eta\\cdot P}{4(1-\\mu\\cdot\\eta)^Q}$.\n\n\tWe acknowledge that gradient norm analysis could provide complementary complexity results, which we plan to explore in future work. For now, our loss-difference bounds effectively account for FedQS's superiority under dual aggregation strategies while providing practical convergence guarantees: momentum alleviates oscillatory phenomena during training under gradient aggregation (Remark 4.5 and Figure 10), while the divide-and-conquer strategy achieves integrated mitigation of model aggregation's suboptimal convergence utility (Remark 4.6 and Table 2).\n\n- **Convergence Rate Clarification:** We apologize for any ambiguity regarding \"exponential convergence\":\n\t- **Precise Characterization:** The $\\mathcal{V}^t$ term in our bounds indeed exhibits exponential decay, but the overall convergence is sublinear due to $\\mathcal{U}+\\mathcal{W}$ residuals (as correctly noted by the reviewer).\n\t- **Terminology Correction:** We will revise the manuscript to:\n\t\t- Replace \"exponential convergence\" with \"exponential decay of $\\mathcal{V}^t$\" where appropriate.\n\t\t- Explicitly state that the overall convergence remains sublinear.\n\t\t- Add discussion comparing with that under strong convexity/Polyak-Lojasiewicz conditions.\n\n\n**[Recent Works Comparison]** \n\nWe sincerely thank the reviewer for highlighting these important recent works in asynchronous federated learning (AFL/SAFL). We have thoroughly analyzed the suggested papers and provide the following responses:\n\n- **Experimental Comparisons:** We have conducted new experiments comparing FedQS against three representative SOTA methods ([2], [4], [5]) across all three task types (CV/NLP/RWD). The results (shown in tables below) demonstrate FedQS's consistent advantages in accuracy (average +10.98%, +4.8%, +47.38% higher compared to [2], [4], [5], respectively) and convergence speed (average +21.8%, +12.4%, +39.5% faster compared to [2], [4], [5], respectively) while maintaining competitive runtime.\n\n1. CV task:\n\n|Algorithm|x=0.1|||x=0.5|||x=1|||\n|-|-|-|-|-|-|-|-|-|-|\n||Accuracy|Conv. Speed|Runtime|Accuracy|Conv. Speed|Runtime|Accuracy|Conv. Speed|Runtime|\n|FedQS-SGD|68.88|239|32784|86.11|213|33656|86.79|127|33400\n|DeFedAvg [2]|52.33|307|30776|83.51|257|31754|86.17|155|30280\n|FADAS [4]|65.34|255|32380|82.2|220|32966|84.21|143|31471\n|C$A^2$FL [5]|42.29|272|108097|63.79|256|109635|70.16|200|108756\n\n2. NLP task:\n\n|Algorithm|R=200|||R=600|||\n|-|-|-|-|-|-|-|\n||Accuracy|Conv. Speed|Runtime|Accuracy|Conv. Speed|Runtime|\n|FedQS-SGD|52.22|188|5248|52.49|216|9135\n|DeFedAvg [2]|40.19|256|4989|48.23|238|8720\n|FADAS [4]|46.83|220|5118|48.95|254|9002\n|C$A^2$FL [5]|25.36|259|36441|28.86|272|36548\n\n3. RWD task:\n\n|Algorithm|Gender|||Ethnicity|||\n|-|-|-|-|-|-|-|\n||Accuracy|Conv. Speed|Runtime|Accuracy|Conv. Speed|Runtime|\n|FedQS-SGD|78.74|18|5523|79.24|22|5465\n|DeFedAvg [2]|77.82|59|4841|78.11|20|4827\n|FADAS [4]|78.04|25|5476|78.54|24|5299\n|C$A^2$FL [5]|76.09|59|19650|66.68|325|19370\n\n- **Theoretical Alignment:**\n\t- For [1]'s momentum adaptivity: While their method shares some conceptual similarities with our momentum adaptation in Mod②, FedQS's *quadrant-based client classification* provides finer-grained control. Specifically, we categorize clients and apply momentum solely to those with minor deviations from global updates. For high-bias clients whose distributions remain inadequately captured, we deliberately withhold momentum and instead deploy feedback mechanisms to prevent more severe oscillations. We will add a detailed discussion in Section 3.\n\t- For [3]'s momentum approximation: Their technique is orthogonal to ours - they propose a uniform momentum approximation technique which could be applied broadly to SAFL frameworks, while we address aggregation disparity. Their method could be integrated into FedQS.\n\n- **Methodological Distinctions:** Compared to [4], [5], which use *server-side calibration* and *historical updates' assistance*, FedQS's innovation lies in:\n\t- *Client-side self-adaptation* via Mod② (eliminating server-side bias)\n\t- *Dual-strategy compatibility* (Theorems 4.2-4.3 prove unified convergence)\n\t- *Dynamic feedback mechanism* (Table 5 shows 7.8% accuracy gain vs. no-feedback)\n\t- *Lower memory storage* (Additionally storing a state table with only ~7.8KB for 100 clients)\n\n- **Reproducibility Note:**\n\t- For [1], we couldn't reproduce the results due to the unavailable code. We will request their code for a fuller comparison.\n\nThese comparisons will be added to Sections 5-6 with proper credit to prior works. We believe they further strengthen FedQS's contributions as the *first framework unifying gradient/model aggregation optimization in SAFL*.\n\n\n\n**Reference**\n\n[1]-[5] same in review comments.\n\n[6] X. Li, et al. On the Convergence of FedAvg on Non-IID Data. ICLR, 2019.\n\n[7] Q. Ma, et al. Fedsa: A semi-asynchronous federated learning mechanism in heterogeneous edge computing. IEEE JSAC, 2021.\n\n[8] Z. Zhou, et al. Towards efficient and stable k-asynchronous federated learning with unbounded stale gradients on non-iid data. IEEE TPDS, 2022.\n\n[9] J. Liu, et al. Adaptive Asynchronous Federated Learning in Resource-Constrained Edge Computing. IEEE TMC, 2022.\n\n[10] L. You, et al. AiFed: An Adaptive and Integrated Mechanism for Asynchronous Federated Data Mining. IEEE TKDE, 2024.\n\n[11] Y. Zhou, et al. Towards Efficient Asynchronous Federated Learning in Heterogeneous Edge Environments. INFOCOM, 2024."}, {"review_id": "KziVwLMrFA", "reviewer": "Reviewer_2stv", "summary": "This paper introduces a framework of semi-asynchronous Federated Learning, FedQS, which mainly tackles two key issues: aggregation disparity and inefficiency of global information of client-centric model aggregation methods.\n\nBased on some key observations on distinct continuity in the optimization trajectories of model / gradient aggregation strategies, the authors categorize all clients into four distinct groups and apply different aggregation methods to them. Then, the local updates (local models / gradients) are accordingly aggregated in different methods.\n\nThe theoretical and empirical results shown in this paper clearly demonstrate the superior FL performance over existing semi-asynchronous FL methods.", "questions": "No specific questions, but I expect healthful discussions regarding my comments shown in the 'weakness' part.", "limitations": "Yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n - The study is well organized and the proposed framework looks well-designed.\n - The key observation is interesting: the gradient aggregation strategy provides more stable global model training.\n - Divide-and-conquer strategy seems to be practical.\n\n**Weaknesses**\n\nWhile I see several strong points, I also see a couple of serious weak points as follows.\n - [System efficiency analysis] FedQS has a few extra steps compared to typical FedAvg, such as calculating pseudo global gradient, calculating similarity scores, and updating aggregation status table at the server side. The clients also have some extra works such as feedback signal calculation and communications. These extra workload increases overall computational and communication costs as well as memory footprint. However, the paper does not discuss them.\n - [Misleading terms] In Mod2, the 'biased' term may mislead readers. Precisely speaking, it is not a matter of biased or unbiased. It is a matter of strongly biased or weakly biased. E.g., *Fast-and-Unbiased* clients still produce more or less biased updates due to the non-IID data characteristics, although the degree of bias is lower than other clients.\n - [Strong assumptions] In Section 4, the gradient is assumed to have a maximum magnitude $G_c$. Although some previous works used this assumption, I still believe it is quite strong, and it makes the results less convincing.\n - The convergence properties are also not thoroughly analyzed. Both theorems show the intermediate results only. The common convention is to show that the expected average gradient norm is bounded by a constant rather than showing the bound of the loss difference. It may show different convergence properties if the left-hand side is the gradient norm, e.g., complexity.\n - In order to accelerate slow clients, the authors employed momentum in Mod2. However, why not applying it to fast clients too? Wouldn't it further improve the training speed? It makes sense to apply it to slow clients only when it hurts the training speed when applied to the fast clients.", "was_revised": true, "final_justification": "I have double checked the discussion, and I do not see any special reasons to change my score.", "rebuttal": "We thank Reviewer 2stv for the constructive feedback. In the following, we would like to answer the concerns individually.\n\n**[System Efficiency Analysis]** \n\nWe sincerely appreciate the reviewer’s insightful feedback regarding computational and communication overhead. We address these concerns through both theoretical and empirical analyses:\n\n- **Scalability by Design:**\n\t- *Client-side:* Each client performs one additional model difference computation (pseudo-global gradient) and two numerical comparisons (for quadrant classification) per round, with no inter-client communication.\n\t- *Server-side:* The state table maintains *O*(1) lookup/update complexity per client, ensuring constant-time operations regardless of client population size.\n\n- **Quantified Overhead:** Experiments on 100-client CIFAR-10 (ResNet-18, ≈43.7MB) show negligible practical impact:\n\t- **Computation:** Similarity scores and feedback signal calculation introduce minimal computational overhead, adding ~4s latency per global round. \n\t- **Communication:** Each client transmits only 4B in uplink (similarity score) and a 1-bit feedback signal, while the server broadcasts 12B downlink additionally (averaged thresholds). This constitutes <0.01% bandwidth overhead versus model updates.\n\t- **Memory:** Client-side storage for similarity scores and feedback signals totals <5B; server-state tables require ~7.8KB for 100 clients.\n\nThe table below shows the computational latency, communication overhead, and memory footprint induced by these mechanisms on average total of 400 global rounds, with consistent patterns holding across other scenarios.\n\n|Operation|Computational cost|communication costs|memory footprint|\n|-|-|-|-|\n|calculating pseudo global gradient (in Mod①)|13.73s|0|42.8MB|\n|calculating similarity scores (in Mod②)|2.23s|0|4B|\n|feedback signal calculation (in Mod②)|1.97s|0|1 bit|\n|feedback signal communications (Mod② -> Mod③)|0|Uplink 1bit(feedback signal)|0|\n|updating aggregation status table (in Mod③)|0.27s|0|~7.8KB|\n|status table communications (Uplink: Mod② -> Mod③, Downlink: Mod③ -> Mod②)|0|Uplink: ~4B (1 float point value); Downlink: ~12B (3 float point value)|0|\n\n- **Runtime Efficiency:** Table 3 in our paper demonstrates that FedQS's overhead is offset by faster convergence (reducing convergence rounds by 10–45% vs. baselines) and lower idle time (>70% reduction versus synchronous FL).\n\n**[Misleading Terms]** \n\nWe sincerely thank the reviewer for their insightful observation regarding the terminology used in Mod②. We fully agree that the terms \"biased\" and \"unbiased\" could be misinterpreted as implying a binary distinction, which does not accurately reflect the continuum of bias degrees inherent in semi-asynchronous federated learning, especially under non-IID data distributions.\n\nOur original intention was to highlight the relative deviation of client updates from the global optimization trajectory, where \"biased\" clients exhibit significant divergence due to staleness or data heterogeneity, while \"unbiased\" clients remain closer to the expected direction. However, we recognize that even the latter group may still exhibit minor biases. To eliminate ambiguity, we will revise the terminology in the manuscript to explicitly differentiate between \"strongly biased\" and \"weakly biased\" updates, emphasizing the spectrum of bias magnitudes. For instance:\n\n- **Fast-but-Strongly-Biased Clients (FSBC)**\n- **Fast-and-Weakly-Biased Clients (FWBC)**\n- **Straggling-but-Weakly-Biased Clients (SWBC)**\n- **Straggling-and-Strongly-Biased Clients (SSBC)**\n\nThis adjustment will better align with the reviewer's suggestion and provide a more precise description of the client categorization logic in FedQS. We appreciate the opportunity to improve the clarity of our work and will incorporate these changes in the revision.\n\n**[Strong Assumptions]** \n\nWe sincerely appreciate the reviewer's insightful feedback regarding the bounded gradient assumption. We agree that this condition can appear restrictive in certain scenarios, and we appreciate the opportunity to clarify its role in our analysis.\n\nAs noted in Remark 4.1, this assumption was introduced *solely* to simplify the interpretation of our convergence bounds by providing a deterministic upper bound for the gradient variation term $\\mathcal{W}$. Crucially, it was *not* used in proving our core convergence theorems (Theorems 4.2 and 4.3), which rely only on standard $L$-smoothness and bounded heterogeneity assumptions. The convergence guarantees (via the $\\mathcal{V}^t$ term) and heterogeneity analysis (via $\\mathcal{U}$) remain fully valid without this condition.\n\nIn our revision, we will add an explicit discussion in Section 4 to emphasize that the assumption is optional for theoretical guarantees but aids interpretability.\n\n**[Convergence Analysis]** \n\nWe appreciate the reviewer's insightful comments regarding our convergence analysis. We acknowledge that presenting bounds on the expected gradient norm could provide additional insights into the iteration complexity of our method. However, our choice to analyze the loss function difference $\\mathbb{E}[F(w_g^t)] - F^*$ was deliberate for several important reasons that align with both the practical and theoretical objectives of our work:\n\n- **Optimization Stability in SAFL Context:** The loss difference directly captures the holistic optimization trajectory in SAFL, which is critical for understanding the interplay between semi-asynchronous updates, non-IID data, and aggregation strategies. Unlike gradient norms, this metric reveals transient regressions and oscillatory behaviors (e.g., Figure 1 in our paper), which are pivotal for diagnosing instability in gradient-based SAFL methods. While averaged gradient norms quantify convergence rates, they may obscure these dynamics, which is a significant limitation given our focus on aggregation-strategy disparities.\n- **Theoretical and Practical Relevance:** Bounding the loss difference enables direct comparison with the centralized optimum ($F^\\*$), which is essential for evaluating SAFL's deviation from ideal convergence. This is particularly valuable for practitioners assessing solution quality (e.g., proximity to $w^*$), whereas gradient norms alone provide limited visibility into this distance. This constitutes one of the notable advantages when choosing the loss function difference as the theoretical objective.\n- **Alignment with SAFL Literature:** Our approach follows established conventions in SAFL research, where loss-difference bounds are also standard for convergence proofs (e.g., FedSA [1], AAFL-RC [2], AiFed [3], EAFL [4]). We cite this precedent to contextualize our methodological choice while advancing beyond prior art by explicitly linking theoretical bounds to empirical aggregation-strategy gaps (Table 1, Figure 2).\n\nWe agree that gradient-norm analysis could complement our results and will explore this direction in subsequent research. For now, our loss-difference bounds effectively account for FedQS's superiority under dual aggregation strategies while providing practical convergence guarantees: momentum alleviates oscillatory phenomena during training under gradient aggregation (Remark 4.5 and Figure 10), while the divide-and-conquer strategy achieves integrated mitigation of model aggregation's suboptimal convergence utility (Remark 4.6 and Table 2).\n\nWe will update our paper to: (1) Clarify in Section 4 that our analysis focuses on qualitative convergence behavior and stability, with gradient-norm complexity left for future work. (2) Expand both theorems' discussion to explicitly contrast loss-difference and gradient-norm perspectives. (3) Cite additional SAFL works using similar convergence forms to reinforce methodological validity.\n\nThank you for this constructive feedback! It will strengthen our manuscript’s theoretical rigor.\n\n**[Momentum Employment in FedQS]** \n\nWe appreciate the reviewer's insightful question regarding the selective application of momentum in FedQS. Our design intentionally applies momentum only to specific client types (FUC, SUC, and SBC in *Situation 1*) based on two key principles:\n\n- **Purpose of Momentum:** The momentum term in FedQS is not primarily a speed accelerator but a *trajectory stabilizer* for clients whose updates align well with the global model (high $s_i^t$). For these clients, momentum mitigates oscillations while accelerating convergence speed (Equation 3). In contrast, for high-bias clients (FBC and SBC in *Situation 2*), premature momentum application could amplify the divergence between their local updates and the global one, as their updates are not yet globally beneficial.\n- **Update Frequency Control:** Fast clients (FUC/FBC) are regulated via *adaptive learning rates* (reduced to prevent dominance for FUC) rather than momentum. This decouples speed control (handled by learning rates) from stability optimization (handled by momentum), avoiding interference between the two mechanisms. Our additional empirical results show that under the CV task, adding momentum to fast clients degrades accuracy by an average of 3.7% and increases oscillations by 1.7$\\times$ on average.\n\nWe will clarify this distinction in the revision, emphasizing that FedQS's momentum is a *bias-aware stabilizer*, not a universal speed booster. Thank you for prompting this important discussion.\n\n**Reference**\n\n[1] Q. Ma, et al. Fedsa: A semi-asynchronous federated learning mechanism in heterogeneous edge computing. IEEE JSAC, 2021.\n\n[2] J. Liu, et al. Adaptive Asynchronous Federated Learning in Resource-Constrained Edge Computing. IEEE TMC, 2022.\n\n[3] L. You, et al. AiFed: An Adaptive and Integrated Mechanism for Asynchronous Federated Data Mining. IEEE TKDE, 2024.\n\n[4] Y. Zhou, et al. Towards Efficient Asynchronous Federated Learning in Heterogeneous Edge Environments. INFOCOM, 2024."}]

Author rebuttal:

Meta-review: This paper proposed the first framework to theoretically analyze and optimize both gradient-based and model-based aggregation strategies within semi-asynchronous FL. It employs a novel divide-and-conquer strategy, dynamically classifying clients into four types based on their update speed and local-global gradient similarity, and adapts their local training strategies accordingly. All reviewers have achieved the agreement to accept this paper. We encourage the authors to carefully address the reviewers’ comments when preparing the camera-ready revision.
Decision: Accept (poster)