# On the Relevance of Byzantine Robust Optimization Against Data Poisoning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 32 of its 48 references that are in the map.
- First posted on arXiv 1 May 2024.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

## Builds on (most cited first, 30 of 32)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Attack of the Tails: Yes, You Really Can Backdoor Federated Learning](https://mlsanity.com/paper/2007.05084/) (2020)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [A backdoor attack against LSTM-based text classification systems](https://mlsanity.com/paper/1905.12457/) (2019)
- [Clean-Label Backdoor Attacks on Video Recognition Models](https://mlsanity.com/paper/2003.03030/) (2020)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning](https://mlsanity.com/paper/2108.10241/) (2021)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [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)
- [Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)](https://mlsanity.com/paper/2008.00742/) (2020)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [Byzantine-Resilient High-Dimensional Federated Learning](https://mlsanity.com/paper/2006.13041/) (2020)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Systematic Evaluation of Backdoor Data Poisoning Attacks on Image Classifiers](https://mlsanity.com/paper/2004.11514/) (2020)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Distributed Robust Learning](https://mlsanity.com/paper/1409.5937/) (2014)

## Built on by (most cited first, 2 of 2)

- [Tight Stability Bounds for Robust Distributed Learning: Byzantine Failures Hurt Generalization More than Data Poisoning](https://mlsanity.com/paper/2506.18020/) (2025)
- [LiD-FL: Towards List-Decodable Federated Learning](https://mlsanity.com/paper/2408.04963/) (2024)

## Abstract (arXiv)

The success of machine learning (ML) has been intimately linked with the availability of large amounts of data, typically collected from heterogeneous sources and processed on vast networks of computing devices (also called em workers). Beyond accuracy, the use of ML in critical domains such as healthcare and autonomous driving calls for robustness against em data poisoningand some em faulty workers. The problem of em Byzantine ML formalizes these robustness issues by considering a distributed ML environment in which workers (storing a portion of the global dataset) can deviate arbitrarily from the prescribed algorithm. Although the problem has attracted a lot of attention from a theoretical point of view, its practical importance for addressing realistic faults (where the behavior of any worker is locally constrained) remains unclear. It has been argued that the seemingly weaker threat model where only workers' local datasets get poisoned is more reasonable. We prove that, while tolerating a wider range of faulty behaviors, Byzantine ML yields solutions that are, in a precise sense, optimal even under the weaker data poisoning threat model. Then, we study a generic data poisoning model wherein some workers have em fully-poisonous local data, i.e., their datasets are entirely corruptible, and the remainders have em partially-poisonous local data, i.e., only a fraction of their local datasets is corruptible. We prove that Byzantine-robust schemes yield optimal solutions against both these forms of data poisoning, and that the former is more harmful when workers have em heterogeneous local data.