mlsanityData to 7 Oct 2026

Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds

arXiv 2604.10179 ↗First posted 11 Apr 2026math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Byzantine-robust distributed optimization relies on robust aggregation rules to mitigate the influence of malicious Byzantine workers. Despite the proliferation of such rules, a unified convergence analysis framework that accommodates general data heterogeneity is lacking. In this work, we provide a thorough convergence theory of Byzantine-robust distributed stochastic gradient descent (SGD), analyzing variants both with and without local momentum. We establish the convergence rates for nonconvex smooth objectives and those satisfying the Polyak-Lojasiewicz condition under a general data heterogeneity assumption. Our analysis reveals that while stochasticity and data heterogeneity introduce unavoidable error floors, local momentum provably reduces the error component induced by stochasticity. Furthermore, we derive matching lower bounds to demonstrate that the upper bounds obtained in our analysis are tight and characterize the fundamental limits of Byzantine resilience under stochasticity and data heterogeneity. Empirical results support our theoretical findings.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 36 of its 48 references that are in the map. First posted on arXiv 11 Apr 2026.

Builds on

36 of 48 references.

References · 36

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  3. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  4. 2019Advances and Open Problems in Federated Learningcited by 3,021
  5. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  6. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  7. 2018Federated Learning with Non-IID Datacited by 1,099
  8. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  9. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  10. 2019Robust Aggregation for Federated Learningcited by 314
  11. 2021A Field Guide to Federated Optimizationcited by 312
  12. 2019A Little Is Enough: Circumventing Defenses For Distributed Learningcited by 285
24 more
  1. 2018RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasetscited by 148
  2. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  3. 2020FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Datacited by 143
  4. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  5. 2020Byzantine-Robust Learning on Heterogeneous Datasets via Bucketingcited by 125
  6. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 100
  7. 2018Generalized Byzantine-tolerant SGDcited by 94
  8. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  9. 2018Byzantine Stochastic Gradient Descentcited by 81
  10. 2019Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attackscited by 79
  11. 2021Differentially Private Federated Learning on Heterogeneous Datacited by 74
  12. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 64
  13. 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
  14. 2020Byzantine-Resilient Non-Convex Stochastic Gradient Descentcited by 56
  15. 2021Quantized Federated Learning under Transmission Delay and Outage Constraintscited by 37
  16. 2023Momentum Benefits Non-IID Federated Learning Simply and Provablycited by 37
  17. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  18. 2020Byzantine-Resilient High-Dimensional Federated Learningcited by 27
  19. 2023Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneitycited by 25
  20. 2024Adaptive Gradient Clipping for Robust Federated Learningcited by 10
  21. 2022Communication-Efficient Federated Learning With Data and Client Heterogeneitycited by 9
  22. 2025Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneitycited by 6
  23. 2025Bant: Byzantine Antidote via Trial Function and Trust Scorescited by 3
  24. 2025Reconciling Communication Compression and Byzantine-Robustness in Distributed Learningcited by 1

Built on by

Not cited yet.