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 \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 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: \textit{(i)} under data poisoning, the uniform algorithmic stability of a robust distributed learning algorithm