# On Optimal Learning Under Targeted Data Poisoning

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

## Key facts

- Cited by 14 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 23 of its 49 references that are in the map.
- First posted on arXiv 6 Oct 2022.

## 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, 23 of 23)

- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain](https://mlsanity.com/paper/1708.06733/) (2017)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Adversarial Attacks and Defences: A Survey](https://mlsanity.com/paper/1810.00069/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [RAB: Provable Robustness Against Backdoor Attacks](https://mlsanity.com/paper/2003.08904/) (2020)
- [Deep Partition Aggregation: Provable Defense against General Poisoning Attacks](https://mlsanity.com/paper/2006.14768/) (2020)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [Subpopulation Data Poisoning Attacks](https://mlsanity.com/paper/2006.14026/) (2020)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)
- [A Framework of Randomized Selection Based Certified Defenses Against Data Poisoning Attacks](https://mlsanity.com/paper/2009.08739/) (2020)
- [On Communication Complexity of Classification Problems](https://mlsanity.com/paper/1711.05893/) (2017)
- [Computational Concentration of Measure: Optimal Bounds, Reductions, and More](https://mlsanity.com/paper/1907.05401/) (2019)
- [Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility](https://mlsanity.com/paper/1909.03547/) (2019)

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

- [Run-Off Election: Improved Provable Defense against Data Poisoning Attacks](https://mlsanity.com/paper/2302.02300/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Generalization Bound and New Algorithm for Clean-Label Backdoor Attack](https://mlsanity.com/paper/2406.00588/) (2024)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026)
- [Backdoor defense, learnability and obfuscation](https://mlsanity.com/paper/2409.03077/) (2024)
- [Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness](https://mlsanity.com/paper/2506.03075/) (2025)
- [Distribution-Free Sequential Prediction with Abstentions](https://mlsanity.com/paper/2602.17918/) (2026)
- [Bagging Robustly Learns VC Classes with Linear Sample Complexity](https://mlsanity.com/paper/2608.13514/) (2026)
- [On Robustness of Linear Classifiers to Targeted Data Poisoning](https://mlsanity.com/paper/2511.12722/) (2025)
- [Phase Transitions in Driven Informational Systems: A Two-Field Perspective on Learning Theory and Non-Equilibrium Chemistry](https://mlsanity.com/paper/2605.16325/) (2026)
- [When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification](https://mlsanity.com/paper/2608.20480/) (2026)
- [Why Backdooring Neural Networks is so Easy?](https://mlsanity.com/paper/2609.36117/) (2026)

## Abstract (arXiv)

Consider the task of learning a hypothesis class H in the presence of an adversary that can replace up to an η fraction of the examples in the training set with arbitrary adversarial examples. The adversary aims to fail the learner on a particular target test point x which is known to the adversary but not to the learner. In this work we aim to characterize the smallest achievable error ε=ε(η) by the learner in the presence of such an adversary in both realizable and agnostic settings. We fully achieve this in the realizable setting, proving that ε=Theta(mathttVC(H)· η), where mathttVC(H) is the VC dimension of H. Remarkably, we show that the upper bound can be attained by a deterministic learner. In the agnostic setting we reveal a more elaborate landscape: we devise a deterministic learner with a multiplicative regret guarantee of ε ≤ C·mathttOPT + O(mathttVC(H)· η), where C > 1 is a universal numerical constant. We complement this by showing that for any deterministic learner there is an attack which worsens its error to at least 2· mathttOPT. This implies that a multiplicative deterioration in the regret is unavoidable in this case. Finally, the algorithms we develop for achieving the optimal rates are inherently improper. Nevertheless, we show that for a variety of natural concept classes, such as linear classifiers, it is possible to retain the dependence ε=ThetaH(η) by a proper algorithm in the realizable setting. Here ThetaH conceals a polynomial dependence on mathttVC(H).