Multi-Neuron Unleashes Expressivity of ReLU Networks Under Convex Relaxation

However, the paper’s main results appear unsupported.

Incorrect Lemma Lemma 3 claims that ReLU neural networks transform polytopes into polytopes. Here is a simple counterexample: consider the polytope $P=[-1,1]$ and the CPWL function $f \colon R^1 \to R^2$ given by $x \mapsto (x,\max${$x,0$}$)$ which can clearly be computed by a 2-layer neural network. Then, $f(P)$ is not a polytope since it is simply the graph of the ReLU function. The issue in the proof is that it concludes that applying the ReLU function to a polytope results in intersecting the polytope with the half-spaces $y \geq 0$. However, this is not the case; the ReLU function maps everything not in the positive orthant to its boundary, which may result in a nonconvex set.

Since the results for both relaxations $M_3$ and $M_{d_{in}+3}^o$ rely on this lemma, the paper’s main results appear unsupported.

Lack of Precision Aside from Lemma 3, the rest of the paper also lacks precision, which made it challenging for me to fully understand the remaining results and verify their correctness. For example:

• The definition of $M_{k}^o$ is unclear. The paper states: “Concretely, $C(x, \rho(x))$ is in the form of {$C(\rho(x_I )) | I \subseteq [d], |I| \leq k$}, and only one index set $I$ is allowed per layer as well." This set appears to range over all possible $I$, but it then states that only one index set $I$ is allowed, which seems contradictory. While I think I understand what is meant, a precise formal definition of the central objects of study would be desirable.
• Moreover, if I understood correctly, the relaxations depend on the set $I$ of output neurons chosen to compute the convex hull of its function values. This should be reflected in the notation to avoid ambiguity.
• In the proof of Theorem 2, the justification for the second equality in the last equation is missing. Although it seems intuitively correct, it is challenging to verify formally given the lack of precision in the definition. Could you provide a more detailed proof of this step?

The presentation of the results need a lot of work. The concepts and results are presented in a backward way with the main results presented first with a lot of unclear terminology and then the preliminaries are presented later. For instance, one needs to read till Section 6 to understand what an unstable neuron is, and the proof of the main result in Section 4 refers to Lemma 1 which states that there exists a ReLU network $\Phi$ of width $d_{in} + 3$ with at most 3 unstable neurons per layer. The word "completeness" is used in place of "full expressivity" without clear definition in many places. The proofs are not written very clearly and are not easy to follow. I would suggest creating a preliminaries section where the basic definitions like "stability" and "bounded stability" are clearly defined and basic lemmas like Lemma 1 are clearly stated with the proofs in the appendix. This should be augmented with Section 3 and done before Section 4 and Section 5. There is no experimental evaluation. For the experimental evaluation, one use single-neuron and multi-neuron relaxations with several different neural network architectures, ranging in width and depth, to show that the computed bounds are exact. This has potential to be a good paper but it needs better presentation of the results and more experimental evidence.

1. Something that I am not convinced about is the proof of Theorem 2 and Lemma 3. I think there is a flaw in the proof and we have a counterexample.

Flaw in the proof: In the induction step we assume that the case of $L = 2$ is proved. However, as we assume that all depth of $\leq L-1$ is proved, it should imply that $3 \leq L$. This means that the case of $L = 2$ should have been proved as a part of the base case, and a counterexample occurs here.

Counterexample: Let $L = k = d_{in} = d_{out} = 2$. Let $X = \{(x, y)\ |\ -2 \leq x+y \leq 2, \ -4\leq x-y \leq 4 \}$. Also $W_1 = W_2 = I$. Then, $f(x) = \rho(x)$ is a network ended with an affine layer. Also, $X$ is a convex polytope. However, $f(X)$ is given as

which is not convex. This also becomes a counterexample of Thm 2, because $\mathbb{M}^{o}_{k}(f,X)$ is convex.

Probably there is a misunderstanding in the proof or the statement of the theorem that I did not fully grasp. However, currently I believe this is the flaw of Thm 2 and Lemma 3, and as Thm 6 uses Thm 2, most parts of the proof should be fixed. Even so, section 7 is true, which I believe is an important result.

• The area of neural network certification is at least motivated by the practical problem of proving robustness of a network's output to the specified perturbation, in particular in classification (Szegedy 2014). The lack of implementable algorithms or even complexity of computing such a relaxation is concerning. There are some appealing points made in the discussion of section 8 such as avoiding BaB procedures, but the impact of this paper would be much greater if more details were provided towards an implementation. Without this, I'm left unsure about the concrete impact for the ICLR community or it may be outside of my own current scope.