Expressivity of ReLU-Networks under Convex Relaxations

Convex relaxations are a key component of training and certifying provably safe neural networks. However, despite substantial progress, a wide and poorly understood accuracy gap to standard networks remains, raising the question of whether this is due to fundamental limitations of convex relaxations. Initial work investigating this question focused on the simple and widely used IBP relaxation. It revealed that some univariate, convex, continuous piecewise linear (CPWL) functions cannot be encoded by any ReLU network such that its IBP-analysis is precise. To explore whether this limitation is shared by more advanced convex relaxations, we conduct the first in-depth study on the expressive power of ReLU networks across all commonly used convex relaxations. We show that: (i) more advanced relaxations allow a larger class of univariate functions to be expressed as precisely analyzable ReLU networks, (ii) more precise relaxations can allow exponentially larger solution spaces of ReLU networks encoding the same functions, and (iii) even using the most precise single-neuron relaxations, it is impossible to construct precisely analyzable ReLU networks that express multivariate, convex, monotone CPWL functions. * Equal contribution 1 Key Results on Univariate Functions In this work, we prove the following key results: • The most precise single-neuron relaxation, ∆ (Wong & Kolter ( 2018 )), and the popular DEEPPOLY-relaxation (Singh et al., 2019b; Zhang et al., 2018) do not share IBP's limitation and can express univariate, convex, CPWL functions precisely. • All considered relaxations, including IBP, can express univariate, monotone, CPWL functions precisely. • The ∆-relaxation permits an exponentially larger network solution space for convex CPWL functions compared to the less precise DEEPPOLY-relaxation. • Multi-neuron relaxations (Singh et al., 2019a; Müller et al., 2022) can express all univariate, CPWL functions precisely using a single layer. Having thus shown that, for univariate functions, the expressivity of ReLU networks under convex relaxations is not fundamentally limited, we turn our analysis to multivariate functions. Key Results on Multivariate Functions In this setting, we prove the following result: • No single-neuron convex relaxation can precisely express even the heavily restricted class of multivariate, convex, monotone, CPWL functions. Interestingly, the exact analysis of such monotone functions on box input regions is trivial, making the failure of convex relaxations even more surprising. In fact, CPWL functions as simple as f (x, y) = max(x, y) = y + ReLU(xy) cannot be encoded by any finite ReLU network such that its ∆-analysis is precise. We thus conclude that, for multivariate functions, the expressivity of ReLU networks under single-neuron convex relaxations is fundamentally limited. Implications of our Results for Certified Training While we believe our results to be of general interest, they have particularly interesting implications for certified training. In this area, all stateof-the-art methods (Müller et al., 2023; Mao et al., 2023; Palma et al., 2023) are based on the simple IBP-relaxation even though it induces strong regularisation which severely reduces accuracy. While Jovanovic et al. (2022) show that more precise relaxations induce significantly harder optimization problems, it remains an open question whether solving these would actually yield networks with better performance. Our results represent a major step towards answering this question. Specifically in the univariate setting, we show that more precise relaxations increase expressivity (see Table 1 ) and lead to larger network solution spaces (compare Theorems 11 and 15). Thus, we hypothesize that using them during training yields a larger effective hypothesis space for the same network architecture. Importantly, this implies that networks with higher performance could indeed be obtained if we can overcome the optimization issues described by Jovanovic et al. (2022) . However, in the multivariate setting, perhaps surprisingly, we show that even the most precise singleneuron relaxations severely limit expressivity (see Corollary 21). This highlights the need for further study of more precise analysis methods such as multi-neuron or non-convex relaxations. BACKGROUND ON CONVEX RELAXATIONS Below, we first discuss notation and background before defining key concepts. Notation We denote vectors with bold lower-case letters a ∈ R n , matrices with bold upper-case letters A ∈ R n×d , and sets with upper-case calligraphic letters A ⊂ R. We refer to a hyperrectangle B ⊂ R n as a box. Further, we consider (finite) ReLU networks h with arbitrary skip connections. CONVEX RELAXATIONS IN NEURAL NETWORK CERTIFICATION Here, we discuss neural network certification methods based on convex relaxations. These methods cast the robustness problem as an optimization problem and make it tractable by replacing the nonconvex activation function