# Towards Federated Learning with Byzantine-Robust Client Weighting
## Appendix D Proof of Lemma 1  
Initially, we assume that each machine \(i\in[K]\) stores \(n_{i}\) examples derived from one-dimensional random variable \(x\sim\mathcal{D}\) such that \(\mathcal{D}\) is the unknown distribution from which we sample the distributed dataset, and \(x\) is \(v\)-sub-exponential. Define\[\mu=\mathbb{E}[x],\] \[x^{i,j}=j\text{th sample of the $i$th client}, \quad\bar{x}^{i}=\frac{1}{n_{i}}\sum_{j=1}^{n_{i}}x^{i,j},\] \[\mathcal{B}=\text{All Byzantine machines}, \quad\mathcal{M}=[K]\setminus\mathcal{B},\] \[\mathcal{T}=\text{All trimmed machines}, \quad\mathcal{R}=[K]\setminus\mathcal{T}.\]  
As done in the proof of Lemma 3 in [12], using [PERSON]'s inequality, we get the following for all \(t\geq 0\) and \(i\in[K]\):  
\[\Pr\Bigl{(}\left|\bar{x}^{i}-\mu\right|\geq t\Bigr{)}\leq 2\exp\left(-n_{i} \min\biggl{\{}\frac{t}{2v},\frac{t^{2}}{2v^{2}}\biggr{\}}\right)\leq 2\exp \left(-\min_{i\in[K]}\{n_{i}\}\min\biggl{\{}\frac{t}{2v},\frac{t^{2}}{2v^{2}} \biggr{\}}\right). \tag{111}\]  
Then, by union bound, we know that  
\[\Pr\biggl{(}\max_{i\in\mathcal{R}}\Bigl{\{}\left|\bar{x}^{i}-\mu\right| \biggr{\}}\geq t\biggr{)}\leq 2(1-2\beta)K\exp\biggl{(}-\min_{i\in[K]}\{n_{i} \}\min\biggl{\{}\frac{t}{2v},\frac{t^{2}}{2v^{2}}\biggr{\}}\biggr{)}. \tag{112}\]  
Our version of the trimmed mean of means computes:  
\[\texttt{trmean}_{\beta}\{\bar{x}^{i}:i\in[K]\}=\frac{\sum_{i\in\mathcal{R}} \bar{n}_{i}\bar{x}^{i}}{\sum_{i\in\mathcal{R}}\bar{n}_{i}}.\]  
From this definition, and assuming Inequality (112) does not hold, we obtain:  
\[ \begin{split}&\left|\texttt{trmean}_{\beta}\{\bar{x}^{i}:i\in[m] \}-\mu\right|=\biggl{|}\frac{\sum_{i\in\mathcal{R}}\bar{n}_{i}\bar{x}^{i}}{ \sum_{i\in\mathcal{R}}\bar{n}_{i}}-\mu\biggr{|}=\frac{1}{\sum_{i\in\mathcal{R} }\bar{n}_{i}}\biggl{|}\sum_{i\in\mathcal{R}}\bar{n}_{i}(\bar{x}^{i}-\mu)\right| \\ &\leq\frac{1}{\sum_{i\in\mathcal{R}}\bar{n}_{i}}\sum_{i\in \mathcal{R}}\bar{n}_{i}\Big{|}\bar{x}^{i}-\mu\Bigr{|}\leq\frac{U}{\sum_{i\in \mathcal{R}}\bar{n}_{i}}\sum_{i\in\mathcal{R}}\Bigl{|}\bar{x}^{i}-\mu\Bigr{|} \leq\frac{(1-2\beta)UK\max_{i\in\mathcal{R}}\left\{\left|\bar{x}^{i}-\mu\right| \right\}}{(1-2\beta)K\min_{i\in[K]}\{\bar{n}_{i}\}}\\ &\leq\frac{tU}{\min_{i\in[K]}\{\bar{n}_{i}\}}\end{split}  \tag{113}\]  
Based on Assumption 5, we can apply inequalities (112) and (113) to the \(k\)-th partial derivative of the loss functions. To extend this result to all \(w\in\mathcal{W}\) and all the \(d\) coordinates, we proceed as in [12] by using the union bound and a covering net argument [23]. Let \(\mathcal{W}_{\delta}=\left\{w^{1},w^{2},\ldots,w^{N_{\delta}}\right\}\) be a finite subset of \(\mathcal{W}\) such that for any \(w\in\mathcal{W}\), there exists \(w^{l}\in\mathcal{W}_{\delta}\) such that \(\left\|w^{l}-w\right\|\leq\delta\). According to the standard covering net results [23], we know that \(N_{\delta}\leq\left(1+\frac{D}{\delta}\right)^{d}\) and obtain:  
\[ \begin{split}&\Pr\biggl{(}\left\|\mathbf{g}(w)-\
abla F(w)\right\| \geq\sqrt{2d}\frac{tU}{\min_{i\in[K]}\{\bar{n}_{i}\}}+2\sqrt{2}\frac{U}{\min_{ i\in[K]}\{\bar{n}_{i}\}}\delta\widehat{L}\biggr{)}\\ &\leq 2(1-2\beta)KdN_{\delta}\exp\biggl{(}-\min_{i\in[K]}\{n_{i}\}\min \biggl{\{}\frac{t}{2v},\frac{t^{2}}{2v^{2}}\biggr{\}}\biggr{)}.\end{split}