# Towards Federated Learning with Byzantine-Robust Client Weighting
## 2 Materials and Methods
### Preprocessing Client-Declared Sample Sizes
#### 2.2.4 Convergence Analysis  
We split our analysis into two parts. In the first part, we analyze our truncation preprocessing step, showing how it bounds the skewness of the learning objective that may be caused by Byzantine clients. In the second part, we discuss stronger guarantees of convergence. Figure 1: Example plot of data generated by executing Algorithm 3 on unbalanced vector \(\mathbf{N}\) and \(\alpha^{*}=50\%\) (this vector corresponds to the partition used in our experiments; see Section 3.1 for details). Objective Function Skewness Bound  
After applying our _Preprocess_ procedure, we have the truncated number of samples per client, marked \(\{\hat{n}_{k}\}_{k\in[K]}\). We can trivially ensure that any algorithm instance works as expected by requiring that clients ignore samples that were truncated. That is, even if an honest (non-Byzantine) client \(k\) has \(n_{k}\) samples, it may use only \(\hat{n}_{k}\) samples during its \(ClientUpdate\). Although this solution always preserves the semantics of _any_ underlying algorithm, it does hurt convergence guarantees since the total number of samples decreases [Tables 5 and 6 in [PERSON] et al. [3]; [PERSON] et al. [12]; [PERSON] and [PERSON] [9]]. Interestingly, Theorem 3 in [PERSON] et al. [16] analyzes the baseline _FedAvg_ and shows that the convergence bound increases with \(max\,n_{k}/min\,n_{k}\) (marked there as \(\
u/\varsigma\)). This suggests that in some cases, unbalancedness itself deteriorates the convergence rate, a phenomenon that may be mitigated by truncation to some degree. Additionally, we note that when the clients' sample distributions are similar, the performance of federated averaging-based algorithms improves when honest clients use all their original \(n_{k}\) samples. Intuitively, this follows from the observation that _Aggregate_ procedures are generally composite mean estimators and \(ClientUpdate\) calls are likely to produce more accurate results given more samples. Lastly, as we have mentioned before, convergence is guaranteed, but we note that the optimization goal itself is inevitably skewed in our Byzantine scenario. The following theorem bounds this difference between the original weighted optimization goal (Equation (2)) and the new goal after truncation. In order to emphasize the necessity of this bound (in terms of Assumption 2), we use an overdot and tilde to signify unreliable and truncated values, respectively, as previously described in Section 2.1.2. **Theorem 3**. : _Given the same setup as in Equation (1) and a truncation bound \(U\), the following holds for all \(w\in\mathbb{R}^{d}\):_  
\[\left\|\frac{1}{\hat{n}}\sum_{i\in[K]}\hat{n}_{i}F_{i}(w)-\frac{1 }{\hat{n}}\sum_{i\in[K]}\tilde{n}_{i}F_{i}(w)\right\|\leq\] \[\left\|\sum_{i:n_{i}>U}\big{(}\frac{\hat{n}_{i}}{\hat{n}}-\frac{1 }{K}\big{)}F_{i}(w)+\big{(}\frac{1}{\hat{n}}-\frac{1}{\hat{n}}\big{)}\sum_{i: n_{i}\leq U}\mathcal{L}(Z_{i})\right\|\!,\]  
_where \(\mathcal{L}(Z_{i})\) is defined as \(\sum_{z\in Z_{i}}\ell(w;z)\)._  
Proof. : Using the fact that \(\hat{n}\leq UK\), we obtain:  
\[\left\|\frac{1}{\hat{n}}\sum_{i\in[K]}\hat{n}_{i}F_{i}(w)-\frac{1 }{\hat{n}}\sum_{i\in[K]}\hat{n}_{i}F_{i}(w)\right\|=\] \[\left\|\sum_{i:n_{i}>U}\frac{\hat{n}_{i}}{\hat{n}}F_{i}(w)+\frac{ 1}{\hat{n}}\sum_{i:n_{i}\leq U}\mathcal{L}(Z_{i})-\sum_{i:n_{i}>U}\frac{1}{ \hat{n}}F_{i}(w)-\frac{1}{\hat{n}}\sum_{i:n_{i}\leq U}\mathcal{L}(Z_{i})\right\|\leq\] \[\left\|\sum_{i:n_{i}>U}\big{(}\frac{\hat{n}_{i}}{\hat{n}}-\frac{1 }{K}\big{)}F_{i}(w)+\big{(}\frac{1}{\hat{n}}-\frac{1}{\hat{n}}\big{)}\sum_{i: n_{i}\leq U}\mathcal{L}(Z_{i})\right\|\!.\]  
From the bound in Theorem 3, we can clearly see how the coefficients in the left term, \((\hat{n}_{i}/\hat{n}-1/K)\), stem from unbalancedness in the values above the truncation threshold, whereas the coefficient in the right term, \((1/\hat{n}-1/\hat{n})\), accounts for the increase of relative weight of the values below the truncation threshold.