Practical Validity Conditions for Byzantine-Tolerant Federated Learning
For federated learning systems, this work addresses the impracticality of convex validity by providing a relaxed geometric condition that is achievable with majority honesty and supports a wider range of aggregation rules.
The paper introduces a relaxed minimum enclosing ball (MEB) validity condition for Byzantine-tolerant federated learning, achieving dimension-independent resilience with a majority of honest clients (n > 2t). It provides an optimal MinMax-MEB rule with c < √2 and proves guarantees for standard aggregators, offering a practical alternative to convex validity.
Robust aggregation is the core operation in Byzantine-tolerant federated learning. To ensure the quality of aggregation independently of data distribution or attacks, validity conditions are needed. They provide geometric guarantees of where the output of the aggregation must lie. The widespread convex validity requires the output to lie in the convex hull of the honest vectors. Although this guarantee is strong in theory, it is poorly suited to modern federated learning systems, as it has dimension-dependent resilience and excludes many practical aggregation rules. We introduce the minimum enclosing ball (MEB) validity condition for robust aggregation, as well as its multiplicative relaxation, $c$-MEB validity, where $c$ is a constant. We show that exact MEB validity still suffers from limited resilience, while relaxed $c$-MEB validity is achievable if a majority of clients is honest, i.e. $n>2t$. We give an optimal MinMax-MEB rule for the relaxed condition with the bound $c<\sqrt{2}$ and prove explicit relaxed-MEB guarantees for standard aggregators including minimum-diameter averaging, medoid and geometric median. Finally, we relate MEB validity to convex, relaxed-convex and box validity studied in prior literature, thus providing a systematic map of geometric validity conditions for Byzantine-robust aggregation. Our results show that relaxed MEB validity connects validity conditions in distributed computing and Byzantine-tolerant aggregation rules, and offers a practical alternative to convex validity.