# Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent

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

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2017.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Survey of Vulnerabilities in Large Language Models Revealed by Adversarial Attacks](https://mlsanity.com/paper/2310.10844/) (2023)
- [CRFL: Certifiably Robust Federated Learning against Backdoor Attacks](https://mlsanity.com/paper/2106.08283/) (2021)
- [MPAF: Model Poisoning Attacks to Federated Learning based on Fake Clients](https://mlsanity.com/paper/2203.08669/) (2022)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [FedRecover: Recovering from Poisoning Attacks in Federated Learning using Historical Information](https://mlsanity.com/paper/2210.10936/) (2022)
- [Federated Learning: A Signal Processing Perspective](https://mlsanity.com/paper/2103.17150/) (2021)
- [Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filtering](https://mlsanity.com/paper/2109.05872/) (2021)
- [Training Fair Models in Federated Learning without Data Privacy Infringement](https://mlsanity.com/paper/2109.05662/) (2021)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [Practical Differentially Private and Byzantine-resilient Federated Learning](https://mlsanity.com/paper/2304.09762/) (2023)
- [FLShield: A Validation Based Federated Learning Framework to Defend Against Poisoning Attacks](https://mlsanity.com/paper/2308.05832/) (2023)
- [Byzantine-Robust and Privacy-Preserving Framework for FedML](https://mlsanity.com/paper/2105.02295/) (2021)
- [Bridging Differential Privacy and Byzantine-Robustness via Model Aggregation](https://mlsanity.com/paper/2205.00107/) (2022)
- [Auto-weighted Robust Federated Learning with Corrupted Data Sources](https://mlsanity.com/paper/2101.05880/) (2021)
- [Robust Collaborative Learning with Linear Gradient Overhead](https://mlsanity.com/paper/2209.10931/) (2022)
- [Data-Free Evaluation of User Contributions in Federated Learning](https://mlsanity.com/paper/2108.10623/) (2021)
- [RobustFed: A Truth Inference Approach for Robust Federated Learning](https://mlsanity.com/paper/2107.08402/) (2021)
- [Towards Efficient Synchronous Federated Training: A Survey on System Optimization Strategies](https://mlsanity.com/paper/2109.03999/) (2021)
- [Byzantine-robust Federated Learning through Spatial-temporal Analysis of Local Model Updates](https://mlsanity.com/paper/2107.01477/) (2021)
- [Auxo: Efficient Federated Learning via Scalable Client Clustering](https://mlsanity.com/paper/2210.16656/) (2022)
- [Byzantine-Robust Federated Learning with Variance Reduction and Differential Privacy](https://mlsanity.com/paper/2309.03437/) (2023)
- [FLTracer: Accurate Poisoning Attack Provenance in Federated Learning](https://mlsanity.com/paper/2310.13424/) (2023)
- [Provably Robust Federated Reinforcement Learning](https://mlsanity.com/paper/2502.08123/) (2025)
- [Robust Federated Learning via Over-The-Air Computation](https://mlsanity.com/paper/2111.01221/) (2021)
- [MixTailor: Mixed Gradient Aggregation for Robust Learning Against Tailored Attacks](https://mlsanity.com/paper/2207.07941/) (2022)
- [Securing Federated Learning against Overwhelming Collusive Attackers](https://mlsanity.com/paper/2209.14093/) (2022)
- [Byzantine Spectral Ranking](https://mlsanity.com/paper/2211.07902/) (2022)

## Abstract (arXiv)

We consider the problem of distributed statistical machine learning in adversarial settings, where some unknown and time-varying subset of working machines may be compromised and behave arbitrarily to prevent an accurate model from being learned. This setting captures the potential adversarial attacks faced by Federated Learning -- a modern machine learning paradigm that is proposed by Google researchers and has been intensively studied for ensuring user privacy. Formally, we focus on a distributed system consisting of a parameter server and m working machines. Each working machine keeps N/m data samples, where N is the total number of samples. The goal is to collectively learn the underlying true model parameter of dimension d. In classical batch gradient descent methods, the gradients reported to the server by the working machines are aggregated via simple averaging, which is vulnerable to a single Byzantine failure. In this paper, we propose a Byzantine gradient descent method based on the geometric median of means of the gradients. We show that our method can tolerate q ≤ (m-1)/2 Byzantine failures, and the parameter estimate converges in O(log N) rounds with an estimation error of √d(2q+1)/N, hence approaching the optimal error rate √d/N in the centralized and failure-free setting. The total computational complexity of our algorithm is of O((Nd/m) log N) at each working machine and O(md + kd log3 N) at the central server, and the total communication cost is of O(m d log N). We further provide an application of our general results to the linear regression problem. A key challenge arises in the above problem is that Byzantine failures create arbitrary and unspecified dependency among the iterations and the aggregated gradients. We prove that the aggregated gradient converges uniformly to the true gradient function.