Expressivity of ReLU-Networks under Convex Relaxations
Authors: Maximilian Baader
Mark Niklas Mueller
Yuhao Mao
Martin Vechev
Venue: ICLR 2024 poster (2024)
Keywords: Convex Relaxations
Neural Network Verification
Certified Robustness
Adversarial Robustness
Universal Approximation
Primary area: societal considerations including fairness, safety, privacy
TL;DR: ReLU networks cannot encode multivariate, convex, monotone, continuous piecewise linear functions such that single-neuron convex relaxations yield precise bounds and more results on the expressiveness of ReLU networks under convex relaxation.

Abstract: 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.

Published as a conference paper at ICLR 2024
EXPRESSIVITY OF RELU-NETWORDS UNDER CONVEX RELAXATIONS
Maximilian Baader; Mark Niklas Müller; Yuhao Mao & Martin Vechev Department of Computer Science
ETH Zurich, Switzerland (mbaader, mark. mueller yuhao. mao, m mww.ii.. wtw.ii.wwwceeeeinf...... ethz.ch
ABSTRACT
Convex relaxations are key component of training and certifying provably safe neural networks. However, despite substantial progress, wide and poorly under- stood accuracy gap to standard networks remains, raising the question of whether this due fundamental limitations of convex relaxations. Initial work 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 -naalsilys is precise. To explore whether this lim- itation 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 larger class of univariate functions be expressed as preciscly amalyzable ReLU net- works, (ii) more precise relaxations can allow exponentially larger solution spaces of ReLU networks encoding the same functions, and (iii) using the most pre- cise single-neuron relaxations, it is impossible to construct precisely analyzable ReLU networks that express multivariate, convex, monotone CPWL functions.
INTRODUCTION
With the increased deployment of neural networks in mission-critical applications, formal robustness guar- antees against adversarial examples (Biggio al., 2013: Szegedy et al., 2014) have become an important and active field of research. Many popular certification methods (Zhang et al., 2018; Singh et al., 2018; 2019a;b) provide such safety guaran- tees by using convex relaxations to compute over-approximations of network's reachable set w.r.t. adversary specification. How- ever, despite significant progress, a wide and poorly understood accuracy gap between robust and conventional networks remains. This raises the fundamental question:
Table I: Expressivity of different relaxations. Novel results are red X and green V. Previous results are in black (x, ?). M: monotone, C: convex, MC: monotone and convex.
Relaxation
CPWL
M-CPWL C-CPWL MC-CPWL
IBP
DEEPPOLY-O DEEPPOLY-I A Multi-Neuron
R"
Is the expressivity of ReLU-newworks under convex relaxations fundamentally limited?
Investigating this question, Mirman et al. (2022) prove that, the class of convex, continuous- piecewise-linear (CPWL) functions cannot be encoded as ReL.U-nttworss such that their analysis with the simple IBP-relaxation (Gehr et al., 2018: Gowal et al., 2018), is precise.
This Work: Expressivity of Common Relaxations To investigate whether this limitation of IBP is fundamental to all single-neuron convex relaxations, we conduct the first in-depth study on the expressive power of ReLU networks under all commonly used relaxations. To this end, we consider CPWL functions, naturally represented by ReLU networks, and two common restrictions, convexity and monotonicity. We illustrate key findings in Table 1, showing novel results as red X and green /.
Equull contribution.

---

Published as a conference paper at ICLR 2024
Key Results on Univariate Functions
In this work, we prove the following key results:
The most precise single-neuron relaxation, A (Wong & Kolter (2018)), and the popular (Singh al., 2019b; Zhang et al., 2018) do not share IBP's limita- tion and can express univariate, convex, CPWL functions precisely.
DEEPPOLY-relin
All considered relaxations, including IBP, can express univariate, monotone, CPWL func- tions precisely.
The A-relaxation permits an exponentially larger network solution space for convex CPWL functions compared to the less precise D relaxxttion.
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 ReLU networks under convex relaxations is not fundamentally limited, we turn 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 multivariate, convex, monotone, CPWL functions.
Interestingly, the exact analysis of such monotone functions on box input regions is trivial, mak- ing the failure of convex relaxations even more surprising. In fact, CPWL functions as simple as [(r,y] v) = max(x, y) = + ReLU(x - y) cannot be encoded by any finite ReLU network such that its A-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 results to be of general interest, they have particularly interesting implications for certified training. In this area, all state- of-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 Jovanović 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 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 Jovanović et al. (2022).
However, the multivariate setting, perhaps surprisingly, we show that even the most precise single- neuron 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.
2 BACKGROUND ON CONVEX RELAXATIONS
We denote vectors with bold lower-case letters a E R", matrices with bold upper-case letters E Raxdd and sets with upper-case calligraphic letters A R. Inequalities a 2 b between vectors are elementwise. We refer to a hyperrectangle B C IR" as box. Further, we consider general (finite) ReL.U networks with arbitrary skip connections, including CNNs and ResNets.
Notation
2.1 CONVEX RELAXATIONS IN NEURAL NETWORK CERTIHCATION
We call a classifier H: X + y locally robust around an input æ E X' if predicts the same, correct class y Y for all similar inputs (x) == {x' E X x x' I|p I e). To prove that classifier is locally robust, we thus have to show that Hxx)) = (xx) y. Vz' E B. For a neural network predicting H(x)= = arg max, h(x),, this is equivalent to showing that the logit of the target class is always greater than that of all other classes, i.e., 0 < min h(2²), h(x'); ). As solving this non-convex optimization problem exactly is generally NP-complete (Katz et al., 2017), sfate-of-the- art neural network verifiers (Brix et al., 2023) relax it to efficiently solvable convex optimization
2

---

Published as a conference paper at ICLR 2024
problem. To this end, replace the non-linear activation functions with convex relaxations in their input-output space, allowing us to compute linear bounds on the output h(x):
{Ai + bt, hic & h(x)= S {A.,, + bu, heu..
for some input region (x),, with index sets L and U. These bounds can in-turn be bounded by
Ly min maxied (Ar, a + by.) E R and By analogously. Hence, we have ly I h(x:) S By.
IBP Interval bound propagation (Mirman et al., 2018; Gehr et al., 2018; Gowal et al., 2018) only considers elementwise, con- stant bounds of the form 1 I v I u. Affine layers y W
are thus also relaxed as
W (L++)-|W((a-)) +b We Wo+bs [( + b,
2
where | the elementwise absolute value. ReLU functions are relaxed by their concrete lower and upper bounds ReI.U()) Re) S ReLU((u) illustrated in Fig. I.
12
Figure 1: IBP-relaxation of ReLU with bounded inputs E [1
DeepPoly (DP) DeepPoly, introduced by Singh et al. (2019b), mathematically identical to CROWN (Zhang et al., 2018) and based recursively deriving linear bounds of the form A a; I v < A, + au
y
S
w-
DP-0
on the outputs of every layer. While this allows affine layers to be handled exactly, ReLU layers y ReLU(v) relaxed neuron-wise, using one of the two relaxations illustrated in Fig.
2:
DP-1
V 2
u
Av < RcLU(u) - (v (v-1) 1-
where product and division are elementwise. Typically, the lower-bound slope À {0, 1} is chosen depending on the input bounds and u. In this work, however, we analyze the relax- ations obtained by always choosing the same lower-bound, which denote with DEEPPOLY-0 (DP-0, green in Fig. 2) and DEEPPOLY-1 (DP-1, blue).
Figure 2: DEEPPOLY-I (blue) and
DEEPPOLY-O (green) ReLU abstrac- tion with bounded inputs E [1, u].
Entangle-Relaaatiin (A) In contrast to the above convex laxations, the A-relaxation (Wong & Kolter, 2018: Dvijotham et al., 2018; Salman et al., 2019; Qin et al., 2019) maintains mul- tiple linear upper- and lower-bounds on every network activation We write
y
(0
n-
y
A x + ah
A. x + auy
y y
I SUS
Figure 3: A-relaxation ReLU
with bounded inputs E B1 u].
Ar, x + ai,,
Au, x + au..
Unstable ReLU activation y ReLU(v) with I < 0 u relaxed with their convex hull as illustrated in Fig. 3
ReLU(v) S (v u
where again, product and division are elementwise. Note that this can lead to an exponential growth (with the depth of the network) in the number of constraints for any given activation.
Multi-Neuron Relaxation (MN) All methods introduced far relax actívation functions neuron-wist wise and are thus limited in precision by (single neuron) convex relaxation barrier (Salman et al., 2019), i.c.. the activation function's 's convex hull in their input-output space.
2-neuron
single-neuron
Multi-neuron relaxations, in contrast, compute the convex hull in the joint ouput- space of multiple neurons in the same layer (Singh al., 2019a; Müller al., 2022), consider multiple inputs jointly (Tjandraatmadja et al., 2020). We illustrate the increase in tightness in Fig. 4 for group of just k = 2 neurons.
Figure Comparison of 2-neuron (green) and single-neuron (blue) re- laxation projected into y2-U1-Up space for ReLU activations yi ReI.U(v.).
3

---

Published as a conference paper at ICLR 2024
2.2 DEFINITIONS
We now define the most important concepts for this work.
Definition 1 (CPWL). We denote the set of continuous piecewise linear functions f: X - y by CPWL(X,)) )). Further, if X' is some interval I C R. then we enumerate the points where f changes slope and call them Tú, where 0 S i S n,
implies I; < Z.., and X' [2o Tnl.
All CPWL functions f: I - R satisfy f(x) = f(x,)) + (r - x²) 1(0,11)=f(aa) for x E [a 1++1] #441-14
We denote by M-CPWL, C-CPWL, and MC-CPWL the class of monotone (M), convex (C), and monotone & convex (MC) CPWL functions, respectively. We say a network h encodes a function f if and only if they are equal all inputs X::
Definition 2 (Encoding). neural network h: X Y encodes function S: X + Y/ if and only if for all x E X' we have fx(z)= = fzz).
In the following, D denotes a convex relaxation and can be IBP, DEEPPOLY-O(DP-0)) DEEPPOLY- 1 (DP-1), A, or Multi-Neuron (MN). We now call the overaapprox of a network's graph (set of input tuples) obtained with domain its D-analysis:
Definition 3 (Analysis). Let h: X x be a network, D a convex relaxation, and C an input box. We denote by h (B) the polytope in h's input-output space containing the graph {(xz, h(z)) x E C) (B) X X' x y of on B, as obtained with D and refer to as the D-analysis of h on B.
For y C R, we denote the interval bounds of f on B by [S(B), [(B) =
[min f(x), maxxes f(x)] and, similarly, the interval bounds implied by h (B as (B)( (B)] = (x))( y, (a)( v).
As any D-analysis of h captures the set of all possible outputs M(z), x E B, it is of key interest to us investigate when the analysis does not lose precision. Specifically, whether the linear output bounds (B) do not exceed the interval bounds of f on B anywhere on B:
Definition 4 (Precise). Let h be network encoding f: X' + ) and D a convex relaxation. We say that the D-analysis is precise for h it yields precise lower and upper bounds, that is for all boxes B C X we have that (B), h (B) = [f [(B)].
In this work, we investigate the expressivity of Rel.U-networks, that is, which function class they can encode such that their D-analysis is precise. Specifically:
Definition 5 (Expressivity). Let D be convex relaxation, F a set of functions, and M set of networks. We say that N can D-express F precisely, if and only if, for all f E F, there exists a network h N, such that h encodes and its D-analysis is precise.
We can often replace (sub-)neewook to encode the same function but yield a (strictly) more precise analysis in terms of the obtained input-output polytope:
Definition 6 (Replacement). Let h and h' be ReLU networks, a box, and D some convex relax- ation. We say h' can replace h with respect D, (P((B) C (B3) for all B and write h & h'.
RELATED WORK
Below, we give a brief overview of the most relevant related work.
Expressing CPWL Functions He et al. (2020) show that ReLU networks require at least 2 layers to encode CPWL functions in Rd (for d > 2) with (d + 1)] layers always being sufficient.
Expressivity with IBP Baader et al. (2020) show that for any continuous function f: I' C R² + IR over compact domain I' and e O, there exists a finite ReLU network h, such that its IBP- analysis for any input box B C I, denoted by h IIP (B), is precise to an e-error:
[(B) + e, ((B) <) C IBP (B) [(BB e, [() c).
4

---

Published as a conference paper at ICLR 2024
An equivalent result immediately follows for all strictly more precise domains such as DP-0, A, and MN. Wang et al. (2022) propose a more efficient construction, generalize this result to squash- able activation functions, and provide first results on the hardness of constructing such networks. However, as these results require network widths going to oo for approximation errors e + 0 and IBP-based methods fail empirically for realistic networks, the study of exact encodings is crucial.
Investigating what class of functions allows for an exact InPaanalysis, Mirman et al. (2022) show that for any function with points of non-invertibility, i.e., x for (x) = | there does not exist a ReLU network -ex-essrssi this function.
Certified Training Certified training methods typically optimize upper bound the worst- case loss over some adversary specification computed via convex relaxations. Surprisingly, using the imprecise IBP-relaxation (Mirman al., 2018; Gowal et al., 2018) consistently yields better performance than tighter relaxations (Wong et al., 2018; Zhang et al., 2020; Balunović & Vechev, 2020). Jovanović al. (2022) investigate this paradox and identify two key properties of the worst- case loss approximation, continuity and sensitivity, required for effective optimization, with only IBP possessing both. However, the heavy regularization that makes IBP trained networks amenable to certification also severely reduces their standard accuracy (Mao et al., 2024).
Neural Network Certification We distinguish complete certification methods, which, given suf- ficient time, can decide any property, i.e., always compute precise bounds, and incomplete methods, which sacrifice precision for speed. Salman et al. (2019) unify a range of incomplete certifica- tion methods including IBP, DEEPPOLY, and A, and show that their precision is limited by that of the A-relaxation. They observe that for a wide range of networks and even when using the A-relaxation, substantial certification gap between the upper- and power-bounde on robust accu- racy remains. Semidefinite programming based methods (Dathathri et al., 2020; Raghunathan et al., 2018) increase tightness the cost of computational efficiency.
Early, complete certification methods directly leveraged off- off-the-shelf SMT (Katz et al., 2017: Ehlers, 2017) MILP solvers (Dutta et al., 2018; Tjeng al., 2019), limiting their applicability to small networks. To improve scalability, Bunel et al. (2020) formulate a branch-and-bound (BaB) frame- work, that recursively splits the certification problem into easier subproblems until they can be decided by cheap incomplete methods. This concept has been widely adopted and improved using more efficient solvers (Xu et al., 2021: Wang al., 2021) and tighter constraints (Palma al., 2021; Ferrari et al., 2022; Zhang et al., 2022).
4 CONVEX RELAXATIONS FOR UNIVARIATE FUNCTIONS
In this section, we differentiate all convex relaxations that are commonly used for neural network certification (IBP, DP-0, DP-1, A, and MN) in terms of their expressivity, i.e., with respect to the function classes they can analyze precisely when encoded by a ReLU network.
We first show that finite-depth ReLU networks can express M-CPWL functions precisely (The- orem 9). This construction can be applied directly to the strictly more precise DP-0 and relaxation and with slight modification also to DP-1. We, then, show that while finite ReLU networks can both DP-O- and A-express M-CPWL and C-CPWL functions, the solution space is exponentially larger when using the more precise A-analysis. Finally, we show that single-layer ReLU networks can MN-express arbitrary CPWL functions. We defer all proofs and supplementary lemmata to App. B.
4.1 BOX
To show that M-CPWL functions can be IBP-expressed, we begin by constructing a step function, illustrated in (Fig. 5), two-layer ReLU network that can be IBP. expressed:
V
,
Lemma 7 (Step Function). Let 3 R20 and f a CPWL( R) s.t. f()) = for x < Fp. f(x)
sen
15g
.51
12
for r > I and linear in between. Then, 6ao. a (x)
Figure 5: IBP-analysis of the step function
a Re क 00 ReLU(x (xo)) encodes f.
3 ReLU(B =1-50 ReLU(x zo)).
5

---

Published as a conference paper at ICLR 2024
Lemma 8 (Precise Step). The IBP-analysis of 21. is precise.
Intuitively, the key to this construction is to leverage that while the IBP-relaxation of the ReLU function does not capture any relational information, it recovers the exact output interval. By using two sequential ReLUs, we allow the inner one to cut away the outer one away the half-space f()) > thus obtaining precise analysis.
f(x) < 0 and the
We can now construct arbitrary M-CPWL functions from these step functions, allowing us to show that they
be Pexpeeseese:::
Theorem 9 (Precise Monotone). Finite ReLU networks can IxP-exs the set of monotone CPWL(I, R) functions precisely.
4.2 DEEPPOLY-O
We show constructively that finite ReLU networks can DP-0- express C-CPWL functions, by first encoding any such funetion a single-layer ReLU network. We note that the below results equiv- alently apply concave functions:
2
Lemma 10 (Convex encoding). Let CPWL(II be convex. Then f is encoded by
h(x)) = b b+ cT (eL -x)),,
(I)
for any choice +; E 11,, b and e are set appropriately, where f(xx)))) is the slope between points 2; and 2,-1, and a; 2 7i 0; 0 0 the slope change at xi+1.
y
Intuitively, we encode the C-CPWL function by starting with a linear function bo b + cæ, coinciding with one of the linear seg- ments of f. We then pick one of the points where f changes slope that are adjacent to this segment and add ReL.U++;;> xx)) changing its activation state at this point. Regardless of +., we now scale this ReLU with 7 = a; 0;-1 1 to introduce the local change of slope, and update the linear term added ReLU affects the segment that the linear function matched originally. We repeat this process until h encodes f-
if the newly
Figure 6: Illustration of two dif- ferent ReLU network encodings of the same function unde DP-0- (top middle) and A A-analysis (bottom).
We illustrate this in Fig. (top), where we start our construction with the left-most linear segment. We continue by adding ReLU, first at the green and then the red point, and show the DP-O relax- ation of the added ReLUs shaded area of the same color. We
illustrate the resulting overall DP-O-relaxation, obtained as their point-wise sum, striped grey. Ob- serve that this always recovers the original linear term the lower bound (see Fig, 6 top). This leads to an imprecise output range unless its slope is 0. If includes such constant section with zero-slope, we can directly apply the above construction, always changing =;- such that the ReLUs open "outward". i.e., in direction that does not affect the constant segment. If does not include such a constant section but a unique minimum, as our example, we place two ReL.Us this point, treating it as constant section with O-width and recovering precise lower bound (see Fig, 6 mid- dle). Thus finite ReLU networks can DP-0 -P-O-express C-CPWL functions but do not allow +; to be chosen freely. Note that the upper bound is still precise regardless of the choice of +..
Theorem 11 (DP-0 Convex). For any convex CPWL function Il + there exists exactly one network of the form h(x)) = b+ Eiez 7% ReLU(=t;<t - æz)) encoding f, with [Z] = 1 if has slope zero on some segment and otherwise [ = n, such that its -P-O-analysis precise, where
ys 0 for all

---

Published as a conference paper at ICLR 2024
4.3 DEEPPOLY-1
To show that DP-1 has the same expressivity as DP-0, we encode ReLU function as h(()) - x + ReLU(-z) which under DP- -analyssi yields the same linear bounds as h' (z))) ReLU(() under DP-O-analysis. The reverse also holds. Thus, the expressivity of DP-0 and DP- is equivalent.
Corollary 12 (DP-1 ReLU), The ReLU network h(z) + ReLU encodes the function f(x) = (z) and, the DP- -n-a-ssllssis of h(x) is identical to the OP-O-analysis of ReLU. Fur- ther, the DP-O-analysis of h(z) is identical to the -anl-snalysis of ReLU.
follows directly that any function that can be DP-O-expressed by a finite ReLU network can be DP-1-expressed by the same ReLU network after substituting every ReLU(xz) with x + ReLU(-z):
Corollary 13 (DP-1 Approximation). Finite ReLU networks can DP-1- and DP-O-express the same function class precisely. In particular, they can DP-1 -express the set of convex functions f E CPWL((I, IR) and monotone functions/ CPWL( IR precisely.
4.4 TRIANGLE
To show that finite ReLU networks can A-express C-CPWI. functions, we reuse the construction from Lemma 10. However, as the A-relaxation yields the exact convex hull for ReLU functions, we first show that the convex hull of a sum of convex functions (such as Eq. (I)) is recovered by the pointwise sum of their convex hulls:
Lemma 14 (Convex Hull Sum). Given two convex functions f. RR + R and the box [2, u]. Then, the pointwise sum of the convex hulls Hy + Hg is identical to the convex hull of the sum of the two functions Hf+g = Hj + Hg-
This follows directly from the definition and implies that the A-analysis is precise for arbitrary choices of +., illustrated in the bottom of Fig. 6:
Theorem 15 (A Convex). Let f E CPWT.(T, IR) be convex. Then, for any network h encoding f as in Lemma 10, we have that its A-analysis is precise. In particular, I, can be chosen freell.
4.5 MULTI-NEURON
-EE--UUURRR-RLLAATTNNS RELAXATIONS
As multi-neuron relaxations yield the exact convex hull of the considered group of neurons (all within the same layer), it is sufficient to show that we can express arbitrary CPWL functions with similar
single-layer network to that they MN-express CPWL functions. To this end, construction as in Lemma 10, where the lack of convexity removes the positivity constraint on %.
Theorem 16 (Multi-Neuron Precision). For every ʃ E CPWL(I, IR), there exists a single layer ReLU network encoding f. such that its MN-analysis (considering all ReLUs jointly) is precise.
5 CONVEX RELAXATIONS FOR MULTIVARIATE FUNCTIONS
After having shown in the previous section that, for univari- ate functions, the expressivity of ReLU networks under con- vex relaxations is not fundamentally limited, we now turn our attention to multivariate functions. There, we prove that no finite ReLU network can A-express the maximum function max: 2 + R precisely (Theorem 20). This directly im- plies that no single-neuron relaxation can express the class of multivariate, monotone, and convex CPWI. functions pre- cisely. Note, this negative result generalizes to all relaxations less precise than A, including IBP and DEEPPOLY.
Figure 7: Illustration of the pre-image of activation pattern changes with (-) and without ( functional change of ReLU network h encoding the g max(s. y) function, as well as the e- neighborhood 24 (O), in which the only activation change occurs at
Intuitively, we will argue along the following lines. We first observe that for any finite ReLU-Network h that encodes the maximum function,
find point (I, 2) E IR² with neighborhood U. such that on 24, all ReLUs in h either switch their activation state for x y or not all (see Fig. 7). Then,
7

---

Published as a conference paper at ICLR 2024
max(a, y)
2
y
Figure 8: Illustration of max(a, 8) (left) with its A lower (middle) and upper (right) bounds obtained
Theorem
we show that for such a neighborhood, we can A-replace the finite ReLU network h with a single layer consisting of just 2 neurons and linear term (Theorems 17 and 18). Finally, we show that no such single-layer network can A A-express max precisely (Theorem 19), before putting everything together in Theorem 20. All proof's and support lemmata are again deferred to App. A.
Let us begin by showing that we can express any finite ReLU network using the functional form of Eq. (2). That is, every i-layer network h' can be written as the sum of an (i 1)-layer network hi and linear function of ReLU applied to another (i 1)-layer network W: ReLU(hh nt (-11) Further, if, for given input region U4 all ReLUs in the original network switch activation state on the hyperplane w x 0 not at all, then, networks change activation state exactly for == w x 0.
ensure that every ReLU in both (i 1)-layer
Theorem 17 (Network Form Coverage). Given a neighborhood U and a finite k-layer ReLU net- work h such that on U and under A-analysis all its ReLUs are either stably active (ReLU(v) v), stably inactive (R) = 0), or switch activation state for 2 == w x with w E Rd then can be represented using the functional form
h :R. h + W, ReLUUh)
h (RRL) = b Wor,
for i i and such that all ReLUs switch their activation state {x E X' w x = 0). Here, L and R are labels, used to distinguish the possibly different (i-1)-layer networks h'-1 from each other.
We can now leverage the fact that all ReLUs change activation state at the same point simplify the sum of ReLUs to a linear term plus single ReLU: Σ, (eLu( A yz + ReLU(=) for some Y, a E R (Lemma 22). This allows us to further simplify ReLU applied to such sum of ReLUs: ReLU(7++ a ReLU(=)) A +' a' ReLU(z) (Lemma 23). These two replacements allow us to recursively reduce the depth of networks in the form of Eq. (2) until just a single layer is left:
Theorem 18 (Network Simplification). Let h² be network as in Theorem 17 such that all ReLUS change activation state at z un T
x with w E Rdd We have
h 1 W RcLU(h
Max b b Wx a RcLU(2).
where (((x)) = bo + wa and all ReLU change state exactly at {æ E X' w x 0}.
Note that, h.* A3- and h map to IR, while h maps to the space of some hidden layer R². Next, we show directly via contradiction that single-layer ReLU networks of this form cannot A-express the maximum function, illustrating the resulting (imprecise) bounds in Fig. 8:
Theorem 19 (Triangle max). ReLU-networks of the form 11x,, v) b + w t ReLU(x- 3) can not A --express the function max: R² + R.
Proof. We consider the input region B [0, 1]2 and constrain our parameters by considering the = h(0 0). For x < y. we have f(x, y) = y W wyy fi(z, y) and thus wz = 0, wy 1. Finally for
following: For 2 = y = O, we have f(0, 0) = 0
y. we have f(z, y)
y + axx y) = h(x, y) and thus a = 1. Hence we have (x, y) = y + ReLU(I y).
y
ReLU(x - v) < { 1 ++
< (α.v) < (x + y + 1).
x
The maximum of the upper bound is attained at x = y = 1, where we get h AB = which is
larger than max(B) (see Fig. 8).
8

---

Published as a conference paper at ICLR 2024
To show that ReLU network can --express max it remains to argue how can find U such that all ReLUs switch their activation state at (x E X w x = 0} or not at all:
Theorem 20 (A Impossibility max). Finite ReL.U networks can not -eexpress the function max.
Proof. We will prove this theorem via contradiction in four steps. Assume there exists finite ReL.U network that A-expresses max precisely.
First - Locality We argue this point in three steps:
1. There exists a point (x, y = x) with an e-neighborhood U' such that one of the following holds for any RcLU(u) with input
(2c, v) of the network h:
the ReLU is always active, i.e., V(x,)) U, ReLU(u) u,
the ReLU is never active, i.e., V(z, y) E U, (e) = 0. or
the ReLU changes activation state for x = i.e,, 3e' E R, ReLU(() = ReLU(u((x v)).
This follows directly from the fact that finite ReLU networks divide their input space into finitely many linear regions (see the illustration in Fig. 7).
2. Further, there exists e-neighborhood U of (x,, such that the above holds under IBP- analysis, as it depends continuously on the input bounds and becomes exact for any network when the input bounds describe point.
3. Via rescaling and translation, we can assume that the point (x, y) is at 0 and that the neigh- borhood U covers [|3.
Second Network Form On the neighborhood U, any finite ReL.Unetwork h can, W.r.f. A, be
represented by h ht-1 + W ReLU(h"=)), (v) b + We with biases b E Rd,, weight matrices W E Rd xd where all ReLUs change activation state exactly for x = y (Theorem 17).
Third Network Replacements We can replace h² w.r.t A with the single layer network (z y) = b W(x, v) + +aR(2= - (Theorem 18).
Fourth Conclusion There exists network of this form encoding the max-function such that its A A-analysis is precise on the interval [0, 1]2 (Theorem 19).
This concludes the proof.
As max belongs to the class multivariate, convex, monotone, CPWL functions, it follows directly from Theorem 20 that finite ReLU network can A-express this class precisely:
Corollary 21 (A Impossibility). Finite ReLU networks can not A-express the of convex, mono- tone, CPWL functions mapping from some box II C IR² to R.
CONCLUSION
We conduct the first in-depth study on the expressivity ReLU networks under all commonly used convex relaxations and find that: (i) more precise relaxations (A, DP-0 or DP-1) allow a larger class of univariate functions (C-CPWL and M-CPWL) be expressed precisely than the simple IBP-relaxation (M-CPWL), (ii) for the same function class (C-CPWL), a more precise relaxation (A vs DP-0 or DP-1), 1). can allow an exponentially larger solution space of ReLU networks, (iii) MN- relaxations allow single-layer networks to express all univariate CPWI. functions, (iv) even the most precise single-neuron relaxation (A) is too imprecise to express multivariate, convex, monotone CPWL functions precisely with finite ReLU networks, despite their exact analysis being trivial.
While more precise domains improve expressivity for univariate functions, all single-neuron convex- relaxations are fundamentally limited in the multivariate setting. Surprisingly, even simple functions that can be encoded with a single neuron h = y ReLU(x y) max [z, y), can not be A -eexpressed precisely using any finite ReLU network. This highlights not only the importance of recent, more precise
and BaB-based neural network certification methods but also suggests more precise methods might be needed for training.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We would like to thank our anonymous reviewers for their constructive comments and insightful questions.
This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agreement
101070617). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Commission. Neither the European Union nor the European Commission can be held responsible for them.
The work has received funding from the Swiss State Secretariat for Education, Research and Inno- vation (SERI).
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Maximilian Baader, Matthew Mirman, and Martin T. Vechev. Universal approximation with certified networks. In Proc. of ICLR, 2020.
Mislav Balunović and Martin T. Vechev. Adversarial training and provable defenses: Bridging the gap. Proc. of ICLR, 2020.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smniic, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Proc of ECML PKDD, volume 8190, 2013. doi: 10.
Christopher Brix, Mark Niklas Müller, Stanley Bak, Taylor Johnson, and Changliu Liu. First three years of the international verification of neural networks competition (VNN-COMP), CoRR, abs/2301 005815, 2023. doi: 10.48550/ARXIV22331.000 arXiv. 2301.05815.
URL https://doi.orgg/1 48550/
Rudy Bunel, Jingyue Lu, Ilker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and M. Pawan Kumar. Branch and bound for piecewise linear neural network verification. J. Mach. Learn. Res., 21, 2020.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Ue- sato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian Goodfellow, Percy Liang, and Pushmeet Kohli. Enabling certification of verification-agnosiic networks via memory-efficient semidefinite programming. In Proc. of NewrlPS, 2020.
Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. Output range analysis for deep feedforward neural networks. In NASA Formal Methods 10th International Symposium, NFM 2018, Newport News, VA, USA, April 17-19, 2018, Proceedings, volume 10811, 1. 2018. doi: 001079977---31--7733-5555
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A. Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. In Proceedings of the Thirty-Fore Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, Au- gust 6-10, 2018, 2018.
Rüdiger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Automated Technology for Verification and Analysis 15th International Symposium, ATVA 2017, Pune, India, October 3-6, 2017, Proceedings, volume 10482, 2017. doi: 10.1007/ 978-3-319-68167-211
Claudio Ferrari, Mark Niklas Müller, Nikola Jovanović, and Martin T. Vechev. Complete verification via multi-neuron relaxation guided branch-and-bound. In Proc. of ICLR, 2022.
Timon Gehr, Matthew Mirman, Dana Trachhler-Cohent Petar Tsankov, Swarat Chaudhuri, and Mar- tin T. Vechev. A12: safety and robustness certification of neural networks with abstract interpreta- tion. In 2018 IEEE Symposium on Security and Privacy, SP 2018, Proceedings, 21-23 May 2018, San Francisco, California, USA, 2018. doi: 10.1109/SP.2018.0000 800055.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovie, Timothy A. Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. ArXiv preprint, Abs/1181.. 2018.
Juncai He, Lin Li. Jinchao Xu. and Chunyue Zheng. Relu deep neural networks and linear finite elements. Journal of Computational Mathematics, 38(3), 2020. ISSN 1991-7139, doi: https:
1901 101---200--666
Nikola Jovanović, Mislav Balunović, Maximilian Baader, and Martin T. Vechev. On the paradox of certified training. Trans. Mach. Learn. Res., 2022, 2022.
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. ArXiv preprint, /ttp///77..01111 135, 2017.

---

Published as a conference paper at ICLR 2024
Yuhao Mao, Mark Niklas Müller, Mare Fischer, and Martin T. Vechev. TAPS: connecting certified and adversarial training. CoRR, abs/2305.0433 04454444 2023. doi: 10.485500anXii.22355..444
Yuhao Mao, Mark Niklas Müller, Mare Fischer, and Martin T. Vechev. Understanding certified training with interval bound propagation. In Proc. of. ICLR, 2024.
Matthew Mirman, Timon Gehr, and Martin T. Vechev. Differentiable abstract interpretation for provably robust neural networks. In Proc. of ICML, volume 80, 2018.
Matthew Mirman, Maximilian Baader, and Martin T. Vechev. The fundamental limits of neural networks for interval certified robustness. Trans. Mach. Learn. Res., 2022, 2022.
Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Piischll, and Martin T. Vechev.
PRIMA: general and precise neural network certification via scalable convex hull approximations. Proc. ACM Program. Lang., 6(PPLL) 2022. doi: 10. (0.1145/3498744
Mark Niklas Müller, Franziska Eckert, Marc Fischer, and Martin T. Vechev. Certified training: Small boxes are all you need. In Proc. of ICLR, 2023.
Alessandro De Palma, Harkirat S. Behl, Rudy Bunel, Philip H. S. Torr, and M. Pawan Kumar. Scaling the convex barrier with active sets. In Proc. of ICLR, 2021.
Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M. Pawan Kumar, Robert Stanforth, and Alessio Lomuscio. Expressive losses for verified robustness via convex combinations. CoRR, abs/2305. 13599, 2023, doi: (0.48550/arXi.2235...33 13991.
Chongli Qin, Krishnamurthy (Di) Dvijotham, Brendan O' O'Donoghue, Rudy Bunel, Robert Stanforth, Sven Gowal, Jonathan Uesato, Grzegorz Swirszez, and Pushmeet Kohli. Verification of non-linear specifications for neural networks. In Proc. of ICLR, 2019.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying ro- bustness to adversarial examples. In Proc. of NeurlPS, 2018.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsich, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. In Proc. of NeurlPS, 2019.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel and Martin T. Vechev. Fast and effecttive robustness certification. Proc. of NeurIPS, 2018.
Gagandeep Singh, Rupanshu Ganvir, Markus Püichel, and Martin T. Vechev. Beyond the single neuron convex barrier for neural network certification. In Proc. of NeurlPS, 2019a.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang,, 3(POPL), 2019b. doi: 10. 10.1145/329354.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In Proc. of ICLR, 2014.
Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Patel, and Juan Pablo Vielma. The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification. In Proc. of NeurIPS, 2020.
Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In Proc. of ICLR, 2019.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In Proc. of NeurIPS, 2021.
Zi Wang, Aws Albarghouthi, Gautam Prakriya, and Somesh Jha. Interval universal approximation for neural networks. Proc. ACM Program. Lang., 6(POPL., 2022. doi: 10.1145/3498675.
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proc. of ICMI., volume 80, 2018
12

---

Published as a conference paper at ICLR 2024
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Proc. of NewrlPS, 2018.
Kaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsich. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. In Proc. of ICLR, 2021.
Huan Zhang, Tsui-Wel Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Proc. of NeurlPS, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane S. Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. In Proc. of ICLR, 2020.
Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsich, and J. Zico Kolter. General cutting planes for cuudd-ropagatioonbeen based neural network verification. In NeurIPS, 2022.
13

---

Published as a conference paper at ICLR 2024
A DEFERRED PROOFS ON MULTIVARIATE FUNCTIONS
Theorem 17 (Network Form Coverage). Given a neighborhood U and a finite k-layer ReLU net- work h such that on V and under A-analysis all its ReLUs are either stably active (RcLU(v) u), stably inactive (RcLU(u) = 0), or switch activation state for 2 == w x with w E Rd then can be represented using the functional form
h = n/ + W, ")
WiRL) = b+ Woxr
(2)
for i = k and such that all ReLUs switch their activation state at {or E X' w To == 0}. Here, L and R are labels, used distinguish the possibly different (i- (i-I)-layer networks h' from each other.
Proof. Given W. Rh "), we partition the columns of the weight matrix into W,
(W. W; (W; depending on whether the associated ReLU is stably active, stably inactive, or unstable, respectively. We thus obtain
IW; (W;+) ReLU - h + W, ReLU(hn
n is still an (i laller We update hi = =h2² + W by showing that W; h
network as follows. We recursively update weight matrices W6 Wknnow
W, Wn obtain
W h W h-- + Wk,new (hx until we have reached k = 1, where we have W h W, + W, Wo, W new ReLU((RR + Wo.
Lemma 22 (Simplification of ReLU Sums w.r.t. A). Let A E Rax1 and u E RR.. Then, we have
h(=) A ReLU(w:)
M(=) 72 + ReLU(=))
where y= -i,,, <o A, and Ei,,,>0 A, -
0. Thus they fully defined by their value at the points 2; E 1,1 Hence, we can show that h and h'' encode the same function by showing their equivalence on these points: 1(0)
Proof. Both h and h' are CPWL functions with slope change only
('()), h(-1) Ei,m<0 -A = - = h1(-1), and h(1) = > Arw; = a + 7. As yz and a ReLU(z) are convex/concave, and their A A-analysis yields their convex hulls, the pointwise sum of their convex hulls, i.e. the A-analysis of h recovers the convex hull of h by Lemma 14 and is thus at least as precise as any convex-relaxation of h.
Lemma 23 (Simplification of Composed ReLUs w.r.t.
A). We have
= 1/2 ReR.U(()) where 7' = - ReLU(->) and a' ReLU(a +7) -
h(=)= = ReI.U(> + a ReI.U(=)) A h'(s) =
Proof. We observe that (=x)) is convex and piecewise- -inear for any 2 E [1, w] C R with < 0 < u and a slope change only at 0. Its convex hull is thus spanned by h(l) ReLU(n() h²((), h(0) = h (0) = 0. and h(u)= = ReLU(()+a)u) = h1(u). We further observe that the A-relaxation of ReLU(=) and is their convex hull. Finally, the convex hull of the positive sum of convex functions is equal to the pointwise sum of their individual convex hulls (Lemma 14). Thus, the trianile-relaxation of (2) recovers the convex hull of h(2) and thus the tightest possible convex relaxation.
For convex functions f.g: R. E, we define the convex hull Hy,(k, = {x,,)) | x
[1, u], f(x) < y < [(1) + f(w)-(() (x [)] 1)} over [1, u] C R. Further, we define the convex hull sum --1
of and g on u, to be H, + nl = {( + v²) (x.1)) Hy, (x,v") Hly)
Lemma 14 (Convex Hull Sum). Given two convex functions f.g: IR + I and the box ,1 w]. Then, the pointwise sum of the convex hulls H, + Hg is identical to the convex hull of the sum of the two functions H./4g = H. + Hy.
Proof. We first show that every point in Hsto can be obtained from H, Hy. Let (α, H. ul). Then we have
(z) Sy S (() + (++))()) (x - -1). f(x)+ Sy & f() + [()-(1)) (x 1) + g(l) - f(w)-(()) (xc 1). n-!
14

---

Published as a conference paper at ICLR 2024
Then can find partition of y y' y". We know for sure that there exists t [0, 1] s.t.
(1 () 9)) + t((s + g)(1) + ([+o))-((++00) (x ()). Hence we pick for example
y' = (1 - ())(())) + ((((1) / (s 1)) E Hl
y" = t)g(z) + +((()) + المرا n-1 (x 1)) E Hg-
get immediately that (z, y) Hy + Hg. The other direction is immediate.
Using Lemma 23, we can show that these networks mapping IR to R can be simplified further:
Theorem 18 (Network Simplification). Let h be network as in Theorem 17 such that all ReLUs change activation state at 2 == w x = with w E Rd. We have
h = n W ReLU(h
-
RcLU(z).
where 1 (x) = by + Wax and all ReLU change state exactly at {o E X' w T x = 0}.
Note that, h h k-1 and h map to R. while k-1 maps to some IR...
Proof. We show more general result on h* with possibly many output dimensions by induction:
Induction Hypothesis: h' b, + W,z + ar ReLU(z).
Base Case: (x)) bo + Wo satisfies the form (x()) = bo + Wix + on ReLU(()) for ao 0, thus we can replace h. (a) by itself.
Induction Step: Using the induction hypothesis, we have W, ReLU(h'
W, ReLU +
W Q;-1 (z)) which by Theorem 17 only changes its activation state 0. Since Re)U(()) = O, we must have b + W;-1 = we for some w (recall that is the projection of æ on a hyperplane in the input space). Further, applying Lemma 23, we obtain
W, ReLU(hR)) =W, ReLU(w= + a; ReLU(=))
A + af ReLU(z) by + W/2 + a ReLU(=).
Using the induction hypothesis, we thus rewrite:
h h h--1- W. (eLU(()) A Wa + a; ReLU(s))
Theorem 19 (Triangle max). ReLU-netwond of the form h( v) = b+ tu, Rell ReLU(x- v) can not A-express the function max: R R.
Proof. We first constrain our parameters by considering the following:
For x y
have f(0, 0) leading to b 1(0, 0).
For I' y, we have far y) w. wyy h(2, y) and thus w₂ 0, Wyy 1.
For x > y, we have far 8) y a(x v) hzx 8) and thus 1.
Hence we have h(x,v) ReLU(x y).
0
ReI.U(x - v) f 11
Adding results in the following:
< h( H(x ( + 1).
x:
The maximum of the upper bound is attained at y 1, where get which is larger than max y) = 1 for x, y E [0, 1).
15

---

Published as a conference paper at ICLR 2024
Theorem 24 (Triangle max tp). ReLU-networks of the form h y) b 2x wy + (eLU(x y) can not A-express the function max: TR= + R for any f--norm bounded per- turbation with p 2 1, i..., input regions (x(x) = (a' X || x'ppp c.
Proof. We first consider the case of as in the proof of Theorem 19 to obtain h(x, y) - ReLU(= y). We consider the input region
and f max y): We again constrain parameters
0.5
Zig
0.5
We can now use Hölder's inequality to compute bounds on the ReLU
9o
0.5
input:
|[-
yo ||[
zo
1/0
5 x u
2
where 1 + 1 1. And thus obtain the following bounds on the ReLU output:
0
S ReL.U(
y) s 2 y )t
y
Adding results in the following:
h(,, v) / (x y )
We again Hölder's inequality bound the upper bound:
[
S S (3r yo )
1/2
c (1 (1+22)) 1,
Where the last inequality holds due to p > = q < co. This upper bound strictly greater than maXg0.5 max(x, y)
We now consider the case of = 1 and the rotated max function f = max K
z+v
We choose
([
the input region Bp=
v2
v2 and observe that we recover the setting as discussed the proof
of Theorem 19 for p rotated by 45 around the origin and thus obtain the same imprecise bounds.
Theorem 20 (A Impossibility max). Finite ReLU networks can not A e-express the function max.
Proof. We will prove this theorem in four steps.
First Locality
1. There exists point (x,y = x) with an e-neighborhood U'' such that one of the following holds for any ReLU(u) with input h,, y) of the network h:
the ReLU is always active, i.e., V(r, v) U, ReLU(v) =
the ReLU is never active, i.e., V(x, y) E U, ReLU(v) = =0, 0. or
the ReLU changes activation state for
y. ie.. Ee' R.
ReLU(v'(x y)).
2. Further, there exists neighborhood U of (z, y) such that the above holds under A-analysis, as depends continuously on the input bounds and becomes exact for any network when the input bounds describe point.
3. Via rescaling and translation, we can assume that the point (x, y) is at 0 and that the neigh- borhood 14 covers
[|,,
Second Network Form On the neighborhood U, any finite ReLU-network h can, w.r.. A, be replaced by h = h k-1 + W ReLU(h with biases b E Rd,, weight matrices W E Rd xda 1, and 1:0 + We, where all ReL.U change activation state exactly for x: y (Theorem 17).
16

---

Published as a conference paper at ICLR 2024
Third - Network Simplifications y) (Theorem 18).
We can replace h" w.r.t triangle with b+ bx,,(x, v) +ayR((x
Fourth Conclusion Every finite ReLU network can be replaced w.r.t A with single layer
network of the form (xx v) = b+ W (r. y) +af((x yy). However, there exists no such network encoding the max-fume max-function such that its A A-analysis is precise on the interval [0, 1]2 (Theorem 19).
Corollary 21 (A Impossibility). Finite ReLU networks can not A-express the set of convex, mono- tone, CPWL functions mapping from some box II C. IR2 to R.
B DEFERRED PROOFS ON UNIVARIATE FUNCTIONS
B.1 Box
Lemma (Step Function). Let B E Rz0 and f E CP, s.t. f(x) 0 for < To. f(x)(( for x > 21 and linear in between. Then, (00 = 3 - ReLU(3 mリー20 ReLU(x -zo)) encodes f.
Proof. We prove the theorem by considering the three cases separately:
1. For x S To have
(()) ReLU
ReLU(x 2o) + () B
F1 FB
ReLU(- ReLU(B) +
0 3) +
31-20
-3 -B+1 + 3
0.
2. For un <x S x1 we have
Daa.n a (x)
ReLU(
ReLU(r x0) + + +
F1-20
ReLU(- 31
B (x -r0) + B) + 3
(x - ro)
33 + B
2g-20 (x -ro)-
3. For x 2 21 we have
(20)
ReLU(- 8 ReLU(x xn) + B) + 3
31-30
ReLU(- (x - Fa) + 3) + 3
-00 B
B.
Lemma (Precise Step). The Ina-asalysis @2 is precise.
17

---

Published as a conference paper at ICLR 2024
Proof. Consider the box [1, u|] C R.
(e ReLU
8 ReLU un) + () + B
Z1-2a
ReLU
ReLU((I zo, u mn)) + (3 + B
ReLU
8
[ReLU(I x ReLU _n) + (3 +
ReLU(
ReI.U(u -r); Ø1-30 ReLU xn)] + +
21 -F0
ReLU
ReLU(u - zo) + 3, 11
ReLU( mo) + 8]) +
.1
ReLU
ReLU(u - zo) + 3,
ReLU( xo) + 8]) +
[ReLU
8
ReLU(u- z0) B), ReLUR 51
ReLU(1 zo) + 3]] + B
11 mm
[ReLU
ReLU(l - -r0) + B), ReLU 21 -1-50
3
ReLU(u x0) 3)] + 3
31
[ReLU( ReLU((- - + 3) + 8, ReLU -1 ReLU(uu - zo) + B) + 3]
a()), +2)),,)),)
Theorem (Precise Monotone), Finite ReLU networks can IBP-express the set of monotone CPWL(T, IR) functions precisely.
Proof. W.L.o.g assume is monotonously increasing. Otherwise, consider -f. Let 2; for i [o. be the set of boundary points the linear regions of with zo < ... < En. We claim that
Mxx) = f(xo) + Σ ((:)))
is equal to on Il and that the IBP-analysis of h is precise. We note that f(z;+1) f(x;) > 0.
We first show f = f on For cach æ ll pick E {l...., n) such that Øy-1 S x < 2j. Then
n-1
Mxx f(ro) +
=f(o)) +
=s(ro) +
1-1
-((o) + Σ (f(#+11) - f(x:)]
f(2,41)-f(3,), 2541-2;
x
1m0
=f(x)) + ((0;1))-((1))
(x xz))
#st1-01
= f((),
where used the piecewise linearity of in the last step.
18

---

Published as a conference paper at ICLR 2024
Now show that the analysis of IBP of h is precise. Consider the box [L, ui S I. We have
h((,,) = f(xo)
-(ern) (14, u))
= =xro)
[f(2))
Σ
Pz Pa /o00)
Σ Se
[N()),(uu)
f(w))
B.2 DEEPPOLY-O
Lemma 10 (Convex encoding), Let f CP,L((TRR) be convex. Then f is encoded by
h(x)) = + cz + N ReLLU(;((=-a) -
(1)
for any choice t; E (-1, if and are set appropriately, where [(m))))-((a)) is the slope 04+1
between points 2; and F1+1, and %/4 0, 0:-1 the slope change at 21+1-
Proof. First, show that 7j 0j aj-1- Evaluating h(x) for æj S x S xz+1 yields
h(x)= = b
2/ (c, -x)) x;))
=b+ +
+ (x - x+) = +, < x/ Σ
N + (r - x,)( = - > x
1=1
= =b CE + Σ 71 x4) + +, < x] Σ
N( 2,) = = >x
=b+ca CE +
Σ 11 - 2z) +] M(1 r;) =].
The derivative of h evaluated at x for 2j x < xz+1 az:
0h dr (z)
- Σ .| -] aj.
c
i=++
By choosing e small enough we can ensure that x, + E [xy, 2541] and x, E [z 23] and thus
0h
Oh
aj a--11 =
dx (z, + e)
(I,
c)
dr
n-1
3-1
n-1
Σ M +] Σ
-
Σ
+|+
Σ -|+==
i=j+1
= - +
19

---

Published as a conference paper at ICLR 2024
Next, show that can pick arbitrarily long as b and are set appropriately. Pick any choice of +, E {-1,1} and set and c to
b: f(oo) =0 f(x) [(xo)
n-1
Σ nalt= = f(xo) 2000
Σ
7a =
21 20
n-1
c: ag +
Σ
Yi M = -|.
1=1
We have h(x) = fz) Indeed: For any x E [ro, pick j s.t. æ E [zy, Then
n
h(x) = cz
71 xx)(=; +1
Σ
r;)[ =1
im++
=
Ti + = +] +
| =1
c+ Σ
=
+]
Σ
#
1=1
offset
linear
The offset evaluates to
H: +]+ Σ 70. =-]
1=1
1++1
n-
= f(xo) - 10
N:0; (+. = = - Σ
Moy No,(+; = +] +
Σ
7o (++ = -]
t=l
+++1
= f(10) - FO00
wa = -1 Σ
may = =+]
f(xo)
000D
7:4
1=1
f(ro) 0goD
71
2222 ................................ -
f(ro) Fg00
(a1
On) 21 (02 01 221
100-0)-1)4
= f(xo) 2ga0 + a6o - a1 + 01 a2 ... - - ajtj
f(xo)) + (x1 20)a0 + (x2 21)a1 + (z) 1)-1)0a-1 ajz
f(xo) + (f(z1) f(xo)) (f(2z) f(x1)) ... ... (f(r,) f(z)-1)) azæj
= =((,) - -ajfj:
where we used that = ai-1 and 0;
f((-1)- f(xs), The linear part evaluates to 1-
++
M = +] Σ
x =1
1=1
#=/+1
R-1
n-1
= 0g
+
% -]+
%|+ = +]
Σ
-==---]
i=1
i=1
i=111
1
0g
+
+|+ Σ
r =+
1=1
1=1
og +
000
02 0%-1
20

---

Published as a conference paper at ICLR 2024
Combining the results, get
h(x> f(zz) - 0j2y + raj f(x;) + +ay(1 zz) f(x),
by the piecewise linearity of f- Lemma 25 (DP-0 Monotone ReLU), The DP-O- of the 1-layer ReLU network h(x) Σ 7/ ReLUUr- n4) yields
M()); h(xz-11) + ai- aj-1 x) } h(x)) v
h(z), h(1)-h(t) (x 1) + h(1)
if all ReLUs are stable,
otherwise.
where x; ER S.t. Sis S n and i < 3; < pp and %i are either all > 0 or all < <. j is the smallest such that 2ū 2 1 and k is the largest i such that x; < u. Thus, DP-O analysis for h(x)) is precise.
Proof. W.o.Igg assume h is monotonously increasing. Otherwise, consider -h.
The cases u I1 and Fa < I are immediate. Choose j as the smallest i such that x; 2 I and is as the largest i such that 2; < u.
DP-0 yields for ReLU(x zz)) on l 2
Vi
i J
24
if j. if if i.
0
j < i < k
< ReLUU(I -2;)
(x
k
a-1 0
0
if i,
Thus have
Σ 71 xz) S h(x)) - Σ x(
x4) Σ
78
u-z a-
(x 1).
(=j
The term
E1=l 7xx 221) can be simplified follows
1-1
Σ 11 21))
7/
W2z
f-1
f-1
x
(a: 01-1))
Σ
(as
04-1
i=1
i=1
j-1 Σ
j-1
= =x(aj-1 - ao)
0::24 +
01-1
1=1
j-2
=x(a;-1 - 00)
011
0g1i41 + a02
i-2
j-2
= =x(0;-1 - 00) 18
0 +
0,3 + 0g
1=1
j-2
= =z(0-11 - ao) a--10 +
a1(2411 xz) agTi
1-2
=aj-1(# - xz-1) + an x) + Σ
(M M(xs))
==1
-2 + an( x) h(r5-1) h((1))
= =((z--1) + 1 (x 1)-1);
hence have proven the lower bound.
21

---

Published as a conference paper at ICLR 2024
Now consider the upper bound. We evaluate the upper bound at I and u. If the two linear upper bounds coincide there, they coincide everywhere:
j-1
k
x =
Σ
rel1 - 2;)) + Σ
w-
11)
i=1
Σ
7:ll - -x;)
h(1) h(w) h(w))b(()) (1 h(t),
7i(u x4)
Σ
78
4-21 (u 1)
k
Ve(u - 22) +
Σ
7/(u - Xz))
Σ Ya(u - -xt)
h(u) h(1)-A(1) u-1 (u + h(1),
hence have proven the upper bound.
Theorem 11 (DP-0 Convex). For any convex CPWL function f: - R. there exists exactly one network of the form h(x) = b+ Eiez Y ReLU(#;;x - 24)) encoding f. with [Z] 1 if f has slope zero on some segment and otherwise |Z] = n, such that its DP-O-analysis is precise, where
7's > for all
Proof. The proof works as follows:
If the function is monotonously increasing, we show that using local argument +, + and if the function monotonously decreasing, we argue ; = If has somewhere zero slope, it will be piecewise linear region the boundary of [ Fn), in which case we need neuron less.
If the function is non-monotone and has slope zero somewhere, then there are two minima x and x² that are also switching points. Hence f is for all T; > x²+2"" increasing and for all 2, < ----" decreasing, so we can reuse the argument from before and need n neurons for that. Then we argue separately for the ReLU at xx and xt
2
If the function is non-monotone and has nowhere slope zero, then there exists a unique minimum Ty. We then show that there exactly one splitting of 7j to ReLU(( - xy)) and ReLJU(-x R.
Finally, prove that network is precise.
We know that there are finitely many switching points 25, 1 i n.
Case 1: f is monotone. W.o.Igg assume f is monotonously increasing; the proof is similar for monotonously decreasing f. Assume that +, for some j. Then there exists >> 0 such that for all [xj e, xy + e]. all the ReLUs except ReLU(-x + æ;) are stable, i.c., either always 0 or always active. Further, for such inputs, DP-0 yields
0 S 7. ReLU(r x,) S (-x +
As f has no minimum, least one other ReLU need to active at zy; If there would be no other active ReLU, then f would have a minimum. The active neuron(s) contributes a linear term of the form Bx, B # 0, hence get for 2;
x, and some R. DP-0 bounds
b Br < h()))
+ Br + 6).
22

---

Published as a conference paper at ICLR 2024
We know that for 2 zj. we get get h(z,) and thus h(zz) b- Sz The slope of h 2; - c -1j-- Hence, we have - - h(zz) contradicts the assumption that we precise since the lower bound from DP-0 analysis h(z,) is unequal to the actual lower bound h(z - e). Hence, we have to have +, = + for all j.
(8 7t)e e > b+ [(z, - <) = h(zz) Be since y > 0. This
Case 2: f is not monotone and has slope 0 somewhere. Then, there two minima which also switching points, x² and x=* The argument in Case is a local one, hence we can use the same argument for all such that æi $ {x xx" J. so we only need consider the cases for 2j and x=. Since I is convex, the only possible case is that f is Ez+1 such that 2j = x² and +j+1 < 2j and monotonously increasing for > Ij+1, thus we have monotonously decreasing for
Hs = - for k < and H& = + for k > j++ ++1. Now we claim that =j = and +5+1 -: We have either (+;, t++1) = (-++) or (++++)++)) = (+. If not, we would not get a unique minimum. The second case also leads directly to a contradiction: Not only would the pre-factors of the two ReLU need to coincide, i.e., 7 7--1 (otherwise one would not have the minimum 0 0 R(x x,) $ (xr x3 cc:
between them), the analysis of f 2j S x + yields (as only the neurons at zj and 1z+1 are active there)
xz+1 R(-x + xz+1)
b 79+1 1 - x - h(x) < 1 xz+1) + 25+1 Ij + E)
Here the lower bound is b 7/+f < b, thus imprecise.
Case 3: f is not monotone and has slope nowhere. Then, there is one minimum x²' = Zj For all x; * 23 can argue before. So just need to argue about z,.. Assume we only have one ReLU involving Tz.. The only unstable ReLU leads to DP-0 lower bound O, while all others together lead
linear term az + b for some a * 0, thus the overall lower bound from DP-0 is M(x;) - lale < h(zr))- Therefore, such network cannot be precise under DP-0 analysis. As one ReLU not enough, we can try two at zy, namely 76 ReLU(x x,) and 7 ReLU z 22). As around 7/ no other ReLU active, immediately follows that we have 7/ = aj and 7/ 0j-1-
Now we finally prove that the network constructed above is precise. Consider the input S x S u. In the case where is monotone on [1, u). we have the result immediately by using Lemma 25 as all ReLU with an opposite orientation are inactive. In the case where f is on [L, u] not monotone, the above construction yields
h(w) = b
% ReLUU-((x (x-))))++
Σ
N: ReLU(x 24).
We can apply Lemma 25 to Ei, ReLU(- - x;)) and Σ +.d x ReLU(x xx) individ- ually to get
0 7i ReLUR-(e - =z)))= s
b(l) a-1 (-x + u),
=
n-1 (x - 1). 0 < Y ReLU(x - -2,) v h(w)-b
$,
Hence the combined bounds are
< hxx) S h(1) + Mww-h(l) (x 1). --1
Evaluating the upper bounds at and x u yields h(1) and hu)) respectively, hence the bounds are precise.
B.3 DEEPPOLY-1
Corollary 12 (DP-1 ReLU). The ReLU network Mxx)) + ReI.U(-x)) encodes the function
f(z) = Re)U(x) and, the DP- Danllsna of h(r) is identical to the DP-O-analysis of ReLU. Fur- ther, the DP-O-analysis of h(z) is identical to the I--lllnalysis of ReLU.
Proof. We first prove that + ReLU
(e..
x ReLU(-x) ReLU(z) ReLU(-z) ReLU(-z) ReLU(x). Next show that the DP-O-analysis of R(xr) coincides with the DP- -analssss of a ReLU(-
23

---

Published as a conference paper at ICLR 2024
Case / < 0 S [1, u/: We have for DP-0 and (xLU(x)::
0 s ReLU(x) & -0 1).
For DP-1 and
RcLU x) have:
S ReLU(--)) - --7 (x u),
Hence
0 S + (eLU(-x) -- u) + - 1).
Case 0 < u, [L u]: We have for DP-0 and ReLU(x):
ReLU(x) = x.
For DP-1 and x + ReI.U(-))) we have:
ReLU(-x) = O,
Hence
x + ReLU(--)) x.
. Case / 5 S 0, x E u]: We have for DP-0 and RcLU(x))
ReLU(x) O.
For DP-1 and x + ReLU(-x) have:
ReLU(-2) = -2,
Hence
0.
To show the opposite, we only need to prove for the case < 0 < u since DP-0 and DP-1 are identical when there is no unstable ReLU. For DP-1 and ReLU(-=)) we have:
S ReLU(-->) I - (x u),
Hence
+ ReLU(-2) - u) + 10 1).
Corollary 13 (DP-1 Approximation). Finite ReLU networks DP-1- and DP-O-express the same function class precisely. In particular, they can DP-1-express the set convex functions f CPWL(I, R) and monotone functions/ CPWL(II I) precisely.
Proof. The follows immediately with Corollary 12 and the technique presented in Theorem 11.
B.4 TRIANGLE
Theorem 15 (A Convex). Let f E CPWL(I, R) be convex. Then, for any network h encoding f as in Lemma 10, we have that its A-analysis precise. particular, I; can be chosen freely.
Proof. The A analysis of ReLU over some input range I I x u results the convex hull of ReLU that range. With that, we can apply the Lemma 14 over the network h from Lemma 10 modeling f:
h(x) b
Σ ns ReLU 21))
This is regardless of the choice of +, a sum of convex functions (7; > 0). With Lemma we get that the A analysis of ha results in the convex hull of h, and thus is precise.
24

---

Published as a conference paper at ICLR 2024
B.5 MULTI-NEURON- RELAXATIONS
MINI--EURRONRRLLAATIONS
Theorem 26 (Multi-Neuron Precision). For every / E CPWL(I, IR), there exists a single layer ReLU network encoding f. such that its multi-neuron analysis (considering all ReLUs jointly) is precise.
Proof. As the multi-neuron relaxation yields the exact convex hull of all considered neurons in their input-output space, it remains show that every f E CPWL.(T, IR) can be represented using single-layer ReLU network.
Recall that every f E CPWL((I, IR) can be defined by the points {(r, vi s.t. 2; > Zi-1 (Defini- tion 1). We set h1 (a) = (xc 20)
Mn 20 + Yo and now update as follows:
21 -u
h (x) 14(x)) +
Mi+1 D4 y/1 yi-!
ReLU(x 24)
3i+1 z2 I2 2i-1
We observe that ReLU(x =z, for all 2, such that s é. As h(x) is CPWL, it is now sufficient to show that h(x,)) = ye, Vi.
h(x;)=
(x Fo
91 + 90 To
Vi+1 Vi
D1 Vi-1
RcLU(x - xza)
01+1 Iz
24 I:-1
Mi++ Vi
y: V/-1
Vi++1
yi
V/
3/
= (zj 2o
NC + 900 + zj
Ti+
4. Ti-1
Ti
i=1
1=1
(xz-
Fo
91 vo -20
+ yo + z2j
Vý
1/
Dj y/ -1
2 Iz-1
21 20
V-+1 Vi (I:+1 w..) 21
1/1
yo
y: 1/1 1
(xt Iia)
1x+1 24
270
43 23
25


Reviews:
[{"review_id": "wZuy1jbGnJ", "reviewer": "Reviewer_FMX3", "summary": "The authors presented an analysis for special classes of convex relaxations of neural networks and their expressivity. Unfortunately, given that I am not an expert with the subject, and that the background in the paper is limited, I have trouble understanding the high level ideas of the paper. I would encourage the authors to engage with discussion, so that I can provide a proper review of this work.", "questions": "As mentioned earlier, I have many basic questions about this work. Perhaps let me start from the basics about the background of this work. \n\n1. Can the authors elaborate on how convex relaxations are helping with formal robustness guarantees? This was quickly glossed over, but I would hope to get a better explanation. \n\n2. Can the authors explain exactly what is being relaxed into a convex function? Section 2.1 reads quite confusingly for me, as all I can discern are inequalities, and I do not see which parts are being relaxed. \n\n3. When the authors write a vector is less than or equal to another vector, is this inequality entrywise? \n\n4. There are a lot of definitions in section 2.2, can the authors provide a simpler explanation of these definitions and what they are trying to capture? In particular, why is it that we care about $D$-analysis in the definition of expressivity? I would have expected expressivity of a network architecture to be about function approximation. \n\n5. At the end, it seems like the authors are investigating whether or not ReLU networks can express certain functions. I thought this was already an answered question with respect to universal approximation, but perhaps I am missing something. Can the authors explain why we need to analyze the expressivity results for these certain class of functions? \n\nPerhaps let's start here. Once we go into discussion and have a better understanding, I can follow up with more questions regarding the actual technical contributions of this work.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "I will re-evaluate the strengths after a discussion with the authors to understand the paper.", "weaknesses": "Similar to strengths, I will re-evaluate after discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FBYcztHQI7", "reviewer": "Reviewer_y6LY", "summary": "This paper studies the expressive power of ReLU neural networks under different convex relaxations that are commonly used for neural network certification. The key findings are:\n\n* For univariate functions, more precise convex relaxations like Δ and DeepPoly allow expressing larger classes of continuous piecewise linear (CPWL) functions precisely compared to the simple interval bound propagation (IBP).\n* IBP can precisely express monotone CPWL functions, while Δ and DeepPoly can also express convex CPWL functions.\n* Multi-neuron relaxations allow single-layer networks to express all univariate CPWL functions precisely.\n* For multivariate functions, even the most precise single-neuron relaxation (Δ) cannot precisely express simple classes like multivariate monotone convex CPWL functions.\n* This suggests single-neuron convex relaxations are fundamentally limited for multivariate functions, highlighting the need for more precise analysis methods like multi-neuron relaxations.\n* The results have implications for certified training, suggesting more precise relaxations could yield larger effective hypothesis spaces and higher performance if optimization challenges can be overcome.\n\nIn summary, the paper provides an in-depth analysis of the expressive power of ReLU networks under different convex relaxations, showing more precise relaxations increase expressivity for univariate functions but are still fundamentally limited for multivariate functions. The results motivate developing more advanced analysis techniques and studying their potential benefits for certified training.", "questions": "Here are my questions:\n\n* There is recent literature on the convex optimization of ReLU network, e.g., [1] and several other follow-up papers by the same authors extending this work to various neural network architectures. Can authors comment on their contributions over this work and explain how their paper supports/refutes the claim there? For example, the very first question to comment on would be: What is the point of having convex relaxations if the ReLU networks can already be trained using convex optimization?\n\n* Can authors also briefly comment on the issues raised in the weaknesses part?\n\n[1] Pilanci and Ergen, Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks, ICML 2020", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Here are some strengths of this paper:\n\n* It provides the first in-depth, systematic study on the expressive power of ReLU networks under a wide range of convex relaxations commonly used in neural network certification.\n* The analysis covers univariate and multivariate functions and simple as well as more complex function classes like (monotone) convex CPWL.\n* It clearly differentiates the capabilities of different relaxations through precise mathematical results and constructive proofs.\n* The paper relates the theoretical results back to certified training, drawing interesting hypotheses about the potential benefits of more advanced relaxations.\n* The paper is clearly structured and provides detailed mathematical proofs for all results.", "weaknesses": "Some potential weaknesses of this paper:\n\n* The focus is exclusively on ReLU networks, not covering other activation functions commonly used like sigmoid or tanh.\n* Only fully-connected feedforward networks are considered, not convolutional or residual architectures widely used in practice.\n* The analysis is limited to deterministic networks, not touching on stochastic networks.\n* Only standardized datasets and perturbation sets are studied; results may not generalize to other domains.\n* While hypotheses are provided for certified training, no experiments are conducted to validate the conjectured benefits.\n* The writing is quite dense and mathematical, which could make it less accessible to a general AI audience.\n* Aside from certified training, implications for other applications of neural network analysis are not discussed much.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JptOWTIcPP", "reviewer": "Reviewer_pT5c", "summary": "This work studies the expressive power of ReLU neural networks under various convex relaxations, by measuring their ability to represent (certain subclass of) CPWL functions. On the positive side, for univariate CPWL functions, most convex relaxation methods are shown to be able to express monotone or convex CPWL functions, and Multi-Neuron can even represent all CPWL functions. However, it's shown that all these methods fail in the multivariate case: they can't even represent the simple $\\max$ function in $\\mathbb{R}^2$.", "questions": "**Motivation for precise analysis:** it's mentioned in this work if we allow approximate analysis, for any approximation error $\\epsilon>0$ and general multivariate continuous function on $\\mathbb{R}^n$, IBP can express the function up to $\\epsilon$ error (Baader et al 20). This seems a strong enough guarantee. What's the significance of considering precise analysis beyond pure theoretical interest?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Novel direction:** the expressive power of neural networks is an interesting and important topic. This work is the first to consider such expressive power in the precise representation setting.\n\n**Wide coverage:** in the univariate setting, this work discusses a broad range of convex relaxation methods, which covers most popular ones in practice.", "weaknesses": "**Univariate is restricted:** the main weakness I found is the restricted univariate assumption. All the positive results for the expressive power of convex relaxation methods hold for univariate functions, which is restricted in two ways: (1) in practice, almost all functions of interest are multivariate (2) in theory, the case of univariate functions is too special, which often times avoids the general difficulty in high dimensions and thereby hard to generalize.\n\nOn the other hand, the negative multivariate result only holds for $\\triangle$, and the precision gap can be arbitrarily small. It's not clear whether multivariate methods can express multivariate CPWL functions precisely.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)