← All papers
First page of Understanding Certified Training with Interval Bound Propagation

Understanding Certified Training with Interval Bound Propagation

Yuhao Mao, Mark Niklas Müller, Marc Fischer, Martin Vechev

cs.LG Jun 17, 2023 · v4 cs.AI
All theoretical results and proofs on IBP bound tightness are formalized in Lean with the Paper Formalizer tool, and the artifact is released on GitHub.
As robustness verification methods are becoming more precise, training certifiably robust neural networks is becoming ever more relevant. To this end, certified training methods compute and then optimize an upper bound on the worst-case loss over a robustness specification. Curiously, training methods based on the imprecise interval bound propagation (IBP) consistently outperform those leveraging more precise bounding methods. Still, we lack an understanding of the mechanisms making IBP so successful. In this work, we thoroughly investigate these mechanisms by leveraging a novel metric measuring the tightness of IBP bounds. We first show theoretically that, for deep linear models, tightness decreases with width and depth at initialization, but improves with IBP training, given sufficient network width. We, then, derive sufficient and necessary conditions on weight matrices for IBP bounds to become exact and demonstrate that these impose strong regularization, explaining the empirically observed trade-off between robustness and accuracy in certified training. Our extensive experimental evaluation validates our theoretical predictions for ReLU networks, including that wider networks improve performance, yielding state-of-the-art results. Interestingly, we observe that while all IBP-based training methods lead to high tightness, this is neither sufficient nor necessary to achieve high certifiable robustness. This hints at the existence of new training methods that do not induce the strong regularization required for tight IBP bounds, leading to improved robustness and standard accuracy.

Certified training methods based on imprecise interval bound propagation (IBP) consistently outperform methods that use more precise bounds, and the reasons for this are not understood.

The authors introduce propagation tightness, a metric comparing IBP bounds to optimal box bounds. They derive necessary and sufficient conditions on weight matrices for IBP bounds to be exact. They analyze how tightness depends on width and depth in deep linear networks at initialization and under IBP training, and then test these predictions on ReLU networks. The theoretical results and proofs are formalized in Lean.

For deep linear networks, tightness decreases with width and depth at initialization and improves under IBP training given sufficient width. Exact IBP bounds impose strong regularization. Wider networks improve state-of-the-art certified accuracy on MNIST, CIFAR-10 and TinyImageNet, and high tightness is neither necessary nor sufficient for high certified robustness.

MethodWidthAccuracyCertified
IBP1×67.9355.85
IBP2×68.0656.18
SABR1×79.2462.84
SABR2×79.8963.28
Certified and standard accuracy vs. width (CIFAR-10, ε=2/255)