The Fundamental Limits of Interval Arithmetic for Neural Networks
This work reveals inherent constraints in a popular method for reliable machine learning, indicating it may be insufficient for addressing key challenges in neural network verification.
The paper demonstrates fundamental limitations of interval arithmetic for verifying neural network robustness, proving that for any network classifying three points, there exists a specification interval analysis cannot verify, and for one-hidden-layer networks, there are sets of points with robust radius α that cannot be proven robust.
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.