Neural Network Expressive Power Analysis Via Manifold Topology

Thank you for your comprehensive and insightful review of our paper. We appreciate your detailed feedback and have addressed the points raised to enhance the quality and clarity of our work.

Q1. How can this theory be applied to deep learning?

Thank you for your detailed feedback and for highlighting key concerns about the practical applicability of our theoretical findings. We value your insights and would like to address these concerns in the context of our study’s objectives and contributions.

Our primary goal is not to devise a method for constructing MLPs from data. Rather, our research aims to deepen the theoretical understanding of how the topology and geometry of data manifolds influence neural network size. We accomplish this by establishing an upper bound for network size required for classifying data from different manifolds. This approach is consistent with numerous theoretical studies in the field that focus on the expressive power of neural networks. Similar works like [1, 2] have provided various upper bounds for neural network sizes in approximating distinct function families, and while these results might not directly apply to datasets, they are invaluable for enhancing our fundamental comprehension of neural networks.

The insights from our theoretical exploration shed light on the intricate relationship between the complexity of data manifolds and the requisite size of neural networks for effective classification. This enhanced understanding has significant potential to guide future research in deep learning, especially regarding the optimization of network architectures based on the characteristics of the underlying data.

Regarding the necessity and relevance of topological complexity and Betti numbers in our study, we invite you to refer to Q1 and Q3 in our summary.

In essence, while our results are rooted in theory, they form an integral part of the evolving understanding of neural networks, laying a foundation for further empirical exploration and practical application in the field of deep learning.

Q2. About the claim of contributions

We sincerely thank the reviewer for directing our attention to the paper [3], which was not previously included in our references. While this paper is indeed relevant, it does not diminish the novelty of our claim. Our work uniquely demonstrates for the first time how the topology, as a global structural characterization of data manifolds, impacts neural network expressiveness.

The study in [3] focuses on a specific category of manifolds: smooth, regular simple curves. These manifolds are characterized by being connected and non-self-intersecting, implying a uniform topology with only one connected component. Consequently, their analysis does not necessitate the inclusion of topological descriptors.

In contrast, our research encompasses a broader spectrum of manifolds with diverse topological features. The incorporation of topological complexity into our upper bound represents a pioneering effort in illustrating how varying topological characteristics of data manifolds influence the size and structure of neural networks. This aspect of our work stands as a distinct and significant contribution to the field, highlighting manifold structures and their relationship with network expressiveness.

Q3. Ambiguity of the term ‘classification’.

We appreciate your attention to the potential ambiguity surrounding the term "classification" as it pertains to both the manifold classification theorem and classification problems in machine learning. In response to your insightful comment, we have carefully revised our manuscript to include clear distinctions and explanations whenever we refer to the manifold classification theorem. This ensures that our usage of the term is precise and unambiguous within the context of our discussion.

Q4. Typos.

We are grateful to the reviewer for highlighting the typos in our manuscript. We have fixed them in the updated version.

[1] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. NeurIPS, 2019

[2] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. CoLT, 2016.

[3] Sam Buchanan, Dar Gilboa and John Wright. Deep Networks and the Multiple Manifold Problem. ICLR 2021.

Thank you for your detailed review and valuable feedback on our manuscript. We appreciate your insights and have addressed the points you raised as follows:

Q1. Limited experimental section.

We are grateful for your insightful suggestions regarding the experimental aspects of our work. Your feedback highlights important areas for potential expansion and improvement.

We would like to clarify that the core contribution of our paper is the establishment of an upper bound, as detailed in our main theorem. This result stands on its own merit, grounded in rigorous mathematical proof. Therefore, the necessity of experimental validation for this specific aspect of our work is not as critical, since the theorem is proven through theoretical methods.

That said, the inclusion of the experimental section was motivated by an intriguing observation: in certain settings, the impact of topological complexity, as predicted by our theorem, becomes quite apparent. We acknowledge that these findings may not be universally applicable across all settings. However, the mere existence of settings where the topological complexity bound is observed to be tight serves as a compelling illustration of our theoretical results.

We understand your perspective on the breadth of experimental validation and appreciate the opportunity to consider how our work might be further enriched. We believe this discussion enhances the understanding of our work's scope and its application in various contexts.

Q2. Ambiguity of the Term "Classification".

We appreciate your attention to the potential ambiguity surrounding the term "classification" as it pertains to both the manifold classification theorem and classification problems in machine learning. In response to your insightful comment, we have carefully revised our manuscript to include clear distinctions and explanations whenever we refer to the manifold classification theorem. This ensures that our usage of the term is precise and unambiguous within the context of our discussion.

Q3. Limitation of manifold’s dimension.

Please refer to Q2 in our summary response.

Q4. Topological complexity and network depth.

Thank you for highlighting the comparison with the findings in Naitzat, et al. 2020. We would like to clarify that our results do not contradict their experimental outcomes. Firstly, our analysis indicates that the size of the neural network, in terms of the total number of neurons, is proportional to $\beta^2$, focusing on the overall network size rather than just its width. It's a common understanding that the size of a neural network can exceed its depth, which aligns with our findings.

Secondly, while Naitzat et al. 2020 [1] observed that the topological complexity of internal representations decreases with network depth, this aligns with the expectation in classification tasks. Typically, the final outputs are binary (0/1), leading to a collapse of topological complexity at the middle layers of the network. In contrast, our work specifically examines how the initial topological complexity of input manifolds influences the overall size and depth of a neural network. Our focus is on the input side of the network, rather than the evolution of topological features within the network layers.

We believe these clarifications underscore the distinct yet complementary nature of our work with respect to the study by Naitzat et al. 2020.

[1] Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim. Topology of deep neural networks. JMLR, 2020.

We thank the reviewer for the thoughtful comments. We would like to address your questions with the following discussions.

Q1. Manifolds in three dimensions or less are too easy.

The complexity of low-dimensional manifolds (3 or lower) should not be underestimated. It is not true that if a theory does not hold in low-dimensional cases, then it won’t hold in general. They differ from high-dimensional manifolds (5 or higher) in the theoretical framework. Low-dimensional manifolds often present unique complexities and challenges in analysis. Please refer to Q1 in our summary response.

Q2. Betti numbers are not accessible from point clouds.

Contrary to the belief that Betti numbers are inaccessible from point clouds, they can indeed be accurately computed from sufficiently dense samples. For more information, please see our detailed response to Q3 in the summary.

Q3. Is the goal of this paper to suggest the value of considering topology?

Our paper emphasizes the intrinsic role of topology in classification problems. We discuss this further in response to Q1 in the summary, addressing the reviewer's concerns about the prior knowledge of the data manifold's phase.

Q4. Real neural networks do not work as the construction in the paper.

We aim to establish an upper bound on network complexity in classification scenarios. And the methodology is to prove by construction. While classification neural networks may not function as a straightforward homeomorphism followed by a classifier, the derived upper bound remains valid, suggesting that real networks could have fewer parameters. Building an upper bound on the size of neural networks to analyze its expressive power is a common approach in many theoretical papers, like [1, 2].

Q5. The assumption in this paper seems to be that the classes of classification are disjointed. Is that a realistic setting?

The assumption that classes in classification are disjoint is both intuitive and realistic, as overlapping manifolds would imply ambiguously labeled points, which is uncommon. This theoretical setting is also employed in other studies, such as [3].

Q6. It would be more appropriate to discuss this in a setting such as expressive learning.

We appreciate the suggestion to frame our discussion in the context of expressive learning. Typically, neural network expressiveness is analyzed through function approximation under assumptions of continuity or smoothness, as in [2]. However, classification involves discontinuous real functions, presenting greater analytical challenges due to their less favorable properties.

[1] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. CoLT, 2016.

[2] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. NeurIPS, 2019

[3] Sam Buchanan, Dar Gilboa and John Wright. Deep Networks and the Multiple Manifold Problem. ICLR 2021.

We greatly appreciate your thorough review and constructive feedback on our work. Your insights have been invaluable in enhancing the clarity of our work. Below, we address the points you raised.

Q1. Assumptions on manifolds’ dimensions.

The constraint to manifolds with dimension $d \leq 3$ may appear overly restrictive at first glance. However, it's important to emphasize that the analysis of 3-dimensional manifolds is far from trivial. These manifolds present unique complexities and require intricate theoretical approaches. For a more detailed discussion on this, please refer to Q1 in our summary response.

Q2. Suggestions on the manuscript.

We are grateful for your insightful suggestions regarding the proof sketch, typos, and references. In response, we have thoroughly revised and updated our manuscript to reflect these valuable inputs.

Q3. Is solid manifold a concept developed in this paper?

Yes, in our study, we use the term 'solid manifolds' to describe manifolds that meet our specific assumptions. This terminology is adopted for clarity and to facilitate the proof process.

Q4. What manifold classification theorem was actually used?

In the proof of Lemma 1, we use the classification theorem for closed 1-manifolds and the classification theorem for closed surfaces.

Q3. The Betti number is not accessible for data as a point cloud.

In [3], it has been demonstrated that a manifold's homology can be accurately reconstructed from a sufficiently dense sample of points. Once the homology group is determined, the computation of Betti numbers, which reveal the quantity and types of holes in a manifold, becomes relatively straightforward. Therefore, employing Betti numbers in analytical processes is generally straightforward and effective. However, the primary challenge often lies in acquiring a data sample that is dense enough. Such sufficient sample density is a fundamental requirement in manifold hypothesis studies like those seen in [4], where the results depend critically on manifold properties like curvature or injective radius. These properties, not directly inferable from point cloud data, are often presupposed as known characteristics of the underlying manifold.

This presumption underscores a significant gap in our capacity to fully comprehend manifold structures from sparse datasets, thereby highlighting the necessity for more robust methodologies in manifold learning. These methods must adeptly navigate the common challenge of data limitations. Nevertheless, the theoretical bounds discussed in these studies are far from redundant. They lay down a vital theoretical framework, deepening our understanding of the structures latent in point clouds. This fundamental insight not only drives the development of algorithms but also aids in evaluating the quality of point cloud representations, effectively bridging advanced theoretical concepts with their practical applications. Moreover, these bounds serve as a catalyst for future research, particularly in adapting and applying them more directly to point cloud data.

[1] Itay Safran and Ohad Shamir. Depth-width tradeoffs in approximating natural functions with neural networks. ICML, 2016.

[2] Sam Buchanan, Dar Gilboa and John Wright. Deep Networks and the Multiple Manifold Problem. ICLR 2021.

[3] Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 2008.

[4] Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. NeurIPS, 2010.

Q2. Manifolds with dimensions of 3 or lower than 3 are too easy and have few applications.

Understanding the structure of low-dimensional manifolds (specifically in 3 and 4 dimensions) present greater challenges compared to their high-dimensional counterparts (5 dimensions and above). While 1-dimensional and 2-dimensional manifolds are relatively simpler, the complexity escalates with 3-manifolds. This is exemplified by the famous Poincaré Conjecture for 3-manifolds, which took a century to prove and asserts that every simply connected, closed 3-manifold is homeomorphic to the 3-dimensional sphere.

In four dimensions, the situation is even more intricate. Unlike the three-dimensional case, where Thurston's Geometrization Conjecture (proven by Grigori Perelman) offers a comprehensive framework, four dimensions lack a similar unifying conjecture. This complexity is partly due to the existence of exotic $\mathbb{R}^4$s, which are differentiable manifolds homeomorphic, but not diffeomorphic, to the Euclidean space $\mathbb{R}^4$.

For manifolds of five dimensions and higher, certain aspects of the theory are simplified, thanks in part to the h-cobordism theorem and surgery theory. The h-cobordism theorem, applicable to manifolds of dimension five and above, facilitates understanding their structure by stating that cobordant manifolds under certain conditions are diffeomorphic. However, these tools don't provide a complete classification of high-dimensional manifolds. The problem of determining whether two high-dimensional manifolds are homeomorphic is as complex as the word problem in group theory, which is known to be undecidable.

Given these complexities, studying manifolds of dimension higher than four requires a fundamentally different approach. It is not feasible to leap into high-dimensional cases without thoroughly understanding the lower-dimensional (3D and lower) scenarios. Presently, the literature only focuses on special cases like $\mathbb{R}^d$ balls [1] and smooth regular simple curves [2]. Our work lays the groundwork for future exploration into the high-dimensional realm, recognizing the distinct methodologies required for these advanced studies.

We also appreciate the reviewers' insights on the practical relevance of low-dimensional manifold theory. This area of study is indeed pivotal in many real-world scenarios where high-dimensional data is frequently simplified into lower-dimensional (2 or 3 dimensions) representations for more effective analysis and visualization. Techniques such as Principal Component Analysis (PCA), t-Distributed Stochastic Neighbor Embedding (t-SNE), and Uniform Manifold Approximation and Projection (UMAP) are deeply rooted in the principles of low-dimensional manifold theory. These methods are crucial in transforming complex, high-dimensional data into comprehensible and actionable forms.

Contrary to the view that low-dimensional manifolds may be less relevant, many datasets widely used in machine learning and computer vision intrinsically exhibit 2 or 3 dimensional manifold structures. A prime example is the MNIST dataset, comprising handwritten digits, which can be considered to reside on a manifold with a dimension much lower than its ambient space. This lower-dimensional representation captures the essential features of the data, facilitating more efficient processing and analysis. Similarly, the LineMOD (LM) dataset, which is integral to object recognition and pose estimation tasks, underscores the importance of understanding the underlying low-dimensional manifold. Grasping the structure of these manifolds is not only theoretically insightful but also practically essential for the development of effective algorithms.

In light of these examples, low-dimensional manifold theory emerges not just as a theoretical curiosity but as a fundamental tool in data analysis and algorithm development.