# Byzantine Machine Learning: MultiKrum and an optimal notion of robustness

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 3 Feb 2026.

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

- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Attack of the Tails: Yes, You Really Can Backdoor Federated Learning](https://mlsanity.com/paper/2007.05084/) (2020)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Wild Patterns Reloaded: A Survey of Machine Learning Security against Training Data Poisoning](https://mlsanity.com/paper/2205.01992/) (2022)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Poisoning Attacks on LLMs Require a Near-constant Number of Poison Samples](https://mlsanity.com/paper/2510.07192/) (2025)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)](https://mlsanity.com/paper/2008.00742/) (2020)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Manipulating Recommender Systems: A Survey of Poisoning Attacks and Countermeasures](https://mlsanity.com/paper/2404.14942/) (2024)
- [Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference](https://mlsanity.com/paper/2103.02860/) (2021)
- [Tournesol: A quest for a large, secure and trustworthy database of reliable human judgments](https://mlsanity.com/paper/2107.07334/) (2021)
- [Dim-Krum: Backdoor-Resistant Federated Learning for NLP with Dimension-wise Krum-Based Aggregation](https://mlsanity.com/paper/2210.06894/) (2022)
- [Unified Breakdown Analysis for Byzantine Robust Gossip](https://mlsanity.com/paper/2410.10418/) (2024)
- [Winter Soldier: Backdooring Language Models at Pre-Training with Indirect Data Poisoning](https://mlsanity.com/paper/2506.14913/) (2025)
- [Byzantine Fault Tolerance in Distributed Machine Learning : a Survey](https://mlsanity.com/paper/2205.02572/) (2022)
- [Krum Federated Chain (KFC): Using blockchain to defend against adversarial attacks in Federated Learning](https://mlsanity.com/paper/2502.06917/) (2025)
- [FedGreed: A Byzantine-Robust Loss-Based Aggregation Method for Federated Learning](https://mlsanity.com/paper/2508.18060/) (2025)
- [Inverting Gradient Attacks Makes Powerful Data Poisoning](https://mlsanity.com/paper/2410.21453/) (2024)
- [Improving (α, f)-Byzantine Resilience in Federated Learning via layerwise aggregation and cosine distance](https://mlsanity.com/paper/2503.21244/) (2025)

## Built on by (most cited first, 1 of 1)

- [Thermo-FL: Thermal-Aware Robust Federated Fine-Tuning of Large Language Models for Edge AI](https://mlsanity.com/paper/2608.21172/) (2026)

## Abstract (arXiv)

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 kappa^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.