mlsanityData to 14 Oct 2026

Byzantine Stochastic Gradient Descent

arXiv 1803.08917 ↗First posted 23 Mar 2018cs.LG cs.DC cs.DScited by 81

Not on the map. Why?

Abstract (arXiv)

This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of the m machines which allegedly compute stochastic gradients every iteration, an α-fraction are Byzantine, and can behave arbitrarily and adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds varepsilon-approximate minimizers of convex functions in T = tildeObig( frac1varepsilon2 m + fracα2varepsilon2 big) iterations. In contrast, traditional mini-batch SGD needs T = Obig( frac1varepsilon2 m big) iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sampling complexity and time complexity.

Key facts. Cited by 81 papers in the map (data through 14 Oct 2026). First posted on arXiv 23 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 21; 2022: 16; 2023: 10; 2024: 17; 2025: 9; 2026: 8.

81 papers.

Sort:

By area:

  1. 2021A Field Guide to Federated Optimizationcited by 315
  2. 2021SPECTRE: Defending Against Backdoor Attacks Using Robust Statisticscited by 130
  3. 2021Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learningcited by 118
  4. 2022Vertical Federated Learning: Concepts, Advances and Challengescited by 108
  5. 2021Provably Secure Federated Learning against Malicious Clientscited by 63
  6. 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
  7. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 54
  8. 2022Byzantine-Robust Decentralized Learning via ClippedGossipcited by 31
  9. 2021Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filteringcited by 30
  10. 2022Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guaranteescited by 30
  11. 2023Label Poisoning is All You Needcited by 29
  12. 2021Robust Training in High Dimensions via Block Coordinate Geometric Median Descentcited by 20
38 more
  1. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  2. 2021Distributed Learning Systems with First-order Methodscited by 17
  3. 2021Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programmingcited by 17
  4. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 17
  5. 2021Towards Demystifying Serverless Machine Learning Trainingcited by 16
  6. 2022Few-shot Backdoor Attacks via Neural Tangent Kernelscited by 15
  7. 2024Trustworthy Distributed AI Systems: Robustness, Privacy, and Governancecited by 14
  8. 2021Secure Distributed Training at Scalecited by 12
  9. 2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
  10. 2021Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inferencecited by 11
  11. 2026Enhancing LLM Training via Spectral Clippingcited by 10
  12. 2021RobustFed: A Truth Inference Approach for Robust Federated Learningcited by 9
  13. 2022Robust Bayesian Learning for Reliable Wireless AI: Framework and Applicationscited by 9
  14. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 9
  15. 2024Unified Breakdown Analysis for Byzantine Robust Gossipcited by 8
  16. 2021Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancycited by 7
  17. 2023Incentivizing Honesty among Competitors in Collaborative Learning and Optimizationcited by 6
  18. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  19. 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Boundscited by 5
  20. 2022MixTailor: Mixed Gradient Aggregation for Robust Learning Against Tailored Attackscited by 5
  21. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  22. 2024On the Byzantine-Resilience of Distillation-Based Federated Learningcited by 5
  23. 2022Network-Level Adversaries in Federated Learningcited by 4
  24. 2023FedREP: A Byzantine-Robust, Communication-Efficient and Privacy-Preserving Framework for Federated Learningcited by 4
  25. 2024A survey on secure decentralized optimization and learningcited by 4
  26. 2021Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resiliencecited by 3
  27. 2023Byzantine-Resilient Decentralized Multi-Armed Banditscited by 3
  28. 2024Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Trainingcited by 3
  29. 2024Incentivizing Truthful Collaboration in Heterogeneous Federated Learningcited by 3
  30. 2025Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participationcited by 3
  31. 2022Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Topcited by 2
  32. 2024Decentralized Federated Policy Gradient with Byzantine Fault-Tolerance and Provably Fast Convergencecited by 2
  33. 2024Parallel Momentum Methods Under Biased Gradient Estimationscited by 2
  34. 2024On the Relevance of Byzantine Robust Optimization Against Data Poisoningcited by 2
  35. 2025Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous MLcited by 2
  36. 2025On the Byzantine Fault Tolerance of signSGD with Majority Votecited by 2
  37. 2025Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoningcited by 2
  38. 2025Adversarial Robustness in Distributed Quantum Machine Learningcited by 2

50 most cited of 81 All 81 (JSON)