Approximation Guarantees for Robust Aggregation in Federated Learning

Byzantine-tolerant aggregation is a central challenge in federated learning, especially under heterogeneous client data where malicious updates may be statistically indistinguishable from honest but unusual clients. Robustness of aggregation algorithms is crucial to the quality of the final model. In this work, we study the robustness of the Byzantine-tolerant aggregation through the lens of centroid approximation, examining how closely an aggregation rule can match the average of honest client updates when up to $t$ of $n$ clients are Byzantine. We connect this objective to classical validity conditions from Byzantine agreement and show that validity alone is insufficient to guarantee good centroid approximation. Our main theoretical contribution is the first lower bound of $\sqrt{\min\{(n-t)/t,d\}}/2$ on the centroid approximation for aggregation under box validity and a matching upper bound of $2\sqrt{\min\{n,d\}}$ in the practically relevant case $n>2t$. In addition, we present a new algorithm that achieves a $2d$-approximation under convex validity, which also proves that the existing lower bound in the literature is tight. These results expose a fundamental tradeoff between validity conditions and approximation quality. We complement the theory with experiments in FedSGD and FedAvg under standard Byzantine attacks, showing that stronger validity improves stability, while tighter centroid approximation can improve accuracy in heterogeneous settings.