# Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks

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

## Key facts

- Cited by 94 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2020.

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

- [PoisonedRAG: Knowledge Corruption Attacks to Retrieval-Augmented Generation of Large Language Models](https://mlsanity.com/paper/2402.07867/) (2024)
- [Adversarial Unlearning of Backdoors via Implicit Hypergradient](https://mlsanity.com/paper/2110.03735/) (2021)
- [Rethinking the Backdoor Attacks' Triggers: A Frequency Perspective](https://mlsanity.com/paper/2104.03413/) (2021)
- [BadEncoder: Backdoor Attacks to Pre-trained Encoders in Self-Supervised Learning](https://mlsanity.com/paper/2108.00352/) (2021)
- [Hidden Backdoors in Human-Centric Language Models](https://mlsanity.com/paper/2105.00164/) (2021)
- [Nightshade: Prompt-Specific Poisoning Attacks on Text-to-Image Generative Models](https://mlsanity.com/paper/2310.13828/) (2023)
- [Provably Secure Federated Learning against Malicious Clients](https://mlsanity.com/paper/2102.01854/) (2021)
- [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022)
- [PointGuard: Provably Robust 3D Point Cloud Classification](https://mlsanity.com/paper/2103.03046/) (2021)
- [Stealthy Backdoor Attack for Code Models](https://mlsanity.com/paper/2301.02496/) (2023)
- [SparseFed: Mitigating Model Poisoning Attacks in Federated Learning with Sparsification](https://mlsanity.com/paper/2112.06274/) (2021)
- [Data Poisoning Attacks to Deep Learning Based Recommender Systems](https://mlsanity.com/paper/2101.02644/) (2021)
- [Poison Forensics: Traceback of Data Poisoning Attacks in Neural Networks](https://mlsanity.com/paper/2110.06904/) (2021)
- [Practical Poisoning Attacks against Retrieval-Augmented Generation](https://mlsanity.com/paper/2504.03957/) (2025)
- [PoisonedEncoder: Poisoning the Unlabeled Pre-training Data in Contrastive Learning](https://mlsanity.com/paper/2205.06401/) (2022)
- [Identifying a Training-Set Attack's Target Using Renormalized Influence Estimation](https://mlsanity.com/paper/2201.10055/) (2022)
- [FLCert: Provably Secure Federated Learning against Poisoning Attacks](https://mlsanity.com/paper/2210.00584/) (2022)
- [CorruptEncoder: Data Poisoning based Backdoor Attacks to Contrastive Learning](https://mlsanity.com/paper/2211.08229/) (2022)
- [A Comprehensive Study of the Robustness for LiDAR-based 3D Object Detectors against Adversarial Attacks](https://mlsanity.com/paper/2212.10230/) (2022)
- [Certifying Robustness to Programmable Data Bias in Decision Trees](https://mlsanity.com/paper/2110.04363/) (2021)
- [BagFlip: A Certified Defense against Data Poisoning](https://mlsanity.com/paper/2205.13634/) (2022)
- [Run-Off Election: Improved Provable Defense against Data Poisoning Attacks](https://mlsanity.com/paper/2302.02300/) (2023)
- [The Dataset Multiplicity Problem: How Unreliable Data Impacts Predictions](https://mlsanity.com/paper/2304.10655/) (2023)
- [On Collective Robustness of Bagging Against Data Poisoning](https://mlsanity.com/paper/2205.13176/) (2022)
- [TextGuard: Provable Defense against Backdoor Attacks on Text Classification](https://mlsanity.com/paper/2311.11225/) (2023)
- [ERASER: Machine Unlearning in MLaaS via an Inference Serving-Aware Approach](https://mlsanity.com/paper/2311.16136/) (2023)
- [A Survey on Machine Unlearning: Techniques and New Emerged Privacy Risks](https://mlsanity.com/paper/2406.06186/) (2024)
- [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022)
- [Rethinking Backdoor Attacks](https://mlsanity.com/paper/2307.10163/) (2023)
- [Learning and Certification under Instance-targeted Poisoning](https://mlsanity.com/paper/2105.08709/) (2021)

## Abstract (arXiv)

In a data poisoning attack, an attacker modifies, deletes, and/or inserts some training examples to corrupt the learnt machine learning model. Bootstrap Aggregating (bagging) is a well-known ensemble learning method, which trains multiple base models on random subsamples of a training dataset using a base learning algorithm and uses majority vote to predict labels of testing examples. We prove the intrinsic certified robustness of bagging against data poisoning attacks. Specifically, we show that bagging with an arbitrary base learning algorithm provably predicts the same label for a testing example when the number of modified, deleted, and/or inserted training examples is bounded by a threshold. Moreover, we show that our derived threshold is tight if no assumptions on the base learning algorithm are made. We evaluate our method on MNIST and CIFAR10. For instance, our method achieves a certified accuracy of 91.1% on MNIST when arbitrarily modifying, deleting, and/or inserting 100 training examples. Code is available at: urlhttps://github.com/jjy1994/BaggingCertifyDataPoisoning.