# The Fundamental Limits of Interval Arithmetic for Neural Networks

arXiv: https://arxiv.org/abs/2112.05235 · HTML: https://mlsanity.com/paper/2112.05235/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 51 references that are in the map.
- First posted on arXiv 9 Dec 2021.

## Builds on (most cited first, 30 of 34)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [End to End Learning for Self-Driving Cars](https://mlsanity.com/paper/1604.07316/) (2016)
- [Ensemble Adversarial Training: Attacks and Defenses](https://mlsanity.com/paper/1705.07204/) (2017)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Fast is better than free: Revisiting adversarial training](https://mlsanity.com/paper/2001.03994/) (2020)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers](https://mlsanity.com/paper/2011.13824/) (2020)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Sparse and Imperceivable Adversarial Attacks](https://mlsanity.com/paper/1909.05040/) (2019)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [Wasserstein Adversarial Examples via Projected Sinkhorn Iterations](https://mlsanity.com/paper/1902.07906/) (2019)
- [Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability](https://mlsanity.com/paper/1809.03008/) (2018)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)
- [CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networks](https://mlsanity.com/paper/1811.12395/) (2018)
- [Fast Certified Robust Training with Short Warmup](https://mlsanity.com/paper/2103.17268/) (2021)
- [Provable robustness against all adversarial lp-perturbations for p≥ 1](https://mlsanity.com/paper/1905.11213/) (2019)
- [Certified Robustness to Programmable Transformations in LSTMs](https://mlsanity.com/paper/2102.07818/) (2021)
- [Interval Universal Approximation for Neural Networks](https://mlsanity.com/paper/2007.06093/) (2020)

## Built on by (most cited first, 4 of 4)

- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [Spelunking the Deep: Guaranteed Queries on General Neural Implicit Surfaces via Range Analysis](https://mlsanity.com/paper/2202.02444/) (2022)
- [Certified Robust Accuracy of Neural Networks Are Bounded due to Bayes Errors](https://mlsanity.com/paper/2405.11547/) (2024)
- [Quantization-aware Interval Bound Propagation for Training Certifiably Robust Quantized Neural Networks](https://mlsanity.com/paper/2211.16187/) (2022)

## Abstract (arXiv)

Interval analysis (or interval bound propagation, IBP) is a popular technique for verifying and training provably robust deep neural networks, a fundamental challenge in the area of reliable machine learning. However, despite substantial efforts, progress on addressing this key challenge has stagnated, calling into question whether interval arithmetic is a viable path forward. In this paper we present two fundamental results on the limitations of interval arithmetic for analyzing neural networks. Our main impossibility theorem states that for any neural network classifying just three points, there is a valid specification over these points that interval analysis can not prove. Further, in the restricted case of one-hidden-layer neural networks we show a stronger impossibility result: given any radius α < 1, there is a set of O(α-1) points with robust radius α, separated by distance 2, that no one-hidden-layer network can be proven to classify robustly via interval analysis.