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.
翻译:间距分析(或间距约束传播,IMBP)是用于核查和培训可靠机器学习领域的一项基本挑战,在可靠机能学习领域,强健的深神经网络的流行技术。然而,尽管做出了大量努力,但应对这一关键挑战的进展停滞不前,使人怀疑间距算术是否是一条可行的前进道路。在本文件中,我们对分析神经网络的间距算术限制提出了两项基本结果。我们的主要不可能的理论指出,任何神经网络仅对三个点进行分类,在这些点上有一个有效的规格,间隔分析无法证明。此外,在一层神经网络的有限情况下,我们显示出一个更不可能的结果:鉴于半径$\alpha < 1美元,有一组美元(alpha ⁇ -1})点,其半径为$/alpha美元,以距离2美元分隔,无法证明任何一层网络可以通过间距分析进行稳健的分类。