# What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 55 references that are in the map.
- First posted on arXiv 3 Jul 2023.

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

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Generalizing from a Few Examples: A Survey on Few-Shot Learning](https://mlsanity.com/paper/1904.05046/) (2019)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Poisoning Web-Scale Training Datasets is Practical](https://mlsanity.com/paper/2302.10149/) (2023)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Unlearnable Examples: Making Personal Data Unexploitable](https://mlsanity.com/paper/2101.04898/) (2021)
- [Are We Really Making Much Progress? A Worrying Analysis of Recent Neural Recommendation Approaches](https://mlsanity.com/paper/1907.06902/) (2019)
- [Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching](https://mlsanity.com/paper/2009.02276/) (2020)
- [Stronger Data Poisoning Attacks Break Data Sanitization Defenses](https://mlsanity.com/paper/1811.00741/) (2018)
- [Transferable Clean-Label Poisoning Attacks on Deep Neural Nets](https://mlsanity.com/paper/1905.05897/) (2019)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [MetaPoison: Practical General-purpose Clean-label Data Poisoning](https://mlsanity.com/paper/2004.00225/) (2020)
- [Adversarial Examples Make Strong Poisons](https://mlsanity.com/paper/2106.10807/) (2021)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Subpopulation Data Poisoning Attacks](https://mlsanity.com/paper/2006.14026/) (2020)
- [Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training](https://mlsanity.com/paper/2102.04716/) (2021)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022)
- [Continuous Learning for Android Malware Detection](https://mlsanity.com/paper/2302.04332/) (2023)
- [Indiscriminate Data Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/2204.09092/) (2022)
- [Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins](https://mlsanity.com/paper/2010.00539/) (2020)
- [Learning Security Classifiers with Verified Global Robustness Properties](https://mlsanity.com/paper/2105.11363/) (2021)
- [Can Adversarial Training Be Manipulated By Non-Robust Features?](https://mlsanity.com/paper/2201.13329/) (2022)
- [Lethal Dose Conjecture on Data Poisoning](https://mlsanity.com/paper/2208.03309/) (2022)
- [Explainable AI for Android Malware Detection: Towards Understanding Why the Models Perform So Well?](https://mlsanity.com/paper/2209.00812/) (2022)
- [The Hammer and the Nut: Is Bilevel Optimization Really Needed to Poison Linear Classifiers?](https://mlsanity.com/paper/2103.12399/) (2021)
- [On Security and Sparsity of Linear Classifiers for Adversarial Settings](https://mlsanity.com/paper/1709.00045/) (2017)

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

- [Preference Poisoning Attacks on Reward Model Learning](https://mlsanity.com/paper/2402.01920/) (2024)
- [Self-Consuming Generative Models with Adversarially Curated Data](https://mlsanity.com/paper/2505.09768/) (2025)
- [On Robustness of Linear Classifiers to Targeted Data Poisoning](https://mlsanity.com/paper/2511.12722/) (2025)

## Abstract (arXiv)

We study indiscriminate poisoning for linear learners where an adversary injects a few crafted examples into the training data with the goal of forcing the induced model to incur higher test error. Inspired by the observation that linear learners on some datasets are able to resist the best known attacks even without any defenses, we further investigate whether datasets can be inherently robust to indiscriminate poisoning attacks for linear learners. For theoretical Gaussian distributions, we rigorously characterize the behavior of an optimal poisoning attack, defined as the poisoning strategy that attains the maximum risk of the induced model at a given poisoning budget. Our results prove that linear learners can indeed be robust to indiscriminate poisoning if the class-wise data distributions are well-separated with low variance and the size of the constraint set containing all permissible poisoning points is also small. These findings largely explain the drastic variation in empirical attack performance of the state-of-the-art poisoning attacks on linear learners across benchmark datasets, making an important initial step towards understanding the underlying reasons some learning tasks are vulnerable to data poisoning attacks.