🤖 machine learning

Rethinking Evaluation Paradigms in IBP-based Certified Training

This paper proposes a new evaluation paradigm for IBP-based certified training that utilizes automated multi-objective hyperparameter optimization to construct Pareto fronts of natural versus certified accuracy, thereby revealing significant undertuning in prior work and enabling fair, unbiased comparisons that establish a new state of the art.

Original authors: Konstantin Kaulen, Hadar Shavit, Holger H. Hoos

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Konstantin Kaulen, Hadar Shavit, Holger H. Hoos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Safety vs. Speed" Dilemma

Imagine you are training a robot to drive a car. You want two things:

Natural Accuracy: The robot drives perfectly on normal, sunny days.
Certified Robustness: The robot is mathematically guaranteed not to crash if a tiny, weird glitch happens (like a sticker on a stop sign that confuses the camera).

The problem is that these two goals usually fight each other. If you make the robot super-safe against glitches, it might become clumsy on normal days. If you make it a great driver on normal days, it might be easily tricked by glitches.

For years, researchers have been trying to find the "perfect" robot that balances these two. But the way they have been testing their robots has been flawed.

The Problem: Judging a Book by One Page

Until now, researchers would tune their robot's settings to find one single "best" setting. They would pick a specific balance between safety and speed, report those numbers, and say, "Look, our robot is the best!"

The authors of this paper argue this is like judging a restaurant by only ordering one dish. Maybe the restaurant is amazing at steaks but terrible at pasta. If you only order the steak, you think they are the best restaurant in town. But if you tried the pasta, you might realize they aren't that great.

In the world of AI, researchers were picking just one point on the "safety vs. speed" spectrum. This meant they were missing the full picture. Some methods might be great at safety but bad at speed, while others are the opposite. By only looking at one point, the scientific community was getting a misleading view of who was actually the best.

The Solution: The "Pareto Frontier" Map

The authors propose a new way to evaluate these robots. Instead of looking for one "best" setting, they map out the entire range of possibilities.

Imagine a map where the X-axis is "Driving Skill" (Natural Accuracy) and the Y-axis is "Crash-Proofing" (Certified Accuracy).

Some robots are high on driving skill but low on crash-proofing.
Some are high on crash-proofing but low on driving skill.
Some are in the middle.

The authors use a special computer algorithm to find the edge of the map (called the Pareto Front). This edge represents the best possible trade-offs. If a robot is on this edge, you cannot improve its driving skill without making it less crash-proof, and vice versa.

By comparing the entire edge of different robots, rather than just one point, they can see who is truly superior.

What They Found: The "Hidden Gems"

When the authors applied this new map-making technique to existing AI methods, they discovered two major things:

1. Previous "Winners" Were Under-Tuned
Many of the methods that were previously considered the "state of the art" were actually just poorly tuned. The researchers found that if you adjust the settings correctly (using their new map), these older methods perform much better than anyone realized.

Analogy: It's like finding out that a car everyone thought was slow was actually capable of going 100 mph, but the previous owner had the gas pedal taped down. Once they untaped it, the car was a rocket.

2. There Is No Single "Best" Robot
The study showed that there isn't one single method that wins at everything.

Method A (SABR) is like a sports car: It's fantastic at driving fast and smooth (high natural accuracy) but offers decent, though not perfect, crash protection.
Method B (MTL-IBP) is like a tank: It's slightly slower on the open road, but it offers the strongest, mathematically guaranteed crash protection.
Conclusion: Depending on what you need (a fast car or a tank), you should pick a different method. They are complementary, not competitors.

The Cost of Truth

The authors admit that making this new map is expensive. It requires a lot of computer power to test thousands of different settings for every robot.

Analogy: To find the best route for a road trip, you could just guess one path. Or, you could use a super-computer to simulate every possible route, traffic condition, and weather scenario. The second way takes more time and electricity, but it guarantees you find the true best route, not just a lucky guess.

The Takeaway

This paper doesn't invent a new robot; it invents a better ruler.

It tells the scientific community: "Stop picking one random setting and claiming victory. Map out the whole trade-off curve. When you do, you'll see that many of our old champions were just under-prepared, and the real winners depend entirely on what you value most: speed or safety."

By using this new, fairer way of measuring, the paper establishes a new standard for how AI safety should be tested in the future.

Technical Summary: Rethinking Evaluation Paradigms in IBP-based Certified Training

Problem Statement

Deep neural networks (DNNs) achieve high performance on supervised learning tasks but remain vulnerable to adversarial perturbations. While neural network verification provides mathematically rigorous robustness guarantees, it is computationally expensive (NP-complete). Certified training techniques, particularly those based on Interval Bound Propagation (IBP), aim to optimize for verifiable robustness during training. However, these methods induce a fundamental trade-off between natural accuracy (performance on clean data) and certified accuracy (performance on provably robust inputs).

The current evaluation paradigm in the field is flawed: researchers typically report a single configuration (a single point in the trade-off space) determined by manual tuning or grid search. This practice is problematic because:

Bias: Comparing single configurations is highly dependent on the specific trade-off point chosen, leading to biased conclusions about the state of the art.
Under-tuning: Prior works often fail to explore the full hyperparameter space, potentially missing superior configurations that dominate reported results.
Lack of Standardization: There is no unbiased, standardized procedure to position new methods against existing ones across the entire robustness-accuracy spectrum.

Methodology

The authors propose a paradigm shift from single-point evaluation to Pareto-front-based evaluation. Instead of optimizing for a single objective (e.g., maximizing certified accuracy), they treat the problem as a multi-objective optimization task to discover the set of non-dominated configurations (the Pareto front).

Core Approach

Multi-Objective Hyperparameter Optimization (MO-HPO): The authors employ multi-objective Bayesian optimization using Gaussian process surrogates and the Expected Hypervolume Improvement (EHVI) acquisition function. This allows for the simultaneous optimization of natural accuracy and certified accuracy.
Search Space Design: To ensure an unbiased comparison, the search space is comprehensive, including:
- General deep learning hyperparameters (learning rate, optimizers like Adam/AdamW/RAdam, decay schedules).
- Method-specific trade-off parameters (e.g., $\kappa$ for IBP/CROWN-IBP, $\alpha$ for MTL-IBP, $\tau$ for SABR).
- Training schedule parameters (warm-up epochs, ramp-up epochs, $\epsilon$ scaling factors).
- Attack parameters (PGD steps, step size, restarts).
- Crucially, the search space includes parameters often fixed or ignored in prior literature (e.g., allowing $\kappa$ transitions, varying warm-up lengths), enabling the discovery of previously unexplored configurations.
Efficient Evaluation Proxy: Since complete verification (required for final certified accuracy) is computationally prohibitive for every trial, the optimization loop uses incomplete verification (IBP, CROWN, CROWN-IBP) as a proxy objective.
Final Verification: Once the Pareto-optimal configurations are identified via the proxy, they are re-evaluated using state-of-the-art complete verification (specifically $\alpha\beta$ -CROWN) to establish the final Pareto front. To manage costs, single-linkage clustering is used to filter redundant configurations before complete verification.
Standardized Budget: All methods are evaluated under a fixed computational budget (100 trials per seed, 3 seeds per method) to ensure fair comparison.

Key Contributions

New Evaluation Standard: The paper establishes a standardized, multi-objective evaluation protocol that replaces single-point comparisons with Pareto-front analysis. This allows for a nuanced assessment where researchers can select methods based on their specific requirements (e.g., prioritizing clean accuracy vs. certified guarantees).
Discovery of Under-tuned Configurations: By systematically exploring the hyperparameter space, the authors demonstrate that many previously reported "state-of-the-art" results are Pareto-dominated by configurations found through their automated optimization. This reveals significant "undertuning" in existing literature.
Comprehensive Benchmarking: The study provides the first comprehensive multi-objective comparison of major IBP-based certified training methods (IBP, CROWN-IBP, SABR, MTL-IBP) across CIFAR-10 and Tiny ImageNet with varying perturbation radii ( $\epsilon$ ).
Hyperparameter Insights: Using fANOVA, the authors identify that complex interactions between hyperparameters (e.g., the transition of $\kappa$ during ramp-up, $\epsilon$ scaling, and warm-up duration) are critical for achieving optimal trade-offs, insights often missed by manual tuning.

Results

Superior Performance: The proposed evaluation uncovers configurations that dominate prior results. For instance, on CIFAR-10 with $\epsilon = 2/255$ , SABR achieves gains of over 1% in both clean and certified accuracy compared to literature. On Tiny ImageNet, MTL-IBP shows improvements of ~2% in both metrics.
Method Complementarity: No single method uniformly dominates.
- SABR generally excels at achieving high natural accuracy.
- MTL-IBP tends to provide the strongest certified guarantees, particularly at smaller perturbation radii.
- IBP and CROWN-IBP remain competitive, especially when higher natural accuracies are desired or at larger perturbation radii ( $\epsilon = 8/255$ ), challenging the assumption that they are obsolete.
Stalled Progress at Large Radii: The analysis suggests that progress at larger perturbation radii has stalled, with older methods contributing significantly to the combined Pareto front.
Validation vs. Test Set Tuning: The authors demonstrate that tuning hyperparameters directly on the test set (a common but problematic practice) leads to Pareto fronts that strictly dominate those obtained via validation set tuning, indicating that prior evaluations likely overestimated generalization performance.
Computational Efficiency: The study shows that while full verification is expensive, reducing the verification timeout (e.g., from 1000s to 100s on CIFAR-10) preserves the shape of the Pareto front while reducing computational costs by an order of magnitude.

Significance and Claims

The paper claims that the current state of the art in certified training has been significantly underestimated due to poor hyperparameter tuning and flawed evaluation methodologies. By adopting a multi-objective perspective:

Reassessment of State of the Art: Recent advancements are less pronounced than previously assumed, particularly for larger perturbation radii.
Actionable Insights: The work provides concrete guidance for the community, highlighting that complex interactions between hyperparameters (often overlooked) are essential for optimal performance.
Future Direction: The authors advocate for a shift toward standardized multi-objective evaluation protocols. They suggest that the community should focus on "cheap verification" strategies rather than relying on increasingly large verification timeouts to distinguish methods, as smaller timeouts are often sufficient to identify the Pareto front.

Ultimately, the paper argues that fair evaluation requires exploring the full trade-off space, enabling the development of certified models that are both robust and practically useful, while preventing misleading conclusions drawn from single-configuration comparisons.