A Theoretical Study of Neural Network Expressive Power via Manifold Topology

We sincerely thank the reviewer for their detailed feedback and thoughtful questions. Below, we address the specific points raised in the review.

1. Clarity of the problem setup and manifold. We appreciate the reviewer’s feedback regarding the clarity of our problem setup. In response, we have revised the manuscript (e.g., Line 72) to explicitly state that our study focuses on the data manifold. Regarding the placement of the ReLU network definition, we deliberately introduced it within the problem setup section to minimize the use of mathematical notation in the introduction. We believe this approach enhances the paper’s readability by using conceptual language to explain foundational concepts, such as neural network size, before delving into more technical details. This structure aims to make the paper more accessible to a broader audience.
2. Investigation on other crucial elements such as the optimizer, task and the network architecture. We acknowledge the reviewer’s concern about the narrow focus on network size in relation to data manifold, without considering other factors such as the optimizer, task, and network architecture. Our work focuses on providing foundational insights into the interplay between data manifold (topology and geometry) and network expressiveness. We agree that a broader framework incorporating factors like optimization dynamics and task-specific requirements would be essential for a more comprehensive understanding of expressiveness. This is an exciting avenue for future research, and we will highlight this limitation and potential extensions.
3. Betti numbers are quantities that are somehow hard to work with. For a detailed response, we kindly refer the reviewer to Point 3 of our summary response.
4. Can we have a better name for 'topological complexity' The term topological complexity (Definition 2 in our paper) is directly adopted from [1], where it is defined as the summation of Betti numbers across all dimensions. In another work [2], a vector of Betti numbers (representing different dimensions) is referred to as homological complexity. As Betti numbers represent the ranks of homology groups, we have maintained consistency with prior terminology. However, we are open to suggestions for refining the terminology further to improve clarity.
5. Empirical validation of the bounds. For details on the empirical validation of the bounds, we kindly refer the reviewer to Point 1 of our summary response.

We hope these responses address the reviewer’s concerns and provide clarity on the contributions and limitations of our work. Thank you again for your valuable feedback, which has been instrumental in improving our manuscript. Please feel free to reach out with any additional questions or suggestions.

[1] Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim. Topology of deep neural networks. The Journal of Machine Learning Research, 21(1):7503–7542, 2020.

[2] William H Guss and Ruslan Salakhutdinov. On characterizing the capacity of neural networks using algebraic topology. arXiv preprint arXiv:1802.04443, 2018.

We sincerely thank the reviewer for their constructive questions and valuable insights. Below, we address the specific points raised in the review.

1. Computational Complexity of Betti Numbers Please kindly refer to Point 3 in our summary response.
2. Applicability to Other Objectives (e.g., Regression) We thank the reviewer for this insightful observation. Our current framework is tailored to classification tasks, focusing on the expressiveness required to approximate indicator functions of manifolds, where $f: M \to \\{0, 1\\}$. However, the methodology can indeed be extended to regression problems by considering the approximation of continuous functions defined on the manifold, where $f: M \to \mathbb{R}$. The approximation of such functions has been studied in [1], which provides a foundation for exploring this extension within our framework (disentangling of data geometry and data topology). Furthermore, it is widely recognized that approximating discrete indicator functions can be more challenging due to their discontinuities. Indicator functions require the network to partition the manifold sharply, which often demands a higher level of expressiveness and complexity. In contrast, continuous functions are smoother and can often be approximated with simpler architectures.
3. High-Dimensional Data and Sampling Challenges We appreciate the reviewer’s concerns regarding Proposition 3 and the challenges of high-dimensional sampling. The “curse of dimensionality” is a well-recognized limitation in machine learning theory, highlighting the importance of the manifold assumption—that high-dimensional data often lies on a lower-dimensional manifold. This assumption is fundamental to theoretical studies like ours. In Proposition 3, the dimension $d$ refers to the intrinsic dimension of the manifold, which is typically much smaller than the ambient dimension. While the sparse sampling characteristic of real-world data can pose challenges for directly recovering the underlying manifold, we note that the principal curve framework (discussed in Point 2 of our summary response) assumes a simplified data manifold. This approach makes it feasible to estimate manifold properties even with limited samples, such as MNIST, addressing some of the practical limitations.
4. Clarification on Network Size Our definition of network size is adapted from [2], where it is defined as the number of hidden neurons, or equivalently, the sum of the hidden layer dimensions, rather than the total number of parameters. This definition yields a more concise value that is both tractable and well-suited for analytical purposes. The term $w_{k+1}$ refers to the dimension of the output space, rather than the hidden layer dimensions. For this reason, it is not included in the calculation of the network size under our definition. This distinction ensures consistency with prior work and facilitates clear theoretical analysis.
5. Theoretical Insights Beyond Practicality Our work provides a formalization of the interplay between geometry (e.g., condition number) and topology (e.g., Betti numbers) in determining the expressiveness of neural networks. This formalization underscores the influence of topological complexity in shaping neural network architectures. By focusing on classification tasks, we introduce a tractable theoretical framework that disentangles the impact of manifold topology and geometry on network size. Importantly, this framework extends beyond classification and can be applied to other machine learning tasks, such as regression or feature learning (see Point 3 in our response to Reviewer CbQd).

We hope our responses address the reviewer’s concerns and clarify the scope and contributions of our work. Thank you again for your thoughtful feedback, which has been invaluable in improving our submission. Please let us know if there are any further questions or points requiring clarification.

[1] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. In Advances in Neural Information Processing Systems, 2019.

[2] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In ICLR, 2018.

We sincerely thank the reviewer for their detailed feedback and valuable insights. Below, we address the specific points and questions raised in the review.

1. Practical Relevance and the Role of Thickened 1-Manifolds. We appreciate the reviewer’s concern regarding the practical relevance of thickened 1-manifolds. Thickened 1-manifolds were chosen as they provide a simple yet representative family of manifolds for theoretical analysis, and their structure aligns well with the latent representations observed in real-world datasets. As discussed in Point 2 of our summary response, the concept of principal curves [Hastie and Stuetzle, 1989] aligns with our framework, where the thickened 1-manifold represents a plausible approximation of the data’s supporting set. To provide further clarification, we have added a synthetic experiment (see Point 1 of our summary response). This experiment uses a binary classification task on synthetic datasets generated from thickened 1-manifolds, verifying the tightness of our bound. Additionally, we highlight the feasibility of estimating Betti numbers of real-world datasets in Point 3 from our summary response.
2. Reconciling Topology (Betti Numbers) and Geometry (Condition Number). Consider a manifold $M$. A binary classifier can be modeled as a function $f: M \to \mathbb{R}$, where the manifold’s topological and geometric properties are simplified into a one-dimensional real representation. To achieve successful classification, the classifier must inherently account for all the manifold properties—both topological and geometric—that were collapsed in this process. This is why both topology and geometry are crucial for determining the expressive power of a neural network. However, for manifold reconstruction, the function acts as a homeomorphism. In this process, the topology of the manifold is preserved, but geometric characteristics, such as the condition number, are altered. This is why works in manifold recovery [1,2] only present geometric characteristics in their results. In our theoretical framework, we disentangle the contributions of manifold geometry and topology to the classifier $f$. We achieve this by constructing a neural network $h$ that first learns a homeomorphism mapping the original manifold $M$ to a simplified manifold $M’$ with trivial geometric features (e.g., a uniform curvature). The fact that a homeomorphism alters the condition number of a manifold is a critical insight linking the condition number to the size of $h$. We then construct another network $g: M’ \to \mathbb{R}$, which works as a classifier. Since the geometric features of $M’$ have been simplified (e.g., reduced to structures like balls and tori), the size of $g$ is primarily determined by the topology of $M’$, such as its Betti numbers. The overall classifier $f = g \circ h$ is thus a composition of $g$ and $h$, combining their respective roles in handling the manifold’s topological and geometric complexities.
3. Relation Towards the ICLR 2016 Work. The paper “Depth-width tradeoffs in approximating natural functions with neural networks” focuses on the role of depth in neural networks. Specifically, it demonstrates that a 2-layer neural network with a size exponential in $d$ cannot approximate the indicator function of a $d$-dimensional unit ball, whereas a 3-layer neural network can achieve it with a size of d^2 . Their work emphasizes the depth-width tradeoff in a specific setting. In contrast, our work investigates the relationship between network size and the topology and geometry of the data manifold. While there is some overlap in focus, our work is not a generalization of the ICLR 2016 paper. Instead, we adapted their theory regarding the approximation of a $d$-dimensional unit ball as a proposition to support our theorem, which examines how the topology of the data manifold (e.g., Betti numbers) influences neural network size. Therefore, our work explores a broader scope that includes both geometric and topological properties, and as such, direct comparison with the ICLR 2016 work is not applicable. However, we have provided empirical validation of the tightness of our bound, as discussed in Point 1 of the summary, further highlighting the practical relevance of our theoretical contributions.

We hope these clarifications address the reviewer’s concerns and help illustrate the scope and practical implications of our work. Thank you again for your valuable feedback, which has significantly helped us strengthen our submission.

[1] Hariharan Narayanan and Partha Niyogi. On the sample complexity of learning smooth cuts on a manifold. In COLT, 2009.

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

I thank the authors for their clarifications to all the points raised by the referees. I have particularly appreciated the validation on a proof-of-concept example, that now they have added to their paper. I now understand the play between the topology (Betti's numbers) and the geometry (curvature linked with condition number). However I maintain to 5 my overall judgement, since I still think that more validation is necessary.

We sincerely thank the reviewer for their supportive feedback and valuable comments. Below, we address the specific points raised.

1. Is there empirical evidence that real datasets can be modeled as 1-manifolds? Please refer to Point 2 in our summary, where we provide reasons to support our belief that the proposed thickened 1-manifold family is representative of data manifolds.

2. The geometric and topological characteristics they use are also somewhat random. We appreciate the reviewer’s concern. We chose reach (or condition number) and total Betti numbers as the geometric and topological characteristics based on established literature and studies. The reach represents the minimum over the entire manifold and captures the overall flatness of a manifold, rather than focusing on a single point. This measure has been widely used in fields such as surface reconstruction [1] and manifold recovery [2, 3]. The total Betti numbers characterize the topological complexity of the manifold. These have been employed in [4], where an empirical study explores the variation in topological complexity across neural network layers. We believe these metrics provide meaningful insights into the interplay between manifold properties and neural network size.

3. Why is TDA not used in this paper? This is an important question. We agree that topological data analysis (TDA) tools, such as persistent homology (PH), capture much richer information than Betti numbers and could potentially offer more precise bounds for network size. However, despite promising empirical evidence linking PH with model performance [5], to the best of our knowledge, no theoretical network size bound based on PH has yet been established. We view this paper as an initial step towards exploring this direction.

We hope these clarifications address your concerns, and we thank you again for your insightful comments, which have helped us improve our work. Please let us know if there are any further points we can address.

[1] Nina Amenta and Marshall Bern. Surface reconstruction by voronoi filtering. In Proceedings of the fourteenth annual symposium on Computational geometry, pp. 39–48, 1998.

[2] Hariharan Narayanan and Partha Niyogi. On the sample complexity of learning smooth cuts on a manifold. In COLT, 2009.

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

[4] Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim. Topology of deep neural networks. The Journal of Machine Learning Research, 21(1):7503–7542, 2020.

[5] Guss, W. H., & Salakhutdinov, R. (2018). On characterizing the capacity of neural networks using algebraic topology. arXiv preprint arXiv:1802.04443.

I thank the authors for their clarifications to all the points raised by the referees. I have particularly appreciated the validation on a proof-of-concept example, that now they have added to their paper. Thanks to their clarification, I now understand the play between the topology (Betti's numbers) and the geometry (curvature linked with condition number). I have then raised to 3 soundness, however I maintain to 5 my overall judgement, since I still think that more validation is necessary.

We sincerely thank the reviewer for their detailed feedback and thoughtful suggestions. Below, we address the specific points and questions raised in the review.

1. Empirical justification of the upper bound. Please refer to point 1 in our summary, where we provide an example of network size with varying topological complexity.

2. On the Upper Bound Dependency. We appreciate the reviewer’s observation regarding the potential influence of the condition number on dependencies related to manifold dimensions. The dependency introduced by the condition number arises primarily due to the high sample requirements necessary to accurately recover the manifold. However, in real-world data, samples tend to be sparse, and the estimated condition number is typically small. Under the manifold assumption that the intrinsic dimension $d$ is low, and given that the condition number $\frac{1}{\tau}$ estimated from real-world datasets is generally small, the impact of the term $\tau^{-d^2/2}$ is less significant than it might appear at first glance. We believe these considerations help contextualize the dependencies in our bounds and their applicability to practical scenarios.

3. Relevance to other research topics, such as representational learning and metric learning,. Our work introduces a framework for studying the relationship between data manifolds and neural network size. While our theoretical results are focused on classification tasks, where data topology plays a critical role, this framework can be extended to other domains, such as regression and feature learning. For example, in [1], the authors empirically investigate the topology changes of neural activations across layers. Building on this idea, our framework and the thickened 1-manifold assumption could be adapted to analyze the number of neurons required to reduce a specific level of topological complexity in these settings. We believe this adaptability underscores the broader relevance of our work and its potential applications in representational learning, metric learning, and beyond.

We hope these clarifications address your concerns, and we thank you again for your insightful comments, which have helped us improve our work. Please let us know if there are any further points we can address.

[1] Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim. Topology of deep neural networks. The Journal of Machine Learning Research, 21(1):7503–7542, 2020.