Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning

Robust distributed learning algorithms aim to maintain reliable performance despite the presence of misbehaving workers. Such misbehaviors are commonly modeled as *Byzantine failures*, allowing arbitrarily corrupted communication, or as *data poisoning*, a weaker form of corruption restricted to local training data. While prior work shows similar optimization guarantees for both models, an important question remains: *How do these threat models impact generalization?* We show, for the first time, a fundamental gap in generalization guarantees between the two threat models: Byzantine failures yield strictly worse rates than those achievable under data poisoning. Our findings leverage a tight algorithmic stability analysis of robust distributed learning. Specifically, we prove that: *(i)* under data poisoning, the uniform algorithmic stability of an algorithm with optimal optimization guarantees degrades by an additive factor of $\Theta ( \frac{f}{n-f} )$, with $f$ out of $n$ workers misbehaving; whereas *(ii)* under Byzantine failures, the degradation is in $\Omega \big( \sqrt{ \frac{f}{n-2f}} \big)$.

Training modern artificial intelligence requires multitudes of connected devices (or institutes) working together. However, some of these devices inevitably malfunction or get hacked. Researchers categorize these rogue devices into two groups: data poisoners, who feed the AI bad information but follow the training rules, and Byzantine attackers, who spy on communications and break all the rules. Researchers had previously developed a theory predicting that both types of attacks damaged the AI equally. This is surprising because Byzantine workers have more capabilities, and real-world tests consistently highlighted that AI models attacked by Byzantine devices performed significantly worse when tested on brand-new, unseen situations. We solve this paradox by providing the first mathematical proof showing why Byzantine attackers are more destructive to an AI’s performance guarantees. By proving this difference, our work provides a principled path for defending future AI systems.