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 \textit{Byzantine failures}, allowing arbitrarily corrupted communication, or as \textit{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: \textit{How do these threat models impact generalization?} We show, for the first time, a fundamental gap in gene