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

• URL: http://arxiv.org/abs/2604.11416v1
• Date: Mon, 13 Apr 2026 13:01:14 GMT
• Title: Exact Certification of Neural Networks and Partition Aggregation Ensembles against Label Poisoning
• Abstract summary: Label-flipping attacks are a major threat to supervised learning models.<n>Existing certification frameworks rely on ensemble techniques such as smoothing or partition-aggregation.<n>We introduce EnsembleCert, the first certification framework for partition-aggregation ensembles.
• Score: 48.86044009211734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• SegPAR: Class-Centric Decision-Based Sparse Attack for Semantic Segmentation [2.3332469289621787]
  We adapt the most representative decision-based black-box sparse attacks from the classification domain to serve as baselines.<n>SegPAR is a novel decision-based framework that shifts to a class-centric exploration paradigm.<n>Experiments show that SegPAR significantly outperforms black-box baselines in sparsity efficiency and MIoU reduction.
  arXiv  Detail & Related papers  (2026-08-11T14:44:33Z)
• Beyond Red-Teaming: Formal Guarantees of LLM Guardrail Classifiers [1.9839136494100942]
  Guardrails defend production language models against harmful behavior, but they provide no formal guarantees.<n>We propose two constructions of such regions: SVD-aligned hyper-rectangles and Gaussian Mixture Models.<n>Applying this framework to three author-trained Guardrails on the toxicity domain, every hyper-rectangle configuration returns SAT.<n>While GPT-2 and Llama-3.1-8B maintain robust coverage of 90% and 80% across varying boundaries, BERT's safety guarantees prove uniquely volatile.
  arXiv  Detail & Related papers  (2026-05-11T17:41:38Z)
• Fast and Flexible Robustness Certificates for Semantic Segmentation [6.1903263165298945]
  We introduce a new class of certifiably robust semantic networks with built-in Lipschitz constraints.<n>Our approach unlocks real-time compatible certifiably robust semantic segmentation for the first time.<n>We find our approach to be around 600 times faster than randomized smoothing methods at inference with comparable certificates on an NVIDIA A100 GPU.
  arXiv  Detail & Related papers  (2025-12-03T10:10:16Z)
• PatchDEMUX: A Certifiably Robust Framework for Multi-label Classifiers Against Adversarial Patches [37.33690151547147]
  We present PatchDEMUX, a certifiably robust framework for multi-label classification against adversarial patches.<n>Our approach is a generalizable method which can extend any existing certifiable defense for single-label classification.<n>We find that PatchDEMUX can achieve non-trivial robustness on the MS-COCO and PASCAL VOC datasets.
  arXiv  Detail & Related papers  (2025-05-30T15:25:51Z)
• Exact Certification of (Graph) Neural Networks Against Label Poisoning [50.87615167799367]
  We introduce an exact certification method for label flipping in Graph Neural Networks (GNNs)<n>We apply our method to certify a broad range of GNN architectures in node classification tasks.<n>Our work presents the first exact certificate to a poisoning attack ever derived for neural networks.
  arXiv  Detail & Related papers  (2024-11-30T17:05:12Z)
• Adaptive Hierarchical Certification for Segmentation using Randomized Smoothing [87.48628403354351]
  certification for machine learning is proving that no adversarial sample can evade a model within a range under certain conditions. Common certification methods for segmentation use a flat set of fine-grained classes, leading to high abstain rates due to model uncertainty. We propose a novel, more practical setting, which certifies pixels within a multi-level hierarchy, and adaptively relaxes the certification to a coarser level for unstable components.
  arXiv  Detail & Related papers  (2024-02-13T11:59:43Z)
• On the Perils of Cascading Robust Classifiers [32.76147960792804]
  Ensembling certifiably robust neural networks has been shown to be a promising approach for improving the emphcertified robust accuracy of neural models. We present an alternate black-box ensembling mechanism based on weighted voting which we prove to be sound for robustness certification.
  arXiv  Detail & Related papers  (2022-06-01T07:15:58Z)
• Smooth-Reduce: Leveraging Patches for Improved Certified Robustness [100.28947222215463]
  We propose a training-free, modified smoothing approach, Smooth-Reduce. Our algorithm classifies overlapping patches extracted from an input image, and aggregates the predicted logits to certify a larger radius around the input. We provide theoretical guarantees for such certificates, and empirically show significant improvements over other randomized smoothing methods.
  arXiv  Detail & Related papers  (2022-05-12T15:26:20Z)
• Robustness Certificates for Implicit Neural Networks: A Mixed Monotone Contractive Approach [60.67748036747221]
  Implicit neural networks offer competitive performance and reduced memory consumption. They can remain brittle with respect to input adversarial perturbations. This paper proposes a theoretical and computational framework for robustness verification of implicit neural networks.
  arXiv  Detail & Related papers  (2021-12-10T03:08:55Z)
• Certified Distributional Robustness on Smoothed Classifiers [27.006844966157317]
  We propose the worst-case adversarial loss over input distributions as a robustness certificate. By exploiting duality and the smoothness property, we provide an easy-to-compute upper bound as a surrogate for the certificate.
  arXiv  Detail & Related papers  (2020-10-21T13:22:25Z)
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing [105.91827623768724]
  Machine learning algorithms are susceptible to data poisoning attacks. We present a unifying view of randomized smoothing over arbitrary functions. We propose a new strategy for building classifiers that are pointwise-certifiably robust to general data poisoning attacks.
  arXiv  Detail & Related papers  (2020-02-07T21:28:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.