MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs
Authors: Tobias Lorenz
Marta Kwiatkowska
Mario Fritz
Venue: NeurIPS 2025 poster ()
Keywords: Mixed Integer Bilinear Programming
Certified Robustness
Provable Defenses
Data Poisoning
Robust Training
Adversarial Machine Learning
Optimization-based Certification
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose MIBP-Cert, a certified training method that uses mixed-integer bilinear programming to compute tight robustness guarantees under complex training-time perturbations. Our approach stabilizes training and improves certified accuracy.

Abstract: Data errors, corruptions, and poisoning attacks during training pose a major threat to the reliability of modern AI systems. While extensive effort has gone into empirical mitigations, the evolving nature of attacks and the complexity of data require a more principled, provable approach to robustly learn on such data—and to understand how perturbations influence the final model. Hence, we introduce MIBP-Cert, a novel certification method based on mixed-integer bilinear programming (MIBP) that computes sound, deterministic bounds to provide provable robustness even under complex threat models. By computing the set of parameters reachable through perturbed or manipulated data, we can predict all possible outcomes and guarantee robustness. To make solving this optimization problem tractable, we propose a novel relaxation scheme that bounds each training step without sacrificing soundness. We demonstrate the applicability of our approach to continuous and discrete data, as well as different threat models—including complex ones that were previously out of reach.

MIBP-Cert: Certified Training against Data
Perturbations with Mixed-Integer Bilinear Programs
Tobias Lorenz CISPA Helmholtz Center for Information Security Saarbrüccen, Germany tobias. lorenz@cispa.de
Marta Kwiatkowska
Department of Computer Science University of Oxford Oxford, UK
marta. www.wkwwwwwawksss...oooo ox. ac.
Mario Fritz
CISPA Helmholtz Center
for Information Security Saarbrücken, Germany fritz@cispa.de de
Abstract
Data errors, corruptions, and poisoning attacks during training pose a major threat the reliability of modern Al systems. While extensive effort has gone into empirical mitigations, the evolving nature of attacks and the complexity of data require more principled, provable approach robustly learn on such data-and understand how perturbations influence the final model. Hence, we introduce MIBP- Cert, a novel certification method based mixed-integer bilinear programming (MIBP) that computes sound, deterministic bounds to provide provable robustness even under complex threat models. By computing the of parameters reachable through perturbed or manipulated data, we can predict all possible outcomes and guarantee robustness. To make solving this optimization problem tractable, we propose novel relaxation scheme that bounds each training step without sacrificing soundness. We demonstrate the applicability of our approach continuous and discrete data, as well different threat models-including complex ones that were previously out reach.
Introduction
Data poisoning attacks are among the most significant threats the integrity machine learning models. Attackers can exert far-reaching influence by targeting systems in sensitive domains such as finance, healthcare, or autonomous decision-makee the training process, causing models to make incorrect or harmful predictions after deployment. Govermment agencies across the US and Europe have recognized poisoning as one of the fundamental threats to Al systems and highlight the need for robust defenses in their respective reports 9 30 and legislation [10].
These attacks inject malicious data into
To counter this threat, many empirical defenses have been proposed [7]. relying on data filtering, robust training, or heuristic inspection mitigate the effect of adversarial data. However, these methods offer no formal guarantees: they may reduce the harm of specific perturbations but cannot ensure robustness in general. As result, increasingly sophisticated poisoning attacks have been developed to bypass these defenses 22
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Property
FullCert 20
Sosnin et al.
28
BagFlip 337
MIBP--ert (Ours)
Deterministic certificates
fo-norm perturbations
x
foo-norm perturbations
/
X
Complex perturbations
X
X
XX
Real-valued features
Categorical features
Stable bounds during training
X
X
Support for & when training on the full dataset in a single batch.
Table I: Comparison of certified training methods. Only MIBP-Cert combines deterministic certifi- cates, mnixed-integee constraints, and support for both real-valued and categorical features.
A recent line of work shifts toward provable guarantees that bound the influence of training-time perturbations model predictions [20] 28 These methods adapt test-time certifiers [2] 36 to
the training process, using interval or polyhedral approximations to track parameter evolution under bounded perturbations. They compute real-valued bounds on model parameters throughout training. constraining the effect of adversarial data. These are important first steps toward certifiable robustness, offering deterministic guarantees under well-defined threat models.
However, while these types of bounds have been shown to be a good trade-off between precision and computational efficiency for test-time certification [19], the significant over-approximations of polyhedral constraints limit the method's ' stability for training. Lorenz et al. (20) show that interval bounds can cause training to diverge due compounding errors.
address this limitation by proposing MIBP-Cert, a precise certification method based on solving mixed-intesd bilinear programs (MIBPs). Rather than approximating training dynamics layer by layer, we frame certified training as an exact optimization problem in parameter space. To keep the method tractable, cut the computational graph after each parameter update and compute bounds iteration-wise. The resulting bounds remain sound and avoid the divergence issues of prior methods. In addition to tighter bounds, formulation supports more flexible and expressive threat models, including complex conditional constraints and structured perturbations beyond -p-balls. Our experimental evaluation confirms the theoretical advantages of MIBP- showing improved stability and higher certified accuracy for larger perturbations compared to prior work.
To summarize, our main contributions are:
New formulation. We present the first formulation that casts training-time robustness certification as mixed-integer bilinear program, enabling a different solution path.
Theoretical stability. We show that approach addresses fundamental convergence issues in existing methods.
Expanded scope. We enable certification of perturbation types that no prior method can handle.
Precision gains. We achieve tighter bounds, leading to certified accuracy improvements, especially in challenging large-perturbation regimes.
The implementation of our method is available at
2
Related Work
There are two major lines of work on certified defenses against training time attacks; probabilistic ensemble-base based methods and deterministic bound-based based methods.
Probabilistic Certificates by Ensemble-Based Methods.
Ensemble-based methods are typically
based on either bagging or randomized smoothing. Wang et al. (31), Rosenfeld et [26), and Weber et al. 34 extend Randomized Smoothing [ to training-time attacks. While Wang et al. [3] and
Weber et al. 34 compute probabilistic guarantees against Eo and fz-norm adversaries respectively, Cohen et al. provide these guarantees against label flipping attacks.

---

A similar line of work provides probabilistic guarantees against training- time attacks using bagging.
Jia et al. [13] find that bagging's 's data subsampling shows intrinsic robustness to poisoning. Wang et al. [33] enhance the robustness guarantees with advanced sampling strategies, and Zhang et al. [37 adapt this approach for backdoor attacks with triggers. Some studies explore different threat models, including temporal aspects [32] and dynamic attacks (5). Recent work (18) introduces deterministic bagging method. contrast, our work advances the state-of-the-ar in deterministic certification as
well as complex perturbation models.
Deterministic Certificates by Bound-Based Methods. contrast to these probabilistic certificates by ensemble based sampling methods, Lorenz et al. [20] and Sosnin et al. (28) propose to compute sound deterministic bounds of the model's parameters during training. They define polytope of allowed perturbations in imput space and propagate it through the forward and backward passes
during training. By over-approximating the reachable set with polytopes along the way, they compute sound worst-case bounds for the model's gradients. Using these bounds, the model parameters can be updated with sound upper and lower bounds, guaranteeing that all possible parameters resulting from the data perturbations lie within these bounds. Lorenz et al. [20] use intervals represent these polytopes and extend the approach to also include test-time perturbations. Sosnin et al. (28] use combination of interval and linear bounds. Both certify robustness to -norm perturbations (i.e., clean-label poisoning), and Sosnin et al. [28] additionally limit the number of data points that can be perturbed. In contrast, training in a mixed-ine -nteeer bilinear program that allows more stable bounds and enables complex perturbations with both real-valued and categorical features Table
provide righter relaxations by formulating deterministic certification of
3 Certified Training using Mixed-Integer Bilinear Programming
The goal of training certification is to rigorously bound the error that perturbations to the training data can introduce in the final model. This is fundamental challenge in certifying robustness to data poisoning: we seek guarantees that, under specified threat model, bound the effect on the trained model and in turn can be used to guarantee correct behavior.
Unfortunately, computing tight bounds on the final model for even small neural networks is infeasible in general. It has been shown to be Ei- -hard problem 23 meaning that to make certification tractable, we must settle for over-approxinnation. The challenge is to construct approximations that (i) are sound, (ii) introduce as little slack as possible, and (iii) remain computationally feasible.
Prior certified training approaches 20 28 address this by using Interval Bound Propagation (IBP) to derive parameter bounds. While sound, IBP suffers from two key limitations. First, it fails to preserve input-output dependencies, leading to compounding vveraapproximations even for simple operations. Second, the bounds grow monotonically over training due subtraction in the parameter update step. As shown by Lorenz et al. (20). this often causes training to diverge entirely.
These issues motivate the core design of our method: we (MIBP) to compute exact bounds for a single training step-including the forward pass, loss, backward pass, and parameter updates. In principle, could chain these exact encodings over the full training: in practice, this would be computationally prohibitive.
miixed-intege bilinear programming
Instead, relax only the parameter space each step, bounding the possible parameter configura- tions resulting from any permitted training data perturbation. This avoids divergence while preserving exact reasoning within each training step. The result is tractable certification scheme with precise per-step guarantees.
The remainder of this section formally defines our threat model (Section 3.1 approach on an illustrative example (Section 3.2). describes the MIBP formulation for parameter bounds (Section 3.3) and presents the implementation (Section 3.4).
demonstrates the
3.1 Formal Threat Model and Certificate Definition
Certification provides guarantees that a desired postcondition (e.g., correctness) holds for all inputs satisfying a specified precondition (e.g., bounded perturbations). In our data poisoning setting, the precondition formalizes the adversary's power to perturb the training dataset, and the postcondition encodes the property we aim verify after training, e.g., correct classification.
3

---

Precondition | Threat Model. We consider perturbations of the original training dataset D {(z,, y:) [= a modified dataset D' { v))] subject constraints. This permits modeling standard fp-norm perturbations, as well rich, dataset-wide threat models that couple samples, features, and labels. While we model perturbations as an adversarial game, they can also have non-malicious, natural causes, such as measurement errors or data biases.
Definition 3.1 (Family of Datasets). Let & S R and Y denote the input and label domains. The adversary's feasible perturbations described by a family of datasets:
D = (D' = [( b/))==1 a E X, 3/. E y, C'),
(1)
where ((D,D") is constraint over the original and perturbed datasets.
Constraint Syntax. The constraint set C(D, D') may include arbitrary linear, bilinear, logical, and integer constraints over (1) original and perturbed inputs F;, xy (2) original and perturbed labels Vi+
y/. (3) auxiliary variables Zj. and (4) global variables (e.g., number modified points). Possible
instantiations include (1) pointwise to bounds, e.g., ||= - zilloo I e; (2) sparsity constraints, e.g..
ΣØ= 2j S with zj 2 [J]' + xi]i::: (3) monotonic constraints, e-g., </[i] 2 =; and (4) class-conditional constraints, e.g.. Yi = c > x² T3. This formulation strictly generalizes threat models used in prior certified training work 20 28
Postcondition. The postcondition is the property we aim to verify for all models trained on permissible datasets. In general, this may include functional correctness, abstention, fairness, or task-specific safety properties. While our method supports arbitrary postconditions that can be encoded MIBP, follow prior work and focus classification correctness for experiments. Definition 3.2 (Certificate). Given a test input (Ir, 3). initial parameters 0o. and training algorithm A, certificate guarantees:
(e) = YD' 0' ((D)0)).
Parameter Bounds. Verifying if Eq. (2) holds directly is typically intractable. Instead, bound the space parameters reachable by the training algorithm under the threat model:
Definition 3.3 (Parameter Bounds). We define bounds [0. 0] such that
= AAD' 0o) + 0' [0.0) VD'E D.
This yields a sufficient condition for certification:
Proposition 3.4. If [xr = for all 0' 10. 0). then the cerlificate condition in Definition 3.2 is satisfied.
Proof. Follows directly from Definition 3.3 by substitution.
Iterative Relaxation. Because training unfolds across multiple iterations, we refine parameter bounds at each step. Let A, denote the i-th update step. Then we compute bounds recursively as:
0, 1 (, 8') < 0 VD'E D, e 0..1)
with d = 0, = 0 by initialization. Each step propagates bounds forward while maintaining soundness with respect to D. This recursive strategy enables certifiably robust training under expressive constraints, especially well-suited for tabular data.
3.2 Illustrative Example
To illustrate how MIBP-Cert captures the training process, we walk through a simple fully connected model with a single training step on a simplified example (Fig. [ This helps build intuition for the constraint operation a fully connected layer (without bias) with weights W11, W12, W21, and W22- This linear layer is followed by ReLU non-linearity and a second fully connected layer with weights wis and wg. We use (I, = 1,
described in the next section. The example has inputs, xq and x22 The first
1) as an example input with target label = 1. We set the perturbations e = 1, which leads upper and lower bounds of [0, 2] for both inputs. In the following, highlight all equations that belong to the optimization problem in teal. The full optimization problem with all constraints is in Appendix

---

Forward Pass. The first step is to encode the forward pass as constraints of the optimization problem. We start with the input by defining Ji and 22 as variables of the optimization prob- lem. By the definition of the threat model, their constraints are 0 S #1 S 2 and 0 S x2 S 2.
SP
W21
ReLÚ
For the fully connected layer, we encode the vari- ables 23 and 24 with respect to 21 and Z2. To do so, we need the parameters Way as variables, which are set to their initial values W11 1, W12 = 1, W21 1, and W22 = -1 One might be tempted to substitute these variables with their values to simplify the optimization prob- lem. However, this would cause information loss, which would decrease the precision of the final solution. This effect will be amplified in later rounds where Wa no longer single val- ues but intervals with upper and lower bounds. We add the constraints 23 W1121 + W21122 and 21 = W1221 + W2222 to the optimization problem. Since each other, the problem becomes bilinear, which is one of the reasons require bilinear opti- mization problem.
#2
84
#t
L(mz,))
8L
81
8L
8x1
Bas
aL
Bou
Dana
aL
0L
Bm
Btn
Figure 1: Illustration of a single forward and back- ward pass for a simplified model.
multiply two variables by
The ReLU layer can be directly encoded as a piecewise linear constraint: I5 max(0, x3) or, equivalently, I7 = 2g if z3 > O, and ay = 0 otherwise, Th defined accordingly. ReLUs are the main reason why we require mixed-integer programming. as they allow us encode piecewise linear constraints using binary decision variables. 27 is a linear combination of the two outputs: Iy Wy + W626 with W; 1 and Wg 1. At this stage, we can already see that MIBP-Cert's bounds are more precise: Computing the bounds for I7 using FullCert, we get -4 S x7 S 2, while solving the optimization problem gives -4 I 37 with tighter upper bound.
Loss. We also encode the loss function as constraints. Here, we use the hinge loss L(r,,t) max(0, 1 (æy) max(0, 1 z7) in this example because it is a piecewise linear function and therefore can be exactly encoded, analogous to ReLUs. General losses can be supported by bounding the function with piecewise linear bounds.
Backward Pass. For the backward pass, we need to compute the loss gradient for each parameter using the chain rule. It starts with the last layer, which is aL also piecewise linear function and can be encoded constraint the optimization problem.
Bey -1 if 27 1,0 otherwise. This is
The gradients for the linear layer 27 Wz + WgZ2 can be determined using the chain rule: at Bhs
0L and BL. ws Day" with corresponding expressions for 36 and wi- Given that das aL as well as Is and Wss are variables, this backward propagation leads to if 23 S and 0L OL otherwise. The derivatives for the parameters W11. W12, W21, and W22 function Dayg des analogously to Wy and Wig
aL 265 dey
the outer gradient Oiry"
bilinear constraints. The derivatives of ReLU are piecewise linear, resulting in âL 8wa
Parameter Update. The last step is the parameter update. We also encode the new parameters as constraint: w/ wi X Bws." Theoretically, could directly continue with the next forward pass, using the new parameters w/, resulting in an optimization problem that precisely encodes the entire training. However, this is computationally infeasible in practice. We therefore relax the constraints after each parameter update by solving the optimization problem for each parameter: w/ min w/ and w. max w/. subject to the constraints that encode the forward and backward passes from above. w/ and W. are real-valued constraints that guarantee w/ S w/ S W. This leads valid bounds for all parameters in consecutive iterations.
OL,
5

---

Using mixed- 3.3 Bounds via Mixed -Itteer Bilinear Programming
key contribution of our method MIBP-Cert is the approach solving Eq. 4 integer bilinear programming, we can compute an exact solution for each iteration, avoiding over- approximations. For each training iteration, we build an optimization problem over each model parameter, with the new, updated value as the optimization target. D, the current model parameters, the transformation functions of each layer, the loss, the gradients of the backward pass, and the parameter update are encoded as constraints. This results in 2m optimization problems- one minimization and one maximization per parameter- for model with m parameters the form
min/max subject to Input Constraints
0 2+1 j=
Parameter Constraints
Layer Constraints
(5)
Loss Constraints
Gradient Constraints
Parameter Update Constraints.
The objectives are the parameters, which we maximize and minimize independently to compute their upper and lower bounds. The constraints are the same for all parameters and only have to be constructed once. We present these constraints for fully connected models with ReLU activation.
Input Constraints. The first set of constraints encodes the allowed perturbations, in this case the
loo -ornorm with radius e, where Ox (0) are the auxiliary variables encoding the n input features:
(0) < +., ==
(0) k
2 Iz
==
(6)
Parameter Constraints. Parameters are bounded from the second iteration, which we encode as:
SO. j= j
m.
Layer Constraints. Linear layer constraints linear combinations of the layer's inputs of (!-1)
and the layer's weights (I) E 0,-1 and biases ((!) 0:-1:
( Σ uffffff + ((()
8
This results in bilinear constraints, as the layer's parameters are multiplied by the inputs, and both variables of the optimization problem.
ReLUy are encoded piecewise-linear constraints, e.g., via Big-M
13
SOS
if (- <0 u 1
1
(1-1) Ou
otherwise
Additional constraints for convolution and other activation functions can be found in Appendix C
Loss Constraints. We use the hinge loss because it is piecewise linear, and exactly. For other loss functions, we can use (piecewise) linear relaxations. With the last-layer output ol (L), the ground- -utth label y, and the auxiliary variable we define the constraint as Eq. (0):
therefore encode
aJ -y
if yol4) <
== max (o, (0,1-y0 yo(4)
(10)
(11)
do(
0
otherwise
Gradient Constraints. The gradients the hinge loss are also piecewise linear (Eq. ITI.
The local gradient of the ReLU function is also piecewise linear (Eq.
12
Multiplication with the
upstream gradient results in piecewise bilinear constraint (Eq. (33
0
if Φ; (1-1) 5
0L
0L
dx, (t)
0z (1-1)
otherwise
(12)
dxy (1-1)
dx
dx
au!!
(1-1)
(13)

---

All partial derivatives for linear layers are bilinear:
0J
ŌL
OJ (1-1) 0J
0J
0J
Wuv do
(14a)
dway ())
ou
0o
(14b)
0b
On
Dou
(
(14c)
Parameter Update Constraints. The last set of constraints is the parameter updates. essential to include this step before relaxation because the old parameters are contained in both subtraction operands. Solving this precisely key advantage compared prior work (Section 4
OJ 003
0 0:
= ,.,..,,?! m.
(15)
3.4 Implementation
We implement MIBP-Cert using Gurobi 14. which provides native support for bilinear and piecewise- linear constraints. To represent parameter bounds throughout training, use the open-source BoundFlow library [20).
During training, we iteratively build and solve a mixed-integer bilinear program for each model parameter. Each program encodes the input perturbation model, forward pass, loss, backward pass, and parameter update step. capturing the complete symbolic structure of one training iteration. Crucially, unlike interval methods, we preserve operand dependencies throughout, allowing bounds to tighten dynamically.
After training, we use the final parameter bounds to certify predictions. At inference time, we encode only the forward pass with symbolic parameters bounded by [0. 0]. If one logit is provably larger than all others across this range, we return its class label; otherwise, the model abstains.
A full pseudocode listing is provided in Appendix and additional implementation details can be found in Appendix D
Bound Convergence Analysis
28 suffer from significant apprrpppxiiationns introduced after each layer. While these approximations are effective for dnference-time certification [2] [7]. they require robust training to compensate (22).
Prior certified training methods based on interval or polyhedral relaxations 20
In training-time certification, the situation is different. Over-approximations accumulate across iterations and cannot be corrected during training. Lorenz et al. (20] show that these accumulated errors can prevent convergence, even at local minimum, resulting in exploding parameter bounds.
This behavior is analyzed using the Lyapunov sequence f; = 110 0012,, which measures the distance
the optimum. For standard SGD 66, the recurrence
h++1 h; (e, - 8 V() X2 (V)((()))))
(16)
distonce to optimum
discrcte dynamics
Under common assumptions (bounded gradients, decaying learning rate), the second term is bounded. The key requirement is that the first term remains negative to guarantee convergence.
Lorenz et al. (20) show that this condition may fail under interval arithmetic: if the current parameter bound + and the (unknown) optimum O* overlap, the worst-case inner product in Eq. (16) may vanish or become positive.
MIBP-Cert avoids this issue by maintaining the exact symbolic structure of the update step. Rather than reasoning over interval bounds, we evaluate the convergence condition for all possible realizations 0g E O,, 0* @+ As shown by Bottou 66. the convergence term remains negative for every such pair under the convexity assumption, ensuring that training remains stable.
A second limitation noted by Lorenz al. 20 is that parameter intervals can only grow when both operands of the addition are intervals: 0 = 6, ( + 0 = |0 [(,) This
leads to expanding bounds over time, regardless of convergence.
MIBP-Cert overcomes this by computing exact parameter updates (Eq. 15 preserving dependencies and allowing parameter bounds to shrink. As result, we do not observe divergence or instability in
7

---

practice. While the exact formulation is more computationnlly expensive, it leads to significantly tighter bounds and more stable certified training.
5
Experiments
We evaluate MIBP-Cert on certified accuracy, runtime, and support for expressive threat models, comparing it to prior methods across multiple datasets.
5.1 f -e-Perturbations of Continuous Features
We evaluate MIBP-Cert experimentally and compare it to the state of the art in deterministic training certification: FullCert (00 and Sosnin al. [28).
TwoMoons. We evaluate on the Two-Mon Moons dataset- two classes configured in interleaving half 2 presents the certified accuracy, i.e., the percentage of data points from a held-out test set where Algorithm returns the ground-truth class. All values are the mean and standard deviation across different iid seeds.
circles-as as it is used in prior work. Table
For small perturbation radii e, our method performs similarly the basclines. With increasing radius, the advantages of tighter bounds become apparent, where our method significantly outperforms the baselines. This trend makes sense, as the over-approximations become more influential with larger perturbations. The second advantage of our method becomes apparent when looking at the standard deviations. The small standard deviation compared to the baselines shows a much more stable training behavior, which aligns with our analysis in Section
0.0001
0.001
0.01
Sosnin et al. FullCert
83.8%+10.02
0.03
69.0%=10.10
83.9%+3.66
82.2%=4.40
71.5%=11.20
MIBP-Cert (ours)
83.3%+00.05
82.0%=0.05
81.4%:00.06
Table 2: Comparison of MIBP-Cert to FullCert (20) and Sosnin et al. 28 for different values. The numbers represent the mean and standard deviation of certified accuracy across random seeds.
UCI Datasets. To show the transferability of these results to different datasets, we evaluate our method on two additional datasets the same threat model: the Iris [T] and Breast Cancer Wisconsin [35]. Table Ba shows certified accuracy for 2-class subset of the Iris dataset. Even for large perturbation radii of 0.1 after standardization, we guarantee correct prediction for all test points. The radius decreases for larger perturbation radii, dropping below 50% for 0.3. Table 3b shows the generalization of our method to multi-class classification. Table Bc (right) demonstrates the certified accuracy for breast cancer diagnostics. MIBP-Cer shows that the larger feature count gives the adversary more control, which decreases the certified accuracy for larger perturbations.
0.1
0.2
0.3
0.00
0.01
0.02
0.000
0.001
0.010
FullCert
88%
76%
20%
FullCert MIBP-Cert
84%
68%
64%
FullCert
95%
83%
38%
MIBP-Cert 100%
92%
40%
84%
72%
68%
MIBP-Cert
95%
94%
51%
(a) 2-class
(b) Iris full
(c) Breast Cancer
Table 3: Certified accuracy of MIBP-Cert (ours) and FullCert (20 for training 2-layer MLP on different UCI datasets [16].
5.2 Complex Constrained Perturbations on Discrete Features
We investigate how to understand and provide robustness when training on health data that has been shown to be prone to corruptions, such as missing data and biases in self-reporting [I] Unlike prior work, MIBP-Cert's general formulation supports fine-grained perturbation models beyond simple f,. norms... We demonstrate this the National Poll on Healthy Aging (NPHA) [21], tabular dataset of 714 14 survey responses from adults over 50. includes 14 self-reported categorical features covering mental and physical health, sleep quality, and employment. We evaluate three structured

---

perturbation scenarios that reflect realistic sources of data uncertainty and use MIBP-Cert to compute the worst-case impact of each. Table reports the certification rate (fraction of test samples with verified prediction) and certified accuracy (fraction of certified samples with the correct label).
Precondition
Certification Rate
Certified Accuracy
Assuming accurate health data
(100.0%)
56.3%
Modeling missing mental health values
56.3% 98.6%
Modeling missing values across all features
95.8%
53.5%
Modeling mental health over-reporting
91.5%
50.7%
Table 4: Certification under complex perturbation models. (preconditions) to assess their impact on prediction robustness.
We vary the allowed perturbations
Missing mental health values. Some participants declined to answer questions mental health, possibly introducing bias (c.g., lower-scoring individuals may be more likely to abstain). We model this by replacing the "no answer" option with perturbation model of any valid response: æ[j]] (0, E,, 1. Despite this uncertainty, 98.6% of the predictions are certifiable (guaranteed not to be affected by the missing values in the training data), and the certified accuracy is unaffected.
Missing values across all features. Extending this idea, we model all missing values across the 14 features as perturbations that can take any valid value. The impact is larger, reducing certification to 95.8% and certified accuracy to 53.5%, indicating that imputation uncertainty can meaningfully affect model hehavior- but on the other hand we still know the (certified) test samples for which the prediction cannot change.
Mental health over-reporting. Self-assessments are prone to bias [I]. We simulate optimistic self-reporting by allowing mental health values above the smallest value to be either the reported value k the next worse value k-1: Ak {2, .2....,5] 5] =]j] vjj & {k; k-,, x x[ki], (rl,, --]
{0, 1), x=k] + z[k-1] = 1. The result: 91.5% of the predictions remain certifiable, but in 8.5%
of the cases, optimistic self aaff-assessment in the training data can alter the model's prediction. This
highlights the importance of accounting for reporting bias in downstream conclusions.
5.3 Runtime and Complexity Analysis
MIBP-Cert achieves tighter bounds than poly- tope-based methods, at the cost of increased op- timization complexity, Solving a mixed-integer bilinear program (MIBP) is NP-hard in general 17
0.01
0.1
batch-size 10
4
36
batch-size 100 116
174552
Table 5: The number of branches explored by the optimizer during the first two training iterations, for different batch sizes and perturbation radii. Al- though theoretical limits are exponential, empirical counts remain tractable.
In our formulation, binary variables arise from ReLU activations and max terms in the loss, yielding approximately (n+ binary deci- sions per iteration, where n is the number of activations, & is the number of classes, and b is the batch size. Each optimization subproblem thus combines combinatorial branching over these binary variables with continuous bilinear relax- ations that depend on the number of model parameters In theory, the resulting search tree thus grows exponentially in (6+ and superlinearly with p. But modern solvers such as Gurobi employ presolve, bound tightening. and outer-approximation heuristics that drastically prune this tree in practice, making solutions feasible for most problems.
Empirical runtimes remain several orders of magnitude below the theoretical worst case, even for large batch sizes or perturbation radii (Table 5 Perturbation radius primarily affects complexity through the number of active ReLU switches, and early epochs are typically faster due to tighter parameter bounds. A full runtime breakdown is provided in Appendix E.2

---

Discussion and Limitations
MIBP-Cert addresses key limitations of prior certified training methods by avoiding coarse convex over-approximations that can lead to diverging bounds and unstable learning. Using mixed-integed bilinear programming (MIBP), it computes tight bounds at each iteration, ensuring that parameter intervals can shrink over time and remain stable.
The primary benefit of this increased tightness is improved certified accuracy, particularly under larger perturbation radii. Our experiments show that MIBP-Cert not only yields higher certified accuracy but also exhibits lower variance, indicating more robust behavior across
Beyond accuracy, the flexibility of our MIBP formulation enables more expressive threat models. As demonstrated in Section 5.2 it can encode structured constraints and domain-specifit assumptions, which was impossible with prior methods. This opens the door to modeling realistic attacks and non-adversarial perturbations alike, such measurement noise reporting bias in tabular domains.
These tighter, more expressive bounds come at the cost of higher complexity, and, thus, compu- tational cost: solving bilinear program per parameter per step is more expensive than layer-wise interval or polytope propagation. We demonstrate that our method can be applied safery, security, or privacy-critical problems used in practice, and we expect that follow-up work can improve on the scalability of our prototype implementation, similarly to how test-time certification methods have improved substantially over early, expensive methods that were limited to small model sizes as well. Potentially impactful directions include: hybrid methods combining our tight bounds selectively with faster approximations elsewhere, exploiting model sparsity and structural properties for faster optimization, exploring low-level engineering efficiency gains through optimized and/or parallelized implementations, and improvements in how to guide optimizer heuristics by exploiting domain/problem knowledge.
range of
Overall, our results suggest that high-precisiog certified training is not only feasible but necessary to move beyond current limitations partinlllll when robustness must be guaranteed under complex perturbation models.
7 Conclusion
We present MIBP-Cert, a certified training approach that overcomes the limitations of prior work by avoiding loose convex veer-approximations and enabling exact parameter bounds via MIBP. This leads to significantly improved certified accuracy and training stability, especially under larger perturbations and expressive threat models. Our results demonstrate that precise, structured certification is not only feasible but essential for robust learning under real-world data corruptions and attacks.
Acknowledgments and Disclosure of Funding
We thank the NeurlPS reviewers and area chairs for their valuable feedback. This work was partially funded by ELSA-ELSEEE European Lighthouse on Secure and Safe Al funded by the European Union under grant agreement number 101070617, as well as the German Federal Ministry of Education and Research (BMBF) under the grant AlgenCY (16KIS2012), and Medizininffrrmaik-Paattte Analytik der Medizin" (PrivateAlM), grant number 01ZZ223160 MK received funding from the ERC under the European Union's 's Horizon 2020 research and innovation programme (FUN2MODEL, grant agreement number 834115).
Prrivatsphären-schhizzee
10

---

References
[1] Alaa Althubaiti. Information bias in health research: definition, pitfalls, and adjustment methods. Journal of multidisciplinary healthcare, 2016.
[2] Evelyn Martin Lansdowne Beale and John A Tomlin. Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. Operational Research, 69, 1970.
[3] Pietro Belotti, Christian Kirches, Sven Leyffer, Jeff Linderoth, James Luedtke, and Ashutosh Mahajan. Mixed-integer nonlinear optimization. Acta Numerica, 22:1-131, 2013,
[4] Akhilan Boopathy, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Cnn-cert: An efficient framework for certifying robustness of convolutional neural networks. In AAAI Conference on Artificial Intelligence (AAAI). 2019.
[5] Avinandan Bose, Madeleine Udell, Laurent Lessard, Maryam Fazel, and Krishnamurthy Dj Dvijotham. Certifying robustness to adaptive data poisoning. In /CML Workshop: Foundations of Reinforcement Learning and Control-Connection and Perspectives, 2024.
[6] Léon Bottou. Online learning and stochastic approximations. On-Line Learning in Neural Networks, 1998.
[7] Antonio Emanuele Cinà, Kathrin Grosse, Ambra Demontis, Sebastiano Vascon, Werner Zellinger, Bernhard A. Moser, Alina Oprea, Battista Biggio, Marcello Pelillo, and Fabio Roli. Wild patterns reloaded: A survey of machine learning security against training data poisoning. ACM Compul. Surv., 2023.
[8] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning (ICML), 2019.
[9] ENISA. Ai cybersecurity challenges: Threat landscape for artificial intelligence. Technical report, European Union Agency for Cybersecurity (ENISA), 2020.
[10] European Union. Regulation (EU) 2024/168 6224/1689 the European Parliament and of the Council of
13 June 2024 laying down harmonised rules artificial intelligence and amending Regulations (EC) No 300/2008, (EU) No 167/2013, (EU) No 168/2013, (EU) 201 8/858, (EU) 201 8/1 139 and (EU) 2019/2144 and Directives 2014/90/EU, (EU) 2016/797 and (EU) 2020/1828 (Artificial Intelligence Act) (Text with EEA relevance). Official Journal of the European Union, 2024.
[11] R. A. Fisher. iris. UCI Machine Learning Repository, 1936.
[12] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 1810. 12715, 2018.
[13] Igor Griva, Stephen G Nash, and Ariela Sofer. Linear and Nonlinear Optimization 2nd Edition. SIAM, 2008.
[14] Gurobi. Gurobi Optimizer Reference Manual, 2024. URL
[15] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong, Intrinsic certified robustness of bagging against data poisoning attacks. In AAAI Conference on Artificial Intelligence (AAAI), 2021.
[16] Markelle Kelly, Rachel Longjohn, and Kolby Nottingham. The uci machine learning repository. URL httts://///:re ics. uci edu
[17] Jon Lee and Sven Leyffer. Mixed integer nonlinear programming, volume 154. Springer Science & Business Media, 2011.
[18] Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In International Conference on Learning Representations (ICLR), 2021.

---

[19] Linyi Li, Tao Xie, and Bo Li. Sok: Certified robustness for deep neural networks, In 2023 IEEE Symposium on Security and Privacy (S&P), 2023.
[20] Tobias Lorenz, Marta Kwiatkowska, and Mario Fritz. Fullcert: Deterministic and-to-end certification for training and inference of neural networks. In German Conference Putlern Recognition (GCPR), 2024.
[21] Preeti N. Malani, Jeffrey Kullgren, and Erica Solway, National poll on healthy aging (npha), 2019. URL URL http::ttp//// //tp:://doo..oo
000.0388////PP/3330000 v1
[22] Yuhao Mao, Stefan Balauca, and Martin Vechev. CTBench: a library and benchmark for certified training. In International Conference on Machine Learning (ICML), 2025.
[23] Samuele Marro and Michele Lombardi. Computational asymmetries robust classification. In Proceedings of the 40th International Conference Machine Learning, 2023.
[24] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[25] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. Journal of machine learning research, 12(Oct):2825-283) 2011.
[26] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label-flipping attacks via randomized smoothing. In International Conference on Machine Learning (ICML), 2020.
[27] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev, An abstract domain for certifying neural networks. In Proceedings of the ACM on Programning Languages (PACMPL), 2019.
[28] Philip Sosnin, Mark N. Müller, Maximilian Baader, Calvin Tsay, and Matthew Wicker. Certified robustness data poisoning in gradient-baad basedd training. arXiv preprint 2XXv:2440.005700 2024.
[29] Octavian Suciu, Radu Marginean, Yigitcan Kaya, Hal Daume III, and Tudor Dumitras. When does machine learning FAIL? generalized transferability for evasion and poisoning attacks. In USENIX Security Symposium (USENIX Security), 2018
[30] Apostol Vassilev, Alina Oprea, Alie Fordyce, and Hyrum Anderson. Adversarial machine learning: A taxonomy and terminology of attacks and mitigations. Technical report, National Institute of Standards and Technology, 2024.
[31] Binghui Wang, Xiaoyu Cao, Neil Zhenqiang Gong, et al. On certifying robustness against backdoor attacks via randomized smoothing. In CVPR Workshop on Adversarial Machine Learning in Computer Vision (CVPRW), 2020.
[32] Wenxiao Wang and Soheil Feizi. Temporal robustness against data poisoning, Advances in Neural Information Processing Systems (NeurIPS), 2023.
[33] Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In International Conference on Machine Learning (ICML), 2022.
[34] Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. In IEEE Symposium Security and Privacy (S&P), 2023.
[35] William Wolberg, Olvi Mangasarian, Nick Street, and W. Street. Breast Cancer Wisconsin (Diagnostic), 1993.
12

---

[36] Huan Zhang, Tsui- Wei Weng, Pin- Yu Chen, Cho-Jui Hsich, and Luca Daniel. Efficient neu- ral network robustness certification with general activation functions. Advances neural information processing systems (NeurIPS), 2018.
[37] Yuhao Zhang, Aws Albarghouthi, and Loris D'Antoni. Bagflip: A certified defense against data poisoning. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
13

---

A Full Example
In Section 3.2 present example model illustrate our method. We list the full optimization problem for the first training iteration here.
min/max
w/1 E [11, 12, 62,
subject to
0 0 2
OL
ØL I6 dxy
0 x2 2
Ows
1 5 w11 1
aL
Sin 0x7
1 < w12 $
d.g
1 S 122 <
AL
if 3/4 otherwise
-1 W22 < -1
dz
0
-1 < W/ < -1
aL
aL Bes
if 23 otherwise
1 S w6 1
33 2 + W2122
24
w 2
T2
aL Dwn1
aL
x3
if 23 > 0 otherwise
25
aL aL.
0
1r dr
Ow12
F4
if 24 > 0
äL ØL
T6
0
otherwise
Ow21
0r
37
= W5435
+ Wg
OL
aL.
Ow22 2 dr
1
if x7 > 0 otherwise
L =
0
aL
aL.
ØL
Ou2 120n 0r3
+ W22 Oaa
aL
-1
if 27 > 0 otherwise
0L = Ii 0x3
aL
0L
827
0
+ w12 0xA
dr
0L
aL Ou7 OL.
w wi X OL
Ows
Dws
OL.
Oze
Ox7
B Training and Prediction Algorithms
We implement the optimization procedure outlined in Section 3.4 according to Algorithm ! For each iteration of the training algorithm. initialize an optimization problem (5) and add the parameter bounds as constraints (6). For each data point æ. we add the input constraints (8), layer constraints (10), loss constraints (12), gradient constraints (13-15), and parameter update constraints (18). We then solve the optimization problem for each parameter, once for the upper and once for the lower bound (19-20). The algorithm returns the final parameter bounds.
Once the model is trained, we can use the final parameter bounds for prediction (Algorithm 2) The principle is the same as encoding the forward pass for training (3-7). For classification, we can then compare the logit and check whether one always greater than others (9-14). so, we return corresponding class (16). Otherwise, cannot guarantee prediction and return abstain (19).
C
Additional Constraints
Our method for bounding neural network functions introduced in Section 3.1 is general and can be extended to layer types beyond linear and ReL.Us introduced in Section as we show on the examples of convolution and general activation functions:
14

---

Algorithm MIBP Train
1: Input: dataset D, initial parameters 0g E R", iterations n E N
2: Output: parameter bounds e, On E R
3: Initialize oo 0g + 80
4: for = 1 to n do
5: mibp <- initialize cettialize_pptmmzzaatinn
6:
Satidauuuuueeeeeesssiinnnne-... 7: for do
8: mibp-add_input input_constraint(((]]
9:
for each layer to L do
10:
mibp.add peaadddllye_emmeeee (alter__costrrint((() end for mibp.add _oss_oos________ poss_constraintty mibp.add loss gradient loss_gradienttttttcceg constraints()
12:
14:
for each layer I L to do
mibp.add granddegggdeenn_eeoe crrrudienn_costtrinss///// end for end for 18: mibp.add Bactlddd_ramaarapppe gypdate_constraing
16:
19:
O mibpp.innimie((0.)
20: 0, mibp.maximize(
21:
end for
22: Return e,, 8n
Algorithm 2 MIBP Predict
1: Input: test data parameter bounds 0, 0 E R.
2: Output: certified prediction y. or abstain
3: mibp +- initialize inttialize_optimizatton
4: mibp.add parameter constraints( B)
5: mibp.add _is__jnnpl___vae variables(x))
6: for layer 1 = 1 to T. do
7: mibp.add_layer_eeee (nnvercconttaiits(]
8: end for
(L)
9: for each logit Ou
10: c True
11: for each logit (4) + Ou
(1)
mibp.minimiie(( (L)
oe (1))
12:
C C (c. 2 0)
14: end for
15: if then
16: Return
17: end if
18:
end for
19: Return abstain
Convolution.
Convolution layers linear operations and can be encoded linear constraints. Given an input tensor X E XXW and kernel K E Ca x Ca xkw the convolution output Y E Caa xHI xW" is defined by:
Cn ΣΣ
kg
kw
Yos.j
KecCmm Xet, Xet, ftm-1. + be.
(17)
This operation is equivalent to sparse affine transformation and can be flattened into set of linear constraints y AX + b, where encodes the convolution as a sparse matrix multiplication and the bias. These constraints can be directly integrated into our MIBP formulation.
15

---

General Activations. MIBP-Cert also supports other non- non-linear activation functions (e.g., sigmoid, tanh) by employing sercewise-linerd upper and lower bounds over the relevant input range. For example, in the range [0, 1]:
Sigmoid: 0.25x + 0.48 & a()) & 0.25z + 0.5
Tanh: 0.76x v tanh x S x.
Although these relaxations introduce some degree of over-approxximatin, their piecewise-linear formulation allows the bounds to be made arbitrarily tight.
D Training and Implementation Details
Implementation Details. We build on Lorenz et al. [20]'s open-source library BoundFlow with an
MIT license, which integrates with PyTorch [24] for its basic tensor representations and arithmetic. As a solver backend, we use Gurobi version 10.0.1 with an academic license. Gurobi a state-of-the- art commercial solver that stable and natively supports solving mixed-integer bilinear programs. It also provides a Python interface for easy integration with deep learning pipelines.
Compute Cluster. All computations are performed on a compute cluster, which mainly consists of AMD Rome 7742 CPUs with 128 cores and 2.25 GHz. Each task is allocated up to 32 cores. No GPUs are used since Gurobi does not use them for solving.
Dataset Details.
Two Moons (Synthetic) We use the popular Two Moons dataset, generated via scikit-learn [25] is 2D synthetic binary classification task with non-linear decision boundaries, commonly used to visualize model behavior and certification properties. We set the noise parameter to 1. and sample 100 points for training, 200 points for validation, and 200 points for testing, respectively.
UCI Iris (77) The Iris dataset is classic multi-class classification benchmark with 150 samples and 4 continuous features. We experiment with both the full 3-class setting (100 train, 25 validation, 25 test) and a reduced binary subset of the first two classes (using 50 train, 25 validation, 25 test). The low input dimensionality and categorical nature of the target make it useful testbed for analyzing certified training on tabular data.
UCI Breast Cancer Wisconsin /35/ We use the UCI Breast Cancer Wisconsin dataset (binary classifi- cation) with 30 continuous input features. We split the data into 369 training. 100 validation, and 100 test samples. The dataset allows us to study our method's ' scalability to medium mrdiium-szzed tabular data and its performance under realistic feature distributions and class imbalances.
The National Poll on Healthy Aging (NPHA) ) [1 is tabular medical dataset with 14 categorical features and target classes. The features represent age, physical health, mental health, dental health, employment, whether stress, medication, pain, bathroom needs, or unknown reasons keep patients from siceping, general trouble with sleeping, the frequency of taking prescription sleep medication, race, and gender. The target is the frequency of doctor visits. We randomly (iid) split the data points into 3 independent sets, with 10 for validation, 10 % for testing, and the remainder for training.
Unless indicated otherwise, we use fully connected networks with ReLU activations, two layers, and 20 neurons per layer. For binary classification problems, loss, i.e., J = max(0 (0, - -- (x)), because it is piecewise linear and can therefore be encoded exactly. It produces similar results to Binary Cross-Entropp loss for regular training without perturbations.
Model Architecture.
hinge
Training Details. We train models until convergence using a held-out validation set, typically after 5 to 10 epochs on Two-Moons. We use default batch size of 100 and constant lcarning rate of 0.1. We sub-sample the training set with 100 points per iteration. All reported numbers are computed using a held-out test set that was not used during training or hyper-parameter configuration.
Comparison with Prior Work. For the comparison to Lorenz et al. 200, we use the numbers from their paper. Since Sosmin et al. (28 do not report certified accuracy for Two-Moons, we train new models in an equivalent setup. As a starting point, we use the Two-Moons configurations provided in their code. We change the model architecture to match ours, i.e., reducing the number of hidden neurons to 20. We also set n = [D] to adjust the threat model be the same as ours. The solver mode left at its preconfigured "interval+crown" for the forward pass and "interval" for the backward pass.
16

---

Contrary to Sosnin et al. (28), we do not increase the separation between the two classes compared to the default scikit-learn implementation. We also do not add additional polynomial features.
E
Additional Experiments
E.1
Model Architecture Ablations
Section 5.3 shows that the complexity of MIBP-Cert mainly depends the number of activations the number classes k, and the batch size b. Table[jeemonstrates the influence of batch size and perturbation size experimentally. Here, we empirically analyze the influence of the model width and depth in Tables and 7 which both influence the number of parameters and activations. We use the same models and data in T with 0.01, training for 1 epoch with varying network width and depth.
Layers width
Total parameters
Training time
x 5
0.75 s
2 x 10
52
1.24
x 20
102
4.79 s
2 x 30
152
27.7
Table 6: MIBP-Cert's runtime for epoch with different layer widths.
Layers x width
Total parameters
Training time
2 x 5
27
0.75
x 5
2.37 s
4 x 5
87
6.24
5 x 5
117
12.9 8
x 5
147
22.1
Table 7: MIBP-Cert's runtime for epoch with different numbers of layers.
The results show that training time corresponds roughly to the number of parameters.
E.2 Runtime Comparison
To compare the real-world execution time of MIBP-Cert with that of prior work, we report the average runtime per epoch on the Two-Moons dataset, the same setting as shown in Table FullCert and Sosnin et al. in pure IBP mode both take 0.014s per epoch. IBP+CROWN mode (the default for TwoMoons) takes 0.04s per epoch, and CROWN takes 0.05s per epoch. This is relatively consistent across different perturbation radii (c) and epochs. We report the average runtime for the first 5 epochs Table Training runs typically either converge or diverge after 5 epochs.
0.0001
0.001
0.01
Method
Time
CA
Time
CA
Time
CA
FullCert
0.01 s
83.9%
0.01
82.2%
0.01 s
71.5%
CROWN+IBP
0.04 s
83.8%
0.04 s
82.3%
0.03
69.0%
MIBP-Cert (ours)
19
83.3%
54 s
82.0%
156
81.4%
Table Runtime of different certified training methods for a 2-layer MLP on TwoMoons. "Time" the average runtime per epoch across the first 5 epochs, and "CA" is the certified accuracy.
While our method slower, especially for larger e, delivers significantly improved certified accuracy and training stability, validating our theoretical analysis regarding the runtime-pres runtime-precision trade-off. Furthermore, as Table I and Section 5.2 demonstrate, our method uniquely certifies perturbation types that were previously impossible.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims are supported by experimental results and/or theoretical analysis.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We clearly state limitations throughout the paper. Section 5.3 analyzes the
theoretical worst-case complexity and practical scaling. General limitations are summarized in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specificatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The method is described in detail in Section 3 including its algorithmic
implementation in Section 3.4 and Appendix Experimental details are described in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
19

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We releasing all code under open-source license reproduce the main experimental results of our paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc
cublic//uuides/Codeetubii. itw.ooeeSuubiissiooooooooiiogg for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccppclcccuui.eeeeeeccc wetpeeee/oooSSeeessssedeee.. www.ssssiicgcyo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details are reported in Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the mean and standard deviation over 10 iid sampled initializations for the main comparison experiments in Table 2 For additional experiments, we limit to single run due to computational constraints.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
20

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details the compute resources used listed in Appendix D Runtime is analyzed Section 5.3 and Appendix E.2
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't itdn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps:/neurips..cm http:////.eaauppp..copp///c/ecaa ctcceeieeeenccccccedeeeeeiee
Answer: [Yes]
Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We expect a positive societal impact, as the method can verify robust machine learning systems against data poisoning, data corruption, biases.
Guidelines:
21

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets and core libraries are referenced. Licenses included where available.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
22

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The assets are documented and will be released under the MIT license once published.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
23

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurips hett:s///eerrrpp.ccc//oofrrreere cc///oofeeeeeeee//22////... for what should or should not be described.
24


Reviews:
[{"review_id": "9oeVthZmDx", "reviewer": "Reviewer_4X7Z", "summary": "This paper is an advanced form of training time certification. The idea is to try to certify a prediction as being valid regardless of a possible adversarial manipulation of the input data. During training, rather than performing normal SGD updates, parameters are updated and so are per parameter bounds that denote the possible range of the parameter given a fixed perturbation on the inputs. After training, these bounds are used during prediction, to provide predictions with certified ranges. The certification means that for any perturbation of the training data within the prescribed range, the prediction is guaranteed to lie within the calculated range. The difference to related works is that bilinear equations are established to compute the bounds, by analyzing the sums of parameters and activations from the previous layer, where the activation functions must be relu in order to yield tractable mixed integer objective, where the integer denotes whether the relu is active. The method gives tighter predictive bounds at the cost of more computation.", "questions": "Q1) isn’t the classic adversarial setting one in which the attacker perturbs a test point given a fixed trained model? Please comment on the general applicability of that and the proposed setting.\nQ2) I feel like equation (1) could be put in a clearer way. (2) also seems kind of strange but maybe I’m just not familiar with this style of notation. I understand the meaning of both of course, so this is a style comment.\nQ3) Does A get overloaded on lines 119 and 125 and equation (2)?\nQ4) On line 127, what does it mean to solve (2)?\nQ5) This may expose my naivety to the area - but could one optimize to convergence (a point in parameter space, no bounds), and then compute the bounds that occur by optimizing from that stationary point under a set of perturbed data? Could this somehow be more efficient that tracking from a random initialization?\nQ6) How about pre-training a large model, and then performing certified post-training for just the prediction head assuming the attacker model? Would that just reduce to a single layer analysis that could be very efficient?\nQ7) What is the number of branches? Please define this for non-specialists.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThis is an important problem. The proposed solution is highly non-trivial but the authors demonstrated practical improvements in terms of tighter bounds. It is remarkable that the authors made this work on real world problems (albeit small ones by today’s industrial ML standards). The paper includes a wonderful background and is very well explained, with thoughtful worked examples. I enjoyed reading the worked example, that shows how one obtains tighter bounds in a concrete example. \n\nThe paper gives stability guarantees where the related [18] actually discusses divergence of related methods, this is very cool!\n\nTable 3 is great, and really makes the main point of the paper clear.\n\nWeaknesses\n\nTo play devil’s advocate - the method is rather complex and presumably very slow to run. However, since the results are so strong, it is pareto optimal (for high compute budgets relative to dataset size). Hopefully, these ideas will pave the way for more efficient and related follow up papers.\n\nIt would be nice to see the timing for FullCert in the timing info in the appendix.", "was_revised": true, "final_justification": "I have considered everything already, thanks.", "rebuttal": "Dear reviewer 4X7Z,\n\nThank you very much for your thoughtful and constructive review! We are delighted that you enjoyed reading our paper and appreciated its relevance, impact, and clarity. Below, we address your questions and suggestions in detail.\n\n&nbsp;\n### 1. Classic adversarial vs. training-time perturbations\n\n**The literature assumes different threat models**. Similarly to traditional software security, any input to a model can negatively influence its behavior. **People have mainly studied two sources: perturbation of the test data (e.g., traditional adversarial examples) and perturbation of the training data (e.g., poisoning attacks)**. While several certification methods exist for test data perturbations, we still largely lack such guarantees for training data, as demonstrated in our paper. Our method thus addresses this gap.\n\nSince training-time guarantees are a much more difficult problem, **it is straightforward to extend our guarantees to also include test-time perturbations**. We can change the post condition (eq. 2) to compute the certificate with respect to a (potentially) perturbed $\\tilde{x}$:\n$$f_{\\theta'}(\\tilde{x}) = y \\quad \\forall \\tilde{x} \\in d(\\tilde{x}, x) \\land \\forall D' \\in \\mathcal{D} \\ \\land\\ \\theta' = A(D', \\theta_0).$$\n\n$d(\\tilde{x}, x)$ defines the perturbation model of $x$, e.g. an $\\ell_p$-norm of classical adversarial examples. We will discuss this potential extension in the revision of our paper.\n\n&nbsp;\n### 2. Clarification of equations (1) and (2)\n\nThank you! We appreciate the feedback and **will look into ways to make the equations more accessible**. Defining pre- and postconditions is common in the certification literature; we will aim to clarify it for a wider audience.\n\n&nbsp;\n### 3. Overloading of Symbol $A$\n\nYes, thank you for pointing this out! We will change the symbol to avoid confusion.\n\n&nbsp;\n### 4. What does it mean to solve Eq. (2)?\n\n**We mean to verify if the equation holds**. We will clarify this in the revision.\n\n&nbsp;\n### 5. Optimization from a stationary point rather than random initialization\n\nThis is an intriguing idea! **It is not obvious to us how to arrive at valid bounds**, because the optimization recursively depends on the intermediate parameter values through the gradient descent steps (i.e., $\\theta_i$ depends on $\\theta_{i-1..0}$. But this could be an interesting idea to explore for future work.\n\n&nbsp;\n### 6. Certified post-training for prediction head\n\nThis is a great suggestion. Indeed, **certifying only the final prediction layer of a larger pre-trained model can substantially reduce complexity** and allow certified training of larger models. Inspired by your comment, **we are currently exploring experiments** in this direction, and will discuss this promising alternative in the revised manuscript. \nPreliminary **results are very promising**. We trained the same model as in Table 1 with $\\epsilon$=0.01 on TwoMoons; once with normal, end-to end training, and once with a pretraining + finetuning setup. For the pretraining, we train on only 4 clean data points without perturbations. We then freeze all parameters except the last prediction head and continue training on the entire dataset with perturbation. \n| Training                  | Epochs       | Epoch Time                        | Total Time | Certified Accuracy |\n|--------------------------|--------------|-----------------------------------|------------|---------------------|\n| Full training            | 1            | 4.5 s                            | 4.5 s     | 80%                |\n| Pretraining + Finetuning | 2 pre + 1    | 0.35 s (pre), 0.7 s (fine)      | 1.4 s     | 81%                |\n\nUsing this setup, we can also train larger models with at least 5 layers at the same width, which were previously out of reach. We believe this is a very promising direction and will include the results of our findings in the paper.\n\n&nbsp;\n### 7. What is the number of branches?\n\nThe number of branches refers to **the potential decisions a solver must explore in branch-and-bound methods** that are commonly used to solve MIBPs. Each binary variable creates two branches (one for each possible value). Although, theoretically, this could yield up to $2^n$ branches, in practice, solver optimizations and heuristics significantly reduce this number. To improve clarity, we will explicitly define this term and include a brief explanation in the revised paper.\n\n&nbsp;\n\nOnce again, thank you for your valuable insights and suggestions, which we will incorporate in the revision of our paper."}, {"review_id": "AZSF5GrD3W", "reviewer": "Reviewer_roE8", "summary": "This paper investigates the robustness verification of a neural network under potential data poisoning threats. The problem studied is essential. The authors proposes MIBP-Cert to provide robustness certificates. The paper is well-written and easy to follow. Please find detailed comments below.", "questions": "1. It is not clear why it is paramount to focus on ReLU MLPs. \n2. The proposed method requires breaking down the NN into its trainable parameters and values for each neuron. It is unclear what would hinder scalability, depth, the number of neurons, or dimensionality. If time allows, the audience may benefit from adding a group of experiments to analyze the impact of these factors.  \n3. The authors claim the proposed method derives tighter bounds compared to bound-based methods. Does this claim still hold when the network gets deeper? If so, it would benefit the practical impact to make a comparison group to illustrate this trend. \n4. Table 4 shows low certified accuracy. How does it compare to other approaches? Is this result showing the limitation of the proposed method? If so, please discuss potential countermeasures.", "limitations": "The primary limitation of the proposed method lies in its scalability. A more comprehensive experimental and analytical evaluation is needed to better assess how factors impact performance and runtime.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strength\n1. The authors provide a comprehensive comparison in Section 2, using Table 1 to highlight the advantages of the proposed approach. \n2. This paper is well-organized and well-written. Section 3 contains an illustrative example, making it easy to follow. Sections 3.2 and 3.3 present the proposed method in a clear and organized manner. \n\n### Weakness\n1. The proposed approach is limited to ReLU MLPs and does not apply to MLPs with other popular activation functions, such as sigmoid and tanh. \n2. Potential scalability issue. Experiments focus on small MLPs (2 layers, 20 neurons per layer). The runtime of the optimization problem relies on the number of parameters that can grow exponentially with the size of the network.  \n3. Experiments show marginal improvement compared to existing works. Table 3 shows promising trends, but Table 3.b only indicates that the proposed approach has yielded a marginal improvement. Table 4 shows low certified accuracy. Table 5 shows the runtime but does not provide a baseline for comparison.", "was_revised": true, "final_justification": "The authors have addressed my concern. However, given the scalability limitations of the proposed approach, I have decided to maintain my current score.", "rebuttal": "Dear reviewer roE8,\n\nThank you for your positive and constructive review! We address your concerns below; please let us know if anything remains unclear.\n\n&nbsp;\n### 1. Why do you focus on ReLU activations instead of other choices such as sigmoid or tanh?\n\nReLUs are among the most popular activation functions due to their efficiency and simplicity. Their piecewise-linear structure is ideal for precise certification, making them the preferred choice in most certification literature. **Solving the problem for ReLU is therefore the first step to piecewise linear bounding of general activation functions**. However, **our method supports other non-linear activations** (e.g., sigmoid, tanh) using piecewise-linear upper and lower bounds. For instance, in the range [0, 1]:\n\nSigmoid: $ 0.25x + 0.48 \\leq \\sigma(x) \\leq 0.25x + 0.5$\n\nTanh: $0.76x \\leq \\tanh(x) \\leq x$\n\nThank you for this suggestion! We will explicitly discuss these extensions in our revision.\n\n&nbsp;\n### 2.  Factors Affecting Scalability\n\nTheoretically, our complexity analysis in section 5.3 shows that the complexity bound is $O(2^{(n + k)b} \\cdot 2p)$, meaning **the dominant factors are the number of activations $n$ and the number of classes $k$**. Therefore, worst-case scalability depends on these two values.\nTo analyze real-world behaviour we run ablation studies on the model width and depth, which both influence the number of parameters and activations. We use the same models and data as in Table 1 with $\\epsilon=0.01$, training for 1 epoch with varying network width and depth.\n\n| layers x width | total parameters | Training time |\n|---|---|---|\n| 2 x 5 | 27 | 0.75s |\n| 2 x 10 | 52 | 1.24s |\n| 2 x 20 | 102 | 4.79s |\n| 2 x 30 | 152 | 27.7s |\n\n| layers x width | total parameters | Training time |\n|---|---|---|\n| 2 x 5 | 27 | 0.75s |\n| 3 x 5 | 57 | 2.37s |\n| 4 x 5 | 87 | 6.24s |\n| 5 x 5 | 117 | 12.9s |\n| 6 x 5 | 147 | 22.1s |\n\nThe numbers show that **training time corresponds roughly to the number of parameters**.\n\n&nbsp;\n### 3. Are the bounds still tighter for deep networks?\n\nYes, **our approach yields tighter bounds than previous methods for models of any size**, and this advantage grows with network depth. In deeper models, approximation errors from previous layers compound significantly, thus increasing the relative benefit of our tighter bound formulation. We will add this discussion and an experimental ablation to the revision.\n\n&nbsp;\n### 4. Table 4 shows low certified accuracy. How does it compare to other approaches?\n\nTable 4 does **not** show low accuracy, but **our method's ability to model complex preconditions** that other methods cannot represent (complex perturbations in Table 1). The first line (“Assuming accurate health data”) shows the baseline accuracy without any perturbations or bounds, which is 56.4%, whereas the following lines show the worst-case impact of different data corruptions using our method. Missing mental health values have no measurable impact (same worst-case accuracy as the baseline), while the missing (unreported) values of all features could impact model performance by 2.8 percentage points (pp). Mental health over-reporting could be responsible for a 5.6pp drop in model accuracy.\n\n&nbsp;\n### 5. Scalability limitations and potential for larger models\n\nThis is **the first work that provides stable bounds for model training**, introducing a novel Mixed Integer Bilinear Programming formulation. We acknowledge that the scalability of our prototype implementation using an off-the-shelf solver is currently the main limitation, but demonstrate that it can be applied to a range of safety-, security-, or privacy-critical problems used in practice. We expect that follow-up work can improve on the scalability of our prototype implementation, similarly to how test-time certification methods have improved substantially over early, expensive methods that were limited to small model sizes as well. Potentially impactful directions include:\n\n- Hybrid methods combining our tight bounds selectively with faster approximations elsewhere\n- Exploiting model sparsity and structural properties for faster optimization\n- Exploring low-level engineering efficiency gains through optimized and/or parallelized implementations\n- Improvements in how to guide optimizer heuristics by exploiting domain/problem knowledge\n\nWe will include this discussion in the revision.\n\n&nbsp;\n### 6. Marginal Improvements and Baseline Comparisons\n\nBoth Table 2 and Tables 3a-c show **consistent improvement in certified accuracy compared to the baselines**. This is especially noticeable for larger perturbation sizes, where **improvements are more than 11 percentage points (pp) on average, up to 20 pp** (10 pp (Table 2), 20pp (Table 3a), 4pp (Table 3b), 13pp (Table 3c)). These are meaningful improvements in the more challenging large perturbation bound settings.\n\nFurthermore, as Table 1 and Section 5.2 demonstrate, our method **uniquely certifies perturbation types that were previously impossible**. We will make this qualitative advantage even more explicit in the revised manuscript.\n\n&nbsp;\n\nThank you again for your helpful feedback! We will incorporate it in the revision of our paper, which will significantly strengthen the submission."}, {"review_id": "ANGCWMLgac", "reviewer": "Reviewer_mYxi", "summary": "The paper introduces a mixed-integer bilinear programming formulation to train ReLU networks with provable robustness. The idea is to compute a reachable set of network parameters by propagating constraints through the network. The experimental results show a slight improvement on toy networks and datasets.", "questions": "In general, I would suggest to evaluate possible adaptation of branch & bound to the actual problem formulation to speed up the \n- Would it be possible to extend the discussion to other neural network architectures (convolutions, normalization, etc..)? \n- Would it be possible to extend the evaluation to MNIST & CIFAR10 datasets.\n- Please report also timing of FullCert and MIBP-Cert", "limitations": "The limitations have been discussed in section 6.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 1, "strengths_and_weaknesses": "### Strengths\n- The idea is clear and properly explained\n- The formulation is comprehensive and produces tight bounds\n- The problem is relevant and important for safety critical applications\n\n### Weaknesses\n- The mixed-integer bilinear optimization formulation has only been investigated for ReLU fully connected networks.\n- Scalability is a major concern. Despite optimized bound propagation, the resulting formulation becomes intractable even for networks of modest size. Timing have not been reported\n- Experimental results have been only evaluated on toy data.", "was_revised": true, "final_justification": "While the proposed method shows some promise in robustness certification, the improvements are too incremental to justify publication. In my opinion, the gains do not sufficiently advance the field.", "rebuttal": "Dear Reviewer mYxi,\n\nThank you for taking the time to review our paper! We are glad that you found it relevant, comprehensive, and clearly explained. We address your questions and concerns below.\n\n&nbsp;\n### 1. Adaptation of branch & bound algorithms\n\nThank you for the suggestion! We agree that the off-the-shelf optimizer, while generally efficient, can potentially be optimized by developing tailored algorithmic schemas that exploit the specific program structure. **The goal of this work is to show that stable certified training is possible** using our novel Mixed Integer Bilinear Programming formulation. Our prototype implementation demonstrates that it can be applied to a range of safety-, security-, or privacy-critical problems. We expect that follow-up work can improve on the scalability of our implementation, similarly to how test-time certification methods have improved substantially over early, expensive methods that were limited to small model sizes as well. Potentially impactful directions include:\n\n- Exploiting model sparsity and structural properties for faster optimization\n- Hybrid methods combining our tight bounds selectively with faster approximations elsewhere\n- Exploring low-level engineering efficiency gains through optimized and/or parallelized implementations\n- Improvements in how to guide optimizer heuristics by exploiting domain/problem knowledge\n\nWe will include this discussion in the revision.\n\n&nbsp;\n### 2. Can you extend the discussion to other network architectures?\n\nYes. We follow prior work on certification and focus on fully connected models with ReLU MLPs, as this is a very general architecture and well-suited for certification. **Solving the problem for ReLU is therefore the first step to piecewise linear bounding of general activation functions**. However, **our method is more general and can support other architectures, which we are happy to include and discuss in the revision.**\n\n**Convolution** layers are linear operations and can be encoded as linear constraints. Given an input tensor $X \\in \\mathbb{R}^{C_{\\text{in}} \\times H \\times W}$ and a kernel $K \\in \\mathbb{R}^{C_{\\text{out}} \\times C_{\\text{in}} \\times k_H \\times k_W}$, the convolution output $Y \\in \\mathbb{R}^{C_{\\text{out}} \\times H’ \\times W’}$ is defined by:\n\n$$Y_{c, i, j} = \\sum_{c'=1}^{C_{\\text{in}}} \\sum_{m=1}^{k_H} \\sum_{n=1}^{k_W} K_{c, c', m, n} \\cdot X_{c', i+m-1, j+n-1} + b_c$$\n\nThis operation is equivalent to a sparse affine transformation and can be flattened into a set of linear constraints $Y = AX + b$, where $A$ encodes the convolution as a sparse matrix multiplication and $b$ is the bias. These constraints can be directly integrated into our MILP formulation, exactly like fully connected layers.\n\n**Our method also supports other non-linear activations (e.g., sigmoid, tanh)** using piecewise-linear upper and lower bounds. For instance, in the range [0, 1]:\n\nSigmoid: $ 0.25x + 0.48 \\leq \\sigma(x) \\leq 0.25x + 0.5$\n\nTanh: $0.76x \\leq \\tanh(x) \\leq x$\n\nThank you for this suggestion! We will explicitly discuss these extensions in our revision. \n\n&nbsp;\n### 3. Would it be possible to extend the evaluation to MNIST & CIFAR10 datasets.\n\nWe thank the reviewer for this suggestion. While evaluation on MNIST and CIFAR-10 would indeed be valuable, **these benchmarks currently exceed the scalability** of our precise certification approach. Instead, we intentionally **focus on lower-dimensional datasets in safety- or security-critical domains**, which offer more **realistic and directly relevant application scenarios** for our method. Our first results on the suggestion by reviewer 4X7Z to restrict certified training to only the classification head look promising towards scaling to more complex models.\n\n&nbsp;\n### 4. Please report also timing of FullCert and MIBP-Cert\n\nThank you for this suggestion, we agree that a runtime comparison makes sense to illustrate the trade-offs involved. To address this, **we report the average runtime per epoch on the Two-Moons dataset**, in the same setting as Table 1. The detailed runtime of our method across epochs and perturbation radii is provided in Appendix C of our manuscript. FullCert and Sosnin et al. in pure IBP mode both take ~0.014s per epoch. IBP+CROWN mode (the default for TwoMoons) takes ~0.04s per epoch, and ~0.05s per epoch for CROWN. This is relatively consistent across different perturbation radii ($\\epsilon$) and epochs. We report the average runtime for the first 5 epochs in the table below. Models typically either converge or diverge after 5 epochs.\n\n| Method | Time ($\\epsilon=0.0001$) | CA ($\\epsilon=0.0001$) | Time ($\\epsilon=0.001$) | CA ($\\epsilon=0.001$) | Time ($\\epsilon=0.01$) | CA ($\\epsilon=0.01$) |\n|---|---|---|---|---|---|---|\n| FullCert | 0.01s |83.9%|0.01s |82.2%|0.01s |71.5%|\n| Sosnin et al.| 0.04s |83.8%|0.04s |82.3%|0.03s |69.0%|\n| MIBP-Cert | 19s |83.3%|54s |82.0%|156s  |81.4%|\n\nWhile our method is slower, especially for larger $\\epsilon$, it delivers significantly improved certified accuracy and training stability, validating our theoretical analysis regarding the runtime-precision trade-off. Furthermore, as Table 1 and Section 5.2 demonstrate, our method **uniquely certifies perturbation types that were previously impossible**. We will include an expanded runtime comparison in Section 5.3.\n\n&nbsp;\n\nThank you again for your valuable feedback. We will incorporate it into our revised paper, which will significantly strengthen the submission."}, {"review_id": "HKYcfzWH9P", "reviewer": "Reviewer_VCxT", "summary": "This work proposes a certified training method against data perturbations via mixed integer bilinear (MIBP) programs. At each training step, the authors formulate the gradient descent process as an MIBP problem and solve it using Gurobi. It allows them to bound the range of the updated model parameters the when the training examples are perturbed. By iteratively applying this process for all steps, the authors can obtain the range of the final model parameters, which is served as a certification.", "questions": "1. What is the running time for your method and previous methods?\n2. How does the running time of your method scale as the model size increases?", "limitations": "Yes.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n1. This paper is well-written and easy to follow. The proposed example is clear and helpful.\n2. The proposed MIBP-Cert method shows tighter bound than previous methods, particularly under large perturbations.\n\nWeaknesses\n1. The proposed method exhibits higher time complexity than previous approaches. Moreover, as the neural network scales, the number of constraints in the MIBP formulation grows, making it impractical for more complex architectures.\n2. There is no running time comparison with previous methods.\n3. The model is a 2-layer MLP, which is too simple.", "was_revised": true, "final_justification": "The authors have addressed my concern. However, given the time complexity of the proposed approach, I have decided to maintain my current score.", "rebuttal": "Dear Reviewer VCxT,\n\nThank you for taking the time to review our paper! We are encouraged that you found it easy to follow and appreciate the more precise bounds of our approach. We address your questions and concerts below.\n\n&nbsp;\n### 1. What is the running time for your method and previous methods?\n\nThank you for this suggestion, we agree that a runtime comparison makes sense to illustrate the trade-offs involved. To address this, **we report the average runtime per epoch on the Two-Moons dataset**, in the same setting as Table 1. The detailed runtime of our method across epochs and perturbation radii is provided in Appendix C of our manuscript. FullCert and Sosnin et al. in pure IBP mode both take ~0.014s per epoch. IBP+CROWN mode (the default for TwoMoons) takes ~0.04s per epoch, and ~0.05s per epoch for CROWN. This is relatively consistent across different perturbation radii ($\\epsilon$) and epochs. We report the average runtime for the first 5 epochs in the table below. Models typically either converge or diverge after 5 epochs.\n\n| Method | Time ($\\epsilon=0.0001$) | CA ($\\epsilon=0.0001$) | Time ($\\epsilon=0.001$) | CA ($\\epsilon=0.001$) | Time ($\\epsilon=0.01$) | CA ($\\epsilon=0.01$) |\n|---|---|---|---|---|---|---|\n| FullCert | 0.01s |83.9%|0.01s |82.2%|0.01s |71.5%|\n| Sosnin et al.| 0.04s |83.8%|0.04s |82.3%|0.03s |69.0%|\n| MIBP-Cert | 19s |83.3%|54s |82.0%|156s |81.4%|\n\nWhile our method is slower, especially for larger $\\epsilon$, it delivers significantly improved certified accuracy and training stability, validating our theoretical analysis regarding the runtime-precision trade-off. Furthermore, as Table 1 and Section 5.2 demonstrate, our method **uniquely certifies perturbation types that were previously impossible**. We will include an expanded runtime comparison in Section 5.3.\n\n&nbsp;\n### 2. How does the running time scale as the model size increases?\n\nOur complexity analysis in section 5.3 shows that the complexity bound is $O(2^{(n + k)b} \\cdot 2p)$, meaning **the dominant factors are the number of activations $n$ and the number of classes $k$**. Therefore, scalability depends on these two values.\n\nTo analyze real-world behaviour we run ablation studies on the model width and depth, which both influence the number of parameters and activations. We use the same models and data as in Table 1 with $\\epsilon=0.01$, training for 1 epoch with varying network width and depth.\n\n| layers x width | total parameters | Training time |\n|---|---|---|\n| 2 x 5 | 27 | 0.75s |\n| 2 x 10 | 52 | 1.24s |\n| 2 x 20 | 102 | 4.79s |\n| 2 x 30 | 152 | 27.7s |\n\n| layers x width | total parameters | Training time |\n|---|---|---|\n| 2 x 5 | 27 | 0.75s |\n| 3 x 5 | 57 | 2.37s |\n| 4 x 5 | 87 | 6.24s |\n| 5 x 5 | 117 | 12.9s |\n| 6 x 5 | 147 | 22.1s |\n\nThe numbers show that **training time corresponds roughly to the number of parameters**.\n\n&nbsp;\n### 3. The model is a 2-layer MLP, which is too simple.\n\nWe agree that **larger models would indeed be desirable**. Nevertheless, we demonstrate that smaller architectures are being **applied in safety-, security-, or privacy-critical scenarios**, where verifiable guarantees are crucial and worth the trade-offs. We expect that follow-up work can improve on scalability by building on our prototype solution to develop tailored algorithmic schemas that are amenable to parallelization and optimization, similarly to how test-time certification methods have improved substantially over early, expensive methods that were limited to small model sizes as well. For example, **our results on the suggestion by reviewer 4X7Z to restrict certified training to only the classification head look promising** towards scaling to more complex models.\n\n&nbsp;\n### 4. Higher time complexity compared to previous approaches.\n\nYes. The more precise bounds of our method are an intentional design decision of our method, which **mitigates convergence issues** inherent in prior work, as shown in Section 4. Since **there is no free lunch in optimization** [a], this necessitates a higher theoretical complexity bound. However, as mentioned before, we expect that follow-up work can improve the scalability of our prototype implementation to develop tailored algorithmic schemas that are amenable to parallelization and optimization. Potentially impactful directions include:\n- Hybrid methods combining our tight bounds selectively with faster approximations elsewhere\n- Exploiting model sparsity and structural properties for faster optimization\n- Exploring low-level engineering efficiency gains through optimized implementations\n- Improvements in how to guide optimizer heuristics by exploiting domain/problem knowledge\n\nWe will include this discussion in the revision.\n\n&nbsp;\n\nThank you again for your valuable feedback, which helps to significantly strengthen the revision of our paper."}]

Author rebuttal:

Meta-review: The paper aims to provide certification for training time data perturbations. The high-level insight is to compute a reachable set (bounds) of network parameters during training, and this set can be formulated and solved as a mixed integer bilinear program. During inference, these bounds are used to provide a prediction with certified guarantees, i.e., the prediction is guaranteed to be correct even in the presence of bounded training time data perturbations. Experiments were conducted mostly on small datasets and ReLU models, since solving MIBPs (using Gurobi) is quite expensive and restricted to ReLU only.

The AC believes the main contribution of the paper is its novel angle and formulation to tackle this problem. The scalability of MIBP is quite limited; however, as the first step in this direction, I believe this paper is worthy of publication, and the tight bounds provided by MIBP can serve as a baseline for future development of faster and relaxed methods. As future work, I encourage the authors to look into the recent progress of the neural network verification literature (check out approaches in VNN-COMP reports), where mixed integer programming has been replaced by more efficient methods such as bound propagation (not IBP), and achieve significantly better scalability. Additionally, there have been extensions of neural network verification beyond ReLU networks.
Decision: Accept (poster)