mlsanityData to 14 Oct 2026

Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

arXiv 2309.13591 ↗First posted 24 Sep 2023cs.LG cs.DC math.OCcited by 26

Not on the map. Why?

Abstract (arXiv)

The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, established lower bounds on the learning error are essentially vacuous and greatly mismatch empirical observations. This is because the heterogeneity model considered is too restrictive and does not cover basic learning tasks such as least-squares regression. We consider in this paper a more realistic heterogeneity model, namely (G,B)-gradient dissimilarity, and show that it covers a larger class of learning problems than existing theory. Notably, we show that the breakdown point under heterogeneity is lower than the classical fraction 1/2. We also prove a new lower bound on the learning error of any distributed learning algorithm. We derive a matching upper bound for a robust variant of distributed gradient descent, and empirically show that our analysis reduces the gap between theory and practice.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). Builds on 27 of its 37 references that are in the map. First posted on arXiv 24 Sep 2023.

Builds on

27 of 37 references.

References · 27

  1. 2018Federated Optimization in Heterogeneous Networkscited by 2,987
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  3. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 711
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  6. 2018The Hidden Vulnerability of Distributed Learning in Byzantiumcited by 329
  7. 2019Robust Aggregation for Federated Learningcited by 317
  8. 2019A Little Is Enough: Circumventing Defenses For Distributed Learningcited by 288
  9. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  10. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  11. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  12. 2019Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulationcited by 141
15 more
  1. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  2. 2020Byzantine-Robust Learning on Heterogeneous Datasets via Bucketingcited by 128
  3. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  4. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  5. 2021Differentially Private Federated Learning on Heterogeneous Datacited by 74
  6. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 65
  7. 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
  8. 2017Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descentcited by 59
  9. 2020Byzantine-Resilient Non-Convex Stochastic Gradient Descentcited by 57
  10. 2020Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)cited by 54
  11. 2015Robust Regression via Hard Thresholdingcited by 39
  12. 2021Approximate Byzantine Fault-Tolerance in Distributed Optimizationcited by 28
  13. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  14. 2021Robust Training in High Dimensions via Block Coordinate Geometric Median Descentcited by 20
  15. 2017On the linear convergence of the stochastic gradient method with constant step-sizecited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 9; 2025: 8; 2026: 9.

26 papers.

Sort:

By area:

  1. 2024The Utility and Complexity of in- and out-of-Distribution Machine Unlearningcited by 20
  2. 2024Achieving Byzantine-Resilient Federated Learning via Layer-Adaptive Sparsified Model Aggregationcited by 15
  3. 2025Detecting Backdoor Attacks in Federated Learning via Direction Alignment Inspectioncited by 13
  4. 2024Adaptive Gradient Clipping for Robust Federated Learningcited by 11
  5. 2024Unified Breakdown Analysis for Byzantine Robust Gossipcited by 8
  6. 2025Towards Trustworthy Federated Learning with Untrusted Participantscited by 8
  7. 2024SoK: Blockchain-Based Decentralized AI (DeAI)cited by 6
  8. 2024Fine-Tuning Personalization in Federated Learning to Mitigate Adversarial Clientscited by 5
  9. 2024A survey on secure decentralized optimization and learningcited by 4
  10. 2025ByzFL: Research Framework for Robust Federated Learningcited by 4
  11. 2024The poison of dimensionalitycited by 3
  12. 2025Bant: Byzantine Antidote via Trial Function and Trust Scorescited by 3
14 more
  1. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  2. 2025Reconciling Communication Compression and Byzantine-Robustness in Distributed Learningcited by 1
  3. 2026Byzantine Machine Learning: MultiKrum and an optimal notion of robustnesscited by 1
  4. 2026mathsfVISTA: Decentralized Machine Learning in Adversary Dominated Environmentscited by 1
  5. 2026On the Gradient Heterogeneity Dynamics of Adversarially Robust Federated Regressioncited by 1
  6. 2024LiD-FL: Towards List-Decodable Federated Learningcited by 0
  7. 2025FL-CLEANER: byzantine and backdoor defense by CLustering Errors of Activation maps in Non-iid fedErated leaRningcited by 0
  8. 2025GRANITE : a Byzantine-Resilient Dynamic Gossip Learning Frameworkcited by 0
  9. 2026From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similaritycited by 0
  10. 2026Byzantine-Robust Optimization under (L0, L1)-Smoothnesscited by 0
  11. 2026Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Boundscited by 0
  12. 2026Defending Against Backdoor Attacks via Alignment Checking in Model-Contrastive Federated Learningcited by 0
  13. 2026Robustifying Asynchronous SGD via Soft Throttlingcited by 0
  14. 2026FUSE: Fairness-aware Update Screening against Byzantine Exploitation in q-Fair Federated Learningcited by 0