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

arXiv: https://arxiv.org/abs/2510.04432 · HTML: https://mlsanity.com/paper/2510.04432/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 40 references that are in the map.
- First posted on arXiv 6 Oct 2025.

## Builds on (most cited first, 28 of 28)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Group Normalization](https://mlsanity.com/paper/1803.08494/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [How To Backdoor Federated Learning](https://mlsanity.com/paper/1807.00459/) (2018)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Federated Learning with Matched Averaging](https://mlsanity.com/paper/2002.06440/) (2020)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping](https://mlsanity.com/paper/2012.13995/) (2020)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [Attack of the Tails: Yes, You Really Can Backdoor Federated Learning](https://mlsanity.com/paper/2007.05084/) (2020)
- [Data Poisoning Attacks Against Federated Learning Systems](https://mlsanity.com/paper/2007.08432/) (2020)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification](https://mlsanity.com/paper/2112.06274/) (2021)
- [An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning](https://mlsanity.com/paper/2302.07173/) (2023)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [Achieving Byzantine-Resilient Federated Learning via Layer-Adaptive Sparsified Model Aggregation](https://mlsanity.com/paper/2409.01435/) (2024)
- [Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates](https://mlsanity.com/paper/2402.12780/) (2024)
- [Byzantine-robust Federated Learning through Spatial-temporal Analysis of Local Model Updates](https://mlsanity.com/paper/2107.01477/) (2021)
- [Byzantine-Robust Federated Learning with Variance Reduction and Differential Privacy](https://mlsanity.com/paper/2309.03437/) (2023)
- [Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy](https://mlsanity.com/paper/2108.11769/) (2021)
- [FedGreed: A Byzantine-Robust Loss-Based Aggregation Method for Federated Learning](https://mlsanity.com/paper/2508.18060/) (2025)
- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [A Methodology Establishing Linear Convergence of Adaptive Gradient Methods under PL Inequality](https://mlsanity.com/paper/2407.12629/) (2024)

## Abstract (arXiv)

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 of Byzantine clients, and thus accordingly select the aggregators with proper degree of robustness (i.e., the maximum number hatf 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 hatf and f. Specifically, we will show that underestimation (hatf<f) can lead to arbitrarily poor performance for both aggregators and federated learning. For non-underestimation (hatf≥ 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 hatf/(n-f-hatf) with n clients, which monotonically increases with larger hatf. This indicates a fundamental trade-off: while an aggregator with a larger robustness degree hatf can solve federated learning problems of wider range f∈ [0,hatf], the performance can deteriorate when there are actually fewer or even no Byzantine clients (i.e., f∈ [0,hatf)).