Organizations: School of Computation, Information and Technology, Technical University of Munich, Germany · Munich Data Science Institute, Technical University of Munich · Munich Center for Machine Learning, Germany · Australian Institute for Machine Learning, Adelaide University, Australia
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.
Figures & tables
Figure 1: (a) Two-step approach of EnsembleCert to derive white-box guarantees for partition aggregation ensembles. (b) Evaluation on CIFAR-10 using wide neural networks trained on a regression loss as base classifiers. Using as few as 10 partitions with white-box knowledge enables the ensemble to withstand up to 26.5% more label flips in median compared to using 1000 partitions. For a definition of the metric median certified robustness we refer the reader to Sec. 4 .
Figure 2: EnsembleCert evaluation using the NTK for (i) kernel SVM with a sufficiently small C (a, b); (ii) kernel regression under strong regularization (c, d). Median certified robustness either remains largely invariant across partitions or exhibits a decay until the white-box certificate converges to the black-box certificate. The tightness of our bounds on the exact certificate for the ensemble is evident, as the upper (EnsembleCert UB) and lower (EnsembleCert LB) bounds largely coincide across all plots.
Figure 3: Comparing certified accuracies of stand-alone base models and their partition aggregation ensembles. Results with the base model as kernel SVM are in (a) and (b). (c): Using a stand-alone kernel regression model on MNIST 1-vs-7 maintains a certified accuracy of close to 80% when the certified accuracy for the corresponding best performing ensemble ( Np=10 ) reaches 0 . (d): Smoothed linear regression as base model, comparing the stand-alone case and the ensembling.
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4
Figure 5: Figures (a) and (b) show the average latency per sample for kernel SVM on CIFAR-10 and MNIST, respectively. Figures (c) and (d) present the corresponding results for kernel regression. We report results for a single value of λ for each dataset, as the trends are consistent across different λ values and do not provide any additional qualitative insight.
Figure 6
Figure 7: Performance of an infinitely-wide neural network with a single trained on hinge loss across different values of C and the cardinality of the training dataset Ns . For each value of Ns , we subsample the training set for 5 different random seeds. The accuracy for each value of Ns initially remains constant up to a certain threshold for C , indicating the range of sufficiently small C, as the SVM performance does not depend on C in this regime. Shading around the central line indicates the standard deviation. In each plot, the region of sufficiently small C is colored blue for distinction.For each plot, the accuracy initially remains constant up to a certain threshold, indicating the range of sufficiently small C , as SVM performance does not depend on C in this regime.
Figure 8: Robustness-accuracy trade-off introduced by sufficiently small C. While Fig. 7 studies empirical performance of stand-alone models, the impact of small C ion the empirical performance of the ensemble is studies here.
Figure 9: Comparison of ScaLabelCert and gradient-based parameter bounding method. The parameter κ represents the gradient clipping parameter. ScaLabelCert significantly outperforms the gradient-based method for all values of κ .
Figure 10: EnsembleCert evaluated on ensembles with finite-width network as base classifiers. The base classifiers are certified by applying the gradient-based bounding technique by Sosnin et al. (2025) . Evidently, EnsembleCert significantly outperforms SS-DPA, the black-box approach applied to the ensemble.
Figure 11: Robustness trends across different λ values on MNIST using kernel regression.
Figure 12: Robustness trends across different λ values on CIFAR-10 using kernel regression.
Figure 13: MNIST binary kernel regression with λ=0.1 results for different number of partitions.
Figure 14: MNIST binary kernel SVM results for different number of partitions.
Figure 15: Invariance to number of partitions
Figure 16: CIFAR-10 kernel regression results for different numbers of partitions ( λ=0.01 ).
Figure 17: CIFAR-10 kernel regression with high regularization ( λ=10 ).
Figure 18: CIFAR-10 kernel SVM results for different numbers of partitions.
Figure 19: CIFAR-10 Smoothed linear regression as base-classifier
Figure 20: MNIST multi-class kernel regression results for different numbers of partitions ( λ=0.0001 ).
Figure 21: MNIST multi-class kernel regression results for different numbers of partitions ( λ=0.1 ).
Figure 22: MNIST multi-class kernel SVM results for different numbers of partitions.
A primary challenge in AI safety is the existence of adversarial examples -- slightly distorted inputs that cause a neural network (NN) to misclassify. To mitigate this problem, recent research focuses on the computation of robustness certifications, which, for a given input, determine the largest distortion the input may receive without breaking the network's prediction. Robustness certifications can be interpreted as an axis-aligned hyper-rectangle (multi-dimensional intervals). Most existing approaches focus on maximizing the certification's volume, but recent intractability results prohibit the computation of volume-optimal certifications in reasonable time. We introduce the apothem measure and show how to compute apothem-optimal certifications in a linear number of calls to a NN verifier (oracle) w.r.t. the input domain's diameter. Moreover, we prove that we cannot have a volume-optimal, oracle-based algorithm, even if we discard the oracle costs. Also, we introduce dual certifications -- an interval including all instances of a class -- thus providing apothem-minimum upper bounds to a robustness certification. Further, we present the ParallelepipedoNN system, which we evaluate on the standard MNIST and Fashion MNIST benchmarks. A preliminary comparison with existing work on the same datasets reveals at least two-fold improvement w.r.t. the minimum edge length.
Foundation for Reasearch and Technology - Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1
Certified training aims to produce models whose predictions can be formally verified against adversarial perturbations, typically by optimising upper bounds on the worst-case loss over an allowed perturbation set. For neural networks, certified training methods based purely on tight relaxation bounds produce networks that are amenable to certification, but sacrifice standard accuracy. Conversely, adversarial training often yields stronger empirical robustness and standard accuracy, but the resulting models are generally difficult to certify with neural network verifiers. Recently, the literature has shown that better standard-certified accuracy trade-offs can be achieved by combining adversarial training objectives with loose over-approximations based on Interval Bound Propagation (IBP), effectively interpolating between lower and upper bounds of the worst-case loss. Building on this, we introduce AD-CERT, a certified training objective that combines adversarial distillation with an IBP upper bound. We show that distilling adversarial information over the logit space from an empirically robust teacher provides an effective lower bound surrogate for certified training, with AD-CERT achieving state-of-the-art certified performance on several robustness benchmarks for ReLU networks. Furthermore, in a unified setup, distilling adversarial information at the logit-level is shown to improve certified accuracy over a robust feature-space distillation objective by up to 5.40 percentage points. Our code has been made available at https://github.com/matteo-melis/ad-cert.
Matteo Melis, Jesus Martinez Del Rincon, Vishal Sharma
Adversarial robustness is essential for deploying neural networks in safety-critical applications, yet standard evaluation methods either require expensive adversarial attacks or report only a single aggregate score that obscures how robustness is distributed across classes. We introduce the GF-Score (GREAT-Fairness Score), a framework that decomposes the certified GREAT Score into per-class robustness profiles and quantifies their disparity through four metrics grounded in welfare economics: the Robustness Disparity Index (RDI), the Normalized Robustness Gini Coefficient (NRGC), Worst-Case Class Robustness (WCR), and a Fairness-Penalized GREAT Score (FP-GREAT). The framework further eliminates the original method's dependence on adversarial attacks through a self-calibration procedure that tunes the temperature parameter using only clean accuracy correlations. Evaluating 22 models from RobustBench across CIFAR-10 and ImageNet, we find that the decomposition is exact, that per-class scores reveal consistent vulnerability patterns (e.g., ``cat'' is the weakest class in 76% of CIFAR-10 models), and that more robust models tend to exhibit greater class-level disparity. These results establish a practical, attack-free auditing pipeline for diagnosing where certified robustness guarantees fail to protect all classes equally. We release our code on GitHub.