# Learning and Certification under Instance-targeted Poisoning arXiv: https://arxiv.org/abs/2105.08709 ยท HTML: https://mlsanity.com/paper/2105.08709/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 25 of its 45 references that are in the map. - First posted on arXiv 18 May 2021. ## Builds on (most cited first, 25 of 25) - [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017) - [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) - [Detecting Backdoor Attacks on Deep Neural Networks by Activation Clustering](https://mlsanity.com/paper/1811.03728/) (2018) - [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017) - [Label-Consistent Backdoor Attacks](https://mlsanity.com/paper/1912.02771/) (2019) - [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) - [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018) - [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) - [Towards the Science of Security and Privacy in Machine Learning](https://mlsanity.com/paper/1611.03814/) (2016) - [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019) - [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018) - [Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution](https://mlsanity.com/paper/1810.12272/) (2018) - [Universal Multi-Party Poisoning Attacks](https://mlsanity.com/paper/1809.03474/) (2018) - [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021) - [Lower Bounds for Adversarially Robust PAC Learning](https://mlsanity.com/paper/1906.05815/) (2019) - [A Framework of Randomized Selection Based Certified Defenses Against Data Poisoning Attacks](https://mlsanity.com/paper/2009.08739/) (2020) - [Can Adversarially Robust Learning Leverage Computational Hardness?](https://mlsanity.com/paper/1810.01407/) (2018) - [Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin](https://mlsanity.com/paper/1908.11335/) (2019) - [Computational Concentration of Measure: Optimal Bounds, Reductions, and More](https://mlsanity.com/paper/1907.05401/) (2019) ## Built on by (most cited first, 13 of 13) - [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022) - [Robustly-reliable learners under poisoning attacks](https://mlsanity.com/paper/2203.04160/) (2022) - [Run-Off Election: Improved Provable Defense against Data Poisoning Attacks](https://mlsanity.com/paper/2302.02300/) (2023) - [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022) - [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) - [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023) - [Accumulative Poisoning Attacks on Real-time Data](https://mlsanity.com/paper/2106.09993/) (2021) - [Regularized Robustly Reliable Learners and Instance Targeted Attacks](https://mlsanity.com/paper/2410.10572/) (2024) - [Learning with Monotone Adversarial Corruptions](https://mlsanity.com/paper/2601.02193/) (2026) - [Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness](https://mlsanity.com/paper/2506.03075/) (2025) - [Certified Robustness to Clean-Label Poisoning Using Diffusion Denoising](https://mlsanity.com/paper/2403.11981/) (2024) - [Distribution-Free Sequential Prediction with Abstentions](https://mlsanity.com/paper/2602.17918/) (2026) ## Abstract (arXiv) In this paper, we study PAC learnability and certification of predictions under instance-targeted poisoning attacks, where the adversary who knows the test instance may change a fraction of the training set with the goal of fooling the learner at the test instance. Our first contribution is to formalize the problem in various settings and to explicitly model subtle aspects such as the proper or improper nature of the learning, learner's randomness, and whether (or not) adversary's attack can depend on it. Our main result shows that when the budget of the adversary scales sublinearly with the sample complexity, (improper) PAC learnability and certification are achievable; in contrast, when the adversary's budget grows linearly with the sample complexity, the adversary can potentially drive up the expected 0-1 loss to one. We also study distribution-specific PAC learning in the same attack model and show that proper learning with certification is possible for learning half spaces under natural distributions. Finally, we empirically study the robustness of K nearest neighbour, logistic regression, multi-layer perceptron, and convolutional neural network on real data sets against targeted-poisoning attacks. Our experimental results show that many models, especially state-of-the-art neural networks, are indeed vulnerable to these strong attacks. Interestingly, we observe that methods with high standard accuracy might be more vulnerable to instance-targeted poisoning attacks.