Source-linked AI summary
On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, Pushmeet Kohli
TL;DR
Provable robustness methods can be difficult to optimize and scale, despite providing guarantees against norm-bounded perturbations. This paper trains verified models with IBP using a tailored loss and hyper-parameter curriculum, achieving state-of-the-art verified accuracy across several datasets and scaling beyond vacuous bounds on downscaled ImageNet.
Problem
Existing provable-robustness methods often involve difficult optimization procedures that are hard to scale, while attack-specific empirical defenses lack guarantees against other adversaries.
Method
The paper trains verifiably robust classifiers with IBP and improves it using a different loss, final-layer elision, and a curriculum over κ and ϵ.
Results
IBP achieves state-of-the-art verified accuracy for single-model architectures, improving verified error rates on MNIST and CIFAR-10 and reaching 93.87% verified error on downscaled ImageNet.
Takeaways & Limitations
Carefully tuned IBP can train large verifiably robust networks quickly while adapting models so that its initially loose bounds become tighter.
Takeaways & Limitations
Attack-based robustness evaluations cannot guarantee protection against a different adversary, such as exhaustive search, and formal verification methods have distinct scalability or tightness trade-offs.
Abstract
from arXiv · showhide
Recent work has shown that it is possible to train deep neural networks that are provably robust to norm-bounded adversarial perturbations. Most of these methods are based on minimizing an upper bound on the worst-case loss over all possible adversarial perturbations. While these techniques show promise, they often result in difficult optimization procedures that remain hard to scale to larger networks. Through a comprehensive analysis, we show how a simple bounding technique, interval bound propagation (IBP), can be exploited to train large provably robust neural networks that beat the state-of-the-art in verified accuracy. While the upper bound computed by IBP can be quite weak for general networks, we demonstrate that an appropriate loss and clever hyper-parameter schedule allow the network to adapt such that the IBP bound is tight. This results in a fast and stable learning algorithm that outperforms more sophisticated methods and achieves state-of-the-art results on MNIST, CIFAR-10 and SVHN. It also allows us to train the largest model to be verified beyond vacuous bounds on a downscaled version of ImageNet.
1. Introduction
The paper argues that empirical attack robustness does not guarantee robustness against stronger adversaries, motivating formal verification. It studies IBP as a fast approach to verified training and introduces enhancements that improve accuracy, scalability, and training stability.
- Motivation: Small adversarial perturbations can cause highly confident misclassification, while defenses tailored to specific attacks may fail against stronger adversaries.The paper uses a PGD example where exhaustive search finds a misclassification that PGD misses.
- Motivation: Formal verification provides guarantees over all inputs in a specified perturbation set, but complete methods are expensive and incomplete methods can produce loose bounds.Complete SMT and MIP approaches may require exhaustive enumeration, whereas convex relaxations trade exactness for scalability.
- Approach: IBP minimizes an upper bound on the maximum pairwise logit difference within an ℓ∞ perturbation ball, with computational cost comparable to two forward passes.This efficiency enables larger models, larger batches, and more extensive hyper-parameter search.
- Approach: The method enhances IBP with a different loss, omission of the final linear layer, and a curriculum scheduling κ and ϵ to stabilize training and improve generalization.These choices improve worst-case logit estimates and help models adapt to IBP's relaxation.
- Results: 2.23% verified error replaces 3.67% on MNIST at ϵ = 0.12, while 8.05% replaces 19.32% at ϵ = 0.3 and 67.96% replaces 78.22% on CIFAR-10 at ϵ = 8/255.The reported comparisons show improved verified error rates over the cited baselines.
- Results: 93.87% top-1 verified error on downscaled 64 × 64 ImageNet at ϵ = 1/255 is reported for a WideResNet-10-10, beyond the vacuous 99.9% level.The result is presented as the largest model verified beyond vacuous bounds.
2. Related Work
Related work includes empirical strategies that improve solver efficiency and differentiable upper-bound methods optimized with SGD. The paper challenges the assumption that tighter relaxations are necessary, arguing that tuned IBP can make its own bounds sufficiently tight.
- Empirical approaches: Empirical approaches reduce ambiguous ReLU units so that subsequent MIP-based verification becomes more efficient.The regularizer targets units whose activation status cannot be determined by bound propagation.
- Differentiable bounds: Differentiable upper bounds on specification violations can be incorporated into losses such as hinge loss and optimized using regular SGD.Examples include semi-definite, dual, and other relaxation-based methods.
- IBP perspective: The paper reports that tighter relaxations, including dual and zonotope formulations, are not necessary to obtain tight verified bounds.This contrasts with conclusions from previous work.
- IBP perspective: IBP requires only two forward passes for bound computation, enabling significantly larger models and extensive hyperparameter tuning.The paper links this computational advantage to its ability to achieve state-of-the-art verified accuracy.
3. Methodology
The method trains classifiers for ℓ∞-bounded adversarial robustness by propagating interval bounds through each network layer and minimizing an upper bound on worst-case specification violation. It tightens and stabilizes this procedure through last-layer elision, a specification-aware loss, and scheduled training parameters.
- Verification problem: The verification objective requires the classification to remain unchanged for every input in an ℓ∞-bounded neighborhood of x0.Robustness is expressed through a specification over all perturbed inputs and can be checked by searching for a violating counter-example.
- Interval bound propagation: IBP encloses each layer’s activations in axis-aligned interval boxes, propagating bounds from x0 − ϵ1 and x0 + ϵ1 through the network.For affine layers, the bounds can be computed efficiently with two matrix multiplies; monotonic activations transform the bounds directly.
- Robustness bound: The propagated output bounds yield an upper bound on the worst-case logit difference between the true class and each alternative class.The final bound compares an alternative class’s upper logit with the true class’s lower logit.
- Bound tightening: Eliding the final linear layer with the specification produces a tighter upper bound by avoiding its additional relaxation.This design directly incorporates the last affine transformation into the verification objective.
- Training objective: The training loss mixes nominal fitting and specification satisfaction, with κ controlling their relative weight and reducing to standard classification when ϵ = 0.The loss uses cross-entropy on nominal logits and bounded logits, weighted by κ and 1 − κ.
- Training procedure: A curriculum starts with κ = 1 and ϵ = 0, then reduces κ and raises ϵ toward a training radius to stabilize optimization and improve accuracy trade-offs.The authors report that a final κ = 1/2 works across MNIST, CIFAR-10, SVHN, and ImageNet, while larger training radii can improve robustness generalization.
4. Results
IBP achieves strong verified robustness across standard benchmarks, scales to downscaled ImageNet, and produces bounds that closely track complete verification when models are trained with IBP.
- MNIST, CIFAR-10 and SVHN: IBP improves verified error rates on MNIST and CIFAR-10, setting state-of-the-art verified robustness on most dataset–radius pairs.Reported reductions include 3.67% to 2.23% on MNIST at ϵ = 0.1, 19.32% to 8.05% at ϵ = 0.3, and 78.22% to 67.96% on CIFAR-10 at ϵ = 8/255.
- MNIST, CIFAR-10 and SVHN: Across perturbation radii, IBP achieves good PGD accuracy and higher provable accuracy than Wong et al. across the evaluated model architectures.Figure 3 selects the best training radius for each model size while also displaying all individual training-radius models.
- MNIST, CIFAR-10 and SVHN: IBP combines a cross-entropy-based loss, omission of the last linear layer, and a curriculum over perturbation radii to improve verified training.Ablations report benefits from cross-entropy, omitting the last linear layer, and using the ϵ schedule.
- MNIST, CIFAR-10 and SVHN: 3.5 seconds per epoch: IBP trains the small MNIST network faster than Madry et al. at 8.5 seconds and Wong et al. at 2 minutes.Standard training takes 1.5 seconds per epoch in the same comparison; IBP adds two network passes relative to the seven PGD steps used for Madry et al.
- Tightness: IBP estimates closely match MIP/LP verified error rates for models trained with IBP, making simple verification effective on those models.The paper reports that IBP estimates are competitive with more sophisticated solvers and that verification becomes easier when models are trained to be verifiable.
5. Conclusion
The paper presents an approach for training verifiable models across four image-classification settings. Experiments report stronger verified adversarial-error bounds than competing techniques while training faster.
- The approach achieves strong baseline results on MNIST, CIFAR-10, SVHN, and downscaled IMAGENET.
- The proposed approach outperforms competing techniques on verified bounds for adversarial error rates in image classification.
- The approach also trains faster than competing techniques.
- Table 4 compares nominal test error, PGD error rate, and verified error-rate bounds against state-of-the-art methods.PGD uses 200 iterations and 10 random restarts; dashes indicate only trivial verified bounds within the time limit.
A. Training parameters
Training uses dataset-specific optimization schedules, including warm-up and perturbation-radius ramp-up. On MNIST, empirical PGD accuracy increases during training and remains stable across independent runs.
- IBP training uses Adam with an initial learning rate of 10^-3, while κ is ramped down and ϵ is ramped up during training.For CIFAR-10 and SVHN, the training radius is set 10% above the desired robustness radius.
- MNIST training runs for 100 epochs and 60K steps, with 10× learning-rate decays at steps 15K and 25K.It uses batches of 100 without data augmentation or image normalization.
- CIFAR-10 training runs for 3200 epochs and 100K steps, using batches of 1600, data augmentation, and channel normalization.The schedule uses learning-rate decays at 60K and 90K steps, with 5K warm-up and 50K ramp-up durations.
- SVHN training runs for 2200 epochs and 100K steps with batches of 50, random translations, and channel normalization.Its remaining schedule is identical to CIFAR-10.
- Downscaled IMAGENET training runs for 160 epochs and 200K steps on 64 × 64 images with random crops, flips, and channel normalization.Testing uses a central 56 × 56 crop; learning-rate decays occur at 120K and 180K steps.
- Median empirical PGD accuracy increases during training for IBP and Madry et al., with consistent results across 10 independent processes.For IBP, the effect of increasing ϵ is visible between steps 2K and 12K.
B. Convolutional filters
Robust training produces sparse first-layer convolutional filters on MNIST and CIFAR-10 compared with nominal non-robust training. IBP’s capacity limitation helps explain why larger models can be preferable, while larger models require careful ϵ scheduling.
- On MNIST, robust models produce extremely sparse first-layer filters compared with a nominal non-robust model.Wong et al. produces the sparsest filters among the methods shown.
- On CIFAR-10, robust models likewise exhibit highly sparse convolutional filters compared with the non-robust model.Madry et al. produces more meaningful filters, but they remain sparse.
- IBP strongly limits the capacity of the underlying network, making larger models often preferable.
- Larger models can cause intermediate interval bounds to explode, so ϵ must be carefully scheduled.The paper suggests combining tighter but slower relaxations with IBP during initial training of deeper and wider models.
C. Ablation study
The ablation study finds that the loss function, last-layer elision, and ϵ scheduling each materially affect verified performance. Their combination is especially beneficial for the small model.
- Without the ϵ schedule, all models fail to train and reach only 11.35% accuracy at best.
- All tested components contribute to obtaining a good final verified error rate.
- 3.88% improvement, or 12.9% relative improvement, results from adding elision with a softplus loss for the small model.
- 4.42% improvement, or 14.7% relative improvement, results from replacing softplus with cross-entropy for the small model.
- 5.15% improvement results from combining cross-entropy with elision for the small model.The improvements are less visible for larger models, which can adapt to obtain tighter bounds.
D. Additional results
Table 6 compares nominal, PGD, and verified error rates across model architectures and prior methods. Except for CIFAR-10 at ϵ = 2/255, IBP outperforms other models by a significant margin, including equivalent model sizes.
- Table 6 reports nominal test error, PGD error, and verified error rates for individual architectures and matching literature models.PGD error uses 200 iterations and 10 random restarts for models trained by the authors; verified bounds use an MIP/LP cascade.
- IBP outperforms all other models by a significant margin except on CIFAR-10 with ϵ = 2/255.The comparison holds even for equivalent model sizes.
E. Runtime
The section compares IBP's training runtime and reported evaluation settings. IBP requires substantially less training time than the compared methods in the MNIST example.
- 3.5 seconds per epoch: IBP training on the small MNIST network, versus 8.5 seconds for Madry et al. and 2 minutes for Wong et al.Standard training takes 1.5 seconds per epoch on the same Titan Xp GPU.
- Two additional network passes: IBP's training overhead compared with Madry et al.'s seven PGD training steps.The runtime comparison uses a small MNIST network and a Titan Xp GPU.
- Table 5 compares median IBP verified error bounds for training variants on MNIST with ϵ = 0.4.The bound is an upper bound on the true verified error rate and uses elision of the last layer.
- Table 6 evaluates nominal test error, PGD error, and verified error rate, with IBP PGD error measured using 200 iterations and 10 random restarts.The verified bound is computed using the MIP/LP cascade described in Section 4.
F. When Projected Gradient Descent is not enough
A MNIST example shows that PGD can miss a misclassifying perturbation found by a complete solver. The loss-landscape analysis attributes this to both boundary dynamics and unreliable gradient directions.
- F. When Projected Gradient Descent is not enough: ϵ = 0.1: PGD with 200 iterations and 10 random restarts still classifies the attack as an “eight”, while a complete MIP solver finds a misclassifying counterexample.The nominal image is the 1365th MNIST test image and is correctly classified as an “eight”; the MIP attack is classified as a “two”.
- F. When Projected Gradient Descent is not enough: Figure 9 varies the input along directions defined by the PGD and MIP perturbations, plotting perturbation magnitudes on u and v and loss on the z axis.The surface colors indicate the model's predicted classification.
- F. When Projected Gradient Descent is not enough: PGD can bounce between the edges of the projected ℓ∞ ball instead of reaching a worst-case corner unless its learning rate becomes sufficiently small.The MIP attack in this example exists only in a corner of the projected ball.
- F. When Projected Gradient Descent is not enough: Gradients cannot always be trusted to point toward the true worst-case attack.The loss landscape indicates that much of the ℓ∞ ball pushes PGD toward the right rather than the bottom.