Conceptio › Archive › arXiv CS

arXiv CSopen access

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

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

ICLR 2026 Workshop: Principled Design for Trustworthy AI

E XACT C ERTIFICATION OF N EURAL N ETWORKS AND PARTITION AGGREGATION E NSEMBLES AGAINST L ABEL P OISONING

arXiv:2604.11416v1 [cs.LG] 13 Apr 2026

Ajinkya Mohgaonkar1 , Lukas Gosch1,2,3 , Mahalakshmi Sabanayagam1,4 , Debarghya Ghoshdastidar1 , Stephan Günnemann1,2,3 1 School of Computation, Information and Technology, 2 Munich Data Science Institute Technical University of Munich, Germany, 3 Munich Center for Machine Learning, Germany 4 Australian Institute for Machine Learning, Adelaide University, Australia

A BSTRACT 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 ensemblelevel 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× fewer partitions, thus, challenging the prevailing notion that heavy partitioning is a necessity for strong certified robustness.

I NTRODUCTION

Machine learning models, especially those trained in supervised settings, are critically dependent on the integrity of labeled data. This reliance exposes them to label-flipping attacks, where the training labels are corrupted to degrade model performance, or induce targeted misclassifications (Biggio et al., 2011; Xiao et al., 2015). In response, a range of empirical defenses have been proposed, including data sanitization techniques that aim to identify and remove poisoned samples prior to training (Paudice et al., 2018), and adversarial training methods that improve robustness by learning on perturbed examples (Bal et al., 2025). However, these approaches often rely on heuristics and have been shown to fail under adaptive attacks (Carlini & Wagner, 2017; Athalye et al., 2018; Koh et al., 2022). This limitation has led to growing interest in robustness certificates, that provide formal guarantees about the robustness of a model’s predictions under a given adversarial threat model. Existing certificates against label-flipping poisoning attacks are predominantly derived using ensemble methods. Techniques include randomized smoothing (Rosenfeld et al., 2020), where base classifiers are trained on datasets with randomly perturbed labels, and partition aggregation (Levine & Feizi, 2021), which trains base classifiers on disjoint partitions of the training data. Since these certificates rely solely on the base classifier outputs, they are inherently black-box (Ashtiani et al., 2020). Black-box treatment of the base classifiers often leads to overly conservative guarantees and provides limited knowledge about the full extent of the ensemble’s robustness. One way to understand the true robustness of the certified model is to utilize white-box information of the base 1

Training Data

Partitions

Base Classifiers

Median Certified Robustness

ICLR 2026 Workshop: Principled Design for Trustworthy AI

ρ1 ScaLabelCert White-box certification

ρ2 Aggregation

ρ3

ρ4 White-box certificates

Ensemble-level certificate

200 150 100 SS-DPA EnsembleCert LB EnsemblCert UB

50 0 0

EnsembleCert

200

400

600

800

1000

Number of Partitions

(a) Two-step approach of EnsembleCert.

(b) EnsembleCert on CIFAR-10.

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. classifiers, i.e., white-box certificates, that leverage internal model information to yield tighter and more informative guarantees. This raises the question: How can we leverage white-box knowledge of the base classifiers to derive a stronger certificate for the ensemble? In this work, we answer this question by proposing EnsembleCert, a white-box certification framework for partition-based aggregation ensembling techniques (Levine & Feizi, 2021). We focus specifically on the partition-based approach since they are the current state-of-the-art certifiable defense against general data poisoning attacks (Levine & Feizi, 2021; Rezaei et al., 2023; Wang et al., 2022), including label-flipping. Additionally, neural networks can be used as base classifiers in this approach, as opposed to only linear classifiers in the randomized smoothing method (Rosenfeld et al., 2020). EnsembleCert yields tighter white-box guarantees by leveraging the model information of the base classifiers following a simple two-step approach: (i) Extract white-box certificates from the base classifiers for each partition; (ii) Aggregate the white-box certificates to derive an ensemble-wide certificate (see Fig. 1a). The problem of aggregating the partition-wise guarantees to obtain the certificate for the ensemble is formulated as an Integer Program (IP), which we show can be solved efficiently in polynomial time. Thus, given a base model and a certification method for extracting white-box knowledge from the chosen base model, EnsembleCert aggregates the white-box knowledge of base classifiers to achieve ensemble-wide guarantees. In this work, we focus on deriving ensemble-level guarantees when neural networks are chosen as the base model. For certifying neural networks as base models in EnsembleCert, existing white-box approaches face significant challenges as they either rely on computationally intense Mixed Integer Linear Program (MILP) formulation (Sabanayagam et al., 2025) or loose gradient-based parameter bounding approaches (Sosnin et al., 2025). To elaborate, solving the MILP is NP-hard in the worst case, hence LabelCert (Sabanayagam et al., 2025) is practical only for datasets with a few hundred training points and does not even scale to moderately sized datasets like MNIST and CIFAR-10. On the other hand, the parameter-bounding technique (Sosnin et al., 2025) provides overly loose guarantees, leading to vacuous bounds in just few training iterations, especially for multi-class classification tasks. Furthermore, the latter method has so far been evaluated only on small multi-layer perceptrons. These limitations make the existing methods unsuitable for white-box injection into EnsembleCert, naturally raising a broader question: Can we derive effective and scalable white-box certificates for neural networks against label-flipping attacks? We answer this question by developing ScaLabelCert, a framework that builds on the exact whitebox method of LabelCert (Sabanayagam et al., 2025). LabelCert derives the first exact certificate for neural networks against data poisoning by leveraging the equivalence between infinitely wide Neural Networks (NNs) trained with a soft-margin loss and Support Vector Machines (SVM) using the Neural Tangent Kernel (NTK) of the network as their kernel (Chen et al., 2021; Sabanayagam et al., 2023). ScaLabelCert shows that under certain conditions, the computation complexity of LabelCert can be reduced from NP-hard to polynomial time, thus, significantly improving the scalability. Beyond the SVM formulation, ScaLabelCert further extends LabelCert by leveraging the equivalence between infinitely-wide NNs trained with a regression loss and kernel regression under the NTK (Jacot et al., 2018; Arora et al., 2019). With its ability to efficiently compute tight certificates, we adopt ScaLabelCert as our primary mechanism for injecting white-box knowledge into EnsembleCert. 2

ICLR 2026 Workshop: Principled Design for Trustworthy AI

The tightness of the resulting partition-wise guarantees reveals the full potential of EnsembleCert and enables a reliable analysis of how partitioning contributes to robustness. Since ScaLabelCert is best suited for certifying infinite-width neural networks (see Sec. 5), we use this instantiation for our primary evaluation. To demonstrate the applicability of EnsembleCert with finite-width networks as base classifiers, we employ the gradient-based parameter bounding approach of (Sosnin et al., 2025) for base-classifier certification. We detail the process of integrating the gradient-based certificate into EnsembleCert and present the evaluation in Sec. D.4. Finally, to highlight that EnsembleCert is not restricted to neural networks, we also instantiate it with a smoothed linear classifier as the base model and apply randomized smoothing certificates (Rosenfeld et al., 2020) to each base classifier. Our contributions are summarized as follows: 1. We present EnsembleCert in Sec. 3.1, the first white-box certification framework for partition aggregation ensembles that leverages the knowledge about base-classifiers to provide white-box informed certificates for the ensemble in polynomial time. In our experimental set-up, we evaluate EnsembleCert with the following choices of base classifiers and corresponding certification methods: (i) Infinite-width neural networks with ScaLabelCert, (ii) Finite-width neural networks with gradient-based parameter bounding certificate by Sosnin et al. (2025) and (iii) Smoothed linear classifier with randomized smoothing based certificate by Rosenfeld et al. (2020). 2. With ScaLabelCert in Sec. 3.2, we derive the first polynomial-time solvable exact certificate for infinite-width neural networks against label-flipping attacks and thus, it is the first exact certificate for neural networks against a poisoning threat model that scales to common image benchmarks. 3. We show in Sec. 4 that for partition aggregation ensembles with a small number of partitions, the infusion of white-box knowledge results in significant improvement in certified robustness. On analyzing the dependence of certified robustness on the number of partitions, we demonstrate that in certain cases, using as low as 10 partitions with white-box knowledge results in stronger robustness guarantees in comparison to as high as 1000 partitions (see Fig. 1b). These findings call into question the emphasis on using very large numbers of partitions to achieve good certified robustness (Levine & Feizi, 2021), suggesting that excessively deep partitioning, which requires training a prohibitively large number of neural networks, is not a necessity to yield strong guarantees. Paper organization. We begin with preliminaries in Sec. 2. In Sec. 3.1 and Sec. 3.2, we introduce our main methods, EnsembleCert and ScaLabelCert, and present their technical details. Experimental results and insights derived are provided in Sec. 4, followed by a discussion in Sec. 5 and conclusion in Sec. 6. Related work and an extended discussion are deferred to the appendix Sec. C.

P RELIMINARIES

Notation. Matrices are denoted by bold uppercase letters, M, and vectors by bold lowercase letters, v. The (i, j)-th entry of a matrix M is denoted mji . For a positive integer C, we write [C] = {1, . . . , C}. The ℓ0 norm is denoted by ∥ · ∥0 , and 1condition represents the indicator function of a given condition. We use 1n for a vector of all 1s of size n. The floor operator is denoted by ⌊·⌋.

Label-flipping and Certification. In a supervised classification task, the training data S = (X, y) consists of feature vectors aggregated in X ∈ Rn×d and labels y ∈ [K]n , where K is the number of classes. A learning algorithm Lalg takes the training set S and a test sample t ∈ T , where T is the test set, as input to predict the label for t, i.e., Lalg (S, t) ∈ [K]. In a label-flipping attack, we assume that the adversary is allowed to change atmost r ≤ n training labels. Formally, an adversary can alter the clean labels y to ỹ ∈ Br (y) := ỹ ∈ [K]n ∥ỹ − y∥0 ≤ r and get a perturbed training set S̃ = (X, ỹ). As the certification objective, for every t ∈ T , we aim to find the maximum number of label flips r̃ in the clean training data up to which the prediction of Lalg for t does not change, i.e. r̃(t) = max r S̃

s.t.

Lalg (S, t) = Lalg (S̃, t) ∀S̃ ∈ {S ′ | y′ ∈ Br (y))}.

We will refer to r̃(t) as the certified radius for t. A point-wise certificate then would be a lower bound on the certified radius for a particular sample. The certificate is exact if it gives the true certified radius r̃(t) rather than just a lower bound. Semi-Supervised Deep Partition Aggregation (SS-DPA). Levine & Feizi (2021) introduce SSDPA, a framework that builds a certified defense against label-flipping poisoning attacks. The framework certifies a partition aggregation ensemble gS , i.e , an ensemble consisting of Np base 3

ICLR 2026 Workshop: Principled Design for Trustworthy AI

classifiers f{1,...,Np } trained on disjoint partitions P{1,...,Np } of the training data S. The motivation behind training on disjoint partitions is simple: Poisoning one label in the training data affects the prediction of only one of the base-classifiers. The training data S is first sorted without using the labels and then partitioned based on the sorted order. This ensures that the partitioning is invariant to any label poisoning attack. As the unlabeled data is trustworthy, we can make use of a selfsupervised learning algorithm to extract features from the entire unlabeled training data and train each fi using the extracted features and labels corresponding to Pi . At inference time, each base classifier fi , trained on its corresponding partition Pi of S predicts the class for a given test sample t ∈ T as fi (t) ∈ [K]. The prediction of the ensemble gS (t) is then determined by a majority vote: gS (t) = arg maxc∈[K] nc (t), where nc (t) := |{i ∈ [Np ] | fi (t) = c}| is the number of votes received by class c. Ties are resolved deterministically by choosing the smaller index. If we denote gS (t) as c∗ , the certificate ρ̃(t) for sample t is given as: nc∗ (t) − maxc′ ̸=c∗ (nc′ (t) + 1c′ <c∗ ) . 2 The above guarantee says that for a poisoned dataset S̃ obtained by changing the labels of at most ρ̃ samples in S, gS̃ (t) = c∗ . As each base classifier is treated as a black-box, the certificate derivation follows from a key worst-case assumption: The prediction of a base classifier can be changed by a single label flip. The formal description of the worst case scenario is presented in Sec. A.1. With white-box knowledge about the base classifiers, one can improve upon this worst-case assumption, leading to a tighter certificate for the ensemble. ρ̃(t) :=

M ETHODOLOGY: E NSEMBLE C ERT AND S CA L ABEL C ERT

3.1

E NSEMBLE C ERT

The underlying worst-case assumption in existing partition aggregation-based certificates, which says that the prediction of a base classifiers can be changed with a single label flip, can be overcome given that we have the following white-box information: for all base classifiers f{1,...,Np } and ∀c ∈ [K], we have access to ρci , which is the minimum number of label flips in Pi required to change the prediction of the base classifier fi (trained on Pi ) to class c. Access to the white-box knowledge through ρci enables verification of the worst-case assumption and provides the necessary information to derive a tighter ensemble-level certificate. Note that the ensemble-level certificate ρ̃(t) that represents the maximum number of flips upto which the ensemble prediction for a sample t remains unchanged, is simply one less than the minimum number of flips required to change the ensemble prediction. To determine the ensemble certificate ρ̃(t), we first compute, for each class c, the least number of flips needed to make c the majority class, and then take the minimum over all classes. Integer Program Formulation for Ensemble-wide Certification. We denote the problem of finding the minimum number of label flips in the training set required to change the prediction of the ensemble to a particular class c′ as P1 (c′ ). The white-box information ρci is collected in ρ ∈ RNp ×K . Given ρ, finding the optimal attack for the adversary, which is equivalent to solving P1 (c′ ), poses as a combinatorial optimization problem leading to an Integer Program (IP) formulation of P1 (c′ ). We denote the ith base classifier as fi if trained on the clean data and f˜i if trained on the perturbed data. The predictions from f{1,...,Np } and f˜{1,...,Np } on the sample t are collected in the vote configurations V and Ṽ ∈ RNp ×K respectively: ∀i ∈ Np , c ∈ [K] : vic = 1{fi (t) = PK PK c} , ṽic = 1{f˜i (t) = c}. Note that c=1 vic = 1 and c=1 ṽic = 1 for all i ∈ [Np ]. Concretely, to model P1 (c′ ), the number of label flips required to reach the vote configuration Ṽ from PNp PK c c ′ V is i=1 be the c=1 ρi ṽi . The constraint that c should majority class after adversarial maPNp c′ c nipulation of labels can be represented as i=1 ṽi − ṽi ≥ 1c<c′ , for all c ̸= c′ . Recollect PK c ′ c=1 ṽi = 1, ∀i ∈ [Np ] should also be satisfied. Thus, this gives the IP formulation of P1 (c ): P1 (c′ ) :

min Ṽ

Np K X X i=1 c=1

ρci ṽic

s.t.

∀c ̸= c′ :

Np X i=1

′ ṽic − ṽic ≥ 1c<c′ ,

∀i ∈ [Np ], ∀c ∈ [K] : 4

K X c=1

ṽic = 1,

ṽic ∈ {0, 1}.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

The ensemble-level certificate ρ̃(t) for a test sample t can then be derived, as mentioned in Sec. 3.1, by simply subtracting one from the minimum over P1 (c), that is, ρ̃(t) = minc∈[K]\c∗ P1 (c) − 1. Reduction to Polynomial-time. Solving P1 (c) in its current form is computationally prohibitive, scaling as O(2Np ×K ) in the worst case. Thus, deriving ρ̃ is even more expensive, with complexity O(K × 2Np ×K ). The problem becomes intractable even for small values of Np and K, motivating the need for a more tractable alternative. We denote as P2 (c′ ), a relaxation of P1 (c′ ) that finds the minimum number of label flips needed to make c′ surpass only c∗ (the original majority class) in the number of votes, rather than making c′ the overall majority class. The formulation of P2 (c′ ) can be PNp c′ obtained from P1 (c′ ) by relaxing the constraint i=1 (ṽi − ṽic ) ≥ 1c<c′ ∀c ̸= c′ to the constraint ′ ∗ c c (ṽi − ṽi ) ≥ 1c∗ <c′ . Despite this relaxation, we have the following result proved in Sec. A.2.

Theorem 1 (Equivalence between problems P1 and P2 ). min P1 (c) =

c∈[K]\c∗

min P2 (c)

c∈[K]\c∗

The intuition for the above result is as follows: while trying to make c′ surpass c∗ , if another class c′′ becomes the majority class, then changing the ensemble prediction to c′′ should be easier compared to c′ . This result is particularly important, as we show that P2 (c) can be reduced to an instance of the Multiple Choice Knapsack Problem (MCKP). Since MCKP is solvable in pseudopolynomial-time (Dudzinski & Walukiewicz, 1987), our approach achieves a complexity of O(Np2 ) for solving P2 per class (Sec. A.2). Consequently, the ensemble-wide certificate ρ̃(t) can be computed in polynomial time by solving P2 (c) for every class and finding the minimum, that is, ρ̃(t) = minc∈[K]\c∗ P2 (c) − 1. This represents a substantial improvement over the naive ILP formulation with complexity O(K× 2Np ×K ). We refer to Sec. A.3 for details on the reduction of P2 (c′ ) to MCKP. 3.2

E XTRACTION OF W HITE - BOX K NOWLEDGE T HROUGH S CA L ABEL C ERT

The approach of our white-box certificate ScaLabelCert builds on the framework introduced by LabelCert (Sabanayagam et al., 2025). LabelCert provides an exact certificate that determines whether the model prediction remains unchanged when at most r training labels are flipped. This definition of the certificate does not immediately align with the white-box knowledge that EnsembleCert utilizes, which is the minimum number of label flips required to change the prediction of the classifier to a particular class. Even more problematic, the computation of the certificate by LabelCert is NP-hard and only scales to a few hundred labeled datapoints. ScaLabelCert makes modifications to the LabelCert approach to address these shortcomings, which result in the computation of an exact certificate against label-flipping attacks in polynomial time. Next, we provide a brief overview of the approach by LabelCert, and then introduce the developments leading to ScaLabelCert. Infinite-Width Neural Networks and The Equivalence to Kernel Methods. The Neural Tangent Kernel (NTK) of a neural network fθ between two inputs i and j with features xi and xj is defined as Qji = Eθ [⟨∇θ fθ (xi ), ∇θ fθ (xj )⟩], where the expectation is taken over the parameter initialization. When fθ is an infinitely wide neural network, the dynamics of training fθ for a classification task using a soft-margin loss are the same as those of an SVM with fθ ’s NTK as kernel (Chen et al., 2021). Similarly, if a regression loss (regularized mean-square) is used, the training dynamics are equivalent to those of kernel regression using fθ ’s NTK as kernel (Jacot et al., 2018). LabelCert. For a test sample t, LabelCert computes a point-wise certificate for sufficiently wide neural networks, by deriving a certificate for a kernel SVM with fθ ’s NTK as kernel, which—due to the above equivalence—extends to a certificate for fθ . Recall that in the dual formulation of an SVM, the parameters are the dual variables α ∈ Rn derived by solving the following problem: Psvm (y) = min − α

n X i=1

αi +

1 XX αi αj yi yj Qji 2 i=1 j=1

s.t.

0 ≤ αi ≤ C, ∀i = [n]

where n is the number of training data, C is the regularization parameter that controls the trade-off between maximizing the margin and minimizing classification error, and Qji is the chosen kernel between inputs i and j. Let the set of α vectors solving Psvm (y) be S(y). The prediction for a test 5

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Pn sample t is given by pt = sign( i=1 αi ỹi Qit ). Let p̂t be the prediction of the SVM trained using clean labels. The certificate is computed by converting the following problem Pcert (y) to a MILP: Pcert (y) := min sign(p̂t ) ỹ,α

n X

αi ỹi Qit

ỹ ∈ Ar (y), α ∈ S(ỹ)

s.t.

i=1

Whether the model prediction for t is robust up to r label flips or not is determined by the sign of the solution to Pcert (y), with a positive sign indicating robustness. SVM Formulation for Sufficiently Small C. The complexity of solving Pcert (y) comes largely from replacing the inner optimization problem α ∈ S(ỹ) with the KKT (Karush-Kuhn-Tucker) conditions of Psvm (y), which can be done as Psvm (y) is convex (Dempe & Dutta, 2012; Sabanayagam et al., 2025). We show that on using a sufficiently small C, we can entirely forego the inner optimization problem and convert Pcert (y) to a simpler, single-level problem based on Theorem 2. Theorem 2. Given a soft margin SVM with regularization C, kernel entry between training samples i , j as Qji , and α being the solution to Psvm (y), then if X j 1 max |Qi | ≤ , it follows that ∀y ∈ {−1, 1}n : α = C · 1n C i∈[n] j∈[n]

The proof is presented in Sec. A.4. When C satisfies the condition stated above, the alpha values are equal to C regardless of the labels. Thus, choosing C appropriately gives us the liberty to eliminate the inner optimization problem α ∈ S(ỹ) as α is invariant to different labelings of the data. The Pn i SVM prediction in this case simplifies to p = sign( C ỹ t i Qt ). As C is a positive constant, this i=1 Pn i further simplifies to pt = sign( i=1 ỹi Qt ). Integrating this insight into ScaLabelCert, we develop an efficient computation scheme for exact white-box certificates for infinite-width networks below that calculates the minimum number of label flips needed to change the prediction of the model. ScaLabelCert For The Binary Setting. Our objective is to find the Pnminimum number of label flips required to change the SVM prediction, i.e., to make sign(p̂t ) i=1 αi ỹi Qit negative. Under sufficiently small C, the above objective can be formulated as: n

O1 (y) :

min n

ỹ∈{−1,1}

1X (1 − yi ỹi ) 2 i=1

s.t.

sign(p̂t )

n X i=1

ỹi Qit < 0, ∀i ∈ [n] : ỹi ∈ {−1, 1}.

O1 (y) can be solved in polynomial time (Sec. A.5). Pn The intuition is that the labels corresponding to the largest positive contributions in sign(p̂t )( i=1 yi Qit ) are the most influential in determining the prediction, so flipping these labels greedily till the prediction changes is the optimal attack from the adversary’s point of view. Thus, solving O(y) leads to a polynomial time computable exact certificate for sufficiently-wide neural networks, if fθ ’s NTK is chosen as the SVM’s kernel. ScaLabelCert For The Multi-Class Setting. For the multi-class case, we use the one-vs-all strategy by decomposing the problem with K classes into K separate binary classification tasks. For each class c ∈ [K], a binary classifier is trained to distinguish between samples of class c and samples from all other classes. Assume that pc is the prediction score of a classifier for the learning problem corresponding to class c. Then, the class prediction c∗ for a test sample is constructed by c∗ = arg maxc∈[K] pc . The labels are collected in the vector y where yic = 1 if the class of the ith sample is c, and 0 otherwise. Recall that for each base classifier, EnsembleCert requires white-box certificates that determine, for every class, the minimum number of label flips needed to change the model’s prediction to that class. Using a soft-margin kernel SVM with a sufficiently small C as our base model, the certificate computing minimum number of label flips required to change the prediction of the model to a particular class c′ can be formulated as (derived in Sec. A.6):  O1 (c′ ) :

min ỹ

X i∈[N ]

1 −

 X

yic ỹic 

s.t.

c∈[K]

′

ỹic Qit >

i∈[N ]

∀i ∈ [N ], c ∈ [K] : 6

X i∈[N ]

ỹic Qit ∀c ̸= c′ ,

X c∈[K]

ỹic = 1 , ỹic ∈ {0, 1}.

(1)

100

75 50

SS-DPA EnsembleCert LB EnsembleCert UB

25 0

100

200

300

400

Number of Partitions

(a) CIFAR-10

500

200

SS-DPA EnsembleCert LB EnsembleCert UB

75 50

100 SS-DPA EnsembleCert LB EnsemblCert UB

25 0

0 0

250

500

750

1000

SS-DPA EnsembleCert LB EnsembleCert UB

300

150

200

400

600

800

1000

Number of Partitions

(b) MNIST

200 100 0

1250

Number of Partitions

MCR

125

100

MCR

125

MCR

ICLR 2026 Workshop: Principled Design for Trustworthy AI

250

500

750

1000

1250

Number of Partitions

(d) MNIST, λ = 0.1

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.

While solving O1 (c′ ) is NP-hard, we show that tight lower and upper bounds for the solution of O1 (c′ ) can be computed in polynomial time (see Sec. A.7). Certificate for Kernel Regression. With minor modifications, we can leverage the above formulation to certify a kernel regression model. Specifically, the adjustment is to replace Qit with (Qeff )it = [(Qtrain + λI)−1 Qt,: ]i where Qtrain is the kernel matrix for the training samples; Qt,: is the vector of kernel entries for test sample t and the training samples; and λ is the regularization parameter. Deriving the certificate for kernel regression with the above modifications, we certify a sufficiently wide NN trained on a regularized mean-squared loss by using the network’s NTK as the kernel. Exact Certificate Given No Partitioning (Np = 1). When there is no partitioning, we do not need to solve O1 (c′ ) exactly for every c′ to get an exact certificate for a stand-alone model. As O1 (c′ ) represents the number of flips required to change the prediction to a particular class c′ , the exact certificate for the stand-alone model can be derived by simply computing the minimum over O1 (c′ ) i.e, ρ̃(t) = minc∈[K]\c∗ O1 (c) − 1. We show that with ScaLabelCert, this can be solved in polynomial time, by employing a similar line of argument as Theorem 1. The proof is presented in Sec. A.6. This results in the first exact certificate for neural networks against a poisoning attack that scales to common image benchmark datasets like MNIST or CIFAR-10.

E XPERIMENTS AND R ESULTS

Implementation Details. We perform experiments on MNIST, CIFAR-10, and binary MNIST 1vs-7. Following SS-DPA (Levine & Feizi, 2021), before training the base-classifiers we extract unsupervised features using RotNet (Gidaris et al., 2018) for MNIST and SimCLR (Chen et al., 2020) for CIFAR-10, using pretrained models from Levine & Feizi (2021). For the supervised training of base-classifiers, the extracted RotNet features for MNIST are used as input to an infinitely-wide convolutional network with a one convolutional layer and no pooling for supervised classification. For CIFAR-10, SimCLR features are fed to an infinitely-wide fully-connected network with one hidden layer and no non-linear activation. NTK computations are performed using the Google neural-tangents library (Novak et al., 2020). Using the NN-kernel equivalence (Sec. 3.2), the NTK is then used either with a kernel SVM for wide NNs trained on the soft-margin loss or with kernel regression for wide NNs trained on the regularized mean-squared loss. Solving the MCKP for ensemble-level certificates as described in Sec. 3.1 is implemented using standard dynamic programming. The metrics used for evaluation are certified accuracy, with certified accuracy at r label flips being the fraction of test samples for which the model prediction is correct and robust up to r label flips; and median certified robustness (MCR), which denotes the number of label flips upto which the model prediction for 50% of the correctly classified samples is robust. We provide further implementation details and certification runtimes in Sec. D.1. Experiments. We instantiate EnsembleCert with sufficiently wide NNs trained on the soft-margin loss (equivalent to kernel SVMs with NTK) and the regularized mean square loss (equivalent to kernel ridge regression with NTK). Although regression losses may seem ill-suited for classification, 7

ICLR 2026 Workshop: Principled Design for Trustworthy AI

1.2

1.6

0.50 0.25 0.00 0

200

400

600

800

Budget (Number of Flips)

(a) CIFAR-10: SVM

1000

Label flips (Percent of training data)

2.0

Num Partitions 1 10 100 1000

0.0

0.2

0.4

0.6

0.8

0.0

1.0

Num Partitions 1 12 120 1200

0.75 0.50 0.25 0.00 0

200

400

600

800

0.5

0.4

0.6

0.8

0.0

200

400

600

800

1000

Budget (Number of Flips)

(b) MNIST: SVM

Label flips (Percent of training data)

1.0

Partitions 1 10 100 600

1000

0.2

1.0

0.0

Certified Accuracy

0.8

Certified Accuracy

0.4

Certified Accuracy

Label flips (Percent of training data)

0.0 0.75

0.2

0.4

0.6

0.8

1.0

Num Partitions 1 10 25 50

0.75 0.50 0.25 0.00 0

200

400

600

800

1000

Budget (Number of Flips)

(d) CIFAR-10: RS

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. they work well in practice (Mika et al., 1999; Rifkin et al., 2003). Moreover, Arora et al. (2019) showed that kernel ridge regression with the NTK of convolutional NNs achieves competitive performance on image datasets. On CIFAR-10, we evaluate EnsembleCert additionally on two different types of base classifiers (i) Finite-width networks and (ii) Smoothed linear classifiers. The relevant implementation details can be found in Sec. D.4 and Sec. B respectively. For every choice of base classifier, we observe that injecting white-box knowledge into the ensemble substantially increases certified robustness for low to intermediate numbers of partitions, highlighting the relative looseness of guarantees obtained using the black-box approach. The substantial improvement in certified robustness achieved by our white-box certificate for kernel methods as base classifiers is evident in Fig. 2. Further results demonstrating the same for every choice of base classifier can be found in Sec. D. The gap between the white-box and black-box certificates narrows as the number of partitions grows, with the white-box certificate eventually converging to the black-box certificate. This convergence reflects the realization of the worst-case scenario, where a single label flip can alter the prediction of a base classifier. Beyond the point of convergence, our method performs on par with the black-box approach. This behavior is a direct consequence of our method’s design and holds consistently across all experiments. In the next sections, we present some crucial insights that can be derived from our evaluation of EnsembleCert and ScaLabelCert. Invariance to Number of Partitions with Kernel SVM. For the instantiation of EnsembleCert with kernel SVM, we use a regularization parameter C that is small enough to satisfy the condition in Theorem 2, as it is the key to computing scalable certificates for kernel SVM. We observe that the MCR of the white-box certificate remains largely invariant to the number of partitions for CIFAR-10 (Fig. 2a) and MNIST 1-vs-7 (Fig. 13a) until the point of convergence. On MNIST, there is a sharp decline initially on increasing the number of partitions, followed by plateauing (Fig. 2b). These findings indicate that strong guarantees can be achieved without requiring overly large ensembles. Robustness Decay with Kernel Regression. For our instantiation of EnsemblCert with kernel ridge regression, we study the effect of the regularization parameter λ on certified robustness of the ensemble. For each dataset, we observe that the trend of certified robustness varies with the regularization parameter λ. As we increase λ from very small values, MCR initially improves with the number of partitions. Beyond a dataset-specific threshold, however, the trend reverses—increasing the number of partitions leads to lower certified robustness. For example, on CIFAR-10, when λ = 100 (which lies beyond the threshold for this dataset), EnsembleCert certifies a median of 219 label flips with just 10 partitions, whereas using 1000 partitions reduces this to 173 (Fig. 2c). Similarly, on MNIST with λ = 0.1, EnsembleCert certifies 356 label flips using only 12 partitions, whereas using 1200 partitions lowers the certified robustness to 82 (Fig. 2d).We present plots for low values of λ and discuss the behavioral change across the spectrum of λ in Sec. D.5. As robust kernel regression is associated with the use of higher values of λ (Hu et al., 2021), the decreasing trend of the MCR observed with high λ suggests that deeper partitioning limits the true robustness potential of the ensemble when the underlying base classifier has a high degree of robustness. To Partition or Not to Partition? The polynomial-time calculable exact certification method derived by ScaLabelCert allows us to analyze the robustness of sufficiently wide neural networks without employing an ensemble, that is, Np = 1. While the simplification under small C eliminates the need to calculate the training kernel for kernel SVM, making it easily scalable to datasets such as CIFAR-10 and MNIST, it remains an essential component of the pipeline for kernel regression. 8

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Thus, performing kernel regression on such datasets without partitioning is computationally challenging due to the need to compute the entire training kernel. Hence, in the no-partition setting, we evaluate ScaLabelCert using the efficient kernel SVMs on all datasets and evaluate using kernel regression only on the relatively small MNIST 1-vs-7 binary dataset. On CIFAR-10, ScaLabelCert achieves non-trivial certified accuracy for up to 1000 label flips, which amounts to 2% of the training data Fig. 3a. In contrast, the evaluation by Levine & Feizi (2021) fails to certify any test sample beyond 500 label flips. Additionally, we compare our method with the gradient-based parameter bounding technique from Sosnin et al. (2025) and show that ScaLabelCert significantly outperforms their method on CIFAR-10 in certified accuracy. Refer to Sec. D.3 for details. Motivated by the observation that deeper partitioning may limit the ensemble’s true robustness potential, we further investigate the role of partitioning by comparing the certified accuracy of a single base model against that of its partition-aggregated ensemble. Our experiments across multiple datasets and base model choices, as shown in Fig. 3, reveal that a single base model trained on the entire training dataset achieves significantly higher certified accuracy as compared to its partition-aggregation ensemble. This raises an important question: Does partition aggregation enhance or diminish the robustness potential of a given base model?

D ISCUSSION

We discuss the most important points here and refer to the appendix (Sec. C) for extended discussion, including related work. Certificate validity for finite-width neural networks. ScaLabelCert leverages the equivalence of infinite-width kernel methods with kernel methods induced by the NTK. This equivalence in training dynamics and model outputs is exact only in the infinite-width case. For a finite-width neural network however, where w denotes the smallest layer width of the network, the output difference of √ w with probability p = 1 − exp(−Ω(w)), as shown the network to the SVM is bounded by O ln w in Gosch et al. (2025), Liu et al. (2020). Thus, our certificates obtained by utilizing the neural network and NTK equivalence based on kernel SVM and regression represent an asymptotically exact certificate as the width w approaches infinity. On Using Sufficiently Small C in Kernel SVM. The choice of the parameter C, which controls the penalty for misclassifications, introduces a robustness–accuracy trade-off in soft-margin SVMs. Smaller values of C improve robustness to label noise and adversarial perturbations, as they encourage larger margins and reduce the influence of individual (potentially corrupted) points on the decision boundary. Thus, our choice of C for the SVM simplification in Theorem 2 aligns with building robust base-classifiers. Although this choice may not be optimal for clean accuracy, We show that performance remains competitive. We ask the reader to refer to Sec. D.2 for a discussion on the robustness-accuracy trade-off and the corresponding experiments.

C ONCLUSION

We introduce EnsembleCert, a framework that leverages model information from base-classifiers to yield significantly tighter ensemble-level certificates against label-flipping attacks in polynomial time . To efficiently extract the white-box information, we develop ScaLabelCert, a framework for the exact certification of sufficiently-wide NNs against label-flipping attacks. ScaLabelCert computes exact certificates against label flipping attacks in polynomial time, making it the first polynomial-time exact certification method that can certify (wide) NNs against data poisoning attacks. Through our evaluation of EnsembleCert instantiated with sufficiently wide NNs, we observe that with robust base-classifiers, the partition aggregation ensemble can achieve stronger guarantees using notably few partitions, outperforming excessively deep partitioning. This is crucial, as excessively deep partitioning requires training a very large number of base-classifiers, introducing significant computational overhead and limiting scalability. The experiments evaluating ScaLabelCert on stand-alone models indicate that employing partition aggregation ensembles does not always bring out the true robustness potential of the chosen base classifier architecture. Overall, our findings motivate the development of effective white-box certificates for finite-width neural networks to bring out the true robustness of a partition aggregation ensemble and to understand the role of partition-based ensembling itself in achieving strong robustness guarantees. 9

ICLR 2026 Workshop: Principled Design for Trustworthy AI

E THICS S TATEMENT Our work introduces EnsembleCert and ScaLabelCert, which, for the first time, leverage whitebox information to quantify the worst-case robustness of partition aggregation ensembles of neural networks against label poisoning. Although such capabilities could, in principle, be misapplied by adversaries, we contend that understanding these vulnerabilities is essential for the trustworthy and safe use of neural networks. We therefore hold that the advantages of advancing robustness research outweigh the potential downsides, and we do not anticipate any immediate risks arising from our contributions.

R EPRODUCIBILITY S TATEMENT The full codebase, along with configuration files for every experiment, is available at https: //github.com/ajinkya-mohan/ensembleCert.

ACKNOWLEDGEMENTS This paper has been supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the German Federal Ministry of Education and Research; by the German Research Foundation, grant GU 1409/4-1; as well as by the TUM Georg Nemetschek Institute Artificial Intelligence for the Built World.

R EFERENCES Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, 2019. Hassan Ashtiani, Vinayak Pathak, and Ruth Urner. Black-box certification and learning under adversarial perturbations. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 388–398. PMLR, 2020. Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning (ICML), 2018. Melis Ilayda Bal, Volkan Cevher, and Michael Muehlebach. Adversarial training for defense against label poisoning attacks. In International Conference on Learning Representations (ICLR), 2025. Song Bian, Xiating Ouyang, Zhiwei Fan, and Paraschos Koutris. Naive bayes classifiers over missing data: Decision and poisoning. In Proceedings of the 41st International Conference on Machine Learning (ICML / PMLR), 2024. Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. In Proceedings of the 3rd Asian Conference on Machine Learning, ACML. PMLR, 2011. Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (S&P), 2017. Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning (ICML). PMLR, 2020. Yilan Chen, Wei Huang, Lam M. Nguyen, and Tsui-Wei Weng. On the equivalence between neural network and support vector machine, 2021. Stephan Dempe and Joydeep Dutta. Is bilevel programming a special case of a mathematical program with complementarity constraints? Mathematical Programming, 2012. 10

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Samuel Drews, Aws Albarghouthi, and Loris D’Antoni. Proving data-poisoning robustness in decision trees. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2020. Kazimierz Dudzinski and Stanislaw Walukiewicz. Exact methods for the knapsack problem and its generalizations. European Journal of Operational Research, 1987. Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference on Learning Representations (ICLR), 2018. Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, and Stephan Günnemann. Provable robustness of (graph) neural networks against data poisoning and backdoor attacks. Transactions on Machine Learning Research, 2025. Tianyang Hu, Wenjia Wang, Cong Lin, and Guang Cheng. Regularization matters: A nonparametric perspective on overparametrized neural network. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 2021. Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, 2018. Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021. Jinyuan Jia, Yupei Liu, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning and backdoor attacks. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 2022. Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. Machine Learning, 2022. Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks. In International Conference on Learning Representations (ICLR), 2021. Chaoyue Liu, Libin Zhu, and Mikhail Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant, 2020. Anna P. Meyer, Aws Albarghouthi, and Loris D’Antoni. Certifying robustness to programmable data bias in decision trees. In Advances in Neural Information Processing Systems (NeurIPS), 2021. S. Mika, G. Rätsch, J. Weston, B. Schölkopf, and K. R. Müller. Fisher discriminant analysis with kernels. In Neural Networks for Signal Processing IX: Proceedings of the 1999 IEEE Signal Processing Society Workshop (Cat. No.98TH8468), 1999. Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference on Learning Representations (ICLR), 2020. Andrea Paudice, Luis Muñoz-González, Andras Gyorgy, and Emil C Lupu. Label sanitization against label flipping poisoning attacks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2018. Keivan Rezaei, Kiarash Banihashem, Atoosa Chegini, and Soheil Feizi. Run-off election: Improved provable defense against data poisoning attacks. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023. Ryan Rifkin, Gene Yeo, and Tomaso Poggio. Regularized least-squares classification. Advances in Learning Theory: Methods, Model and Applications, NATO Science Series III: Computer and Systems Sciences, 190, 06 2003. Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to labelflipping attacks via randomized smoothing. In International Conference on Machine Learning (ICML), 2020. 11

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Mahalakshmi Sabanayagam, Pascal Mattia Esser, and Debarghya Ghoshdastidar. Analysis of convolutions, non-linearity and depth in graph neural networks using neural tangent kernel. Transactions on Machine Learning Research, 2023. Mahalakshmi Sabanayagam, Lukas Gosch, Stephan Günnemann, and Debarghya Ghoshdastidar. Exact certification of (graph) neural networks against label poisoning. In International Conference on Learning Representations (ICLR), 2025. Philip Sosnin, Mark Niklas Mueller, Maximilian Baader, Calvin Tsay, and Matthew Robert Wicker. Certified robustness to data poisoning in gradient-based training. Transactions on Machine Learning Research, 2025. Binghui Wang, Xiaoyu Cao, Jinyuan jia, and Neil Zhenqiang Gong. On certifying robustness against backdoor attacks via randomized smoothing, 2020. Wenxiao Wang, Alexander J Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In Proceedings of the 39th International Conference on Machine Learning (ICML), 2022. Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. In Proceedings of the IEEE Symposium on Security and Privacy (SP), 2023. Han Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Adversarial label flips attack on support vector machines. In 20th European Conference on Artificial Intelligence (ECAI), 2015. Yuhao Zhang, Aws Albarghouthi, and Loris D’Antoni. Bagflip: A certified defense against data poisoning. In Proceedings of NeurIPS (Advances in Neural Information Processing Systems), 2022.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

T HEORETICAL D ETAILS

A.1

T HE FORMAL DESCRIPTION OF THE WORST CASE SCENARIO

Recall that the prediction of the partition aggregation ensemble gS (t) is determined by a majority vote over the prediction by the base classifiers f{1,...,Np } : gS (t) = arg maxc∈[K] nc (t), where nc (t) := |{i ∈ [Np ] | fi (t) = c}| is the number of votes received by class c. Ties are resolved deterministically by choosing the smaller index. If we denote gS (t) as c∗ , the certificate ρ̃(t) for sample t, that computes the number of adversarial label flips upto which the prediction of the ensemble will not change, as derived by black-box treatment of the base classifier is given as: nc∗ (t) − maxc′ ̸=c∗ (nc′ (t) + 1c′ <c∗ ) ρ̃(t) := . 2 As each base classifier is treated as a black box, the certificate derivation follows from a key worstcase assumption: The prediction of certain base classifiers can be altered by a single label flip. The formal description of the worst-case scenario is given below. Formalising the worst-case scenario: Let Csec := arg maxc̸=c∗ (nc (t) + 1c<c∗ ). One can think of Csec as the set of runner-up classes. We define Pmaj as the set of base classifiers that voted for c∗ . The worst-case scenario can be represented as: ∃ c′ ∈ Csec s.t. the prediction of at least ρ̃ + 1 base classifiers in Pmaj can be changed from c∗ to c′ with one label flip in their corresponding partitions. In such a scenario, attacking the corresponding base classifiers with one label flip each would change the prediction of the ensemble to c′ . Note that the numerator in ρ̃: nc∗ − maxc′ ̸=c∗ (nc′ (t) + 1c′ <c∗ ), is the difference in the number of the votes received by the majority class c∗ and c′ . Flipping the vote of a base classifier from c∗ to c′ bridges the gap between c∗ and c′ by 2 votes, explaining the 2 in the denominator. In light of the worst-case assumption, the reader can now see that the certificate actually calculates the number of base classifiers whose prediction needs to be flipped in order to change the ensemble prediction. With white-box knowledge about the base classifiers, we can improve upon the worstcase assumption, leading to a tighter certificate for the ensemble. One could argue that we need the white-box information solely about the base classifiers in Pmaj and classes in Csec to challenge the assumption. The point to note is that if information about Pmaj indicates that the worst-case scenario cannot be realized, we cannot assume that the adversary will attack partitions only in Pmaj and change the prediction to a class in Csec . Hence, to derive a tighter certificate, we would need this information for all base classifiers and classes. A.2

T HEOREM 1: min P1 (c) = min P2 (c)

Intuition. Recall that P1 (c′ ) denotes the minimum number of label flips needed to make c′ the majority class, whereas P2 (c′ ) denotes the minimum number of label flips needed to make c′ surpass the current majority class c∗ in number of votes. Intuitively, if c′ is the class that requires the fewest flips to become the new prediction, then making it just beat c∗ will already make it the majority class. Vote Configuration Let Ṽ ∈ {0, 1}Np ×K denote the perturbed vote configuration, where ṽic = 1 if partition i votes for class c after label flips, and 0 otherwise. Let V denote the clean vote configuration. We define O(Ṽ) as the number of label flips required to reach configuration Ṽ starting from the clean configuration V. Restatement of P1 (c′ ). Recall that P1 (c′ ) is defined as the minimum number of label flips needed to make c′ the majority class. In Sec. 3.1, the contraint was formulated through the set of inequalities Np X i=1

′ ṽic − ṽic ≥ 1c<c′ ,

∀c ∈ [K] \ c′ ,

which constraints c′ to be the majority class (with deterministic tie-breaking). For brevity, we PNp c now re-express this condition using the function majVote(Ṽ) := arg maxc∈[K] i=1 ṽi , as c′ = majVote(Ṽ) where ties are resolved deterministically by choosing the class with the smaller index. 13

ICLR 2026 Workshop: Principled Design for Trustworthy AI

With this shorthand notation, we write P1 (c′ ) = min O(Ṽ) Ṽ

s.t.

c′ = majVote(Ṽ), K X

ṽic = 1,

c=1 ṽic ∈ {0, 1},

∀i ∈ [Np ], ∀i ∈ [Np ], ∀c ∈ [K].

Restatement of P2 (c′ ). Problem P2 (c′ ) relaxes the above by requiring c′ to surpass only the original majority class c∗ , instead of all classes: P2 (c′ ) = min O(Ṽ) Ṽ

s.t.

Np X i=1 K X

′

ṽic − ṽic

ṽic = 1,

c=1 ṽic ∈ {0, 1},

Theorem (Restating Theorem 1).

min

c′ ∈[K]\{c∗ }

∗

≥ 1c∗ <c′ ,

∀i ∈ [Np ], ∀i ∈ [Np ], ∀c ∈ [K].

P1 (c′ ) = ′ min ∗ P2 (c′ ) c ∈[K]\{c }

Proof. We first state three lemmas and then combine them to prove the theorem. Lemma 1. ∀c′ ∈ [K] \ c∗ ,

P1 (c′ ) ≥ P2 (c′ ).

Proof. The feasible region of P1 (c′ ) is contained within that of P2 (c′ ) since the latter has a weaker constraint. Hence, P2 (c′ ) can only be smaller (or equal) to P1 (c′ ). Lemma 2. ∀c∗1 ∈ arg minc′ ∈[K]\c∗ P1 (c′ ),

P1 (c∗1 ) = P2 (c∗1 ).

Proof. By contradiction. Suppose P1 (c∗1 ) > P2 (c∗1 ). Let S̃ be the optimal solution for P2 (c∗1 ), i.e., O(S̃) = P2 (c∗1 ).

(2)

Since O(S̃) < P1 (c∗1 ), S̃ is not feasible for P1 (c∗1 ). As the feasibility for P1 (c∗1 ) requires c∗ to be the majority class, there must exist some c∗s ̸= c∗1 such that c∗s = majVote(S̃). Note that S̃ is feasible for P1 (c∗s ) as c∗s is the majority class for the vote configuration (S̃), so O(S̃) ≥ P1 (c∗s ).

(3)

Combining (2) and (3) with the assumption that P1 (c∗1 ) > P2 (c∗1 ) gives P1 (c∗1 ) > P1 (c∗s ), contradicting the assumption that c∗1 minimizes P1 (c′ ). Lemma 3. ∃z ∗ ∈ arg minc′ ∈[K]\c∗ P2 (c′ ) such that P1 (z ∗ ) = P2 (z ∗ ). Proof. Let c∗2 ∈ arg minc′ ∈[K]\c∗ P2 (c′ ) and let S̃ be the vote configuration in the optimal solution for P2 (c∗2 ), i.e, O(S̃) = P2 (c∗2 ). (4)

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Let z ∗ = majVote(S̃). Then S̃ is feasible for both P1 (z ∗ ), that requires z ∗ to be the majority class and P2 (z ∗ ), that requires z ∗ to have higher votes than c∗ , implying O(S̃) ≥ P2 (z ∗ )

and

(5)

O(S̃) ≥ P1 (z ∗ ).

(6)

With (4), (5) and the minimality of c∗2 , we have z ∗ ∈ arg minc′ ∈[K]\c∗ P2 (c′ ) and O(S̃) = P2 (z ∗ ). Combining this result with (6) and using Lemma 1.1 we conclude P1 (z ∗ ) = P2 (z ∗ ). Proof of Theorem 1. Let c∗1 ∈ arg minc′ ∈[K]\c∗ P1 (c′ ) and z ∗ ′ ∗ ∗ arg minc′ ∈[K]\c∗ P2 (c ) s.t. P1 (z ) = P2 (z ). . Using Lemmas 1.2 and 1.3, we obtain

∈

P1 (z ∗ ) = P2 (z ∗ ) ≤ P2 (c∗1 ) = P1 (c∗1 ), which implies

P1 (c∗1 ) = P1 (z ∗ ) = P2 (z ∗ ),

thus proving that min

c′ ∈[K]\{c∗ }

A.3

P1 (c′ ) = ′ min ∗ P2 (c′ ) . c ∈[K]\{c }

R EDUCTION TO MCKP AND COMPLEXITY ANALYSIS

In this section, we will use the terms base classifiers and partitions interchangeably, and discuss the optimal attack from an adversary’s point of view to make c′ surpass c∗ . Let’s denote the set of partitions that voted for c∗ originally as Pmaj , the ones that voted for c′ originally as Ptarget and rest of the partitions as Prest . Formally: ∗

Pmaj = {i ∈ [Np ] | vic = 1},

′

Ptarget = {i ∈ [Np ] | vic = 1},

Prest = [Np ]\(Ptarget ∪ Pmaj ).

The adversary will not attack partitions in Ptarget . If a partition in Prest is attacked, the vote can change only to c′ . Changing the vote to any other class will deem the label perturbation pointless. Let Ci be the set of classes that partition i could vote for after the optimal attack: ∀i ∈ Prest : Ci = {c ∈ K | c = c′ or vic = 1} , ∀i ∈ Ptarget : Ci = {c′ }.

Note that ∀i ∈ [Np ], we need the binary variable ṽic only if c ∈ Ci . Attacking a partition in Pmaj could change the vote to c′ or to the class with the minimal number of flips required for a prediction change to that class. Formalizing the above notion, we define cmin as: ∀i ∈ Pmaj : cmin (i) = arg minc∈[K]\c∗ ρci . Given this we have: ∀i ∈ Pmaj : Ci = {c ∈ K | c = c′ or c = cmin (i) or c = c∗ }. PNp c′ c∗ We model the constraint C1 := i=1 (ṽi − ṽi ) ≥ 1c∗ <c′ differently. Let d be the original PNp c∗ ′ difference between the number of votes for c′ and c∗ : d = i=1 (vi − vic ). We define ric to be the reduction in the gap between c′ and c∗ caused by flipping the vote of partition i to class c. For partitions in Pmaj , if the vote changes to c′ , the difference will decrease by 2. If the vote goes to any other class, the reduction is by 1. It is trivial to see that ∀i ∈ Ptarget , c ∈ Ci : ric = 0. We can similarly define these values for partitions in Prest and get:  ′ 2 if c = c 1 c c ∀i ∈ Pmaj , c ∈ Ci : ri = 1 else if c = cmin (i) , ∀i ∈ Prest , c ∈ Ci : ri =  0 0 else if c = c∗

if c = c′ else

For c′ to have higher number of votes than c∗ , the total reduction in the difference should be greater than or equal to d + 1c∗ <c′ . Remodeling C1 with the above idea, we can reformulate P2 (c′ ) as: 15

ICLR 2026 Workshop: Principled Design for Trustworthy AI

′

P2 (c ) :

min Ṽ

Np X X

ρci ṽic

s.t.

i=1 c∈Ci

Np X X i=1 c∈Ci

ric ṽic ≥ d + 1c∗ <c′ ,

∀i ∈ [Np ], ∀c ∈ Ci :

X c∈Ci

ṽic = 1, ṽic ∈ {0, 1}.

This problem can be easily converted to a MCKP (multiple choice knapsack problem). To arrive at the excact formulation of MCKP, we need to change the min objective to a max objective and reverse the sign of the constraint inequality . Note that solving minṽ O(Ṽ) is same as solving A − maxṽ (A − O(Ṽ)) , where A is a positive constant. We choose the constant A to be Np ∗ ρmax , where ρmax = maxi∈Np ,c∈Ci ρci . Lets denote P3 (c′ ) as follows . ′

P3 (c ) = max (Np ∗ ρmax − ṽ

Np X X

ρci ṽic )

i=1 c∈Ci

Np −1

s.t. (

X X i=0 c∈Ci

ric ṽic ) ≥ d + 1c∗ <c′ ,

ṽic = 1,

c∈Ci ṽic ∈ {0, 1},

∀i ∈ [Np ], ∀i ∈ [Np ], ∀c ∈ Ci

P PNp −1 P c As c∈Ci ṽic = 1 , we can rewrite Np ∗ ρmax as ( i=0 c∈Ci ρmax ∗ ṽi ) . Using this trick, we ′ reformulate P3 (c ) as : Np X X

′

P3 (c ) = max ṽ

i=1 c∈Ci

(ρmax − ρci ) ṽic

Np −1

s.t. (

X X i=0 c∈Ci

ric ṽic ) ≥ d + 1c∗ <c′ ,

ṽic = 1,

c∈Ci ṽic ∈ {0, 1},

∀i ∈ [Np ], ∀i ∈ [Np ], ∀c ∈ Ci

We use the same trick to reverse the sign of the inequality. We will skip through the construction for the trick as it is exactly the same. Reformulating it finally gives us :

P3 (c′ ) = max ṽ

Np X X i=1 c∈Ci

(ρmax − ρci ) ṽic

Np −1

s.t.

X X i=0 c∈Ci

(rmax − ric ) ṽic ≤ Np ∗ rmax − (d + 1c∗ <c′ ),

ṽic = 1,

c∈Ci ṽic ∈ {0, 1},

∀i ∈ [Np ], ∀i ∈ [Np ], ∀c ∈ Ci

As we have explicitly specified the ric values, we can see that rmax is 2. The value of d is upper bounded by Np as it is the difference in the number of votes. Thus, just as a sanity check, we can confirm that Np ∗ rmax - (d + 1) is positive.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

We can define ρef f = ρmax − ρ and ref f = rmax − r . Note that ref f and ρef f are non-negative. Hence we have a MCKP with positive weights and profits .

P3 (c′ ) = max ṽ

Np X X

(ρef f )ci ṽic

i=1 c∈Ci Np −1

s.t.

X X i=0 c∈Ci

(ref f )ci ṽic ≤ Np ∗ rmax − (d + 1c∗ <c′ ),

ṽic = 1,

c∈Ci ṽic ∈ {0, 1},

∀i ∈ [Np ], ∀i ∈ [Np ], ∀c ∈ Ci

Complexity. The worst case complexity for solving the above problem is O((Np ∗ rmax − (d + PNp PNp 1c∗ <c′ )) ∗ i=1 |Ci |) (Dudzinski & Walukiewicz, 1987). Note that i=1 |Ci | ≤ 3 ∗ Np . Hence, the worst case complexity of solving the MCKP for our use case is O(Np2 ). P2 (c′ ) can be computed as Np ∗ ρmax − P3 (c′ ). We derive the certificate for the ensemble by solving P2 (c′ ) for every class and finding the minimum. Thus, we derive ensemble-level guarantees by aggregating the white-box certificates from the base classifiers in O(K ∗ Np2 ).

ICLR 2026 Workshop: Principled Design for Trustworthy AI

A.4

SVM SIMPLIFICATION FOR SUFFICIENTLY SMALL C

Theorem (Restating Theorem 2). Given a soft-margin SVM with penalty parameter C, kernel matrix entries Qji , and dual solution α to Psvm (y), if   n X j C max |Qi | − 1 ≤ 0, i∈[n]

j=1

then for all label assignments y ∈ {−1, 1}n we have:

α = C · 1n .

That is, all dual variables are equal to C, independent of the choice of labels. Proof. We restate the dual formulation of the soft-margin SVM optimization problem for completeness. Given training labels y ∈ {−1, 1}n and kernel matrix entries Qji , the dual problem is: 

 n n X X 1 Psvm (y) = min − αi + yi yj αi αj Qji  α 2 i=1 i=1 j=1 n X

s.t.

0 ≤ αi ≤ C ∀i ∈ [n].

The gradient of the objective Psvm (y) with respect to αi is: n ∂Psvm (y) X = yi yj αj Qji − 1. ∂αi j=1

Over the feasible domain 0 ≤ αj ≤ C ∀j ∈ [n], we can bound the derivative as: n X ∂Psvm (y) ≤C |Qji | − 1. ∂αi j=1

Pn Now, if C maxi∈[n] j=1 |Qji | − 1 ≤ 0,, then for every i ∈ [n]: n ∂Psvm (y) X = yi yj αj Qji − 1 ≤ 0. ∂αi j=1

This implies that Psvm (y) is monotonically decreasing in each αi over the feasible set. Hence, the minimum is attained at the boundary: αi = C

∀i ∈ [n].

Thus, under the stated condition on C, the solution is α = C · 1n , regardless of the choice of labels y ∈ {−1, 1}n . A.5

S CA L ABEL C ERT FOR THE BINARY SETTING

Recall that for the binary setting, we wish to find the minimum number of label flips required to change the prediction of a soft-margin SVM that uses a sufficient small C (as described P in Sec. A.4). n Under sufficiently small C, the SVM prediction p̂t on a test sample t simplifies to p̂t = i=1 yi Qti . We denote the perturbed training labels as ỹ. Then, the number label flips required to get the Pof n perturbed labels ỹ from the clean labels y can be formulated as 21 i=1 1−yi ỹi . For the prediction pt to change when the model is trained Pn on the perturbed labels, the sign of the clean prediction p̂t and the tamperd prediction pt = i=1 ỹi Qti should be opposite. With this information we can formulate our objective as: 18

ICLR 2026 Workshop: Principled Design for Trustworthy AI

O(y) :

min n

ỹ∈{−1,1}

1X 1 − yi ỹi s.t. 2 i=1

sign(p̂t )

n X

ỹi Qti < 0.

i=1

We show that O(y) can be solved in polynomial P time. The intuition being: The labels corresponding n to the largest positive contributions in sign(p̂t )( i=1 yi Qit ) are the most influential in determining the prediction, so flipping these labels greedily till the prediction changes is the optimal attack from the adversary’s point of view. Pn i Proof. We define the prediction margin to be the sum S = i=1 sign(p̂t )yi Qt . Note that S is always positive as we have included the sign(p̂t ) inside the sum. The prediction for the SVM Pn trained on the perturbed labels ỹ will change when = i=1 sign(p̂t ) · ỹi Qit becomes negative. PS̃ n Let ai = sign(p̂t ) · yi · Qti ∀i ∈ [n]. Thus, S = i=1 ai . Flipping a subset of the clean training [n] labels F ∈ 2 to get the perturbed labels ỹ changes the ith term ai to −ai for i ∈ F , resulting in X S̃ = S − 2 ai . i∈F

The prediction changes when S̃ is negative, i.e, i∈F ai > S/2. Hence, O(y) reduces to finding the smallest subset F such that satisfies the above condition. Greedy algorithm. Construct W = (a1 , . . . , an ) and sort it in descending order: a(1) ≥ a(2) ≥ Pk · · · ≥ a(n) . Let Pk = j=1 a(j) be the cumulative sum of the largest k elements. We find the smallest k ′ such that Pk′ > S/2 and construct the set F by including the labels corresponding to a(1) , . . . , a(k′ ) . Note that ∀k < k ′ : Pk < S/2. We claim that F is the minimal set that we want and k is the minimum number of flips required to change the prediction of the SVM. By construction we ensure that S̃ corresponding to the label flips in F is negative. We prove that that F is the minimal ′ set by contradiction. Assume there exists a subset F ′ ∈ 2[n] with |F | = m P ≤ k − 1 such that ′ flipping P the labels in F results in changing the prediction of the SVM , i.e, i∈F ai > S/2. Note that i∈F ai can be only as large as Pk′ −1 , which is the sum of the k ′ −1 largest elements in W . But P Pk′ −1 is less than S/2 as ∀k < k ′ : Pk < S/2. This contradicts the requirement i∈F ′ ai > S/2. Thus, F is the minimal subset and k is the minimum number of label flips required to change the SVM prediction. Complexity. Sorting W requires O(n log n), and scanning for k is O(n). Hence O(y) is solvable in O(n log n) time, i.e., in polynomial time. Thus, ScaLabelCert provides a polynomial-time computable exact certificate for sufficiently-wide neural networks, when their NTK is used as the SVM kernel. The certificate for kernel regression can be derived similarly by replacing Qit by (Qef f )it , where (Qef f )it can be obtained by a minor modification described in Sec. 3.2.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

A.6

E XACT CERTIFICATE FOR MULTICLASS WITHOUT PARTITIONING PROOF

For the multi-class case, we use the one-vs-all strategy by decomposing the problem with K classes into K separate binary classification tasks. For each class c ∈ [K], a binary classifier is trained to distinguish between samples of class c and samples from all other classes. Assume that pc is the prediction score of a classifier for the learning problem corresponding to class c. Then, the class prediction c∗ for a test sample is constructed by c∗ = arg maxc∈[K] pc . The labels are collected in the vector y ∈ {0, 1}n×K where yic = 1 if the class of the ith sample is c and 0 otherwise. Recall ˜ denotes the maximum number of label flips up to which that for a test sample t, the certificate ρ(t) the prediction for the classifier does not change. We derive the certificate by finding for every class c′ ∈ [K], the minimum number of label flips required to change the prediction of the classifier to a particular class c′ , and then taking the minimum over c′ . The number of label flips to reach the PN PK perturbed label ỹ from the clean labels y can be represented as i=1 (1 − c=1 yic ỹic ). For the ′ ′ class c to be the predicted class, the score pc′ for class c should exceed the score pc for every other class c. Using a soft-margin kernel SVM with a sufficiently small C as our base model, the score PN pc can be written as pc = i=1 yic Qti , . With this information, the minimum number of label flips required to change the prediction of the model to a particular class c′ can be formulated as:  O1 (c′ ) : min ỹ

X i∈[N ]

s.t.



1 −

yic ỹic 

c∈[K]

′ ỹic Qit >

i∈[n]

X i∈[N ]

∀i ∈ [n], c ∈ [K] :

ỹic Qit ∀c ̸= c′ , X c∈[K]

ỹic = 1 , ỹic ∈ {0, 1}.

The certificate ρ̃(t) can be calculated as: ρ̃(t) = minc′ ∈[K]\{c∗ } O1 (c′ ) − 1. O1 (c′ ) is a Integer Linear Program(ILP) with n × K binary variables. Hence, the complexity for solving O1 (c′ ) the problem is O(2n×K ). Consequently, the complexity for deriving ρ̃(t), which is calculated by taking the minimum over O1 (c′ ), is O(K × 2n×K ). This prompts us to solve a simpler alterative O2 (c′ ) instead, that relaxes the constraint in O1 (c′ ) requiring c′ to be the predicted class:  O2 (c′ ) : min ỹ

X i∈[N ]

s.t.



1 −

X c∈[K]

′ ỹic Qit >

i∈[n]

yic ỹic 

∗

ỹic Qit ,

(7)

i∈[N ]

∀i ∈ [n], c ∈ [K] :

X c∈[K]

ỹic = 1 , ỹic ∈ {0, 1}.

O2 (c′ ) calculates the minimum number of label flips needed to make the prediction score pc′ for class c′ exceed the prediction score pc∗ for the original predicted class c∗ . Notably, this relaxation is similar to the relaxation of P1 (c′ ) to P2 (c′ ) in the context of computing the certificate for the ensemble. Despite the relaxation, we show that the minimum over O1 (c′ ) is preserved, i.e.: Theorem 3. min

c′ ∈[K]\c∗

O1 (c′ ) = ′ min ∗ O2 (c′ ) c ∈[K]\c

The intuition being — while trying to make c′ surpass c∗ , if another class c′′ becomes the predicted class, then changing the classifier prediction to c′′ should be easier compared to c′ . As the design of the relaxation and the intuition are similar to the ensemble case, the proof strategy for this result is exactly the same as Theorem 1. The only difference would be that the notation majVote(Ṽ), that finds the majority class for a vote configuration Ṽ will be replaced by the majScore notation that predicts the class when the model is trained on the perturbed labels

ICLR 2026 Workshop: Principled Design for Trustworthy AI

P ỹ, i.e, majScore(ỹ) = arg maxc∈[K] i∈[n] ỹic Qit . Hence, we direct the reader to the proof for Theorem 1 provided in Sec. A.2. With the above result, we can derive the certificate ρ̃(t) as: ρ̃(t) = minc′ ∈[K]\{c∗ } O2 (c′ ) − 1

Solving O2 (c′ ). We focus our attention on solving O2 (c′ ). Recall that O2 (c′ ) denotes the minimum number of label flips needed to make the prediction score pc′ for class c′ exceed the prediction score pc∗ for the original predicted class c∗ . We denote the training samples that were labeled c∗ originally as Pmaj and samples that were labeled c′ originally as Ptarget . Prest denote the set of remaining samples ∗

Pmaj = {i ∈ [N ] | yic = 1},

′

Ptarget = {i ∈ [Np ] | yic = 1},

Prest = [n] \ Pmaj ∪ Ptarget

P ∗ ′ Let d be the original difference between score for c′ and c∗ : d = i (yic − yic )Qti . We define ric to be the reduction caused by flipping label of the i th sample to class c in the difference between score for c′ and c∗ . For the score pc′ exceed the score pc∗ , the total reduction caused by the label flipping attack should exceed d. Lets see what these values will be for different i and c. For samples in Pmaj . For samples that were originally labeled c∗ , if the label is flipped to c′ , reduction will be 2 ∗ Qti . If the label is flipped from c∗ to any other class, the reduction is only by Qti as it affects the score only for c∗ . If Qti is positive, flipping the label to c′ will cause the maximum reduction possible by flipping the ith label. Hence, an optimal attack will flip the ith label to c′ (if it chooses to flip the label). If Qti is negative, an optimal attack will not flip the label for the ith sample as it will further increase the gap between c′ and c∗ .  ′ 2 ∗ Qti if c = c c ∀i ∈ Pmaj , c ∈ [K], ri = 0 else if c = c∗  Qti else For samples in Ptarget . Following a similar line of argument as above, we can safely say that ∀i ∈ Ptarget , if Qti < 0, an optimal attack will flip the label for sample i to c∗ (if it chooses to flip the label). If Qti is positive, an optimal attack will not flip the label for the ith sample as it will further increase the gap between c′ and c∗ .

∀i ∈ Ptarget , c ∈ [K],

 −2 ∗ Qti ric = 0  −Qti

if c = c∗ else if c = c′ else

For samples in Prest . For samples with the true label other than c′ or c∗ , if Qti > 0, an optimal attack will flip the ith label to c′ . If Qti is negative, the optimal attack will flip the ith label to c∗ , if it chooses to flip the label.

∀i ∈ Prest , c ∈ Ci ,

 Qti ric = −Qti  0

if c = c′ if c = c∗ else

With this, we can define r(i) as the reduction in the difference between scores for c′ and c∗ in the optimal attack, if the attacker chooses to flip the ith label: ∀i ∈ [N ], r(i) = maxc∈[K] ric . Note that if ri is 0 , the ith label will not be flipped. Hence we define the set of candidates for flipping the labels as Ef : Ef = {i ∈ [N ] | r(i) > 0} We employ a greedy strategy similar to the one used in the computation of the certificate for the binary case (Sec. A.5). We first sort the candidate flipping labels Ef based on their r(i) values in Pk the descending order,i.e., r(1) ≥ r(2) ≥ . . . . Let Pk = j=1 r(j) be the cumulative sum of the largest k elements. We find the smallest k ′ such that Pk′ > d and construct Gk′ by including the indices corresponding to the k ′ largest r(i) values. We claim that k ′ is the minimum number of label flips required to make the score for c′ exceed c∗ and Gk′ is the minimal set of the labels that need to be flipped to make it happen. The greedy algorithm is illustrated in Algorithm 1. 21

ICLR 2026 Workshop: Principled Design for Trustworthy AI

We prove optimality by contradiction. Recall that Gk = {(1), . . . , (k)} is the greedy choice of k Pk largest r(i) and Pk = j=1 r(j) . Suppose there exists a set F ⊆ Ef with |F | = m ≤ k ′ − 1 P such that flipping achieves the objective, i.e, i∈F r(i) > d. But Gm consists of the m Plabels in F P largest r(i), so i∈F r(i) ≤ i∈Gm r(i) = Pm ≤ Pk′ −1 ≤ d, a contradiction. Algorithm 1 Greedy Certificate Computation Input: Score gap d, reductions r(1), . . . , r(n) Output: Minimum number of flips k 1: total red ← 0 2: sorted ← sort(r, descending) 3: i ← 0 4: while total red < d do 5: total red ← total red + sorted[i] 6: i←i+1 7: end while 8: return i Complexity. Sorting based on the reduction values takes O(n log n), and scanning for the minimal k ′ takes O(n). Solving O2 (c′ ) for all c′ ∈ [K] \ c∗ can be done in O(Kn log n), resulting in a polynomial-time exact certificate for test sample t: ρ̃(t) = minc′ ∈[K]\c∗ O2 (c′ ) − 1.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

A.7

E XTRACTING WHITE - BOX KNOWLEDGE FOR THE MULTI - CLASS SETTING

Recollect that EnsembleCert utilizes the white-box knowledge ρci for all base classifiers i ∈ [Np ] and all classes c ∈ [K] where ρci denotes the minimum number of flips required to change the prediction of the ith base classifier to c. For each base classifier, using a soft-margin kernel SVM with a sufficiently small C as our base model, we formulate the problem of finding the minimum number flips required to change the prediction of the classifier to c′ is formulated as:  O1 (c′ ) : min ỹ

s.t.

X i∈[N ]

X i∈[n]

1 − ′

 X

yic ỹic 

c∈[K]

ỹic Qit >

X i∈[N ]

∀i ∈ [n], c ∈ [K] :

ỹic Qit ∀c ̸= c′ , X c∈[K]

(8)

ỹic = 1 , ỹic ∈ {0, 1}.

The above problem is an ILP with n × K binary variables, resulting in a computational complexity of O(2nK ). For each base classifier, we need to solve this problem for all classes. Consider an ensemble with Np base classifiers. We would need to solve Np × K ILPs with the computational complexity of O1 (c′ ), making the problem intractable. Hence, instead of solving the problem O1 (c′ ) exactly, we bound the problem efficiently, and show that our bounds are sufficiently tight on empirical evaluation. A.7.1

L OWER B OUND

For the purpose of computing the exact certificate for the multiclass case in the no partition case, we formulated an alternate problem O2 (c′ ) (Eq. (7)), a relaxed version of O1 (c′ ) which only requires the score pc′ for class c′ to exceed the score pc∗ for class c∗ . We showed in Sec. A.6 that O2 (c′ ) can be solved in polynomial time. As the constraint set of O2 (c′ ) is a subset of O1 (c′ ), the solution for O2 (c′ ) will always be less than or equal to O1 (c′ ). Hence, O2 (c′ ) represents a valid lower bound on O1 (c′ ), that is polynomial-time calculable. Notably, O2 (c′ ) is also a certificate by definition, as it is a lower bound on the certified radius. A.7.2

U PPER BOUND

To compute a valid upper bound on O1 (c′ ), finding an instance of perturbed labels ỹ that satisfies the constraints of O1 (c′ ), i.e, majScore(ỹ) = c′ , is sufficient. The number of label flips needed to reach any such ỹ from the clean labels y represents a valid upper bound on O1 (c′ ). To compute this upper bound efficiently, we adopt a greedy strategy that iteratively flips training labels to reach a feasible solution of Eq. (1). At theP beginning of each iteration, we compute the current majority class n c∗ = arg maxc Sc , where Sc = i=1 ỹic Qit is the score of class c. Note that c∗ may change after each label flip, and our method accounts for this by re-evaluating c∗ and all per-sample damages di after every label flip. Let S (2) = maxc∈[K]\c∗ Sc denote the score of the runner-up class. For each sample i, we define the per-sample damage di as the maximum possible reduction in the gap between c′ and the majority class achievable by flipping i:  ∗ i i (2)  ∗ − S min 2Q , Q + S , if ỹic = 1 and Qit > 0,  c t t       min 2|Qi |, |Qi | + S ∗ − S (2) , else if ỹ c′ = 1 and Qi < 0, c t t t i di =  ∗ ′    Qit , if ỹic = 0, ỹic = 0, and Qit > 0,     0, otherwise. Intuitively, di captures the maximal contribution that flipping sample i can make toward satisfying the class-change constraint of Eq. (1).

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Cases explained ∗

1. Case 1 (ỹic = 1, Qit > 0): Flipping a positively contributing c∗ -labeled sample to c′ both reduces Sc∗ and increases Sc′ , leading to a decrease of 2Qit . The possibility that the runnerup class becomes the majority is considered by the term Qit + Sc∗ − S (2) , which accounts for the score gap to the second-highest class. ′

2. Case 2 (ỹic = 1, Qit < 0): Flipping a negatively contributing c′ -labeled sample to c′ helps both by increasing Sc′ and decreasing Sc∗ , giving a decrease of 2|Qit |. The possibility of runner-up class becoming the majority class is handled as above. 3. Case 3 (neutral sample, Qit > 0): Flipping such a sample to c′ only increases Sc′ , so the reduction in the gap is exactly Qit . In each iteration, we select i⋆ = arg maxi di , flip the corresponding label to c′ or c∗ , re-evaluate the majority class, and repeat this process until c′ becomes the majority class. Hence, by design, the greedy algorithm results in a feasible ỹ satisfying Eq. (1), and the number of flips performed constitutes a valid upper bound on O1 (c′ ). Our greedy approach is illustrated in Algorithm 2. Complexity. We choose the label to flip by calculating the possible reduction each label flip can cause in the gap between c∗ and c′ , and choosing the one that causes the maximum reduction. This involves scanning the dataset at every iteration. Hence the worst case complexity in computing the upper bound for O1 (c′ ) is O(n2 ). Algorithm 2 Greedy Upper Bound Computation for O1 (c′ ) 1: Input: Clean labels y, kernel entries corresponding to the ith training sample and test sample

t: Qit ∀i ∈ [N ], target class c′

2: Output: Upper bound on O1 (c′ ) (number of label flips) 3: Initialize ỹ ← y PN 4: Compute Sc = i=1 ỹic Qit for all c ∈ [K] 5: c∗ ← arg maxc Sc 6: while c∗ ̸= c′ do 7: S (2) ← maxc̸=c∗ Sc 8: for i = 1∗ to N do 9: if ỹic = 1 and Qit > 0 then 10: di ← min 2Qit , Qit + Sc∗ − S (2) ′

else if ỹic = 1 and Qit < 0 then di ← min 2|Qit |, |Qit | + Sc∗ − S (2) ′ ∗ 13: else if ỹic = 0 and ỹic = 0 and Qit > 0 then 14: di ← Qit 15: else 16: di ← 0 17: end if 18: end for 19: i⋆ ← arg maxi di ′ 20: if ỹic∗ = 1 then ∗ 21: ỹic∗ ← 1 22: else ′ 23: ỹic∗ ← 1 24: end if PN 25: Update Sc = i=1 ỹic Qit for all c ∈ [K] 26: c∗ ← arg maxc Sc 27: end while 28: return Number of flips applied to reach ỹ 11: 12:

ICLR 2026 Workshop: Principled Design for Trustworthy AI

D ETAILS OF R ANDOMIZED S MOOTHING INTEGRATION

B.1

S MOOTHED L INEAR C LASSIFIER AS THE BASE M ODEL

In addition to ScaLabelcert for sufficiently wide networks, we use the method from Rosenfeld et al. (2020) for certification of base classifiers. Their approach uses a smoothed linear classifier as the base classifier. The smoothing process involves independently flipping each label with probability q and assigning a flipped label uniformly at random among the remaining K − 1 classes. To certify robustness, the method bounds the probability that this randomized classifier switches its prediction from one class to another. B.2

P REDICTION BY THE S MOOTHED C LASSIFIER

The method by Rosenfeld et al. (2020) computes, for each pair of classes (c, c′ ), a Chernoff bound pc,c′ (q) that gives an upper-bound on the probability that the randomized classifier switches its predicted class from c to c′ under the randomized label flips. For each class c, the method evaluates max pc,c′ (q)

c′ ∈[K]\c

and defines the predicted class as c∗ = arg min ′ max pc,c′ (q), c∈[K] c ∈[K]\c

B.3

C OMPUTING THE C ERTIFICATE

The certified radius r is obtained by plugging the worst-case probability bound maxc′ ∈[K]\c∗ pc∗ ,c′ (q) into the robustness guarantee from a result in Rosenfeld et al. (2020), giving log 4p(1 − p) , r≤ q 2(1 − 2q) log 1−q where p = maxc′ ∈[K]\c∗ pc∗ ,c′ (q). This bound guarantees that if at most r labels were flipped by the adversary, the smoothed classifier would still predict c∗ . B.4

A DAPTATION FOR OUR USE CASE

We follow the same prediction rule to obtain c∗ . However, instead of computing the radius that certifies that the prediction will not change to any other class, we focus on certifying robustness against a specific target class c′ . This is because our objective is to compute the minimum number of label flips required to change the prediction of a base classifier to every class. This whitebox information is then used by EnsembleCert to construct a white-box infused certificate for the ensemble. Concretely, we use the pairwise Chernoff bound pc∗ ,c′ (q) and compute log 4pc∗ ,c′ (1 − pc∗ ,c′ ) , rc′ ≤ q 2(1 − 2q) log 1−q which gives the number of label flips required to change the prediction specifically from c∗ to c′ .

ICLR 2026 Workshop: Principled Design for Trustworthy AI

E XTENDED D ISCUSSION AND R ELATED W ORK

Scarcity of relevant white-box certificates. Our evaluations of EnsembleCert demonstrate significant improvement in certified robustness when the white-box knowledge of the base classifiers is utilised. Notably, EnsembleCert demands white-box certificates deriving minimum number of samples that need to be tampered with to change the prediction to a particular class. The dearth in works exploring certification of this nature pose an imminent challenge in the way of realising the true potential of EnsembleCert. Versatility of ScaLabelCert. Through the formulation O1 (c′ ) (Eq. (1)), ScaLabelCert derives efficient certificates for sufficiently wide networks that compute the minimum number of label flips needed to change the prediction of the classifier to a particular class c′ . Although these certificates are not exact, we compute sufficiently tight bounds (see Sec. 4). Note that the certificate definition is different from the certified radius, which represents the minimum label flips needed to change the classifier’s prediction to any class. We remind the reader that our certificate for computing the certified radius for a stand-alone model is exact and polynomial-time calculable (Sec. A.6). Moreover, ScaLabelCert provides a general framework for certifying kernel SVMs and kernel regression models against label-flipping. Using the NTK is one instance of this framework, enabling efficient certification for sufficiently wide NNs. Finally, a kernel SVM with a sufficiently small C and kernel regression-based classifiers can be interpreted as weighted nearest-neighbor models, where Qit and (Qeff )it denote the weight of the ith neighbor of the test sample t for kernel SVM and kernel regression, respectively. From this perspective, ScaLabelCert can also certify weighted nearest-neighbor models against label-flipping attacks in polynomial time, demonstrating its broad applicability. Potential of EnsembleCert for Certifying Against Clean-Label Attacks. In this work, we utilize EnsembleCert to certify against label-flipping attacks. However, EnsembleCert can also leverage white-box knowledge of base-classifiers to provide robustness guarantees against clean-label attacks. Specifically, consider an adversary capable of corrupting only the features of a training sample within an ℓp ball. Under this threat model, the white-box information ρci can denote the number of samples that must be corrupted to change the prediction of the ith base classifier to class c. EnsembleCert can aggregate this white-box information from the base classifiers to compute the number of samples in the entire training dataset that need to be corrupted to alter the prediction of the ensemble. In this way, EnsembleCert can be adapted to derive white-box certificates for partition aggregation ensembles under multiple threat models. However, deriving efficient and scalable white-box clean-label certificates for certifying the base classifiers is still an open challenge. Related Work. Current ensemble-based poisoning certificates typically use the following ensembling techniques: (i) randomized smoothing (Rosenfeld et al., 2020; Wang et al., 2020; Zhang et al., 2022; Weber et al., 2023), where the randomization is over the training dataset, (ii) partition-based aggregation (Levine & Feizi, 2021; Wang et al., 2022; Rezaei et al., 2023), and (iii) bootstrap aggregation (Jia et al., 2021), where the base classifiers are trained on independently sampled subsets of the training data. None of these works use white-box knowledge of the base classifiers, making them inherently black-box methods. Apart from the white-box certificates discussed in the introduction (Sabanayagam et al., 2025; Sosnin et al., 2025), Gosch et al. (2025) is the only other white-box certification method that certifies NNs against clean-label attacks, notably using the NTK approach similar to ours and to Sabanayagam et al. (2025). The remaining white-box certificates in the literature do not extend to NNs and apply to only decision trees (Meyer et al., 2021; Drews et al., 2020), nearest neighbor models (Jia et al., 2022) or naive Bayes classifiers (Bian et al., 2024).

A DDITIONAL PLOTS

D.1

F URTHER IMPLEMENTATION DETAILS AND C ERTIFICATION RUNTIME

Hardware. All the experiments were done on an internal cluster. We used GPUs solely for the NTK kernel computation, which was done using the Google neural-tangents library (Novak et al., 2020). As the kernel computation is not the main focus of our work, we refer interested readers to (Novak et al., 2020) for details on latency and memory requirements. All the following steps for certificate derivation were executed on CPUs.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Certificate derivation. We process the test data in parallel batches of 100 samples. Recall that for each test sample, EnsembleCert first computes ρci for every base classifier i ∈ [Np ] and class c ∈ [K] using ScaLabelCert, which provides both upper and lower bounds. This requires computing Np × K entries before passing this information to EnsembleCert for aggregation. In the current implementation, white-box information is computed sequentially by iterating over the partitions and classes. However, these computations are inherently parallelizable across both partitions and classes because the certificates are independent. In particular, the lower bound calculation for each ρci (Sec. A.7.1) can be fully vectorized, whereas the upper bound calculation (Sec. A.7.2) must be performed independently for each sample. The aggregation step, which combines white-box information to derive the ensemble-level certificate, is also executed independently per sample. This step involves solving a Multiple-Choice Knapsack Problem (MCKP) for each test sample, which to the best of our knowledge, cannot be vectorized efficiently. Average Certification Time per Sample. As discussed, both EnsembleCert and ScaLabelCert yield polynomial-time computable certificates. Since lower bound computations are vectorized within each batch, per-sample latency cannot be measured directly. Instead, we report average amortized time, which refers to the total time taken to certify a batch divided by the number of samples in that batch, providing a fair per-sample estimate. We present this average amortized certification time per sample for EnsembleCert in Fig. 4. Latencies presented in the figure above also include the training and prediction latencies, which are negligible owing to the simplification under small C for kernel SVM and the closed form solution for kernel Regression. The total certification time per sample is the sum of the latencies for the upper and lower bound computations. Importantly, the upper bound latency is not amortized since the computation is performed sequentially per sample. For small Np , the number of samples per partition is high, which leads to a noticeable gap between the latencies of upper and lower bound computations. This is because (i) the lower bound computation is linear in the number of samples whereas the upper bound computation is quadratic and (ii) lower bounds computation is vectorized whereas upper bound computation is done independently. As Np increases, white-box aggregation latency for both computations becomes dominant due to the quadratic complexity of MCKP in Np , thereby narrowing the gap between the upper and lower bound curves. For CIFAR-10, the average (amortized) certification time per sample goes from as low as 5 seconds for Np = 50 to as high as under 2 minutes for Np = 500. For MNIST, the average amortized latency varies from 8 sec to a max of around 4 min.

100

Avg. certification time (s)

Choosing Np . Sec. 4 discussed the invariance of robustness to partitioning observed for EnsembleCert with kernel SVMs, and the robustness decay observed with sufficiently regularized kernel regression. This raises questions about the practical utility of using heavy partitioning. Moreover, the experiments in Fig. 4 show that larger ensembles are computationally more expensive to certify using EnsembleCert. When robust base classifiers are employed, it becomes evident that using a low to medium number of partitions offers the best trade-off between achieving high certified robustness and minimizing computational costs. Overall EnsembleCert LB EnsembleCert UB

80 60 40 20 0 0

100

200

300

400

500

Overall EnsembleCert LB EnsembleCert UB

200 150 100 50 0 0

Number of partitions

100

200

300

400

500

Number of partitions

(a) CIFAR-10 Kernel SVM

(b) MNIST Kernel SVM

600

Avg. certification time (s)

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Overall EnsembleCert LB EnsembleCert UB

100 80 60 40 20 0 0

100

200

300

400

Overall EnsembleCert LB EnsembleCert UB

200 150 100 50 0

500

100

Number of partitions

200

300

400

500

600

Number of partitions

(d) MNIST Kernel Reg λ=0.1

Figure 4: 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. D.2

ROBUSTNESS - ACCURACY TRADEOFF FOR SMALL C

0.80

0.75

0.90

Sufficiently small C regime

Test Accuracy

Sufficiently small C regime

0.85

Test Accuracy

Recall that the key to obtaining polynomial-time computable certificates by ScaLabelCert for infintely-wide networks trained on the hinge loss is choosing a sufficiently small value of C. Hence, this introduces a robustness-accuracy tradeoff as we are constrained to choose C that is sufficiently small to achieve the polynomial-time certificate. To study this tradeoff, we perform 5-fold crossvalidation for different values of C. For every number of partitions, 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. The results for CIFAR-10 are shown in Fig. 6. In addition to studying the tradeoff on an ensemble level, we conduct experiments to study the performance trade-off induced by ”sufficiently small C” for stand-alone classifiers as a function of the training set size Ns . For each value of Ns , we sub-sample the training set for 5 different random seeds while keeping class balance. The models trained on the sub-sampled training data are evaluated on the entire test dataset. The results can be seen in Fig. 5. It is evident from these experiments that performance remains competitive in the small C regime. We do not evaluate on MNIST, as for our chosen kernel and RotNet preprocessing, the threshold for sufficiently small C is significantly larger (order of 102 ).

0.85

0.80

10−4

10−3

10−2

10−1

100

101

102

10−4

10−3

10−2

(a) Ns = 100

0.86 0.84 0.82 0.80

0.75

0.70

Sufficiently small C regime

0.88

10−1

100

(b) Ns = 200

101

102

10−4

10−3

10−2

10−1

100

101

102

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Sufficiently small C regime

0.90

0.88 0.86 0.84 0.82

Sufficiently small C regime

0.90

Test Accuracy

Sufficiently small C regime

Test Accuracy

0.90

0.88 0.86 0.84 0.82

10−4

10−3

10−2

10−1

100

101

10−4

102

10−3

10−2

10−1

100

101

10−4

102

10−3

10−2

(d) Ns = 1000

10−1

100

101

102

(e) Ns = 2000

(f) Ns = 5000

Validation Accuracy

Figure 5: 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.

Np 40 80 160 200 400 800

0.90

0.88

0.86 10−4

10−3

10−2

10−1

100

C Figure 6: Robustness-accuracy trade-off introduced by sufficiently small C. While Fig. 5 studies empirical performance of stand-alone models, the impact of small C ion the empirical performance of the ensemble is studies here.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

D.3

C OMPARISON OF S CA L ABEL C ERT WITH THE G RADIENT- BASED B OUNDING C ERTIFICATE (S OSNIN ET AL ., 2025)

We compare the performance of ScaLabelCert with the gradient-based parameter bounding method proposed by Sosnin et al. (2025) on CIFAR-10. The gradient-based approach uses convex relaxations to over-approximate all possible parameter updates under a given poisoning threat model. The parameter bounds are then propagated to bound the logits for individual classes. The robustness of the prediction for a particular sample can then be certified by checking if the lower bound on the output logit for the predicted class is greater than the upper bounds of all other classes given the perturbation budget. If this condition is satisfied, the prediction is certifiably robust under the given budget. To evaluate this method, we add a linear layer on top of the CIFAR-10 features extracted via SimCLR. We train the network for 2 epochs and keep other parameters consistent with the codebase for Sosnin et al. (2025). For ScaLabelCert, the same SimCLR features are input to an infinitely wide fully-connected network with a single hidden layer and no non-linear activation, as described in Sec. 4. Although the models are not identical, the architectures are structurally aligned as both models rely on fully connected layers without activations, making the comparison meaningful. As shown in Sec. D.3, ScaLabelCert consistently outperforms the gradient-based method. This improvement highlights the importance of exact certification: while the gradient-based approach is inherently limited by the looseness of its over-approximations, ScaLabelCert provides tight guarantees, resulting in stronger certified robustness.

0.0

Percent of training set

0.2

0.4

0.6

1.0

1.2

White-box method ScaLabelCert AGT, κ = 0.01 AGT, κ = 0.1 AGT, κ = ∞

0.8

Certified Accuracy

0.8

0.6 0.4 0.2 0.0 0

100

200

300

400

500

600

Budget (Number of Flips) Figure 7: 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 κ.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

D.4

E NSEMBLE C ERT WITH FINITE - WIDTH NETWORKS AS BASE CLASSIFIERS

The certificates derived by ScaLabelCert are asymptotically exact and deterministic for neural networks as the width of the network goes to infinity. Hence, ScaLabelCert is best suited for certifying infinite-width neural networks. To demonstrate that EnsembleCert can provide deterministic certificates even when finite-width networks are used as base classifiers, we instantiate EnsembleCert with a fully connected linear classifier as the base model and utilize the gradient-based parameter bounding method by Sosnin et al. (2025), introduced in the previous section, to certify the base classifiers. The gradient-based method certifies, for a given sample, whether the model’s prediction remains unchanged when at most r training labels are flipped. However, this guarantee does not directly match the white-box quantity required by EnsembleCert, which is the minimum number of label flips needed to change the prediction to a particular class. In what follows, we explain how this gradient-based certificate can be incorporated into EnsembleCert.. Certificate alignment. For any certificate that verifies whether a model’s prediction remains robust under a fixed perturbation budget of r label flips, one can obtain a certificate for the minimum number of label flips needed to change the prediction to some class by applying the fixed-budget certificate incrementally—starting at r = 0 and increasing r until the certificate first indicates non-robustness. Note that EnsembleCert requires white-box information quantifying the minimum number of label flips needed to change the prediction of a base classifier to a specific target class. The certificate that computes the minimum flips needed to change the prediction to some class then serves as a valid lower bound on ρci , the minimum number of label flips required to force the i-th base classifier to predict a particular class c. This relationship enables us to incorporate the gradient-based certificate into EnsembleCert. Experiments. We evaluate EnsembleCert on ensembles with finite-width linear networks as base classifiers by applying the gradient-based certificate to each base classifier. As described in the previous section, this certificate can be incorporated into EnsembleCert. Briefly, for each sample we compute the minimum number of label flips required to change the prediction of base classifier i to some class by applying the gradient-based certificate over increasing budgets until robustness fails. We then use this value as ρci for every class c. Because this incremental application of the gradientbased method is computationally demanding, our experiments on finite-width models are limited to CIFAR-10 and a small number of partitions. Nevertheless, as shown in Fig. 8, incorporating whitebox information through EnsembleCert substantially improves certified accuracy. This demonstrates that EnsembleCert extends naturally to ensembles built from finite-width neural networks. Moreover, the integration procedure highlights a broader utility: any certificate that determines whether a model remains robust up to a given number of label flips can be adapted to certify the base classifiers within EnsembleCert.

Label flips (Percent of training data)

EC with AGT type 1 SS-DPA

0.8 0.6 0.4 0.2 0.0 0

1.0

Label flips (Percent of training data)

0.0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18

EC with AGT type 1 SS-DPA

0.8 0.6 0.4 0.2 0.0 0

Certified Accuracy

0.0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18

Certified Accuracy

Label flips (Percent of training data)

1.0

0.0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18

EC with AGT type 1 SS-DPA

0.8 0.6 0.4 0.2 0.0 0

Budget (Number of Flips)

(a) Np = 10

(b) Np = 25

Figure 8: 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.

ICLR 2026 Workshop: Principled Design for Trustworthy AI

ROBUSTNESS TRENDS ACROSS λ FOR E NSEMBLE C ERT WITH K ERNEL R EGRESSION

D.5

We study the effect of the L2 regularization parameter λ on certified robustness. For low λ, the MCR increases with the number of partitions across all datasets. In contrast, for high λ, the certified robustness appears to be negatively affected by increasing the number of partitions. The contrasting behavior potentially arises due to the varying degree of robustness that the choice of λ imparts the base classifier. Low λ makes kernel regression unstable, causing base classifiers to be easily influenced by a few label flips, even with large partitions. In this regime, the ensemble is closer to the black-box assumption - that a single label flip can change a base classifier’s prediction - even when the number of partitions is small, resulting in white-box certificates that aren’t much tighter than the black-box ones. In contrast, using a high degree of regularization exhibits a substantial improvement in the certified accuracy on white-box infusion. Fig. 10 shows how the robustness trend changes with varying λ for CIFAR-10. While at λ = 0.01, the median certified robustness scales almost linearly with the number of partitions, the trend completely changes by the time we reach λ = 100. Empirical analysis suggests that the nature of the trend changes somewhere between λ = 1 and λ = 5. Interestingly, the change in trend also points towards the possibility that for some value between λ = 1 and λ = 5, the median certified robustness could exhibit invariance to the number of partitions, a phenomenon we observed with kernel SVMs. Similar behavior is seen for experiments on MNIST as well (Fig. 9). As we mentioned in Sec. 4, the threshold λ, where the behavior changes is data dependent.

100

400

300

200 100

SS-DPA EnsembleCert LB

0 200

400

600

200

(a) λ = 0.0001

400

600

200 100

Number of Partitions

SS-DPA EnsembleCert LB

300

100

SS-DPA EnsembleCert LB

0 0

SS-DPA EnsembleCert LB

MCR

200

400

MCR

300

MCR

400

0 0

200

400

600

200

400

Number of Partitions

(b) λ = 0.01

(d) λ = 0.1

600

Figure 9: Robustness trends across different λ values on MNIST using kernel regression. 250

250

200

100 SS-DPA EnsembleCert LB EnsemblCert UB

200

150 100

SS-DPA EnsembleCert LB EnsemblCert UB

MCR

150

MCR

200

100

200

300

400

500

100

SS-DPA EnsembleCert LB EnsemblCert UB

50 0

150

Number of Partitions

100

200

300

400

500

Number of Partitions

(a) λ = 0.01

100

200

(b) λ = 0.1

150 100

SS-DPA EnsembleCert LB EnsemblCert UB

50 0

0 0

100

200

300

400

Number of Partitions

(d) λ = 5

500

MCR

SS-DPA EnsembleCert LB EnsemblCert UB

MCR

100

500

SS-DPA EnsembleCert LB EnsemblCert UB

200 200

150

400

250 200

300

Number of Partitions

150 100 50 0

100

200

300

400

Number of Partitions

(e) λ = 10

500

100

200

300

400

Number of Partitions

(f) λ = 100

Figure 10: Robustness trends across different λ values on CIFAR-10 using kernel regression.

500

ICLR 2026 Workshop: Principled Design for Trustworthy AI

D.6

MNIST 1- VS -7

0.6 0.4 0.2 0.0 100

200

300

400

EnsembleCert SS-DPA

0.8 0.6 0.4 0.2 0.0

500

Budget (Number of Flips)

0.8 0.6 0.4 0.2 0.0 0

100

200

300

400

0.8

0.2 0.0 300

0.2 0.0 0

0.2 0.0

400

100

200

300

400

500

0.4 0.2 0.0 100

200

300

400

500

EnsembleCert SS-DPA

0.6 0.4 0.2 0.0 0

100

200

300

400

500

Budget (Number of Flips)

(f) Partitions: 300

0.6

300

0.8

500

EnsembleCert SS-DPA

0.8

200

1.0

Budget (Number of Flips) 1.0

100

Budget (Number of Flips)

0.4

Certified Accuracy

0.4

200

0.4

(e) Partitions: 200

0.6

100

0.6

500

0.6

500

EnsembleCert SS-DPA

400

EnsembleCert SS-DPA

(d) Partitions: 100 0.8

300

1.0

Budget (Number of Flips) 1.0

200

EnsembleCert SS-DPA

0.8

(b) Partitions: 25

EnsembleCert SS-DPA

Certified Accuracy

(a) Partitions: 10 1.0

100

1.0

Budget (Number of Flips)

Certified Accuracy

1.0

Certified Accuracy

EnsembleCert SS-DPA

0.8

500

Certified Accuracy

1.0

Certified Accuracy

Kernel Regression. We present results for evaluation using kernel regression with NTK and the ℓ2 regularization parameter λ = 0.1 in Fig. 11.

1.0

EnsembleCert SS-DPA

0.8 0.6 0.4 0.2 0.0 0

100

200

300

400

500

Budget (Number of Flips)

(g) Partitions: 400

(h) Partitions: 500

(i) Partitions: 600

Figure 11: MNIST binary kernel regression with λ = 0.1 results for different number of partitions. Kernel SVM We present results for evaluation using kernel SVM with NTK and a sufficiently small C in Fig. 12.

0.8 EnsembleCert SS-DPA

0.2 0.0 0

100

200

300

400

0.6

EnsembleCert SS-DPA

0.4 0.2 0.0

500

Budget (Number of Flips)

100

0.8 EnsembleCert SS-DPA

0.4 0.2 0.0 0

100

200

300

400

0.6

0.2 0.0 0

Certified Accuracy

0.2 0.0 300

0.0 0

100

400

200

300

400

500

EnsembleCert SS-DPA

0.2 0.0 0

100

200

300

400

500

0.8 0.6

EnsembleCert SS-DPA

0.4 0.2 0.0 0

100

200

300

400

500

Budget (Number of Flips)

(f) Partitions: 300

0.8

0.4

300

1.0

500

1.0

0.6

200

Budget (Number of Flips)

(e) Partitions: 200

EnsembleCert SS-DPA

200

0.2

Budget (Number of Flips)

0.8

100

EnsembleCert SS-DPA

0.4

EnsembleCert SS-DPA

0.4

(d) Partitions: 100

0.6

500

0.8

500

1.0

0.4

400

1.0

Budget (Number of Flips)

0.6

300

0.8

(b) Partitions: 25 Certified Accuracy

Certified Accuracy

(a) Partitions: 10 1.0

0.6

200

1.0

Budget (Number of Flips)

Certified Accuracy

0.4

0.8

Certified Accuracy

0.6

1.0

Certified Accuracy

1.0

Certified Accuracy

ICLR 2026 Workshop: Principled Design for Trustworthy AI

400

500

1.0 0.8 0.6 0.4 EnsembleCert SS-DPA

0.2 0.0 0

100

200

300

400

500

Budget (Number of Flips)

(g) Partitions: 400

(h) Partitions: 500

(i) Partitions: 600

Figure 12: MNIST binary kernel SVM results for different number of partitions. MCR results Consistent with the results on MNIST and CIFAR10, Fig. 13 demonstrates the invariance of median certified robustness to the number of partitions, for both kernel Reg and kernel SVM 500

DPA (Black Box)

300

Exact (White Box)

MCR

400 200 100

SS-DPA EnsembleCert 100

200

300

400

500

200 100 0

0 0

300

600

100

200

300

400

500

Number of Partitions

(a) MNIST 1-vs-7: SVM

(b) MNIST 1-vs-7: Reg

Figure 13: Invariance to number of partitions

600

ICLR 2026 Workshop: Principled Design for Trustworthy AI

D.7

CIFAR-10

Kernel Regression

0.4 0.2 0.0 100

200

300

400

0.4 0.2 0.0

500

100

200

300

400

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

Budget (Number of Flips)

(a) Partitions = 10

(b) Partitions = 50

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8 0.6 0.4 0.2 0.0 0

0.6

100

200

300

400

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

Certified Accuracy

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8

Certified Accuracy

0.6

Certified Accuracy

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8

Certified Accuracy

For low values of λ, the base classifier by itself is not robust and is closer to the worst-case black box assumption described in Sec. A.1. Consequently, we do not see a significant improvement on utilizing white-box knowledge of the base classifiers. This is illustrated in Fig. 14 , where we evaluate EnsembleCert using kernel regression as base classifier and a low regularization parameter λ = 0.01. In contrast, using a high degree of regularization changes the trend as mentioned in the experiments section. In this case, we see a substantial improvement in the certified accuracy on white-box infusion. The results on using a high lambda can be seen in Fig. 15.

500

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

Budget (Number of Flips)

(d) Partitions = 200

(e) Partitions = 250

(f) Partitions = 500

500

0.4 0.2 0.0 0

100

200

300

400

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8 0.6 0.4 0.2 0.0

500

Budget (Number of Flips)

0.6 0.4 0.2 0.0 0

100

200

300

400

200

300

400

0.6 0.4 0.2 0.0

500

0.6 0.4 0.2 0.0 0

100

200

300

400

200

300

400

500

0.8

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.6 0.4 0.2 0.0 0

100

200

300

400

Budget (Number of Flips)

(d) Partitions = 200

(e) Partitions = 250

(f) Partitions = 500

Figure 15: CIFAR-10 kernel regression with high regularization (λ = 10).

500

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8

100

Budget (Number of Flips)

(b) Partitions = 50

EnsembleCert UB EnsembleCert LB DPA (Black Box)

Certified Accuracy

(a) Partitions = 10 0.8

100

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8

Budget (Number of Flips) Certified Accuracy

0.6

Certified Accuracy

EnsembleCert UB EnsembleCert LB DPA (Black Box)

0.8

Certified Accuracy

Figure 14: CIFAR-10 kernel regression results for different numbers of partitions (λ = 0.01).

500

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Kernel SVM

0.4 0.2 0.0 100

200

300

400

0.4 0.2 0.0

500

100

200

300

400

Exact Cert Upper Bound Exact Cert Lower Bound DPA (Black Box)

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

500

Budget (Number of Flips)

(a) Partitions = 10

(b) Partitions = 50

Exact Cert Upper Bound Exact Cert Lower Bound DPA (Black Box)

0.8 0.6 0.4 0.2 0.0 0

0.6

100

200

300

400

Exact Cert Upper Bound Exact Cert Lower Bound DPA (Black Box)

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

Certified Accuracy

Exact Cert Upper Bound Exact Cert Lower Bound DPA (Black Box)

0.8

Certified Accuracy

0.6

Certified Accuracy

Exact Cert Upper Bound Exact Cert Lower Bound DPA (Black Box)

0.8

Certified Accuracy

Substantial improvement can be observed in certified accuracy on white-box infusion, as seen in Fig. 16.

Exact Cert Upper Bound Exact Cert Lower Bound DPA (Black Box)

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

500

Budget (Number of Flips)

(d) Partitions = 200

(e) Partitions = 250

(f) Partitions = 500

Figure 16: CIFAR-10 kernel SVM results for different numbers of partitions. Smoothed linear classifier

0.6 0.4 0.2 0.0 0

100

200

300

400

EnsembleCert SS-DPA

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

EnsembleCert SS-DPA

0.8 0.6 0.4 0.2 0.0

500

100

200

300

400

500

(a) Partitions = 10, q = 0.0001

(b) Partitions = 25, q = 0.0001

Budget (Number of Flips)

Certified Accuracy

Budget (Number of Flips)

Certified Accuracy

Budget (Number of Flips)

Certified Accuracy

EnsembleCert SS-DPA

0.8

Certified Accuracy

Similar to kernel regression and kernel SVM, substantial improvement is observed in certified accuracy on white-box infusion, as shown in Fig. 17.

EnsembleCert SS-DPA

0.8 0.6 0.4 0.2 0.0 0

100

200

300

400

500

Budget (Number of Flips)

(d) Partitions = 10, q = 0.0125

EnsembleCert SS-DPA

0.8 0.6 0.4 0.2 0.0 0

100

200

300

400

500

Budget (Number of Flips)

(e) Partitions = 25, q = 0.0125

EnsembleCert SS-DPA

0.8 0.6 0.4 0.2 0.0 0

100

200

400

500

(f) Partitions = 50, q = 0.0125

Figure 17: CIFAR-10 Smoothed linear regression as base-classifier

300

Budget (Number of Flips)

ICLR 2026 Workshop: Principled Design for Trustworthy AI

D.8

MNIST

Kernel Regression

0.4 0.2 0.0 0

200

400

EnsembleCert UB EnsembleCert LB SS-DPA

0.8 0.6 0.4 0.2 0.0

600

Budget (Number of Flips)

0.8 0.6 0.4 0.2 0.0 0

200

400

1.0 0.8 0.6 0.4 0.2 0.0

600

0.6 0.4 0.2 0.0 0

200

400

600

0.2 0.0 0

200

400

1.0

0.6 0.4 0.2 0.0 0

200

400

600

400

600

EnsembleCert UB EnsembleCert LB SS-DPA

0.8 0.6 0.4 0.2 0.0

600

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

200

Budget (Number of Flips)

200

400

600

Budget (Number of Flips)

(e) Partitions = 150 Certified Accuracy

Certified Accuracy

EnsembleCert UB EnsembleCert LB SS-DPA

0.4

Budget (Number of Flips)

(d) Partitions = 120 0.8

0.6

600

EnsembleCert UB EnsembleCert LB SS-DPA

Budget (Number of Flips) 1.0

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

(b) Partitions = 30 Certified Accuracy

Certified Accuracy

EnsembleCert UB EnsembleCert LB SS-DPA

400

1.0

Budget (Number of Flips)

(a) Partitions = 12 1.0

200

Certified Accuracy

0.6

1.0

Certified Accuracy

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

(f) Partitions = 200 Certified Accuracy

1.0

Certified Accuracy

We analyze the low and high regularization parameter λ on MNIST. Similar to CIFAR-10, we observe that for low values of λ, the base classifier by itself is not robust and is closer to the worst-case black box assumption described in Sec. A.1. Consequently, we do not see a significant improvement in utilizing white-box knowledge of the base classifiers. This is illustrated in Fig. 18 using low λ = 0.0001. In contrast, using a high degree of regularization changes the trend. In this case, we see a substantial improvement in the certified accuracy on white-box infusion. The results on using a high lambda can be seen using high λ = 0.1 in Fig. 19.

1.0 0.8 0.6 0.4

EnsembleCert UB EnsembleCert LB SS-DPA

0.2 0.0 0

200

400

600

Budget (Number of Flips)

(g) Partitions = 300

(h) Partitions = 400

(i) Partitions = 600

Figure 18: MNIST multi-class kernel regression results for different numbers of partitions (λ = 0.0001).

0.6 0.4 0.2 0.0 200

400

0.6 0.4 0.2 0.0

600

0.4 0.2 0.0

600

200

400

600

(a) Partitions = 12

(b) Partitions = 30

0.6 0.4 0.2 0.0 200

400

EnsembleCert UB EnsembleCert LB SS-DPA

0.8 0.6 0.4 0.2 0.0

600

0.6 0.4 0.2 0.0 200

400

600

0.6 0.4 0.2 0.0

600

EnsembleCert UB EnsembleCert LB SS-DPA

0.8 0.6 0.4 0.2 0.0 0

200

400

600

200

400

600

Budget (Number of Flips)

(e) Partitions = 150 Certified Accuracy

EnsembleCert UB EnsembleCert LB SS-DPA

400

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

Budget (Number of Flips)

(d) Partitions = 120 0.8

200

Certified Accuracy

Budget (Number of Flips)

Certified Accuracy

400

0.6

Budget (Number of Flips)

0.8

200

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

Budget (Number of Flips)

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

(f) Partitions = 200 Certified Accuracy

Certified Accuracy

1.0

Certified Accuracy

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

Certified Accuracy

1.0

Certified Accuracy

ICLR 2026 Workshop: Principled Design for Trustworthy AI

EnsembleCert UB EnsembleCert LB SS-DPA

0.8 0.6 0.4 0.2 0.0 0

200

400

600

Budget (Number of Flips)

(g) Partitions = 300

(h) Partitions = 400

(i) Partitions = 600

Figure 19: MNIST multi-class kernel regression results for different numbers of partitions (λ = 0.1).

ICLR 2026 Workshop: Principled Design for Trustworthy AI

Kernel SVM

0.4 0.2 0.0 100

200

300

400

0.4 0.2 0.0

500

300

400

0.4 0.2 0.0

500

100

200

300

400

500

(a) Partitions = 12

(b) Partitions = 30

EnsembleCert UB EnsembleCert LB SS-DPA

0.4 0.2 0.0 100

200

300

400

EnsembleCert UB EnsembleCert LB SS-DPA

0.8 0.6 0.4 0.2 0.0

500

0.2 0.0 200

300

400

500

Certified Accuracy

0.4

100

300

400

0.6 0.4 0.2 0.0

500

0.6 0.4 0.2 0.0 0

100

200

300

400

200

300

400

500

(f) Partitions = 200

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

100

Budget (Number of Flips)

(e) Partitions = 150

EnsembleCert UB EnsembleCert LB SS-DPA

0.6

200

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

Budget (Number of Flips)

(d) Partitions = 120 0.8

100

Certified Accuracy

Budget (Number of Flips)

Certified Accuracy

200

0.6

Budget (Number of Flips)

0.6

100

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

Budget (Number of Flips)

0.8

0.6

500

Certified Accuracy

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

Certified Accuracy

0.6

Certified Accuracy

EnsembleCert UB EnsembleCert LB SS-DPA

0.8

Certified Accuracy

Results showing substantial improvement in the certified accuracy on white-box infusion for kernel SVM are observed in Fig. 20.

EnsembleCert UB EnsembleCert LB SS-DPA

0.8 0.6 0.4 0.2 0.0 0

100

200

300

400

500

Budget (Number of Flips)

(g) Partitions = 300

(h) Partitions = 400

(i) Partitions = 600

Figure 20: MNIST multi-class kernel SVM results for different numbers of partitions.

Record · ID 10375 · SHA-256 3aaf3ca26d5c104c
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.