Near Optimal Robust Federated Learning Against Data Poisoning Attack
Authors: Jingfan Yu
Zhixuan Fang
Venue: ICLR 2026 Poster (2026)
Keywords: federated learning
data poisoning attack
Primary area: learning theory
TL;DR: We focus on data poisoning attack in federated learning and propose a mechanism that asymptotically meets the lower bound in both IID setting and non-IID setting.

Abstract: We revisit data poisoning attacks in the federated learning system. There will be $m$ worker nodes (each has $n$ training data samples) cooperatively training one model for a machine-learning task, and a fraction (i.e.,  $\alpha$) of the workers may suffer from the data poisoning attack. We mainly focus on the challenging and practical case where $n$ is small and $m$ is large, such that each worker does not have enough statistical information to identify the poisoned data by itself, while in total they have enough data to learn the task if the poisoned data are detected. Therefore, we propose a mechanism for workers to cooperatively detect workers with poisoned data. In terms of attack loss, our mechanism achieves $\tilde{O}((\frac{1}{n})^{\frac{1}{2}}+(\frac{d}{mn})^{\frac{1}{2}})$ in IID setting and $\tilde{O}((\frac{1}{\gamma})^{\frac{1}{2}}+(\frac{1}{n})^{\frac{1}{2}}+(\frac{d}{mn})^{\frac{1}{2}})$ in non-IID setting, where $d$ is the VC-dimension of the learning model and $\gamma$ is a concentration parameter characterizing the non-IIDness. Alongside attack loss, our mechanism limits the adversary’s free-ride gain even when it cannot be directly quantified by the attack loss. We also propose the lower bound of the attack loss, and our proposed algorithm matches the lower bound when $m\rightarrow \infty$ both in IID setting and non-IID setting.

Published as a conference paper at ICLR 2026
NEAR OPTIMAL ROBUST FEDERATED LEARNING AGAINST DATA POISONING ATTACK
Jingfan Yu Tsinghua University Shanghai Qi Zhi Institute
Zhixuan Fang"
Tsinghua University
Shanghai Qi Zhi Institute z f fang @m 1. t.s ttsiingtt wngiing..eee....... cn
yujf20@ma 1.1 s. t tsinghua. edu on
ABSTRACT
We revisit data poisoning attacks in the federated learning system. Consider m worker nodes (each has n training data samples) cooperatively training one model for machine-leaminng task, and fraction (i.e., oi) of the workers may suffer from the data poisoning attack. We mainly focus on the challenging and practical case where n small and m large, such that each worker does not have enough statistical information to identify the poisoned data by itself, while in total they have enough data to learn the task if the poisoned data are detected. Therefore, we propose mechanism for workers to cooperatively detect workers with poisoned data. In terms of attack loss, setting and Ō(())) à + ()) + ( }² in non-III setting, where d is the VC- dimension of the learning model and y is concentration parameter characterizing the non- lon-II Alongside attack loss, our mechanism limits the adversary's 's free- ride gain even when cannot be directly quantified by the attack loss. We also propose the lower bound of the attack loss, and our proposed algorithm matches the lower bound when m - oc both in IID setting and non-IID setting.
mechanism achieves Ō((2) + (mnn) ) in IID
INTRODUCTION
Federated learning trains a target model across distributed nodes without centralizing data. server dispatches the target model, workers return gradients, and the server aggregates them to update the model. Federated learning inherits the vulnerabilities to poisoming attacks. There are two types of poisoning attacks: model poisoning Chen et al. (2017): Su & Xu (2018); Yin et al. (2018), Blanchard at. (2017) and data poisoning [Sun et al. (2021) ): Kairouz al. (2021) y Tolpegin et al. al, (2020). Model poisoning attack refers to the attack where malicious workers modify the gradient sent to the server. These malicious workers are completely untrustworthy.
While model poisoning attack attracts much attention in the literature, there is rising concern about a weaker yet more practical version of the poisoning attack, the data poisoning attack. Data poisoning attack refers attack where adversary modifies the dataset of corrupted workers, as in Figure T The corrupted workers are honest, but their raw data is unknowingly corrupted by the adversary. Thus, compared to the model poisoning attack, the gradient of workers reflects their dataset, even when the dataset is contaminated. For example, data poisoning allows a non-expert attacker to implement the classic and effective attack of label flipping without knowing the target model type or controlling the workers.
Yet little attention has been paid to data poisoning. Literature usually adopts the gradient robust aggregation method as the primary means of countering adversarial attacks Kairouz et al. (202I). The gradient robust aggregation method, originally designed counter the model poisoning attack, also mitigates the data poisoning attack. However, since the data poisoning attack is weaker attack, more efficient defenses for the data poisoning attack should exist.
Our research question is how well we can defend against arbitrary data poisoning in the worst case. The defense is characterized by two objectives: maximizing the target model accuracy of the unpoi- soned data and mitigating the adversary's gain from the attack. The two objectives are not equivalent
"Corresponding author.

---

Published as a conference paper at ICLR 2026
because there exists the so-called Trojan attack: The adversary can make the trained target model succeed in both meeting the attacker's 's goal and achieving high accuracy among the unpoisoned data.
Our solution in this paper addresses this question in the following ways.
(a) We establish the minimax lower bound of the target model attack loss due to the poisoning attack. Following the previous literature Yin et al. (2018); Blanchard et al.] (007)) we focus on the case where more than half of the datasets are unpoisoned. The detection difficulty increases as the unpoisoned datasets' correlation decreases. Therefore, we develop quantitative relation between the attack loss lower bound and the correlation. More specifically, in terms of how the workers' data are sampled, we consider the ITD setting and the non-lll) setting. In the IID setting, each worker samples n data samples independently from the same distribution. In the non-IID setting, the Dirichlet distribution with concentration parameter y is used to characterize the non-III extent Hsu et al. (2019). We show that the lower bound of attack loss is 52( ( in IID setting and in non-III setting. The parameters n and characterize the dataset similarity. More details will be in Section 3
vn
2 vn
(b) We propose an algorithm to asymptotically match the lower bound. The challenge is how to discriminate between poisoned and unpoisoned datasets. Little literature works on data poisoning, researchers believe that the robust gradient aggregation defense against model poisoning attack can also address data poisoning attack ining the gradients that the workers compute on the target model and removing outliers as poisoned ones. However, direct application of this method to the scenario of the data poisoning attack will introduce two limitations. First, the server needs to distinguish the malicious gradient every time it collects gradients, inducing continuous computational overhead. Second, the gradient may not faithfully reflect whether the corresponding dataset is poisoned. The gradient is a nigh-dimensional vector, and outlier detection more difficult with nigher-dimensional vectors. Figure [[b-)) shows the two principal axes of gradients calculated by the unpoisoned datasets and a poisoned dataset, where the attack is the label-flipping attack. The gradients in the two figures are calculated from the same datasets, while the target model size is different. When the model is larger (Figure [c)), the gradient dimension is larger and the poisoned one is harder to detect. In addition, in the data poisoning attack, the gradient is generated according to the poisoned data instead of being arbitrarily generated. Such patterns of poisoned gradients are not utilized in robust gradient aggregation.
al. (2021) Robust gradient aggregation relies on exam-
To solve this challenge, train discriminator model to directly differentiate among the workers' datasets instead of differentiating the gradients. To train the discriminator model, we propose a vari- notion that characterizes the variances of the datasets the training loss function. Our variance notion is also aligned with the definition of H-divergence, which describes the distance between the datasets. To train the discriminator model, workers send gradients and model outputs the server so that the server does not need direct access to the datasets. In our algorithm, the discriminator model is trained before starting the training of the target model. Compared with the gradient robust aggregation method, our algorithm is more effective and tailored to the data poisoning attack sce- nario by exploiting the feature that the gradient of each worker faithfully reflects its dataset (whether the dataset is poisoned or not).
Our algorithm achieve Ō((H)) - mn }&) ( attack loss in IID setting and Ō(( + (+) + (mi
in non-lID setting, where is the number of workers and d is VC-dimension of the learning task. Previous literature achieves the attack loss of O(( (race(Ez))
Feng et al. (2014); Yin al. dz ) } )u & Xu (2018) in IID setting, where Eg is the covariance matrix
) + mm
de
n
2018)) and O(( [Eaalla) ) + man of gradients and &, is the dimension of the gradients. Since trace(E, ) and ||E 12 increases with the size of models Karakida et al. (202T), our algorithm achieves a better bound. When - cc, the upper bound produced by our algorithm matches the lower bound.
(c) We propose notion that characterizes the adversary's gain from the attack. We show that our algorithm mitigates the adversary's gain both theoretically and experimentally. To mitigate the attacker's gain from free ride or Trojan attacks, we propose robustness metric, effective poison rate (EPR), for data poisoning attacks in federated learning systems, alongside the attack loss. EPR of a specific algorithm reflects the fraction of data that is effectively poisoned. For example, EPR of indicates that the training outcome is the same as a locally trained model with proportion of the data being poisoned. If an algorithm achieves e < a, where a is the proportion of workers that
2

---

Published as a conference paper at ICLR 2026
the adversary can corrupt, the attack influence is sub cub--rooortional and thus reduced. Our proposed mechanism achieves EPR bound of )({))* + )x)))))))))))))))) in IID setting and O((2)) + ( +
)å) in non-llD setting, demonstrating that, with sufficient samples, the adversary's impact can be effectively constrained.
Our theoretical contribution focuses the region where the ratio of poisoned datasets considers the optimization of model parameters as a black box, and assumes that we can get an optimized parameter from the black box. In our experiment, we use stochastic gradients to optimize the parameters and show that the optimization can be done with reasonable computation costs.
a
Server
500
noraa
normal
poisomed
poisenod
principle aixs
0.3
250
Worker
Worker
Worker
Worker
0.0
Prisoral
Pelumted Sats
Ueprriemnt
Ixprrserna
dess
0.3
-200
Adversary
-06
-500
-0.6
-033
0.6
-250
250 500
(a)
(b)
principle aixs x
principle aixs x
Figure 1: (a) Data poisoning attack in a federated learning system. (b-c) Two principal axes of gra- dients calculated by the same datasets different neural networks. (b) The gradients are computed from a dense neural network (DNN) with 2 hidden layers and 128 neurons each hidden layer. (c) The gradients are computed from DNN with 32 hidden layers and 128 neurons each hidden layer.
PROBLEM FORMULATION AND GOALS
Participant. We consider the federated learning setting with one parameter server and m workers. Each worker i has n data points as his local dataset W..
Data space. Let Z wish to label and y = 1-1, is the label set. The binary-label setting can be generalized to the multi-label setting by combining the original object and the label into single composite object, then assigning a binary label that indicates whether the label is the original label Mirza & Osindero (014). Therefore, we focus on the binary-label setting in the theoretical part.
X' x y be the data space, where X' is the set of objects that we may
Attack model. An adversary AA can corrupt the dataset a fraction of workers and arbitrarily poison these datasets. Let S, C [m]] be the set of workers with poisoned data and S, = [m]] \ Sp be the set of normal workers. Therefore, SSpl = am and S..| = (1 - a)mm. The adversary A completely decides the dataset of workers in Sp. while it can not control subsequent actions of the workers. Also, the adversary cannot manipulate the datasets of normal workers.
Normal worker dataset. In terms of the distribution of local datasets of normal workers, we con- sider an IID setting and non-lID setting. Let P(Z) and P(zz) be the set of distributions over data points and n-sample datasets. In general, the dataset of each normal worker is sampled from a distribution P E P(Z"). For the IID setting, each data point of the normal worker is sampled independently from an unknown ground truth distribution D E P(Z). This means that the dataset of each normal worker is sampled from a distribution Den E P(2²). For the non-IID setting, Dirichlet distribution is used to characterize the con-identicalness detailed in Section 3.2
Learning model To carry out learning tasks, consider set of parameterized learning models {ge Jace. where θ is the parameter space and each ge is a function from X' to IR. The set of learning models can induce hypothesis class 76 = {sign go 8 E ²). Each hypothesis is map from X to y. Here, each hypothesis is a composition of a sign function and the learning model function. Let denote the VC-dimension of 7 Shwarev-Swwrtz & Ben-Davie (014).
Let M be a federated learning mechanism. Mechanism M takes m datasets as input and outputs a hypothesis, denoted as M M(W.) h.
3

---

Published as a conference paper at ICLR 2026
To measure the success of the trained target model, the error of the output hypothesis over the ground truth distribution D E P(2). For each E H. the error defined as follows:
(D(h) P ((.,))/(h(a)) # yl
2.1
ATTACK LOSS
For mechanism M that outputs h under attack, we define the attack loss to be:
RD(h) = ED(h) min
<D(h')
(2)
#'EH
The attack loss characterizes the increment of the target-model error incurred under attack relative to the attack-free case.
2.2 EFFECTIVE POISON RATE (EPR)
In addition to the attack loss, we also have robustness goal aimed at limiting the effectiveness of the adversary A. We define a metric EPR Definition 2.2 that characterizes the effectiveness based on the concept of H--iiergeence in Definition 2.1
H--iivergence "Ben-David et al. (2010) is modified from the total variation distance of two distribu- tions to measure the difference related to the hypothesis class H. The definition of H-diiergence is as follows:
Definition 2.1 (H--ivergence). The H-divergence between the two distributions D and D' for label y is
dx (', sup REH
Σ ay (P(z,))=(((()) 1, s'1 ((..)) [h(x)= 1, v/l) V'EY
(3)
where IP represents the probability, (x, y) D denotes (z, y) sampled from distribution D, a {ag' byey is 2-dimension probability vector, and A is the corresponding probability simplex.
The intuition is that since hypothesis divides the input space X' into subsets, either being M(x) = or 0, H-divergence dæ specifies the best hypothesis that can be used to differentiate the samples with label y' generated from two distribution D and D', When H-divergence means no hypothesis can differentiate the two distributions.
We now define EPR that characterizes the effectiveness of adversary A.
Definition 2.2 (EPR). A federated learning mechanism M is c-EPR against an adversary that con- trols (We if there exists dataset D) that satisfies the followings:
Dataset D close to the normal workers' dataset, with a distance at most e in terms of H divverggeec:: du (Vies, W,, D)
2. The output of M is the same in two cases: (a) the data set of each worker is W,, (b) the data set of each worker all D. Write as VS C H. PlM((We))e(mm) E S] PPMM(DD)stmm) E ST.
We slightly abuse the notion that for dataset D, x ~ D denote r is uniformly sampled from D.
Roughly speaking, for mechanism with c-EPR, we guarantee that the result of the training equiv- alent to training a model on dataset where no more than proportion of total data is poisoned. direct learning mechanism on datasets ] such as FedAvg McMahan al. (2017): Chen et al. (017), can be c-EPR. This is because we can let D Use[m)] W. and fraction of the dataset "D can be arbitrarily different from those in Uies, W,, Thus, a mechanism c a, the attack influ- show in experiments that c-EPR leads
ence is sub-proportions and thus reduced. In Section 6 to low accuracy in the poisoned datasets.
LOWER BOUND OF MINIMAX ATTACK LOSS
In this section, calculate the lower bound of minimax attack loss in both IID and non-III settings.
4

---

Published as a conference paper at ICLR 2026
3.1 LOWER BOUND IID SETTING
To show the lower bound on the attack loss that the learned model can achieve, we consider that the server can directly observe the dataset of each worker. Formally, consider the estima- tion problem: Nature chooses a ground truth distribution D. For each normal worker i, nature generates n IID data samples from D. W; D For each poisoned worker i, an adver- sary generates n samples W; from distribution Q E P(Z"). Upon observing [W) [em)) the server estimates a hypothesis h((W:) The estimator can be deterministic or randomized. Let Mixla, P,Q) (1 P + aQ be the mixture distribution. When - xc, we can consider (WiJ= Mix(a, D Q) 8m Then, the minimax attack loss can be written as:
min max max B
(4)
D Q
Theorem 3.1 (Lower bound in IID setting). In the IID setting, the lower bound of the minimax attack loss is 21-aa/a
Therefore, the lower bound for the sample complexity is nH (c,
4(1 41-a)²
a²
To prove Theorem 3.1 construct two situations that the server cannot distinguish from each other. The ground truth distributions of the two situations are different and any hypothesis leads to at least 2 attack loss for either of the two situations. The proof will be in Appendix C.I
3.2 LOWER BOUND IN NON-IID SETTING
Then, we consider the lower bound non-IID setting. We consider commonly adopted non-III model in federated learning: Dirichlet distribution Hsu et al. (2019). Let Di...., D, be J data distributions and consider a J-dimension vector p with |p|| = and a concentration parameter 7.
The dataset of each worker is sampled as follows: (1) Sample J-dimension vector q from the Dirichlet distribution Dir(1p). (2) Sample n data samples from mixture probability distribution Mix'(q) = Σj=1 Dz. We can see that for each worker i, his dataset W; C 2h is sampled from compound probability distribution that 9: Dir(1p) and W; (: ~ Mix Mix'(q,) (0, We use (2") c P(z") to denote the set of such compound probability distributions.
For each concentration parameter 7, we consider the following estimation problem:
Nature chooses a distribution C from (2").. Let C be the compound probability distribution and W ~ C' refers to q Dir(1p) and Wlq Miz' (q) Then, the ground truth distribution induced by Cgt = Mix' (p) Σ Pj Dj. For each normal worker i, nature samples a dataset W; from C. For each poisoned worker i, an adversary generates the n-sample dataset W, from distribution Q P. Upon observing (W;) the server estimates hypothesis (m Then, the minimax attack loss can be written
son
min max max E ((w.)y, CEC,
RC,, (f((W))
(5)
Theorem 3.2 (Lower bound in non-IID setting). In the non-IID setting, the lower bound of the & where 8 = max, S1 U S2.
minimax attack loss is 27.
( B
a² 2(1 - a) J: S2 = 5)-{8l0=
7a
S
21
(6)
B
2-
7
Vn(1 -
?
where B(,,) is the Beta function. For large and n, the lower bound of the minimax attack loss is O
vn
The proof will be in Appendix C.2 the scale of 1. of normal workers. Therefore, it is harder for the server to distinguish the poisoned workers from the normal workers.
Compared with the IID setting, there an additional attack loss v.. This is because in the non-IID setting, there is less correlation among the datasets
5

---

Published as a conference paper at ICLR 2026
4 ALGORITHM
Algorithm Overview. Our algorithm is divided into two phases (shown in Algorithm D. i.e, the trustworthiness weight update phase and the target model training phase. The first phase returns weight on workers that represents the trustworthiness of each worker from the server's ' view. The weight {w,), 1= I is m-dimensional vector whose elements sum to 1. In the trust- worthiness weight update phase, we train a discriminator model and assign a proper weight to each worker. This is the unique and crucial phase of method. The second phase trains the target model leveraging the weight w.
Let Dw denote the mixture distribution, where the mixing weight w, and the mixing component is worker datasets. The weight updating phase aims to obtain a weight w that minimizes H-diivegencce between Dw and the unknown ground-truth distribution D. Then, in the target model training phase, the server trains the target model from the distribution Dw by minimizing the weighted error of the workers, as in Algorithm where (0) P (a..))>,, ssign e (x f yl is the local error function of io
Algorithm 1: Robust Federated Learning
// Weight update phase: assign a weight for each worker Let w + WeightUpdateeaj)
// Training phase: minimize the weighted error 8" < arg minsee E (,E;
return sign 90-;
Trustworthiness weight update phase. In this phase, we train discriminator model to differ- entiate the workers' datasets. The discriminator model is an auxiliary model, different from the target model. The server assigns a proper trustworthiness weight to each worker according to the discriminator model. To train the discriminator model, we first propose the following definition that characterizes the 'variance' of datasets. The following definition can be seen variance notion induced by the H-divergennc distance notion.
Definition 4.1 (Variance of datasets). The variance of m datasets (W.) in terms of a weight vector w, a model parameter 0 and a label is
m
Varo,a ((WV)a m
w)
R)(0,a) Σ Wi Σ 1=1
wr 13F)(0,a)
(7)
a)) Σ By (ar 1/' sign(.go (x)) = 1]
(8)
W'EY
Then, the weighted variance of (Wi) )m in terms of hypothesis class H (sign go O) is: 1m Varn (ern((1)) ((W) 1e w) == max Varo,a([W.) aE0
(9)
The value ((ea))W; [y v', (i))(go(x)) 1] represents the proportion of input data that originally have a label of y and are labeled as 1 by the model with parameter 0. Thus, V Vare,a ((W: w) characterizes the variance of worker datasets in the lens of model parameter 6. When the weight is uniform, use Varn ((W,
denote the uniformly weighted variance.
We show in Lemma 3 (IID setting) and Lemma (non-IID setting) that the variance over the datasets effectively characterizes the correlation of the datasets. The variance will be small when the datasets are correlated. For the extreme case, if the datasets workers are duplicated, the variance will be O.
Since the variance will be small when the datasets correlated, the variance of the normal workers' dataset is small. Therefore, to bound H-divergence between the weighted distribution Dw and the unknown ground-truth distribution D, the weight should satisfy: (a) the weighted variance V Varx( (m w) is small; (b) the weight should be as dispersed as possible among the (1 a)m normal workers. Formally, the weight vector should be in this set:
Ca..A {w E Vm, Vary ((WH((W))) w) S 1).
(10)

---

Published as a conference paper at ICLR 2026
m
Vm,B8, =
(101 (101.... Wm)
we =
Σ wy E, and S wi
Vi
(11)
3m
SESn
where <B gives the upper bound of each weight value.
We will prove in that Lemma that if w E Cg.g,t, H-divergence between Dw and the unknown ground-truth distribution D can bounded according t and 8.
We propose how to find vector in Cg.g. in Algorithm 2 In Algorithm 2 we first initialize a set S to be all workers and let be uniform weight in the S. We also initialize vector R to be all zeros. Each element in s refers to score indicating how likely worker is poisoned. learn hypothesis that maximizes the variance of workers' datasets (L. Since the variance of normal workers is bounded, the large variance will be mostly contributed by poisoned workers. Therefore, we increase the score 8; for those workers with larger deviation from the mean (Lines 5 8) Then, we remove the worker from set S if his score is larger than threshold (Line
Then, we optimize the parameter
We repeat the above steps until |S| is smaller than (1 20x).
Algorithm 2: WeightUpdate
Function Wei ght.ghhttttteteeee (a) laziiin
//
S [m]. w + { ........
1 in 1. s 00....,00:
for r = 1,2, do
Let 0, a < arg m E (F(().)) - -E Fy (0,
For PerieS E.S. + (F(0,a) a) Ej wjFFy Fj a)
Traa f- max,es Túi
For i E 5, 84 8; Tmux
If 17, then remove from S;
[|] <1 2amm then
return w: end else
11
Update the weight w such that w; + [S]
for i E and w; + 0 otherwise;
end
end
We prove in Lemma C.5 that our weight update phase can find weight in Ca.e. and prove Theo- rem 5.1 (IID setting) and Theorem A. (non-IID setting) that our algorithm asymptotically matches the lower bound in both IID and non-IlD settings.
To realize the maximization step in the distributed setting, first replace the sign function by the sigmoid function. Then, can be implemented by generalized FedAVG, where the workers send the gradients and the model output to the server, described in Appendix The pseudo-code of the variance maximization process is in Algorithm 4 in Section D.I
Target model training phase. In the training phase, the system trains the target model minimize the weighted error. The phase can be implemented directly by FedAVG. The server collects the gra- dients from workers and sums them with w the weight, where obtained in the trustworthiness weight update phase.
5 ANALYSIS
We first analyze our algorithm in the IID setting in this section. show that our algorithm achieves cEER, where e = Ō(()) + (.) In addition, the error the learning task can also bounded by O(()) + d )3). We state the EPR and the attack loss bound in Theorem 5.1 Theorem 5.1 is
proved in Appendix, where we break down the proof into Lemma 6
7

---

Published as a conference paper at ICLR 2026
Theorem 5.1 (Main result in IID setting). When S 3. 1 d. there exists a constant C' and
4-9a C
C". Then, with probability Algoritim satisfies:
3a 3-3
30x
ClV
dln (mn/d) /d) +In (1/8)
-EPP
The attack loss of our algorithm is C(VA dln (ma//d +n (1/8)
For the non-IlI setting, we show that our algorithm achieves an attack loss roughly V that in the IID setting in Appendix A
more than
EXPERIMENT
1.0
Bttaak accurncy 1
C aattack accuracy
accuracy
knun fituring geo median this work
029
0.4
000
data number
poison ratio B
poison ratio 3
14
test accurncy
test accuracy
test accurncy
axc ass- an
40
65 23
round
data number n
poison ratio $
poison ratio
Experimental results. (b-e) are conducted in IID setting. (f.g) are conducted in non- non-IID setting. Figures in the top row (b,d,f) show the attack accuracy. Figures in the bottom row (c.e.g) show the test accuracy. We adopt standard error as the error bar.
Figure 2:
We evaluate robust federated learning mechanisms in MNIST and CIFAR-I0 datasets with the flip- label attack and backdoor attack. In this section, we focus on the result of defending the flip-label attack in MNIST dataset. More details and experiments
provided in Appendix
Training process of the discriminator model. We first show an example of the discriminator model training process show that our discriminator model is effective in differentiating the unpoisoned datasets and poisoned datasets with large number of workers. In Figure(a), we consider 2000 normal workers and 500 workers with poisoned datasets. Each normal worker dataset consists of 30 IID data samples. Each poisoned dataset consists of 30 label-flipped data samples. We see from Figure(a) that the discriminator model maximizes the dataset variance, the unpoisoned datasets and poisoned datasets are differentiated.
6.1 COMPARING WITH BASELINES
Baselines. We consider the commonly adopted and theoretically guaranteed poisoning attack de- fenses: geometric median method BBlanchard et al. (2017): Chen et al.] (2017). iterative filtering method Su Xu (2018), and Krum function method Shejwalkar et al. (2022). We set the learning rate and the epoch number of the baselines and our training phase to be the same, where the learning rate Ç = 0.01 and the training epoch is 20. The server selects 20% of workers at each round.
Metric. To characterize the attack loss, MNIST test dataset. The larger the test accuracy, the smaller the attack loss will be. To characterize the adversary's gain, denoted as attack accuracy. Here, the poisoned data samples are the flipped label data samples that the adversary put in the corrupted workers' datasets.
the accuracy of the trained target model the
the accuracy of the trained target model the poisoned data samples,
Result We consider 200 normal workers, 50 workers with poisoned data, and = in Algorithm 2 Line 8 Figure (b.c) demonstrates how the effectiveness of the defenses varies with the number of
8

---

Published as a conference paper at ICLR 2026
IID data samples n each worker has. With larger n, the datasets of normal workers converge. Thus, it will be easier to defend against the adversary. Our algorithm maintains higher test accuracy and lower attack accuracy than the baselines, especially when n is small.
In Figure dg). the adversary camoufaages the poisoned data samples with the normal workers' data samples. We use the poison rate B to denote the ratio of poisoned data in each dataset. We consider 30 samples for each worker. In Figureed.ss d,e), we consider the IID setting. In Figure fg.g) consider the non-IlD setting. The normal workers' data are non-IlD over the different labels Hsu itt al. (211)). and the concentration parameter is 1.0. Our algorithm maintains higher test accuracy and lower attack accuracy than the baselines both IID and non-IID settings.
In addition, our algorithm is more efficient compared to the baselines. The commutation complexity of both phases in our algorithm is the same as that of FedAVG. In comparison,in the baseline algo- rithms, the server conducts complicated gradient aggregation operations. When m is large, this will be the primary cause of the algorithm's is slowdown.
RELATED WORK
Robust gradient aggregation: Robust gradient aggregation is initially a defense the model poisoning attack is gradient robust aggregation [hen et al. (2017); [S & Xu] (2018); Yin et al. (2018); [Blanchard et al. 2017). The method can applied to defend against the data poison- ing attack. However, these algorithms are not effective enough because their performance depends on the variance of gradients calculated by the workers, which are vectors with high dimensions and grow the models become larger. In federated learning with robust gradient aggregation, the server uses robust mean aggregation to aggregate those gradients, instead of averaging the gradi- ents collected from the workers as in FedAVG McMahan et al. (2017). Different robust aggregation techniques provide bounds of the resulting model's attack loss based on different norms of the co- variance matrix of gradients Eg and the number of model parameters (dimension of gradients) dg- For example, if dimension-wise median Yin et al. (2018), or geometric median Feng et al. (2014); Chen al. (207)) are used as the robust aggregation technique, the attack loss can be bounded by O(( (roce(2
Feng et al. (2014); Yin et al. (018)). For iterative filtering Su & Xu (2018); Steinhardt et al. (017)) Diakonikolas al. (2019) method, the attack loss can be bounded de Su & Xu 2018), where |E is 7.2-norm of the covariance matrix. For man
by O(( -2 [2012
Krum function Blanchard et (2077) the number of samples should be comparable with the number of model parameters d, for their theoretical bound. With the increasing number of parame- ters of the model, the above attack loss bounds expand, even when goes to infinity. For the trace of the covariance matrix, it explicitly depends on the dimension of the gradients. For the L2-norm of the covariance matrix, it can also go infinity as the width of the neuron network model goes to infinity Karakida et al. (202T)
Data poisoning attack in federated learning: Tolpegin et al. Tolpegin et al. (020)) adopt principal component analysis (PCA) to detect the outlier gradients as their defense against the data poisoning attack. PCA over gradients is also
of the robust gradient aggregation methods. Kairouz
al. Kairouz et al. 1021) and Han et al. Han et al. (2024) consider both data poisoning attack and model poisoning attack. They also adopt robust gradient aggregation methods their defenses against the data poisoning attack.
Naseri al. Naseri et al. (2200) explore the similarity between protecting privacy and robustness. Random perturbation is more effective when the number of poisoned data smaller. Since our EPR property limits the number of poisoned data, random perturbation and our mechanism can complement each other.
Random perturbation:
8 CONCLUSION
We propose mechanism that asymptotically achieves the lower bound of attack loss in both IID setting and non-IID setting, when a < J. addition, we propose metric EPR for data poisoning attacks in the federated learning system to characterize the effectiveness of the adversary. Our mechanism also achieves low EPR.

---

Published as a conference paper at ICLR 2026
9 ACKNOWLEDGEMENT
This work supported by Tsinghua University Dushi Program and Shanghai Qi Zhi Institute Inno- vation Program.
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference Computer and Communications Security, CCS 16, pp. 308-318, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341394, doi: //t:::///oooooo 011144//297744.29778811 / org/ 11..:...11112997741111 2977833
Eugene Bagdasaryan and Vitaly Shmatikov. Blind backdoors in deep learning models. In 30th USENIX Security Symposium (USENIX Security 21), pp. 1505-1521, 2021.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 19:151-175,
2010.
Peva Blanchard, El Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017.
Jack Brimberg. Further notes on convergence of the weiszfeld algorithm. Yugoslav Journal of
Operations Research, 13(2), 2016.
Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance matrix estimation via matrix depth. arXiv preprint (rXXi:1506.006)) 2015.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial set- tings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-25, 2017.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742 864, 2019.
Jiashi Feng. Huan Xu, and Shic Mannor. Distributed robust learning. arXiv preprint MXXv:1409.5937 2014.
Ehsan Hallaji, Roozbeh Razavi-Far, Mehrdad Saif, and Enrique Herrera- Herrera-Viedma. Viedma. Label noise analysis meets adversarial training: A defense against label poisoning in federated learning.
Knowledge-Batd Systems, 206:110384, 2023. ISSN 0950-7051. doi: http:://bo..rr//10.116///
knosys.2023. 110384, uRL/ttps: www. www.::/ssieneecccicc..ommmm com/ ccm./acienc//artiel. p21/509507051230000
Shanshan Han, Baturalp Buyukates, Zijian Hu, Han Jin, Weizhao Jin, Lichao Sun, Xiaoyang Wang. Wenxuan Wu, Chulin Xie, Yuhang Yao, Kai Zhang, Qifan Zhang, Yuhui Zhang. Carlee Joe-Wong, Salman Avestimehr, and Chaoyang Hc. Fedsecurity: A benchmark for attacks and defenses in federated learning and federated llms. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '24, pp. 5070-5081, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400704901.
doi: 10. 10.1 00.114533335528.3671555
URL / /tt:://ooi..m http:///oooooogo.../
1tt.:/oogg0....11/333111 110.0..1115333333 728. 3671545
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data
distribution for federated visual classification. arXiv preprint arXiv: /900://:9000333333 2019.
Najeeb Moharram Jebreel, Josep Domingo-Ferrer, David Sánchez, and Alberto Blanco-Justicia. Lfighter: Defending against the flbel-fiipping attack in federated learning. Neural Ner-
works, 170:1 2024. ISSN 0893-6080. doi: https://bb..or//10000.....eee
2023.11.019, URL /tt.tt/::///..seeeeeeeoe http::::www..ceeneeerree.....oor htt.://wwweccacceeeccccccceeeaaa
2083360002200444
10

---

Published as a conference paper at ICLR 2026
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and trends@ in machine learning,
14(1-2):1-210, 2021.
Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. Pathological spectra of the fisher information metric and its variants in deep neural networks, Neural Computation. (3(8):2274-23077 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robuss learning on heterogeneous datasets via bucketing. In International Conference Learning Representations, 2022. URL
htttps://ppenrevlew.. net/ www.:/nne/ffrmmiccocoooooo forum?id= E jXKKDEi
Tao Lin, Lingjing Kong, Sebastian Stich, and Martin Jaggi. Ensemble distillation for robust model
fusion in federated learning. Advances in Neural Information Processing Systems, 33:2351-2366 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effice learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp.
PMLR, 2017.
Mchdi Mirza and Simon Osindero. Conditional generative adversarial nets, 2014. URL https:
Mohammad Naseri, Jamie Hayes, and Emiliano De Cristofaro. Local and central differential privacy for robustness and privacy in federated learning. arXiv preprint arXiv:2009.03561 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Virat Shejwalkar, Amir Houmansadr, Peter Kairouz, and Daniel Ramage, Back to the drawing board: A critical evaluation poisoning attacks on production federated learning. 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022, pp. 1354 1371. IEEE, 2022. doi: 10. 109900942214.000000 923322779787777 URL https: /to.dooooo//ooooooooooooo 10. 1109 SP 4. 2022. 9833647
Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. arXiv preprint arXiv:1703.0494. 2017.
Lili Su and Jiaming Xu. Securing distributed machine learning in high dimensions. arXiv preprint 1rXiv: 10140, pp. 1536-1233, 2018.
Gan Sun, Yang Cong, Jiahua Dong, Qiang Wang, Lingjuan Lyu, and Ji Liu. Data poisoning attacks federated machine learning. IEEE Internet Things Journal, 9(13):11365 11375, 2021.
Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against federated learning systems. In Computer SSORris 2020: 25th European symposium on research in computer security, ESORICs 2020, guildford, UK, September 14-18. 2020, proceed- ings, part 25, pp. 480-501. Springer, 2020.
Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan I Luo, Jinfeng Yi, and James Bailey. Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 322-330, 2019.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robus distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
11

---

Published as a conference paper at ICLR 2026
A ANALYSIS IN NON-IID SETTING
In the non-IlD setting, the main difference is that the dataset variance of the normal worker is 2(7+1) larger than that in the IID IID-setting Therefore, the EPR and attack loss are follows:
1
Theorem A.1 (Main result in non-lID setting). Let the dataset of each normal worker be sampled from a distribution C & (2"). When a S 3
d
+ m there exists a constant C' and
C C=
I-30 C 90 + val2-3a) CC', E= C(y C
)C'
d (mm /d) +Iu (1/6)
(1/6)
1-2a
7711
2m
Then, with probability Algorithm satisfies:
E-EPR
The attack loss of our algorithm is also
can see the upper bound asymptotically matches the lower bound when m - 0c.
B DETAIL OF FEDAVG
FedAVG McMahan al. 2017); Chen et al. (2017) is basic federated learning mechanism in which the worker calculates the gradient of his local dataset and the server collects the gradients and updates the model with the weighted average of the gradients. The mechanism is described in Algorithm 3
where Sr is the learning rate of round r.
Algorithm 3: FedAVG
Worker é:
If selected in S at round compute gradi,r + VF:(B,);
Send grad,,- to server;
Server:
for = 1,2,... do
S f- (random set of s workers by weight w);
Receive grad,, from worker E S;
0r+1 + 0, Sr Eies gra
end
C PROOFS
C.1 PROOF OF THEOREM 3.1
Proof. Let Dh, A, +)+) be data distribution that P((x, v)) [ +)()))++A) Let D(h, be data distribution that P((2,,)) v)) (े h(x)))))))))))())) +
Let H2(PQQ) = EEQ (1 (1- 5 27 be the squared Hellinger distance. Then,
H² (D(h, +), -)) = 4A2
(12)
and
112 (D(h, A, +) D(,, -)-
=2 1 1 H2 (D(h, D(,,,
(13)
=2 2(1 - 4/2
<4nA²
12

---

Published as a conference paper at ICLR 2026
The total variant distance between D(h, A, + 8m and D(h, A, -) be bound as:
drv((((h,A,t) ((,, A. -))n)
(14)
<H(D(),A,,) 6m (h,, A, A, -)0m) 2VTTA
Let A 2(1 2(1-a)/a' Then,
drv "..,,,.))"n.D(AAA-))))))))) cc((1-0
(15)
By Lemma there exists distributions Q+ and Q- that (1 - a) A, +) + aQ+ a) Dh,, A, @n + aQ- Thus, for any hypothesis, the server will estimate the hypothesis h the same probability whether the data sets sampled from (1 D(,, A +)80 aQ or (1 (1-a) ((, - +QQ_.
For any h,
ED(h,.,)(h)) ED(H,A)-)(h))
-((es)-D(hA,tthh + y] + P(..))-( Hv
(16)
Therefore, RD(,A,,)))) (h) + (D) - 2* ( A) = 22
Thus,
min max max E (ww. RD (Btp
Q
(BD( RD(h.,,-)())
(17)
a)
Lemma (Chen et al. 2015)). Consider two distributions Pı and P/2 such that drv (PI. S +
Then, there exists distributions Q1 and Q2 that (1 c') P: + dQ = (1 - c) Pg + dQ2-
C.2 PROOF OF THEOREM 3.2
Proof. Consider concentration parameter y and a Dirichlet distribution Dir(m, 72). where + 2-6
72 7. Let d 72 71. Then, 2 72 2 Let f (: 72, 72) be the corresponding 1+h(z)ey
2+-6
probability density function. Let D(h, +) be a data distribution that P((x,v) y)) = [
Let D(h, -) be data distribution that P((x,, v)) 1 (1-h())=))
Let S1, S2 C,(2") be two distributions of workers' datasets defined in Section 3.2
For S₁, the parameters are = (2,, ?,), D1 = D(h, -), and D3 = D(h, +). Let D denote the corresponding ground-truth distribution. Let fi (:: q) be the probability density function of the n-fold mixture distribution (q: D(h -) + Q2 D(h, +))
For Sz, the parameters denote the corresponding ground-truth distribution. Let f=(:: q) be the probability density function of the n-fold mixture distribution D(,, +) + q2 D(h -))
== ( (,. D1 D(h, +), and D2 D(h -). Let Dgt.2
Then,
13

---

Published as a conference paper at ICLR 2026
dTv(S),8)) = / |s| -2
/1S1-
1 //a11=11 1(W: - -
=
-S
M f: - 72)
(18)
<
11q1:=11
B( 222222 214022
$/2 2
B(7,, 71)
The last inequality follows from the below Lemma 2 In addition,
dIv(Si, = / |s| S2l
1 =/YEE
f1(W: (( - //q (o
JWEE
1911==1
$
SWEE
(f((W: -
(19)
||1|1=1
=
-JWEEN 1|9l/==1
(f((W:g) - fi(W; - q)1 fni Y,
<
2/
1
f1) (1:71722) vn( 72 71
||l1l==1
2
?
Let set S1 = {6
B)3.3)
$
2(1 2(1003= }, S2 = 1
8
vm(1-a) }. and 5 = max S1 U S2-
aa
BC
7-5 8
2
Then,
min max max max Bax Wwgg Rc, (h((W)) h CEC,12") Q
1
RD (h) (h))
(20)
2
8
2-
To estimate the asymptotic behavior, we can approximate gamma functions by Stirling's approxi- mation. Let w
8
B(3
B 7 1-W/ 748/T
2
W
7- WVT
(7 1) In
In
2
2
2
7: + W
7 W. 7
+0
2
2
7 - w /
In(1
2
7
-w/Fln(1 + w. / ) + O (7-
w
2 +t1
14

---

Published as a conference paper at ICLR 2026
Therefore,
min max max B Mi Re, (h((W) h (EC, Q
2 max S1 US2
(21)
2 max{ V/
log(1 2(1 a)²
+ +0(r)))
a
2y
2(1 a)
-
vn
Bi _ ححمدد
Lemma 2. drv (Di((i 72), Dir(12,))) & /
B(aa-1
Proof. Let (P be the squared Hellinger distance.
H² (Dir(7, (2), Dir(12, 7))
-2 /
Vf(x; 71, 72) [ 72,
=2 - 2 f
21 - (1 - x) 2
(22)
B32 71)
B (2 71
=2 2
B(12.m)
By the relation between total variant distance and the squared Hellinger distance,
B =2 21
drv
m)) S /2 2- B(72, 71)
(23)
C.3 PROOF OF THEOREM 5.1
We summarize the proof of Theorem 5.1 I in the following lemmas, and the proofs of the Lemmas are We first prove that the variance of normal workers is bounded in Lemma 3
in Appendix C.4 C.8
Lemma (Statistic of IID normal workers), Let {W: be [Sa] datasets that each dataset con- sists of n data sampled independently from distribution When n >> 1 me there exists a constant C' that with probability 1 8,
Varw Varm ((W))ie))))))) S ( dln(mnndd) + ln(18))
(24)
mn
In Lemma 4 we prove that when the variance of normal workers is bounded, Algorithm 2 can output a weight such that the weighted variance of all workers is also bounded by a similar bound.
Lemma (Property of W Wiightupaate), For a 3. let be the weight vector output by W "eightUppaaee (a) in Algorithm 2 Then, w E Cg.g, where E 2
1-2a" B
1-30
1 2o.
t < 4- D--aaaar arr (FW((FWres).).
1-3a
Since the above Lemma proves that Algorithm poutptt weight vector in Cg.e,, in Lemma 5 we prove that the distance between the weighted distribution Dw and the unknown distribution D can be bounded by t and 8 when w E Cg.g.--
Lemma (Property of Cg.e.).. For w E CBa.s.
1-5
BE
dn Dw) SV
Varx ((W))((
3E
(25)
+ Ui,,s, W.)
15

---

Published as a conference paper at ICLR 2026
Since die (D, (ie,,,)) is the H--divergence between D and [S, In samples independently sampled
from D. By Lemma in Ben-David al. (010)). dx(,, (Es,) Ō(( _ ) Therefore,
du Dw) O(()) ) Then, the EPR bound in Theorem 5.1 directly follows the
above lemmas.
For the attack loss, the following lemma shows the relation between du (D, Dw) and (ED(h) EDw (h)).
Lemma 6. Let be a hypothesis in class H. Then, (ED(h) - ED ( S 2dx (D,
C.4 PROOF OF LEMMA
PP ((.,))>w.ly = v', sign(go(z)) = 1]. Let m' = [.,). Draw m'n samples from the dataset and randomly partition them into m' groups of size n. Define [i/n] and r = i i- (s 1)n, and let X; be the sample assigned to position in worker s's local dataset. Consider an m' di-dimmnsional vector v with entries V,. Define (0) (i. ( and
Proof. Let Fi.r
(0) Em (0). We construct the Doob martingale
Zv F(Fv.y X1 Xx)
(26)
Since k. Zv Zv S
|vll the Azuma-Hogffding incquality yields aym"
||v||2
E
S
exp
(27)
8m
Let n. Ze, m. where e, is the i-th standard basis vector. Then, for any 2n.
]
$ 11
t
mm' /2
E
exp
Z
Lim'n
(28)
2n
Applying Chernoff's bounding method,
P
Σ
Dran' n.y. >e Se-tt(1
)
)
(29)
The above probability is calculated given the 6. Since d is the VC-dimension of the hypothesis class induced by θ by the uniform bound, for any 0 O
P
n
Z
n.g.0
m'
+ e, AOA < cen'n " e - ama
(1 2n
) -mmmm m
(30)
4n
Therefore, with probability 1 1-
Varu([W.))
n
In(1/8) + dnndddnmn///// (ndemmnn/d tm' /4n (m (2m In t/2n)
+ min
m//
(31)
/dlm(mn/dd) In(1/5)
Vmn
dIn(mnn/d + ln(1/8)
12
mn
16

---

Published as a conference paper at ICLR 2026
C.5 PROOF OF LEMMA 4
Proof. Since |S| < (1 - 20)m, it is evident from the algorithm that { 2
1-3a
and / 2 1 - 12..
1-2a
In the following, we show that the algorithm outputs,
Varu([Wij) mm
w) - 9a
VarH ((W))es)
3x
We prove this by contradiction. Assume that k 2 will not output.
4-9a
We show that in this case, the algorithm
1-3a"
We define some notations. For v f and w variance be
define the weighted mean and {w; am
(lv, w) Dis Witt Ei wi
m wilu - p(v, w))²
and Var(v, w)
E Wi
We partition = w + w as follows: w" is the m-dimensional vector with
w w:
if E Sn if E Spr
0
and w is the m-dimensional vector with
Wi
if E Sp: i E Sn.
Then, we define
S
S
||Sp n
On,,
Opr
m
Let be the m-dimensional vector whose i-th element is defined in Section 4
Inductive claim. We prove by induction that at each round r, when is 2 I-3a
4-9e
17 2 V
3a
+
1,
30
Onn Oppr
1 - 2a + 1t
and
Onnr 2 1 2ax
Thus, |S] 2 (1 2a)m.
Inductive step. By the constraint & Var(T, w")) Var(T, w) and the variance decomposition formula, we obtain
k(an, + Var(T) w") = Var(T, w") + apr Var(T (f,w), wP)
+ tanr(u(T, w") ) (1(T w)) tp,prHlTT, w²) - M(TT, w))²
(32)
Rearranging gives
((k: 1)an, + Mar.-)) w") (n (!) uU(,, w))²
(33)
Sap. [Var(T, wP) + (M(T, w²) 11(T, w))?]
Let |u(T, wn) U(T, w)l and k' k(an, + ap,r) Un,r
Var(T, w() + +x²
Opp
On, + Var(T, wP) +
x22
Var(T, w²)
Onn (0mxz)) x:2 ag.
W
b
On x)²
an
app.
On, + 1)(
Cpp. ) Onr
b
+
k!
(34)
2
On.r
1
0
Cppr
On, tap.
17

---

Published as a conference paper at ICLR 2026
This implies
ap.r
On.r
WET
(35)
max
nn
Opp (k
Onrr tapr
max
SESp
Since S 17 for for i S441 and 17 S 8/ S 17 + for any i & Sy+1, by the induction claim, we have
-0 a -a
a
(n0 + (1+ 1)(a - aprr+1)) m. (36)
1- 20x + 1+1
k k-1
Thus,
apr
an,+1 21 21-a-
+
(37)
1
1+1
1
"1
"1
Since
n h+1 1
+ 8-1
(38)
1 1a +
I+n
we have
2 - 2a + aprr+1
0n,441
(39)
Since 0 S ap,r+1 S. a, it follows that
2a + m+1
ap,r-1
2
(40)
ap.r+1
Q
and
0n,r+1 2 1 - 20.
(41)
Finally, since |S] decreases by least 1 each round, the algorithm terminates.
C.6 PROOF OF LEMMA 5
Proof. Since E CB.g.t, Eies, Wi 2 E. By Lemma for all 0,y,
2
W ()) - Σ w Wf ()))
m
1 1-
(42)
Lies,
Wi
E
EES
j=1
Similarly,
Wi
(0)
Σ F2)(()
Cies, Wl
SSa
JESn
jESn
(43)
3E Varn(tWiless))
<
BE
The distribution Dw is the compound sampling such that for each sample in the data set of each worker i, the sampling probability is " mi Therefore,
w.
dx (D, Dw) Sdx (UiEs, W., Dw) + dx( W.)
1-
1- a 3E
E ++
Varx((W))es..
(44)
BE
+ dD. (D, Vies.
18

---

Published as a conference paper at ICLR 2026
Lemma 7 (Property of weighted variance). Forv for and w [w: mean and variance as
define the weighted
Ei=1 Witi t 2i=1 w,
(vv, w)
and Var(v,w)
Σ
Wi( - μl w))²
D -i=1
W/
iml
Consider weight vector w' + w" with ws w/o wp 2 0. Li=1 wi L, and = (0, 1). Then
-i= ma
(uv, u(v, 1- VE Var(v,
(45)
Proof. By the variance decomposition formula,
Var(v, w) - [ [Var ava(v, w + (n(v, w') H(v,, [(v,,w))
(46)
+ (1 [Var(v, w") + (u(v,w") w))
Since variances nonnegative, we have
Var(v, w) 2 5(u(v, w') (u(, w))² + (1 - -VVVV w") - v1(v, w))?
(47)
Using the constraint ((v, w) = (') (1 - E)m(v. w"), we obtain
- Eu(V, w") u(v, E I- -- (') -ul, w))?
(48)
Combining these yields
5 - Elu(v, ulv, -(v, - 1-
8 (K(v, - -u(v,w))
Var(v, w) 2 1 g
(49)
Taking square roots completes the proof.
C.7 PROPERTY OF ?-DIVERRENNE
For completeness, we briefly prove du (Wihes,) Ö( ) by the following lemma. Let Nott = nm. The lemma characterizes the property of H-divergence between distribution and neo samples from the distribution.
Lemma 8 (Property of dx). Let D be nhat data sampled independently from the distribution D. Then, with probability
2d 2dgogeene 16
2 ln(40)
dx (D,D)) S 8/
(50)
Nhto
Nooo
Proof. Let (x1, for any y'.
(Xn, Un) be the Noot data samples. Then, by the property of VC-dimension,
H((( v/)((h (x1) =1),
T(m = -/) (x,) = 1)) h E 7H
(51)
entot d
Using Theorem 26.5 and 26.8 in Shalev-Shward & Ben-Davil 2014), we obtain that with proba- bility of at least 1 - 8, for every H we have that
log(ennoo /d) + /
In (n/4/))
dn D) < S/
(52)
Peeo
neso
19

---

Published as a conference paper at ICLR 2026
C.8 PROOF OF LEMMA 6
Proof. By the definition of the learning error,
(h)) =P (a.)) 1, -1
(53)
((.))) (h(x))(()))))))))())) 11,
By the definition of H-divergence,
du (D,
Σ By (P(ew))olM())=1111 y'1 ((..)) -1, 1, = V'EY
sup AEH,
(54)
Σ ay (P(e.))olM(z)== -1, s/1 - -P (r..)>/(((()) 1, v1)
sup AEH,NEAI
y'EY
Therefore,
(cD-(h)-coll 2dn (D, D')
(55)
C.9 PROOF OF THEOREM A.1
Theorem A.T can be proved in the same way as Theorem 5.1 except the the variance of normal workers is bounded in the following lemma:
Lemma 9 (Statistic of non-IID normal workers), Let (Wi)m be m' data sets that each data set sampled from (2*). With probability 1 5,
(orn((Wi)ess))- o (: +- n
d'Inmmn/d) + 1n(1/8) In (1/5)
(56)
mn
2m
Proof. Let be the vector that worker sampled from Dir(p). Let De.j be the distribution of value (0,x,) = [l = (sig((i(gg) (z)) = 1), where (x,z) y) Dg. Let μie the expectation of Daj and μs be the Jddimension vector that each jth element μtg.j- Then, we can write Fl (0) = [ Sy (0, y) such that (0, 20, v) E [0, 1] and each fyr (0, x. y) an random variable from Do(g) = Σÿ- li Ui Da.j- Then,
Varu ((Wiles)))
2
1
max max PCy ICO
F
(0)
m
m'
j=1
m
(57)
< max max y 6 m
max (0P - (O)))
1=1
m (q: - 140 p 2o)
max max
yCy 8CB m7!
Therefore, the variance is bounded by the variance in the IID setting plus the variance induced by the non-IID feature.
For any a such that each element Pw E [0, 1], let q sampled from Dir(p). Since each element pair of vector q p is negatively correlated,
Eq-Dirrp)lla-H --pl-l-p----- p-m)3]
Σ L
p;)
1
(58)
7 7+1
20

---

Published as a conference paper at ICLR 2026
Thus, with probability 1 5,
m
1
In (1/8)
max max yCy OC0 m
2 (q. po p -O02 -
(59)
2(7 + 1)
2m
Thus,
(ars((Wi)iEss)) =0(= 1 dlInmmn/d)) + 1l(11//)
In (1/0)
(60)
mn
2m
D EXPERIMENT DETAILS
Our experiment run on an RTX 4090 GPU. In the label-flip attack, adversary increments each label by one, with 9 wrapping around O. For MNIST experiments, (DNN) with 2 hidden layers and 128 neurons in each hidden layer. We conduct 5 experiments for each hyperparameter combination. Our algorithm maintains higher test accuracy and lower attack accuracy with Wilcoxon test p-values all below 0.05.
dense neural network
D.1 VARIANCE MAXIMIZATION PROCESS
The maximization process Line 5 of Algorithm in conducted by generalized FedAVG as in Algorithm 4
For the function (0, a), we use the sigmoid function o(z) = Ite to replace the sign function to induce the hypothesis from the model parameter. Therefore, we let a) (e..)>w.lyy ay Ily - y y')a (go (x))] in Line 5 and Line 6 in Algorithm
Algorithm 4: Variance Maximization: a <- arg maxg, En wi (F)(0,a) - wy
Worker i:
If selected by the server, compute
grad <- Ve.,a. F,(O,, a,)
value, +- F2 a,)
Send grad,, value," server; Server:
for ... do
Randomly select workers;
Let {grad,, value; Hejj [sj be the received gradient and value from the selected workers;
Let value" be mean of {value, hegh grad, + EiEjo (value, value" value")gradd"
10
0.41 + O, grgad,
11
end
D.1.1 COMPLEXITY OF VARIANCE MAXIMIZATION PROCESS
From Algorithm we can for the server-side computational complexity, that computation burden for the server at each round is almost the same as that of FedAVG with & workers selected each round. By contrast, aggregating the gradients with robust mean estimation techniques needs extra optimization processes. For example, for the geometric median, Weiszfeld's iterative algo- rithm BBrimeeg (2016) may be needed.
21

---

Published as a conference paper at ICLR 2026
attack accuracy
attack accuracy
attack accuracy
1.0+
0.6
0:75
0.4-
02-
0.50
0.25
60
(a) data number 72
120
(c)
poison ratio B
(e)
22
data number 72
krum
iterative heerative_ltternng
0.00
0.8
goo ____mediin
rest accuracy
0190-
rest accuracy
test accuracy
this work
0.65
0.6
0.35-
0.50
0.00
0.75
0.-
0.25
6:70
(b) data number n
1200
(d)
poison ratio
data number
Figure 3: Experimental results. (a-d) conducted against the backdoor attack. (e,f) are conducted in the CIFAR-10 10 dataset.
E FURTHER EXPERIMENT RESULT
Evaluation under backdoor attack. Figure 3 a-d) demonstrates that our algorithm is also effective against the backdoor attack. We reimplement backdoor attacks based on code provided by Bag- dasaryan et all (Bagdasryyan & Shmatikov (2021) and the federated learning mechanism and train- ing models based on code provided by Lin et al Lin et al. 2020). We consider 200 normal workers and 50 workers with poisoned data. In Figure 3 aa-b), we consider n samples for each worker, and all data in each poisoned dataset are backdoor data. In Figure Bc-d), we consider 30 samples for each worker, and / proportion of data in each poisoned dataset backdoor data. Our algorithm maintains higher test accuracy and lower attack accuracy than the baselines in both settings.
Evaluation under CIFAR-10. Figure Z[e-I), demonstrates that our algorithm is also effective in the CIFAR- 10 dataset. We use VGG13 as the neural network. We consider n samples for each worker, and all data in each poisoned dataset are label-flip data. Figure [e) shows that all the baseline algorithms can not defend against the adversary's free ride. The accuracies are close to 1 in terms of the poisoned data. In contrast, our algorithm effectively suppresses the accuracy on the poisoned data.
Evaluation under the same complexity budget constraint. Figure (a-b) presents a performance comparison between our proposed algorithm and existing methods under the same complexity bud- get. The horizontal axis denotes the epoch, defined as the computational complexity associated with processing the entire dataset to perform one gradient update. More specifically, the computation complexity for each epoch is mndy. where m is the number of workers, n is the number of data samples for each worker, and d, is the dimension of each gradient. The communication complexity is rıd.. since each worker computes the gradient on each of its local data samples before submitting gradients the server in this experiment. Since our algorithm has two phases, we assign the com- plexity budget to the two phases proportionally, with 40% going to the first and 60% to the second. For example, with 20 epochs, we use epochs for training the discriminator model and 16 epochs for training the target model. Our algorithm achieves the highest test accuracy and lowest attack accuracy.
Evaluation under the same complexity privacy constraint. In Figure T cc-d), we show the com- patibility of our algorithm and the local differential privacy. presents performance comparison between proposed algorithm and existing methods under the same privacy budget. We follow the method in Abadi et al.] (2016) to achieve differential privacy. We add the Gaussian noise to both gradients and model output values, F, a), sent to the server. More specifically, for the output value, we add Gaussian noise (0, VT).. For the gradient, we first clip the norm of the gradient 1 and add Gaussian noise (O TT), where T is the total number of output values and the
22

---

Published as a conference paper at ICLR 2026
1.0
atlook axcuracy
LeSt socumnc
0.75
0.5
0.5
0.50
0.8
0.25
0.0
0.01
10
20
30
(b)
10
20
30
(c)
0.00
0.022
0.04
(d)
0.00
0.02
0.04
epoch
spoch
noise
1,0
accuracy
test accuray
0.8
principle sine
principle sizer
0.5
0.5
0.0
0.6
0.0
100
1
(h)
data number is
data mumber
principle sixs
principle siss
1.0
1est accurary
88
0.5
06
0.0
0.50
0,75
0.50
0.75
poison rnlo
poison
Figure 4: Experimental results. (a-b) are evaluated under the same complexity budget constraint. (c-d) are evaluated under the same privacy budget constraint. (e-f) compares the performance of our algorithm against the label-flipping defenses. (g) illustrates the principal components of gradients calculated by workers. (h) illustrates the principal components of worker datasets in terms of the H-divergence.
gradients sent to the server. Since with the same a,, each method consumes the same privacy budget, our algorithm achieves the highest test accuracy and lowest attack accuracy under the same privacy budget.
Comparison with label-flipping defenses. In Figure (--f), we compare our algorithm with base- line label-flipping defenses Jebreel et al. (2024): Hallaji et al. (2023). [Jeghter[Jebreel et al. (2024) leverages the K-means algorithm to detect workers with poisoned data by clustering the gradients extracted from the last layer of the neural network. |Hallaii et al. (023) incorporates robust training methods to immunize itself against label-flip attacks. Since the algorithm is compatible with various robust training methods, we adopt symmetric cross-entropy learning (SCEL) Wang et al. (2019) as a representative. We use a wider neural network with 1024 neurons in each hidden layer to amplify the differences between algorithms. Our algorithm achieves the highest test accuracy and lowest attack accuracy in a wide neural network.
Comparison with robust gradient aggregation with bucketing. In Figure 4 (-j). compare our
algorithm with robust gradient aggregation with bucketing Karimireddy et al. (2022). We consider --uckketing (each bucket having elements) for Krum and geometric median, with
and 8 2. We consider 200 normal workers and 50 workers with poisoned data, so can at most be 2. We consider the non-llD setting with concentration parameter being 1.0 and 30 data samples worker. As in Karimireddy et al. (2022). bucketing improves test accuracy in non-iid setting. However, we also observe higher attack accuracy with larger bucket size. Our algorithm achieves the highest test accuracy and lowest attack accuracy in non-iid setting compared to robust gradient aggregation methods with various bucket sizes.
Intuition that explains our algorithm's effectiveness. Figure g- explains why our discriminator-weightin algorithm is more effective than gradient aggregation. Figure (g illus- trates two principal components of gradients calculated by workers, which are two orthogonal pro- jections that maximize the variance of gradients in Euclidean distance. Figure 4[h) illustrates two principal components that maximize the variance of workers' datasets defined in Definition 41 Each scatter point represents a worker. The relative distance between the two points illustrates the H-divergence between the two workers' datasets. More specifically, the x-axis (y-axis) of the point
23

---

Published as a conference paper at ICLR 2026
corresponding to the worker i is F.(8, a). where (f,, a) is obtained in Algorithm 2 Line 5 in round r = -1 2).
We can that it is hard to differentiate the normal datasets from the poisoned datasets from the gradients in Figure However, it is casy to differentiate them through the lens H-divergence in Figure h)), since it directly characterizes the distance between datasets. This is because the gradient is an indirect representative of the dataset. Therefore, gradient aggregation can be less effective compared to our approach.
F BACKGROUND: FEDERATED LEARNING AND FEDAVG
We describe the problem formulation of federated learning McMahan al. (2017). A federated learning system consists of federated learning setting with one parameter server and m worker nodes. Each worker i has a loss function Fi(0) calculated from his own dataset, where / is the model parameter. Federated learning with weight vector w [w aims to minimize the following function:
min [(())
& m
Σ w (.())))))))
(61)
basic federated learning mechanism in which the worker calculates the gradient of his local dataset and the server collects the gradients and updates the model with weighted average of the gradients. The mechanism described in Algorithm 3 in Appendix
FedAVG McMahan al. (2017); Chen et al. (2017)
FedAVG can be generalized minimize the following function:
min { (F())
Fi.
(62)
For each round r, workers calculate the local gradient Jür and local value F.(O,). Then, workers send them the server the server update the model follows:
0f grads,
0,+1 + 0, - 17r OF.(0,) )F.(0,)9rau.,
(63)
24


Reviews:
[{"review_id": "XRpUS8DC7e", "reviewer": "Reviewer_pxLN", "summary": "This paper addresses the problem of defending against data poisoning attacks in Federated Learning (FL), focusing on the practical scenario where the number of workers $m$ is large, but each has only a small local dataset of size $n$. The authors make three key contributions:\n\nLower Bounds: They establish minimax lower bounds for the attack loss, proving it is $\\Omega(1/\\sqrt{n})$ in the IID setting and $\\Omega(1/\\sqrt{\\gamma} + 1/\\sqrt{n})$ in a Dirichlet-based non-IID setting (where $\\gamma$ is the concentration parameter).\n\nNovel Algorithm: They propose a two-phase algorithm. The core innovation is a trustworthiness weight update phase that trains a discriminator model to maximize a notion of dataset variance, allowing the server to assign weights to workers and effectively identify those with poisoned data. This is fundamentally different from prior robust gradient aggregation methods.\n\nNew Metric and Upper Bounds: They introduce a new robustness metric, the Effective Poison Rate (EPR), to quantify the adversary's gain. Their algorithm achieves upper bounds for both attack loss and EPR of $\\tilde{O}(1/\\sqrt{n} + \\sqrt{d/(mn)})$ (IID) and $\\tilde{O}(1/\\sqrt{\\gamma} + 1/\\sqrt{n} + \\sqrt{d/(mn)})$ (non-IID), which asymptotically match the lower bounds when $m \\rightarrow \\infty$, demonstrating near-optimality.", "questions": "The theoretical analysis and algorithm design assume $\\alpha < 1/3$. What is the empirical performance of your method when $\\alpha \\geq 1/3$? Does the performance degrade gracefully, or is there a sharp breakdown point? Is there a pathway to relax this assumption in future work?\n\nThe trustworthiness weight update phase is a pre-training step. How does the computational and communication cost of this phase scale with the number of workers $m$ and the model/discriminator complexity? Could this initial phase become a bottleneck in very large-scale FL systems compared to baselines that perform robust aggregation during the main training?\n\nYour method effectively identifies and down-weights suspicious workers. However, in a strongly non-IID setting, could \"honest but unusual\" workers (those with rare but valid data distributions) be mistakenly penalized by your variance-maximizing discriminator? How does your theory or experiments account for or mitigate this potential issue?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "Novel Defense Strategy: The two-phase algorithm, particularly the trustworthiness weight update phase using a discriminator model, is a creative and well-motivated departure from existing methods.\n\nTheoretical Completeness: Provides a full minimax analysis with matching lower and upper bounds under both IID and non-IID settings, a hallmark of strong theoretical work.\n\nPractical Performance: Empirically demonstrates superior performance over several strong baselines on multiple datasets and attack types, validating the theoretical advantages.\n\nNew Metric: The Effective Poison Rate (EPR) is a useful and intuitive metric for quantifying the adversary's success beyond simple test accuracy.", "weaknesses": "Computational Overhead: The trustworthiness weight update phase requires training an auxiliary discriminator model, which adds non-trivial computational and communication cost before the main training can begin. While argued to be similar to FedAvg per round, the total cost of this extra phase is not thoroughly compared against baselines.\n\nStrong Assumption on $\\alpha$: The theoretical guarantees hold under the assumption that the fraction of malicious workers $\\alpha < 1/3$. The performance of the algorithm when this assumption is violated (e.g., $\\alpha \\geq 1/3$) is not explored empirically or discussed in depth.\n\nClarity of Presentation: As noted above, the paper is challenging to read. The technical depth is high, but the presentation could do more to guide the reader through the complex ideas and proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9TlAtHCKd8", "reviewer": "Reviewer_vDhi", "summary": "The paper addresses the challenge of defending against data poisoning attacks in federated learning by proposing a novel algorithm. The method first assigns a trustworthiness weight to each worker based on the variance of datasets, and then updates the global model using local gradients weighted by these trustworthiness weights. The authors provide a theoretical analysis of the attack loss, establishing an upper bound that matches the lower bound as the local dataset size approaches infinity. Empirical results further corroborate the theoretical analysis, demonstrating the algorithm’s robustness under data poisoning attacks and its superiority over representative robust aggregators.", "questions": "My detailed questions are listed in the above section; please refer to it.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The investigated problem of developing federated learning algorithms robust to data poisoning attacks is important and remains relatively underexplored.\n\t\t\n2.  This paper conveys a key message that fine-grained algorithmic designs can defend against data poisoning attacks by exploiting the fact that poisoned workers still strictly follow the algorithmic protocol, rather than relying on coarse-grained robust aggregators.", "weaknesses": "1. The lower bounds of the attack loss presented in Theorems 3.1 and 3.2 appear to be not tight, as the upper bounds of the proposed algorithm in Theorems 5.1 and A.1 do not align with them, leaving at least a gap of $\\tilde{O}\\left(\\sqrt{\\frac{d}{mn}}\\right)$. Could the lower or upper bounds be further improved to close this gap?\n\t\t\n2. Related to my above comment, the authors should compare their derived lower bound with that in the case of model poisoning attacks, e.g., $\\Omega\\left(\\frac{\\alpha}{\\sqrt{n}} + \\sqrt{\\frac{d_g}{mn}}\\right)$ in Yin et al. (2018), and clarify why the lower bound under data poisoning attacks is asymptotically smaller than that under model poisoning attacks.\n\t\t\n3. In Equation (8), what is the role of the probability simplex $a$? Furthermore, does the updated value $F_i(\\theta, a)$ pose any risk to the privacy of worker $i$? The authors are encouraged to provide further discussion on these points.\n\t\t\n4. In line 319, the authors claim that the variance of normal workers’ datasets is small when their datasets are correlated. In my view, this holds only under the i.i.d. setting. Will this statement also hold in the non-i.i.d. case? If so, please provide a detailed explanation, as this is a key insight underlying the proposed algorithm.\n\t\t\n5. In Algorithm 2, the server removes a worker when its score exceeds a threshold $\\eta$. How is $\\eta$ chosen, either theoretically or in the experiments? Furthermore, why is the final size of the trust set $(1-2\\alpha)m$ rather than $(1-\\alpha)m$, given that only an $\\alpha$ fraction of workers are poisoned?\n\t\t\n\t\t\n6. The experimental baselines are limited. Several other algorithms defend against data poisoning attacks in federated learning [1] [2]. The authors should include comparisons with these methods in their experiments.\n\n    [1] Jebreel, N. M., Domingo-Ferrer, J., Sánchez, D., \\& Blanco-Justicia, A. (2024). Lfighter: Defending against the label-flipping attack in federated learning. Neural Networks, 170, 111-126.\n\n    [2] Hallaji, E., Razavi-Far, R., Saif, M., \\& Herrera-Viedma, E. (2023). Label noise analysis meets adversarial training: A defense against label poisoning in federated learning. Knowledge-based systems, 266, 110384.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TGzIViWqrZ", "reviewer": "Reviewer_73aR", "summary": "This paper proposes a mechanism for data poisoning attacks in federated learning that asymptotically achieves the theoretical lower bound of attack loss in both IID and non-IID settings when α<1/3. Additionally, the authors introduce a new metric, EPR, to quantify the effectiveness of data poisoning attacks.", "questions": "See Weaknesses.", "limitations": "", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper proposes a mechanism for data poisoning attacks in federated learning that asymptotically achieves the theoretical lower bound of attack loss in both IID and non-IID settings when α<1/3.\n2. The authors introduce a new metric, EPR, to quantify the effectiveness of data poisoning attacks.", "weaknesses": "**The main contributions of this paper lie in the theoretical domain, an area where I do not feel adequately qualified. Therefore, I will focus my critique primarily on potential weaknesses from a practical perspective.**\n\n1. From a practical perspective, data poisoning attacks are generally considered less threatening to federated learning (FL) systems than model poisoning attacks. The latter can directly manipulate model parameters to make malicious updates resemble benign ones, thereby evading detection more effectively. The paper does not clearly justify why focusing on data poisoning is necessary or impactful given this context.\n\n2. The experimental evaluation includes only four baseline methods, all of which were proposed before 2022. This limited selection raises concerns about the adequacy and fairness of the comparison. Including more recent and stronger baselines would provide a clearer picture of the proposed method’s relative performance and novelty.\n\n3. The proposed method is evaluated only on two small-scale datasets, MNIST and CIFAR-10. While these benchmarks are commonly used, they are insufficient to demonstrate robustness and scalability in realistic FL scenarios. Experiments on larger datasets such as ImageNet would strengthen the empirical claims, and extending the evaluation to other modalities, such as NLP tasks, could further validate the generality of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DiSpjzlEDN", "reviewer": "Reviewer_XehN", "summary": "The paper studies robust federated learning (FL) under data poisoning in the regime with many workers \\(m\\) and few samples per worker \\(n\\). The authors focus on two goals: minimizing the attack loss (excess error over the attack-free optimum) and bounding a new metric, Effective Poison Rate (EPR), which measures how much of the overall data becomes *effectively* poisoned by the learning pipeline. \n\nThey first prove minimax lower bounds on the unavoidable attack loss: in IID settings the loss is \\(\\Omega(1/\\sqrt{n})\\); for non-IID modeled with a Dirichlet distribution of concentration \\(\\gamma\\), there is an extra \\(\\Omega(1/\\sqrt{\\gamma})\\) penalty. Then they propose a two-phase defense. Phase 1 learns trustworthiness weights for workers by training a discriminator to maximize a dataset-variance objective aligned with an \\(H\\)-divergence view; workers with high deviation get down-weighted. Phase 2 runs weighted FedAvg using these trust weights. \n\nThe authors prove upper bounds that match the lower bounds up to logarithmic factors: for IID, attack loss and EPR are \\(\\tilde{O}\\!\\left(1/\\sqrt{n}+\\sqrt{d/(mn)}\\right)\\); for non-IID, they add \\(\\tilde{O}(1/\\sqrt{\\gamma})\\). Here \\(d\\) is a capacity term (e.g., VC dimension). Empirically, on MNIST and CIFAR-10 with label-flip and backdoor attacks, the method tends to improve test accuracy and decrease attack success compared to geometric median, Krum, and iterative filtering, while keeping server-side cost close to standard FedAvg. Overall I feel the paper is promising and quite practical.", "questions": "The following two papers seem very related\n   - An Equivalence Between Data Poisoning and Byzantine Gradient Attacks (S. Farhadkhani, R. Guerraoui, L. Hoang, O. Villemaud).  \n   - On the Relevance of Byzantine Robust Optimization Against Data Poisoning (Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot).  \n   What is the connection with those results? In particular, how do your EPR notion and your lower/upper bounds relate to the equivalence and to the implications for gradient-robust optimization? Do your results identify regimes where gradient-robustness is provably insufficient but your discriminator-weighting remains effective?\n\n\nCan your method work under secure aggregation or local differential privacy? If gradients/outputs are obfuscated, can the \\(H\\)-divergence alignment still be estimated reliably?\n\nIn cross-device FL with partial participation, \\(\\alpha\\) can change across rounds. Do your theory and algorithm adapt if the set of corrupted clients varies over time?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear objectives: I appreciate the joint focus on attack loss and the new EPR metric.\n- Matching Lower and upper bounds align up to logs in both IID and non-IID cases, and the non-IID penalty is expressed cleanly via \\(\\gamma\\).\n-The algorithm and results are novel to my knowledge. Using a discriminator on client datasets (outputs) to drive weights avoids heavy dependence on high-dimensional gradient aggregation.\n- Practical cost: Communication and compute remain similar to FedAvg; the method seems easy to plug into existing FL pipelines.", "weaknesses": "- Baselines are mostly classic robust aggregators. Including more recent FL defenses (NNM, Bucketing, ...) and also poisoning specific defenses (see questions below) would give a fairer picture of current SOTA.\n\n\n- Many results rely on \\(\\alpha<1/3\\). Whereas most other works only require a majority of honest clients. is there a fundamental reason for this?\n\n- Experiments mainly test label-flip and standard backdoor. Stronger or adaptive poisoning (e.g., clean-label poisoning, gradient-aware poisoning including fall of empires and a liitle is enough) would strengthen the empirical story.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)