Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients
Authors: Shiyuan Zuo
Xingrun Yan
Rongfei Fan
Li Shen
Puning Zhao
Jie Xu
Han Hu
Venue: NeurIPS 2025 poster ()
Keywords: Federated learning
Byzantine attacks
convergence analysis
data heterogeneity.
Primary area: optimization

Abstract: Federated Learning (FL) enables multiple clients to collaboratively train models without sharing raw data, but is vulnerable to Byzantine attacks and data heterogeneity, which can severely degrade performance. Existing Byzantine-robust approaches tackle data heterogeneity, but incur high computational overhead during gradient aggregation, thereby slowing down the training process. To address this issue, we propose a simple yet effective Federated Normalized Gradients Algorithm (Fed-NGA), which performs aggregation by merely computing the weighted mean of the normalized gradients from each client. This approach yields a favorable time complexity of $\mathcal{O}(pM)$, where $p$ is the model dimension and $M$ is the number of clients. We rigorously prove that Fed-NGA is robust to both Byzantine faults and data heterogeneity. For non-convex loss functions, Fed-NGA achieves convergence to a neighborhood of stationary points under general assumptions, and further attains zero optimality gap under some mild conditions, which is an outcome rarely achieved in existing literature. In both cases, the convergence rate is $\mathcal{O}(1/T^{\frac{1}{2} - \delta})$, where $T$ denotes the number of iterations and $\delta \in (0, 1/2)$. Experimental results on benchmark datasets confirm the superior time efficiency and convergence performance of Fed-NGA over existing methods.

Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients
Shiyuan Zuo zuoshiyuanbhit. edu.
Xingrun Yan ystarr_cs$166 com
Rongfei Fan Banrongfei@bii edu.
Li 2hen shenli6@mail sysu, edu. cn
Puning Zhao?
Jie Xu xujie@cuhk. edu cn
zhaopn@mail sysu. edu. cn
Han Hu!
hhu@bit edu.cn
Beijing Institute of Technology, Beijing, China Sun Yat-Sen University, Guangzhou, China Thhe Chinese University of Hong Kong (Shenzhen), Shenzhen, China
Abstract
Federated Learning (FI.) enables multiple clients to collaboratively train models without sharing raw data, but is vulnerable Byzantine attacks and data het- erogeneity, which can severely degrade performance. Existing Byzantine-robat approaches tackle data heterogeneity, but incur high computational overhead during gradient aggregation, thereby slowing down the training process. To address this issue, propose simple yet effective Federated Normalized Gradients Algorithm (Fed-NGA), which performs aggregation by merely computing the weighted mean of the normalized gradients from each client. This approach yields favorable time complexity of OpMM), where is the model dimension and M the num- ber of clients. We rigorously prove that Fed-NGA is robust both Byzantine faults and data heterogeneity. For non-convex loss functions, Fed-NGA achieves convergence neighborhood of stationary points under general assumptions, and further attains zero optimality gap under some mild conditions, which is an outcome rarely achieved in existing literature. In both cases, the convergence rate is (L1TT -6). where T denotes the number of iterations and å e (0, Experimental results on benchmark datasets confirm the superior time efficiency and convergence performance of Fed-NGA over existing methods.
Introduction
FL has recently emerged as distributed paradigm that addresses challenges of large-scale data and privacy concerns by enabling multiple edge clients to collaboratively train a global model without sharing raw data (Zuo al. 2024 Yin et al. 2018 Konečný et al. 2016 Li et al. 2020). Under coordination of central server, clients exchange model parameters gradients rather than raw data. In each training round, the server aggregates the received messages to update the global model, which
is then broadcast back to clients for local updates using their private data (Wang al. 2019 Guo ct al. 2023). This crivac-prreeevvng mechanism, coupled with growing edge computing capabilities,
makes FL increasingly attractive for modern learning scenarios (Dorfman et al. 2023 Zhao et al.
2024).
"oorresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Despite its advantages, FL faces robustness challenges due to the participation of multiple clients (Kairouz et al. 2021] Vempaty et al. 2013). Messages uploaded to the central server may deviate
from expected values because of data corruption, device failures, or malicious behavior (Yang et al.
2020 Cao and Lai 2019). Such anomalies are referred to as Byzantine attacks, and the responsible
clients are termed Byzantine clients, while others are considered honest (So et al. | Cao and Lai 2019). The server neither knows the number nor the identities of Byzantine clients, who may adaptively craft and coordinate misleading updates (Chen et al. 2017). These attacks can severely degrade or even derail training, making robust aggregation strategies essential for secure FL.
In addition to robustness issues, data heterogeneity among participating clients presents a major challenge in FL. Unlike traditional distributed learning. FL clients gather training data from their local environments, resulting in non won-independent and non-identically distributed (non-lID) data across clients (Zhao et al., 2018). This heferogeneity introduces biases local optimal solutions, which can hinder the convergence of the global model. As result, achieving reliable convergence under non-IID conditions remains central focus in FL. research (Xie and Song 2023).
The literature on Byzantine-resilient FL aggregation spans both strongly convex settings (Pillutla ct al. 2022: Wu et al. 2020; Zhu and Ling] 2023 Li et al., 2019, Karimireddy et al. 202I) and
the more general and challenging case of non-convex loss functions (Yin et al. 2018 Turan et al.
2022, Blanchard et al., 2017; Luan et al.
2024). The robustness performance of these methods
has been analyzed on IID (Xie et a 2018: Yin et al. [018]] Turan et al. [022] Blanchard et al.
2017: Wu et al., 2020 Zhu and Ling, 2023; Karimireddy al., (021) and pon-IID datasets (Pillutla
Luan et al. 2022, Li et al. 2019; Luan et al. 2024), with the wish of achieving a stationary point. Most existing studies have established convergence to a neighborhood of stationary points, while none have thus far guaranteed convergence with zero optimality gap, that is, assured convergence to a true stationary point. It is worth noting that most prior work has primarily concentrated on designing sophisticated aggregation schemes to counter Byzantine attacks, often overlooking the need to reduce the computational burden of aggregation. As summarized in Table the most robust aggregation algorithms typically impose significant computational overhead on the central server, with complexities dependent on parameters mainly including the model dimension p. the number of clients M, and the error tolerance of aggregation algorithm e. A more detailed survey of related work is provided in Appendix [D] In this paper, we aim to fill this research gap, i.c., to reduce the cost of computational complexity for aggregation while preserving generality to data heterogeneity. One potential approach for achieving our goal is to normalize the uploaded vectors before aggregation. Using normalization to handle gradients is widely adopted in machine learning (Cutkosky and Mchta 2020) as it helps stabilize training by ensuring that the loss remains low even under slight perturbations to model parameters (Dai et al. 2023), and by mitigating the impact of heavy-tailed noise during training (Jakovetic et al. 2023). In FL, normalization has also been used to address data heterogeneity, as demonstrated Li et al. (2021) and Wang et al. (222)). While existing literature has not applied normalization specifically to counter Byzantine attacks, its ability to tackle peavy-tailed noise suggests potential for mitigating the influence of outliers, which are commonly observed under Byzantine attacks. Even in the absence of adversarial behavior, the operation of normalization can still alleviate data heterogeneity and perform well in a FL system. Last but not least, as shown in Table 1, normalization incurs minimal computational overhead, making it highly attractive option provided it can effectively mitigate the impact of Byzantine attacks. Motivated by above factors, we investigate the realization of Federated learning employing the Normalized Gradients Algorithm on non-IID datasets and propose a novel robust aggregation algorithm named Fed-NGA Fed-NGA normalizes the vectors offloaded from participating clients and then calculates their weighted mean to update the global model parameters. Rigorous convergence analysis is conducted for the non-convex loss function.
Contributions: Our main contributions are summarized as follows:
Algorithmically, we propose new aggregation algorithm, Fed-NGA, which employs normalized gradients for aggregation to ensure robustness against Byzantine attacks and data heterogeneity. The aggregation complexity is as low as O(pM).
Theoretically, we provide a rigorous convergence analysis of the proposed Fed-NGA algorithm under non-convex loss functions. Specifically, we prove that Fed-NGA converges in the presence of Byzantine attacks, as long as the fraction of corrupted data remains below one-half, despite the presence of data heterogeneity. With regard to the convergence,
2

---

Table 1: List of references the convergence of FL under Byzantine attacks.
References
Algorithm
Function
Data Heterogeneity
Time Complexity for Aggregation
al.
2018
median
log(A)
Yin et al.
2018
trimmed mean
non-convex
IID
OlpM log(M))
strongly convex
Turan et
RANGE
non-convex
log(M)
strongly convex
Blanchurd et al.
2017
Krum
non-convex
IID
O(pM/)
Pillutla al.
2022
RFA!
strongly convex
non-IID
OlpM (MMe)))
et al.
2020
Byrd-SAGA
strongly convex
Oppid log" (MMe
Zhu and Ling
2023
BROADCAST
strongly convex
IID
(pu log" (M)"1))
1. et al.
2019
RSA?
strigly convex
non-Ill)
((MyA-B)
Karimireddy al.
2021
CClip'
non-convex
IID
Op)
al. 2024
MCA
strinlyy convex
O(pM log. (Me
This work
Fed-NGA
non-convex
non IID
O(P)))
The commonly used Weisufeld algorithm calculate geometric median not always converge. Therefore, we use currently
fastest algorithin provided in Cohhen et al (2016] to evaluate the time complexity.
The aggregation rale of RSA requies solving,
problems involving nonlinear feasible regions.
r demotes the number of times centered clipping carried out.
The algorithmic flow of MCA highly similar that of the geometric median, allowing conclude that the algurilims share the same time complexity.
establish convergence rate of O(1/T)/2-1), where T denotes the number of iterations and ò E (0, 1/2). Furthermore, under general assumptions and with a properly designed learning rate schedule, we show that the optimality gap converges neighborhood of stationary points. Remarkably, under certain mild conditions, Fed-NGA achieves exact convergence to stationary points, i.e., optimality gap, representing significant theoretical advancement over existing Byzantine-robust federated learning methods.
Numerically, we conduct extensive experiments to compare Fed-NGA with baseline meth- ods under various setups of data heterogeneity. The results confirm the superiority of our proposed Fed-NGA terms of test accuracy, robustness, and running time.
Problems Statement
In this section, we present Fed-NGA. We first describe the problem setup under Byzantine attacks.
2.1 Problem Setup
FL optimization problem: Consider FL system with one central server and M clients, which form the set M A (1,2,3,- ... .M.. For any participating client, say the mtth client, it has local dataset Sm with 5m elements. The ith element of S,, is ground-truth label Sm,; = {Am, Vn. Here, Zm,i E 2 2, 2...... M, the learning task is to train a p-dimensional model parameter w E IP to minimize the global loss function, denoted as F(w). Specifically, we aim to solve the following optimization problem:
dataset Sm for represents the input vector, and Vm. E Rou denotes the output vector. Using the
min F(w). WER"
In 1b. the global loss function F(w) is defined as
F(w)= EmEM Sm
Σ Σ
f(w, sm,),,
(2)
mE Sm.:ESm.
where f(w, sm,) denotes the loss function to evaluate the error for approximating Um, with input of x a- For convenience, we define the local loss function of the mith client as
Fm (w)) A
Σ
f(w, sm.)
(3)
Sm
3

---

and the weight coefficient of the mit client as am function F(w) is rewritten as
EIEM Si m E M. Then the global loss
Sm
F(w) E am Fm(
mEM
Accordingly, the gradient of the loss function of F(w) and Fi (w) with respect to the model parameter w are written as VF(w) and V (w), respectively.
In the conventional FL framework, iterative interactions between central server and group of M clients are performed to update the global model parameter w until convergence, under the assumption that all clients transmit reliable messages. However, in the presence of Byzantine attacks, the key challenge in solving the optimization problem (I) lies in the ability of Byzantine clients to collude and send arbitrarily malicious updates to the server, thereby distorting the learning process. This underscores the need for a federated training framework that is robust against such adversarial behavior.
Byzantine attack: Based on the above FL framework, assume there are B Byzantine clients out of M total clients, which form the set B, Any Byzantine client can send arbitrary vector E IP to the central server. Suppose d'm is the actual vector uploaded by the mth client to the central server during the tth round of iteration, then we have
I' = *, m E B.
For ease of representing the ratio of Byzantine attacks, we denote the intensity level of the Byzantine attack C.. with the weight coefficient of the mit client, as
C. -
Σ mEB
Om ΣiEm S₁
1
Em.
Sm.
(6)
mEB
Intuitively, we assume C. < 0.5, a common assumption in many studies Xie et 2018); Yin et al. (2018); (Piluttaa et al. (2022); : Wu et al. (2020); (Zhu and Ling (2023) Li et al. (2019). Accordingly, the ratio of honest clients can defieed as
Ca = 1 1C.
2.2 Algorithm Description
To achieve design goal, we develop Fed- NGA. In each iteration, the honest clients up- load their locally trained gradient vectors to the central server, while B Byzantine clients may send arbitrary vectors to bias the FL learning process. After receiving the uploaded vectors from all M clients, the central server normalizes each vector and uses the normalized vectors to update the global model parameter. Once the global model parameter is updated, the central server broadcasts to all M clients in prepa- ration for the next iteration of training. Below, we provide a full description of Fed-NGA (see Algorithm
Cantral
Alak
Bycantine Clients
Honest Clients
D and Figure [T), with its crucial steps explained in detail as follows.
Figure Illustration of the learning process Fed- NGA on iteration number t.
In the tth round of iteration, after receiving the global model parameter w broadcast by the central server, all honest clients m, where m .M \ B, select a subdataset et. from their dataset S., to calculate their local training gradient V F... (w"", st.)). Meanwhile, all Byzantine clients m, where m E B, may send arbitrary vectors or other malicious messages based on their dataset and the global model parameter w Let g'n represent the vector (either the local training gradient or malicious message) uploaded the central server by client m, and we have
Local Updating:
V VF S,m)
MMA B
dim
(8)
m E B

---

Algorithm 1: Fed-NGA Algorithm
1: Input: Initial global model parameter w clients set M, and the number of iteration T..
2: Output: Updated global model parameter w
3: % % Initialization
4: Every client establishes its set S. for M B.
5: for (- 0, ... T - 1 do
6: for every client m .M \ in parallel do
7:
Receive the global model w'. Select sub-dataset e. from Sm to train local model and evaluate the local training gradient V (w <m). Set Im V Fm (w", (m) and upload g to the central server.
8:
end for
9: for every client m E B in parallel do
Receive the global model wf. Generate an arbitrary vector malicious vector gim based on w' and dataset Sm Upload this vector I'm to the central server. end for
12: Receive all uploaded vectors Im E M. Normalize all uploaded vectors g'n to generate g'. Update the global model parameter w++1 by
w w n/ g'
(11)
13: Broadcast the model parameter ++ to all clients.
14: end for
15: Output the model parameter w
Aggregation and Broadcasting: the tth iteration, upon receiving the vectors g'n from clients m E M,, the central server normalizes each vector by dividing its corresponding norm and updates the global model parameter w+11 using the learning rate 17", as given by
w ++ w r
Om
(9)
lgt
MEM
For convenience, also define
g'm
g
Σ Om MEM
(10)
which represents the weighted sum of the normalized local gradients from all clients in the tth iteration. Then, the central server broadcasts the global model parameter w all clients in preparation for the calculation in the f + 1th iteration.
3 Theoretical Results
In this section, we theoretically analyze the robustness and convergence performance of Fed-NGA on non-lII datasets. Below, we first present the necessary assumptions.
3.1 Assumption
First. we state some general assumptions for m .M \ B, which are also assumed in Huang al. (023): Wu et al. (2023); Xiao and Ji (2023).
Assumption 3.1 (Lipschitz Continuity). The loss function f(w, sm,)) has L-Lipschitz continuity, i... for Vw,, Wa e RP, it follows that
f(w1, sm,)) f(w2, sm.)) < (V sm.)), w1 - W22 + ||w1
wz2
(12)
given that the local loss functions F., (w) are linear combinations of the loss function f(w, 8m. Huang et al. (2023). it can be rigorously deduced that they all exhibit Lipschitz
Under Assumption
3.1

---

continuity. By an analogous line of reasoning, the global loss function can also be shown to satisfy Lipschitz continuity. notable characteristic of Lipschitz continuous functions is that they can be non-convex, which provides flexibility in the analysis and optimization of these functions.
Assumption 3.2 (Local Unbiased Gradient). For Em S Sm. the gradient of local training loss function Fm(w; Em) unbiased, which implies that
V Fm (w, {m) V. (w)
(13)
This assumption is widely adopted in the literature Huang et al. (2023): : Wu et al. (2023); Xiao and Ji (2023), and V Fm (m,,mm) reduces to the exact gradient V (w) when Çm Sm.
Assumption 3.3 (Bounded Inner Error: Type 1). For Vw E RP, the inner error of gradients is uniformly bounded, i.e.,
E ( (w,
FFm(w))) C.
(14)
This assumption is also assumed in Huang et al. 2023 Wu et al. (2023); Xiao and (2023).
Assumption 3.4 (Bounded Data Heterogeneity: Type I), We define representation of data hetero- geneity by inspecting gradient direction, i.e.,
Om (m)))) VF(w)l
(15)
We also assume the data heterogeneity is bounded, which implics
On
(16)
where 9 is the heterogeneity upper bound.
This assumption is also assumed in Huang et al.
2023 Wu et al. (0023 Xiao and (2023).
Building upon the aforementioned general assumptions, we introduce two refined variants, which are Their relationships with Assumptions 3.3 and 3. are
demonstrated to be reasonable in Appendix A also discussed therein.
Assumption 3.5 (Bounded Inner Error: Type II). For Vw E IR, an alternative bound on the inner gradient error is presented as follows:
Fm Em)
(m)
E
o'.
(17)
F El)
V (w)
Assumption 3.6 (Bounded Data Heterogeneity: Type II), For m M, define another representa- tion of data heterogeneity by inspecting gradient direction, i.e.,
V (w)
VF(w)
8 =
(18)
[F)(
[F(w)]
Then the bounded data beterogeneity implics
0'n < 0'
(19)
where 0' is the heterogeneity upper bound.
3.2 Convergence Analysis
In this subsection, we present the convergence analysis the proposed Fed-NGA algorithm for non-convex loss functions that satisfy Assumption 3.T. All the proofs are deferred to Appendix F and Appendix[] F
3.2.1
With Assumption
and
3.3 and
3.4
on the loss function
Theorem 3.7. With Assumption 3.7 3.2
3.3
3.4
and p such that
2p C. 1> O, we have p+l
T-1
2p Ca - 1 |||((0)) S E(F(w²) -F(wF)
TT (n
20
p Cola +
p+1
Σr1 n
2 2 n¹
2
t=
(20)

---

Proof. Please refer to Appendix E
Remark 3.8. For the case with Assumption 3.3 and Assumption 3.4, the bound of optimality gap and convergence rate in Theorem 3.7 reveal the impact of learning rate ry', the ratio of Byzantine attack Co (i.e., - C.), Type I inner error bound a, and Type I data heterogeneity bound 0 on the convergence performance for our proposed Fed-NGA. With the above results, to reduce the optimality gap and speed up the convergence rate, we need to first select an appropriate learning rate ny'. Then we analyze the robustness of Fed-NGA to Byzantine attacks on non-IID datasets under our selected learning rate. All the discussions are given as follows:
T-1 With regard to the optimality gap, when lim Σ T-o0 t=
r/ do and lim En7) < oc, T-200
together with the prerequisite condition of Theorem 3.7 can be derived that the av-
erage iteration error Σ. Ei (22 Ca - 1) n/ V F(")ll converges O(o + 0).
Therefore, min
VF (w") will converge to O( + 0).
To further concretize the convergence rate, we set n/' = n c) 1/2+6 >> O, where à is an arbitrary value lying between (0, 1/2). Then, the right-hand side of (20) is upper bounded by
(F(w") - F(ww)) 1/T
+0
Lmy11 + 28 281 20) 20)
+ +0
20²
colo+ (21)
27'2-6
p+1
which still converges to O
20 p+1
Calo + 0)) as T + co. a rate of O (1/T2-0).
The constraint 2p C. - > and the term 20² Ca + which characterizes the p+1 optimality gap, reveal a trade-off between the optimality gap and the tolerable ratio of Byzantine clients in the proposed Fed-NGA algorithm. the extreme case where there no Byzantine clients (i.e., Ca = 1), the optimality gap can be reduced to as small as + A.
p+I
3.2.2
With Assumption
3.5 and on on the loss function
Theorem 3.9. With Assumption
3.1
3.5 3.6 and (2 (01) Ca Ca -
1>> 0, we have
T-1 Σ 0=
E
(F(w0) F(w")}
L EΣTI
T-1 (1/²)2
n' VF(''))
(2
(012 2 d')Ca
Etiom 2(22- (0r) o')Co -1
Ex-o n²
(22)
Proof. Please refer to Appendix F
Remark 3.10. For the case based on Assumption 3.5 and 3.6 the bound of optimality gap and convergence rate in Theorem 3.9 reveal the impact of learning rate 17", the ratio of Byzantine attack C., Type II inner eгror bound a', and Type II data heterogeneity bound 6' on the convergence performance for our proposed Fed-NGA. With the above results, to reduce the optimality gap and speed up the convergence rate, we first select appropriate learning rate 1/¹, and then analyze the associated robustness of Fed-NGA to Byzantine attacks on non-III datasets, which are given as follows:
T-1
With regard to the optimality gap, when lim
Σ
dc and lim Σ oc.
T-000
T-000
together with the prerequisite condition of Theorem 3.9 it can be derived that the average
iteration error (1 (1/2XT111) nf) ET- of [[VF((")] converges to O.
To further concretize the convergence rate, we set = n arbitrary value lying between (0, 1/2). Then, the right-hand side of (22 is upper bounded
O, where ò is an
7

---

Table 2: The maximum test accuracy (%) for Fed-NGA and baselines is evaluated under different types of Byzantine attacks, with the concentration parameter 3 = 0.6, with TinyImageNet (Ca, = 0.2, MobileNetV3), CIFARIO (Ca 0.3, LeNet), and MNIST (Ca 0.4, MLP) datasets.
CHARIE
Atash Navo
No Attack
Gaaolan
Saau-ridie
Sig=-1t
1.2
Fst.
No. Araak
Gonolia
Slps-pp
L3K
TVE
No. Al.Attck
Cunaniia
Suce-1ake
Stax-Bip
LIE
Fed-NG
$5.45
55.11
09.31
65.56
15:33
51.13
$1.66
$1.03
$1.16
$1.05
$1.65
01:11
01.02
Folteg
35.97
0.34
01:01
15.43
Midia
18.05
65:01
11
11:41
16.07
18.00
14.54
1966
10.20
16.00
36.55
14.14
50.01
47.52
63.00
67.33
42.59
40/0
Knes
35.30
16.75
30:08
16.31
36.00
0.50
13:35
36.55
10.11
90.7
36.66
14.00
60.40
67.35
50.53
62.34
02.71
67.50
CC3p
30.0
42.59
4331
38.88
03.68
13.25
4833
4342
100
0000
41.9
1800
94.55
94.87
00.99
900
94305
920
by
B (F - F]
Lm(1 + - -28T-26)
O
+ +0
(23)
((2 (07)2 Oa)Ca 1) 1/72 -5
2 2(
10112
2 - -0yCaa - -1)
(-1))3 T3-
which still converges to 0 as T + 0o, at a rate of O (1/T
As discussed in Appendix A in the ideal scenario where both the inner error and data heterogeneity remain uniformly small throughout the entire training process, or in the case of full-batch training on IID datasets (i.e., o' and e' = 0), such that Assumptions and hold at all training iterations, convergence to a stationary point with zero optimality gap can be rigorously guaranteed. more general scenarios, Assumptions and (36 as well Assumptions 3.3 3.4] can be adopted in an alternating manner. Specifically. during the early stages of training when gradient norms are typically large, Assumptions [3d and a.e more likely to be satisfied, thereby guiding the learning process toward convergence with zero optimality gap. As the model approaches convergence and gradient norms become smaller, Assumptions 3.3 and 3.4 become more applicable and continue to ensure convergence.
Experiments
4.1 Setup
Datasets, Models and Hyperparameters: Our experiments are conducted on the TinylmageNet.
CIFAR1O, and MNIST datasets, utilizing the MobileNetV3 (Howard et al.) 2019), LeNet (LeCun)
al. 1998), and Multilayer Perceptron (MLP) (Yue et al. 2022) models. For the non-lID settings, we adopt the Dirichlet (3) distribution, where the label distribution on each device follows Dirichlet distribution with 3 > 0 as the concentration parameter. Additionally, we consider five types of Byzantine attacks to bias the FL training process. Further details are provided in Appendix B
The convergence performance of six methods (Fed-NGA, FedAvg, Median, Krum, Geometric Median (GM), MCA (Luan al. 2024)), and CClip (Karimireddy et al. 2021) is compared. Among these, FedAvg is renowned in traditional FL and can be used as a performance metric with no Byzantine attacks. Median, Krum, GM, MCA, and CClip utilize coordinate- wise median, Krum, geometric median, maximum correntropy aggregation, and centered clipping, respectively, to update the global model parameters over the uploaded messages.
Baselines:
evaluate the performance of Fed-NGA, we compare it with other baselines by measuring both the test accuracy and the running time of the parameter aggregation process (excluding model training time at local, see Appendix B for implementation specifics). Higher test accuracy indicates better performance, while a lower running time reflects greater efficiency in the aggregation process.
Metries:
4.2 Results for Convergence Performance
We begin with Table Saale and Table which summarize the maximum test accuracy and running time (excluding model training time at local) of Fed-NGA and baselines under five types of Byzantine attacks for three learning models. Figure? 2 shows the maximum test accuracy with f 0.6 on CIFAR10 10 dataset and LeNet model. Figure presents the running time of Fed-NGA and the baselines
8

---

Table 3: The running time (in seconds) of Fed-NGA and robust baselines is evaluated under different types of Byzantine attacks, with the concentration parameter of 3 = 0.6, with TinylmageNet (Ca 0.2, MobileNetV3), CIFARIO (C. 0.3, LeNet), and MNIST (Ca 0.4, MLP) datasets.
Niuk New
Milk
Lemriben
Neeevake
1.0
T+E
No.10 1i.4
Uravibis
Noveriate
9gx-8p
1.K
Fak
No Nivel
Genviie
Sige4ly
1.01
F+l
8.380
0.142
8.1801
0.311
(11911
0.167
3.003
0.899
8.8544
8.401
61812
8.40
00643
$.800
8.861
0.821
04..0
Medis
0.322
0.2903
22.143
11.03
4.505
53301
53753
4.990
53586
1.05
11833
1.075
4.809
2538
1330
1.353
124.5
CC3p
2.88
22758
33174
155M
3.030
3230
5.809
4.50
30015
306-
4.073
1860
1.007
2726
4.505
39437
1254
76437
(a) Gaussian attack.
(b) Sign-flip attack.
(c) LIE attack.
(d) FoE attack.
Figure 2: The maximum test accuracy (%) for Fed-NGA and baselines with / 0.6 on CIFARIO dataset and LeNet model.
under Same-value attacks on TinylmageNer and MNIST datasets. Finally, Figure demonstrates the convergence of Fed-NGA on the TinylmageNer dataset across three distinct data heterogeneity concentration parameters. Additional experimental results and detailed performance analysis are provided in Appendix C
Byzantine Attack Robustness Analysis: Table quantifies Fed-NGA's superior robustness on TinylmageNet across pristine (no-attack) and five Byzantine attack scenarios. Fed-NGA achieves minimum accuracy improvements 1.27% no-attack environments and peak gains of 2.35% under Byzantine attacks, demonstrating remarkable resistance to Sign- flip and FoE attacks. On CIFARIO with Ca 0.3 and 3 0.6, Fed-NGA attains SoTA with accuracy enhancements ranging from 0.35% to 5.37%. For MNIST, while showing marginal parity (-0.01% %) with baselines under LIE attacks, Fed-NGA delivers substantial improvements of 13.55% and 26.62% against Same-value and FoE attacks respectively. Figure validates these findings, illustrating Fed-NGA's consistent defensive efficacy across varying attack intensities.
(a) TinylmageNet dataset.
(b) MNIST dataset.
(a) LIE attack.
(b) FoE attack.
Figure 3: The rumning time (s) for Fed-NGA and baselines is evaluated Same-value at- tack and f = 0.6 across three different Byzan- tine ratios.
Figure 4: The maximum test accuracy (%) for Fed-NGA is evaluated TinyImageNet dataset and C. = 0.2 across three different data heterogeneity concentration parameters.
Running Time: From Table 3 Fed-NGA demonstrates the shortest parameter aggregation time among robust baselines across all datasets and model architectures. For the TinylmageNe dataset, Fed-NGA establishes state-of-the-ar (SoTA) performance, achieving the lowest aggregation latency under all Byzantine attack scenarios. The efficiency gap becomes even more pronounced on CIFARIO 10, where baseline methods require at least 100x longer aggregation time than Fed-NGA for LeNet. When applied to simpler datasets like MNIST, other robust baselines exhibit aggregation times at least 20x longer than those of Fed-NGA. As shown in Figure 3, Fed-NGA requires only 3x the aggregation time of FedAvg while maintaining Byzantine resilience. These results collectively

---

demonstrate Fed-NGA's significant advantages in computational efficiency compared to existing robust aggregation algorithms.
Data Heterogeneity: Figure illustrates the relationship between data heterogeneity and Fed- NGA's classification performance TinylmageNer with C. 0.2. The results show inverse correlation between the concentration parameter 3 and test accuracy: As 8 decreases (indicating greater data heterogeneity), Fed-NGA's performance gradually declines. Furthermore, the results exhibit differential sensitivity to data heterogeneity depending on attack type.
Conclusion
In this paper, we proposed Fed-NGA, a simple yet effective algorithm that addresses the dual challenges of Byzantine robustness and data heterogeneity in FL. By leveraging normalized gradients and lightweight aggregation rule, Fed-NGA significantly reduces computational overhead while maintaining strong theoretical guarantees. Our analysis establishes convergence to a neighborhood of stationary points under general assumptions, and to true stationary point under some other mild conditions, with provable convergence rate of ( (1/TT1/2-6), Empirical evaluations standard benchmarks validate the practical benefits of Fed-NGA in terms of both time efficiency and robustness. With regard limitation, more general assumptions may be required guarantee zero optimality gap, although this work is the first to prove it for Byzantine-resistan FL algorithms but under some mild conditions.
Acknowledgment
This work was supported by the National Natural Science Foundation of China Nos.62171034 U2336211, 62471424, 62576364, 92267202, the Guangdong Provincial Key Laboratory of Future Networks of Intelligence No.2022B121201000
References
Baruch, G., Baruch, M., and Goldberg, Y. (2019). A little is enough: Circumventing defenses for distributed learning, Advances in Neural Information Processing Systems, 32.
Blanchard, P., El Mhamdi, F. M., Guerraoui, R., and Stainer, J. (2017). Machine learning with
adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30.
Cao, X. and Lai, L. (2019). Distributed gradient descent algorithm robust to an arbitrary number of byzantine attackers. IEEE Transactions on Signal Processing, 67(22):5850-5864.
Chen, Y., Su, L., and Xu, J. (2017). Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 122):1-25.
Cohen, M. B., Lee, Y., Miller, G., Pachocki, J., and Sidford, A. (2016). Geometric median in nearly linear time. In Proceedings of the forty- forty-eighth annual ACM symposium on Theory of Computing, pages 9-21.
Cutkosky, A. and Mehta, H. (2020). Momentum improves normalized sgd. In International conference on machine learning, pages 2260-2268. PMLR.
Dai, Y., Ahn, K., and Sra, S. (2023). The crucial role of normalization in sharpness-aware minimiza- tion. Advances in Neural Information Processing Systems, 36:67741-677 67770.
Defazio, A., Bach, F., and Lacoste-Julien, S. (2014). Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27.
Dorfman, R., Vargaftik, S., Ben-Itzhak, Y., and Levy, K. Y. (2023). Docofl: downlink compression for cross-device federated learning. International Conference on Machine Learning, pages 4356-8388 PMLR
10

---

Guo, Y., Tang, X., and Lin, Т. (2023). Fedbr: Improving federated learning on heterogeneous data via local learning bias reduction. In International Conference on Machine Learning, pages 12034-12054. PMLR.
Howard, A., Sandler, M., Chu, G., Chen, L.-C.,, Chen, B., Tan, M., Wang, W., Zhu, Y., Pang, R., Vasudevan, V., et al. (2019). Searching for mobilenetv3. In Proceedings of the IEEF/CVF international conference on computer vision, pages 1314-1324.
Huang, M., Zhang, D., and Ji. K. (2023). Achieving linear speedup in non-iid federated bilevel learning. International Conference on Machine Learning, pages 14039-14059, PMLR.
Jakovetić, D., Bajovié, D., Sahu, A. K., Kar. S., Miloševié, N., and Stamenković, D. (2023). Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy- tail noise. SIAM Journal Optimization, 33(2):394 423.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. (2021). Advances and open problems in federated learning. Foundations and trends in machine learning, 14(1-2)11-210.
Karimireddy, S. He, L., and Jaggi, M. (2021). Learning from history for byzantine robust optimization. In International conference on machine learning, pages 5311-5315 PMLR.
Konečný, McMahan, H. B., Yu, X., Richtárik, P., Suresh, A. T., and Bacon, (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 1610.5549
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, (1998). Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):22)8-22333
Li, L., Xu, W., Chen, T., Giannakis, G. B., and Ling, Q. (2019). RSA: Byzantine-robus, stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 1544-1551.
Li, T. Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. (2020). Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429- 450.
Li, X., Jiang, M., Zhang, X., Kamp, M., and Dou, Q. (2021). Fedbn: Federated learning on non-iid features via local batch normalization. arXiv preprint arXiv:2102.07623.
Luan, Z., Li, W., Liu, M., and Chen, B. (2024). Robust federated learning: Maximum correntropy aggregation against byzantine attacks. IEEE Transactions on Neural Networks and Learning Systems.
McMahan, B., Moore, E., Ramage, D., Hampson, S.,, and y Arcas, B. A. (2017). Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR.
Pillutla, K., Kakade, S. M., and Harchaoui, Z. (2022). Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70: 70:1142-1154,
So, J.. Güler, B., and Avestimehr, A. S. (2020). Byzantine-resilient secure federated learning. 1EEE Journal on Selected Areas in Communications, 39(7):2168-211 -181.
Turan, B., Uribe, C. A., Wai, H.-T., and Alizadeh, M. (2022). Robust distributed optimization with randomly corrupted gradients. IEEE Transactions on Signal Processing, 70:3484-3495
Vempaty, A., Tong, L., and Varshney, P. K. (2013). Distributed inference with byzantine data: State- of-the-art review on data falsification attacks. IEEE Signal Processing Magazine, 30(5):65-75.
Wang, J., Liu, Q. Liang, H., Joshi, G., and Poor, H. V. (2020). Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 1-7623.

---

Wang, S., Tuor, T., Salonidis, T., Leung, K. K., Makaya, C., He, T., and Chan. K. (2019). Adaptive federated learning resource constrained edge computing systems. journal on selected areas in communications, 37(6):1205-12211
Wu, F. Guo, S., Qu, Z., He. S., Liu, Z. and Gao, J. (2023). Anchor sampling for federated learning with partial client participation. In International Conference on Machine Learning, pages 77379-374161 PMLR.
Wu, Z.,, Ling, Q., Chen, T., and Giannakis, G. B. (2020). Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583-4596.
Xiao, P. and Ji, K. (2023). Communication-efficccnn federated hypergradient computation via aggregated iterative differentiation. In International Conference on Machine Learning, pages 38059-38000 38086. PMLR.
Xie, C., Koyejo, O., and Gupta, I. (2018). Generalized byzantine-tolerant SGD, arXiv preprint arXiv:1802.10116.
Xie, C., Koyejo, O., and Gupta, (2020). Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pages 261-270. PMLR.
Xie, Z. and Song. S. (2023). Fedkl: Tackling data heterogeneity in federated reinforcement learning by penalizing kl divergence. IEEE Journal on Selected Areas in Communications, 41(4):1227-1242
Yang. Z., Gang, A., and Bajwa, W. U. (2020). snvvessay-resilieen distributed and decentralized statistical inference and machine learning: An overview of recent advances under the byzantine threat model. IEEE Signal Processing Magazine, 3763):146-15.
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. (2018). Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650-5659. PMLR.
Yue, K., Jin, R., Pilgrim, R., Wong, C.-W., Baron, D., and Dai, H. (2022). Neural tangent kernel empowered federated learning. In International Conference on Machine Learning, pages 25783- 25803. PMLR.
Zhao, P., Yu, F,, and Wan, Z. (2024). A huber loss minimization approach to byzantine robust federated learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 21806-21814.
Zhao, Y., Li, M., Lai, L.,, Suda, N., Civin, D., and Chandra, V. (2018). Federated learning with non-iid data. arXiv preprint arXiv: (0XXVv/8066000 1806.00582.
Zhu, H. and Ling, Q. (2023). Byzantine-robuss distributed learning with compression. Transactions Signal and Information Processing over Networks.
IEEE
Zuo, S., Yan, X., Fan, R., Hu, H., Shan, H., and Quek, T. Q. S. (2024). Byzantine-resillen federated learning with adaptivity to data heterogeneity.
12

---

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: We introduce the main contributions and scope about this paper in the abstract and the end of introduction. The claims align with algorithmic framework and numerical results, suggesting their applicability across various settings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
NA answer to this question will not be 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.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
In this paper, Section 5 discusses the our proposed algorithm's 's limitations.
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 are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn 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 tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't '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 set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: Section 3.1 we present fundamental assumptions serving as the foundation for generalization. In Appendix A we justiff the rationality of our two mild assumptions. For the detailed proofs of our proposed theorems under these assumptions in Section 3.1 they are provided in Appendices and
Guidelines:
The answer NA means that the paper does not include theoretical results.
the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 4 Appendix and C we give the detail of the experiments setups, including dataset, model, and hyperparameters settings, clearly.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 are provided or not.
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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 to 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, or other means that are appropriate to the research performed.
While NeurlPS 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) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way 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 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
14

---

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, described in supplemental material?
Answer: [No]
Justification: The paper's contributions mainly involve theoretical proofs and al- gorithm, which can verified according the detail of the algorithm in Section g easily. Furthermore, the datasets
are all public.
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 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 NeurIPS code and data submission guidelines (https
bttiis..ccppublicuuu.eeee
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) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: 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 to understand the results?
Answer: [Yes]
Justification: In Section 4 Appendix B and C give the detail of the experiments setups, including dataset, model, and hyperparameters settings, clearly.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Appendix C gives the final test accuracy under different setting of the test segmentation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

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, or 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 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 error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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: In Appendix B we reported the type and number of GPUs and CPU, the version about the Py and the type and version of OS.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as 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 fidn't make it 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 httts://neurips.c http://pp...pp....pp.ccccceeeaee
Answer: [Yes]
Justification: In Section discuss about the application scenarios of Fed-NGA in society. And we believe there is no negative socictal impacts of this work.
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).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In Section [ we discuss about the application scenarios of Fed-NGA in society. And we believe there is negative societal impacts of this work.
Guidelines:
16

---

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 no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.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 not 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 a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as 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 unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
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 have this kind of risk.
Guidelines:
The answer NA means that the paper poses 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 to usage guidelines or restrictions to 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 not 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: We cite the original papers of the models used. The elements of the figures in the article are publicly available and allowed for free use, and we use public dataset to test our algorithm.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
17

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular 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 it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 NeurlPS Code of Ethics, 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 equivalent for research with human subjects
Question: 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
18

---

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
Does the paper describe the usage of LLMs if 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, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Our paper 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 as any important, original, non-standard components.
Please refer to our LLM policy (https://neurd) auttep://eearrppcccc///ooeeeeeer //t//////oeeeeeece/22////..... for what should or should not be described.
19

---

de with A The Reasonableness of Assumptions 3.5 and 3.6
To justify Assumptions 3.5 and 3.6 we observe that the direction of the gradient conveys more critical information than its norm, as the impact of the norm can be modulated by the learning rate 17'. Motivated by this insight, we redefine the notions of inner error bound and data het- erogeneity bound purely from the perspective of gradient direction, leading to the concepts of Type II inner error and Type II data heterogene- ity, as formalized in Assumptions 3.5 and 3.6
21 22
22 Teil
Regarding the relationship between Assump- tions 3.3 and 3.5 (i.e., Type and Type II in- ner error bound), as well as Assumptions 3.4 (i..,,,, Type I and Type II data heterogene- ity bound), we offer the following insights. As illustrated Figure when the norms of both vectors and 22 are greater than 1, it can be ob-
1
served that ||r x2| exceeds
Figure 5: The illustration depicts the vectors 21. 21 T2, Ø1 - 22, |[i][| |[a]||
Therefore, ||I| - æ2|| < on. then the nor- malized distance is also bounded by Tu- Con- versely, when ||~1|| < 1 and ||2l|| < 1, the
22 and |
21
Teall
the radius of the circle set to 1.
[.. ||all| dominates and hence provides
tighter bound ||||| - =2ll. Motivated by this observation, we map the gradient vectors (F(w). Fm (w), and V (w, Em) to Iy and 22, and draw the following implications: When the norms of the concerned gradients are relatively large (e.g., greater than 1), Assumptions 3.3 and 3.4 are more restrictive. In contrast, when the norms of concerned gradients are small, Assumptions 3.5 and 3.6 become more restrictive. In practice, the selection of the appropriate assumption set should be guided by the behavior and scale of gradient norms during different stages of training.
Reviewing the training process, gradient norms are typically large during the early stages and gradually decrease to below 1 as training progresses. Consequently, in the initial phase, Assumptions (.5 3.6
being more relaxed, are more likely to hold, thereby guiding the training toward convergence with zero optimality gap. As the model nears convergence and the gradient norms diminish, Assumptions 3.3
and 3.4 become more suitable and also ensure convergence. Notably, if the inner error and data heterogeneity remain consistently small throughout the entire training process, i.c., Assumptions 3.5 and 3.6 at all iterations, then convergence to stationary point with zero optimality gap can be rigorously guaranteed.
B Experimental Setups in Detail
To carry out our experiments, we set up a machine learning environment in PyTorch 2.2.2 on Ubuntu 20.04, powered by four RTX A6000 GPUs and one AMD 7702 CPU. Firstly, we describe the datasets as below:
Datasets:
MNIST:
MNIST dataset includes training set and test set. The training set contains 60000 samples and the test set contains 10000 samples, each sample of which is 28 x 28 pixel grayscale image.
CIFAR10: The CIFAR10 dataset includes training set and test set. The training set contains 50,000 samples, and the test set contains 10,000 samples, each of which a 32 x 32 pixel color image.
20

---

TinyImageNet: The TinyImageNet dataset consists of a training set, validation set, and test set. The training set includes 100,000 samples, while both the validation set and the test set contain 10,000 samples each. Each sample is a 64 64 pixel color image.
We split the above three datasets into M non-llI training sets, which is realized by letting the label of data samples to conform to Dirichlet distribution. The extent of non-IID can be adjusted by tuning the concentration parameter 3 of Dirichlet distribution.
Models: We adopt LeNet, Multilayer Perceptron (MLP), and MobileNetV3 models, respectively. The introduction of these three models is as follows:
The LeNet model is one of the earliest published convolutional neural networks. For the experiments, like LeCun et al. (1998), two convolutional layers (both kernel sizes are 5 and the out channel of first one is 6 and second one is 16), two pooling layers (both kernel size are 2 and stride are 2), and three fully connected layer (the first one is (16 4 4, 120), the second is (120, 60) and the last is (60, 10)) for MNIST dataset. And for CIFAR 10 dataset, we going to train LeNet model with two convolutional layers (both kernel size are 5 and the out channels are 64), two pooling layers (both kernel size are 2 and stride are 2), and three fully connected layers (the first one is (64 * 5 555, 5, 384), the second is (384, 192) and the last is (192, 10)). Cross-entropy function taken as the training loss.
LeNet:
going to train LeNet model with
MLP:
The MLP model is machine learning model based on Feedforward Neural Network that can achieve high-level feature extraction and classification. We configure the MLP model to be with three connected layers (the first one (28 28, 200), the second is (200, 100) and the last is (100, 10)). And for CIFAR 10 dataset, we configure the MI.P model to be with three connected layers (the first one is (3* 32 * 32, 200), the second is (200, 200) and the last is (200, 10)) like Yue et al. (2022). And also cross-entropy function is taken as the training loss.
MobileNetV3 a lightweight convolutional neural network (CNN) metic- ulously optimized for mobile and embedded devices. It integrates depthwise separable convolutions with Neural Architecture Search (NAS) to enable efficient feature extraction and classification under strict computational constraints, with its detailed architectural de- sign documented in Howard et al. (2019). For specific dataset adaptability, we conducted fine-tuning to optimize its performance on the TinylmageNet dataset, ensuring robust feature learning across its 200-class image corpus.
MobileNetV3:
Hyperparameters: We set M = 50 and fix the batch size at 32 across all experiments. For numerically computing the GM and MCA, the error tolerance is defined as 1 x 10-5 The concentration parameter 3 takes values 0.6, 0.4, and 0.2. The number of iterations is configured as 500 for the MNIST and CIFARIO datasets, and 100 for the TinylmageNet dataset.
Regarding learning rates:
On MNIST dataset, Fed-NGA employs ry"
2v0.00214T' while baseline methods use
1)'
2V0.1984+I'
For CIFARIO dataset, Fed-NGA uses n/'
V0.002r41 with baselines adopting nf
198141
On TinyImageNet dataset, Fed-NGA uses 1/
1.2
whereas baselines use 17
v0.014+T
100/0.01E4T
These divergent learning rate schedules stem from Fed-NGA's gradient normalization mechanism, which introduces variations in gradient magnitudes across iterations. Using Fed-NGA's learning rates for baseline methods leads to substantially degraded performance, necessitating tailored adjustments to maintain stability and convergence. For time complexity benchmarking, we implement distinct numerical computation frameworks tailored to time complexity: TensorFlow tensor operations accelerate MobileNetV3's execution profiling due to its deep architecture, while NumPy array computations handle the lightweight LeNet and MLP models.
21

---

Byzantine Attacks: The ratio of Byzantine attacks, Ca, is set to O, 0.1, 0.2, 0.3, and 0.4, We select five types of Byzantine attacks, which are introduced as follows.
Gaussian attack: All Byzantine attacks are selected as the Gaussian attack, which obeys (0,, 81).
Same-value attack: Each dimension of the Byzantine clients' uploaded vector to
Sign-flip attack: All Byzantine clients upload -3 EmeMis In to the central server on iteration number t.
LIE attack (Baruch et al., 2019): LIE attack adds small amounts of noise to each dimension of the benign gradients. The noise controlled by coefficient c. which enables the attack to evade detection by robust aggregation methods while negatively impacting the global model. Specifically, the attacker calculates the mean p and standard deviation v of the parameters submitted by honest users, calculates the coefficient based on the total number of honest and malicious clients, and finally computes the malicious update as p + cv. We set to 0.7.
FoE attack (Xie et al. 2020): The FoE attack enables Byzantine clients to upload M-B EM Im to disrupt the FL training process. The coefficient is configured differ- ently based on the specific attack and algorithm. For FedAvg, we set g -3 (M B). For Median, Krum, and GM, we set q -0.1. For MCA and CClip, we also set q -3 (M - B). the case our proposed Fed-NGA, since the uploaded vec- tors are normalized, the value of does not influence the actual aggregation. Nonetheless, we set -3 (M B) for consistency.
C Results for Convergence Performance in Detail
C.1 Training Performance for Different Byzantine Attacks
Taa Aucuumey
Tou Aeccumecy
Tess Aecuumeyy
Reration Number
Beration Number
Eeration Number
(a) LeNet and B = 0.6.
(b) LeNet and B = 0.4.
(c) LeNet and B = 0.2.
Accuwryy
Acqunry
Acanreyy
Banation Number
Number
Ecrab on Numberr
(d) MLP and 3 = 0.6.
(e) MLP and / 0.4.
(f) MLP and 3 0.2.
Figure 6: The test accuracy (%) over 500 iterations for Fed-NGA and baselines is evaluated without Byzantine attacks on MNIST dataset.
In this section, we analyze the training performance under various Byzantine attacks, referencing Table 4 Table and Table as well as Figure [ Figure 7 Figure g Figure 9 Figure TO and Figure
11 Tables 4 Table 5 and Table summarize the maximum test accuracy for Fed-NGA and baselines under four Byzantine ratios, three data heterogeneity concentration parameter setups, five types of Byzantine attacks, and three learning models, applied to the MNIST, CIFARIO, and TinylmageNet
22

---

Table The maximum test accuracy (%) of 500 iterations of Fed-NGA and baselines with different types, ratios of Byzantine attack, and concentration parameter on MNIST dataset and two learning models.
Aralk Name
No Arteck
Genecian bttack
Sacte vollevieeeeeeeoee Aiteck
Atback
LJF Atteck
Mold
001
0.2
03
0.4
0.1
044
0.1
0.3
0.3
0.4
0.1
R2
03
0.4
D.1
Algxlin
Pel-NGA
98.58
96,39
98,17
90.63
97.48
97.00
$3.96
$8.25
$1.34
98.24
98.16
96.02
97.52
95,3T
95.18
90,0
97.64
18.34
98.16
98432
97.53
97.25
11.35
1:35
11:55
95.27
$3.50
$9.36
87.33
11:55
Kram
05.04
33
94.95
95.00
9457
$130
5121
90-14
75.37
GM
90.04
07.12
90.26
97.11
91.43
16.22
94.53
91.54
18.76
97.15
95.82
56.51
99.23
95.50
$1.40
99.17
97.47
$4.77
7.61
5.88
8.92
MCA
97.68
96,10
07.78
97.61
12.02
97.80
1::55
11.35
11.35
97.68
11.26
9:80
10,09
93.01
5132
97.66
97.35
51.68
11:35
5.30
10.09
9.50
Lohit
11:35
15
11.35
10/19
10:04
61.22
11
50663
19.19
11:35
10.37
10.00
Modia
92.99
00.37
00.90
34.30
59.70
10675
$2.59
35.55
10:45
91.50
$3.18
50.65
12223
93.24
53.19
15.79
14443
59:77
$6.72
06.14
13.27
Aram
03.23
02.83
03.97
59.80
09.75
50.51
12:32
68.25
10:42
53.25
93.03
$5,10
91.99
92.36
$3
50.56
14
50.2
53.52
64.41
13.09
CCky
90:45
07.32
97.48
17.55
96.57
90.87
9.82
$0.30
11.35
97.41
9.90
9.80
9.50
56
$7.45
07.27
97.37
S7.1
9.50
5.50
9:30
Fell NGA
96.72
96.40
96.87
55.16
94.98
03.05
79.75
$6.55
$3.65
96.21
95.00
95.34
94.7
96.4
$5.00
95.35
9499
96.21
95.00
9483
94.71
10.25
11.35
9.62
62.95
78.43
92.71
02.08
00.75
60055
90.34
92.35
51.77
77.94
67.50
GM
94.69
94.75
94.15
46
94.46
05.70
90.55
85.25
70.11
34.
54.55
50.96
14.31
94.65
54,00
54.35
94.33
51.15
5005
11:45
11.12
MCA
03.15
05.00
05.00
56
94.82
95.15
13.15
11.35
11.35
34
51.51
11.01
11.35
95.15
55.20
04.33
04.54
54.4
91.51
11.91
11.35
9.50
MLP
13.05
14:37
15.55
10.74
10.00
10.10
30
10:04
53.77
33
10.00
11:35
10.00
Mediun
91.36
91.44
10082
21:21
51.08
1A492
55.00
73.07
47.12
00.05
90.27
50.96
91.20
91.30
91.55
$0.0
38.16
70440
$1.04
Xraza
91:33
91.30
91.00
90.95
50.82
55.37
78.55
48.25
91.07
90.26
50.06
19.52
11.31
$1.16
91.25
91.33
50.70
18.45
SUL12
-0.22
CC3p
95.00
94.94
94.99
34.75
94.76
04:95
10.32
10.10
10.10
92.57
14.47
9.00
9.50
95.06
55.05
94.95
$4.77
14.47
5.50
9:30
(a) Gaussian attack.
(b) Same-value attack.
(c) Sign-flip attack.
C5
056
<on
(d) LIE attack.
(c) FoR attack.
Figure The maximum test accuracy (%) over 500 iterations for Fed-NGA and baselines is evaluated on the MNIST dataset and MLP model wiht B = 0.2 across five different Byzantine ratios.
23

---

Rirrosion Rumber
Biroo on Number
Reration Number
LeNet and 0.6.
LeNet and 0.4.
LeNet and 0.2.
"Tat
(d) MLP and 3 0.6. (e) MLP and 3 0.4.
(i) MLP and 3 0.2.
Figure 8: The test accuracy (%) over 500 iterations for Fed-NGA and baselines is evaluated on CIFARIO 10 dataset without Byzantine attacks.
6.6
(a) Gaussian attack.
(b) Same-value attack.
(c) Sign-flip attack.
(d) LIE attack.
(c) FoE attack.
Figure The maximum test accuracy (%) over 500 iterations for Fed-NGA and baselines is evaluated on the CIFAR10 dataset and LeNet model with 3 = 0.4 across five different Byzantine ratios.
datasets, respectively. Figure 6 Figure g and Figure 10 illustrate the test accuracy trends for Fed- NGA and baselines under three data heterogeneity concentration parameters and three learning models in the absence of Byzantine attacks, respectively. Figure 7 Figure and Figure [1 present the maximum test accuracy for Fed-NGA and baselines across four Byzantine ratios, under three data heterogeneity concentration parameters, for three learning models on the MNIST, CIFARIO, and TinylmageNet datasets, respectively. In the subsequent analysis, we evaluate the performance Fed-NGA and baseline methods according to the type of Byzantine attack.
the MNIST, CIFARIO, and TinyImageNet datasets,

---

Table The maximum test accuracy (%) of 500 iterations of Fed-NGA and baselines with different types, ratios of Byzantine attack, and concentration parameter on CIFARIO dataset and two learning models.
Aralk Name
No Artckk
Genecias bttack
Sacte voler Aiteck
Atback
LIF Atteck
Mold
0.1
0.2
03
044
0.1
02
04
0.1
0.3
033
0.4
0.1
R2
03
0.4
D.1
Algxiton
Pel-NGA
54.48
63,88
63,60
52.67
58
45.95
38.58
26.16
35.90
53.60
$3.49
$1.16
R066
$3.06
$1.88
80.6
5340
F3.49
$1.66
99.65
FedArg
10.00
10.05
10.00
10.00
10.31
1863
1000
1093
Kram
40.70
41.43
41.08
55
12.41
22.54
10:46
34.25
36,67
40.22
40.05
40:59
78.99
25.00
11:25
GM
45.41
47.73
47.53
06
48.25
42.95
5635
29.51
21.15
45.
43.55
41.00
47.06
45.08
45.15
47,00
46.90
51.55
1006
1047
10.04
MCA
63
45,99
47.90
40.52
41.00
40.34
10.00
12.00
10000
47.69
34.07
10000
10,00
45.18
45,02
48.25
43.92
4120
3407
1000
10.00
Lohit
11
16/00
00
10:45
10:00
00
10/00
10/00
10.00
30.00
10000
10.00
10:54
10.35
10:4
1800
1000
1000
10.00
Media
35.66
S7/25
29.05
35.43
37.14
21.35
31.30
11:20
10085
36.17
33.00
$1.00
26:25
37.60
39:47
16.40
5505
35.75
25.56
11:52
1090
64
Kram
21.64
30.01
31.33
35:31
39.12
30.95
23.68
11.16
10:75
35.32
37.16
37,19
$7.50
35.23
31355
S7.06
56.0
34.66
24.99
11.9
691
CCkp
47.90
48,33
43.37
44:05
46:53
48.27
10.00
10.00
10/00
47.30
41.04
10000
10.00
55.50
45
47.58
4501
47:30
44.64
1000
10.00
Fell NGA
48.26
47.78
47.82
46.53
46.19
30.57
25.99
30.54
19.00
47.50
47.36
46.40
4677
45.10
47.40
46.49
46.15
47.00
47.26
46.48
45.32
FedArg
10.00
10,00
18.12
14:54
Kram
40.34
36-42
74.94
34.06
34.05
39,00
76.00
40.55
40.44
4062
20.9
19.37
34.00
21.4
17.04
GM
64
45,00
46.03
43.00
45:51
31.19
25.53
20.99
15.56
43.43
48.19
44,09
44.71
5.
45
44.90
44.44
36.26
18:22
9.55
10.92
MCA
46.63
43.96
46.23
5::0
44.65
46.21
12.65
12.00
10000
43.52
25.55
13.01
10.00
40
45.29
44.95
4490
45.52
20.35
1391
10.00
MLP
PedAig
11
11:41
13:67
13:3
17:45
10:00
10:00
10.00
10/00
30.00
11.76
10:58
17:90
1643
13.91
1000
11.75
10.04
Modian
30.35
58.42
30.47
35.72
35.00
35.17
26.63
17.51
15:25
37.83
35.16
30.36
20,32
35.55
39.54
18:76
39.75
37:55
24.05
22.99
12.55
04
Kram
21.34
38,79
31441
39.23
39.83
33.06
26.15
17.00
16:72
3544
35.41
35.39
26,75
35.02
40UI1
37.29
35.14
22.75
12.00
39.51
13.03
CC3p
18
46.48
45.28
45.00
45.38
45.99
10.00
10.00
10/00
44.10
10.00
1000
10.00
45
45:95
44.10
1000
1000
10.00
Beraion Number
Benaton Number
beration Number
(a) 0 = 0.6.
(b) 8 = 0.4.
(c) B = 0.2.
Figure 10: The test accuracy (%) over 100 iterations for Fed-NGA and baselines is evaluated on TinylmageNet dataset and MobileNetV3 model without Byzantine attacks.
First, for the simpler dataset (MNIST), Table and Figure 6 demonstrate that Fed- NGA consistently outperforms all other baselines across different data heterogeneity concentration parameter configurations and two learning models in the absence of Byzantine attacks. Specifically, compared the baselines, Fed-NGA improves test accuracy for the LeNet model by 0.81 %, and 0.74% for data heterogeneity concentration parameters B = 0.6, and 0.2, respectively. Similarly, for the MLP model, Fed-NGA achieves test accuracy gains of 1. 1.4%, and 1.17% for data heterogeneity concentration parameters 3 = 0.6, and 0.2, respectively. Moreover, as shown in Figure 6, the convergence speed of Fed-NGA is comparable to that of other baselines and exhibits superior performance under different data heterogeneity conditions. In contrast, the Median and Krum methods demonstrate poor performance irrespective of the learning model used. For the more complex CIFAR1O 10 dataset, Table and Figure 8 also highlight the advantages of Fed-NGA over
No Attack:
25

---

Table The maximum test accuracy (%) of 100 iterations Fed-NGA and baselines with differ- ent types, ratios of Byzantine attack, and concentration parameter on MobileNetV3 model.
dataset and
No.
roler
LJR
Attal:
82
Algesttee
56.55
54.54
49.11
22.68
2.00
$5338
13.41
0.50
56.20
PedArs
33.67
43.33
46.07
40.12
34.30
0/72
0.34
0.51
820
220
0.30
1.30
0.50
51.57
46.15
43.95
42.00
0.30
0.30
0.50
0:30
Medion
18:45
05.90
05.00
11.00
15.03
12331
41.1
$6.0
50.35
36.19
21.01
1.54
9.34
16.06
65.07
15.35
15.66
43.00
38.00
23,00
3,23
66
Krom
36.33
15.84
16.76
14.00
37.85
36.07
1066
31.0
11.67
56.55
16.11
95.55
17
15
15.05
96
13.75
0.51
0.50
0:47
33.08
54.43
54.22
33.50
48.08
50.71
43.14
4.7
0.02
$4.56
54.32
$3.25
42.85
0.53
Ma
51.17
831
3.0
0.30
0:20
Medoo
1030
17.09
36.77
4040
60.34
10.75
7.61
10.76
16.54
43.01
90.20
2//8
Kram
33.52
26.82
30.12
23.50
11.43
35.97
30.30
23.59
$1.15
51.31
12.00
34.89
2007
11AT
30.37
32.00
33.36
0148
0145
0.48
0.43
GM
55.33
51.66
50.01
53.66
53.04
53.01
47A1
3:98
861
5000
1967
0.17
0.00
50.01
51.59
51.9
53.61
50.49
74-61
6.11
810
59.32
54.95
5505
00900
0.00
5408
54.19
0.50
46.92
35:35
43.17
34.33
15.90
31.14
0.2
46.25
45.69
41.53
(a) Gaussian attack.
(b) Same-value attack.
(c) Sign-flip attack.
020
A20
020
(d) LIE attack.
(c) FoE attack.
The maximum test accuracy (%) over 100 iterations for Fed-NGA and baselines is evaluated on the TinylmageNet dataset and MobileNetV3 model with B = 0.6 across five different Byzantine ratios.
Figure 11:
other baselines across different data heterogeneity concentration parameter configurations and two learning models without Byzantine attacks. Compared the MNIST dataset, Fed-NGA achieves even more pronounced improvements on the CIFAR 10 dataset, improving test accuracy for the LeNet model by 5.37%, and 5.55% for data heterogeneity concentration parameters 3 0.6, and 0.4, respectively. For the MLP model, Fed-NGA achieves test accuracy gains of 1.65%, and 1.67% for data heterogeneity concentration parameters 3 0.6, and 0.4, respectively. Furthermore, Figure indicates that Fed-NGA demonstrates convergence speed comparable other baselines for both learning models, while maintaining greater stability in the presence of high data heterogeneity. Finally for TinyImageNe dataset, Table 6 and Figure I0 show Fed-NGA outperformed baselines across different data heterogeneity concentration parameter configurations on MobileNerV3 model without Byzantine attack. Fed-NGA improves the test accuracy by 1.27% and 1.5% for B = 0.6, and 0.4, respectively. Also, as shown in Figure TO we can easily see the advantages of Fed-NGA compared with basclines.
26

---

Finally, on the InyamageNet dataset, Table 6 and Figure 10 demonstrate Fed-NGA's consistent supe- riority over baseline methods under varying data heterogeneity settings (8 values) when implemented on MobileNerV3 models in non-Byzantine scenarios. Specifically, Fed-NGA yields test accuracy improvements of 1.27% and 1.5% for concentration parameters 3 = 0.6 and 0.4, respectively. Fur- thermore, the visual comparison in Figure cleaarly reveals Fed-NGA's accelerated convergence rate and enhanced stability throughout the training process compared to conventional approaches.
First, we assess the training performance of Fed - -GA and the baselines on the MNIST dataset. As presented in Table 4 among all the baselines, Fed NGA attains the highest test accuracy in most instances (with the exception of / = 0.2 on the MLP model) across four different Byzantine ratios,For the LeNet model, when considering the data heterogeneity concentration parameters, Fed-NGA enhances the test accuracy by 0% to 1.27% for 3 = 0.6 and by 0.04% to 0.79% for 3 = 0.2 across the four different Byzantine ratios. Similarly, on the MI. model, Fed-NGA boosts the test accuracy by 0.11 %% to 1.4% for 3 = 0.6 and by 0.15% to 1.17% for = 0.2. Furthermore, as depicted in Figure 7 it is evident that Fed-NGA is robust against all types of Byzantine attacks and maintains excellent performance across the four different Byzantine ratios. Turning to the CIFARIO dataset, Table shows that Fed-NGA outperforms all baselines, achieving the highest test accuracy. Specifically, Fed-NGA improves test accuracy on the LeNet model by 2.39% to 5.32%, and 1.44% to 4.88% across four different Byzantine ratios for data heterogeneity concentration parameters B 0.6, and 0.4, respectively. Similarly, for the MLP model, Fed-NGA achieves improvements of 0.68% to 1.92%, and 0.59% to 1.79% across four different Byzantine ratios for data heterogeneity concentration parameters B 0.6, and 0.4, respectively. Moreover, Figure P verifies Fed-NGA's sustained robustness to Gaussian attacks, maintaining the highest accuracy across four Byzantine ratios. For the Imayeme dataset, Table 6 demonstrates Fed-NGA's statistically significant superiority over baseline methods across data heterogeneity settings C. = 0.1, 0.2, and 0.3, achieving peak test accuracy while showing minor limitations at C. 0.4. When implemented on the MobileNet model under Byzantine attack scenarios, Fed-NGA achieves accuracy gains ranging from -0.54% 1.9% and -1.4% 1.5% across four Byzantine client ratios, corresponding to data heterogeneity parameters 3 = 0.6 and 0.4 respectively. The complementary analysis in Figure further confirms Fed-NGA's consistent stability and accuracy advantages of experimental configurations.
Gaussian Attack:
Referencing the Same-value attack, the performance of Fed-NGA is not always the best among all baselines, but it is undoubtedly the most stable. For the MNIST dataset, as shown in Table 4 Fed-NGA improves test accuracy by 2.48% to 64.19% under high Byzantine ratios (C, = 0.4) on the LeNet model. A similar phenomenon is observed for the MLP model with C. = 0.3 and 0.4, where the accuracy improvement ranges from 0.04% 14.27%. From Figure 7 all robust methods experience performance degradation as the Byzantine ratio increases. Even under high data heterogeneity, where other baselines may fail to converge, Fed-NGA demonstrates the least performance degradation, highlighting its stability in the face of high data heterogeneity and Byzantine ratios. On the CIFAR1O dataset, Fed-NGA exhibits a consistent performance trend with the MNIST results, achieving test accuracy improvements of 0.24%-11.63 % under high Byzantine ratios (Ca = 0.3, 0.4). As shown in Figure 9 Fed-NGA maintains accuracy advantages across most attack scenarios while remaining marginally below baselines at C. = 0.1. However, the TinyImageNet dataset exhibits distinct behavioral patterns compared to the other two benchmark datasets. Intriguingly, we observe an unexpected positive correlation between Byzantine client ratios and test accuracy the Median method, which the set of Same-value attack is not reasonable. Notably, Fed-NGA demonstrates measurable improvements of 0.53% and 0.04% test accuracy at C. = 0.1, while maintaining competitive performance at high Byzantine ratio surpassing all bascline methods except the Median and Krum approaches. These findings corroborated by the comparative analysis in Figure II which further validates Fed-NGA's robustness across heterogencous experimental conditions.
Same-value Attack:
Sign-flip Attack:
For the MNIST dataset, Table 4 illustrates that Fed-NGA achieves higher test accuracy than all baselines in most cases with the exception of B = 0.2 and C. = 0.4 on the LeNet model-across four Byzantine ratios. Specifically, under the data heterogeneity parameter 3 = 0.6, Fed-NGA improves test accuracy on the LeNet model by 0.24% to 1.34% across all Byzantine ratios. When 3 = 0.2, a minor performance gap of approximately 0.06% arises only at C. 0.4; in all other scenarios, accuracy improvements reach up to 1.14%, highlighting its robustness to varying data distributions. On the MLP model, Fed- yields 0.4% to 1.47% accuracy
27

---

gains for 3 = 0.6 and 0.3% to 1.62% for 3 = 0.2 across the four Byzantine ratios, consistently outperforming baseline methods. Moreover, Figure 7 visually demonstrates the superiority of Fed- NGA: the framework maintains notable accuracy lead over baselines, showcasing resilience across all evaluated Byzantine attack scenarios. For the CIFARIO 10 dataset, using the LeNet model, Fed-NGA achieves performance improvements of 3.27% to 5.47%, and 1 1.52% to 5.75% across four Byzantine ratios for data heterogeneity concentration parameters B = 0.6, and 0.4, respectively. For the MLP model, Fed-NGA achieves similar improvements, ranging from 1.01 % to 2.38%, and 0.7% to 1.99%, across the same conditions. Moreover, as shown in Figure 9 Fed-NGA consistently outperforms under the Sign-flip attack regardless of the Byzantine ratio. Only the GM method demonstrates comparable performance under scenarios with high Byzantine ratios and significant data heterogeneity. Turning to the TinyImageNet dataset, Fed-NGA demonstrates significant superiority at C. = 0.2, achieving test accuracy improvements of 2.24% and 1.78% under data heterogeneity parameters 3 = -0.6 and = 0.4 respectively. Notably, we observe inverse performance pattern under high Byzantine ratios where all comparative methods underperform Krum a divergence from results observed in smaller-scale datasets. This phenomenon may stem from MobileNetV3's s enhanced architectural complexity and expanded parameter space (relative to baseline models), which potentially aligns better with Krum's 's robust aggregation paradigm. These findings are validated through the comparative analysis in Figure
We first evaluate the training performance of Fed-NGA and baselines on the MNIST dataset. As shown in Table 4 Fed-NGA achieves the highest test accuracy among all baselines except for the case of C. 0.4. For the LeNet model, under data heterogeneity parameters / = 0.6 and [ = 0.2, test accuracy changes range from a slight decrease of 0.03% to an increase of 0.36%, and from a 0.22% decrease accuracy variations span from a 0.01% % decrease to a 0.79% increase for B = 0.6, and from a 0.45% decrease 0.78% increase for 3 0.2, reflecting Fed-NGA's competitive performance across most configurations. Additionally, Figure demonstrates that Fed-NGA maintains stable test accuracy when facing attacks of different proportions, outperforming baselines in most scenarios. This consistency highlights the framework's 's ability to withstand both data heterogeneity and Byzantine attacks during training. For the CIFARIO dataset, Fed-NGA consistently outperforms all baselines under all experimental setups. Test accuracy increases by 3 3.26% to 5.75%, and 1.4% to 4. 4.96% for the LeNet model, and by 1.11% to 1.7% and 0.38% to 2.09% for the MLP model, across four Byzantine ratios for data heterogeneity concentration parameters | = 0.6, and 0.4, respectively. As further evidenced by Figure 9 Fed-NGA maintains robust performance against LIE attack, achieving the highest accuracy among comparative baselines. Finally, we evaluate Fed-NGA's performance on the TinyImageNee dataset under varying Byzantine attack scenarios. While Fed-NGA does not universally dominate across all four Byzantine ratios and two data heterogeneity parameters (B- = 0.6, 0.4), it demonstrates significant superiority in most experimental configurations. The framework achieves marginal improvements ranging from 0.04% to 1.6% in test accuracy across these settings. with only a single outlier instance showing a 1.78% degradation at C₂ = 0.4 combined with 3 = 0.4. Crucially, evidenced in Figure II Fed-NGA exhibits remarkable resilience against LIE attack. outperforming all baseline methods by maintaining superior decision boundaries in high-dimensional feature spaces.
LIE Attack:
0.44% increase, respectively. For the MLP model, corresponding
7
Against the newly proposed Byzantine attack, the FoE attack, Fed-NGA exhibits superior defense performance compared to all baseline methods, regardless of the dataset, learning model, or data heterogeneity level. For the MNIST dataset, as shown in Table Fed-NGA improves test accuracy by 0.56% to 85.57% and 0.67% to 83.54% for data heterogeneity concentration parameters 3 = 0.6, and 0.2, respectively, across four different Byzantine ratios. For the MLP model, Fed-NGA also enhances test accuracy by 1.67% to 26. and 0.91% to 43.34% for data heterogeneity concentration parameters 8 = 0.6, and 0.2, respectively. Figure 6 conclusively demonstrates that Fed-NGA maintains the highest test accuracy across all four Byzantine client ratios under FoE attacks. Similarly, on the CIFARIO dataset, Fed-NGA achieves test accuracy improvements of 5.91% % to 38.87%, and 5.75% to 38.97% for data heterogeneity concentration parameters 3 = 0.6, and 0.4, respectively, across four different Byzantine ratios. For the MLP model, Fed-NGA provides additional improvements of 2.38% 28.34%, and 2313% to 32.95% for data heterogeneity concentration parameters 3 = 0.6, and 0.4, respectively. Moreover, Figure 9 demonstrates that although the training performance of Fed-NGA decreases the Byzantine ratio increases, its convergence remains robust and intact. In contrast, the baselines fail to converge under high Byzantine attack rates underscoring the robustness and superiority of Fed-NGA. On
FoE Attack:
28

---

Table 7: The running time (in seconds) for 500 iterations of Fed-NGA and robust baselines is evaluated under varying types and ratios of Byzantine attacks, as well as different concentration parameters, on the MNIST dataset using two learning models. Notably, only the running time of the aggregation algorithms is considered, excluding the model training time.
Bip
0.694
0.809
8.441
08.21
0.900
8.827
08:04
04017
SteBion
1281
1,475
1,733
1,800
1.4417
1.347
18465
1.505
1.500
1.46
1430
1/230
1.435
1350
1.000
1460
1,89
03553
1
1302
1306
1339
1.500
1796
1.511
1483
1.000
1435
1.447
13400
1.001
12205
12200
28775
30670
36550
2.1443
43750
555.3
22101
12209
45792
0.001
00472
8.044
0.440
04627
6.344
6.401
00437
0641
0141
5.444
0.007
0U4D4
0.485
CASI
01411
0.444
0.407
1.336
1.000
1.005
50014
12200
1/074
1000
13884
1488
1231
13864
14013
Kmn
12500
1.044
1.334
12044
1.044
12544
1/040
1352
1442
1.30
13485
1.450
1.200
15575
1241
039955
2060
26411
30033
1AD4S
1.20
070114
CC3y
1.300
12000
12200
1.825
02215
39722
1099
13803
20133
515
3:6:55
2530
140
1382
1.504
6.000
33050
59644
De6NGA
0.484
8.481
6.4472
00407
8.347
0.545
00443
06401
01423
6.411
DU413
0.407
RM22
0945
0.577
Media
45015
51482
3.141
52804
51385
33433
5120
3348
5483
51400
5.371
5180
5.336
3
5.1544
4.540
19605
MEA
12239
1.108
1.107
1.499
1.411
2.0566
5557
12.03
5.192
57355
31431
134.5
1250
1.000
1
1259
3131
31431
134.5
MIP
CUit
13007
11224
1,945
1,2000
1.722
1,292
35547
433133
47950
4.387
52971
775.7
74437
1330
1.131
1507
13541
41557
175.33
744.77
Po6NGA
6.649
8,500
0.8335
01544
0.345
0.845
SU4SS
0144
084S5
01507
0.505
0U423
B.ML1
0.559
0A512
5,425
0,007
G2M
3.400
32010
4.996
4.789
45502
3,101
45185
12
3.120
44871
51002
5.315
22716
24476
25055
74475
147150
MBA
1.5765
1.420
12701
1.102
10006
5,005
4.131
60076
40574
23722
AXTI0
30.37
342
1.306
1,2122
13130
1.400
2
30037
3-2.4
CC3y
15441
1.61d
19996
12122
12314
4.354
38811
4.414
56.14
35899
50070
703.
09.31
1.072
1.090
12289
1.881
5,079
09.51
the TinyImageNet dataset, Fed-NGA demonstrates consistent superiority over all baseline methods at C. 0.2, achieving statistically significant accuracy gains of 2.35% and 3.93% under data heterogeneity parameters 3 = 0.6 and 3 = 0.4 respectively. Notably, we observe a paradigm shift in high Byzantine scenarios where all methodologies exhibit degraded performance
marked contrast to patterns seen in smaller-scale datasets, as validated in Figure| [1] Crucially, under low Byzantine ratios (0.1 and 0.2), Fed-NGA maintains competitive advantages across evaluation metrics.
C.2 Aggregation Running Time Analysis
In this section, we analyze the running time under different Byzantine attacks, referencing Table 7 Ta Table 9 Figure [2] Figure 13 and Figure [4] Table 7 Table g and Table 9 provide the running time for Fed-NGA and robust baselines under four Byzantine ratios, three data heterogeneity concentration parameter setups, five types of Byzantine attacks, and three learning models, applied to the MNIST, CIFARIO and TinyImageNet datasets, respectively. Figure [2] Figure [3] and Figure 14 depict the running time for Fed-NGA and baselines under three Byzantine ratios and three learning models, for the MNIST dataset with 3 = 0.2, the CIFARIO dataset with 3 = 0.4, and the TinylmageNet dataset with 3 = 0.6, respectively. In the following analysis, we assess the performance of Fed-NGA and baselines in relation to the type of dataset.
From Table it is evident that Fed-NGA outperforms the baselines in terms of aggregated running time. In the absence of Byzantine attacks, the aggregated running time of some bascline methods is up 20 times, and in some cases over 100 times, that of Fed-NGA. This demonstrates that the proposed algorithm significantly reduces computational complexity. Under Byzantine attacks, the aggregated running time of baseline methods increases markedly with higher Byzantine ratios, whereas Fed-NGA remains unaffected due to its straightforward normalization of uploaded vectors. Specifically, the aggregated running time of baselines is at least 20 times, and in some instances up to 200 times, the running time of our algorithm Fed-NGA. Furthermore, as shown in Figure [2] while Fed-NGA requires only 2 to 2.5 times the aggregation cost of FedAvg, it achieves robustness against Byzantine attacks with time cost that is merely 1/20 of other robust algorithms. This highlights the fast and efficient nature of Fed-NGA aligning with our theoretical proofs and underscoring its effecttivnnes in experimental settings.
MNIST Dataset:
29

---

13
(a) LeNet and Gaussian attack.
(b) LeNet and Same-value attack.
(c) LeNet and Sign-flip attack.
(d) MLP and Gaussian attack.
(e) MLP and LIE attack.
(1) MLP and FoE attack.
Figure 12: The running time (s) over 500 iterations for Fed-NGA and baselines is evaluated on the MNIST dataset and 3 0.2 across three different Byzantine ratios.
(a) LeNet and Gaussian attack.
(b) LeNet and Sale-value attack.
(c) LeNet and Sign-flip attack.
564
0.89
0
(d) MLP and Gaussian attack.
(c) MLP and LIE attack.
(f) MLP and FoE attack.
Figure 13: The running time (s) over 500 iterations for Fed-NGA and baselines is evaluated on the CIFAR10 dataset and B = 0.4 across three different Byzantine ratios.
Similarly to the case of the MNIST dataset, Fed-NGA outperforms the baselines in terms of aggregated running time. Due the increased complexity of the dataset and learning models, the aggregation time cost for Fed-NGA and the baselines is significantly higher than that observed for the MNIST dataset. As shown Table g the aggregation time cost for the robust baselines is at least 60 times, and in some cases up to 500 times, that of our proposed Fed-NGA algorithm. Moreover, consistent with the MNIST results, Figure 13 illustrates that while Fed-NGA requires only 2 to 2.5 times the aggregation cost of FedAvg, it achieves robustness against Byzantine attacks with a time cost that is merely 1/60 of other robust algorithms. These results reaffirm the fast and efficient nature of Fed-NGA.
CIFAR10 Dataset:
30

---

Table 8: The running time (in seconds) for 500 iterations of Fed-NGA and robust baselines is evaluated under varying types and ratios of Byzamtine attacks, as well as different concentration parameters, on the CIFARIO dataset using two learning models. Notably, only the running time of the aggregation algorithms is considered, excluding the model training time.
0.2
Pwl/NG NG.
8.498
6.6977
8.822
011224
08843
Modiun
32.60
31.359
31685
31.90
31,05
32.70
31185
30 410
25.16
31317
30
34155
30:357
25380
Knee
31.73
666
33.766
11.000
33908
11.03
92515
54.56
12.20
30500
51 235
32.077
50500
31,00
30.755
30604
25009
GM
1997
11.60
1.500
16791
1800
115
09496
MBA
63329
6.1991
6.74
13342
53812
34033
16.313
14667
1399
12115
72373
12.00
14567
13564
121L5
Median
12:09
30.774
22.94
21,112
31,53
24.70
30539
30.35
33
31.155
23.13
30.224
20512
10.343
Kmnh
22.51
13
21.112
31.479
31.05
31255
34.79
14M0
31.59
25.05
31683
11.255
23
3. 823
34785
51.00
31756
GM
1840
13.30
14117
15230
12.40
14,00
36187
26445
38.570
23.43
3005
18.22
15792
12750
13
54.21
11:97
48.50
35A22
43.415
12322
MCA
55415
11:11
1921
1196
5115
51100
5.00%
1995
11866
Knoa
14723
21.36
17.84
21.24
30547
15.05
22.299
17.293
17.275
15.000
GM
35000
5.325
19417
12.50
5.007
11.53
S1344:
75590
15
354
15335
11.551
72417
MICA
3.507
4.164
4.355
4.177
41442
7A574
30013
15574
12
6.400
130.
11175
50190
40012
4.003
43376
6.460
3,597
1323
31175
30.P
14400
0.715
1.00
5.507
17500
5,700
5.415
55.55
Pel-NGA
Krees
12.344
17:00
11:00
GM
33557
72474
7266
38665
28.900
12.000
11287
00554
30.74
7.330
7,5182
50000
35.06
21.04
35.320
45102
MBCA
42159
33851
33128
4.745
3040
44108
30012
54772
12.40
2-457
10552
16114
$77.54
4.177
4.89/
4.10
K4451
94512
19314
$73.4
CC3P
38506
30817
2570
3753/
57827
2,793
83773
12085
11422
23700
72285
19534
562.7
3.25L
3,662
37507
37800
5370
722.55
155.44
550.7
Table 9: The running time (in seconds) for 100 iterations of Fed-NGA and robust baselines is evaluated under varying types and ratios of Byzantine attacks, as well as different concentration parameters, the TinylmageNet dataset using MobileNetV3 model. Notably, only the running time of the aggregation a algorithms is considered, excluding the model training time.
Fall Attcc
Alpesias
Fri M6A
6.195
8.0922
0.194
0.144
0.193
8.191
8.196
0,095
SLITON
ELI922
1LIN12
1L1912
8,201
6,377
6,311
3150
5.444
4.234
4.991
4.664
5,322
5.841
8.324
8.557
45124
7,500
DA256
57212
53722
55855
556-1
44499
31
33270
NCCA
3.546
31140
2.400
35277
2460
3.000
5,259
3.315
12100
4,403
GARI
214.6
4J4G4
4.126
4090
4.3775
4.575
4.500
4,575
CC3p
32796
19945
24371
2014
3.302
3.1MO
3USM
3,323
3,557
31420
Kmm
47642
45102
47.65
17.05
03.511
4TAST
47.299
48 25
JU121
45105
29.29
45391
456%6
48:29
GM
31331
4.055
4.007
4.801
51526
5,505
4.447
55000
7.754
1M47
55512
57MI
55003
5004
$7500
12240
74145
15155
2.420
2.085
38023
20139
3.073
5.202
21.24
4A328
213.8
40212
44824
4/150
43829
43000
Tiny ImageNet Dataset: Fed-NGA maintains its computational efficiency advantage over robust baselines on the TinylmageNet benchmark. As evidenced in Table 9 our method achieves state- of-the-art (SoTA) time efficiency across all robust aggregation benchmarks. The baseline methods demonstrate 1.5x higher aggregation time costs compared Fed-NGA's optimized workflow. Notably, Figure 14 reveals that while Fed-NGA marginally trails FedAvg in absolute speed an expected trade-off given FedAvg's 's vulnerability to Byzantine attacks - it achieves superior robustness--fficinncy balance. These empirical results conclusively validate Fed-NGA's time complexity advantages in large-scale FI. scenarios.
C.3 Convergence Performance of Data Heterogeneity
In this section, we analyze the training performance under different data heterogeneity concentration parameter setups, as illustrated in Figure 15
Figure 16 and Figure 17 These figures depict the
31

---

Gaussian attack.
(h) Same-value attack.
(c) Sign-flip attack.
(d) LIE attack.
(e) FoE attack.
Figure 14: The running time (8) over 100 iterations for Fed-NGA and baselines is evaluated on the
TinyImageNet dataset, MobileNetV3 model and 0.6 across three different Byzantine ratios.
(a) Gaussian attack.
(b) Same-value attack.
(c) Sign-flip attack.
(d) FoE attack.
Figure 15: The test accuracy (%) over 500 iterations for Fed-NGA is evaluated on the MNIST dataset
and C. = 0.4 across three different data heterogeneity concentration parameters.
(a) Gaussian attack.
(b) Sign-flip attack.
(c) LIE attack.
(d) FoE attack.
Figure 16: The test accuracy (%) over 500 iterations for Fed-NGA is evaluated on the CIFAR10 dataset and C, = 0.3 across three different data heterogeneity concentration parameters.
test accuracy trends for Fed-NGA under three data heterogeneity concentration parameter setups, five types of Byzantine attacks, and three learning models, applied to the MNIST, CIFARIO, and TinyImageNet datasets, respectively. In the subsequent analysis, evaluate the performance of Fed-NGA and baseline methods in relation to the dataset type.
MNIST Dataset: From Figure 15 it is evident that as data heterogeneity increases, indicated by smaller concentration parameter values, the training performance of Fed-NGA declines. However, the performance degradation remains within acceptable range, typically resulting in only 1% to gap. This observation demonstrates the strong adaptability of Fed-NGA to varying levels of data heterogencity.
32

---

(a) Gaussian attack.
(b) Same-value attack.
(c) LIE attack.
(d) FoP: attack.
Figure 17: The test accuracy (%) over 100 iterations for Fed-NGA is evaluated on the TinylmageNet
dataset, MobileNetV3 model, and C. 0.2 across three different data heterogeneity concentration parameters.
CIFAR10 Dataset: As shown in Figure [6 the test accuracy trend of Fed-NGA is consistent with the observations for the MNIST dataset. When comparing different data heterogeneity concentration parameter setups, it is evident that the choice of learning model has more significant impact per- formance. Notably, the MLP model demonstrates greater stability across varying data heterogeneity concentration parameter setups compared to the LeNet model, although the maximum test accuracy achieved by the LeNet model is higher than that of the MLP model. Nonetheless, the performance degradation remains within an acceptable range, typically resulting in only a 2% to 3% gap.
Figure reveals Fod-NGA's accuracy dependence on data heterogeneity levels under varying Byzantine attack patterns. Specifically, the framework exhibits heightened sensitivity to data distribution skews under Same-value and FoE attacks, where heterogeneity-indee accuracy degradation exceeds in extreme cases. Conversely, for Gaussian attack and LIE attack, Fed-NGA demonstrates relative stability with marginal accuracy losses at low heterogeneity levels. This divergence from MNIST/CIFAR 10 benchmarks likely stems from MobileNetV3's enhanced parameter space and InnllmaeNeets complex feature hierarchies, which amplify both attack surface vulnerabilities and model resilience characteristics.
Tiny ImageNet Dataset:
D Related Works in Detail
FL is firstly proposed in (MeMahan et al. 2017). The security issue in FL has been focused on since the emergence of FL (Vempaty et al. [2013] Yang et al. (2020). Byzantine attack, as a common mean of distributed attacking, has also caught considerable research attention recently. In related works dealing with Byzantine attacks, various assumptions are made for loss function's 's convexity (strongly convex or non-convex), and data heterogeneity (IID dataset or non-III dataset). Furthermore, time complexity for aggregation is also a concerned performance metric as pointed out in Section [ A detailed introduction of them given the following subsections. Also summary of these related works' assumptions and performance is listed in Table [
D.1 Aggregation Strategy of Byzantine-resilient FL Algorithms
As for aggregation strategies in related literature, the measures to tolerate Byzantine attacks can be categorized median, Krum, geometric median, etc. For the methods based on Median: Xie et al. (2018) takes the coordinate-wist median of the uploaded vectors as the aggregated one, while Yin et al. (2018) aggregates the uploaded vectors by calculating their coordinate-wise median coordinate- wise trimmed mean. Differently, the Robust Aggregating Normalized Gradient Method (RANGE) (Turan et al. (022) takes the median of uploaded vectors from each client as the aggregated one, and each uploaded vector is supposed to be the median of the local gradients from multiple steps of local updating. For the methods based on Krum: Blanchard al. (2017) selects a stochastic gradient as the global one, which has the shortest Euclidean distance from group of stochastic gradients that are most closely distributed with the total number of Byzantine clients given. For the methods based on Geometric median: all existing methods, including Robust Federated Aggregation (RFA) (Pillutia al. 2022 Byzantine attack resilient distributed Stochastic Average Gradient Algorithm (Byrd- SAGA) (Wu et al. 2020), and Byzantine-ROhie Aggregation with gradient Difference Compression And STochastic variance reduction (BROADCAST) (Zhu and Ling 2023). leverage the geometric median to aggregate upload vectors. Differently, RFA selects the tail-average of local model parameter
33

---

over multiple local updating as the upload vector, both Byrd-SAGA and BROADCAST utilize the SAGA method (Defazio al., 2014) to generate the upload message while the latter one allows uploading compressed message. For Other methods: Robust Stochastic Aggregation (RSA) (Li al. 2019) penalizes the difference between local model parameters and global model parameters by la norm to isolate Byzantine clients. And Maximum Correntropy Aggregation (MCA) (Luan et al.,
2024) leverages maximum correntropy to aggregate the aggregate upload vectors. Centered Clipping
(CClip) (Karimireddy et al. (02I) employs the previously aggregated gradient as a reference, clips the modulus the gradient vector, and then performs aggregation.
D.2 Assumptions and Performance of Byzantine-resllien FL Algorithms
the aggregation complexity of median methods is all O(p (M).. To see the difference, Xie et al. (2018) verifies the robustness of Byzantine attacks on IID datasets only by experiments, while both trimmed mean (Yin et al., 2018) and RANGE TTran et a 2022) offer theoretical analysis for non-convex and strongly convex loss functions on III datasets. For the methods based on Krum: the aggregation complexity of Blanchard et al. 2017) is (p and convergence analysis is established on non-convex loss function and III datasets. For the methods based on Geometric median:
For the methods based on Median:
the time complexity for aggregation is Op (Ag (M) (Cohen et al., 2016) for all the three methods (Pillutla et al. 2022 Wu et al. 2020; Zhu and Ling (023)) which exhibit the robustness to Byzantine attacks under strongly convex loss function. Only RFA (Pillutla et al. 2022) reveals the proof on non-IID datasets, while both Byrd- SAGA (Wu et al. 2020) and BROAD CAST (Zhu and Ling 2023) are established on IID datasets. For Other methods: RSA (Li ct al. 2019) exhibits an aggregation complexity of O (MMp')) ). with its convergence performance analyzed on heterogeneous datasets for strongly convex loss functions. Similarly, MCA (uan et al. 2024), which has aggregation complexity of O(pM log"((e (M)-))). has its convergence performance evaluated on heterogeneous datasets for strongly convex loss func- tion. The CClip algorithm (Karimireddy et al. 2021), tested under IID dataset with non-convex function, exhibits Mp) aggregation complexity. Last but not least, the optimality gap of all above algorithms is non-zero.
In contrast the aforementioned studies, we focus on non-convex objectives under non- -ID data distributions. Moreover, the proposed Fed-NGA algorithm exhibits computational complexity of only (pM)) which strictly lower than that of all existing Byzantine-roke robust methods. Despite its simplicity, Fed-NGA achieves convergence and even zero optimality gap under mild conditions, which have not been theoretically established by previous Byzantine-rohuu approaches.
E Proof of Theorem 3.7
Under Assumption 3.1 and recalling ( and (10), we have
( -F((())
(VF(w"), w -w²) + L || ++ w01l
VF(W") {g')) + (n')² {1lor113
(24)
A
Ag
A2 can be easily bounded because of Jensen's 's inequality f (2 m am E am (m)(
with EmeM a'm 1, am for m M and f(x) = x², which implics that
34

---

A E {11
Σ
Im
11
MEM
Im
Oym
l1
ll
MEM
1.
(25)
Next, we aim to bound A1. According to 10 there is
A1
E,
gin
VF(W), E
Σ am
1l Il
MEM
I'm
E Om VFF(w),BB
119tn
Σ am
VF(W"),
Im
Σ
am
(VE(W))
I'm light
(26)
[1g
lI
mEMiB
mEB
B.
B2 is easier to be handled, so we first consider the bound of Bg. Because of - (xx, y) < ||=||| have
1lyll.
gh
B₂
Σ am
VF(w"),
E
mEB
g'm 119h
Σ am |F(w'>)]
MEB
(v(''')
Om
C.) /F(w')|
(27)
g'n = 1, and @ comes from the definition of C. in 7).
where ① follows from
Then aim to bound B1, which implies that
gi
}
Σ
am
E
VF(w")
llgf.
mEMiB
V Fm (w= Et.
Σ
am E
VF(w')
V Fm (w", gt )|
mEMiB
VVF 2 + (Ww) V Vmn(w' et) - VF(w)))
Σ OmE E
(28)
V V Fw'",, st.ill
m
35

---

We first assume that VF(w')I 2 2 V (m" )tm - VF(w")ll
there is
[VF(w*) (F(""), VF (w" stm - VFF(w))
18
IV (w", 6m)
VF((')I VF VI Vm 5m) v
E
V m (w', sm))
(p 1) [F
E
P PIVFF(W Fm (w*, Em) - VF(ww)]]
(p 1) (
EE
(p ( 1) [VF())V
(29)
where ! comes from - (a, b) < ||||| |b]1. 3 comes from V 2 pl|| Fa -.m) - V F
>11-
and
comes from ||a + bll S |a|| + |6|| and | 2 / Vm Fm (w",, ...) V Fx(w0))
Then considering
VF(w"))] _ م V. <th) (F ||| we have.
-B {{
(P(("))
FV (w Chh )I } $ |F(('')]
V (um
=-P-1 VF(w0)] + 2p |VF(w')]
p+1
p+1
p-1
VF( || +
2p²
VF (wo (o0'",,0 (m)) VF(w")]
1+1
p+1
(30)
Due to
V FV (m)
V VF(W))| > 0, Assumption
3.2
Assumption
3.3 and Assumption 3.4 there is
Bi S Σ am
p-1
VF(w')) )|
2p²
E
(wo" ..... <F(w')l)
1+1
p+
1
m
Σ am
p-1
|F(w')| )1 +
2p²
E
VF ( Fm((w') + Fml('") VF
p+1
p+l
m
< 0
|
C.
2p²
(a
(31)
p+1
p+1
Then Ai can bounded as follow,
A1 (22g Ca - 1) ||F 2p²
2p
([)a-11][[[[]) p+1 Cala
p+1 pp
(32)
Then we have
E
- -F(u)))))F(()} S -nj ( (f21 C. -1) ||F[((|||+
20²
Can (o +0)
(1/)
L
(33)
p+1
2
Let
20 20 C. - 1> O. we have
T-1
2p C.. - 1) [[F(''))]
E [F[(w)) F(wT))
L JET-(11'
20²
Ca +
p+1
Σi 17
2 2 op
p+1
1=
(34)
This completes the proof of Theorem 3.7
36

---

F Proof of Theorem 3.9
Regarding the proof of Theorem 3.9 only the proof of Bi is different. Then we aim to bound Bi, which implies that
B1 =-
Σ
Om VF(w'')
E
9in
mEM
Vim ( <m)
Σ Om E
VFF(c'),
mEM
(Vr(w))) ) VF(w")
[VF(w))] (Vr(w()), (wn)
VF(w")
Σ am
|| (w²)]l
[VF(w*)]
MEMiB
(VF(u"))
Vm (w' (mm) F (w+ 5
V Fm (w]²]] )))
Vi (wo')
+ E.
(35)
Because of (a,, x) = ||0l| and the definition of C. in there is,
B1 Σ am
((VF(w)),
(F)(w))
VF(w") ) +B (B((FF((')) ( VVF(w')]
VFn(w .m) | (w S..)
| Fm (w" )1 }})
V Fm Fmm('))
[VFm(w
Co |(V(('))
Σ am (VF(W'),
(F)(w")
[VF('']] +o'C. /VF(w')) C. |FF(''||
VF(w')
mE.M/B
Om VF(W')I
VF(w")
|2
(um("")
VF(w')
|
Vmm(w')
|VF(w*)]
2
VF [Fn(("))
MEMBB
(1 O'aC VF(W')I
VF (ww'))
(1 + (0th - (1 o' Ca [F(w(]]
mEMIB
2 (0) [VF(')) - ('1--''C. / |F((')]]
--(1-109 (0)) -o) d) -o-
C. \V(w'))]
(36)
where ① comes from (cr, v) & |||||| livll and Assumption 3.5 2 can be derived from (a. = 1/2 ||=|| +
I|yll || - 311. and ① is bounded by Assumption 3.6
Combining Bi and Ba. we have
A B, + B2
(0')
d)) Ca |[(('))) +1 Ca) |/
< -
2
2 (0')² d' Ca -1) ||FF('))]
(37)
Then combining A and Az, there is
E E(F(w't) - F(w')}
L
& <nn Ai + ラタ (n1)), A2
n ((2 (2- (0')²
-o'
Co -a-1)
||FF( )|+ L (n
(38)
2
37

---

Summing up the inequality in 338 for 1 0,1, ... T 1. we obtain
E F(F(w)) - F(w))
((2 2 (0') d.) d) Ca Ca-1)
T-1
L T-1
Σ of
VF
(w0
|||
+
(m') (m')
(39)
2 1=0
When (2 (0)² - o')
Ca 1 > O, dividing the inequality in (39 by ((2 (0)2
2
-
0')
Co
-1
Σ 7
on both sides, we have
E (F [w
- (1²²)
Σ r \
E
(12
(01)2 - 0')Co. 1) 2 or
2 2(
(09)
d' - 1)
Ei= n (40)
2
This completes proof of Theorem
3.9
38


Reviews:
[{"review_id": "P5aruDM9N1", "reviewer": "Reviewer_8n5C", "summary": "The paper presents Fed-NGA, a federated learning (FL) algorithm designed to enhance robustness against Byzantine attacks and data heterogeneity. Fed-NGA uses normalized gradients and computes their weighted mean for aggregation, significantly reducing computational overhead compared to existing robust aggregation methods. Experimental evaluations on standard datasets (MNIST, CIFAR-10, TinyImageNet) demonstrate the efficiency and robustness of Fed-NGA compared to baselines such as FedAvg, Median, Krum, GM, CClip, and MCA.", "questions": "- How does Fed-NGA handle partial client participation or dropped clients?\n- How does the method ensure fairness among clients with varying data quality, quantity, or training effort?\n- Have you evaluated the communication cost of your method, such as the number of transmitted bytes, communication rounds, or total bandwidth usage?", "limitations": "Yes. The paper acknowledges some limitations, but critical limitations regarding robustness to adaptive attackers, unrealistic theoretical assumptions, and neglected gradient magnitude information remain inadequately addressed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n* Overall, the structure of the paper is well-organized and easy to follow.\n* The proposed method has good potential for real-world deployment with many clients, as it significantly reduces computational overhead with O(pM) aggregation complexity.\n* The paper provides theoretical analysis supporting robustness against Byzantine attacks and convergence guarantees.\n* The experiments provide comparative analysis across multiple attacks and scenarios.\n\n**Weaknesses:**\n- My main concern is the lack of analysis of communication cost in the proposed method, which is a critical aspect of FL systems. Communication overhead can dominate computation in real-world FL deployments and making it a more critical bottleneck than the efficiency of the aggregation method itself. E.g., it is unclear if normalization incurs additional costs during message preparation or transmission.\n- There is a fairness issue related to the client’s actual contribution to the model’s improvement, i.e., normalizing gradients and aggregating them without accounting for factors such as data quality, quantity, or training effort. In real-world FL settings, clients with more useful data may not want to participate since their extra contribution is not recognized or rewarded.\n- This study may overestimate model performance and convergence speed since it assumes full client participation. It is important to consider partial participation, which is a more common and realistic form of the FL setting.", "was_revised": true, "final_justification": "After the rebuttal and discussion phase, the authors address my concerns regarding communication overhead and partial participation. Therefore, I decided to keep the positive score for this paper.", "rebuttal": "1. **Regarding the communication cost issue**\n\nRegarding the communication cost issue, as detailed in Algorithm 1 on Page 5, Fed-NGA normalizes the uploaded vectors at the central server, requiring each participating client to upload its gradient (real or fake depending on whether it is malicious). This design yields exactly the same communication cost as all the robust  baselines, and thus does not introduce any additional communication overhead.\n\n2. **Regarding clients contributing higher data quality, quantity, or training effort could deserve greater weight**\n\nWe acknowledge that clients contributing higher data quality, quantity, or training effort could deserve greater weight. Nonetheless, under the threat of uncertain Byzantine behavior, relying on such trust becomes precarious. To be specific, Byzantine clients may gradually build credibility over multiple rounds before launching attacks, making over-reliance on them risky. On the other hand, this type of time-varying behavior highlights the need for robust methods that can adapt to dynamic adversaries. Although our analysis assumes fixed Byzantine clients, the proposed method actually remains effective even when the set of Byzantine clients changes over time, as long as the per-round Byzantine ratio $\\bar{C}_{\\alpha} < 0.5$ is maintained.\n\n3. **Regarding partial client participation and dropped clients**\n\nWith regard to the case of partial participation, to the best of our knowledge, none of the existing robust aggregation methods, including ours, explicitly consider this setting. This is primarily due to a fundamental limitation. Byzantine clients, whose objective is to disrupt the training process, may consistently participate in each training round. If some honest clients are inactive due to partial participation, the instantaneous Byzantine ratio $\\bar{C}_{\\alpha}$ in a given round can exceed 0.5. This challenges the core assumption required by all Byzantine-resilient algorithms, namely that honest clients form the majority in each round, and poses a fundamental limitation on defending against Byzantine attacks without leveraging external trusted information.\nEven in scenarios where the central server randomly drops clients, regardless of whether they are Byzantine or honest, the resulting Byzantine ratio after dropping cannot be guaranteed to stay below 0.5, either.\n\nOn the other hand, partial participation or client dropout can be accommodated in our framework by treating inactive or dropped clients as Byzantine, since Byzantine clients are allowed to upload arbitrary gradients to the central server, including the null vector. Under this modeling, our theoretical results still guarantee convergence as long as the effective Byzantine ratio $\\bar{C}_{\\alpha} < 0.5$ in each training round, where inactive or dropped clients are also counted as Byzantine.\n\nIt is also worth noting that the set of tolerable inactive or dropped clients and Byzantine clients can vary across training rounds. Although our theoretical analysis assumes a fixed set of Byzantine clients, the proposed Fed-NGA actually remains effective even when the Byzantine set changes over time, demonstrating robustness under more dynamic and realistic conditions."}, {"review_id": "KxvJ749MaV", "reviewer": "Reviewer_TKaS", "summary": "Fed-NGA introduces a approach for secure federated learning, effectively addressing dual challenges of Byzantine attacks and data heterogeneity through an elegantly simple yet powerful mechanism. By aggregating normalized client gradients via weighted averaging, the algorithm achieves unprecedented computational efficiency—reducing time complexity to optimal linear scaling while maintaining strong robustness guarantees. Crucially, Fed-NGA demonstrates rigorous convergence to stationary points even under non-convex loss landscapes, with theoretical analysis confirming resilience when malicious clients comprise up to half the network. Experimental validation across diverse datasets shows significant speed advantages over existing methods while maintaining competitive accuracy, though performance gradually decreases under extreme data heterogeneity.", "questions": "See Weakness.", "limitations": "Yes, the proposed method, while promising, reveals certain limitations in the Experiments section.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1.Fed-NGA excels in algorithmic simplicity and conceptual clarity, making it highly accessible for both theoretical analysis and practical implementation. The core innovation lies in its streamlined aggregation process: instead of relying on complex statistical filters or iterative optimizations, Fed-NGA merely normalizes each client's gradient vector to unit length and computes their weighted mean.\n2.Beyond efficiency, Fed-NGA demonstrates remarkable resilience against security threats. It maintains robust performance even when malicious clients comprise 40% of the network, effectively neutralizing diverse attack strategies including Gaussian noise injection, gradient flipping, and sophisticated evasion techniques. The normalization process inherently nullifies magnitude-based attacks while preserving the directional integrity of honest updates.\n3.The algorithm also addresses the persistent challenge of data heterogeneity. Unlike alternatives that require specialized handling of non-IID data distributions, Fed-NGA's normalized gradient aggregation naturally balances biased local updates. This provides reliable performance across varying degrees of data skew without additional computational cost.\n\nWeaknesses:\n1.The algorithm exhibits concerning performance volatility when confronting Byzantine client ratios exceeding 30%, revealing a critical vulnerability threshold in its security architecture. Beyond this inflection point, coordinated attacks (particularly Same-Value and Sign-Flip strategies) trigger precipitous accuracy declines that manifest as erratic fluctuations rather than graceful degradation. \n2.Fed-NGA displays heightened sensitivity to data heterogeneity that compounds operational challenges in practical environments. As client data distributions become increasingly skewed—quantified by decreasing β values in the Dirichlet allocation framework, the algorithm suffers progressive performance erosion that persists despite its superiority over conventional baselines.", "was_revised": true, "final_justification": "After the rebuttal and discussion process, I am happy to change my decision to accept this paper.", "rebuttal": "1. **Regarding Weakness 1**\n\nWith regard to Weakness 1, we acknowledge that the performance degradation of Fed-NGA is not entirely uniform. However, as shown in Figure 7 (Page 15) and Figure 9 (Page 16), nearly all baselines exhibit an inflection point where the degradation pattern shifts from a gradual to a markedly faster decline in test accuracy. For instance, Figure 7(b) and Figure 9(b) demonstrate that MCA and CClip experience a modest decline when $\\bar{C_{\\alpha}} \\leq 0.1$, followed by a steep drop under the Same-value attack, reaching their lowest performance at $\\bar{C_{\\alpha}} = 0.2$. Similarly, Figure 7(e) and Figure 9(e) show that Median, Krum, and GM also undergo slow degradation up to their respective inflection points, after which the performance decreases rapidly under the FoE attack ($\\bar{C_{\\alpha}} = 0.3$ for Median and Krum, and $\\bar{C_{\\alpha}} = 0.2$ for GM).\n\nThese observations suggest that such abrupt performance degradation beyond certain Byzantine ratios is a common vulnerability in existing approaches. In contrast, Fed-NGA maintains a more stable performance trajectory, with test accuracy degrading slowly over a wider range of Byzantine ratios. The onset of sharp degradation is postponed to significantly higher Byzantine ratios, particularly under the Same-value and Sign-flip attacks. Moreover, Figures 7 and 9 show that Fed-NGA outperforms the baseline methods across the evaluated attack scenarios in most cases.\n\n2. **Regarding Weakness 2**\n\nWe acknowledge that the performance of Fed-NGA degrades as $\\beta$ decreases. However, as shown in Table 4 (Page 15), Table 5 (Page 17), and Table 6 (Page 18), the performance of nearly all baselines decreases as $\\beta$ decreases. And the performance fluctuations under different $\\beta$ settings are summarized in the table below (We omit FedAvg from the comparison here, as the algorithm barely converges under attacks.).\n\nTable: Fluctuation of accuracy under different $\\beta$ settings with $\\bar{C_{\\alpha}}=0.2$ over five attack types. - indicates that the algorithm does not converge under this setting.\n|         |          |            |  Table 4  |          |          |          |            |  Table 5  |         |          |          |            |  Table 6  |           |          |\n|:-------:|:--------:|:----------:|:---------:|:--------:|:--------:|:--------:|:----------:|:---------:|:-------:|:--------:|:--------:|:----------:|:---------:|:---------:|:--------:|\n|         | Gaussian | Same-value | Sign-flip |    LIE   |    FOE   | Gaussian | Same-value | Sign-flip |   LIE   |    FOE   | Gaussian | Same-value | Sign-flip |    LIE    |    FOE   |\n| Fed-NGA |   0.62   |    1.91    |  **0.45** |   0.48   | **0.45** |   1.64   |    2.04    |    0.47   |   1.33  | **0.47** |   0.92   |    2.19    |    2.93   |    1.03   | **1.69** |\n|  Median |   1.76   |    8.92    |    2.19   |   1.88   |   2.83   |   0.36   |    3.71    |    1.68   |   0.66  |    0.7   |   8.18   |    1.14    |   10.63   |    6.23   |   8.41   |\n|   Krum  |    1.8   |    9.17    |    2.28   |   1.56   |   7.12   |   0.73   |    1.12    |    2.42   |   2.74  |   0.51   |   4.64   |  **0.29**  |    3.62   |    5.32   |     -    |\n|    GM   |   0.78   |  **0.96**  |    1.05   |   0.39   |     -    |   0.24   |  **0.81**  |  **0.16** |   0.62  |     -    | **0.21** |    1.37    |  **2.47** |   -0.27   |   3.27   |\n|   MCA   | **0.07** |      -     |     -     |   3.09   |     -    | **0.15** |      -     |     -     | **0.3** |     -    |   0.23   |      -     |     -     | **-0.41** |     -    |\n|  CClip  |   0.23   |      -     |     -     | **0.23** |     -    |   3.22   |      -     |     -     |   1.72  |     -    |   2.12   |    0.34    |    7.24   |   -0.21   |   7.28   |\n\nFrom this table, the results indicate that Fed-NGA's (achieved 4 best performance) adaptability to data heterogeneity is comparable to that of GM (achieved 5 best performance) and MCA (achieved 4 best performance), and better than other robust algorithms. Additionally, even in suboptimal scenarios, Fed-NGA performs comparably to its optimal-case performance.\n\nThe above analysis confirms that Fed-NGA exhibits top-tier adaptability to data heterogeneity compared to all baselines, without displaying heightened sensitivity to it."}, {"review_id": "lTS36Bv5SO", "reviewer": "Reviewer_Zgfg", "summary": "This paper addresses the issue of high computational overhead when defending against Byzantine attacks in federated learning. The authors propose a Federated Normalized Gradients Algorithm (Fed-NGA), which achieves a favorable time complexity of O(pM). Extensive experiments are conducted to compare Fed-NGA with several baseline methods under various settings of data heterogeneity and Byzantine attacks.", "questions": "1. In line 194, what does $\\delta$ represent? Is it related to the proportion of Byzantine clients, or how should it be interpreted?", "limitations": "N/A", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The related work and background sections are thorough and well-documented, demonstrating a significant amount of effort.\n2. The experimental section is comprehensive, including extensive comparisons across multiple datasets and attack scenarios.\n\n**Weaknesses**\n1. The algorithmic explanation lacks clarity. Specifically, the motivation behind using normalization is not well justified. Why is normalization effective in improving time complexity for aggregation under Byzantine attacks?\n2. The idealized scenario of achieving a zero optimality gap discussed in Remark 3.10 relies on a very strong assumption. Therefore, it should not be presented as a main contribution of the paper.\n3. As shown in Table 1, some baseline methods are analyzed under different loss function settings (e.g., strongly convex vs. non-convex). Using them in experimental comparisons without discussion may not be appropriate.\n4. Although the authors justify the divergence in learning rates (Line 490) by referring to gradient magnitudes, the overall learning rate schedule remains unclear. It is not well-explained how the learning rates for baseline methods were selected, raising concerns about whether faster convergence is simply due to different learning rates.", "was_revised": true, "final_justification": "Currently, the paper lacks a clear explanation and discussion of normalization techniques. Without such clarification, the use of normalization may appear insufficiently motivated, even if it brings theoretical or empirical gains. Given the significance of this issue,  I believe it warrants further revision and possibly another round of review. At this stage, I do not believe the paper is strong enough to warrant acceptance.", "rebuttal": "1. **Regarding Weakness 1**\n\nWith regard to Weakness 1, the motivation behind normalization stems from its low computational complexity compared to existing robust algorithms, as justified between Line 50 and Line 58 and detailed in Table 1. Specifically, Fed-NGA benefits from reduced aggregation time complexity through normalization: normalizing and aggregating vectors at the central server incurs a complexity of $\\mathcal{O}(pM)$. This is substantially lower than that of other robust aggregation methods, such as $\\mathcal{O}(pM \\log(M))$ for Median and $\\mathcal{O}(pM^2)$ for Krum, as reported in Table 1 on Page 2. Empirical results in Table 3 on Page 8 and Figure 3 on Page 9 further validate the algorithm’s efficiency gains in aggregation speed.\n\n2. **Regarding Weakness 2**\n\nWith regard to Weakness 2, to the best of our knowledge, no existing work has achieved a zero optimality gap, which remains the ultimate goal in convergence analysis, as also noted on Line 75 and Line 799. For the first time, we provide a theoretical condition under which a zero optimality gap can be guaranteed. Moreover, this condition is practically attainable, for example, in scenarios involving full-batch training on IID datasets, or when the inner error and data heterogeneity, as measured by gradient direction, are sufficiently constrained during training, as detailed in Appendix A.\n\nLast but not least, we would like to emphasize that this result is only one of the three theoretical contributions presented in our work, beyond which we also have algorithmic and empirical contributions. As such, this particular theoretical result is not intended to be the primary contribution of the paper.\n\n3. **Regarding Weakness 3**\n\nWith regard to Weakness 3, we would like to clarify that it is common practice in the literature to establish theoretical analysis under either the strongly convex or non-convex setting and then evaluate the proposed aggregation algorithms using standard and widely adopted training models, regardless of the specific assumptions made in the theoretical analysis. This practice is prevalent and generally accepted in our research community.\n\nFor example, CClip [1], whose convergence guarantee is established under the non-convex setting, is empirically compared with RFA, which is only theoretically justified under the strongly convex setting. Conversely, MCA [2], with theoretical support under the strongly convex setting, is experimentally compared with Krum, whose analysis assumes the non-convex setting. Therefore, our evaluation protocol follows the standard experimental practices adopted in this field.\n\n[1] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. \"Learning from history for byzantine robust optimization.\" International conference on machine learning. PMLR, 2021.\n\n[2] Luan, Zhirong, et al. \"Robust federated learning: Maximum correntropy aggregation against Byzantine attacks.\" IEEE Transactions on Neural Networks and Learning Systems 36.1 (2024): 62-75.\n\n4. **Regarding Weakness 4**\n\nWith regard to Weakness 4, we would like to emphasize that the primary advantage and contribution of our work lie in the final test accuracy achieved after convergence under various types and intensities of Byzantine attacks, rather than in the convergence speed.\n\nIn terms of the convergence performance of our Fed-NGA, we would like to clarify that, theoretically, as stated in both the Abstract and the summary of contributions (Line 71), we only specify that Fed-NGA achieves a convergence rate of $\\mathcal{O}(1/T^{1/2-\\delta})$, but we do not present this as an advantage over the baselines in terms of convergence speed. Experimentally, we also observe that sometimes Fed-NGA tends to converge slowly than some baselines.\n\nRegarding the conceptual distinction between convergence speed and final test accuracy, we would like to emphasize that convergence rate is not necessarily indicative of the final accuracy. This phenomenon is illustrated in Figure 6 (Page 14) and Table 4 (Page 15). For instance, when training the LeNet model, Fed-NGA demonstrates slightly faster convergence than most baselines and ultimately achieves superior final accuracy. In contrast, when training the MLP model, Fed-NGA converges marginally slower but still outperforms the baselines in terms of final accuracy.\n\nOn the other hand, as explained in the paper starting from Line 490, we intentionally adopt a favorable learning rate setup for the baselines to improve their convergence speed compared to using our learning rate directly, in the interest of fairness.\nIn summary, we did not tune the learning rate in a biased manner to gain an unfair advantage over the baselines.\n\n5. **Regarding Question 1**\n\nWith regard to Question 1, we explain the definition of $\\delta$ in Line 194 of our paper as “$\\delta$ is an arbitrary value lying between $(0, 1/2)$.” This actually implies the $\\delta$ serves solely as a tunable parameter for setting the learning rate and is not related to the proportion of Byzantine clients or any other physical parameters. Conceptually, $\\delta$ can be viewed as a parameter that influences the convergence rate. Its presence indicates that convergence is guaranteed as long as the learning rate for given $t$ falls within a certain range, rather than requiring a specific fixed value."}]

Author rebuttal:

Meta-review: This paper introduces a simple byzantine resilient aggregation technique that simply normalizes the client gradients before averaging. The reviewers generally agree that the work is technically sound, with convergence analysis, proofs of Byzantine robustness, and  experiments across diverse datasets and attack types. A key strength is the scalability compared to classic methods like Krum.  The empirical results convincingly show both runtime and accuracy advantages compared to established baselines (Median, Krum, GM, MCA, CClip). One reviewer raised concerns about the motivation since normalization is not an inherently novel idea. Another concern (from the meta-reviewer) is the need to tune new HP for this method compared to the base FL method used. Overall, the paper makes a solid contribution to the area of Byzantine-robust FL, with both an empirical evaluation of a simple practical method and providing the associated theoretical basis.
Decision: Accept (poster)