Byzantine Failures Harm the Generalization of Robust Distributed Learning Algorithms More Than Data Poisoning
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914096510664704 |
|---|---|
| author | Boudou, Thomas Bars, Batiste Le Gupta, Nirupam Bellet, Aurélien |
| author_facet | Boudou, Thomas Bars, Batiste Le Gupta, Nirupam Bellet, Aurélien |
| contents | 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? Empirical evidence suggests a gap, yet it remains unclear whether it is unavoidable or merely an artifact of suboptimal attacks. 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 $\varTheta ( \frac{f}{n-f} )$, with $f$ out of $n$ workers misbehaving; whereas $\textit{(ii)}$ under Byzantine failures, the degradation is in $Ω\big( \sqrt{ \frac{f}{n-2f}} \big)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18020 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Byzantine Failures Harm the Generalization of Robust Distributed Learning Algorithms More Than Data Poisoning Boudou, Thomas Bars, Batiste Le Gupta, Nirupam Bellet, Aurélien Machine Learning Cryptography and Security 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? Empirical evidence suggests a gap, yet it remains unclear whether it is unavoidable or merely an artifact of suboptimal attacks. 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 $\varTheta ( \frac{f}{n-f} )$, with $f$ out of $n$ workers misbehaving; whereas $\textit{(ii)}$ under Byzantine failures, the degradation is in $Ω\big( \sqrt{ \frac{f}{n-2f}} \big)$. |
| title | Byzantine Failures Harm the Generalization of Robust Distributed Learning Algorithms More Than Data Poisoning |
| topic | Machine Learning Cryptography and Security |
| url | https://arxiv.org/abs/2506.18020 |