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

arXiv:2506.18020v3 Announce Type: replace Abstract: Robust distributed learning algorithms aim to maintain reliable performance despite the presence of misbehaving workers. Such misbehaviors are commonly modeled as extit{Byzantine failures}, allowing arbitrarily corrupted communication, or as extit{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: extit{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 are based upon a tight algorithmic stability analysis of robust distributed learning. Specifically, with f out of n workers misbehaving, we prove that: extit{(i)} under data poisoning, the uniform algorithmic stability of a robust distributed learning algorithm

Source: arXiv cs.LG | 2026-07-07