mlsanityData to 14 Oct 2026

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

arXiv 2506.18020 ↗First posted 22 Jun 2025cs.LG cs.CR stat.MLcited by 2

On the map: LLM safety and security → Backdoor and data poisoning attacks

Abstract (arXiv)

Robust distributed learning algorithms aim to maintain reliable performance despite the presence of misbehaving workers. Such misbehaviors are commonly modeled as textitByzantine failures, allowing arbitrarily corrupted communication, or as textitdata 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: textitHow 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

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security. Builds on 30 of its 54 references that are in the map. First posted on arXiv 22 Jun 2025.

Builds on

30 of 54 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024On the Relevance of Byzantine Robust Optimization Against Data Poisoning1 May

Other references · 29

  1. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 711
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  4. 2019Local Model Poisoning Attacks to Byzantine-Robust Federated Learningcited by 493
  5. 2018The Hidden Vulnerability of Distributed Learning in Byzantiumcited by 329
  6. 2019A Little Is Enough: Circumventing Defenses For Distributed Learningcited by 288
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  8. 2019Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulationcited by 141
  9. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  10. 2020Byzantine-Robust Learning on Heterogeneous Datasets via Bucketingcited by 128
  11. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  12. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
17 more
  1. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  2. 2019Sharper bounds for uniformly stable algorithmscited by 93
  3. 2018Byzantine Stochastic Gradient Descentcited by 81
  4. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 65
  5. 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
  6. 2020Byzantine-Resilient Non-Convex Stochastic Gradient Descentcited by 57
  7. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  8. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
  9. 2021Approximate Byzantine Fault-Tolerance in Distributed Optimizationcited by 28
  10. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  11. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  12. 2020An Accurate, Scalable and Verifiable Protocol for Federated Differentially Private Averagingcited by 20
  13. 2022An Equivalence Between Data Poisoning and Byzantine Gradient Attackscited by 16
  14. 2024Adaptive Gradient Clipping for Robust Federated Learningcited by 11
  15. 2023On the Tradeoff between Privacy Preservation and Byzantine-Robustness in Decentralized Learningcited by 8
  16. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  17. 2024Generalization Error Matters in Decentralized Learning Under Byzantine Attackscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Dangerous Liaisons of Convex Learning and Non-Affine Aggregationcited by 0
  2. 2026Unveiling the Non-Monotonic Effect of Privacy on Generalization under Byzantine Robustnesscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024BadSampler: Harnessing the Power of Catastrophic Forgetting to Poison Byzantine-robust Federated Learning
  2. 2025A Practical and Secure Byzantine Robust Aggregator ↗
  3. 2024Regularized Robustly Reliable Learners and Instance Targeted Attacks
  4. 2022Robustly-reliable learners under poisoning attacks
  5. 2025Keeping up with dynamic attackers: Certifying robustness to adaptive online data poisoning
  6. 2024Certified Robustness to Data Poisoning in Gradient-Based Training
  7. 2024Data-Dependent Stability Analysis of Adversarial Training
  8. 2021FedCom: A Byzantine-Robust Local Model Aggregation Rule Using Data Commitment for Federated Learning