# Byzantine Stochastic Gradient Descent

arXiv: https://arxiv.org/abs/1803.08917 · HTML: https://mlsanity.com/paper/1803.08917/

## Key facts

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

## Built on by (most cited first, 30 of 81)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics](https://mlsanity.com/paper/2104.11315/) (2021)
- [Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning](https://mlsanity.com/paper/2108.10241/) (2021)
- [Vertical Federated Learning: Concepts, Advances and Challenges](https://mlsanity.com/paper/2211.12814/) (2022)
- [Provably Secure Federated Learning against Malicious Clients](https://mlsanity.com/paper/2102.01854/) (2021)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filtering](https://mlsanity.com/paper/2109.05872/) (2021)
- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [Label Poisoning is All You Need](https://mlsanity.com/paper/2310.18933/) (2023)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Towards Demystifying Serverless Machine Learning Training](https://mlsanity.com/paper/2105.07806/) (2021)
- [Few-shot Backdoor Attacks via Neural Tangent Kernels](https://mlsanity.com/paper/2210.05929/) (2022)
- [Trustworthy Distributed AI Systems: Robustness, Privacy, and Governance](https://mlsanity.com/paper/2402.01096/) (2024)
- [Secure Distributed Training at Scale](https://mlsanity.com/paper/2106.11257/) (2021)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [Variance Reduced Median-of-Means Estimator for Byzantine-Robust Distributed Inference](https://mlsanity.com/paper/2103.02860/) (2021)
- [Enhancing LLM Training via Spectral Clipping](https://mlsanity.com/paper/2603.14315/) (2026)
- [RobustFed: A Truth Inference Approach for Robust Federated Learning](https://mlsanity.com/paper/2107.08402/) (2021)
- [Robust Bayesian Learning for Reliable Wireless AI: Framework and Applications](https://mlsanity.com/paper/2207.00300/) (2022)
- [Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneity](https://mlsanity.com/paper/2305.18285/) (2023)
- [Unified Breakdown Analysis for Byzantine Robust Gossip](https://mlsanity.com/paper/2410.10418/) (2024)
- [Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy](https://mlsanity.com/paper/2108.11769/) (2021)
- [Incentivizing Honesty among Competitors in Collaborative Learning and Optimization](https://mlsanity.com/paper/2305.16272/) (2023)
- [Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries](https://mlsanity.com/paper/2403.09940/) (2024)

## 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.