Topological Expressive Power of ReLU Neural Networks

We would like to thank the reviewer for the insightful review and especially for pointing at potential connections between our construction and concepts in dynamical systems used in the referenced works, as well as to the construction in Telgarksys work.

Regarding the first question, there are connections between our construction and the ones used in the mentioned references. For example, the coordinates of the cutting points (the points in our constructions that are the center of the resulting annuli) are non-periodic points of the simple triangle function(they are the points that get mapped to the fixed point $0$ after a certain number of application). Although this observation suggests a potential link between our construction and concepts in dynamical systems, we are not seeing a connection to the notion of topological entropy so far.

Regarding the second question, for $d=1$, our bounds imply the depth separation given by Telgarsky and in fact even for shallower networks (i.e., the functions inapproximable by networks of depth $k$ and polynomial size(in $k$) can be represented by networks with a depth and size of $O(k^2)$). Since we showed that our construction is robust with respect to small perturbation, this separation holds for a full Lebesgue measure set of neural networks. We believe that the reason why the bounds obtained in this way are slightly better is due to the simplicity of the analysis. Since all our connected components have a constant size and contain a point with a constant negative function value, the inapproximability by small shallow neural networks follows easily by the fact that they are not capable of expressing the same number of connected components. For general $d$, our construction differs from the one of Telgarsky in the way that we apply the triangle map in every coordinate and make use of the arising subdivision of the unit cube.

Due to the technical overlaps, we totally agree with the reviewer that it would be interesting to see whether we can use a possible connection to concepts from dynamical systems like Li-Yorke chaos and periodic points to gain a better understanding of the topological behaviour of the decision regions. On the other side, topological results like ours might also be fruitful for dynamical systems or further inapproximability results and we believe that exploring this connection more explicitly and rigorously is an interesting direction for future research.

We would like to thank the reviewer once again for the meaningful and interesting review and we would be happy to answer further questions or discuss potential deeper connections to dynamical systems.

We thank the reviewer for their valuable input. We would like to address their concerns in the same order:

1. In such a case, if $X = X^- \cup X^+$ denotes the union of the supports of the data distributions of the positive and the negative data points, the Betti numbers of $X \cap F^{-1}((-\infty,0])$ need to equal the Betti numbers of $X^-$. The construction of the lower bound is easily applicable in such a setting as well.
2. We are motivated to define the topological expressive power of an architecture as the representation of the "most complex" topology achievable by a neural network with that architecture. Consequently, our construction provides a lower bound for this concept.
3. Proposition 10 suggests that in the parameter space, there are open neighborhoods around the weight vectors that arise from our construction such that every point in these open neighborhoods also represent functions with Betti numbers at least our bounds. Therefore, it is possible to find the weight representation of such a function in the parameter space by e.g. gradient descent methods.
4. The main goal of this paper is not to suggest techniques relevant for practice, but rather to point out at theoretical barriers (or capabilities) of expressivity of a neural network. Furthermore, the topological theoretical insights might have connection to other aspects of deep learning, see e.g. the discussion with reviewer UFRF. Moreover, Betti numbers are indeed used in practice, at least in dimensions up to 2.
5. The ''exponential gap'' refers to the fact that only exponentially sized shallow neural networks can encapsulate the Betti numbers that are already achievable by linear sized deep neural networks. We can gladly elaborate further if the reviewer wishes to.
6. We have tried to keep the lower bound construction self-containing, which required multiple pages since definitions and figures had to be introduced. On the other hand, we have included a sketch for our upper bounds, missing steps being standard topological arguments. These can be found in the appendix.
7. While the extension from sigmoid activation to ReLU activation may seem incremental, it is still a significant contribution since the ReLU activation function is widely used in modern neural networks. Neither in Bianchini-Scarselli nor in our case is it immediately clear that one must imply the other. Moreover, we have extended the result to any Betti number, answering the question whether the expressivity results hold as well for ``holes'' affirmatively for any dimension.

We thank the reviewer once again, for the minor remarks in particular. Among others, the figure seems to have suffered a compilation error, which has been cleared, so that it shows the piecewise linear function $f(x)=0.5-|x-0.5|$ which we used in the first $L-1$ layers repeatedly to create the exponential number of ''holes''. We are looking forward to a discussion.

I thank the authors for further clarification. I encourage the authors to spell out the precise meaning of their notion "lower bound of" in concrete mathematical terms. It seems that this is the lower bound of a maximum of certain quantity taken over some set, but what exactly is the set over which the maximum is taken? Does this maximum depends on the architecture only, or also on the dataset $X$? If it depends on the dataset $X$ what is the meaning/effectiveness of this notion depending on $X$?

Also concerning another issue, I really encourage the authors to try to find a practical real-world case in which their results bring a novel perspective.

We thank the reviewer for their suggestions, and would like to address their concerns in the same order.

1. One standard definition of Landau symbols which is used often in complexity theory is that, given a function $f$, the terms $O(f)$ resp. $\Omega(f)$ denote sets for which $g=O(f)$ resp. $g=\Omega(f)$ (as the reviewer mentioned) would hold, see e.g. https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation. We can, however, gladly switch to the equal sign, as it seems to be the better-known variant.

2. Proposition 10 of the paper implies that there exist positive radius neighborhoods around each of our constructed functions that satisfy the same properties with respect to Betti numbers of the sublevel sets. Therefore, efficient algorithms based on e.g. gradient descent methods can be used for the detection of functions that prove our lower bounds (which also answers the reviewer's question). That being said, we agree that experiments would be an enrichment to our theoretical findings.

3. We believe that the short version of the paper is self-contained (at least with respect to the definitions and constructions) and includes all our results, and is therefore suitable for a conference. The interested reader shall be able to find the appendix online in the future.

We thank the reviewer once again and are looking forward to a discussion.