Depth-Bounds for Neural Networks via the Braid Arrangement

We thank the reviewer for carefully reading and evaluation our paper and for the positive and encouraging feedback.

This paper is extremely heavy in notations which makes it very hard to follow. I acknowledge that the notations are overall clearly defined and I do not immediately know how to simplify the notations but it really makes the reading hard currently.

Thanks for sharing this impression. We are happy to implement any concrete suggestion on how to improve this issue, including your comments below.

The setting of this work is quite restrictive: it applies to a single activation function and focuses on a setting which requires exact representation of the target function.

Our results can be transferred to any activation function that is piecewise linear (including ReLU, leaky ReLU, maxout, ...). You are correct in that they don't apply to smooth activation functions. In our current version, our results do not imply anything for approximation, but we see the exact representations as a necessary base case, that is already substantially non-trivial.

This work focuses on exact representation of the target function. Have you thought about a similar lower bound on the depth when allowing for some approximation error with the target?

See above.

At lines 107-109 you state that you disprove the conjecture with a counter example in dim 6. Do you think that the conjecture could still hold asymptotically with the same bound up to constants?

It could be either way, we do not want to make a guess at this point.

It would be valuable to add a conclusion section to wrap-up your results.

We will do this, see also our discussion with Reviewer jBBb.

line 67: what does "integral" weights" mean?

It means that all weights are in $\mathbb{Z}$.

line 89-90: could you link to the lemma or proposition that proves the "observation is that the set of functions that are representable by a B0d-conforming network forms a finite-dimensional vector space"?

This is implied by Prop. 2.2. We are happy to add such a reference.

line 110-112 Does it constitues a matching upper-bound to your lower bound? If yes, it could be nice to highlight it.

Unfortunately, the problem setups are slightly different, so while morally the two bounds match, this is not a formal match.

line 165: "fan" was not defined?

We will add a definition: A fan is a polyhedral complex in which every polyhedron is a cone anchored at the origin.

line 179: do you denote $F=\Phi\circ f$ here? If yes it would be good to add it.

Not exactly: the meaning is that $\Phi(f)$ is defined as the set function $F$ that sends $S$ to $f(1_S)$. We will make this clearer in the final version.

line 190: Do you denote $[n]_0 = [n]\cup 0$?

Yes

line 194: what is the * in $(R^L)^*$?

It is a standard notation for the dual space, the set of linear functions mapping from $R^L$ to $R$. We will add an explanation.

line 199: if I understand well $\sigma_M$ is a function, and hence should be $F(S)$. But don't we expect $F(S)$ to be scalar?

This is indeed a typo. $F(S)$ is a scalar, as you say. The formula should not contain the $\sigma_M$, it should just be a linear combination of the $\lambda$s.

line 226: should you add $S_n\subset[d]?

Yes, this can be added here.

Paper Formatting Concerns: The font used seems different than the usual Neurip format font.

You are correct and we are sorry about this. By accident, we loaded the package lmodern, which changes the font. But our font takes up more space than the usual NeurIPS font, so we do not overshoot the page limit when changing it back to the NeurIPS font. In contrast, we will even have a little bit of additional space for the final version.

We thank the reviewer for carefully reading and evaluation our paper and for the positive and encouraging feedback.

Weaknesses: The main theorem proved in the paper is conditional on the structure of the neural network, so a complete solution to the desired problem is still missing. However, the exceptional difficulty of this combinatorial problem makes this perhaps inevitable.

We agree with your estimation of the situation.

I think that there is a typo on line 70. It seems that the required depth of the network grows as $N\rightarrow \infty$, which doesn't make sense since the restriction on the weights is now weaker. Should the $\log N$ be in the denominator?

Yes, this is a typo, d and N should be exchanged in the expression. Thanks for pointing it out.

We thank the reviewer for carefully reading and evaluation our paper and for the constructive feedback.

Weakness: Absence of empirical verification on its main results (even on vanilla examples of fully connected networks, see Suggestions).

Our work is fundamental research on the expressive power of ReLU networks, and as such of theoretical nature. Many related previous papers published at top-tier ML conferences are purely theoretical papers, including the cited papers by Hertrich et al. 2023; Haase et al. 2023; Averkov et al. 2025. We agree that an empirical verification would be a nice add-on, but designing it in an insightful way would be nontrivial and is beyond the scope of our paper.

1. Could one empirically confirm that a ReLU network with l < log log d layers fails to approximate max{0,x_1,...,x_d}? How would you test this?

See response above.

2. Are there concrete examples where the Ω(log log d) lower bound is actually tighter for specific values of d or other specific cases?

We are not aware of tight examples. The best upper bound is singly-logarithmic in d. Nevertheless, our lower bound is the first proof of a non-constant lower bound, and as such a big step towards matching upper and lower bounds eventually.

3. Is it possible to prove more generally that for certain rank vectors, the expressivity of maxout networks indeed exceeds the bound given by $\prod_i r_i$?

Our result can be stacked: by alternating $\ell$ rank-2 and $\ell$ rank-3 layers, one can compute the maximum of $7^\ell$ numbers. We are, however, not aware of a more general construction of this type.

This paper presents reliable theoretical analysis and establishes a novel lower bound related to the depth on the expressivity of ReLU networks within specific conditions. However, it lacks empirical verification, even on simple network architectures such as fully connected networks, which limits its significance. As such, it is difficult to consider it a theoretical contribution with substantial impact. If the authors could provide experimental results to support the $\omega(\log \log d)$ lower bound in a future revision, the paper would have strong potential for acceptance. Moreover, while the definition of B_d-conforming networks is theoretically well-defined and precise, the main claims would be significantly strengthened if the authors could empirically demonstrate—or at least provide some examples—showing that real-world neural networks tend to exhibit such structure, either inherently or approximately. Establishing this connection would enhance the practical relevance of the proposed lower bounds and make the results more compelling to a broader audience. Otherwise, the current submission resembles a combinatorial-algebraic exploration whose contribution falls short of the standards for acceptance at NeurIPS.

See above. We kindly disagree and think that the theoretical contribution alone is a significant contribution to the NeurIPS audience.

Finally, although the main results of this paper are clearly presented, I could not find a summary or discussion of the work, particularly regarding its limitations, despite the authors' claim in the checklist that such limitations and conclusions are discussed. If I have misunderstood or overlooked this, I would appreciate clarification.

Thanks for pointing this out. While we think that all assumptions, implications, and limitations are appropriately discussed around the theorem statements in the introduction, we are happy to include a specific paragraph summarizing these points. In such a paragraph we are also happy to discuss potential approaches for empirical verification, as you suggest.

We thank the reviewer for carefully reading and evaluation our paper and for the positive and encouraging feedback.