ML Security PapersByzantine Machine Learning: MultiKrum and an optimal notion of robustness
Gilles Bareilles 1, Wassim Bouaziz 2, Julien Fageot 3, El Mahdi El Mhamdi 1
Published on arXiv
2602.03899
Data Poisoning Attack
OWASP ML Top 10 — ML02
Key Finding
MultiKrum's robustness bounds are provably never worse than Krum's and superior in realistic Byzantine regimes, with experimental validation confirming the tightness of the derived lower bound.
MultiKrum
Novel technique introduced
Aggregation rules are the cornerstone of distributed (or federated) learning in the presence of adversaries, under the so-called Byzantine threat model. They are also interesting mathematical objects from the point of view of robust mean estimation. The Krum aggregation rule has been extensively studied, and endowed with formal robustness and convergence guarantees. Yet, MultiKrum, a natural extension of Krum, is often preferred in practice for its superior empirical performance, even though no theoretical guarantees were available until now. In this work, we provide the first proof that MultiKrum is a robust aggregation rule, and bound its robustness coefficient. To do so, we introduce $κ^\star$, the optimal *robustness coefficient* of an aggregation rule, which quantifies the accuracy of mean estimation in the presence of adversaries in a tighter manner compared with previously adopted notions of robustness. We then construct an upper and a lower bound on MultiKrum's robustness coefficient. As a by-product, we also improve on the best-known bounds on Krum's robustness coefficient. We show that MultiKrum's bounds are never worse than Krum's, and better in realistic regimes. We illustrate this analysis by an experimental investigation on the quality of the lower bound.
Key Contributions
- First formal proof that MultiKrum is a robust aggregation rule under the Byzantine threat model, filling a theoretical gap despite its widespread empirical use
- Introduction of κ* (optimal robustness coefficient), a tighter notion of aggregation robustness compared to previously adopted formulations
- Upper and lower bounds on MultiKrum's κ* showing it is never worse than Krum and strictly better in realistic regimes
🛡️ Threat Analysis
Byzantine attacks in federated learning — malicious clients sending arbitrary model updates — fall squarely under ML02. MultiKrum is a robust aggregation rule (defense) designed to tolerate such adversaries, and this paper provides the first formal proof of its robustness with bounds on the new optimal robustness coefficient κ*.