Make Interval Bound Propagation great again

Patryk Krukowski, Daniel Wilczak, Jacek Tabor, Anna Bielawska, Przemysław SpurekSubmission to ICLR 2025 · Withdrawn

TL;DR

While Interval Bound Propagation (IBP) is widely used for neural network robustness, its certifications often fail on standard pre-trained models due to the "wrapping effect"—where interval overestimations compound exponentially layer by layer. By adapting Doubleton Arithmetic (DA) and Affine Arithmetic (AA) from rigorous numerical analysis, this paper introduces certification methods that propagate linear transformations without wrapping error and tightly bound activations like ReLU and Softmax, yielding bounds dramatically closer to the true reachable output set.

What Problem Does This Paper Address?

Neural Network Certification (NNC) guarantees that bounded input perturbations (e.g., adversarial noise $\epsilon$) cannot alter a model's prediction. IBP is a popular approach because it is fast: it pushes axis-aligned hypercubes through layers using interval arithmetic.

However, when evaluating pre-trained or standard-trained networks, IBP's bounds rapidly degrade. Because linear layer transformations rotate and shear these sets, re-enclosing the resulting geometry into axis-aligned interval boxes at every layer introduces geometric overestimation. Known in dynamical systems as the wrapping effect, this causes bounds to expand exponentially with depth, rendering verification bounds completely vacuous (e.g., output probability intervals expanding to $[0, 1]$).

Methods

The authors replace standard interval bounds with representations designed to resist the wrapping effect:

  • Doubleton Arithmetic (DA): Represents reachable sets in the form $X = \{x + Cr + Qq\}$, splitting the representation into a base point $x$, a linear propagation component $Cr$, and accumulated error $Qq$ over a transformed coordinate system. The authors extend DA to handle changing layer dimensions and non-smooth activations using QR-decomposition and pivoting strategies.
  • Affine Arithmetic (AA): Represents quantities as first-order affine forms over noise symbols in $[-1, 1]^m$. Because it tracks shared variable dependencies, linear layers are evaluated sharply with zero wrapping error.
  • Nonlinear Enclosures (ReLU & Softmax): For non-smooth ReLU activations, AA computes an optimal linear surrogate $B(t)$ and encloses the deviation using an explicit bounding parameter $\tau \approx \frac{a_0 + S}{2S}$, pushing the residual error into a newly created noise symbol. For Softmax, first-order Taylor expansions are paired with interval bounds over the second derivatives.
  • Rigorous Floating-Point Verification: Unlike Python-based prototypes vulnerable to round-off drift, the core methods are implemented in C++ using the CAPD library, guaranteeing strict mathematical enclosures under IEEE 754 floating-point rounding.

Datasets

The authors evaluate their approach on standard computer vision benchmarks:

  • MNIST ($28 \times 28$ grayscale digits)
  • CIFAR-10 ($32 \times 32$ color images)
  • SVHN (Street View House Numbers, $32 \times 32$ color images)
  • Digits ($8 \times 8$ grayscale digits from scikit-learn)

No new datasets were introduced. Experiments evaluated Small, Medium, and Large CNN architectures alongside a 4-layer MLP.

Key Insights and Ideas

  • Theoretical Proof of Exponential Blowup: The authors prove that even under purely orthogonal linear transformations (random isometries that preserve Euclidean volume and distance), IBP bounds inflate by a factor of $\approx \sqrt{\frac{2n}{\pi}}$ at every single layer. Over $k$ layers, IBP output bounds scale as $\mathcal{O}\left(\left(\sqrt{\frac{2n}{\pi}}\right)^k\right)$.
  • IBP Training Masks Architectural Flaws: Networks explicitly trained with an IBP objective adapt their weights to align principal axes with coordinate frames. When evaluated on standard-trained models or larger CNNs, standard IBP quickly collapses, whereas AA keeps bounds tight.
  • Exact Linear Mapping: Both DA and AA retain linear dependencies without wrapping error, confining bound looseness strictly to nonlinear activations.

Key Results

  • Closeness to Empirical Lower Bounds: In boundary-point tests across MNIST and CIFAR-10, AA and DA bounds track closely alongside the empirical Lower Bound (LB)—computed by densely sampling 1,000 points per perturbation neighborhood.
  • Eliminating Vacuous Outputs: For standard-trained models, IBP output intervals quickly hit maximum uncertainty (diameter 1.0) even at minor perturbation radii ($\epsilon \approx 10^{-3}$ to $10^{-2}$). AA produces meaningful, non-trivial diameter bounds across much larger perturbations.
  • Robustness Under Data Masking: When evaluating 50% randomly masked inputs on SVHN and Digits, AA maintained sharp uncertainty bounds, outperforming IBP by orders of magnitude in output interval diameter.
  • Scalability Trade-off: While DA and AA achieve nearly identical precision, AA is orders of magnitude faster than DA, making AA the practical choice for multi-layer CNNs.

Limitations and Future Work

  • Doubleton Complexity: DA requires operations with full non-sparse matrices, resulting in an $\mathcal{O}(n^3)$ computational complexity (where $n$ is the layer dimension). This made DA intractable on CIFAR-10 and SVHN CNNs under standard CPU constraints.
  • Variable Accumulation in AA: Because AA introduces an additional error symbol for every ReLU activation that crosses zero, memory footprint and runtime scale with network width and depth.
  • Certified Training: The paper focuses on post-hoc certification of pre-trained networks. Integrating AA or DA directly into the robust training loss loop remains an open challenge due to non-constant, input-dependent computation graphs.

Summary updated

Abstract

In various scenarios motivated by real life, such as medical data analysis, autonomous driving, and adversarial training, we are interested in robust deep networks. A network is robust when a relatively small perturbation of the input cannot lead to drastic changes in output (like change of class, etc.). This falls under the broader scope field of Neural Network Certification (NNC). Two crucial problems in NNC are of profound interest to the scientific community: how to calculate the robustness of a given pre-trained network and how to construct robust networks. The common approach to constructing robust networks is Interval Bound Propagation (IBP). This paper demonstrates that IBP is sub-optimal in the first case due to its susceptibility to the wrapping effect. Even for linear activation, IBP gives strongly sub-optimal bounds. Consequently, one should use strategies immune to the wrapping effect to obtain bounds close to optimal ones. We adapt two classical approaches dedicated to strict computations -- Dubleton Arithmetic and Affine Arithmetic -- to mitigate the wrapping effect in neural networks. These techniques yield precise results for networks with linear activation functions, thus resisting the wrapping effect. As a result, we achieve bounds significantly closer to the optimal level than IBPs.
BibTeX
@misc{krukowski2024make,
  author = {Patryk Krukowski and Daniel Wilczak and Jacek Tabor and Anna Bielawska and Przemysław Spurek},
  title = {{Make Interval Bound Propagation great again}},
  year = {2024},
  eprint = {2410.03373},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.03373},
}
Figure