# Exact Certification of Neural Networks and Partition Aggregation Ensembles against Label Poisoning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 37 references that are in the map.
- First posted on arXiv 13 Apr 2026.

## Builds on (most cited first, 29 of 29)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Unsupervised Representation Learning by Predicting Image Rotations](https://mlsanity.com/paper/1803.07728/) (2018)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [Stronger Data Poisoning Attacks Break Data Sanitization Defenses](https://mlsanity.com/paper/1811.00741/) (2018)
- [On the linearity of large non-linear models: when and why the tangent kernel is constant](https://mlsanity.com/paper/2010.01092/) (2020)
- [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)
- [Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks](https://mlsanity.com/paper/2008.04495/) (2020)
- [On Certifying Robustness against Backdoor Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.11750/) (2020)
- [Label Sanitization against Label Flipping Poisoning Attacks](https://mlsanity.com/paper/1803.00992/) (2018)
- [Certified Robustness of Nearest Neighbors against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2012.03765/) (2020)
- [Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation](https://mlsanity.com/paper/2202.02628/) (2022)
- [Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network](https://mlsanity.com/paper/2007.02486/) (2020)
- [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)
- [Certified Robustness to Data Poisoning in Gradient-Based Training](https://mlsanity.com/paper/2406.05670/) (2024)
- [On the Equivalence between Neural Network and Support Vector Machine](https://mlsanity.com/paper/2111.06063/) (2021)
- [Run-Off Election: Improved Provable Defense against Data Poisoning Attacks](https://mlsanity.com/paper/2302.02300/) (2023)
- [Black-box Certification and Learning under Adversarial Perturbations](https://mlsanity.com/paper/2006.16520/) (2020)
- [Analysis of Convolutions, Non-linearity and Depth in Graph Neural Networks using Neural Tangent Kernel](https://mlsanity.com/paper/2210.09809/) (2022)
- [Exact Certification of (Graph) Neural Networks Against Label Poisoning](https://mlsanity.com/paper/2412.00537/) (2024)
- [Adversarial Training for Defense Against Label Poisoning Attacks](https://mlsanity.com/paper/2502.17121/) (2025)
- [Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks](https://mlsanity.com/paper/2407.10867/) (2024)
- [Naive Bayes Classifiers over Missing Data: Decision and Poisoning](https://mlsanity.com/paper/2303.04811/) (2023)

## Abstract (arXiv)

Label-flipping attacks, which corrupt training labels to induce misclassifications at inference, remain a major threat to supervised learning models. This drives the need for robustness certificates that provide formal guarantees about a model's robustness under adversarially corrupted labels. Existing certification frameworks rely on ensemble techniques such as smoothing or partition-aggregation, but treat the corresponding base classifiers as black boxes, yielding overly conservative guarantees. We introduce EnsembleCert, the first certification framework for partition-aggregation ensembles that utilizes white-box knowledge of the base classifiers. Concretely, EnsembleCert yields tighter guarantees than black-box approaches by aggregating per-partition white-box certificates to compute ensemble-level guarantees in polynomial time. To extract white-box knowledge from the base classifiers efficiently, we develop ScaLabelCert, a method that leverages the equivalence between sufficiently wide neural networks and kernel methods using the neural tangent kernel. ScaLabelCert yields the first exact, polynomial-time calculable certificate for neural networks against label-flipping attacks. EnsembleCert is either on par, or significantly outperforms the existing partition-based black box certificates. Exemplary, on CIFAR-10, our method can certify upto +26.5% more label flips in median over the test set compared to the existing black-box approach while requiring 100 times fewer partitions, thus, challenging the prevailing notion that heavy partitioning is a necessity for strong certified robustness.