Data geometry and topology dependent bounds on network widths in deep ReLU networks

We have summarized your concerns and questions below for a detailed response.

W1, Q4. The relationship of novel terminologies used in this paper to other ideas learning theory is unclear. For instance, what is the relationship between the margin $\varepsilon$ of a "feasible architecture" on a manifold and the generalization error of that architecture on that manifold? Can you clarify the relationship of your novel terms to other terms in learning theory?

In our work, the margin $\varepsilon$ in Definition 3.1 signifies that if $\varepsilon$ is large, the data manifold may have a 'simple' polytope-basis cover, involving fewer polytopes or a smaller total number of faces. Consequently, the network architecture proposed in Theorem 3.4 suggests that 'the large margin cover can be approximated with a reduced number of neurons.' In other words, increasing the filtration value $\varepsilon$ generally leads to a decreased number of neurons, establishing a connection between generalization error and network architecture from the perspective of learning theory.

The insights from Theorem 3.5 can be grasped through a similar approach. In this theorem, we present a bound in terms of the dimension of the simplicial complex and the number of its faces. In TDA, the simplicial complex tends to simplify as the filtration value $\varepsilon$ increases, consequently, our bounds in Theorem 3.5 decrease. This highlights the correlation between the growth in the number of required neurons (the network width) and the increasing complexity of the dataset geometry.

W2. Proof of Proposition C.1 is not convincing, you assume existence of function then proe NN equals to this function. How do you know NN exists? UAP guarantees but it is what you try to prove indeed?

Here we provide detailed explanations. What Proposition C.1 demonstrates is that if we can construct a constant function with its support sufficiently 'close' to $\mathcal{X}$, then we can also construct a function whose $L^p$ distance from $1_{\mathcal{X}}$ is sufficiently small. In simpler terms, the proposition establishes that "constructing the indicator function" is more difficult than "approximating the indicator function in $L^p$ sense." This is the reason why we solved the first problem. In the revised paper, we have added some sentences to provide a more detailed understanding. Refer to the first paragraph on page 3 in the revised manuscript.

W3, W4, W6, Q2, Q3. It is clear that ReLU networks can fit polytopes exactly, but it is not clear how well they can fit arbitrary manifolds. What guarantees are there for finding a tight cover for a given manifold? How do you actually find a polytope-basis cover?

Indeed, this is the common concern raised by all reviewers. Please refer to General Comments KR1 in the overall comment for the detailed response.

W5, Q5. Missing some discussion of prior related work on relating topological characteristics to generalization theory.

We have revised the paper to have relevant comparison with prior related work. See KR2 in General comments.

W7. Many strong claims are made in this paper, and after reading the paper it's not altogether clear to me they are substantiated.

Throughout the revisions, we have improved the flow of our manuscript and emphasized our contributions. We highly recommend reviewing Section 1 in the revised manuscript for a comprehensive understanding. In summary, our main contribution lies in providing bounds on network widths that depend on the geometric characteristics of the dataset, described in terms of its polytope cover.

W8. Proposition 3.5 seems trivial.

It might be understood trivially. In the revised paper, we have moved this result to the appendix, and removed from our main contributions.

Q1. Is topological space really the right level of generality for this paper? Why not just consider manifolds? The former is substantially more general, and it appears you only consider subsets of $\mathbb{R}^{d}$.

Thank you for highlighting a crucial aspect. As you suggested, the role of neural networks in real-world applications is not merely to distinguish a data point within $\mathbb{R}^d$, but rather to establish a decision boundary against other classes. In response to your feedback, we have slightly generalized the definition of a 'convex polytope' in Definition E.1 in the revised paper. Then, our theoretical results still hold with this definition, where the setting becomes more practical.

Furthermore, we want to emphasize that our empirical findings in Appendix E demonstrate that each class in the real datasets (MNIST, Fashion-MNIST, CIFAR10) datasets can be effectively classified by a 'convex polytope' characterized by a simple number of faces. Therefore, our result in Theorem 3.4 can provide the feasible architecture of neural networks on these datasets.

As the deadline for the Reviewer-Author discussion phase is fast approaching (there is only a day left), we respectfully ask whether we have addressed your questions and concerns adequately.

Dear Reviewer J9Hi,

This is a gentle reminder as the deadline is approaching. We have tried our best to fully address your questions and concerns. In particular, we have included experiments on real datasets by providing a polytope-basis cover of real-world datasets and theoretical results to support them.

Given the limited time for author-reviewer discussion, we would appreciate it if you can answer timely manner whether your queries and concerns have been satisfactorily addressed.

Dear reviewer J9Hi,

Thanks for acknowledging our rebuttal. We are pleased to hear that you do not have any more questions. Nonetheless, we do not see the score adjustment, so we would appreciate it if you could confirm your final score in regard to our revision. If you have further questions, please let us know we are happy to engage in further discussion.

W1. Lack of applications to practical real-world datasets.

In the revised paper, we supplied empirical application of our results, involving seeking a polytope-basis cover of the real-world dataset. See General Comment KR1 in the overall comments.

W2. Paper does not provide the detail proofs in the main body, leading to bad presentation.

Thanks for the constructive comment. We moved less important proofs to the appendix, and allocated more paragraphs to highlight our key ideas. See General Comment KR 2 in the overall comments.

W3. What is the novelty of paper when establishing the lower bound, especially comparison between previous works considering used term "bent hyperplane argument"?

Thank you for the valuable feedback. We referenced the 'arrangement of bent hyperplanes' in [Hanin et al.] as the 'bent hyperplane argument' in the original manuscript to convey that we employed a similar idea to derive a lower bound on the required number of neurons. Indeed, we used this idea to explore how the decision boundary can be 'refracted' if and only if it intersects with some activation boundary of a neuron, in the proof of Proposition 3.2.

However, as there are no previous results on such a lower bound for the number of neurons based on the number of faces of a polytope, we assert that our results are novel. [Hanin et al.] and [Grigsby et al.] utilized the concept of 'bent hyperplanes' to obtain an upper bound on the number of linear regions or to investigate topological features of the decision boundary, none of which are comparable to our geometric results.

References.

[Hanin et al.] Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. Advances in neural information processing systems, 32, 2019.

[Grigsby et al.] J Elisenda Grigsby and Kathryn Lindsey. On transversality of bent hyperplane arrangements and the topological expressiveness of relu neural networks. SIAM Journal on Applied Algebra and Geometry, 6(2):216–242, 2022.

W4. The numerous allusions to topological aspects are heavily overstated. It only appears in Theorem 3.7 stating Betti numbers, with heavy assumptions on the shape.

Recognizing that our results primarily pertain to geometric rather than topological aspects, we have revised our manuscript, including adjustments to the title, to emphasize the geometric perspective rather than topological analysis. See General Comment KR3 in the General comments.

W5. Related work section does not mention vast literature on geometry and topology applications in analysis of data representations.

We have revised our paper with additional related work and detail comparison with our results. See General Comment KR2 in the General comments.

W6. Limitations regarding specific initialization for the verification of gradient descent.

Our convergence result in Theorem 4.3 demonstrates that the viability of approaching the proposed neural network through gradient descent. We want to claim that this result holds particular significance when compared to other UAP outcomes, such as those presented by [Park et al.] or [Cai], as they solely establish the existence of such neural networks without offering a convergence guarantee. Furthermore, we empirically validate that gradient descent reliably converges to the envisioned network.

Furthermore, we want to highlight that the initialization condition is adaptable to dataset characteristics and not restricted to specific configurations. It varies based on the dataset distribution, illustrated by the fact that the permissible range for $v_0$ in equations (9) or (10) can widen as $\rho$ decreases—a constant linked to data distribution. In simpler terms, this expansion happens when data points are predominantly located on the surface of the separating polytope. Thus, we propose that these initialization conditions offer a mathematical representation of the dataset's distribution quality, providing insight into its inherent 'niceness.'

References.

[Park et al.] Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin. Minimum width for universal approximation. arXiv preprint arXiv:2006.08859, 2020. [Cai] Cai, Yongqiang. "Achieve the minimum width of neural networks for universal approximation." arXiv preprint arXiv:2209.11395 (2022).

Specific remarks: Some feedback and inquiries on figures, sentences, claims, and terminologies.

Thank you for careful reading and providing beneficial comments. Below, we answer for each remark.

● page 1: The figure appearing on the article first page usually serves to highlight the principal contribution of the paper, does the standard Figure 1 with very well-known XOR dataset really serve such purpose?

We agree with the reviewers' comment, and have changed Figure 1 to highlight our contribution. We believe this will engage readers in understanding our motivation and contributions.

● page 2: "considering the given dataset as a topological space" -> considering the support of the data distribution as a topological space?

We considered the data distribution $\mathcal{X}$ as a topological space. In practice, it refers the manifold of each class in the dataset.

● page 2: "We answer this question by constructing a collection of convex polytopes..." - where is it described in the paper how to construct such collection?

The sentence would be corrected to, "We answer the question when a polytope-basis cover of $\mathcal{X}$ is given." For the construction of these covers, please refer to Section 5 of the revised manuscript.

● page 2: "forms m-simplicial complex..., we establish a novel topology-dependent bound" - the bound established in Theorem 3.6 concerning simplicial complexes is in terms of numbers of j-dimensional facets, which are not "topology-dependent" quantities.

Indeed, rigorously speaking, the dimension of a simplicial complex is not a topology-dependent quantity, despite the use of simplicial complexes to explore topological properties. What we aimed to highlight was the demonstration that the bound depends on the dimension of the simplicial complex, which may be related to the topological complexity of $\mathcal{X}$. In response to your insightful suggestion (W4 above), we have removed topological aspects in the revised paper.

● page 4: "from the volume identity of the polytope"- what is it? a reference is necessary here.

Thank you for a good comment. It means that the volume of a convex polytope is sum of the volume of small pyramids which is a partition of the polytope, which we only described in the proof in Appendix B.1.1. We allocated more space to explain this proof idea in the main body, in the revised version.

● page 5: in Theorem 3.6 "$d_1$ is bounded by" refers to the presented construction of the network, or to any 2 layer network which is feasible on X, it is not clear

The $d_1$ refers the width in the presented construction of the network, not any 2-layer. We have modified the sentence.

● page 6: "the first result on the width of neural networks in terms of topological data structure"- the result in Theorem 3.6 is in terms of numbers of j-dimensional facets, which is not "in terms of topological data structure"

This is similar to one of the previous comments above. We initially considered it to be related to topological data structure, but we have removed some sentences that might be understood as an overstatement.

● page 7: "This implies that the architecture outlined in Theorem 3.7 is dictated by the filtration parameter"- The topological space considered in Theorem 3.7 is a convex polytope with disjoint prism-shaped convex polytopes removed, it is not the Cech complex with respect to some parameter epsilon, so there is no architecture in Theorem 3.7 related to the filtration parameter.

Thank you for the significant comment. We decided to remove this part from our draft.

● page 8: "which completely classifying the given dataset " - perhaps, which classifies with zero error the given dataset?

The sentence means the classifier with zero error on the given dataset. We have modified the sentence in the revised version.

Q1. How Theorem 4.3 can be improved, for example, when the dataset is non-convexly separated or the number of classes is greater than 2?

Theorem 4.3 explains that if a two-layer ReLU network is initialized in proximity to the polytope cover, gradient descent may converge to the global minimum. This result readily extends to multiple polytopes or a polytope-basis cover. Specifically, consider a scenario with $m$ polytopes covering a single class and a three-layer network $\mathcal{T}$ as defined in Proposition 3.7, equation (5) in the revised paper. Assuming the $m$ subnetworks, denoted as $\mathcal{N}_i$, are initialized near polytopes, satisfying the conditions in Theorem 4.3. Then, we can apply Theorem 4.3 to each polytope individually. This is possible because $\mathcal{T}$ is the minimum of $m$ two-layer ReLU networks - it is important to note that the $\min$ operation in the network executes all gradients in backpropagation, except only one subnetwork for each input. This establishes the extension of Theorem 4.3 to a polytope-basis cover for three-layer ReLU networks.

Q2. Is it possible to obtain some UAP results of the 3-layer ReLU networks to approximate a compactly supported functions $f:\mathbb{R}^{d_x} \rightarrow \mathbb{R}^{d_y}$, in terms of smoothness?

Thank you for a insightful question. We obtained that it is possible. Since we proposed a method to approximate the indicator function in $\mathbb{R}^d$ by a 3-layer ReLU network, a common idea in Lebesgue theory easily generalizes this result to approximate a compactly supported functions $f:\mathbb{R}^{d_x} \rightarrow \mathbb{R}^{d_y}$. We propose the result in the appendix. See Theorem C.5 in the revised paper. As the reviewer anticipated, the width is related with the error bound and the Lipshictz constant of $f$.

Remark. Notably, (Wang et al., 2022) recently proved that 2-layer ReLU networks cannot approximate a compactly supported function in $L^p(\mathbb{R}^d)$, while 3-layer ReLU networks can. However, their proof establishes only the existence of such networks without offering any width bounds. Consequently, our result in Theorem C.5 represents a refinement of their findings. This is one example that our results on polytope can be leveraged to derive width bounds for the UAP.

Reference.

[Wang et al., 2022] Ming-Xi Wang and Yang Qu. Approximation capabilities of neural networks on unbounded domains. Neural Networks, 145:56–67, 2022.

Q3. How can your results be applied to real datasets?

In the revised paper, we supplied empirical application of our results, by constructing a polytope-basis cover of the given real dataset. See General Comment KR1 in the overall comments.

W1. The geometric structure of the given dataset (the simplicial complex or Betti numbers) looks hard to be achieved in real dataset.

To address your concern, in the revised paper, we present a way to find a polytope-basis cover for the given real dataset. See General Comment KR1 for more details of real experimental results.

W2 & W3. The abstract and certain sentences in introduction is highly recommended to be revised. Further, there are some lack of introducing related works and detail comparison.

We thank for suggesting relevant references and valuable feedback. We have revised Section 1 and 2 with additional references. See General Comment KR2 in the overall comments.

Q1. Why did the authors choose to approximate the indicator function?

Thank you for the valuable feedback. Indeed, approximating the indicator function is generally more difficult than just classifying finite classes in the dataset. However, if a neural network $\mathcal{N}$ can effectively approximate the indicator function on a given dataset class $\mathcal{X}$, it inherently possesses the capability to classify $\mathcal{X}$ from other classes. We intended to set the goal of our paper to cover not only classification tasks, but also regression tasks. We have indeed considered the MSE loss function in Section 4 (see Theorem 4.3), and we have included a simple approximation result in Theorem C.5, requested by Reviewer nRVF. See footnote 1 on page 4 of the revised manuscript for more detail.

Q2. What does the terminology `architecture' (denoted by $\mathcal{A}$) exactly mean?

In our manuscript, the terminology `architecture' refers to the structure of neural networks, specifically the depth and width of each hidden layer. We introduced a notation, $d \rightarrow d_1 \rightarrow \cdots \rightarrow d_k \rightarrow 1$, to represent a $k$-layer neural network with widths $d_1, \cdots, d_k$ in the manuscript, and we did not fix the network architecture.

As you commented, the UAP result can be achieved when the the hidden layer dimension is allowed, as presented in Theorem C.5. More precisely, the hidden widths grows $O(\varepsilon^{-d_x})$ as the error bound $\varepsilon$ reduces. Similarly, our other results (Theorem 3.2, 3.4, 3.5, 3.6) imply that the width increases as the number of polytopes and their faces increases. Precisely, Theorem 3.5 explicitly demonstrates how the width grows with the increasing complexity of the simplicial complex. We have made this part clearer in the revised manuscript (see Section 3.1 and Definition 3.1 of the revised paper).