mlsanityData to 14 Oct 2026

The Fundamental Limits of Interval Arithmetic for Neural Networks

arXiv 2112.05235 ↗First posted 9 Dec 2021cs.LG cs.AIcited by 4

Not on the map. Why?

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.

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

34 of 51 references.

References · 34

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2013Intriguing properties of neural networkscited by 5,155
  3. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,998
  4. 2016Adversarial examples in the physical worldcited by 1,769
  5. 2020Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attackscited by 1,451
  6. 2016End to End Learning for Self-Driving Carscited by 1,009
  7. 2017Ensemble Adversarial Training: Attacks and Defensescited by 840
  8. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  9. 2020Fast is better than free: Revisiting adversarial trainingcited by 727
  10. 2015Distillation as a Defense to Adversarial Perturbations against Deep Neural Networkscited by 678
  11. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 567
  12. 2016Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samplescited by 446
22 more
  1. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 445
  2. 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 328
  3. 2018Certified Defenses against Adversarial Examplescited by 306
  4. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  5. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 187
  6. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  7. 2018Scaling provable adversarial defensescited by 143
  8. 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 125
  9. 2019Sparse and Imperceivable Adversarial Attackscited by 95
  10. 2016Measuring Neural Net Robustness with Constraintscited by 90
  11. 2019Wasserstein Adversarial Examples via Projected Sinkhorn Iterationscited by 89
  12. 2018Training for Faster Adversarial Robustness Verification via Inducing ReLU Stabilitycited by 67
  13. 2018Provable Robustness of ReLU networks via Maximization of Linear Regionscited by 51
  14. 2018CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networkscited by 50
  15. 2021Fast Certified Robust Training with Short Warmupcited by 46
  16. 2019Provable robustness against all adversarial lp-perturbations for p≥ 1cited by 39
  17. 2021Certified Robustness to Programmable Transformations in LSTMscited by 18
  18. 2020Interval Universal Approximation for Neural Networkscited by 14
  19. 2019Universal Approximation with Certified Networkscited by 9
  20. 2019On Certifying Non-uniform Bound against Adversarial Attackscited by 6
  21. 2019Training Provably Robust Models by Polyhedral Envelope Regularizationcited by 6
  22. 2021Fast Training of Provably Robust Neural Networks by SinglePropcited by 5

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 0; 2024: 1.

4 papers.

  1. 2022Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspectivecited by 51
  2. 2022Spelunking the Deep: Guaranteed Queries on General Neural Implicit Surfaces via Range Analysiscited by 11
  3. 2024Certified Robust Accuracy of Neural Networks Are Bounded due to Bayes Errorscited by 7
  4. 2022Quantization-aware Interval Bound Propagation for Training Certifiably Robust Quantized Neural Networkscited by 3