mlsanityData to 7 Oct 2026

Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates

arXiv 2310.09804 ↗First posted 15 Oct 2023math.OC cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

Byzantine robustness is an essential feature of algorithms for certain distributed optimization problems, typically encountered in collaborative/federated learning. These problems are usually huge-scale, implying that communication compression is also imperative for their resolution. These factors have spurred recent algorithmic and theoretical developments in the literature of Byzantine-robust learning with compression. In this paper, we contribute to this research area in two main directions. First, we propose a new Byzantine-robust method with compression - Byz-DASHA-PAGE - and prove that the new method has better convergence rate (for non-convex and Polyak-Lojasiewicz smooth optimization problems), smaller neighborhood size in the heterogeneous case, and tolerates more Byzantine workers under over-parametrization than the previous method with SOTA theoretical convergence guarantees (Byz-VR-MARINA). Secondly, we develop the first Byzantine-robust method with communication compression and error feedback - Byz-EF21 - along with its bidirectional compression version - Byz-EF21-BC - and derive the convergence rates for these methods for non-convex and Polyak-Lojasiewicz smooth case. We test the proposed methods and illustrate our theoretical findings in the numerical experiments.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 68 of its 106 references that are in the map. First posted on arXiv 15 Oct 2023.

Builds on

68 of 106 references.

References · 68

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  3. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  4. 2019Local Model Poisoning Attacks to Byzantine-Robust Federated Learningcited by 479
  5. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  6. 2018Sparsified SGD with Memorycited by 373
  7. 2018The Hidden Vulnerability of Distributed Learning in Byzantiumcited by 324
  8. 2019Robust Aggregation for Federated Learningcited by 314
  9. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  10. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  11. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  12. 2019A Little Is Enough: Circumventing Defenses For Distributed Learningcited by 285
38 more
  1. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  2. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  3. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
  4. 2018The Convergence of Sparsified Gradient Methodscited by 228
  5. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  6. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 218
  7. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 179
  8. 2020Privacy and Robustness in Federated Learning: Attacks and Defensescited by 163
  9. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
  10. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  11. 2020On Biased Compression for Distributed Learningcited by 140
  12. 2020Learning from History for Byzantine Robust Optimizationcited by 137
  13. 2019Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulationcited by 136
  14. 2016Distributed Mean Estimation with Limited Communicationcited by 134
  15. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  16. 2020Byzantine-Robust Learning on Heterogeneous Datasets via Bucketingcited by 125
  17. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  18. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  19. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
  20. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  21. 2019Natural Compression for Distributed Deep Learningcited by 88
  22. 2018Byzantine Stochastic Gradient Descentcited by 81
  23. 2019Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attackscited by 79
  24. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  25. 2018DRACO: Byzantine-resilient Distributed Training via Redundant Gradientscited by 74
  26. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  27. 2023Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneitycited by 64
  28. 2020Linearly Converging Error Compensated SGDcited by 61
  29. 2021Distributed Deep Learning in Open Collaborationscited by 58
  30. 2020Byzantine-Resilient Non-Convex Stochastic Gradient Descentcited by 56
  31. 2018Distributed learning with compressed gradientscited by 53
  32. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 50
  33. 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 45
  34. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  35. 2019DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregationcited by 44
  36. 2020Adaptive Gradient Quantization for Data-Parallel SGDcited by 43
  37. 2020A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!cited by 41
  38. 2021Rethinking gradient sparsification as total error minimizationcited by 41

50 most cited of 68 All 68 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 4; 2026: 5.

12 papers.

  1. 2024A survey on secure decentralized optimization and learningcited by 4
  2. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  3. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 1
  4. 2024Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filteringcited by 1
  5. 2025Reconciling Communication Compression and Byzantine-Robustness in Distributed Learningcited by 1
  6. 2025Screen Before You Fetch: Compressed Byzantine Screening for Decentralized Learning on the Edge-Cloud Continuumcited by 1
  7. 2025Beyond Trade-offs: A Unified Framework for Privacy, Robustness, and Communication Efficiency in Federated Learningcited by 0
  8. 2026From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similaritycited by 0
  9. 2026Byzantine-Robust and Communication-Efficient Distributed Training: Compressive and Cyclic Gradient Codingcited by 0
  10. 2026On the Gradient Heterogeneity Dynamics of Adversarially Robust Federated Regressioncited by 0
  11. 2026Robustifying Asynchronous SGD via Soft Throttlingcited by 0
  12. 2026Compression Footprints as Security Signals for Model-Poisoning Defense in Federated Learningcited by 0