MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs

Dear Reviewer VCxT,

Thank 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.

 

1. What is the running time for your method and previous methods?

Thank 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.

While 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.

 

2. How does the running time scale as the model size increases?

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, scalability depends on these two values.

To 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.

The numbers show that training time corresponds roughly to the number of parameters.

 

3. The model is a 2-layer MLP, which is too simple.

We 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.

 

4. Higher time complexity compared to previous approaches.

Yes. 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:

• 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 implementations
• Improvements in how to guide optimizer heuristics by exploiting domain/problem knowledge

We will include this discussion in the revision.

 

Thank you again for your valuable feedback, which helps to significantly strengthen the revision of our paper.

Dear Reviewer VCxT,

Thank you for your response to our rebuttal, we are glad that it addresses your concerns.

While we take the scalability challenge seriously, we respectfully argue that appropriate weight should be given to the problem's importance, as well as the method’s clear novelty, correctness, and demonstrated advantages over prior work.

We believe that foundational methods such as ours—which for the first time enable certified training guarantees with stable convergence and for previously uncertifiable perturbation types—represent a significant advancement in the science of robustness. Such contributions should be judged in the context of works in this area, where many impactful certification methods initially started with small models and high runtimes, and only later scaled through sustained follow-up work [a, b, c]. We view our work as a critical first step that opens up new directions for certifiably robust training.

Our current solution's high computational complexity is a known limitation, but it is clearly acknowledged, discussed, and accompanied by concrete suggestions for improvement. We are confident that our formulation and findings contribute meaningfully to the scientific foundation on which more scalable and practical approaches can be built.

Thank you for your consideration—we would be happy to discuss this further if needed.

 

[a] Katz, Guy, et al. "Reluplex: An efficient SMT solver for verifying deep neural networks." International conference on computer aided verification. Cham: Springer International Publishing, 2017.

[b] Tjeng, Vincent, Kai Y. Xiao, and Russ Tedrake. "Evaluating Robustness of Neural Networks with Mixed Integer Programming." International Conference on Learning Representations.

[c] Brix, Christopher, et al. "The fifth international verification of neural networks competition (vnn-comp 2024): Summary and results." arXiv preprint arXiv:2412.19985 (2024).

Dear reviewer roE8,

Thank you for your positive and constructive review! We address your concerns below; please let us know if anything remains unclear.

 

1. Why do you focus on ReLU activations instead of other choices such as sigmoid or tanh?

ReLUs 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]:

Sigmoid: $0.25x + 0.48 \leq \sigma(x) \leq 0.25x + 0.5$

Tanh: $0.76x \leq \tanh(x) \leq x$

Thank you for this suggestion! We will explicitly discuss these extensions in our revision.

 

2. Factors Affecting Scalability

Theoretically, 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. To 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.

The numbers show that training time corresponds roughly to the number of parameters.

 

3. Are the bounds still tighter for deep networks?

Yes, 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.

 

4. Table 4 shows low certified accuracy. How does it compare to other approaches?

Table 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.

 

5. Scalability limitations and potential for larger models

This 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:

• 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
• Improvements in how to guide optimizer heuristics by exploiting domain/problem knowledge

We will include this discussion in the revision.

 

6. Marginal Improvements and Baseline Comparisons

Both 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.

Furthermore, 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.

 

Thank you again for your helpful feedback! We will incorporate it in the revision of our paper, which will significantly strengthen the submission.

Dear Reviewer mYxi,

Thank 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.

 

1. Adaptation of branch & bound algorithms

Thank 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:

• Exploiting model sparsity and structural properties for faster optimization
• Hybrid methods combining our tight bounds selectively with faster approximations elsewhere
• Exploring low-level engineering efficiency gains through optimized and/or parallelized implementations
• Improvements in how to guide optimizer heuristics by exploiting domain/problem knowledge

We will include this discussion in the revision.

 

2. Can you extend the discussion to other network architectures?

Yes. 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.

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:

$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$

This 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.

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]:

Sigmoid: $0.25x + 0.48 \leq \sigma(x) \leq 0.25x + 0.5$

Tanh: $0.76x \leq \tanh(x) \leq x$

Thank you for this suggestion! We will explicitly discuss these extensions in our revision.

 

3. Would it be possible to extend the evaluation to MNIST & CIFAR10 datasets.

We 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.

 

4. Please report also timing of FullCert and MIBP-Cert

Thank 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.

While 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.

 

Thank you again for your valuable feedback. We will incorporate it into our revised paper, which will significantly strengthen the submission.

Dear Reviewer mYxi,

The paper has received mixed reviews, so your opinion is quite important. As the deadline for the discussion period approaches (August 8), please take a moment to read the authors' responses and reply to them at your earliest convenience. It’s important to give the authors ample time to respond, so please avoid waiting until the last minute.

If you plan to maintain your current rating of the paper, kindly respond to the authors to confirm your support or any unresolved concerns. This feedback will be very helpful to the authors.

Thank you,
AC

Dear reviewer 4X7Z,

Thank 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.

 

1. Classic adversarial vs. training-time perturbations

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.

Since 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}$: $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).$

$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.

 

2. Clarification of equations (1) and (2)

Thank 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.

 

3. Overloading of Symbol $A$

Yes, thank you for pointing this out! We will change the symbol to avoid confusion.

 

4. What does it mean to solve Eq. (2)?

We mean to verify if the equation holds. We will clarify this in the revision.

 

5. Optimization from a stationary point rather than random initialization

This 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.

 

6. Certified post-training for prediction head

This 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. Preliminary 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.

Using 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.

 

7. What is the number of branches?

The 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.

 

Once again, thank you for your valuable insights and suggestions, which we will incorporate in the revision of our paper.