Trade-off in Estimating the Number of Byzantine Clients in Federated Learning

## Abstract

Abstract Federated learning has attracted increasing attention at recent large-scale optimization and machine learning research and applications, but is also vulnerable to Byzantine clients that can send any erroneous signals. Robust aggregators are commonly used to resist Byzantine clients. This usually requires to estimate the unknown number f f of Byzantine clients, and thus accordingly select the aggregators with proper degree of robustness (i.e., the maximum number f ^ \hat{f} of Byzantine clients allowed by the aggregator). Such an estimation should have important effect on the performance, which has not been systematically studied to our knowledge. This work will fill in the gap by theoretically analyzing the worst-case error of aggregators as well as its induced federated learning algorithm for any cases of f ^ \hat{f} and f f . Specifically, we will show that underestimation ( f ^ < f \hat{f}<f ) can lead to arbitrarily poor performance for both aggregators and federated learning. For non-underestimation ( f ^ ≥ f \hat{f}\geq f ), we have proved optimal lower and upper bounds of the same order on the errors of both aggregators and federated learning. All these optimal bounds are proportional to f ^ / ( n − f − f ^ ) \hat{f}/(n-f-\hat{f}) with n n clients, which monotonically increases with larger f ^ \hat{f} . This indicates a fundamental trade-off: while an aggregator with a larger robustness degree f ^ \hat{f} can solve federated learning problems of wider range f ∈ [ 0 , f ^ ] f\in[0,\hat{f}] , the performance can deteriorate when there are actually fewer or even no Byzantine clients (i.e., f ∈ [ 0 , f ^ ) f\in[0,\hat{f}) ).

### 1 Introduction

Federated learning proposed by (McMahan et al., 2017) is an important and popular framework for large-scale optimization and machine learning where multiple clients (i.e. computing devices) collaboratively optimize the objective function while keeping their local training data private. The most fundamental and common algorithm is federated averaging (FedAvg) (McMahan et al., 2017; Li et al., 2020; Collins et al., 2022), where the clients update their own model by using multiple steps of gradient-based approach on their own data, upload their updated models to the server, and download the average of these models from the server.

However, federated learning algorithms such as FedAvg is vulnerable to Byzantine clients (Lamport et al., 2019) which can upload arbitrary model to the server. A fundamental and popular way to make federated learning algorithm robust to Byzantine clients is to apply a robust aggregation to the uploaded models to filter outliers (Li et al., 2021a, 2023; Allouah et al., 2024). Some representative aggregations include geometric median (GM) (Chen et al., 2017; Pillutla et al., 2022), coordinate-wise trimmed mean (CWTM) (Yin et al., 2018), coordinate-wise median (CWMed) (Yin et al., 2018), Krum (Blanchard et al., 2017), centered clipping (Karimireddy et al., 2021), clustering (Sattler et al., 2020; Li et al., 2021b), etc., as summarized and empirically compared in (Li et al., 2023). Existing works typically require to estimate the actual number $f$ or the fraction of the Byzantine clients to select the maximum number $\hat{f}$ that the aggregator can tolerate (Karimireddy et al., 2022; Gupta et al., 2023; Allouah et al., 2024; Otsuka et al., 2025), but $f$ is usually unknown in applications. Hence, an estimation $\hat{f}\approx f$ is usually needed, while it still lacks a systematic study on the effect of the estimation $\hat{f}$ on the performance of federated learning. Therefore, it is natural to ask the following fundamental research question:

#### 1.1 Our Contributions

To our knowledge, this work for the first time systematically investigates the theoretical effect of the estimated number of Byzantine clients on federated learning performance. In particular, we theoretically prove that underestimation of $f$ (i.e. $\hat{f}<f$) can lead to arbitrarily poor performance on both aggregation error and convergence of the commonly used Federated Robust Averaging (FedRo) algorithm, even if the objective function satisfies the Polyak-Łojasiewicz (PŁ) condition that is amenable to global convergence. When $\hat{f}\geq f$ (non-underestimation), we obtain the lower and upper bounds of the aggregation error and convergence rate of FedRo. Each lower bound is tight as its order matches the corresponding upper bound. All these tight bounds are proportional to $\frac{\hat{f}}{n-f-\hat{f}}$ with $n$ clients, which is monotonically increasing as $\hat{f}$ increases from $f$. This indicates a fundamental trade-off: while an aggregator with a larger robustness degree $\hat{f}$ can solve federated learning problems of wider range $f\in[0,\hat{f}]$, the performance can deteriorate when there are actually fewer or even no Byzantine clients (i.e., $f\in[0,\hat{f})$).

#### 1.2 Related Works

Some federated learning works (Bagdasaryan et al., 2020; Tolpegin et al., 2020; Wang et al., 2020a; Xie et al., 2020) focus on targeted attacks (i.e., back-door attacks) that fool the global model to predict certain samples with some incorrect targeted labels, while this work focuses on untargeted attacks (i.e., Byzantine attacks) (Li et al., 2023; Allouah et al., 2024; Xu et al., 2025) that hamper the overall learning performance with no specific focus. In addition to aggregation-based approach of our focus, various other approaches have been proposed to resist Byzantine clients in federated learning. Xie et al. (2019); Cao et al. (2021); Park et al. (2021); Kritharakis et al. (2025) allow the server to preserve some representative data samples to evaluate and select the uploaded models, which is not always possible in practice since these representative samples can be similar to those on the local clients and thus raise privacy concern (Xu et al., 2025). Panda et al. (2022); Meng et al. (2023); Zhang & Hu (2023); Xu et al. (2025) sparsify the model updates to alleviate the effect of Byzantine clients.

### 2 Preliminaries

Federated Learning Problem with Byzantine Clients: In standard federated learning, there is a server communicating with $n$ clients. Among the $n$ clients indexed by $[n]\overset{\rm def}{=}\{1,2,\ldots,n\}$ respectively, there are $f$ Byzantine clients sending any erroneous signals (Byzantine attack) to interfere with the server. Denote $\mathcal{H}$ as the set of the other honest clients, with size $|\mathcal{H}|=n-f$. The server can only communicate model parameters with the clients, but does not know the number and identity of the Byzantine clients. These honest clients aim to collaboratively solve the following optimization problem, under the interference of the $f$ Byzantine clients.

$$ $\displaystyle\min_{w\in\mathbb{R}^{d}}\Big\{\ell_{\mathcal{H}}(w)\overset{\rm def}{=}\frac{1}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\ell_{k}(w)\Big\}.$ (1) $$

where the loss function $\ell_{k}:\mathbb{R}^{d}\to\mathbb{R}$ is associated with the local private data in the $k$-th client, and is thus unknown to the server and the other clients. Here, we assume that less than half of the clients are Byzantine (i.e., $f<\frac{n}{2}$) since this problem has been proved intractable otherwise (Liu et al., 2021).

Federated Robust Averaging (FedRo) Algorithm: The Federated Robust Averaging (FedRo) algorithm (as shown in Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1)) is commonly used to solve the federated learning problem ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) with Byzantine clients (Li et al., 2021a, 2023; Allouah et al., 2024). In each communication round, every client downloads the model $w_{t}$ from the server. Then every honest client $k\in\mathcal{H}$ performs local gradient descent updates ([2](https://arxiv.org/html/2510.04432v1#S2.E2)) $H$ times on its local loss function $\ell_{k}$, while the Byzantine clients can upload arbitrary vectors to interfere with the learning. At the end of each round, the server updates its global parameter by aggregating the uploaded vectors. Since the server does not know which clients are Byzantine, the selection of the aggregator $\mathcal{A}:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}$ is essential to ensure the updated global model is robust to the Byzantine attacks. When selecting the averaging aggregator $\mathcal{A}(\{x_{k}\}_{k=1}^{n})=\frac{1}{n}\sum_{k=1}^{n}x_{k}$, the FedRo algorithm reduces to the popular federated averaging (FedAvg) algorithm (McMahan et al., 2017; Li et al., 2020; Collins et al., 2022) which is vulnerable to Byzantine clients.

Figure: Algorithm 1 FedRo: Federated Robust Averaging Algorithm

### 3 Aggregation Error Analysis

The aggregator $\mathcal{A}$ is the core of the robust federated learning algorithms such as FedRo (Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1)), so it is essential to select a proper aggregator with certain robustness properties to Byzantine clients. Multiple robustness metrics have been proposed. This work will focus on the following $(f,\kappa)$-robustness (Allouah et al., 2023) which unifies the other robustness metrics including $(f,\lambda)$-resilient averaging (Farhadkhani et al., 2022) and $(\delta_{\max},c)$-ARAgg (Karimireddy et al., 2022).

###### Definition 1 ( $(f,\kappa)$ -robust aggregator) .

For any $\kappa\geq 0$ and integer $0\leq f<\frac{n}{2}$, an aggregator $\mathcal{A}:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}$ is called $(f,\kappa)$-robust if for any $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$ and any $S\subset[n]\overset{\rm def}{=}\{1,2,\ldots,n\}$ with size $|S|=n-f$, we have

$$ $\displaystyle\|\mathcal{A}(\{x_{k}\}_{k=1}^{n})-\overline{x}_{S}\|^{2}\leq\frac{\kappa}{|S|}\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2}$ (4) $$

where $\overline{x}_{S}=\frac{1}{|S|}\sum_{i\in S}x_{i}$, and $\|\mathcal{A}(\{x_{k}\}_{k=1}^{n})-\overline{x}_{S}\|^{2}$ is called the aggregation error.

Since the server does not know which clients are Byzantine, the aggregation error bound ([4](https://arxiv.org/html/2510.04432v1#S3.E4)) should hold for any set $S$ after removing $f$ possibly Byzantine clients. Therefore, an $(f,\kappa)$-robust aggregator can resist $f$ Byzantine clients with robustness coefficient $\kappa$. Some commonly used aggregators have been proved $(f,\kappa)$-robust, such as geometric median (GM), coordinate-wise trimmed mean (CWTM), coordinate-wise median (CWMed), Krum, etc. (Allouah et al., 2023), as shown in the first row of Table [1](https://arxiv.org/html/2510.04432v1#S3.T1). Ideally, one can apply an $(f,\kappa)$-robust aggregator when there are actually $f$ Byzantine clients. However, $f$ is usually unknown in practice, so we can only use its estimation $\hat{f}$ and apply an $(\hat{f},\hat{\kappa})$ ($\hat{\kappa}>0$) aggregator. This section will analyze the aggregation error of an $(\hat{f},\hat{\kappa})$-robust aggregator when there are actually $f$ Byzantine clients, for both underestimation ($\hat{f}<f$) and non-underestimation ($\hat{f}\geq f$). To our knowledge, the existing literature has only studied a small number of special cases, including $f=\hat{f}$ (exact estimation) (Allouah et al., 2023) and $f=0$ (no Byzantine clients) (Yang et al., 2025) as shown in the first two rows of Table [1](https://arxiv.org/html/2510.04432v1#S3.T1). Throughout this work, we always assume that $\hat{f},f\in\big[0,\frac{n}{2}\big)$ to ensure tractability.

**Table 1: The value of $\kappa$ for $(\hat{f},\hat{\kappa})$-robust aggregator that is also $(f,\kappa)$-robust. We use the names $\hat{f}$-Krum, $\hat{f}$-NNM and $TM_{\hat{f}/n}$ to stress their dependence on the parameter $\hat{f}$ for clarity, while geometric median (GM) and coordinate-wise median (CWMed) do not depend on $\hat{f}$. The composite aggregator $\hat{f}$-Krum$\circ$$\hat{f}$-NNM is defined by Definition [3](https://arxiv.org/html/2510.04432v1#Thmdefinition3) with $\mathcal{A}=\hat{f}$-Krum.**
| $f$ | GM | CWTM $TM_{\hat{f}/n}$ | CWMed | $\hat{f}$-Krum | $\hat{f}$-Krum$\circ$$\hat{f}$-NNM | Lower bound |
| --- | --- | --- | --- | --- | --- | --- |
| $f=\hat{f}$ (Allouah et al., 2023) | $4\big(\frac{n-\hat{f}}{n-2\hat{f}}\big)^{2}$ | $\frac{6\hat{f}}{n-2\hat{f}}\big(\frac{n-\hat{f}}{n-2\hat{f}}\big)$ | $4\big(\frac{n-\hat{f}}{n-2\hat{f}}\big)^{2}$ | $6\big(\frac{n-\hat{f}}{n-2\hat{f}}\big)$ | - | $\frac{\hat{f}}{n-2\hat{f}}$ |
| $f=0$ (Yang et al., 2025) | $1$ | $\frac{\hat{f}}{n-\hat{f}}$ | $\frac{\lfloor\frac{n-1}{2}\rfloor}{n-\lfloor\frac{n-1}{2}\rfloor}$ | - | - | $\frac{\hat{f}}{n-\hat{f}}$ |
| $f\leq\hat{f}$ (Theorem [2](https://arxiv.org/html/2510.04432v1#Thmthm2)) | - | - | - | - | $\frac{84\hat{f}}{n-f-\hat{f}}$ | $\frac{\hat{f}}{n-f-\hat{f}}$ |

###### Definition 1 ( ( f , κ ) (f,\kappa) -robust aggregator) .

#### 3.1 Aggregation Error for Underestimation ( f ^ < f \hat{f}<f )

###### Theorem 1 .

For any $\hat{f}\in\big(0,\frac{n}{2}\big)$ and $\hat{\kappa}>0$, there exists an $(\hat{f},\hat{\kappa})$-robust aggregator that is not $(f,\kappa)$-robust for any $f\in\big(\hat{f},\frac{n}{2}\big)$ and $\kappa>0$.

Remark: Theorem [1](https://arxiv.org/html/2510.04432v1#Thmthm1) indicates that an $(\hat{f},\hat{\kappa})$-robust aggregator does not necessarily tolerate more than $\hat{f}$ Byzantine clients. Therefore, if we underestimate the number $f$ of Byzantine clients, the aggregator can have arbitrarily inaccurate performance.

A typical example of such an aggregator satisfying Theorem [1](https://arxiv.org/html/2510.04432v1#Thmthm1) is the commonly used coordinate-wise trimmed mean (CWTM) aggregator (Yin et al., 2018; Allouah et al., 2023; Yang et al., 2025), as defined below.

###### Definition 2 .

For any $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$, the CWTM aggregator denoted as $TM_{\hat{f}/n}:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}$ is defined as follows

$$ $\displaystyle[TM_{\hat{f}/n}(x_{1},\ldots,x_{n})]_{j}=\frac{1}{n-2\hat{f}}\sum_{x\in\mathcal{X}_{j}}x,$ (5) $$

where $[v]_{j}$ denotes the $j$-th coordinate of a vector $v$, and the set $\mathcal{X}_{j}$ is obtained by deleting the $\hat{f}$ smallest and $\hat{f}$ largest values from $\{[x_{i}]_{j}\}_{i=1}^{n}$.

In other words, $TM_{\hat{f}/n}$ averages the remaining $n-2\hat{f}$ samples of each coordinate after removing the $\hat{f}$ largest and $\hat{f}$ smallest samples. $TM_{\hat{f}/n}$ has been proved to be an $(\hat{f},\hat{\kappa})$-robust aggregator (see Proposition 2 of Allouah et al. (2023)) with $\hat{\kappa}=\frac{6\hat{f}}{n-2\hat{f}}\big(1+\frac{\hat{f}}{n-2\hat{f}}\big)$. However, if there are $f$ ($f>\hat{f}$) extremely large (or small) $x_{i}$ given by Byzantine clients, then after removing $\hat{f}$ largest (smallest) elements, the remaining extreme values can still heavily affect the average ([5](https://arxiv.org/html/2510.04432v1#S3.E5)). This intuition motivates the counter example for proving Theorem [1](https://arxiv.org/html/2510.04432v1#Thmthm1) in Appendix [A](https://arxiv.org/html/2510.04432v1#A1).

###### Theorem 1 .

###### Definition 2 .

#### 3.2 Aggregation Error for Non-underestimation ( f ^ ≥ f \hat{f}\geq f )

When the estimated number $\hat{f}$ of Byzantine clients is not less than the true number $f$, any $(\hat{f},\hat{\kappa})$-robust aggregator satisfies the following important properties.

###### Theorem 2 .

For any $0\leq f\leq\hat{f}<\frac{n}{2}$, an $(\hat{f},\hat{\kappa})$-robust aggregator $\mathcal{A}$ satisfies:

- 1.
$\mathcal{A}$ is always $(f,\kappa)$-robust with $\kappa=\hat{\kappa}$.
- 2.
If $\mathcal{A}$ is $(f,\kappa)$-robust, then $\kappa\geq\frac{\hat{f}}{n-f-\hat{f}}$.
- 3.
Furthermore, there exists such an $\mathcal{A}$ that is $(f,\kappa)$-robust with $\kappa\leq\frac{84\hat{f}}{n-f-\hat{f}}$.

Remark: In Theorem [2](https://arxiv.org/html/2510.04432v1#Thmthm2), Item [1](https://arxiv.org/html/2510.04432v1#S3.I1.i1) shows that an $(\hat{f},\hat{\kappa})$-robust aggregator is able to tackle any problem with fewer Byzantine clients $f\leq\hat{f}$. However, the robust coefficient $\kappa$ has a lower bound $\frac{\hat{f}}{n-f-\hat{f}}$ by Item [2](https://arxiv.org/html/2510.04432v1#S3.I1.i2), which reduces to the existing lower bound $\frac{\hat{f}}{n-2f}$ when $f=\hat{f}$ (Allouah et al., 2023) and to $\frac{\hat{f}}{n-2\hat{f}}$ when $f=0$ (Yang et al., 2025). This lower bound $\frac{\hat{f}}{n-f-\hat{f}}$ is order-optimal since a certain $(\hat{f},\hat{\kappa})$-robust aggregator can achieve the order-matching upper bound $\kappa\leq\mathcal{O}\big(\frac{\hat{f}}{n-f-\hat{f}}\big)$ by Item [3](https://arxiv.org/html/2510.04432v1#S3.I1.i3). Note that as $\hat{f}$ increases from $f$, this order-optimal bound $\mathcal{O}\big(\frac{\hat{f}}{n-f-\hat{f}}\big)$ is increasing, which yields a larger aggregation error.

###### Theorem 2 .

#### 3.3 Proof Sketch for Item 3 of Theorem 2

Item [3](https://arxiv.org/html/2510.04432v1#S3.I1.i3) is the most challenging to prove in Theorem [2](https://arxiv.org/html/2510.04432v1#Thmthm2). One challenge is to find out such a proper aggregator with order-matching lower bound $\kappa\leq\mathcal{O}\big(\frac{\hat{f}}{n-f-\hat{f}}\big)$ under $f$ Byzantine clients, partially since $\kappa$ of the commonly used aggregators like GM, CWTM, CWMed and Krum do not match the lower bound even in the simple special case of $f=\hat{f}$, as shown in the first row of Table [1](https://arxiv.org/html/2510.04432v1#S3.T1). To improve $\kappa$ of these aggregators, we will composite them with the nearest neighbor mixing (NNM) proposed by (Allouah et al., 2023), an aggregator booster defined as follows.

###### Definition 3 .

For any $\hat{f}\in\big[0,\frac{n}{2}\big)$, $k\in[n]$ and $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$, denote $\mathcal{N}_{k}\subset[n]$ as the set of $(n-\hat{f})$ indexes from $[n]$ such that $\{x_{i}\}_{i\in\mathcal{N}_{k}}$ are the $(n-\hat{f})$ nearest neighbors of $x_{k}$. In other words, $\max_{i\in\mathcal{N}_{k}}\|x_{i}-x_{k}\|\leq\min_{j\in[n]\backslash\mathcal{N}_{k}}\|x_{j}-x_{k}\|$. The mapping $\hat{f}$-NNM: $(\mathbb{R}^{d})^{n}\to(\mathbb{R}^{d})^{n}$ is defined as follows.

$$ $\displaystyle\hat{f}\mathchar 45\relax{\rm NNM}(x_{1},\ldots,x_{n})=(y_{1},\ldots,y_{n}),{\rm~where~}y_{k}=\frac{1}{n-\hat{f}}\sum_{i\in\mathcal{N}_{k}}x_{i}.$ (6) $$

For any aggregator $\mathcal{A}:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}$, define the composite aggregator $(\mathcal{A}\circ\hat{f}\mathchar 45\relax{\rm NNM})(x_{1},\ldots,x_{n})=\mathcal{A}(y_{1},\ldots,y_{n})$, with the notations in Eq. ([6](https://arxiv.org/html/2510.04432v1#S3.E6)).

Lemma 1 of (Allouah et al., 2023) has proved that for any $(\hat{f},\hat{\kappa})$-robust aggregator $\mathcal{A}$, the composite aggregator $\mathcal{A}\circ\hat{f}\mathchar 45\relax{\rm NNM}$ is $(\hat{f},\kappa^{\prime})$-robust with improved robustness coefficient $\kappa^{\prime}\leq\frac{8\hat{f}(\hat{\kappa}+1)}{n-\hat{f}}$. Selecting $\mathcal{A}=\hat{f}$-Krum which is $(\hat{f},\hat{\kappa})$-robust with $\hat{\kappa}=6\big(\frac{n-\hat{f}}{n-2\hat{f}}\big)$, the composite aggregator has $\kappa^{\prime}\leq\frac{56\hat{f}}{n-2\hat{f}}$, which matches the lower bound $\frac{\hat{f}}{n-2\hat{f}}$ when $f=\hat{f}$ (see the first row of Table [1](https://arxiv.org/html/2510.04432v1#S3.T1)). Therefore, it is natural to consider boosting $\hat{f}$-Krum with NNM. We extend the boosting property of NNM to the case of $f\leq\hat{f}$ as follows, which preserves the order of $\kappa^{\prime}\leq\frac{8\hat{f}(\hat{\kappa}+1)}{n-\hat{f}}$ in (Allouah et al., 2023) when $f=\hat{f}$.

###### Lemma 1 .

For any $0\leq f\leq\hat{f}<\frac{n}{2}$ and any $(f,\kappa)$-robust aggregator $\mathcal{A}$, the composition $\mathcal{A}\circ(\hat{f}\mathchar 45\relax{\rm NNM})$ is an $(f,\kappa^{\prime})$-robust aggregator with $\kappa^{\prime}\leq\frac{12\hat{f}(\kappa+1)}{n-f}$.

We will prove Lemma [1](https://arxiv.org/html/2510.04432v1#Thmlemma1) in Appendix [B.4](https://arxiv.org/html/2510.04432v1#A2.SS4).

Then we investigate the following $\hat{f}$-Krum aggregator (Blanchard et al., 2017; Allouah et al., 2023; Yang et al., 2025).

###### Definition 4 .

The $\hat{f}$-Krum aggregator is defined as the following mapping $(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}$.

$$ $\displaystyle(\hat{f}\mathchar 45\relax{\rm Krum})(x_{1},\ldots,x_{n})=x_{k^{*}},{\rm where~}k^{*}=\mathop{\arg\min}_{k\in[n]}\sum_{i\in\mathcal{N}_{k}}\|x_{i}-x_{k}\|,$ (7) $$

where $\mathcal{N}_{k}\subset[n]$ is the set of $(n-\hat{f})$ indexes from $[n]$ such that $\{x_{i}\}_{i\in\mathcal{N}_{k}}$ are the $(n-\hat{f})$ nearest neighbors of $x_{k}$. In other words, $\max_{i\in\mathcal{N}_{k}}\|x_{i}-x_{k}\|\leq\min_{j\in[n]\backslash\mathcal{N}_{k}}\|x_{j}-x_{k}\|$.

In Appendix [B.5](https://arxiv.org/html/2510.04432v1#A2.SS5), we will prove the following property of $\hat{f}$-Krum aggregator when applying to the scenario with $f$ Byzantine clients, which exactly reduces to $\kappa=\frac{6(n-\hat{f})}{n-2\hat{f}}$ obtained in Proposition 3 of (Allouah et al., 2023) when $f=\hat{f}$.

###### Lemma 2 .

For any $0\leq f\leq\hat{f}<\frac{n}{2}$, $\hat{f}$-Krum is an $(f,\kappa)$-robust aggregator with $\kappa=\frac{6(n-f)}{n-f-\hat{f}}$.

Based on Lemmas [1](https://arxiv.org/html/2510.04432v1#Thmlemma1) and [2](https://arxiv.org/html/2510.04432v1#Thmlemma2), for any $0\leq f\leq\hat{f}<\frac{n}{2}$, $(\hat{f}\mathchar 45\relax{\rm Krum})\circ(\hat{f}\mathchar 45\relax{\rm NNM})$ is an $(f,\kappa)$-robust aggregator with

$$ $\kappa=\frac{12\hat{f}}{n-f}\Big(\frac{6(n-f)}{n-f-\hat{f}}+1\Big)\leq\frac{12\hat{f}}{n-f}\cdot\Big(\frac{6(n-f)}{n-f-\hat{f}}+\frac{n-f}{n-f-\hat{f}}\Big)=\frac{84\hat{f}}{n-f-\hat{f}}.$ $$

This concludes the proof.

###### Definition 3 .

###### Lemma 1 .

###### Definition 4 .

###### Lemma 2 .

#### 3.4 Summary: Trade-off in Estimating f f for Aggregators

We have analyzed the aggregation error in this section when applying $(\hat{f},\hat{\kappa})$-robust aggregator to a setting with $f$ Byzantine clients. Theorem [1](https://arxiv.org/html/2510.04432v1#Thmthm1) shows we should by no means underestimate the number of Byzantine clients (i.e. $\hat{f}<f$) since that can lead to arbitrarily poor performance. While Theorem [2](https://arxiv.org/html/2510.04432v1#Thmthm2) shows that non-underestimation ($\hat{f}\geq f$) can tackle this problem, the order-optimal lower bound of robustness coefficient $\kappa\geq\frac{\hat{f}}{n-f-\hat{f}}$ increases (i.e., increased aggregation error) as $\hat{f}$ increases. Therefore, it is recommended to reduce the overestimation amount $\hat{f}-f\geq 0$ as much as possible, and the exact estimation $\hat{f}=f$ yields the optimal performance. This indicates a fundamental trade-off in estimating $f$, while a highly robust aggregator with larger $\hat{f}$ can tackle a wider range of settings for any $f\leq\hat{f}$, the aggregation error is also larger for any fixed $f$. The next section will prove a similar order-optimal bound and trade-off on federated learning.

### 4 Convergence Analysis

To analyze the convergence of Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1), we adopt the following standard assumptions on the federated optimization problem ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) below.

###### Assumption 1 (Loss bound) .

The objective function ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) admits a finite minimum value denoted as $\ell^{*}\overset{\rm def}{=}\inf_{w\in\mathbb{R}^{d}}\ell_{\mathcal{H}}(w)\in\mathbb{R}$.

###### Assumption 2 (Smoothness) .

Each individual function $\ell_{k}$ is $L$-smooth for some $L>0$, that is, for any $w,w^{\prime}\in\mathbb{R}^{d}$, we have $\|\nabla\ell_{k}(w^{\prime})-\nabla\ell_{k}(w)\|\leq L\|w^{\prime}-w\|$.

###### Assumption 3 (Heterogeneity bound) .

There exists a constant $G>0$ such that

$$ $\displaystyle\frac{1}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\|\nabla\ell_{k}(w)-\nabla\ell_{\mathcal{H}}(w)\|^{2}\leq G^{2}.$ (8) $$

###### Assumption 4 (Polyak-Łojasiewicz (PŁ) condition) .

There exists a constant $\mu>0$ such that $\ell_{\mathcal{H}}$ is $\mu$-PL gradient dominant, that is, $\ell_{\mathcal{H}}(w)-\ell^{*}\leq\frac{1}{2\mu}\|\nabla\ell_{\mathcal{H}}(w)\|^{2}$ for any $w\in\mathbb{R}^{d}$.

Assumptions [1](https://arxiv.org/html/2510.04432v1#Thmassum1)-[3](https://arxiv.org/html/2510.04432v1#Thmassum3) are popular in distributed and federated learning (Allouah et al., 2023; Errami & Bergou, 2024; Allouah et al., 2024; Yang et al., 2025; Otsuka et al., 2025). In particular, a larger $G^{2}$ in Assumption [3](https://arxiv.org/html/2510.04432v1#Thmassum3) means the honest clients have more heterogeneous data, which makes the federated optimization problem ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) more challenging. The notion of PŁcondition (Assumption [4](https://arxiv.org/html/2510.04432v1#Thmassum4)) proposed by (Polyak, 1963) is widely used in nonconvex optimization to guarantee global convergence (Karimi et al., 2016; Chakrabarti & Baranwal, 2024; Yang et al., 2025). With these assumptions, we will analyze the convergence rate of Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with an $(\hat{f},\hat{\kappa})$-robust aggregator on federated learning with $f$ Byzantine clients. We will discuss in two cases, underestimation ($\hat{f}<f$) and non-underestimation ($\hat{f}\geq f$).

###### Assumption 1 (Loss bound) .

###### Assumption 2 (Smoothness) .

###### Assumption 3 (Heterogeneity bound) .

###### Assumption 4 (Polyak-Łojasiewicz (PŁ) condition) .

#### 4.1 Divergence For Underestimation ( f ^ < f \hat{f}<f )

###### Theorem 3 .

For any $0\leq\hat{f}<f<\frac{n}{2}$, there exist an $(\hat{f},\hat{\kappa})$-robust aggregator $\mathcal{A}$, a set $\mathcal{H}\subset[n]$ with size $|\mathcal{H}|=n-f$, Byzantine clients’ strategies and loss functions $\{\ell_{i}\}_{i\in\mathcal{H}}$ satisfying Assumptions [1](https://arxiv.org/html/2510.04432v1#Thmassum1)-[4](https://arxiv.org/html/2510.04432v1#Thmassum4) such that when implementing Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with the aggregator $\mathcal{A}$, any initialization $w_{0}$ and constant stepsize $\gamma_{t}=\gamma>0$, the generated sequence $w_{t}$ diverges as follows as $T\to+\infty$.

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\to+\infty$ (9) $$

$$ $\displaystyle\ell_{\mathcal{H}}(w_{T})-\ell^{*}\to+\infty$ (10) $$

Remark: Theorem [3](https://arxiv.org/html/2510.04432v1#Thmthm3) indicates that if the aggregator is only robust to $\hat{f}$ Byzantine clients that is fewer than the actual number $f$ of Byzantine clients, then Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with any initialization and stepsize can diverge in some federated learning problems. Therefore, we should always guarantee the non-underestimation condition that $\hat{f}\geq f$.

###### Theorem 3 .

#### 4.2 Convergence Rate For Non-underestimation ( f ^ ≥ f \hat{f}\geq f )

###### Theorem 4 .

For any $0\leq f\leq\hat{f}<\frac{n}{2}$ and any $(\hat{f},\hat{\kappa})$-robust aggregator $\mathcal{A}$, there exist $\mathcal{H}\subset[n]$ with size $|\mathcal{H}|=n-f$, Byzantine clients’ strategies and loss functions $\{\ell_{i}\}_{i\in\mathcal{H}}$ satisfying Assumptions [1](https://arxiv.org/html/2510.04432v1#Thmassum1)-[4](https://arxiv.org/html/2510.04432v1#Thmassum4) such that for any initialization $w_{0}$ and constant stepsize $\gamma_{t}=\gamma>0$, the sequence $w_{t}$ generated from Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with aggregator $\mathcal{A}$ either does not change over iteration (i.e., $w_{t}\equiv w_{0}$) or satisfies the following convergence lower bounds.

$$ $\displaystyle\mathop{\lim\sup}_{T\to\infty}\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\geq\frac{\hat{f}G^{2}}{n-f-\hat{f}}$ (11) $$

$$ $\displaystyle\mathop{\lim\sup}_{T\to\infty}\ell_{\mathcal{H}}(w_{T})-\ell^{*}\geq\frac{\hat{f}G^{2}}{2\mu(n-f-\hat{f})}$ (12) $$

Remark: In most cases, the heterogeneity $G^{2}>0$. Then regardless of the hyperparameter choices, Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with an $(\hat{f},\hat{\kappa})$-robust aggregator cannot converge to a stationary or optimal point of some objective functions, since the convergence metric of gradients and function value are lower bounded by $\frac{\hat{f}G^{2}}{n-f-\hat{f}}>0$ and $\frac{\hat{f}G^{2}}{2\mu(n-f-\hat{f})}>0$ respectively as shown above. These lower bounds increase as $\hat{f}$ increases from $f$. Later, we will show that these lower bounds are tight since their orders match the upper bounds in the upcoming Theorem [5](https://arxiv.org/html/2510.04432v1#Thmthm5).

Proof Sketch of Theorem [4](https://arxiv.org/html/2510.04432v1#Thmthm4): Select the following loss functions with scalar input $w\in\mathbb{R}$, which can be verified to satisfy Assumptions [1](https://arxiv.org/html/2510.04432v1#Thmassum1)-[4](https://arxiv.org/html/2510.04432v1#Thmassum4).

$$ $\displaystyle\ell_{k}(w)=\left\{\begin{aligned} &cG(w+1)^{2},k=1,2,\ldots,\hat{f}\\ &cGw^{2},k=\hat{f}+1,\hat{f}+2,\ldots,n\end{aligned}\right.,$ (13) $$

where $c=\frac{n-f}{2\sqrt{\hat{f}(n-f-\hat{f})}}$. Suppose $\mathcal{H}=[n-f]=\{1,2,\ldots,n-f\}$ and the Byzantine clients adopt the same honest behavior as the honest clients, i.e., upload the result after $H$ local gradient descent updates ([2](https://arxiv.org/html/2510.04432v1#S2.E2)). Then the global model updates as follows.

$$ $w_{t+1}=\Gamma^{H}w_{t},~{\rm where}~\Gamma=1-2cG\gamma.$ $$

Then we can prove Theorem [4](https://arxiv.org/html/2510.04432v1#Thmthm4) in four cases of the hyperparameters $\gamma$ and $H$ that respectively satisfy $|\Gamma^{H}|<1$, $\Gamma^{H}=1$, $\Gamma^{H}=-1$ and $|\Gamma^{H}|>1$. See the whole proof in Appendix [D](https://arxiv.org/html/2510.04432v1#A4).

###### Theorem 5 (Upper bound) .

Suppose Assumptions [1](https://arxiv.org/html/2510.04432v1#Thmassum1)-[3](https://arxiv.org/html/2510.04432v1#Thmassum3) hold. Apply Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with an $(f,\kappa)$-aggregator and stepsize $\gamma=\frac{1}{c^{\prime}LHT^{1/3}}$ ($c^{\prime}=\max(4\sqrt{2},\sqrt{384\kappa})$) to the federated optimization problem ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) with $f$ Byzantine clients. The algorithm output $\{w_{t}\}_{t=0}^{T-1}$ satisfies the following convergence rate.

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\leq$ $\displaystyle\frac{16c^{\prime}LH[\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+G^{2}}{T^{2/3}}+90\kappa G^{2}.$ (14) $$

Furthermore, under Assumption [4](https://arxiv.org/html/2510.04432v1#Thmassum4) (i.e., $\ell_{\mathcal{H}}$ satisfies the PŁ condition), we can select stepsize $\gamma=\frac{1}{c^{\prime}LHT^{1-\beta}}$ for any $\beta\in(0,1)$ which yields the following convergence rate.

$$ $\displaystyle\ell_{\mathcal{H}}(w_{T})-\ell^{*}\leq$ $\displaystyle\exp\Big(-\frac{\mu T^{\beta}}{8c^{\prime}L}\Big)[\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+\frac{G^{2}}{2\mu T^{2-2\beta}}+\frac{45\kappa G^{2}}{\mu}.$ (15) $$

Remark: As $T\to+\infty$, the upper bounds above respectively converge to $90\kappa G^{2}$ and $\frac{45\kappa G^{2}}{\mu}$. Moreover, if Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) uses an $(\hat{f},\hat{\kappa})$-robust aggregator with $\hat{f}\geq f$, which is also $(f,\kappa)$-robust that can achieve the order-optimal upper bound $\kappa\leq\mathcal{O}\big(\frac{\hat{f}}{n-f-\hat{f}}\big)$ by Theorem [2](https://arxiv.org/html/2510.04432v1#Thmthm2), then the upper bounds ([14](https://arxiv.org/html/2510.04432v1#S4.E14)) and ([15](https://arxiv.org/html/2510.04432v1#S4.E15)) respectively converge to $\mathcal{O}\big(\frac{\hat{f}G^{2}}{n-f-\hat{f}}\big)$ and $\mathcal{O}\big(\frac{\hat{f}G^{2}}{\mu(n-f-\hat{f})}\big)$, which are tight since they match the orders of the lower bounds in Theorem [4](https://arxiv.org/html/2510.04432v1#Thmthm4).

###### Theorem 4 .

###### Theorem 5 (Upper bound) .

#### 4.3 Summary: Trade-off in Estimating f f for Federated Learning

We have analyzed the convergence of Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with an $(\hat{f},\hat{\kappa})$-robust aggregator on federated learning with $f$ Byzantine clients. Theorem [3](https://arxiv.org/html/2510.04432v1#Thmthm3) indicates that we should always avoid underestimation ($\hat{f}<f$) as that can lead to divergence. When $\hat{f}\geq f$, Theorem [4](https://arxiv.org/html/2510.04432v1#Thmthm4) provides convergence lower bounds that match the orders of the upper bounds in Theorem [5](https://arxiv.org/html/2510.04432v1#Thmthm5). These results are analogous to those for the robustness coefficient $\kappa$ of the aggregator analyzed in Section [3](https://arxiv.org/html/2510.04432v1#S3). We summarize all these main theoretical results in Table [2](https://arxiv.org/html/2510.04432v1#S4.T2), which shows that the order-optimal bounds for both $\kappa$ and the two federated learning convergence metrics are proportional to $\frac{\hat{f}}{n-f-\hat{f}}$ which increases as $\hat{f}$ increases from $f$. Therefore, there is a fundamental trade-off in estimating $f$: Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) with aggregators robust to more Byzantine clients has degraded performance in terms of both aggregation error and algorithm convergence, when there are actually not that many Byzantine clients.

**Table 2: Summary of our main theoretical results. As we apply an $(\hat{f},\hat{\kappa})$-robust aggregator to federated learning with $f$ Byzantine clients, we show three performance metrics: robust coefficient $\kappa$ of the aggregator (also $(f,\kappa)$-robust) and the two convergence metrics for Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1), under Assumptions [1](https://arxiv.org/html/2510.04432v1#Thmassum1)-[4](https://arxiv.org/html/2510.04432v1#Thmassum4). These metrics can be arbitrarily poor when $\hat{f}<f$, and have the following lower bounds that match the order of the corresponding upper bounds when $\hat{f}\geq f$.**
|  | $\kappa$ | $\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}$ | $\ell_{\mathcal{H}}(w_{T})-\ell^{*}$ |
| --- | --- | --- | --- |
| Underestimation | Possibly non-exist | Possibly $\to+\infty$ | Possibly $\to+\infty$ |
| ($\hat{f}<f$) | (Theorem [1](https://arxiv.org/html/2510.04432v1#Thmthm1)) | (Theorem [3](https://arxiv.org/html/2510.04432v1#Thmthm3)) | (Theorem [3](https://arxiv.org/html/2510.04432v1#Thmthm3)) |
| Non-underestimation | $\mathcal{O}\big(\frac{\hat{f}}{n-f-\hat{f}}\big)$ | $\mathcal{O}\big(\frac{\hat{f}G^{2}}{n-f-\hat{f}}\big)$ | $\mathcal{O}\big(\frac{\hat{f}G^{2}}{\mu(n-f-\hat{f})}\big)$ |
| ($\hat{f}\geq f$) | (Theorem [2](https://arxiv.org/html/2510.04432v1#Thmthm2)) | (Theorems [4](https://arxiv.org/html/2510.04432v1#Thmthm4)-[5](https://arxiv.org/html/2510.04432v1#Thmthm5)) | (Theorems [4](https://arxiv.org/html/2510.04432v1#Thmthm4)-[5](https://arxiv.org/html/2510.04432v1#Thmthm5)) |

Comparison with Related Works: Two recent works have obtained results that are similar to part of our results. Allouah et al. (2024) obtains a near-optimal convergence rate of Byzantine-robust federated learning algorithm where a random subset of $\hat{n}$ clients participate in each communication round, which relies on the effect of the estimated number $\hat{f}$(^1^11Allouah et al. (2024) uses $b$ to denote the true number of Byzantine clients and $\hat{b}$ to denote the estimation of $b$. We replace them with $f$ and $\hat{f}$ respectively.) of Byzantine clients in this subset. However, their convergence requires overestimation of the fraction of Byzantine clients, i.e., $\frac{\hat{f}}{\hat{n}}>\frac{f}{n}$, while the cases of underestimation and exact estimation are not studied. In addition, they obtain the convergence gap $\kappa G^{2}$, while the optimal lower and upper bound on $\kappa$ is not studied. Yang et al. (2025) studies distributed learning with only $H=1$ local gradient update and no Byzantine clients ($f=0$), a small special case of our setting. They found that the performance degrades with $\hat{f}$, which fits our results of non-underestimation in this special case.

### 5 Experiments

To demonstrate the aforementioned trade-off in estimating the number of Byzantine clients in federated learning, we apply the FedRo algorithm to a classification task on the CIFAR-10 dataset (Krizhevsky, 2009), using the cross-entropy loss function as the objective function and ResNet-20 (He et al., 2016) as the classifier model.

Data Assignment: CIFAR-10 consists of 10 classes and 5k training images per class. We equally divide the 50k samples into $n=16$ clients. Among the 3125 samples in each client $k$, suppose a fraction $p_{k,c}$ belongs to the $c$-th class. Randomly set $[p_{k,1},\ldots,p_{k,10}]$ from the $10$-dimensional symmetric Dirichlet distribution $\text{Dir}_{10}(\alpha)$. A smaller $\alpha$ corresponds to greater heterogeneity among the clients.

Models and Training Schemes: The batch normalization (BN) layers in ResNet-20 are replaced with group normalization (GN) layers, since BN performs poorly with heterogeneous data across clients (Wu & He, 2018). We implement the FedRo algorithm with an $\hat{f}$-CWTM aggregator on a grid of $\hat{f}\in\{0,1,\ldots,7\}$, $f\in\{0,4\}$ and $\alpha\in\{0.1,1,10\}$. For $\alpha=0.1$, we run FedRo for $T=800$ total communication rounds with $H=49$ local SGD steps per round. For $\alpha=1$ and $\alpha=10$, we run FedRo for $T=400$ total communication rounds with $H=98$ local SGD steps per round. Each SGD step uses batchsize 64, weight decay $5\times 10^{-4}$ and an step-wise diminishing stepsize (see Eq. ([46](https://arxiv.org/html/2510.04432v1#A6.E46)) in Appendix [F](https://arxiv.org/html/2510.04432v1#A6)). Each Byzantine client uploads a vector from normal distribution $\mathcal{N}(0,5)$. More details on data division, model architectures, and training schemes are provided in Appendix [F](https://arxiv.org/html/2510.04432v1#A6).

**Table 3: Top-1 Accuracies of FedRo Algorithm on CIFAR-10 Data. A smaller $\alpha$ corresponds to higher heterogeneity $G^{2}$. When $\hat{f}>f$, the accuracy drops compared with the corresponding accuracy under $\hat{f}=f$ (bolded) are marked in the parentheses.**
| $\hat{f}$ | $f=0$ | $f=4$ |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| $\alpha=0.1$ | $\alpha=1.0$ | $\alpha=10.0$ | $\alpha=0.1$ | $\alpha=1.0$ | $\alpha=10.0$ |  |
| 0 | 65.61 | 78.76 | 80.24 | 10.01 | 10.11 | 10.01 |
| 1 | 62.28(-3.33) | 77.31(-1.45) | 79.45(-0.79) | 12.85 | 10.04 | 10.00 |
| 2 | 53.01(-12.60) | 77.13(-1.63) | 79.63(-0.61) | 9.17 | 10.00 | 9.85 |
| 3 | 51.87(-13.74) | 76.76(-2.00) | 78.28(-1.96) | 11.46 | 23.98 | 25.70 |
| 4 | 48.47(-17.14) | 76.80(-1.96) | 77.93(-2.31) | 54.58 | 74.19 | 75.80 |
| 5 | 47.25(-18.36) | 76.93(-1.83) | 77.67(-2.57) | 49.83(-4.75) | 73.53(-0.66) | 75.77(-0.03) |
| 6 | 45.27(-20.34) | 75.32(-3.44) | 77.91(-2.33) | 47.65(-6.93) | 72.62(-1.57) | 74.35(-1.45) |
| 7 | 43.38(-22.23) | 75.01(-3.75) | 77.87(-2.37) | 43.69(-10.89) | 72.45(-1.74) | 74.02(-1.78) |

Main Results: Table [3](https://arxiv.org/html/2510.04432v1#S5.T3) reports the top-1 accuracies for each candidate $(\hat{f},f,\alpha)$. When $\hat{f}<f=4$ (underestimation), the accuracies are extremely low, which fits the divergence result in Theorem [3](https://arxiv.org/html/2510.04432v1#Thmthm3). When $\hat{f}\geq f$ (non-underestimation) in both no-Byzantine ($f=0$) and Byzantine ($f=4$) settings, the accuracy decreases in general as $\hat{f}$ increases from $f$. Moreover, with larger $\alpha$ (i.e. lower heterogeneity $G^{2}$), such an accuracy decrease with larger $\hat{f}$ slows down. These results fit Theorems [4](https://arxiv.org/html/2510.04432v1#Thmthm4) and [5](https://arxiv.org/html/2510.04432v1#Thmthm5) which indicate that as $\hat{f}$ increases from $f$, the tight convergence lower bound $\frac{\hat{f}G^{2}}{n-f-\hat{f}}$ increases at a rate proportional to the heterogeneity $G^{2}$.

### 6 Conclusion

To our knowledge, this is the first work that systematically investigates the theoretical effect of the estimated number of Byzantine clients on both aggregation error and federated learning performance. Both theoretical and empirical results demonstrate that while an aggregator with a larger robustness degree can tolerate more Byzantine clients, the performance can deteriorate when there are actually fewer or even no Byzantine clients.

### References

- Allouah et al. (2023)
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan.
Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity.
In *International Conference on Artificial Intelligence and Statistics (AISTATS)*, pp. 1232–1300, 2023.
- Allouah et al. (2024)
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, Geovani Rizk, and Sasha Voitovych.
Byzantine-robust federated learning: Impact of client subsampling and local updates.
In *Proceedings of International Conference on Machine Learning (ICML)*, pp. 1078–1114, 2024.
- Bagdasaryan et al. (2020)
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov.
How to backdoor federated learning.
In *International conference on artificial intelligence and statistics (AISTATS)*, pp. 2938–2948, 2020.
- Blanchard et al. (2017)
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer.
Machine learning with adversaries: byzantine tolerant gradient descent.
In *Proceedings of the International Conference on Neural Information Processing Systems (Neurips)*, pp. 118–128, 2017.
- Cao et al. (2021)
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Gong.
Fltrust: Byzantine-robust federated learning via trust bootstrapping.
In *Proceedings of Network and Distributed Systems Security (NDSS) Symposium*, 2021.
- Chakrabarti & Baranwal (2024)
Kushal Chakrabarti and Mayank Baranwal.
A methodology establishing linear convergence of adaptive gradient methods under pl inequality.
In *Proceedings of European Conference on Artificial Intelligence (ECAI)*, 2024.
- Chen et al. (2017)
Yudong Chen, Lili Su, and Jiaming Xu.
Distributed statistical machine learning in adversarial settings: Byzantine gradient descent.
*Proceedings of the ACM on Measurement and Analysis of Computing Systems*, 1(2):1–25, 2017.
- Collins et al. (2022)
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai.
Fedavg with fine tuning: local updates lead to representation learning.
In *Proceedings of the International Conference on Neural Information Processing Systems (Neurips)*, pp. 10572–10586, 2022.
- Errami & Bergou (2024)
Latifa Errami and El Houcine Bergou.
Tolerating outliers: gradient-based penalties for byzantine robustness and inclusion.
In *Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)*, pp. 3935–3943, 2024.
- Farhadkhani et al. (2022)
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan.
Byzantine machine learning made easy by resilient averaging of momentums.
In *Proceedings of International Conference on Machine Learning (ICML)*, pp. 6246–6283, 2022.
- Gupta et al. (2023)
Nirupam Gupta, Thinh T Doan, and Nitin Vaidya.
Byzantine fault-tolerance in federated local sgd under $2f$-redundancy.
*IEEE Transactions on Control of Network Systems*, 10(4):1669–1681, 2023.
- He et al. (2016)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.
Deep residual learning for image recognition.
In *2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016*, pp. 770–778. IEEE Computer Society, 2016.
doi: 10.1109/CVPR.2016.90.
URL [https://doi.org/10.1109/CVPR.2016.90](https://doi.org/10.1109/CVPR.2016.90).
- Karimi et al. (2016)
Hamed Karimi, Julie Nutini, and Mark Schmidt.
Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.
In *Joint European conference on machine learning and knowledge discovery in databases*, pp. 795–811, 2016.
- Karimireddy et al. (2021)
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi.
Learning from history for byzantine robust optimization.
In *Proceedings of International Conference on Machine Learning (ICML)*, pp. 5311–5319, 2021.
- Karimireddy et al. (2022)
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi.
Byzantine-robust learning on heterogeneous datasets via bucketing.
In *Proceedings of International Conference on Learning Representations (ICLR)*, 2022.
- Kritharakis et al. (2025)
Emmanouil Kritharakis, Antonios Makris, Dusan Jakovetic, and Konstantinos Tserpes.
Fedgreed: A byzantine-robust loss-based aggregation method for federated learning.
*ArXiv:2508.18060*, 2025.
- Krizhevsky (2009)
Alex Krizhevsky.
Learning multiple layers of features from tiny images.
Technical report, University of Toronto, 2009.
Technical Report.
- Lamport et al. (2019)
Leslie Lamport, Robert Shostak, and Marshall Pease.
The byzantine generals problem.
In *Concurrency: the works of leslie lamport*, pp. 203–226. 2019.
- Li et al. (2021a)
Shenghui Li, Edith Ngai, and Thiemo Voigt.
Byzantine-robust aggregation in federated learning empowered industrial iot.
*IEEE Transactions on Industrial Informatics*, 19(2):1165–1175, 2021a.
- Li et al. (2023)
Shenghui Li, Edith C-H Ngai, and Thiemo Voigt.
An experimental study of byzantine-robust aggregation schemes in federated learning.
*IEEE Transactions on Big Data*, 10(6):975–988, 2023.
- Li et al. (2020)
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang.
On the convergence of fedavg on non-iid data.
In *Proceedings of the International Conference on Learning Representations (ICLR)*, 2020.
- Li et al. (2021b)
Zhuohang Li, Luyang Liu, Jiaxin Zhang, and Jian Liu.
Byzantine-robust federated learning through spatial-temporal analysis of local model updates.
In *2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)*, pp. 372–379, 2021b.
- Liu et al. (2021)
Shuo Liu, Nirupam Gupta, and Nitin H Vaidya.
Approximate byzantine fault-tolerance in distributed optimization.
In *Proceedings of the ACM Symposium on Principles of Distributed Computing*, pp. 379–389, 2021.
- McMahan et al. (2017)
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.
Communication-efficient learning of deep networks from decentralized data.
In *International Conference on Artificial Intelligence and Statistics (AISTATS)*, pp. 1273–1282, 2017.
- Meng et al. (2023)
Mark Huasong Meng, Sin G Teo, Guangdong Bai, Kailong Wang, and Jin Song Dong.
Enhancing federated learning robustness using data-agnostic model pruning.
In *Pacific-Asia conference on knowledge discovery and data mining (PAKDD)*, pp. 441–453, 2023.
- Otsuka et al. (2025)
Kaoru Otsuka, Yuki Takezawa, and Makoto Yamada.
Delayed momentum aggregation: Communication-efficient byzantine-robust federated learning with partial participation.
*ArXiv:2509.02970*, 2025.
- Panda et al. (2022)
Ashwinee Panda, Saeed Mahloujifar, Arjun Nitin Bhagoji, Supriyo Chakraborty, and Prateek Mittal.
Sparsefed: Mitigating model poisoning attacks in federated learning with sparsification.
In *International Conference on Artificial Intelligence and Statistics (AISTATS)*, pp. 7587–7624, 2022.
- Park et al. (2021)
Jungwuk Park, Dong-Jun Han, Minseok Choi, and Jaekyun Moon.
Sageflow: robust federated learning against both stragglers and adversaries.
In *Proceedings of the International Conference on Neural Information Processing Systems (Neurips)*, pp. 840–851, 2021.
- Pillutla et al. (2022)
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui.
Robust aggregation for federated learning.
*IEEE Transactions on Signal Processing*, 70:1142–1154, 2022.
- Polyak (1963)
B. T. Polyak.
Gradient methods for minimizing functionals (in russian).
*Zh. Vychisl. Mat. Mat. Fiz.*, 3:643–653, 1963.
- Sattler et al. (2020)
Felix Sattler, Klaus-Robert Müller, Thomas Wiegand, and Wojciech Samek.
On the byzantine robustness of clustered federated learning.
In *ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, pp. 8861–8865, 2020.
- Tolpegin et al. (2020)
Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu.
Data poisoning attacks against federated learning systems.
In *European symposium on research in computer security*, pp. 480–501, 2020.
- Wang et al. (2020a)
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos.
Attack of the tails: yes, you really can backdoor federated learning.
In *Proceedings of the International Conference on Neural Information Processing Systems (Neurips)*, pp. 16070–16084, 2020a.
- Wang et al. (2020b)
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris S. Papailiopoulos, and Yasaman Khazaeni.
Federated learning with matched averaging.
In *8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020*. OpenReview.net, 2020b.
URL [https://openreview.net/forum?id=BkluqlSFDS](https://openreview.net/forum?id=BkluqlSFDS).
- Wu & He (2018)
Yuxin Wu and Kaiming He.
Group normalization.
In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), *Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XIII*, volume 11217 of *Lecture Notes in Computer Science*, pp. 3–19. Springer, 2018.
doi: 10.1007/978-3-030-01261-8\_1.
URL [https://doi.org/10.1007/978-3-030-01261-8_1](https://doi.org/10.1007/978-3-030-01261-8_1).
- Xie et al. (2020)
Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li.
Dba: Distributed backdoor attacks against federated learning.
In *Proceedings of the International Conference on Learning Representations (ICLR)*, 2020.
- Xie et al. (2019)
Cong Xie, Sanmi Koyejo, and Indranil Gupta.
Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance.
In *Proceedings of International Conference on Machine Learning (ICML)*, pp. 6893–6901, 2019.
- Xu et al. (2025)
Jiahao Xu, Zikai Zhang, and Rui Hu.
Achieving byzantine-resilient federated learning via layer-adaptive sparsified model aggregation.
In *2025 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)*, pp. 1508–1517, 2025.
- Yang et al. (2025)
Yi-Rui Yang, Chang-Wei Shi, and Wu-Jun Li.
On the tension between byzantine robustness and no-attack accuracy in distributed learning.
In *Proceedings of International Conference on Machine Learning (ICML)*, 2025.
- Yin et al. (2018)
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett.
Byzantine-robust distributed learning: Towards optimal statistical rates.
In *Proceedings of International Conference on Machine Learning (ICML)*, pp. 5650–5659, 2018.
- Zhang & Hu (2023)
Zikai Zhang and Rui Hu.
Byzantine-robust federated learning with variance reduction and differential privacy.
In *2023 IEEE Conference on Communications and Network Security (CNS)*, pp. 1–9, 2023.

## Appendix

### Appendix A Proof of Theorem 1

The commonly used coordinate-wise trimmed mean (CWTM) aggregator $TM_{\hat{f}/n}$ defined by Eq. ([5](https://arxiv.org/html/2510.04432v1#S3.E5)) has been proved to be an $(\hat{f},\hat{\kappa})$-robust aggregator (see Proposition 2 of Allouah et al. (2023)) with $\hat{\kappa}=\frac{6\hat{f}}{n-2\hat{f}}\big(1+\frac{\hat{f}}{n-2\hat{f}}\big)$. Hence, it remains to prove that $TM_{\hat{f}/n}$ is not $(f,\kappa)$-robust for any $\hat{f}<f<\frac{n}{2}$ and $\kappa>0$.

Select the scalars $\{x_{k}\}_{k=1}^{n}\subset\mathbb{R}$ as follows.

$$ $\displaystyle x_{1}=x_{2}=\cdots=x_{n-f}=0,x_{n-f+1}=x_{n-f+2}=\cdots=x_{n}=1.$ (16) $$

For $S=[n-f]=\{1,2,\ldots,n-f\}$ with $|S|=n-f$, we have

$$ $\displaystyle\overline{x}_{S}=\frac{1}{|S|}\sum_{k\in S}x_{k}=0,\quad\frac{1}{|S|}\sum_{k\in S}(x_{k}-\overline{x}_{S})^{2}=0.$ $$

Suppose $TM_{\hat{f}/n}$ is $(f,\kappa)$-robust for some $\kappa>0$, which implies that

$$ $\displaystyle|TM_{\hat{f}/n}(x_{1},\ldots,x_{n})-\overline{x}_{S}|\leq\kappa^{\prime}\cdot\frac{1}{|S|}\sum_{k\in S}(x_{k}-\overline{x}_{S})^{2}=0,$ (17) $$

so $TM_{\hat{f}/n}(x_{1},\ldots,x_{n})=\overline{x}_{S}=0$. This contradicts with the definition ([5](https://arxiv.org/html/2510.04432v1#S3.E5)) of $TM_{\hat{f}/n}$ which along with the scalars ([16](https://arxiv.org/html/2510.04432v1#A1.E16)) implies that

$$ $\displaystyle TM_{\hat{f}/n}(x_{1},\ldots,x_{n})=\frac{1}{n-2\hat{f}}\sum_{k=\hat{f}+1}^{n-\hat{f}}x_{k}=\frac{f-\hat{f}}{n-2\hat{f}}>0.$ (18) $$

Therefore, $TM_{\hat{f}/n}$ is not $(f,\kappa)$-robust for any $\hat{f}<f<\frac{n}{2}$ and $\kappa>0$.

### Appendix B Proof of Theorem 2

#### B.1 Proof of Item 1

The conclusion is obvious when $f=\hat{f}$, so we consider the case where $0<f<\hat{f}$.

For any set $S\subset[n]$ with size $|S|=n-f$, $S$ contains $q=\frac{(n-f)!}{(n-\hat{f})!(\hat{f}-f)!}$ subsets $S_{1},\ldots,S_{q}\subset S$ with the same size $|S_{1}|=\ldots=|S_{q}|=n-\hat{f}$. Then for any $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$ and $E\subset[n]$, denote $\overline{x}_{E}=\frac{1}{|E|}\sum_{k\in E}x_{k}$. Then, we prove that $\mathcal{A}$ is $(f,\hat{\kappa})$-robust as follows.

$$ $\displaystyle\|\mathcal{A}(x_{1},\ldots,x_{n})-\overline{x}_{S}\|^{2}$ $\displaystyle=$ $\displaystyle\Big\|\mathcal{A}(x_{1},\ldots,x_{n})-\frac{1}{q}\sum_{i=1}^{q}\overline{x}_{S_{i}}\Big\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{1}{q}\sum_{i=1}^{q}\|\mathcal{A}(x_{1},\ldots,x_{n})-\overline{x}_{S_{i}}\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{1}{q}\sum_{i=1}^{q}\frac{\hat{\kappa}}{n-\hat{f}}\sum_{k\in S_{i}}\|x_{k}-\overline{x}_{S_{i}}\|^{2}$ $\displaystyle=$ $\displaystyle\frac{\hat{\kappa}}{q(n-\hat{f})}\sum_{i=1}^{q}\sum_{k\in S_{i}}\|(x_{k}-\overline{x}_{S})-(\overline{x}_{S_{i}}-\overline{x}_{S})\|^{2}$ $\displaystyle=$ $\displaystyle\frac{\hat{\kappa}}{q(n-\hat{f})}\sum_{i=1}^{q}\sum_{k\in S_{i}}\big[\|x_{k}-\overline{x}_{S}\|^{2}+\|\overline{x}_{S_{i}}-\overline{x}_{S}\|^{2}-2\langle x_{k}-\overline{x}_{S},\overline{x}_{S_{i}}-\overline{x}_{S}\rangle\big]$ $\displaystyle=$ $\displaystyle\frac{\hat{\kappa}}{q(n-\hat{f})}\sum_{i=1}^{q}\sum_{k\in S_{i}}\big[\|x_{k}-\overline{x}_{S}\|^{2}\big]+\frac{\hat{\kappa}}{q}\sum_{i=1}^{q}\big[\|\overline{x}_{S_{i}}-\overline{x}_{S}\|^{2}\big]$ $\displaystyle-\frac{2\hat{\kappa}}{q(n-\hat{f})}\sum_{i=1}^{q}\langle|S_{i}|\overline{x}_{S_{i}}-|S_{i}|\overline{x}_{S},\overline{x}_{S_{i}}-\overline{x}_{S}\rangle$ $\displaystyle\overset{(c)}{=}$ $\displaystyle\frac{\hat{\kappa}(n-\hat{f})!(\hat{f}-f)!}{(n-\hat{f})(n-f)!}\frac{(n-f-1)!}{(n-\hat{f}-1)!(\hat{f}-f)!}\sum_{k\in S}\big[\|x_{k}-\overline{x}_{S}\|^{2}\big]+\frac{\hat{\kappa}}{q}\sum_{i=1}^{q}\big[\|\overline{x}_{S_{i}}-\overline{x}_{S}\|^{2}\big]$ $\displaystyle-\frac{2\hat{\kappa}}{q}\sum_{i=1}^{q}\big[\|\overline{x}_{S_{i}}-\overline{x}_{S}\|^{2}\big]$ $\displaystyle\leq$ $\displaystyle\frac{\hat{\kappa}}{n-f}\sum_{k\in S}\big[\|x_{k}-\overline{x}_{S}\|^{2}\big].$ $$

where (a) applies Jensen’s inequality to the convex function $\|\cdot\|^{2}$, (b) applies the $(\hat{f},\hat{\kappa})$-robust aggregator $\mathcal{A}$ to the set $S_{i}$ of size $|S_{i}|=n-\hat{f}$, (c) uses $q=\frac{(n-f)!}{(n-\hat{f})!(\hat{f}-f)!}$ and the fact that each $k\in S$ is contained by $\frac{(n-f-1)!}{(n-\hat{f}-1)!(\hat{f}-f)!}$ sets of $\{S_{i}\}_{i=1}^{q}$ (since these sets for a certain $k\in S$ can be obtained by removing $(\hat{f}-f)$ elements from $S\backslash\{k\}$ with size $|S\backslash\{k\}|=n-f-1$).

#### B.2 Proof of Item 2

Suppose an aggregator $\mathcal{A}:(\mathbb{R}^{d})^{n}\to\mathbb{R}^{d}$ is $(\hat{f},\hat{\kappa})$-robust and $(f,\kappa)$-robust. Select the scalars $\{x_{k}\}_{k=1}^{n}\subset\mathbb{R}$ as follows.

$$ $\displaystyle x_{1}=x_{2}=\ldots=x_{n-\hat{f}}=0,x_{n-\hat{f}+1}=\ldots=x_{n}=1.$ (19) $$

Since $\mathcal{A}$ is $(\hat{f},\hat{\kappa})$-robust, for $S^{\prime}=[n-\hat{f}]=\{1,2,\ldots,n-\hat{f}\}$ we have

$$ $\displaystyle\overline{x}_{S^{\prime}}=$ $\displaystyle\frac{1}{|S^{\prime}|}\sum_{k\in S^{\prime}}x_{k}=0,\quad|\mathcal{A}(x_{1},\ldots,x_{n})-\overline{x}_{S^{\prime}}|^{2}\leq\frac{\kappa}{|S^{\prime}|}\sum_{k\in S^{\prime}}|x_{k}-\overline{x}_{S^{\prime}}|^{2}=0,$ $$

so $\mathcal{A}(x_{1},\ldots,x_{n})=\overline{x}_{S^{\prime}}=0$.

Denote the set $S=\{f+1,f+2,\ldots,n\}$ which contains $n-\hat{f}+1,\ldots,n$ as $0\leq f\leq\hat{f}<\frac{n}{2}$, so $\overline{x}_{S}=\frac{1}{|S|}\sum_{k\in S}x_{k}=\frac{\hat{f}}{n-f}$. Then since $|S|=n-f$ and $\mathcal{A}$ is $(f,\kappa)$-robust, we have

$$ $\displaystyle|\mathcal{A}(x_{1},\ldots,x_{n})-\overline{x}_{S}|^{2}\leq\frac{\kappa}{|S|}\sum_{k\in S}|x_{k}-\overline{x}_{S}|^{2}.$ $$

Substituting $\mathcal{A}(x_{1},\ldots,x_{n})=0$, $\overline{x}_{S}=\frac{\hat{f}}{n-f}$, $|S|=n-f$ and Eq. ([19](https://arxiv.org/html/2510.04432v1#A2.E19)) into the inequality above, we have

$$ $\displaystyle\frac{\hat{f}^{2}}{(n-f)^{2}}\leq$ $\displaystyle\frac{\kappa}{n-f}\Big[\hat{f}\Big(1-\frac{\hat{f}}{n-f}\Big)^{2}+(n-f-\hat{f})\Big(\frac{\hat{f}}{n-f}\Big)^{2}\Big]$ $\displaystyle=$ $\displaystyle\frac{\kappa}{(n-f)^{3}}\Big[\hat{f}(n-f-\hat{f})^{2}+(n-f-\hat{f})\hat{f}^{2}\Big]$ $\displaystyle=$ $\displaystyle\frac{\kappa\hat{f}(n-f-\hat{f})}{(n-f)^{3}}[(n-f-\hat{f})+\hat{f}]$ $\displaystyle=$ $\displaystyle\frac{\kappa\hat{f}(n-f-\hat{f})}{(n-f)^{2}},$ $$

which implies $\kappa\geq\frac{\hat{f}}{n-f-\hat{f}}$.

#### B.3 Proof of Item 3

We use the composite aggregator $\hat{f}$-Krum$\circ$$\hat{f}$-NNM is defined by Definition [3](https://arxiv.org/html/2510.04432v1#Thmdefinition3) with $\mathcal{A}=\hat{f}$-Krum. Based on Lemmas [1](https://arxiv.org/html/2510.04432v1#Thmlemma1) and [2](https://arxiv.org/html/2510.04432v1#Thmlemma2), for any $0\leq f\leq\hat{f}<\frac{n}{2}$, $(\hat{f}\mathchar 45\relax{\rm Krum})\circ(\hat{f}\mathchar 45\relax{\rm NNM})$ is an $(f,\kappa)$-robust aggregator with

$$ $\kappa=\frac{12\hat{f}}{n-f}\Big(\frac{6(n-f)}{n-f-\hat{f}}+1\Big)\leq\frac{12\hat{f}}{n-f}\cdot\Big(\frac{6(n-f)}{n-f-\hat{f}}+\frac{n-f}{n-f-\hat{f}}\Big)=\frac{84\hat{f}}{n-f-\hat{f}}.$ $$

This concludes the proof of Item [3](https://arxiv.org/html/2510.04432v1#S3.I1.i3). It remains to prove Lemmas [1](https://arxiv.org/html/2510.04432v1#Thmlemma1) and [2](https://arxiv.org/html/2510.04432v1#Thmlemma2) in the next two subsections.

#### B.4 Proof of Lemma 1 for NNM

For any $n\geq 1$, $\hat{f}\in\big[0,\frac{n}{2}\big)$, $k\in[n]$ and $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$, denote $\mathcal{N}_{k}\subset[n]$ as the set of $(n-\hat{f})$ indexes from $[n]$ such that $\{x_{i}\}_{i\in\mathcal{N}_{k}}$ are the $(n-\hat{f})$ nearest neighbors of $x_{k}$. In other words, $\max_{i\in\mathcal{N}_{k}}\|x_{i}-x_{k}\|\leq\min_{j\in[n]\backslash\mathcal{N}_{k}}\|x_{j}-x_{k}\|$. Then, for any set $S\subset[n]$ with size $|S|=n-f$, we have

$$ $\displaystyle\frac{1}{|\mathcal{N}_{k}|}\sum_{i\in\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}\leq\frac{1}{|S|}\sum_{i\in\mathcal{S}}\|x_{i}-x_{k}\|^{2},$ (20) $$

since $\frac{1}{|\mathcal{N}_{k}|}\sum_{i\in\mathcal{N}_{k}}\|x_{k}-x_{i}\|^{2}$ is the average of the $|\mathcal{N}_{k}|=n-\hat{f}$ smallest numbers in $\{\|x_{k}-x_{i}\|^{2}\}_{i=1}^{n}$, while $\frac{1}{|S|}\sum_{i\in\mathcal{S}}\|x_{k}-x_{i}\|^{2}$ is the average of $|S|=n-f$ ($|S|\geq|\mathcal{N}_{k}|$) numbers in $\{\|x_{k}-x_{i}\|^{2}\}_{i=1}^{n}$. Then we have

$$ $\displaystyle\|y_{k}-\overline{x}_{S}\|^{2}$ $\displaystyle=$ $\displaystyle\Big\|\frac{1}{n-\hat{f}}\sum_{i\in\mathcal{N}_{k}}x_{i}-\frac{1}{n-f}\sum_{i\in S}x_{i}\Big\|^{2}$ $\displaystyle=$ $\displaystyle\Big\|\Big(\frac{1}{n-\hat{f}}-\frac{1}{n-f}\Big)\sum_{i\in S\cap\mathcal{N}_{k}}(x_{i}-x_{k})+\frac{1}{n-\hat{f}}\sum_{i\in\mathcal{N}_{k}\backslash S}(x_{i}-x_{k})-\frac{1}{n-f}\sum_{i\in S\backslash\mathcal{N}_{k}}(x_{i}-x_{k})\Big\|^{2}$ $\displaystyle\leq$ $\displaystyle 3\Big\|\frac{\hat{f}-f}{(n-\hat{f})(n-f)}\sum_{i\in S\cap\mathcal{N}_{k}}(x_{i}-x_{k})\Big\|^{2}+3\Big\|\frac{1}{n-\hat{f}}\sum_{i\in\mathcal{N}_{k}\backslash S}(x_{i}-x_{k})\Big\|^{2}$ $\displaystyle+3\Big\|-\frac{1}{n-f}\sum_{i\in S\backslash\mathcal{N}_{k}}(x_{i}-x_{k})\Big\|^{2}$ $\displaystyle\leq$ $\displaystyle\frac{3|S\cap\mathcal{N}_{k}|(\hat{f}-f)^{2}}{(n-\hat{f})^{2}(n-f)^{2}}\sum_{i\in S\cap\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}+\frac{3|\mathcal{N}_{k}\backslash S|}{(n-\hat{f})^{2}}\sum_{i\in\mathcal{N}_{k}\backslash S}\|x_{i}-x_{k}\|^{2}$ $\displaystyle+\frac{3|S\backslash\mathcal{N}_{k}|}{(n-f)^{2}}\sum_{i\in S\backslash\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{3(\hat{f}-f)^{2}}{(n-\hat{f})(n-f)^{2}}\sum_{i\in S\cap\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}+\frac{3f}{(n-\hat{f})^{2}}\sum_{i\in\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}$ $\displaystyle+\frac{3\hat{f}}{(n-f)^{2}}\sum_{i\in S\backslash\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{3\hat{f}}{|S|(n-f)}\sum_{i\in S\cap\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}+\frac{3f|\mathcal{N}_{k}|}{|S|(n-\hat{f})^{2}}\sum_{i\in\mathcal{S}}\|x_{i}-x_{k}\|^{2}+\frac{3\hat{f}}{|S|(n-f)}\sum_{i\in S\backslash\mathcal{N}_{k}}\|x_{i}-x_{k}\|^{2}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\Big[\frac{3\hat{f}}{|S|(n-f)}+\frac{3f}{|S|(n-\hat{f})}\Big]\sum_{i\in S}\|x_{i}-x_{k}\|^{2}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle\frac{6\hat{f}}{|S|(n-f)}\sum_{i\in S}\|x_{i}-x_{k}\|^{2},$ (21) $$

where (a) uses $|S\cap\mathcal{N}_{k}|\leq|\mathcal{N}_{k}|=n-\hat{f}$, $|\mathcal{N}_{k}\backslash S|\leq n-|S|=f$, $|S\backslash\mathcal{N}_{k}|\leq n-|\mathcal{N}_{k}|=\hat{f}$, (b) uses Eq. ([20](https://arxiv.org/html/2510.04432v1#A2.E20)), $0\leq f\leq\hat{f}<\frac{n}{2}$ (so $\hat{f}-f\leq\hat{f}\leq n-\hat{f}$) and $|S|=n-f$, (c) uses $|\mathcal{N}_{k}|=n-\hat{f}$, and (d) uses the following inequality.

$$ $\displaystyle\frac{3\hat{f}}{|S|(n-f)}-\frac{3f}{|S|(n-\hat{f})}=\frac{3\hat{f}(n-\hat{f})-3f(n-f)}{|S|(n-f)(n-\hat{f})}=\frac{3(\hat{f}-f)(n-\hat{f}-f)}{|S|(n-f)(n-\hat{f})}\geq 0.$ $$

Denote $(y_{1},\ldots,y_{n})=\hat{f}\mathchar 45\relax{\rm NNM}(x_{1},\ldots,x_{n})$ where $y_{k}=\frac{1}{n-\hat{f}}\sum_{i\in\mathcal{N}(x_{k})}x_{i}$ as defined in Eq. ([6](https://arxiv.org/html/2510.04432v1#S3.E6)). Then denote $\overline{x}_{S}=\frac{1}{S}\sum_{k\in S}x_{k}$ and $\overline{y}_{S}=\frac{1}{S}\sum_{k\in S}y_{k}$. We obtain that

$$ $\displaystyle\|\overline{y}_{S}-\overline{x}_{S}\|^{2}+\frac{1}{|S|}\sum_{k\in S}\|y_{k}-\overline{y}_{S}\|^{2}$ $\displaystyle=$ $\displaystyle\frac{1}{|S|}\sum_{k\in S}\big(\|y_{k}-\overline{y}_{S}\|^{2}+\|\overline{y}_{S}-\overline{x}_{S}\|^{2}\big)$ $\displaystyle=$ $\displaystyle\frac{1}{|S|}\sum_{k\in S}\big[\|(y_{k}-\overline{y}_{S})+(\overline{y}_{S}-\overline{x}_{S})\|^{2}-2\langle y_{k}-\overline{y}_{S},\overline{y}_{S}-\overline{x}_{S}\rangle\big]$ $\displaystyle=$ $\displaystyle\frac{1}{|S|}\sum_{k\in S}\|y_{k}-\overline{x}_{S}\|^{2}-2\Big\langle\overline{y}_{S}-\overline{x}_{S},\frac{1}{|S|}\sum_{k\in S}(y_{k}-\overline{y}_{S})\Big\rangle$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{1}{|S|}\sum_{k\in S}\frac{6\hat{f}}{|S|(n-f)}\sum_{i\in S}\|x_{i}-x_{k}\|^{2}-2\langle\overline{y}_{S}-\overline{x}_{S},\overline{y}_{S}-\overline{y}_{S}\rangle$ $\displaystyle=$ $\displaystyle\frac{6\hat{f}}{|S|^{2}(n-f)}\sum_{i,k\in S}(\|x_{i}-\overline{x}_{S}\|^{2}+\|x_{k}-\overline{x}_{S}\|^{2}-2\langle x_{i}-\overline{x}_{S},x_{k}-\overline{x}_{S}\rangle)$ $\displaystyle=$ $\displaystyle\frac{6\hat{f}}{|S|^{2}(n-f)}\Big[|S|\sum_{i\in S}(\|x_{i}-\overline{x}_{S}\|^{2})+|S|\sum_{k\in S}(\|x_{k}-\overline{x}_{S}\|^{2})-2\big\langle|S|\overline{x}_{S}-|S|\overline{x}_{S},|S|\overline{x}_{S}-|S|\overline{x}_{S}\big\rangle\Big]$ $\displaystyle=$ $\displaystyle\frac{12\hat{f}}{n-f}\cdot\frac{1}{|S|}\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2},$ (22) $$

where (a) uses Eq. ([21](https://arxiv.org/html/2510.04432v1#A2.E21)).

For any $S\subset[n]$ with size $|S|=n-f$, we prove below that the composite aggregator $\mathcal{A}\circ\hat{f}\mathchar 45\relax{\rm NNM}(x_{1},\ldots,x_{n})=\mathcal{A}(y_{1},\ldots,y_{n})$ is $(f,\kappa)$-robust with $\kappa=\frac{12\hat{f}(1+\kappa)}{n-f}$.

$$ $\displaystyle\|\mathcal{A}\circ\hat{f}\mathchar 45\relax{\rm NNM}(x_{1},\ldots,x_{n})-\overline{x}_{S}\|^{2}$ $\displaystyle\leq$ $\displaystyle(1+\kappa^{-1})\|\mathcal{A}(y_{1},\ldots,y_{n})-\overline{y}_{S}\|^{2}+(1+\kappa)\|\overline{y}_{S}-\overline{x}_{S}\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{1+\kappa}{|S|}\sum_{k=1}^{n}\|y_{k}-\overline{y}_{S}\|^{2}+(1+\kappa)\|\overline{y}_{S}-\overline{x}_{S}\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{12\hat{f}(1+\kappa)}{n-f}\cdot\frac{1}{|S|}\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2}$ (23) $$

where (a) uses the fact that $\mathcal{A}$ is an $(f,\kappa)$-robust aggregator, (b) uses Eq. ([22](https://arxiv.org/html/2510.04432v1#A2.E22)).

#### B.5 Proof of Lemma 2 for Krum Aggregator

For any $n\geq 1$, $\hat{f}\in\big[0,\frac{n}{2}\big)$, $k\in[n]$ and $x_{1},\ldots,x_{n}\in\mathbb{R}^{d}$, denote $\mathcal{N}_{k}\subset[n]$ as the set of $(n-\hat{f})$ indexes from $[n]$ such that $\{x_{i}\}_{i\in\mathcal{N}_{k}}$ are the $(n-\hat{f})$ nearest neighbors of $x_{k}$. In other words, $\max_{i\in\mathcal{N}_{k}}\|x_{i}-x_{k}\|\leq\min_{j\in[n]\backslash\mathcal{N}_{k}}\|x_{j}-x_{k}\|$. Then, for any set $S\subset[n]$ with size $|S|=n-f$, Eq. ([20](https://arxiv.org/html/2510.04432v1#A2.E20)) has been proved as repeated below.

$$ $\displaystyle\frac{1}{|\mathcal{N}_{k}|}\sum_{i\in\mathcal{N}_{k}}\|x_{k}-x_{i}\|^{2}\leq\frac{1}{|S|}\sum_{i\in\mathcal{S}}\|x_{k}-x_{i}\|^{2}.$ (24) $$

Then for $k^{*}\in[n]$ defined in the $\hat{f}$-Krum ([7](https://arxiv.org/html/2510.04432v1#S3.E7)), we have

$$ $\displaystyle\sum_{i\in\mathcal{N}_{k^{*}}}\left\|x_{k^{*}}-x_{i}\right\|^{2}$ $\displaystyle=$ $\displaystyle\min_{k\in[n]}\sum_{i\in\mathcal{N}_{k}}\left\|x_{k}-x_{i}\right\|^{2}$ $\displaystyle\leq$ $\displaystyle\frac{1}{|S|}\sum_{k\in S}\sum_{i\in\mathcal{N}_{k}}\left\|x_{k}-x_{i}\right\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{n-\hat{f}}{|S|^{2}}\sum_{i,k\in S}\left\|x_{k}-\overline{x}_{S}-\left(x_{i}-\overline{x}_{S}\right)\right\|^{2}$ $\displaystyle=$ $\displaystyle\frac{n-\hat{f}}{|S|^{2}}\sum_{i,k\in S}\Big(\left\|x_{k}-\overline{x}_{S}\right\|^{2}+\left\|x_{i}-\overline{x}_{S}\right\|^{2}-2\left\langle x_{k}-\overline{x}_{S},x_{i}-\overline{x}_{S}\right\rangle\Big)$ $\displaystyle=$ $\displaystyle\frac{n-\hat{f}}{|S|^{2}}\Big[\sum_{i,k\in S}\left\|x_{k}-\overline{x}_{S}\right\|^{2}+\sum_{i,k\in S}\left\|x_{i}-\overline{x}_{S}\right\|^{2}-2\sum_{i,k\in S}\left\langle x_{k}-\overline{x}_{S},x_{i}-\overline{x}_{S}\right\rangle\Big]$ $\displaystyle=$ $\displaystyle\frac{n-\hat{f}}{|S|^{2}}\Big[2|S|\sum_{i\in S}\left\|x_{i}-\overline{x}_{S}\right\|^{2}-2\sum_{i\in S}\Big\langle\underbrace{\sum_{k\in S}\left(x_{k}-\overline{x}_{S}\right)}_{=0},x_{i}-\overline{x}_{S}\Big\rangle\Big]$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle 2\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2}.$ (25) $$

where (a) uses Eq. ([24](https://arxiv.org/html/2510.04432v1#A2.E24)) and $|\mathcal{N}_{k}|=n-\hat{f}$, and (b) uses $|S|=n-f\geq n-\hat{f}$. Note that

$$ $\displaystyle\|x_{k^{*}}-\overline{x}_{S}\|^{2}\leq 2\|x_{k^{*}}-x_{i}\|^{2}+2\|x_{i}-\overline{x}_{S}\|^{2},\forall i\in S$ (26) $$

which can be rearranged into

$$ $\displaystyle\|x_{k^{*}}-x_{i}\|^{2}\geq\frac{1}{2}\|x_{k^{*}}-\overline{x}_{S}\|^{2}-\|x_{i}-\overline{x}_{S}\|^{2},\forall i\in S.$ (27) $$

Then, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}_{k^{*}}}\left\|x_{k^{*}}-x_{i}\right\|^{2}$ $\displaystyle\geq\sum_{i\in S\cap\mathcal{N}_{k^{*}}}\left\|x_{k^{*}}-x_{i}\right\|^{2}$ $\displaystyle\overset{(a)}{\geq}\frac{|S\cap\mathcal{N}_{k^{*}}|}{2}\left\|x_{k^{*}}-\bar{x}_{S}\right\|^{2}-\sum_{i\in S\cap\mathcal{N}_{k^{*}}}\left\|x_{i}-\bar{x}_{S}\right\|^{2}$ $\displaystyle\overset{(b)}{\geq}\frac{n-f-\hat{f}}{2}\left\|x_{k^{*}}-\bar{x}_{S}\right\|^{2}-\sum_{i\in S\cap\mathcal{N}_{k^{*}}}\left\|x_{i}-\bar{x}_{S}\right\|^{2},$ $$

where (a) uses Eq. ([27](https://arxiv.org/html/2510.04432v1#A2.E27)) and (b) uses $|S\cap\mathcal{N}_{k^{*}}|=|S|+|\mathcal{N}_{k^{*}}|-|S\cup\mathcal{N}_{k^{*}}|\geq(n-f)+(n-\hat{f})-n=n-f-\hat{f}$. By rearranging the inequality above, we have

$$ $\displaystyle\|x_{k^{*}}-\bar{x}_{S}\|^{2}\leq$ $\displaystyle\frac{2}{n-f-\hat{f}}\Big[\sum_{i\in\mathcal{N}_{k^{*}}}\|x_{k^{*}}-x_{i}\|^{2}+\sum_{i\in S\cap\mathcal{N}_{k^{*}}}\|x_{i}-\bar{x}_{S}\|^{2}\Big]$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\frac{2}{n-f-\hat{f}}\Big[2\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2}+\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2}\Big]$ $\displaystyle\leq$ $\displaystyle\frac{6}{n-f-\hat{f}}\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2}=\frac{6(n-f)}{n-f-\hat{f}}\cdot\frac{1}{|S|}\sum_{i\in S}\|x_{i}-\overline{x}_{S}\|^{2},$ $$

where (a) uses Eq. ([25](https://arxiv.org/html/2510.04432v1#A2.E25)). Therefore, $(\hat{f}\mathchar 45\relax{\rm Krum})(x_{1},\ldots,x_{n})=x_{k^{*}}$ defined by Eq. ([7](https://arxiv.org/html/2510.04432v1#S3.E7)) is $(f,\kappa)$-robust with $\kappa\leq\frac{6(n-f)}{n-f-\hat{f}}$

### Appendix C Proof of Theorem 3

Without loss of generality, use $\mathcal{H}=[n-f]=\{1,2,\ldots,n-f\}$ as the set of honest clients. Select the loss function $\ell_{k}(w)=\frac{w^{2}}{2}(w\in\mathbb{R})$ for every client $k\in[n]$, which satisfies Assumptions [1](https://arxiv.org/html/2510.04432v1#Thmassum1)-[4](https://arxiv.org/html/2510.04432v1#Thmassum4).

In Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1), use the coordinate-wise trimmed mean (CWTM) aggregator defined by Eq. ([5](https://arxiv.org/html/2510.04432v1#S3.E5)) which has been proved to be an $(\hat{f},\hat{\kappa})$-robust aggregator (see Proposition 2 of Allouah et al. (2023)) with $\hat{\kappa}=\frac{6\hat{f}}{n-2\hat{f}}\big(1+\frac{\hat{f}}{n-2\hat{f}}\big)$. All the honest clients $k\in\mathcal{H}=[n-f]$ perform the local gradient descent updates ([2](https://arxiv.org/html/2510.04432v1#S2.E2)) as follows.

$$ $\displaystyle w_{t,h+1}^{(k)}=w_{t,h}^{(k)}-\gamma\ell_{k}^{\prime}(w_{t,h}^{(k)})=(1-\gamma)w_{t,h}^{(k)},k\in\mathcal{H}=[n-f].$ (28) $$

Iterating the update rule above yields that

$$ $\displaystyle w_{t}^{(k)}=w_{t,H}^{(k)}=(1-\gamma)^{H}w_{t,0}^{(k)}=(1-\gamma)^{H}w_{t},k\in\mathcal{H}=[n-f].$ $$

In contrast, we let the Byzantine clients $k\in[n]\backslash\mathcal{H}=\{n-f+1,n-f+2,\ldots,n\}$ upload $w_{t}^{(k)}=n|(1-\gamma)^{H}w_{t}|+t$. Therefore, the global parameter update rule ([3](https://arxiv.org/html/2510.04432v1#S2.E3)) becomes

$$ $\displaystyle w_{t+1}=$ $\displaystyle w_{t}+\mathcal{A}(\{w_{t}^{(k)}-w_{t}\}_{k=1}^{n})$ $\displaystyle=$ $\displaystyle w_{t}+\frac{(n-f-\hat{f})[(1-\gamma)^{H}w_{t}-w_{t}]+(f-\hat{f})[n|(1-\gamma)^{H}w_{t}|-w_{t}+t]}{n-2\hat{f}}$ $\displaystyle=$ $\displaystyle\frac{n(f-\hat{f})|(1-\gamma)^{H}w_{t}|-(n-f-\hat{f})|(1-\gamma)^{H}w_{t}|+t(f-\hat{f})}{n-2\hat{f}}$ $\displaystyle\overset{(a)}{\geq}$ $\displaystyle\frac{t(f-\hat{f})}{n-2\hat{f}},$ $$

where (a) uses the CWTM aggregator $\mathcal{A}$ defined by Eq. ([5](https://arxiv.org/html/2510.04432v1#S3.E5)) as well as the fact that $\{w_{t}^{(k)}-w_{t}\}_{k=1}^{n}$ contains $n-f$ scalars $(1-\gamma)^{H}w_{t}-w_{t}$ and $f$ larger scalars $n|(1-\gamma)^{H}w_{t}|-w_{t}+t$, and (b) uses $n(f-\hat{f})-(n-f-\hat{f})>f+\hat{f}>0$ and $n-2\hat{f}>0$ since the integers $\hat{f}$, $f$, $n$ satisfy $0\leq\hat{f}<f<\frac{n}{2}$. Since $\frac{(f-\hat{f})}{n-2\hat{f}}>0$, the inequality above implies that $|w_{t}|\to+\infty$ as $t\to+\infty$. Note that the objective function ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) in this example is $\ell_{\mathcal{H}}(w)=\frac{w^{2}}{2}$. Hence, Eqs. ([9](https://arxiv.org/html/2510.04432v1#S4.E9)) and ([10](https://arxiv.org/html/2510.04432v1#S4.E10)) can be proved as follows as $T\to+\infty$.

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}|\ell_{\mathcal{H}}^{\prime}(w_{t})|^{2}=\frac{1}{T}\sum_{t=0}^{T-1}|w_{t}|^{2}\to+\infty.$ $$

$$ $\displaystyle\ell_{\mathcal{H}}(w_{T})-\ell^{*}=\frac{w_{T}^{2}}{2}-0\to+\infty.$ $$

### Appendix D Proof of Theorem 4

Without loss of generality, use $\mathcal{H}=[n-f]=\{1,2,\ldots,n-f\}$. Let the Byzantine clients adopt the same honest behavior as the honest clients, i.e., upload the result after $H$ local gradient descent updates. This is valid since Byzantine clients can upload any vectors.

Select the following loss functions.

$$ $\displaystyle\ell_{k}(w)=\left\{\begin{aligned} &cG(w+1)^{2},k=1,2,\ldots,\hat{f}\\ &cGw^{2},k=\hat{f}+1,\hat{f}+2,\ldots,n\end{aligned}\right.,$ (29) $$

where $w\in\mathbb{R}$ and the constant $c>0$ is to be selected later. The derivatives of these loss functions are shown below.

$$ $\displaystyle\ell_{k}^{\prime}(w)=\left\{\begin{aligned} &2cG(w+1),k=1,2,\ldots,\hat{f}\\ &2cGw,k=\hat{f}+1,\hat{f}+2,\ldots,n\end{aligned}\right..$ (30) $$

It is straightforward to check that these loss functions ([29](https://arxiv.org/html/2510.04432v1#A4.E29)) satisfy Assumption [2](https://arxiv.org/html/2510.04432v1#Thmassum2), i.e., $L$-smoothness with Lipschitz constant $L=2cG$. Then the objective function ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) is

$$ $\displaystyle\ell_{\mathcal{H}}(w)=$ $\displaystyle\frac{1}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\ell_{k}(w)$ $\displaystyle=$ $\displaystyle\frac{1}{n-f}[\hat{f}\cdot cG(w+1)^{2}+(n-f-\hat{f})\cdot cGw^{2}]$ $\displaystyle=$ $\displaystyle\frac{cG}{n-f}\Big[(n-f)w^{2}+2\hat{f}w+\hat{f}\Big]$ $\displaystyle=$ $\displaystyle cG\Big[\Big(w+\frac{\hat{f}}{n-f}\Big)^{2}+\frac{\hat{f}(n-f-\hat{f})}{(n-f)^{2}}\Big],$ (31) $$

which has the following derivative.

$$ $\displaystyle\ell_{\mathcal{H}}^{\prime}(w)=2cG\Big(w+\frac{\hat{f}}{n-f}\Big),$ (32) $$

The objective function ([31](https://arxiv.org/html/2510.04432v1#A4.E31)) satisfies Assumption [1](https://arxiv.org/html/2510.04432v1#Thmassum1) with $\ell^{*}=\inf_{w\in\mathbb{R}^{d}}\ell_{\mathcal{H}}(w)=\frac{cG\hat{f}(n-f-\hat{f})}{(n-f)^{2}}$, and also satisfies Assumption [4](https://arxiv.org/html/2510.04432v1#Thmassum4) with $\mu=2cG$ since

$$ $\displaystyle\ell_{\mathcal{H}}(w)-\ell^{*}-\frac{1}{2\mu}\|\nabla\ell_{\mathcal{H}}(w)\|^{2}=cG\Big(w+\frac{\hat{f}}{n-f}\Big)^{2}-\frac{1}{4cG}\cdot 4c^{2}G^{2}\Big(w+\frac{\hat{f}}{n-f}\Big)^{2}=0.$ $$

Next, we will check Assumption [3](https://arxiv.org/html/2510.04432v1#Thmassum3) as follows.

$$ $\displaystyle\frac{1}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}|\ell_{k}^{\prime}(w)-\ell_{\mathcal{H}}^{\prime}(w)|^{2}$ $\displaystyle=$ $\displaystyle\frac{1}{n-f}\Big[\hat{f}\cdot(2cG)^{2}\Big(\frac{n-f-\hat{f}}{n-f}\Big)^{2}+(n-f-\hat{f})\cdot(2cG)^{2}\Big(\frac{\hat{f}}{n-f}\Big)^{2}\Big]$ $\displaystyle=$ $\displaystyle\frac{(2cG)^{2}}{(n-f)^{3}}\big[\hat{f}(n-f-\hat{f})^{2}+(n-f-\hat{f})\hat{f}^{2}\big]$ $\displaystyle=$ $\displaystyle\frac{\hat{f}(n-f-\hat{f})(2cG)^{2}}{(n-f)^{2}}$ (33) $$

By letting the equation above equal to $G^{2}$ to ensure Assumption [3](https://arxiv.org/html/2510.04432v1#Thmassum3), we can select

$$ $\displaystyle c=\frac{n-f}{2\sqrt{\hat{f}(n-f-\hat{f})}}.$ (34) $$

Suppose all the Byzantine clients behaves in the same way as the honest clients. Then every client $k\in S:=\{\hat{f}+1,\ldots,n\}$ adopts the following local gradient descent update.

$$ $\displaystyle w_{t,h+1}^{(k)}=w_{t,h}^{(k)}-\gamma\ell_{k}^{\prime}(w_{t,h}^{(k)})=(1-2cG\gamma)w_{t,h}^{(k)},\forall k\in S.$ $$

Iterating the update rule above yields that

$$ $\displaystyle w_{t}^{(k)}=w_{t,H}^{(k)}=(1-2cG\gamma)^{H}w_{t,0}^{(k)}=(1-2cG\gamma)^{H}w_{t},\forall k\in S.$ $$

Since $|S|=n-\hat{f}$, $\frac{1}{|S|}\sum_{k\in S}(w_{t}^{(k)}-w_{t})=[(1-2cG\gamma)^{H}-1]w_{t}$ and $\mathcal{A}$ is an $(\hat{f},\hat{\kappa})$-robust aggregator, we have

$$ $\displaystyle\big|\mathcal{A}(\{w_{t}^{(k)}-w_{t}\}_{k=1}^{n})-[(1-2cG\gamma)^{H}-1]w_{t}\big|^{2}$ $\displaystyle\leq$ $\displaystyle\hat{\kappa}\cdot\frac{1}{|S|}\sum_{k\in S}\big|w_{t}^{(k)}-w_{t}-[(1-2cG\gamma)^{H}-1]w_{t}\big|^{2}=0,$ $$

so the global parameter update rule ([3](https://arxiv.org/html/2510.04432v1#S2.E3)) becomes

$$ $\displaystyle w_{t+1}=w_{t}+\mathcal{A}(\{w_{t}^{(k)}-w_{t}\}_{k=1}^{n})=w_{t}+[(1-2cG\gamma)^{H}-1]w_{t}=(1-2cG\gamma)^{H}w_{t}.$ (35) $$

We consider the following cases of hyperparameter choices.

(Case 1): When $0<\gamma<\frac{1}{cG}$, we have $|(1-2cG\gamma)^{H}|<1$ and thus $w_{t}\to 0$ by Eq. ([35](https://arxiv.org/html/2510.04432v1#A4.E35)). This implies that as $T\to+\infty$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\to|\ell_{\mathcal{H}}^{\prime}(0)|^{2}=\frac{4c^{2}G^{2}\hat{f}^{2}}{(n-f)^{2}}=\frac{\hat{f}G^{2}}{n-f-\hat{f}}$ $$

and

$$ $\displaystyle\ell_{\mathcal{H}}(w_{T})-\ell^{*}\to\ell_{\mathcal{H}}(0)-\ell^{*}=cG\Big(\frac{\hat{f}}{n-f}\Big)^{2}=\frac{2c^{2}G^{2}}{\mu}\Big(\frac{\hat{f}}{n-f}\Big)^{2}=\frac{\hat{f}G^{2}}{2\mu(n-f-\hat{f})}$ $$

where we use $\mu=2cG$ and the choice of $c$ in Eq. ([34](https://arxiv.org/html/2510.04432v1#A4.E34)). Hence, Eqs. ([11](https://arxiv.org/html/2510.04432v1#S4.E11)) and ([12](https://arxiv.org/html/2510.04432v1#S4.E12)) hold in this case.

(Case 2): When $\gamma=\frac{1}{cG}$ and $H$ is an even number, Eq. ([35](https://arxiv.org/html/2510.04432v1#A4.E35)) implies that $w_{t}=w_{t-1}$ and thus $w_{t}\equiv w_{0}$.

(Case 3): When $\gamma=\frac{1}{cG}$ and $H$ is an odd number, Eq. ([35](https://arxiv.org/html/2510.04432v1#A4.E35)) implies that $w_{t}=-w_{t-1}$. Then for any even number $T$, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}=$ $\displaystyle\frac{1}{2}\big[|\ell_{\mathcal{H}}^{\prime}(w_{0})|^{2}+|\ell_{\mathcal{H}}^{\prime}(-w_{0})|^{2}\big]$ $\displaystyle=$ $\displaystyle\frac{1}{2}\Big[4c^{2}G^{2}\Big(w_{0}+\frac{\hat{f}}{n-f}\Big)^{2}+4c^{2}G^{2}\Big(-w_{0}+\frac{\hat{f}}{n-f}\Big)^{2}\Big]$ $\displaystyle=$ $\displaystyle 4\cdot\frac{(n-f)^{2}}{4\hat{f}(n-f-\hat{f})}\cdot G^{2}\Big(w_{0}^{2}+\frac{\hat{f}^{2}}{(n-f)^{2}}\Big)\geq\frac{\hat{f}G^{2}}{n-f-\hat{f}}.$ $$

and

$$ $\displaystyle\mathop{\lim\sup}_{T\to\infty}\ell_{H}(w_{T})-\ell^{*}=$ $\displaystyle cG\max\Big[\Big(w_{0}+\frac{\hat{f}}{n-f}\Big)^{2},\Big(-w_{0}+\frac{\hat{f}}{n-f}\Big)^{2}\Big]$ $\displaystyle\geq$ $\displaystyle\frac{2c^{2}G^{2}}{\mu}\frac{\hat{f}^{2}}{(n-f)^{2}}=\frac{\hat{f}G^{2}}{2\mu(n-f-\hat{f})},$ $$

where we use $\mu=2cG$ and the choice of $c$ in Eq. ([34](https://arxiv.org/html/2510.04432v1#A4.E34)). Hence, Eqs. ([11](https://arxiv.org/html/2510.04432v1#S4.E11)) and ([12](https://arxiv.org/html/2510.04432v1#S4.E12)) hold in this case.

(Case 4): When $\gamma>\frac{1}{cG}$, we have $|(1-2cG\gamma)^{H}|>1$ and thus $|w_{t}|\to+\infty$ by Eq. ([35](https://arxiv.org/html/2510.04432v1#A4.E35)). This implies that as $T\to+\infty$, we have

$$ $\displaystyle|\ell_{\mathcal{H}}^{\prime}(w_{T})|^{2}=4c^{2}G^{2}\Big(w_{T}+\frac{\hat{f}}{n-f}\Big)^{2}\to+\infty\Rightarrow\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\to+\infty$ $$

and

$$ $\displaystyle\ell_{\mathcal{H}}(w_{T})-\ell^{*}=cG\Big(w_{T}+\frac{\hat{f}}{n-f}\Big)^{2}\to+\infty.$ $$

Hence, Eqs. ([11](https://arxiv.org/html/2510.04432v1#S4.E11)) and ([12](https://arxiv.org/html/2510.04432v1#S4.E12)) hold in this case.

### Appendix E Proof of Theorem 5

#### E.1 Supporting Lemmas for Theorem 5

###### Lemma 3 .

Suppose $L^{2}\gamma_{t}^{2}H_{t}(H_{t}-1)\leq\frac{1}{2}$ and Assumption [3](https://arxiv.org/html/2510.04432v1#Thmassum3) holds. Then $V_{t,k}\overset{\rm def}{=}\sum_{h=0}^{H_{t}-1}\|w_{t,h}^{(k)}-w_{t}\|^{2}$ obtained from Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) has the following upper bounds.

$$ $\displaystyle V_{t,k}\leq$ $\displaystyle 2\gamma_{t}^{2}H_{t}^{2}(H_{t}-1)\|\nabla\ell_{k}(w_{t})\|^{2}$ (36) $\displaystyle\sum_{k\in\mathcal{H}}V_{t,k}\leq$ $\displaystyle 4\gamma_{t}^{2}|\mathcal{H}|H_{t}^{2}(H_{t}-1)\big[G^{2}+\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big]$ (37) $$

###### Proof.

$$ $\displaystyle V_{t,k}\overset{\rm def}{=}$ $\displaystyle\sum_{h=0}^{H_{t}-1}\|w_{t,h}^{(k)}-w_{t}\|^{2}$ $\displaystyle\overset{(a)}{=}$ $\displaystyle\sum_{h=0}^{H_{t}-1}\Big\|\sum_{h^{\prime}=0}^{h-1}\gamma_{t}\nabla\ell_{k}(w_{t,h^{\prime}}^{(k)})\Big\|^{2}$ $\displaystyle\leq$ $\displaystyle\gamma_{t}^{2}\sum_{h=0}^{H_{t}-1}\sum_{h^{\prime}=0}^{h-1}h\|\nabla\ell_{k}(w_{t,h^{\prime}}^{(k)})\|^{2}$ $\displaystyle=$ $\displaystyle\gamma_{t}^{2}\sum_{h^{\prime}=0}^{H_{t}-2}\sum_{h=h^{\prime}+1}^{H_{t}-1}h\|\nabla\ell_{k}(w_{t,h^{\prime}}^{(k)})\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{\gamma_{t}^{2}H_{t}(H_{t}-1)}{2}\sum_{h^{\prime}=0}^{H_{t}-1}\|\nabla\ell_{k}(w_{t,h^{\prime}}^{(k)})\|^{2}$ $\displaystyle\leq$ $\displaystyle\gamma_{t}^{2}H_{t}(H_{t}-1)\sum_{h=0}^{H_{t}-1}\big[\|\nabla\ell_{k}(w_{t,h}^{(k)})-\nabla\ell_{k}(w_{t})\|^{2}+\|\nabla\ell_{k}(w_{t})\|^{2}\big]$ $\displaystyle\leq$ $\displaystyle L^{2}\gamma_{t}^{2}H_{t}(H_{t}-1)\sum_{h=0}^{H_{t}-1}\big[\|w_{t,h}^{(k)}-w_{t}\|^{2}\big]+\gamma_{t}^{2}H_{t}^{2}(H_{t}-1)\|\nabla\ell_{k}(w_{t})\|^{2}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\frac{1}{2}V_{t,k}+\gamma_{t}^{2}H_{t}^{2}(H_{t}-1)\|\nabla\ell_{k}(w_{t})\|^{2}$ (38) $$

where (a) uses the local update rule ([2](https://arxiv.org/html/2510.04432v1#S2.E2)), (b) uses $\sum_{h=h^{\prime}+1}^{H_{t}-1}h\leq\sum_{h=1}^{H_{t}-1}h=\frac{H_{t}(H_{t}-1)}{2}$, and (c) uses $L^{2}\gamma_{t}^{2}H_{t}(H_{t}-1)\leq\frac{1}{2}$. Hence, Eq. ([36](https://arxiv.org/html/2510.04432v1#A5.E36)) can be proved by rearranging the inequality above.

Therefore, we can prove Eq. ([37](https://arxiv.org/html/2510.04432v1#A5.E37)) by summing Eq. ([36](https://arxiv.org/html/2510.04432v1#A5.E36)) over $k\in\mathcal{H}$ as follows.

$$ $\displaystyle\sum_{k\in\mathcal{H}}V_{t,k}\leq$ $\displaystyle 2\gamma_{t}^{2}H_{t}^{2}(H_{t}-1)\sum_{k\in\mathcal{H}}\|\nabla\ell_{k}(w_{t})\|^{2}$ $\displaystyle\leq$ $\displaystyle 4\gamma_{t}^{2}H_{t}^{2}(H_{t}-1)\sum_{k\in\mathcal{H}}\big[\|\nabla\ell_{k}(w_{t})-\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}+\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big]$ $\displaystyle\leq$ $\displaystyle 4\gamma_{t}^{2}|\mathcal{H}|H_{t}^{2}(H_{t}-1)\big[G^{2}+\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big],$ $$

where the final $\leq$ uses Assumption [3](https://arxiv.org/html/2510.04432v1#Thmassum3).
∎

###### Lemma 4 .

Define the following quantity obtained from Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1).

$$ $\displaystyle\Delta_{t}\overset{\rm def}{=}\frac{1}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}(w_{t}^{(k)}-w_{t})\overset{\rm Eq.(\ref{eq:localGD})}{=}-\frac{\gamma_{t}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\sum_{h=0}^{H_{t}-1}\nabla\ell_{k}(w_{t,h}^{(k)}).$ (39) $$

Suppose $L^{2}\gamma_{t}^{2}H_{t}(H_{t}-1)\leq\frac{1}{2}$, the aggregator used in Algorithm [1](https://arxiv.org/html/2510.04432v1#alg1) is $(f,\kappa)$-robust and Assumptions [2](https://arxiv.org/html/2510.04432v1#Thmassum2)-[3](https://arxiv.org/html/2510.04432v1#Thmassum3) hold. Then $\Delta_{t}$ above satisfies the following two bounds.

$$ $\displaystyle\|w_{t+1}-w_{t}-\Delta_{t}\|^{2}\leq$ $\displaystyle 3\kappa H_{t}^{2}\gamma_{t}^{2}G^{2}[1+8L^{2}H_{t}(H_{t}-1)\gamma_{t}^{2}]$ $\displaystyle+24\kappa L^{2}H_{t}^{3}(H_{t}-1)\gamma_{t}^{4}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2},$ (40) $\displaystyle\|\Delta_{t}+H_{t}\gamma_{t}\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\leq$ $\displaystyle 4L^{2}\gamma_{t}^{4}H_{t}^{3}(H_{t}-1)\big[G^{2}+\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big],$ (41) $$

###### Proof.

Since $\mathcal{A}$ is an $(f,\kappa)$-robust aggregator ($f=n-|\mathcal{H}|$) by Definition [1](https://arxiv.org/html/2510.04432v1#Thmdefinition1), we can prove Eq. ([40](https://arxiv.org/html/2510.04432v1#A5.E40)) as follows.

$$ $\displaystyle\|w_{t+1}-w_{t}-\Delta_{t}\|^{2}$ $\displaystyle=$ $\displaystyle\|\mathcal{A}(\{w_{t}^{(k)}-w_{t}\}_{k=1}^{n})-\Delta_{t}\|^{2}$ $\displaystyle\leq$ $\displaystyle\frac{\kappa}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\|w_{t}^{(k)}-w_{t}-\Delta_{t}\|^{2}$ $\displaystyle\overset{(a)}{=}$ $\displaystyle\frac{\kappa}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\Big\|-\gamma_{t}\sum_{h=0}^{H_{t}-1}\nabla\ell_{k}(w_{t,h}^{(k)})+\frac{\gamma_{t}}{|\mathcal{H}|}\sum_{k^{\prime}\in\mathcal{H}}\sum_{h=0}^{H_{t}-1}\nabla\ell_{k^{\prime}}(w_{t,h}^{(k^{\prime})})\Big\|^{2}$ $\displaystyle=$ $\displaystyle\frac{\kappa\gamma_{t}^{2}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\Big\|\sum_{h=0}^{H_{t}-1}\Big[\nabla\ell_{k}(w_{t,h}^{(k)})-\frac{1}{|\mathcal{H}|}\sum_{k^{\prime}\in\mathcal{H}}\nabla\ell_{k^{\prime}}(w_{t,h}^{(k^{\prime})})\Big]\Big\|^{2}$ $\displaystyle\leq$ $\displaystyle\frac{\kappa H_{t}\gamma_{t}^{2}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\sum_{h=0}^{H_{t}-1}\Big\|\nabla\ell_{k}(w_{t,h}^{(k)})-\frac{1}{|\mathcal{H}|}\sum_{k^{\prime}\in\mathcal{H}}\nabla\ell_{k^{\prime}}(w_{t,h}^{(k^{\prime})})\Big\|^{2}$ $\displaystyle=$ $\displaystyle\kappa H_{t}\gamma_{t}^{2}\sum_{h=0}^{H_{t}-1}\frac{1}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\Big\|\nabla\ell_{k}(w_{t,h}^{(k)})-\frac{1}{|\mathcal{H}|}\sum_{k^{\prime}\in\mathcal{H}}\nabla\ell_{k^{\prime}}(w_{t,h}^{(k^{\prime})})\Big\|^{2}$ $\displaystyle\leq$ $\displaystyle 3\kappa H_{t}\gamma_{t}^{2}\sum_{h=0}^{H_{t}-1}\frac{1}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\Big[\Big\|\nabla\ell_{k}(w_{t})-\frac{1}{|\mathcal{H}|}\sum_{k^{\prime}\in\mathcal{H}}\nabla\ell_{k^{\prime}}(w_{t})\Big\|^{2}$ $\displaystyle+\Big\|\nabla\ell_{k}(w_{t,h}^{(k)})-\nabla\ell_{k}(w_{t})\Big\|^{2}+\Big\|\frac{1}{|\mathcal{H}|}\sum_{k^{\prime}\in\mathcal{H}}[\nabla\ell_{k^{\prime}}(w_{t})-\nabla\ell_{k^{\prime}}(w_{t,h}^{(k^{\prime})})]\Big\|^{2}\Big]$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle 3\kappa H_{t}^{2}\gamma_{t}^{2}G^{2}+\frac{3L^{2}\kappa H_{t}\gamma_{t}^{2}}{|\mathcal{H}|}\sum_{h=0}^{H_{t}-1}\sum_{k\in\mathcal{H}}\|w_{t,h}^{(k)}-w_{t}\|^{2}$ $\displaystyle+3\kappa H_{t}\gamma_{t}^{2}\sum_{h=0}^{H_{t}-1}\frac{1}{|\mathcal{H}|}\sum_{k^{\prime}\in\mathcal{H}}\|\nabla\ell_{k^{\prime}}(w_{t})-\nabla\ell_{k^{\prime}}(w_{t,h}^{(k^{\prime})})\|^{2}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle 3\kappa H_{t}^{2}\gamma_{t}^{2}G^{2}+\frac{6L^{2}\kappa H_{t}\gamma_{t}^{2}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}V_{t,k}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle 3\kappa H_{t}^{2}\gamma_{t}^{2}G^{2}+\frac{6L^{2}\kappa H_{t}\gamma_{t}^{2}}{|\mathcal{H}|}\cdot 4\gamma_{t}^{2}|\mathcal{H}|H_{t}^{2}(H_{t}-1)\big[G^{2}+\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big]$ $\displaystyle=$ $\displaystyle 3\kappa H_{t}^{2}\gamma_{t}^{2}G^{2}[1+8L^{2}H_{t}(H_{t}-1)\gamma_{t}^{2}]+24\kappa L^{2}H_{t}^{3}(H_{t}-1)\gamma_{t}^{4}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2},$ $$

where (a) uses Eqs. ([2](https://arxiv.org/html/2510.04432v1#S2.E2)) and ([39](https://arxiv.org/html/2510.04432v1#A5.E39)), (b) uses Assumptions [2](https://arxiv.org/html/2510.04432v1#Thmassum2)-[3](https://arxiv.org/html/2510.04432v1#Thmassum3), (c) uses Assumption [2](https://arxiv.org/html/2510.04432v1#Thmassum2) and defines $V_{t,k}\overset{\rm def}{=}\sum_{h=0}^{H_{t}-1}\|w_{t,h}^{(k)}-w_{t}\|^{2}$, (d) uses Eq. ([37](https://arxiv.org/html/2510.04432v1#A5.E37)).

Then we prove Eq. ([41](https://arxiv.org/html/2510.04432v1#A5.E41)) as follows.

$$ $\displaystyle\|\Delta_{t}+H_{t}\gamma_{t}\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}$ $\displaystyle\overset{(a)}{=}$ $\displaystyle\Big\|\frac{H_{t}\gamma_{t}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\nabla\ell_{k}(w_{t})-\frac{\gamma_{t}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\sum_{h=0}^{H_{t}-1}\nabla\ell_{k}(w_{t,h}^{(k)})\Big\|^{2}$ $\displaystyle=$ $\displaystyle H_{t}^{2}\gamma_{t}^{2}\Big\|\frac{1}{H_{t}|\mathcal{H}|}\sum_{k\in\mathcal{H}}\sum_{h=0}^{H_{t}-1}[\nabla\ell_{k}(w_{t})-\nabla\ell_{k}(w_{t,h}^{(k)})]\Big\|^{2}$ $\displaystyle\leq$ $\displaystyle H_{t}^{2}\gamma_{t}^{2}\cdot\frac{1}{H_{t}|\mathcal{H}|}\sum_{k\in\mathcal{H}}\sum_{h=0}^{H_{t}-1}\|\nabla\ell_{k}(w_{t})-\nabla\ell_{k}(w_{t,h}^{(k)})\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\frac{L^{2}H_{t}\gamma_{t}^{2}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}\sum_{h=0}^{H_{t}-1}\|w_{t,h}^{(k)}-w_{t}\|^{2}$ $\displaystyle\overset{(c)}{=}$ $\displaystyle\frac{L^{2}H_{t}\gamma_{t}^{2}}{|\mathcal{H}|}\sum_{k\in\mathcal{H}}V_{t,k}$ $\displaystyle\overset{(d)}{\leq}$ $\displaystyle 4L^{2}\gamma_{t}^{4}H_{t}^{3}(H_{t}-1)\big[G^{2}+\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big],$ $$

where (a) uses Eqs. ([1](https://arxiv.org/html/2510.04432v1#S2.E1)) and ([39](https://arxiv.org/html/2510.04432v1#A5.E39)), (b) uses Assumption [2](https://arxiv.org/html/2510.04432v1#Thmassum2), (c) defines $V_{t,k}\overset{\rm def}{=}\sum_{h=0}^{H_{t}-1}\|w_{t,h}^{(k)}-w_{t}\|^{2}$, and (d) uses Eq. ([37](https://arxiv.org/html/2510.04432v1#A5.E37)).
∎

###### Lemma 5 .

For any $0\leq x<1$, we have

$$ $\displaystyle\log(1-x)\leq-x$ (42) $$

###### Proof.

Denote the function $g(x)=\log(1-x)$, which has derivatives $g^{\prime}(x)=(x-1)^{-1}$ and $g^{\prime\prime}(x)=-(x-1)^{-2}$. Then based on the Taylor’s theorem, there exists $\theta\in[0,1]$ such that

$$ $\displaystyle\log(1-x)=g(x)=g(0)+g^{\prime}(0)x+\frac{1}{2}g^{\prime\prime}(\theta x)x^{2}=-x-\frac{x^{2}}{2(1-\theta x)^{2}}\leq-x.$ $$

∎

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

#### E.2 Remaining Proof of Theorem 5

Using $L$-smoothness of $\ell_{\mathcal{H}}$, we have

$$ $\displaystyle\ell_{\mathcal{H}}(w_{t+1})$ $\displaystyle\leq$ $\displaystyle\ell_{\mathcal{H}}(w_{t})+\langle\nabla\ell_{\mathcal{H}}(w_{t}),w_{t+1}-w_{t}\rangle+\frac{L}{2}\|w_{t+1}-w_{t}\|^{2}$ $\displaystyle\leq$ $\displaystyle\ell_{\mathcal{H}}(w_{t})\!+\!\langle\nabla\ell_{\mathcal{H}}(w_{t}),w_{t+1}\!-\!w_{t}\!-\!\Delta_{t}\rangle\!+\!\langle\nabla\ell_{\mathcal{H}}(w_{t}),\Delta_{t}\rangle\!+\!L\|w_{t+1}\!-\!w_{t}\!-\!\Delta_{t}\|^{2}\!+\!L\|\Delta_{t}\|^{2}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\ell_{\mathcal{H}}(w_{t})+\frac{H_{t}\gamma_{t}}{4}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}+\frac{1}{H_{t}\gamma_{t}}\|w_{t+1}-w_{t}-\Delta_{t}\|^{2}+\frac{1}{2H_{t}\gamma_{t}}\|\Delta_{t}+H_{t}\gamma_{t}\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}$ $\displaystyle-\frac{H_{t}\gamma_{t}}{2}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}-\frac{1}{2H_{t}\gamma_{t}}\|\Delta_{t}\|^{2}+L\|w_{t+1}-w_{t}-\Delta_{t}\|^{2}+L\|\Delta_{t}\|^{2}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\ell_{\mathcal{H}}(w_{t})-\frac{H_{t}\gamma_{t}}{4}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}-\Big(\frac{1}{2H_{t}\gamma_{t}}-L\Big)\|\Delta_{t}\|^{2}$ $\displaystyle+\frac{1}{2H_{t}\gamma_{t}}\cdot 4L^{2}\gamma_{t}^{4}H_{t}^{3}(H_{t}-1)\big[G^{2}+\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big]$ $\displaystyle+\!\Big(L\!+\!\frac{1}{H_{t}\gamma_{t}}\Big)\big\{3{\kappa}H_{t}^{2}\gamma_{t}^{2}G^{2}[1+8L^{2}H_{t}(H_{t}\!-\!1)\gamma_{t}^{2}]+24{\kappa}L^{2}H_{t}^{3}(H_{t}\!-\!1)\gamma_{t}^{4}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\big\}$ $\displaystyle\overset{(c)}{\leq}$ $\displaystyle\ell_{\mathcal{H}}(w_{t})-\frac{H_{t}\gamma_{t}}{4}\big[1-8L^{2}\gamma_{t}^{2}H_{t}(H_{t}-1)-96{\kappa}L^{2}H_{t}(H_{t}-1)\gamma_{t}^{2}\big]\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}$ $\displaystyle+G^{2}H_{t}\gamma_{t}\{2L^{2}\gamma_{t}^{2}H_{t}(H_{t}-1)+3{\kappa}(1+LH_{t}\gamma_{t})[1+8L^{2}H_{t}(H_{t}-1)\gamma_{t}^{2}]\},$ (43) $$

where (a) uses $\langle u,v\rangle\leq\frac{H_{t}\gamma_{t}}{4}\|u\|^{2}+\frac{1}{H_{t}\gamma_{t}}\|v\|^{2}$ for $u=\nabla\ell_{\mathcal{H}}(w_{t})$ and $v=w_{t+1}-w_{t}-\Delta_{t}$, as well as $\langle\nabla\ell_{\mathcal{H}}(w_{t}),\Delta_{t}\rangle=\langle u,v\rangle=\frac{1}{2}(\|u+v\|^{2}-\|u\|^{2}-\|v\|^{2})$ for $u=\sqrt{H_{t}\gamma_{t}}\nabla\ell_{\mathcal{H}}(w_{t})$ and $v=\frac{\Delta_{t}}{\sqrt{H_{t}\gamma_{t}}}$, (b) uses Eqs. ([40](https://arxiv.org/html/2510.04432v1#A5.E40))-([41](https://arxiv.org/html/2510.04432v1#A5.E41)), (c) uses $\gamma_{t}\leq\frac{1}{2LH_{t}}$.

Select constant hyperparameters $\gamma_{t}=\gamma$ and $H_{t}=H$ such that

$$ $\displaystyle L^{2}\gamma^{2}H(H-1)\leq\min\Big(\frac{1}{32},\frac{1}{384{\kappa}}\Big),\gamma\leq\frac{1}{2LH}.$ (44) $$

Then Eq. ([43](https://arxiv.org/html/2510.04432v1#A5.E43)) simplifies into

$$ $\displaystyle\ell_{\mathcal{H}}(w_{t+1})\leq\ell_{\mathcal{H}}(w_{t})\!-\!\frac{H\gamma}{16}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\!+\!G^{2}H\gamma\Big[2L^{2}\gamma^{2}H(H\!-\!1)+3{\kappa}\Big(1\!+\!\frac{1}{2}\Big)\Big(1\!+\!\frac{1}{4}\Big)\Big].$ (45) $$

Telescoping Eq. ([45](https://arxiv.org/html/2510.04432v1#A5.E45)) above over $t=0,1,\ldots,T-1$, we have

$$ $\displaystyle\ell^{*}\leq\ell_{\mathcal{H}}(w_{T})\leq\ell_{\mathcal{H}}(w_{0})-\frac{H\gamma}{16}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}+TG^{2}H\gamma\Big[2L^{2}\gamma^{2}H(H-1)+\frac{45{\kappa}}{8}\Big].$ $$

Rearranging the inequality above, we prove the convergence rate ([14](https://arxiv.org/html/2510.04432v1#S4.E14)) as follows.

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\|\nabla\ell_{\mathcal{H}}(w_{t})\|^{2}\leq$ $\displaystyle\frac{16}{TH\gamma}[\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+G^{2}[32L^{2}\gamma^{2}H(H-1)+90{\kappa}]$ $\displaystyle\leq$ $\displaystyle\frac{16cLH}{T^{2/3}}[\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+G^{2}\Big[\frac{32(H-1)}{c^{2}HT^{2/3}}+90{\kappa}\Big]$ $\displaystyle\leq$ $\displaystyle\frac{16cLH[\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+G^{2}}{T^{2/3}}+90{\kappa}G^{2},$ $$

where we select the stepsize $\gamma=\frac{1}{c^{\prime}LHT^{1/3}}$ with $c^{\prime}=\max(4\sqrt{2},\sqrt{384{\kappa}})$ which satisfies the conditions in Eq. ([44](https://arxiv.org/html/2510.04432v1#A5.E44)).

Furthermore, suppose Assumption [4](https://arxiv.org/html/2510.04432v1#Thmassum4) holds, that is,

$$ $\displaystyle\|\nabla\ell_{\mathcal{H}}(w)\|^{2}\geq 2\mu(\ell_{\mathcal{H}}(w)-\ell^{*}).$ $$

Substituting the inequality above into Eq. ([45](https://arxiv.org/html/2510.04432v1#A5.E45)).

$$ $\displaystyle\ell_{\mathcal{H}}(w_{t+1})-\ell^{*}\leq\Big(1-\frac{H\gamma\mu}{8}\Big)[\ell_{\mathcal{H}}(w_{t})-\ell^{*}]+G^{2}H\gamma\Big[2L^{2}\gamma^{2}H(H-1)+\frac{45{\kappa}}{8}\Big].$ $$

Iterating the inequality above over $t=0,1,\ldots,T-1$, we have

$$ $\displaystyle\ell_{\mathcal{H}}(w_{T})-\ell^{*}\leq$ $\displaystyle\Big(1-\frac{H\gamma\mu}{8}\Big)^{T}[\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+\frac{G^{2}}{\mu}\big[16L^{2}\gamma^{2}H(H-1)+45{\kappa}\big]$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle\exp\Big[T\log\Big(1-\frac{\mu}{8c^{\prime}LT^{1-\beta}}\Big)\Big][\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+\frac{16G^{2}}{\mu c^{\prime 2}T^{2-2\beta}}+\frac{45\kappa G^{2}}{\mu}$ $\displaystyle\overset{(b)}{\leq}$ $\displaystyle\exp\Big[T\Big(-\frac{\mu}{8c^{\prime}LT^{1-\beta}}\Big)\Big][\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+\frac{G^{2}}{2\mu T^{2-2\beta}}+\frac{45\kappa G^{2}}{\mu}$ $\displaystyle\leq$ $\displaystyle\exp\Big(-\frac{\mu T^{\beta}}{8c^{\prime}L}\Big)[\ell_{\mathcal{H}}(w_{0})-\ell^{*}]+\frac{G^{2}}{2\mu T^{2-2\beta}}+\frac{45\kappa G^{2}}{\mu},$ $$

where (a) uses the stepsize $\gamma=\frac{1}{c^{\prime}LHT^{1-\beta}}$, (b) uses Lemma [5](https://arxiv.org/html/2510.04432v1#Thmlemma5) and $c^{\prime}\geq 4\sqrt{2}$.

### Appendix F Experiment Details

#### F.1 Dirichlet-based partition strategies

We adopt the Dirichlet-based partitioning scheme (Wang et al., 2020b) to simulate heterogeneous client data distributions for CIFAR-10. Specifically, we partition each dataset across clients using a Dirichlet-based distribution over class labels. In this setting, both the number of data points and the class proportions are imbalanced across clients. Specifically, we simulate a heterogeneous partition into $n$ clients by drawing class proportions from a Dirichlet distribution:

$$ $(p_{1,k},p_{2,k},\dots,p_{10,k})\sim\mathrm{Dir}(\alpha_{1},\alpha_{2},\dots,\alpha_{10}),$ $$

where $p_{c,k}$ denotes the proportion of training instances of class $c\in\{1,2,\ldots,10\}$ assigned to client $k$.The distribution $\mathrm{Dir}_{10}(\cdot)$ is the $10$-dimensional Dirichlet distribution. We set $\alpha_{1}=\alpha_{2}=\dots=\alpha_{K}=\alpha$ to induce heterogeneity.

As a property of the Dirichlet distribution, when $\alpha_{k}<1$, the sampled class proportions tend to concentrate near the corners and edges of the probability simplex, so that clients receive data from only a few dominant classes, thereby simulating severe label imbalance and statistical heterogeneity—common characteristics of practical federated learning environments.

Based on the sampled proportions $\{p_{c,k}\}$, we allocate the training data to each client accordingly. For evaluation, we use the original test set from each dataset as a global test set to ensure a fair comparison across all methods.

The number of training samples per client is the same across 16 clients. Since CIFAR-10 has 50,000 training examples, we assign each client $50,000/16=3,125$ training samples.

#### F.2 Model Details

Table [4](https://arxiv.org/html/2510.04432v1#A6.T4) presents the detailed architecture of ResNet-20 with group normalization.

**Table 4: Architecture of ResNet-20 with Group Normalization (GN) for CIFAR-10**
| Stage | Output Size | Layers |
| --- | --- | --- |
| Input | $32\times 32$ | $3\times 3$ conv, 16 filters, stride 1 |
| Stage 1 | $32\times 32$ | 3 $\times$ [ $3\times 3$ conv, 16 filters + GN($G=4$) + ReLU ] |
| Stage 2 | $16\times 16$ | 3 $\times$ [ $3\times 3$ conv, 32 filters + GN($G=8$) + ReLU ] |
| Stage 3 | $8\times 8$ | 3 $\times$ [ $3\times 3$ conv, 64 filters + GN($G=8$) + ReLU ] |
| Output | $1\times 1$ | Global average pooling, FC-10, softmax |

#### F.3 Train Schemes

##### Preprocess of CIFAR-10:

For preprocessing the images in the CIFAR-10 datasets, we follow the standard data augmentation and normalization procedures. Specifically, we apply random cropping and horizontal flipping for data augmentation. For normalization, each color channel is standardized by subtracting the mean and dividing by the standard deviation of that channel. This ensures that the input images have zero mean and unit variance per channel, which is a common practice to stabilize and accelerate training.

##### Local Update:

We perform one epoch of local updates per client when $\alpha=0.1$, and two epochs of local updates per client when $\alpha=1,10$. Note that each epoch consists of multiple mini-batch SGD iterations, where each SGD step uses a batch size of 64. Therefore, we run FedRo with

$$ $H=\left\lfloor\tfrac{1\times 3125}{64}\right\rfloor=49$ $$

local SGD steps per round for $\alpha=0.1$, and with

$$ $H=\left\lfloor\tfrac{2\times 3125}{64}\right\rfloor=98$ $$

local SGD steps per round for $\alpha=1,10$.

##### Weight Decay:

We use L2 weight decay, i.e., and apply SGD to the cross-entropy loss with L2 regularizer $\tfrac{\mu}{2}\|w\|_{2}^{2}$ of the model parameter $w\in\mathbb{R}^{d}$. In our experiments, we set $\mu=5\times 10^{-4}$.

##### Learning Rate Schedule:

We use a step-wise diminishing learning rate schedule as follows.

$$ $\gamma_{t}=\begin{cases}\gamma_{0},&0\leq t<\tfrac{T}{2},\[6.0pt] 0.1\,\gamma_{0},&\tfrac{T}{2}\leq t<\tfrac{3T}{4},\[6.0pt] 0.01\,\gamma_{0},&\tfrac{3T}{4}\leq t\leq T,\end{cases}$ (46) $$

where $T$ denotes the total number of communication rounds, and $\gamma_{0}$ is fine-tuned from $\{0.5,0.2,0.1,0.05\}$.

## Peer Reviews

confidence: 5
contribution: 4
initial_rating: 6
presentation: 3
questions: The theoretically optimal aggregator ($\hat{f}$-Krum $\circ$ $\hat{f}$-NNM) appears computationally heavy for large $n$ and $d$, involving $O(n^2 d)$ operations per round. What are your thoughts on developing more computationally efficient aggregators (e.g., using approximate nearest neighbor search or sampling) that can still preserve, or nearly preserve, the theoretical guarantees? Would such approximations fit into your current theoretical framework?

Your experiments use a simple Gaussian noise attack. How do you expect your theoretical findings and the observed trade-off to hold under more complex and adaptive Byzantine attacks, such as those designed to mimic honest updates or perform model poisoning? Could such attacks potentially alter the established lower or upper bounds, for example, by affecting the heterogeneity constant $G^2$?

The convergence upper bound (Theorem 5) is derived under the PL condition, leading to an asymptotic error floor of $\mathcal{O}\big(\frac{\hat{f}G^2}{n-f-\hat{f}}\big)$. Can you provide any intuition or discussion on whether the core trade-off—that the asymptotic error floor scales with $\frac{\hat{f}}{n-f-\hat{f}}$—would still hold in non-PL settings, perhaps under different or weaker assumptions?
soundness: 4
strengths: Novel Problem Formulation: Systematically studying the effect of the estimated number of Byzantine clients ($\hat{f}$) is a highly original and important direction.

Theoretical Completeness: The paper provides a complete minimax analysis, with tight lower and upper bounds for both aggregation error and algorithm convergence, under both underestimation ($\hat{f} < f$) and non-underestimation ($\hat{f} \geq f$) scenarios. The bounds, proportional to $\frac{\hat{f}}{n-f-\hat{f}}$, are rigorously derived.

Practical Relevance: The theoretical trade-off is clearly demonstrated and validated through experiments on a standard benchmark (CIFAR-10), connecting theory with practice.

Algorithmic Insight: The analysis of the composite aggregator ($\hat{f}$-Krum $\circ$ $\hat{f}$-NNM) provides a constructive method to achieve the order-optimal bound.
summary: This paper provides a systematic theoretical analysis of the impact of estimating the number of Byzantine clients in Federated Learning (FL). The authors consider a scenario where an aggregator is chosen with a robustness parameter $\hat{f}$ (the estimated maximum number of Byzantine clients it can tolerate), while the true number is $f$. Their key contributions are:

Underestimation Risk: They rigorously prove that underestimation ($\hat{f} < f$) can lead to arbitrarily poor performance and divergence, even under favorable conditions like the Polyak-Łojasiewicz (PL) inequality.

Minimax Optimal Bounds for Non-Underestimation: For the non-underestimation case ($\hat{f} \geq f$), they establish matching lower and upper bounds (i.e., minimax optimal rates) for both the aggregation error and the convergence rate of the Federated Robust Averaging (FedRo) algorithm. These bounds are proportional to $\frac{\hat{f}}{n - f - \hat{f}}$.

Fundamental Trade-off: This bound reveals a fundamental trade-off: while an aggregator with a larger $\hat{f}$ can tolerate a wider range of attacks (any $f \leq \hat{f}$), its performance deteriorates when the actual number of attackers $f$ is small, as the error bound increases with $\hat{f}$.

Optimal Algorithm: They propose a novel composite aggregator ($\hat{f}$-Krum $\circ$ $\hat{f}$-NNM) that is proven to achieve the order-optimal upper bound without prior knowledge of the true $f$.

Empirical Validation: Experiments on CIFAR-10 validate the theoretical trade-off, showing performance collapse when $\hat{f} < f$ and performance degradation as $\hat{f}$ increases beyond $f$.
weaknesses: Computational Complexity of Optimal Aggregator: While the composite aggregator ($\hat{f}$-Krum $\circ$ $\hat{f}$-NNM) is theoretically optimal, it is computationally expensive. The per-round cost involves nearest neighbor searches for all clients, which may be prohibitive for very large-scale systems or high-dimensional models. The paper does not discuss efficient approximations or the practical scalability of this aggregator.

Limited Empirical Scope: The experiments, while supportive, are limited to one dataset (CIFAR-10), one model (ResNet-20), and one type of attack (Gaussian noise). Broader experimentation with more datasets (e.g., CIFAR-100, FEMNIST), model architectures, and sophisticated Byzantine attacks (e.g., label-flipping, backdoor) would strengthen the empirical validation.

Assumption of PL Condition: The convergence analysis for the upper bound (Theorem 5) relies on the Polyak-Lojasiewicz (PL) condition to achieve a global convergence rate. While the PL condition holds for some machine learning problems, it is a relatively strong assumption. Discussing the plausibility of this assumption in FL settings or exploring convergence under weaker conditions (e.g., just smoothness) would be valuable.

---

confidence: 5
contribution: 3
initial_rating: 4
presentation: 3
questions: My detailed questions are outlined in the section above; please refer to them. If the authors can fully address my concerns, I will consider adjusting my score accordingly.
soundness: 2
strengths: 1. The investigation of the impact of under- and over-estimating the number of Byzantine clients in the context of Byzantine attacks is a relevant and important topic for the field of Byzantine-robust federated learning.

2. This paper is well-written, clear, and theoretically sound.
summary: This paper investigates the effect of underestimation and overestimation of the number of Byzantine clients and highlights the importance of accurately estimating the Byzantine size. The authors theoretically prove and empirically validate that underestimation can lead to divergence under Byzantine attacks, while overestimation results in a trade-off: a larger estimated Byzantine size enhances robustness under Byzantine attacks but degrades performance when there are no or fewer Byzantine clients.
weaknesses: 1. The theoretical results in Theorems 1 and 3 do not fully support the conclusion that underestimation leads to arbitrarily large aggregation and convergence errors, as they apply only to a specific robust aggregator, not all such aggregators. If a different robust aggregator is used, the effect of underestimation may not hold. This represents a notable limitation of the paper. Can the authors generalize the results in Theorems 1 and 3 to all robust aggregators to address this issue?

2. There is a discrepancy between the theoretical analysis and the empirical results, as the former is conducted in a deterministic setting, while the latter is based on a stochastic setting. This gap is significant, as stochastic noise can substantially affect the performance of FedRo and lead to different convergence properties. Can the authors extend the analysis to address this gap?

3. In Table 1, the robustness coefficient $\kappa$ for the combination of $\hat{f}$-Krum and $\hat{f}$-NNM matches the lower bound in order. Why does the authors not use that aggregator in experiments? The reviewer would like to see the results of using $\hat{f}$-Krum $\circ$ $\hat{f}$-NNM in experiments.

4. In Line 48, the authors claim that "Existing works typically require estimating the actual number $f$ or the fraction of the Byzantine clients to select the maximum number $\hat{f}$ that the aggregator can tolerate." To my knowledge, the tolerable maximum number of Byzantine clients (i.e., the breakdown point) for some robust aggregators is independent of the actual number $f$ or fraction of Byzantine clients, meaning that these terms do not need to be estimated in advance for such aggregators. For instance, $\frac{n}{2}$ for CWMed, $\frac{n-2}{2}$ for CWTM, and $\frac{n}{10}$ for centered clipping, with respect to the breakdown point. The authors should revise this statement to make it more precise and rigorous.

5. In line 237, the authors claim that "since $\kappa$ of the commonly used aggregators like GM, CWTM, CWMed, and Krum do not match the lower bound even in the simple special case of $f = \hat{f}$." This statement is incorrect. As noted in Remark 2 of Allouah et al. (2023), CWTM does match the lower bound in order. The reviewer suggests that the authors carefully verify this statement.

6. There are several typos in this paper. For instance, in line 225, $\frac{\hat{f}}{n - 2f}$ should be $\frac{\hat{f}}{n - 2\hat{f}}$, and in line 226, $\frac{\hat{f}}{n - 2\hat{f}}$ should be $\frac{\hat{f}}{n - \hat{f}}$. The authors are advised to carefully review the paper to address these and prevent any similar issues.

---

confidence: 5
contribution: 2
initial_rating: 4
presentation: 3
questions: - Since the underestimation result follows the breakdown-point logic, what is the extra conceptual significance here? 

see weaknesses
soundness: 4
strengths: - Clear split between two regimes: underestimation can be catastrophic; otherwise there is a tight, quantified floor.
- Matching lower and upper bounds
- The dependence on both \(f\) and \(\hat f\) is explicit, which clarifies the cost of being conservative.
summary: The paper studies Byzantine-robust federated learning when the server only knows an estimate \(\hat f\) of the number of Byzantine clients (the true number is \(f\)). 
Main takeaways: (i) if we underestimate  (\(\hat f < f\)), aggregation / training can become arbitrarily bad; (ii) if we do not underestimate (\(\hat f \ge f\)), the best-possible error (and convergence floor) scales like
\[
\kappa = \Theta\!\left(\frac{\hat f}{\,n - f - \hat f\,}\right),
\]
with matching lower/upper bounds and a simple construction that achieves this rate up to constants.
weaknesses: - The underestimation impossibility is not really new: it is closely tied to the **breakdown point** in robust statistics.  
  If the true contamination $f/n$ exceeds the method's breakdown (here essentially $\hat f/n$), you can get unbounded error.  
  So this part feels more like transferring a known concept, rather than introducing a new phenomenon.

- Novelty in the *order* of the bound is modest. Away from edges, it matches the trivial (previously known) bound up to constants.  
  Precisely, for a constant $c \in (0, \tfrac{1}{2})$ such that  
  $$
  \hat f \le \big(\tfrac{1}{2} - c\big)\,n 
  \quad \text{and} \quad
  f + \hat f \le (1 - c)\,n,
  $$
  both denominators are $\Theta(n)$, and  
  $$
  \frac{\hat f/(n - f - \hat f)}{\hat f/(n - 2\hat f)}
  \;=\; \frac{n - 2\hat f}{\,n - f - \hat f\,}
  \;=\; \frac{1}{\,1 + \frac{\hat f - f}{\,n - 2\hat f\,}\,}.
  $$
  This ratio stays bounded between two positive constants (and $<1$ when $\hat f > f$),  
  so the two expressions are of the *same order*.

- They only separate near the **edges**:
  - $f + \hat f \to n$: the paper’s denominator $n - f - \hat f$ collapses $\Rightarrow$ larger floor than the trivial count.  
  - $\hat f \to n/2$: the trivial denominator $n - 2\hat f$ collapses $\Rightarrow$ trivial bound blows up sooner.  
  - **Underestimation** $\hat f < f$: the paper (consistent with breakdown) shows no finite guarantee, while the trivial bound misleadingly remains finite.

- Experiments could be broader; I appreciate the paper is from a theoretical nature so this is a minor issue for me.


Decision: Reject