# Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates

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

## Key facts

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

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [FLDetector: Defending Federated Learning Against Model Poisoning Attacks via Detecting Malicious Clients](https://mlsanity.com/paper/2207.09209/) (2022)
- [Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning](https://mlsanity.com/paper/2108.10241/) (2021)
- [Neurotoxin: Durable Backdoors in Federated Learning](https://mlsanity.com/paper/2206.10341/) (2022)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [CRFL: Certifiably Robust Federated Learning against Backdoor Attacks](https://mlsanity.com/paper/2106.08283/) (2021)
- [Multimodal Federated Learning via Contrastive Representation Ensemble](https://mlsanity.com/paper/2302.08888/) (2023)
- [Survey on Federated Learning Threats: concepts, taxonomy on attacks and defences, experimental study and challenges](https://mlsanity.com/paper/2201.08135/) (2022)
- [DeepSight: Mitigating Backdoor Attacks in Federated Learning Through Deep Model Inspection](https://mlsanity.com/paper/2201.00763/) (2022)
- [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)
- [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)
- [FedCorr: Multi-Stage Federated Learning for Label Noise Correction](https://mlsanity.com/paper/2204.04677/) (2022)
- [FedRecover: Recovering from Poisoning Attacks in Federated Learning using Historical Information](https://mlsanity.com/paper/2210.10936/) (2022)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Federated Learning: A Signal Processing Perspective](https://mlsanity.com/paper/2103.17150/) (2021)
- [Byzantine-Robust Decentralized Federated Learning](https://mlsanity.com/paper/2406.10416/) (2024)
- [Challenges and Approaches for Mitigating Byzantine Attacks in Federated Learning](https://mlsanity.com/paper/2112.14468/) (2021)
- [SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification](https://mlsanity.com/paper/2112.06274/) (2021)
- [VeriFi: Towards Verifiable Federated Unlearning](https://mlsanity.com/paper/2205.12709/) (2022)
- [Recent Advances on Federated Learning: A Systematic Survey](https://mlsanity.com/paper/2301.01299/) (2023)
- [PipAttack: Poisoning Federated Recommender Systems forManipulating Item Promotion](https://mlsanity.com/paper/2110.10926/) (2021)
- [FLIP: A Provable Defense Framework for Backdoor Mitigation in Federated Learning](https://mlsanity.com/paper/2210.12873/) (2022)
- [Federated Learning for Malware Detection in IoT Devices](https://mlsanity.com/paper/2104.09994/) (2021)
- [FedIPR: Ownership Verification for Federated Deep Neural Network Models](https://mlsanity.com/paper/2109.13236/) (2021)
- [FL-WBC: Enhancing Robustness against Model Poisoning Attacks in Federated Learning from a Client Perspective](https://mlsanity.com/paper/2110.13864/) (2021)
- [Advances and Open Challenges in Federated Foundation Models](https://mlsanity.com/paper/2404.15381/) (2024)
- [Backdoor Attacks and Defenses in Federated Learning: Survey, Challenges and Future Research Directions](https://mlsanity.com/paper/2303.02213/) (2023)
- [An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning](https://mlsanity.com/paper/2302.07173/) (2023)

## Abstract (arXiv)

In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures -- arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithms that are provably robust against such failures, with a focus on achieving optimal statistical performance. A main result of this work is a sharp analysis of two robust distributed gradient descent algorithms based on median and trimmed mean operations, respectively. We prove statistical error rates for three kinds of population loss functions: strongly convex, non-strongly convex, and smooth non-convex. In particular, these algorithms are shown to achieve order-optimal statistical error rates for strongly convex losses. To achieve better communication efficiency, we further propose a median-based distributed algorithm that is provably robust, and uses only one communication round. For strongly convex quadratic loss, we show that this algorithm achieves the same optimal error rate as the robust distributed gradient descent algorithms.