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 $\alpha < 1$, there is a set of $O(\alpha^{-1})$ points with robust radius $\alpha$, separated by distance $2$, that no one-hidden-layer network can be proven to classify robustly via interval analysis.

本文讨论了区间分析（或区间边界传播，IBP）用于验证和训练可靠机器学习的深度神经网络的可行性问题。研究发现，对于任何深度神经网络分类只有三个点，存在IBP无法证明的有效规范。此外，在单隐藏层神经网络的限制情况下，存在一组点，无论采用多少隐藏层，都无法通过区间分析来证明其分类鲁棒性。

神经网络的区间算法基本限制