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.
Foundation for Reasearch and Technology - Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1