A Theoretical Study of Neural Network Expressive Power via Manifold Topology
Authors: Jiachen Yao
Lingjie Yi
Mayank Goswami
Chao Chen
Venue: Accepted by TMLR ()

Abstract: A prevalent assumption regarding real-world data is that it lies on or close to a low-dimensional manifold. When deploying a neural network on data manifolds, the required size, i.e., the number of neurons of the network, heavily depends on the intricacy of the underlying latent manifold. While significant advancements have been made in understanding the geometric attributes of manifolds, it's essential to recognize that topology, too, is a fundamental characteristic of manifolds. In this study, we investigate network expressive power in terms of the latent data manifold. Integrating both topological and geometric facets of the data manifold, we present a size upper bound of ReLU neural networks.

Published in Transactions on Machine Learning Research (Apr/202)
A Theoretical Study of Neural Network Expressive Power via Manifold Topology
Jiachen Yao Stony Brook University
jaceyoo@@s..sonngrrook.
Lingjie Yi Stony Brook University
chris. dhris..i@@stongboookeeee edu
Mayank Goswami
mayonk.isi@@gmail.com
CUNY Queens College
Chao Chen Stonyy Brook University
cheo. chen. 1 www.nisstttoooooo.oooooo edu
Reviewed on OpenReview: https: //
// openreview. net/ forum? id- gRAj2uf485
Abstract
A prevalent assumption regarding real-world data is that it lies on or close to a low-dimensional manifold. When deploying a neural network on data manifolds, the required size, i.e., the number of neurons of the network, heavily depends on the intricacy of the underlying latent manifold. While significant advancements have been made understanding the geometric attributes of manifolds, it's essential to recognize that topology, too, is a fundamental characteristic of manifolds. In this study, we investigate network expressive power in terms of the latent data manifold. Integrating both topological and geometric facets of the data manifold, present size upper bound of ReLU neural networks.
1 Introduction
The expressive power of deep neural networks (DNNs) is believed to play a critical role in their astonishing performance. Despite a rapidly expanding literature, the theoretical understanding of such expressive power remains limited. The well-known universal approzimation theorems (Horuik) 1989 Cybenko, 1989 Leshno et al. 1993 Hanin 2017) guarantee that neural networks can approximate vast families of functions with an arbitrarily high accuracy. However, the theoretical upper bound of the size of such networks is rather pessimistic; it is exponential to the input space dimension. Indeed, these bounds tend to be loose, because the analyses are often oblivious to the intrinsic structure of the data. Real-world data such as images are believed to live in a manifold of a much lower dimension (Roweis & Saul 2000 van der Maaten & Hinton 2008 Jolliffe & Cadima, 2016). Such manifold's structure can be used to achieve better bounds of network size. It has been shown that the network size can be bounded by exponential of the manifold's intrinsic
dimension rather than the encompassing input space dimension (Chen al. 2019 Schmidt-Hieber 2019).
However, the intrinsic dimension is only small part of the manifold's property. It is natural to ask whether other properties of the manifold, such as topology and geometry, may lead to improved bounds. [Safran & Shamir (2016) demonstrate that to approximate the indicator function of a d-dimensional ball, one only needs a network of size quadratic to d. However, this work assumes a rather simplistic input. To extend to a more general setting, one needs to incorporate the topology and geometry of the manifold into the analysis.
Early rescarch has probed the geometry and topology manifolds. Notably, Fedorer 1959 :
Amenta
Bern (1998) introduce pivotal curvature measure, which adeptly captures the global geometric nuances of manifolds and has been embraced in manifold learning studies (Narayanan & Niyogi
2009 Narayanan &

---

Published in Transactions on Machine Learning Research (Apr/2025)
Mitter 2010
Ramamurthy et al. 2019 On the topological front, descriptors like Betti numbers have been formalized in the language of algebraic topology to characterized the numbers of connected components and holes of a manifold (Hatcher 2002 Bott et al. 1982 Munkres 2018 Rieck et al. 2019). In their seminal work, Niyogi et al. (2008) integrate manifold's geometry and topology, sctting forth conditions for topologically laithful reconstructions grounded in geometric metrics.
With the advent of the deep learning era, there has been a burgeoning interest in discerning the interplay between network size and manifold's intrinsic structural attributes. Existing studies (Dikkala et al.) 2021 Schonsheck et al., 2019) bound network size with the geometry of manifolds. However, theoretical framework that successfully integrates network size and topological traits has not yet been developed. This is a missed opportunity. The topological complexity of manifolds plays a crucial role in the learning problem, particularly concerning network size. Empirical findings (Guss & Salakhutdinov 2018 Naitzat et al.) 2020) suggest that even with similar geometry, data with larger topological complexity requires a larger network. These empirical obscrvations highlight the need for a thcorctical analysis that examines how manifold topology and geometry interact with network size. Addressing this need poses a significant challenge, as incorporating topological descriptors into the current analytical framework is inherently difficult due to the discrete nature of topology.
In this paper, we address this gap by presenting an innovative theoretical framework that integrates topology with neural network size. We tackle the challenge by first approximating a homeomorphism to disentangle the geometry and topology of a manifold. Notably, manifold topology remains invariant under a homeomorphism. This allows us to simplify the geometric complexity while maintaining the topological complexity. We then successfully represent discrete topological complexity as a combination of the complexities of basic topological shapes, thus overcoming the challenge posed by the discrete nature of topological descriptors. The resulting upper bound is obtained by constructing a neural network that first learns a low-dimensional embedding of the imput manifold, followed by classification in the embedding space. This approach aligns with modern neural network design principles.
Our theoretical result reveals for the first time how the data topology, as a global structural characterization of data manifold, affects the network expressiveness. The beauty of the theorem is that it explicitly bounds the network size with both topology and geometry, giving us insights as to how the two important manifold properties affect lcarning. To capture the manifold's topology, we use the classic Betti numbers, which measure the number of connected components and holes within the manifold. For geometric measure, we use the reach introduced by Federer [1959]; Amenta & Bern (9988), describing the manifold's overall flatness. See Figure D for illustrations of these measures,
Our main theoretical result summarized informally below; the formal version is presented Theorem 2.
Main Theorem. (Informal) Let M C. RPD be d-dimensional manifold (d S D) from a family of thickened 1-manifold and has two classes. There exists a ReLU network classifier 9 with depth at most O(log B + log +)
and size at most O + (t))(12) such that with large probability, the true risk of g is small. 3 is the sum of Betti numbers and 1 is the inverse of reach.
According to our bound, the network size scales quadratically in terms of the sum of Betti numbers B. Conversely, in terms of 1, it scales O (()) This bound reveals interesting insights. The growth of network size is only affected by Betti numbers quadratically. Meanwhile, the network size can be affected by condition number more significantly when the intrinsic manifold dimension is high. These insights can be the foundation for future development of tighter bounds, and potentially inspire new designs of network architectures that capitalize on data's intrinsic manifold structures.
In the following section, discuss related works and compare our derived bounds with those previously established. In Scction B we define the problem and introduce the concept of the thickened 1-manifold family. At first glance, this family may appear overly restrictive; however, we will explain why it actually represents a broad and versatile class of manifolds. In Section [] we present our theoretical findings, detailing the step-by-step derivation of our bounds. Our results establish a new theoretical perspective that can stimulate further exploration into the expressiveness of networks. Looking ahead, this theory could inform the design of more efficient neural networks by leveraging insights from manifold topology and geometry.
2

---

Published in Transactions on Machine Learning Research
(b) Figure 1: Illustration of Betti numbers and reach. (a) A 2-manifold embedding in R& with 80 1, = 0. (b) A 2-manifold embedded in R with 90- = 11 = 3. (c) A 1-manifold with large reach. (d) A 1-manifold with small reach, which is the radius of the dashed circle.
(a)
(c)
(d)
2 Related Works
Network size with manifold geometry. Multiple studies have formulated network size bounds across varied manifold learning contexts based on geometry. [Schonsheck al. (2019) establish bound of D(LdDe-d-d12( 1 e)) on the network size for manifold reconstruction tasks. L is the covering number terms of the injectivity radius, a geometric property. They utilize an auto-encoder, denoted as D o E, for the reconstruction of manifold. Both the encoder E and the decoder D are designed to function homeomorphisms. As result, the overarching objective is the construction of homeomorphism within the same space, which elucidates the absence of topological considerations in their outcomes, Our findings include not only the homcomorphism but also the classification network, with the latter being influenced by the manifold's topology. Chen et al. (2019) demonstrate the existence of a net of size O(e-d/n log _ + D Dlog _ + D D) that can approximate any smooth real function supported on a compact Riemannian manifold. In this context, n denotes the order of smoothness of the function. Their primary objective to illustrate that, in manifold learning, the manifold dimension chiefly determines network size, with only marginal dependence on the ambient dimension. Moreover, their smoothness assumption is inapplicable to classification tasks, where the target function lacks continuity. Yet, the interplay between manifold properties and their impact on network size in manifold classification largely remains unexplored.
Classifier learned on manifold. Dikkala et al. (2021) investigate network size in classification contexts. However, their foundational assumption is that a manifold's 's essence can be distilled into just two parameters: a centroid and surrounding perturbation. They further assume there is a sensitive hashing property on manifolds. These assumptions are quite constrained, might not align with real-world complexities, and also overlooks the intrinsic properties of the manifold. Nevertheless, the aforementioned studies predominantly concentrate on network size and geometric traits, neglecting the equally critical role of topological features.
Buchanan et al. (2021) establish lower bound on the size of classifiers for inputs situated on manifolds. However, their theoretical framework is restricted to smooth, regular simple curves; it fails to account for complex manifold structures. Chhng et al. (2018) focus on three types of manifolds: manifolds with strictly smooth convex hulls, manifolds of convex polytopes, and ring manifolds. They generate generic bounds on the manifold separability capacity using linear separation. Guuss & Salakhutdinov (2018) provide empirical evidence showing that classifiers, when trained on data with higher Betti numbers, tend to have slower convergence rates. They also highlight that with rising topological complexity, smaller networks face challenges in effective learning. These findings underscore the need for more comprehensive theoretical understanding.
There are some intriguing studies not primarily centered on manifold learning. Specifically, Bianchini & Scarselli (2014) establish a bound for the Betti number of a neural network's expression field based on its capacity. Nevertheless, their proposed bound is loose, and it exclusively addresses the regions a network can generate, neglecting any consideration of input manifold. [Safran & Shamir (2016) explore the challenge of approximating the indicator function of unit ball using ReLU network. While their primary objective is to demonstrate that enhancing depth is more effective than expanding width, their approach has provided valuable insights. Naitzat et al. (2020) empirically examines the cvolution of manifold topology as data traverses the layers of a proficiently trained neural network. We have adopted their concept of topological complexity. number of studies, such as those by Hanin & Rolnick (2019) and Grigsby & Lindsey (2022), concentrate on exploring the potential expressivity of neural networks. However, these works primarily focus on the network's inherent capabilities without extensively considering the characteristics of the input data. Theoretically, BBiddl et al. (2021) Andreeva et al. (024) propose persistent homology generalization
3

---

Published in Transactions on Machine Learning Research (Apr/202)
bound that accounts for the topology of the training trajectory. They propose comprehensive metric that encompasses the neural network, optimization process, and network activations. In contrast, our work focuses specifically on approsimating the indicator function of the data manifold using a neural network and studying the relationship between neural network size and the properties of the data manifold.
3 Preliminaries
Topological Manifolds. In this paper, we focus on a specific class of manifolds called the thickened I-manifold family, which are derived from operations 1-manifolds. To lay the groundwork, we begin with the concept. of a manifold. An n-dimensional manifold is topological space where every point has a neighborhood that is homeomorphic (topologically equivalent) to R". And an n-manifold with boundary allows for points that have neighborhoods homcomorphic to the half-space Ry0 x RR-1, For example, a circle (s') ) is a 1-manifold without boundary, known as a closed manifold, while a line segment (I') a 1-manifold with boundary.
Thickened 1-manifold. Our manifolds of interest are those obtained through operations on 1-manifolds, particularly when they are 'thickened' to higher dimensions. Specifically, consider d-thickened 1-manifolds, which are (d + 1)-dimensional manifolds homeomorphic to M x Bá, where M is compact 1-manifold (with or without boundary), and 8 denotes a d-dimensional closed ball. Figure illustrates the 1-thickened I-manifold. According to the classification theorem for 1-manifolds, M is homeomorphic to either closed interval I' or a circle S Consequently, a 1-thickened 1-manifold homeomorphic to either 1 x B or 5 B!
#
Figure 2: Illustration of connected sum.
Connected Sum and Disjoint Union. To construct more complex manifolds from simpler ones, we utilize operations such the connected sum and disjoint union. The connected sum of two closed manifolds M and N, denoted M # N, is formed by removing small open ball from each manifold and then gluing them together along the resulting boundary sphere. The disjoint union M U combines two manifolds by considering them together without connecting them. These operations yield new compact manifolds that combine the topological features of the original manifolds. Although the connected sum of thickened 1-manifolds differs from the standard definition of the connected sum for closed manifolds mentioned earlier, utilize the fact that the boundary QM of thickened 1-manifold M is closed manifokd. The connected sum of two thickened 1-manifolds is defined by performing the connected sum their boundaries and extend the gluing to the interiors of identifying corresponding points in the neighborhoods adjacent to the removed sphere. The formal definition of connected sum is provided in section A.1 Figure illustrates the connected sum between thickened 1-manifolds.
With the tools defined above, we can now define the thickened 1-manifold family, which is the class of manifolds we will study in this paper.
Definition (Thhckened 1-Manifold Family). Let M represent a compact 1-manifold (with or without boundarg). d-thickemed 1-manifold a (d + 1) -)manifflld homeomorphic to M² Bd, The family of d d-thickened I-manifolds, denoted by M, includes all such manifolds obtained via finite operations of connected and disjoint union.
The proposed thickened 1-manifold family may appear straightforward at first. However, homeomorphisns, connected sums, and disjoint unions greatly enhance its expressivity, enabling a broad range of topolog- ical constructions. A homeomorphism allows the manifold to be smoothly deformed without. altering its
4

---

Published in Transactions on Machine Learning Research (Apr/202)
1-Manifold
1-thickened 1-Manifold
|=B
Homeomorphism
r
g1''' A
Homeomorphism
S1
Figure 3: An illustration of the 1-thickened 1-manifold in 2D space. The top row shows manifold that has the same homotopy type closed interval 71, while the bottom shows manifold that is homotopy equivalent to circle St. The 1-thickened 1-manifold lamily contains all manifolds that can be obtained through the disjoint union and connected sum of these manifolds.
fundamental topological properties, thus accommodating diverse geometric shapes. Connected sums introduce additional "handles" or loops by merging two manifolds along shared boundaries, while disjoint unions allow multiple manifolds to cocxist independently. These operations can yicld manifolds of higher genus (e.g., multiple "holes") or several distinct loop-like components. As illustrated in Figure even single homeomorphism can significantly transform a manifold's embedded shape. Notably, all manifolds that can contracted into skeletons belong the thickened 1-manifold family. Examples include knots, multi-gemus tori, and various high-dimensional "patches" formed through these constructions. Many real-world objects, such cups, tires, and tables, also fall within this family due to their topological equivalence to thickened I-dimensional structures. However, spheres in three-dimensional space are excluded, thickened 1-manifolds only support non-trivial 0- and 1-dimensional Betti numbers, preventing the existence of üigher-dimessions holes. While this assumption restricts the lypes of shapes considered, it also simplifies the computation of high-dimensional Betti numbers in real data. In fact, the concept of principal curves (Hastie & Stuet- where data are assumed to cluster around a low-dimensional (ID) manifold underscores the practicality of focusing on thickened 1-manifolds.
zle 1989
Betti numbers. We employ Betti number Bx(M) to quantify topology of manifold M. 1 is the dimension of that Betti number. o-dimension Betti number Bo(M) is the number of connected components in M, and (MM) (k 2 1) can be informally described as the number of k-dimensional holes. 1-dimensional hole is a circle and 2-dimensional hole is a void. For the sake of coherence, we defer the formal definition of Betti numbers to Appendix A.1 Following Naitzat et al.] (2020), we utilize the total Betti number of M as its topological complexity. The topological complexity we employ here the topological complexity of data manifolds, instead of the topological complexity of neural networks used in Andreeva et al. (2024).
Definition 2 (Topological Complexity). M is a d-dimensional manifold. Bx(M) is the k-dimensional Betti number of M. The topological complerity defined as
B(M) Σ Ba(M). k=
(1)
Reach and condition number. We then introduce metrics that encapsulate these geometric properties. For a compact manifold M, the reach 7 is the largest radius that the open normal bundle about M of radius is embedded in Rd i.e, selfintersection.
5

---

Published in Transactions on Machine Learning Research AArr2223)
Definition 3 (Reach and Condition Number). For compact manifold M C RD, let
G E R p. q M, + q, x pl = |x qll
(2)
inf yEM
||x |x-xxll yll).
The reach of M is defined r(M) = infx x- y-l-- The condition number is the inverse of the reach.
Niyogi et al. 2000)) prove that the condition number controls the curvature of the manifold at every point. A modest condition number 1/T signifies a well-conditioned manifold exhibiting low curvature.
Problem sctup. In this paper, we examine the topology and geometry of manifolds in the classification setting. We have access to training dataset ((xx,0)){x E M, [4]]=>> where M -ن M₁. Each sample is drawn i.i.d. from a mixture distribution μ L. disjoint manifolds with the corresponding label. For the simplification of notation, we build our theory binary classification. It can be extended to multi-class without efforts in a one vee-verses-all setting. In binary case, the dataset is {(x,, 8i) E M, E {0, 13 where M = MM MM E TRP. M₁ and Mo are two disjoint d-dimensional manifolds representing two classes. The label yi is determined by the indicator function
(1, XEMi, {0, otherwise.
[x)
33)
A neural network h(x): : TRD - [0, 1] approaches the classification problem by approximating the indicator function IM₁ (x). In the scope of this study, we focus on neural networks utilizing the RcLU (Rectifiod Linear Unit) activation function.
Definition (Adapted from Arora et al. (2018)): ). A ReLU mulli-layer feed-forward network h R R with is + layers is defined
(xx) = hat1 o h2 ... hx(x),
(4)
where hy R - R ha(x) a (W,x b,) for 1 I S h. ReLU layers, and ha41 TR
Rw++1 ( = WK+1X bR+1 is a linear layer. is the ReLU activation function. The depth of the ReLU network is defined as ls + 1. The width of the ReLU network is max(wi...... wy). The size of the ReLU network is Σ 1 W;:
The approximation error of a ReLU network is determined by the truc risk.
Definition (Approximation Error). Let's consider the indicator function IM, for a manifold Mi in a binary classification problem where M = Mi U Mo- A neural network operates as a function l(x): : M - R. The approzimation error of the neural network h then defined as:
True Risk: R(h)- [ (h- (h-IMi)?u Mxx)xx
(5)
P.. is any continuous distribution over M.
4 Main Results
In this section, we explore how the topology of manifolds influence network size classification scenarios. Our results, derived methodically through construction, follow two steps. First, we approximate homeomorphism between the imput manifold and latent one; second, carry out classification within this latent manifold. This latent manifold is designed to have simple geometric features, akin to those found in spheres and tori, while retaining the intrinsic topological characteristics of the original manifold. By design, the first phase is purely geometric, as the topological traits remain unaltered, while the subsequent classification phase is predominantly topological. Consequently, the required network size can be delineated into two distinct parts. We employ Betti numbers and the condition number as metrics gauge topological and goometric complexities, respectively. Specifically, Betti numbers quantify the number of connected components and holes within the manifold, whereas the condition number characterizes the manifold's overall curvature.

---

Published in Transactions on Machine Learning Research Apr/2222)
4.1 Complexity Arising from Topology
To focus on the topological aspects rather than the geometric intricacies of the manifold, our attention shifts to the elemental shapes that typify the thickened 1-manifold collection. Among these shapes are the d-dimensional balls, denoted as (c),,, and the solid d-tori, represented by T. The d-dimensional ball, (c), is characterized by a radius and is centered at c, mathematically defined
Bx(c) ExER* || cll2 r)
On the other hand, the solid d-torus, r. embodics a gemus11 torus with a tunnel radius of r and a tunnel center radius R2 centered at c. Its formula given by
2
RC))
x EERR (aa-ca)² +
Σ a - a)2
5
It's pertinent to acknowledge that the general structure of a d-torus becomes significantly more complex as increases. The provided equation for T represents only one of its potential configurations. Nevertheless, this depiction suffices within the context of the thickened 1-manifold ensemble.
Lemma (Topological Representative). Let M C M be a d-dimensional manifold from the thickened I-manifold family. There erist a set of my d-balls B = (c:)) and a set of m2 solid d-tori = (TY,R, (c)) such that M is homeomorphic to the union (UBES B) U (UreT T), where my + m2 S 3(MM) is a constant integer. We term M' = (UBER B) U (UTeT')) as the topological representative of M.
ma
Given the classification theorem of 1-manifolds, compact 1-manifolds without boundary are homcomorphic to a circle, while compact 1-manifolds with boundary are homeomorphic to a closed interval. Therefore, the thickened 1-manifolds are homcomorphic either a solid torus or ball. Our preliminary analysis focuses on the network size associated with d-balls and d-tori. Using this as foundation, we then explore how various topological configurations of thickened 1-manifold impact the size of neural networks. Proposition determines the network size required to approximate a Rd ball. While the original result is found in Safran & Shamir (2016). our study utilizes fewer parameters and offers different way to approximate the threshold function. Proposition outlines a network size bound for the approximation of a solid torus.
2
Proposition 1 (Approximating Rd Ball, adapted from Theorem 2 in Safran & Shamir 2016 Given >>00 0, there erists a ReLU network h d + R with 3 layers and with size at most 4d 2d + 2, which can approrimate the indicator function Ing within error R(h) S c for any continuous distribution μ(x).
Proposition 2 (Approximating a Solid Torus). Given e > 0, there erists a ReLU network h E - IR with 5 loyers and with size at most 2d (A(d +) + 8 + v + 9, which can approzimate the indicator function Ins within error R(h) S for any continuous distribution p(x). F
Both proofs begin by expressing the indicator function composition of truncated power functions. Each truncated power function can be approximated by a piecewise lincar function, which can be precisely represented by ReLU layer. The composition of these power functions is then thresholded, and this threshold function can also be approximated by another ReLU layer. The overall approximation error is estimated across these two steps. Proposition and 2 address the network size associated with approximating B and T Detailed proofs can be found in the Appendix A.3. Building on this, we can infer the network size for approximating topological representatives by combining the complexities of approximating D and Ted with those of union operation. This consolidated insight is captured in Theorem
Theorem 1 (Complexity Arising from Topology). Suppose M' is the topological representative of d-manifold from the thickened 1 1-manifold family. Given e >>> 0, there exists a ReLU network h TRd + R with depth at most Olog 8) and size at most O df that can approzimate the indicator function IM with error R(h) $ for any continuous distribution μ over Rdd, B is the topological complexity of M'.
7

---

Published in Transactions on Machine Learning Research (Apr/2025)
Since a topological representative is the union of balls and solid tori, the overall network size is computed by summing the network sizes required to approximate the balls and tori, along with the network size needed for the union operations. The detailed proof can be found in Appendix [A.4 This theorem offers an upper bound on the network size required to approximate the indicator function of a topological reprosentative. It is important to note that this captures the full range of complexities arising from the topology of a manifold M E M, given that M and M' are homcomorphic. To the best of our knowledge, this is the first result. bounding neural network size in terms of manifold's Betti numbers.
4.2 Overall Complexity
For general manifolds in M E M, due to their inherent complexity, often defy explicit expression. This hinders the direct use of function analysis for approximating their indicator functions, as was done in previous studies. To tackle this issue, we construct a homeomorphism, continuous two-way transformation, between M and its corresponding topological representative M'. This method only alters the geometric properties, preserving the object's 's topological attributes. Therefore, the network size in approximating the indicator function of M is constructed by the approximation of the homeomorphism and the classification of topological representatives. The network size of constructing the homeomorphism is exclusively influenced by the geometric properties, whereas the network size of classifying topological representatives pertains solely to topological properties. The latter we already figured in previous section. This methodology enables us to distinguish the influence of topology and geomelry of manifold on classifiers. In this section, we aim to obtain the overall network size for a classifier.
To build a homcomorphism from M, we first need to recover the homology of M. The subsequent proposition outlines a lower limit for the number of points essential recover the homology of the initial manifold M.
Proposition 3 (Theorem 3.1 in Niyogi et al. (2008)). Let M be a compact d-dimensional submanifold of D with condition number 1/T. Let X = {x1, X2. .n. be set of n points drawn in i.i.d. fashion according to the uniform probability measure on M. Let 0 < E< 2. open subset of RDD Then for all
Let U ===l UxEx (x) be a corresponding random
> (log((22) + logt
(8)
U is a e-cover of M, and the homology of U equals the homology of M with high confidence (probability > 1 8). Here
vol(M)
vol(M)
\1 =
)oll and d2 = voo
(9)
8 arcsin(e/8r) and 02 = arcsin(e/161) vol( denotes the d- d-dimensional volume of the standard d-dimensional ball of rudius e. vol(M) is the d-dimensional volume of M.
This result stipulates a lower bound for the training set size necessary to recover the homology of the manifold, which is the foundation to learn the homeomorphism between a manifold M E M and its topological representative M'. However, directly construct ing this homeomorphism remains challenging. As a workaround, we develop a simplicial homeomorphism to approximate the genuine homeomorphism. Notably, this simplicial approach lends itself readily to representation via neural networks.
Combined with the topological representative classification network in Theorem we can construct a classification network for general manifolds in M, as depicted in Figure 4 Initially, we project M to its simplicial approximation |K] using a neural network Ny- This is succeeded by network N₂ that facilitates the simplicial homeomorphism between [K] and [4], the latter being the simplicial approximation of the topological representative M'. Finally, network h is utilized to classify between [A, and LTol- Consequently, the network's 's size is divided into two main parts: one focused on complexities related to geometric attributes and the other concerning topological aspects. This distinction separates topology from geometry in classification problems.
In Theorem we design such neural network based on this training set, ensuring that approximation errors are effectively controlled. The detailed proof is provided in Appendix A.5. Our proof strategy begins with
8

---

Published in Transactions on Machine Learning Research (Apr/202)
the construction of a ReLU network, followed by evaluation of the network's size. Subsequently, we place bounds on the involved approximation errors.
N
N
R
1
M2
141
Figure 4: Construction of the network g. The network first learns a performs classification in the embedding space. This paradigm mirrors the typical operation of deep networks. While the diagram illustrates only the process for the manifold of the positive class, the procedure for Mu mirrors this operation identically.
embedding and then
Theorem 2 (Main Theorem). Let ME-M- J.M C. R be d- d-dimensional manifold from the thickened i-manifold family. M2 and Mo are two disjoint sub-manifolds of M representing two classes. The condition number of M is + and the total Betti number of .M is 3. Given training set {(x;, y:)|x; E M, ys E [0,1))== where x; are sampled i.i.d. from M by uniform distribution, and ys = IM,,).), (x:). For any O, if émequality { holds, then for any > 0, there erists ReLU network g with depth at most O(log B + dlog?, & + log log 1 and size at most 0 dB + --- log Tō + +D log 24) such that
P(R(g) S <6)>1-1
(10)
where R(g) Im(9 IM,) I with any continuous distribution μ.
Proof Sketch. Since = M L. from thickened 1-manifold family, has a topological representative =M=M,, M'j C Rd, d where Mi and Mý are topological representatives of .M and Ma; respectively. The proof follows Figure 4 by first constructing simplicial approximations |K] and [L] of M and M', respectively. Then represent simplicial homeomorphism Ø | + LT by neural network No, where K is constructed from M and L from M'. Built on the top of this, a projection from M to its simplicial approximation |]] is represented by another net welwork N,- The overall network can be constructed by is completed by first constructing the network 9, and then bounding the approximation error.
o N₂ N₂- The proof
Upon examining the depth and size of the neural network, it bocomes evident that the topological complexity, denoted by B, and the geometric complexity, symbolized by т, are distinctly delineated. Note that result provides upper bound on the network size required to achieve given classification error rate and may not necessarily be tight. However, our empirical validation suggests that the topological component of the bound has the potential to be tight in practice. While this bound serves a theoretical guarantee, it the distinct factors that contribute to the complexity of the network. The topological complexity contributes O (1 )²) the overall network size. In contrast, geometry contributes
also offers valuable insights into
o (r & /2 loga/2 d/2 1/2 + Dr log )
5
Experiments
In this section, we present numerical results that showcase our topological bound O 8 Even though this bound is derived through construction and serves as an upper limit, it intriguing to discover that the bound is tight and can be readily obscrved experimental settings. In practical scenarios, when training networks of varying sizes on data drawn from manifolds with different total Betti numbers B, and achieving the same error rate, anticipate linear relationship between the network size and B².
in fixed dimension.
9

---

Published in Transactions on Machine Learning Research (Apr/202)
5-0
300
55% centidecce imaral
0 150-
2449
200
120
(a) Solid torus of genus 1.
(b) Solid torus of genus 2.
(c) Relation between network size and 8
Figure Validation of topological complexity bound. We utilize manifolds characterized as solid genus-g tori, with g spanning from 1 to 10. For cach torus, we consistently sample 10* points from surrounding bounding box that cover the torus. The labels for these points are generated using the indicator function of the solid torus. (a,b) are two examples of gemus-g tori, but samples from the background class are not visualized in the gruph. (c) showcases the linear regression results between the network size and the square of topological complexity. A 5-layer neural network with adaptive width trained to fit tori of varying genus 9. The width of the network is increased until the training accuracy can exceeds 0.95 when the MSF loss converges. This regression underscores pronounced linear association between network size and 8², with correlation coefficient 0.9698.
We utilize manifolds characterized as solid genus-g tori, with g spanning from 1 10. Each genus-g torus is synthesized by overlapping two identical tori. For each torus, consistently sample 10a points from a surrounding bounding box. The labels for these points generated using the indicator function of the solid torus.
For training, we deploy a 5-layer ReLU network, gradually increasing its width until the training accuracy surpasses 0.95. Figure 5c presents a regression line charting the relationship between network size and the squared topological complexity, 8 This regression underscores a pronounced linear association between network size and 82, with correlation coefficient 0.9698.
5 S-O1p")
95% Cun fidence interval
820
8C0
400
The tori used in the previous experiment were sampled using Equation 7 with parameters = 3 and r= To investigate the impact of geometric properties, we shrink the inner radius to r 0.5, effectively increasing the condition number 1. We then repeat the same experiments
(L9R31" 01.003
113734
these modified tori for genus to 10, as shown in Figure 0 The results continue to indicate linear relationship between network size and f Compared to Figure [c]] learning a torus with the same genus but a larger condition number requires a larger network, highlighting the impact of geometric complexity on work expressivity.
20
40
60
80
100
120
Figure Relation between network size and B² with larger condition number.
6 Conclusion
In this study, we delved into the intricate relationship between network size, and both geometric and topological characteristics of manifolds. Our findings underscored that while many existing studies have been focused on geometric intricacies,
important also approciate the manifold's topological characteristics. These characteristies not only offer an alternative perspective on data structures but also influence network size in significant ways.
10

---

Published in Transactions on Machine Learning Research (Apr/202)
Our proposed network size bounds represent theoretical upper limits, meaning that real-world implementations may yield efficiencies beyond these confines. To attain a more direct and refined theoretical bound, we may need more comprehensive descriptors of manifolds that go beyond merely the Betti numbers and the condition number. We leave this exploration for future work. We hope that our study acts as a catalyst for further research, pushing the boundaries of manifold learning and applications modern Al systems.
Acknowledgments
This research is partially supported by National Science Foundation (NSF) grants CCF-2144901, the National Institue of Health (NTH) grants ROINS 143143, and the Stony Brook Trustees Faculty Award. This research is also partially supported by NSF CCF-2503086.
References
Nina Amenta and Marshall Bern. Surface reconstruction by voronoi filtering, In Proceedings of the fourleenth anmual symposium on Compulational geomelry, pp. 39 48, 1998.
Rayna Andreeva, Benjamin Dupuis, Rik Sarkar, Tolga Birdal, and Umut Şingekli. Topological generalization bounds for discrete-ting stochastic optimization algorithms. Advances in Newral Information Processing Systems, 2024.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018.
Marshall W. Bern, L. Paul Chew, David Eppstein, and Jim Ruppert. Dihedral bounds for mesh generation in high dimensions. In ACM-SIAM Symposium Discrete Algorithms, 1995.
Monica Bianchini and Franco Scarselli, On the complexity of neural network classifiers: A comparison between shallow and deep architectures. IEEE Transactions on Neural Networks and Learning Systems, 2014.
Tolga Birdal, Aaron Lou, Leonidas J Guibas, and Umut Simsekli. Intrinsic dimension, persistent homology and generalization in neural networks. Advances in Neural Information Processing Systems, 2021.
Raoul Bott, Loring W Tu, et al. Differential forms in algebraic topology, volume 82. Springer, 1982.
Sam Buchanan, Dar Gilboa, and John Wright. Deep networks and the multiple manifold problem. In International Conference on Learning Representations, 2021.
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.
SueYeon Chung, Daniel D Lee, and Haim Sompolinsky. Classification and geometry of general perceptual manifolds. Physical Review X, 8(3):031003, 2018.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314 1989.
Nishanth Dikkala, Gal Kaplun, and Rina Panigrahy. For manifold learning, deep neural networks can be locality sensitive hash functions. arXim:2103.068: 2021.
Herbert Edelsbrunner and John L Harer. Computational topology: introduction. American Mathematical Society, 2022.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In 29th Annual Conference on Learning Theory, 2016.
Herbert Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418-45) 1918, 1959.
11

---

Published in Transactions on Machine Learning Research (Apr/202))
Rocio Conzalez-Diaz, Miguel Angel Gutiérrez-aaramjo, and Eduardo Pahzo-Hidalgo. Two-hidden-layer feedforward neural networks are universal approximators: A constructive approach. Neural networks the official journal of the International Neural Network Society, 2019.
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, 2022.
William H Guss and Ruslan Salakhutdinov. On characterizing the capacity of neural networks using algebracc topology. Xiv preprint arXiv:1802.0444 2018.
Boris Hanin. Approximating contimuous functions by relu nets of minimal width. ar preprint
1rXiv:1710.111 710.11278. 2017.
Boris Hanin and David Rolnick. Complexity of lincar regions in deep networks. In International Conference on Machine Learning, 2019.
Trevor Hastic and Werner Stuetzle. Principal curves. Journal of the American statistical association, 84(406): 502-516, 1989.
Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002.
Kurt Hornik. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359 366, 1989.
Ian Jolliffe and Jorge Cadina. Principal component analysis: A review and recent developments. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 374:20150202, 04 2016.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867) 1993.
James R. Munkres. Elements of algebraic topology. CRC press, 2018.
Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim. Topology of deep neural networks. The Journal of Machine Learning Research, 21(1):7503 7542, 2020.
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In Advances in Neural Information Processing Systems, 2010.
Hariharan Narayanan and Partha Niyogi. On the sample complexity of learning smooth cuts on manifold. In COLT, 2009.
Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrele & Compulational Geomelry, 2008.
Karthikeyan Natesan Ramamurthy, Kush Varshncy, and Krishnan Mody. Topological data analysis of docision boundaries with application to model selection. In Proceedings of International Conference on Machine Learning, 2019.
Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, and Karsten Borgwardt. Neural persistence: complexity mcasure for deop neural networks using algebraic topology. International Conference on Learning Representations, 2019.
Sam T. Rowcis and Lawrence K. Saul. Nonlincar dimensionality reduction by locally lincar embedding. Science, 290(550))22323 2326, 2000.
Itay Safran and Ohad Shamir. Depth-width tradcoffs in approximating natural functions with neural networks In International Conference on Machine Learning, 2016.
Johannes Hieber. Deep relu network approximation of functions on a manifold. ai preprint S5::1908.00993 2019.
12

---

Published in Transactions on Machine Learning Research (Apr/202)
Stefan C. Schonsheck, Jie Chen, and Rongjie Lai. Chart auto-encoders for manifold structured data. CoRR, abs/1912.10094, 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, ((86):2579-261)) 2008
13

---

Published in Transactions on Machine Learning Research (Apr/202)
A
Appendix
In this section, we formally prove the theoretical findings presented in the primary manuscript. Initially, we utilize some necessary definitions and cxisting results. Then we prove the network size bound for balls, solid tori and general topological representatives.
A.1 Additional Definitions
The first definition Belli reumber, which is a vital part of this paper. The k-th Betti number is defined as the rank of k-th homology group. Therefore, we have to properly define homology group first. Our definition follows Hatcher (2002) but is tailed for simplification. We first define simplicial homology for simplicial complexes. (Actually for A-complexes.
simplify it to avoid introducing A-complexes) Then extend it to singular homology that can be applied to manifolds.
Simplicial Homology. Let K be a simplicial complex, and let K* be the set of all k-dimensional simplices in K. The set k together with the field Zg forms a group (K)). It is a vector space defined on Z2 with K as a basis. The element of (K) is called a k-chain, Let K be a k-simplex, The boundary (x(o) is the collection of its (k- - 1)-dimension faces, which k 1-simplicial complex. The boudnary operator is linear, i.e.
0x(2101 + 2202) = (01) + (02).
The boundary operator 0x (K) (K) introduces chain complex
Ca 04 Ca-1 0u Ca-2 Co ر 0.
d is the maximum dimension of K. Ker 0₂ the collection of k-chains with empty boundary and Im Os is the collection of (k- - 1)-chains that are boundaries of k-chains. Then we can define the k-th homology group of the chain complex to be the quotient group H₃ Ker Or. IIm Oc+1. The k-th Betti number is defined by 02/Im
Bx rank Ha.
Singular Homology. Given topological space X, the k-th singular chain group (X) is defined as the free Abelian group generated by the continuous maps & K + X, where K is the standard k-simplex in R Each such map referred to as a singular k-simplex in X.
A boundary operator 0: Cc(X)) Ck-1(X) can be defined as:
dΦ Σ (-1)
(oo.. Aarr
k=0
where oliv,.- B.r represents the restriction of to the i-th face of K* The k-th singular homology group Hx) is then represented as the quotient:
Ha(X)= = Ker 0n/Tn Se+1.
The k-th Betti number is still defined as 3x rank (X).
Connected Sum of Thickened 1-Manifold. Let M = - x Bd and V = A2t x Bd be two d-thickened 1- manifolds, where M and and A are compact 1-manifolds (with or without boundary), and Bd a d-dimensional closed ball. We define the connected sum M#W by performing connected sum on their boundarics and then extend the gluing to the interior. The process defined as:
1. The connected sum of boundaries. The boundaries of M and N are closed manifolds, where 0M = M x gá-1 and ON = A x 5d-11 Two open neighborhoods U C aM and V c aN are removed from the boundaries. Then a homeomorphism aU + @V is defined to match the resulting boundaries. Then glue aM \ U and aN along OU and 0V via h, forming @(M#N).
Extend the gluing to the interiors of M and A by identifying corresponding points in the neighbor- hoods adjacent to U and V.
14

---

Published in Transactions on Machine Learning Research (Apr/202)
A.2 Preliminary Results
We present some pre-established results regarding the network size associated with learning a 1-dimensional piecewise linear function, as well as basic combinations of functions.
Lemma 2 (Theorem 2.2. in Arora al. (2018)): ). Given any piecewise linear function + R with p pieces there evists a 2-layer ReLU network with al most p nodes that can represent. J. Moreover, if the rightmost or leftmost piece of a the piecewise linear function has 0 slope, then we compute such p piece function using a 2-layer ReLU network with size p 1.
Lemma 3 (Function Composition, Lemma D.I. in Arora et al. (2018)) ). ff : + =tth is represented by ReLU DNN with depth k1 + 1 and size $1, and f2 R. + R" is represented by ReLU DNN with depth 2/2 + and size 82, then f2 o f1 can be represented by ReLU DNN with depth ky + k2 + and size 81
Lemma 4 (Function Addition, Lemma D.2. in Arora et al. (2018)). If fi R. Rm is represented by a ReLU DNN with depth Is + 1 and size and f2 Rn - Rm is represented by ReLU DNN with depth i + and size 82, then fi + f2 can be represented by ReLU DNN with depth k + 1 and size 81 + 82.
Lemma 5 (Taking maximums, Lemma D.3. in Arora et al. (2018)). Let fi, fm : F - R be the functions that each can be represented by ReLU networks with depth k; ++1 and size Si, = 1,.., m. Then the function R + I defined as = max{fa..... fm] can be represented by ReLU network of depth at most max (k1, kmm,...,mmm kim) }+ + log(m) + 1 and size at most + + 8m + 442mm11)
We proceed to disclose the network size involved in learning a 1-dimensional Lipschitz function.
Lemma 6 (Lipschitz Function Approximation, adapted from Lemma 11 in Eldan & Shamir (2016)) ). For any I--Lipschizz function f IR - which constant oulside a bounded interval (a, b), and for any e > 0, there exits a two-layer ReLU network h(z) with at most [L(b - a)/e] + nodes, such that
sup [f(x) -(x)) -(x) <.
FEB
Proof. We follow the original proving idea but adapt it for better understanding. We prove the lemma by estimate the Lipschitz function by a piece-wise linear function within error e and use a two-layer ReLU network to represent the piece-wise linear function.
We first cut the interval equally into m scctions [a, b] = (a- + interval I {a+ (i- 1)ō, id), we denote fi(x) = fl,,- Then Voi, E It [f((m]])())/))))))))()))))) f((x2) < 1 x22 < L8. Let hz(z) be the linear function defined on this interval and connect (a + (i - 1)6, f((a + (i 1)6)) and
where 8 = (b-a)/m For each
(a + i8, fi(a + i8)). Then we can bound the difference between fi(x)) and hz(x) by
(z) h2(2)l S max( max fa(x) min h, | min f((x) - max hx))]
max( max fi(x) fi(a + (i - 1)63 min f((x) fi(a + +8))
(A.1)
Lò.
The second line assumes h2(x) non-decreasing. The other case can also be easily verified. By setting m = [(b=)),, for every interval, the error is controlled by e. Let h(z) be the collection of all hy and also the constant outside of [a, b), so we have supzER [f(x)) - h(x))+++ <.
h(x) is a piece-wise linear function with m + 2 pieces. According to Lemma there exists a 2-layer ReLU network with at most m + pieces that can represent h(z). Proof done.
A.3 Approximating Basic Solid Manifolds
Now we are in good position to prove Proposition and
Proposition (Approximating a idd Ball, adapted from Theorem Safran & Shamir (0166). Given
0, there erists a ReLU network h Ed + R with 3 layers and with size most 4d /e 2d + 2, which can opprozimate the indicator function Jg within error R(h) for any continvoous distribution μ(x).
15

---

Published in Transactions on Machine Learning Research (Apr/202)
Proof. We generally follow the original proof but derive slightly different bound with fewer parameters. The proof is organized by first using non-linear layer to approximate a truncated square function and then using another non-linest layer to approximate a threshold function. Consider the truncated square function
(x;r) min(2" ,r)..
(A.2)
Clearly r(;;)) is a Lipschitz function with Lipschitz constant 2r. Applying Lemma network hn that can approximate ((;rr) with
we have a 2-layer ReLU
sup [2) -(xx) S Sa. zER
(A.3)
with most 2r 2r²/cr nodes. Now for x E Fd, let
h1 (x)))
Σ h1((2)).
(A.4)
Note that h is also 2-layer network because no extra non-linear operation introduced in equation A.4 and has size most 2dr²/e, 2d. This can also be verified by Lemma Let
L(x) Σ L(xgr),
(A.5)
and we have
sup (x) L(x) S des.
(A.6)
Let é = de,, then hn has size al most 2d/r2 /el + 2d. Although L(x) is different from Σ x2, the trick here is to show a = {x: L(x) S r²}. On the one hand, L(rux) s r², remember that
L(x) Σ min min x²
(A.7)
This means for all Hi, x; S2, Therefore, L(x) >i x.. On the other, L(x) > ,2 only happens when there exists such that 27 r2. Thus, x & B Consequently, one can represent Inş by L(x) r
The next step towards this proposition is to construct another 2-layer ReLU network to threshold L(x). Consider
1
I <² 6, E 1r2 - 8, r2) 12
f(x)
(A.8)
0,
r r>
Note that f is 3-picce picco-wise lincar function that approximates threshold function. According Lemma 2 2-layer ReLU network he with size can represent f. The function f I(x) can then be estimated by 3-layer network h h2 hı, whose size is 2r2r2 /c + 2d + 2. The next step to bound the error between h and IB. We consider the L2-type bound [lh(x) - Igg (x=(xx]l = (h(x) Ing (x)) u(x)xxx We divide the integral into two parts
[1x(x)
< [1ʃ L(x) By (x)]la2)))))) + Ilf o L(x) h2 hi (x)
(A.9)
1 + Iz.
Since μ((x is continuous, there exists 6 such that
/ p(x))dx S E2.
(A.10)
16

---

Published in Transactions on Machine Learning Research (Apr/202)
S fx E R ,2² - Ei of S r²) Combine equation A.8 have
1 =
(s L(x) - IB. (x))² (x)))xxxxxxxx p(x)dx
Rd
(fo L(xx) (
J So
(f [(x) 1) (xx)dxxx
(A.11)
/ p(x)dxx
Ss
S 62.
The first incquality is because f E [0, 1}, such that (fo 1)2 1. easily bounded by its infinity norm.
The second part of the error can be
I = IIf L(x) h2 hı (x))laa)))))) $ llf L(x) h2 h1 (x)]l c1.
(A.12)
The last incquality is because h2 is the exact representation of f. the error only occurs between L(x) and h1 Combine A.11 and A.12 and let 61 62 e/2, we have
[|(xx) (xx))((a()) Sc
(A.13)
The size of network h then bounded by 4d2,2/ / 2d 2
Proposition (Approximating a Solid Torus). Given > 0, there erists a ReLU nelwork h : Rd - with layers and with size at most 2d (4(d 1)(R + r)² + 87 + ) +9, which can approzimate the indicator function Lys within error R(h) S e for any continuous distribution p(x).
RR
Proof. The proof done by two steps. We first use layers to estimate a truncated function. Then estimate a threshold function by another layer.
Consider the truncated square function and root function,
(x:77) = min("",
(x 72) min m n., (m %2).
The Lipschitz constants for 4 and la 2y and 2/7 respectively. By Lemma. 6 there is 2-layer ReLU network to approximate 4 and with size [4> /eil + 1 and [(12 (2) m + 1, respectively, Let
L(x) = (((TT) + 4 (12 Σ (2 R); r, R:r).
R
(A.14)
Then is time to show T xxER= (VEiL x
5 {x L(x) S 12}. For e R RR)
ITa (x), the following inequalities hold a
(Rtr
(A.15)
d-1
R+r2
Σ
2 R-r,
(A.16)
d-1
Σ
2 R)² S2.
(A.17)
1=1
17

---

Published in Transactions on Machine Learning Research
These indicate that T(x)= xd
- xt (VE
R2) r², when E Ty And when $ T if
((x) = 22 +
VE - o - R still holds, clearly L(x) > r². Otherwise, one of the inequalities in A.15
A.16 and A.17 must break. If one of A.17 breaks, then clearlv L(x) > r². If A.16 does not hold, then r², resulting [(x) r The violation of A.15 resulting violation of A.16. which then
(va I + 222 Rj
leads to L(x)
To see how a ReLU network can estimate L(x), we start by estimating each of its component. We define the following 2-layer networks. To make the overall network take x Rd input, we consider the structure in figure A.1
h1
R
l12
1131
...
-d-1
Rd
Fdd
Fd
h,22
Figure A.1: Network construction.
The size of parts the network is provided table A.1
Table A.1: Sub-network Size.
Network
Target
Size
his
( R +r) (2; R r, R+)+
S1i [(R ((R+r) +1
h2
82 (r/(eivR-m)) +1
ha1
(r;;
831 /4/2/e14+ +1
hz2
(
832 /1/2 +1
By Lemma 4 and Lemma 3 and the given structure, a ReLU network with depth 4 and size (d 1)811 + 82 831 + 832 + 2, where
3, can approximate T(x)) such that
sup [(xx) f.(x)l S de1-
(A.18)
The next stop to threshold L(x). Consider a function
1
< 2 - 6, I 2r2 8, r²] 2
f(x)
(A.19)
This function approximates a thresholding function [[r S 2 but with error inside the interval f 5, r By Lemma 2 layer ReLU network f with size 2 can represent f(x). Then is ReLU network with depth 5 and size (d 1) 1)811 82 831 + 832 + 4, such that
sup If [(x) i(x) S G
(A.20)
18

---

Published in Transactions on Machine Learning Research Apr/2222)
with letting 6 c1/d.
Let h(x)= = =fo fo (xx). We claim that (xx) is the desired network with depth 5 and size
(d - 1)811111111111111 + 82 + 831 + 832 + 4
d (4(d (id--)((R))) + r) +r VR r +9
(A.21)
c1
d2
= o
To finalize our proof, we just need to bound the error |1((x) - ITI (x) La(a)- The proof follows proof of Proposition The crror is divided into two parts and is bounded scparately. The only difference is we define
Sy to be Ss= = x E IRd : - ā S + (V RR) S r such that
f "(x) cz.
(A.22)
55s
We can get 1 62, and I2 c1. Let 61 62 e/2, we have
[1((x) - 1 (xx)l((((n) S
(A.23)
And h has size at most 2d ([4(d-1)(R--)) r)² + 8r2 + -H- +
A.4 Approximating Topological Representatives
After getting the size arising from fundamental manifolds, we proceed to study the combination of them. We start by proving the representative property.
Lemma (Topological Representative)) Let M.C M be d-dimensional manifold from the thickened I-manifold family. There erist a set of mı d-balls B = B (c.) and a set of m2 solid d-tori T = (T r. (e)) such that M homeomorphic the union (Uner B) (UTETT) T), where my + my S ((M) is a constant integer. We term M' (UBEB B) U)U(UA UUrTT T) as the topological representative of M.
Proof. Since M M, regarding the definition, M is homeomorphic to connect sum or disjoint union of thickened 1-manifolds. A thickened 1-manifold is denoted as M Bd-1, And based the classification theorem of 1-manifold, M is homeomorphic either to circle S or I [0, 1]. If M M x Bd-1 ~ S' x B ~ Tol If MM ~ I, then M x Bd-l ~ I x Bd-1 ~ B Now let M1 and M2 be two thickened 1-manifold, the connected sum of Mi and M2, denoted by Mi @ M2, can be represented by the union of two manifolds M₁ M22 Since M is homeomorphic to connect sum or disjoint union of m thickened I-manifolds, suppose my of them are homeomorphic to Bd and m2 of them are homeomorphic to T Therefore, M (UBES B) (UreTT). T).
S1, then
Notice that among B, the union is disjoint union, otherwise the union is still homcomorphic to a B Similarly, the union between B and T is also disjoint union, otherwise the union is still homeomorphic to a solid torus T The union among T could be joint union or disjoint union. For two solid tori T and Ty, B(TT) = 3(T)) 3(T UT) > 3 2. Overall, 3(M) 2 mi m22
Lemma 7 (Manifold Union). M1 and M2 are two manifolds in Rd. IM, can be approzimated by a ReLU network by with depth d + and size at most 8 with ervor R(h,) C₁, Iyz can be approrimated by a ReLU network he with depth d2 + and size at most s2 with error R(h2) Eg. Then IMJUM, con be approrimated within error en e2 by ReLU network with depth at most max (d, d2) } and size at most 81 82 2.
19

---

Published in Transactions on Machine Learning Research (Apr/200) 2025)
Proof. We represent IMJuM, I2>0 (IM, IM2 by threshold function L250 The threshold function can be approximate by a function
f(x)
8 E (0
(A.24)
1,
x x26 d.
with errors only in (0, I can be represented by a 2-layer ReLU net hy with size 2. Then if let = hy o (h1 + h2), according to Lemma and is a neural network with depth max(dy d2) + 2 and size $1 + $2 + 2. Then we bound the crror
|| (MIUMalleat)
| o (hi + h2) 100 (LM, + (M2)llea(H)
< |1k (/1 + h2) f (IM, +1m2)llea(a)
+ IIf o (IM, + [M,) - I=>0 (IM, + Imn)ll
< ||ly o (h1 + h2) h, o (Imi + +MMa)leaae)
(A.25)
x ||ar|loool[tt + h2) - (LM, + +Imalllea())
< [1(b + h2) - (TM, + [m>)llea())
S 6l + 62
Theorem 1 (Complexity Arising from Topology). Suppose M' is the topological representative of d-manifold from the thickened 1-manifold famāly. Given c <> 0, there erists a ReLU network: IR. + R with depth at most Ollog B) and size al most O ( that can approzimate the indicalor function I with error R(h) S for any continuous distribution over IRd. B is the topological complexity of M'
Proof. Since M' is topological representative, according to Lemma 1 there exist set of my d-balls B = ( (c,, (m.) and set of m2 solid d-tori T = {Tr (c))= such that M' = (UBEB B) U) UUUUTTT T).
Let. m = my + m2. According to Lemma 7 TM' can be approximated by a ReLU network h with depth at most max/d1, d2.,, } + logm m and size at most Σ 8; + log m. with error R(h) S > 4,. Then
according Proposition and 2 s; ~ ((d2/G), de ~ O(1) and take & be all the same for all i i= [m]. Lot
m6; and note that m I B. We have h has depth at most O(log () and size at most 0 d232 =), and can approximate IM with error R(h)= S e.
A.5 Overall Complexity
We present result from Gonzalez-Diaz et al. 2019 which gives bound of network size to represent simplicial map.
Proposition (Adapted from Theorem 4 in Gonzalez-Diaz al. (019 ) Let consider simplicial map de | [L] between the underlying space of two finite pure simplicial complezes K and L. Then aoo-hidden-layee feed-forward network No such that Φe(x)) = -N(xx) for all E |K| can be explicitly defined. The size of Ny is D + d k(D + 1) I(d 1), where D = dim([K() and d = di)((L)), k and I are the number of simplices in and L, respectively.
Theorem 2 (Main Thcorem). Let M Mi M C R be a d-dimensional manifold from the thickened I-manifold family. Mi and Mo are two disjoint sub-manifolds of M representing two classes. The condition number of M is 1 and the total Betti number of M2 is B. Given a training set {(x,, y,)xx, E M, ys E [0,1)]mm where x; are sampled i.i.d. from M by uniform distribution, and ys = IM, (x;). For any 8 > O, if inequality g holds, then for any O, there erists ReLU network: g with depth at most Th + Dr-d log 18), such that
Ollog B + dlog? 1 + log log 1.) and size at most O d88" + -d2 122 4/2
P(R(g) 10)>1-6
(A.26)
where R(g) Smn(9 IMi) (xx)dxx with any continvoous distribution μ.
20

---

Published in Transactions on Machine Learning Research (Apr/2025)
Proof. Since M .M L. is from thickened 1-manifold family, it has topological representative M' = MM C R2, where M'1 and M' are topological representatives of Mi and M2, respectively.
The proof follows by first constructing simplicial approximations |K] and [1] of M and M', respectively. Then we represent a simplicial homeomorphism Φ | - L| by a neural network Ng. where K is constructed from M and I, from M'. Built on the top of this, a projection from M to its simiplicial approximation [K] is represented by another network Np. The overall network can be constructed by g = h No o Np. Note that h is the function to approximate M,; but the data after projection and homeomorphism is from [L)) There should be error in this approximation. However, we will show that by using the true risk, having [ S M' will make sure 11 - MM; [laa(/)) = 0. We move ahcad by first constructing the network 9, and then bounding the approximation error.
Network Construction. Given M is a compact submanifold Df and x, are sampled according to a uniform distribution, by Proposition 3. for all < r < 7/2 and n > >1 (1og((>2)) + log( (n ~ O log(1 1/88)),, U U, Bx((x) has the same homology as .M with probability higher than 1 8. Note that every (x.x)) (x:) is contractible because T. Therefore by the nerve theorem (Edelsbrunner & Harer 2022). the nerve of U is homotopy equivalent to M. Note that U is a collection of e-balls. The nerve of U is the Čech complex, which is an abstract complex constructed as Cech(r) = fo S X Bx(x) * 0}. But since the dimension of M is d, it suffices to only consider simplices with dimension < d. Delaunay complex is such a geometric construction that limits the dimension of simplices we get from a nerve. And in the other hand, we also do not want to lose the radius constraint. Here we construct the Alpha complex, a sub-complex of the Delaunay complex. It is constructed by intersecting each ball with the corresponding Voronoi cell, Rx(r) Bx) Vx. The alpha complex is defined by
Alpha(r) = to S XI N (x(r) 0)-
(A.27)
XEa
Basod on the construction, Alpha(r) also has the same homotopy type as U. Bern et al. (1995) provided the number of simplices in a Delaunay complex of vertices is bounded by O(n 421).. Since the Alpha complex is a sub-complex of Delaunay complex, the number of simplices in Alpha(r) is also bounded by
O( O(T d² 1/2 log d/2 logd/2
1
(A.28)
78
Denote K = Alpha(r).
We claim that there exists a vertex map Φ x; x for i 1,.,, n, such that with probability higher than 1- 5, U' = U, B (x() has the same homology of M. We prove this claim after the proof. We can construct
an alpha complex from {x in a similar way, L = Alpha(r). The number of simiplices is also bounded by O 8 2/2 :
@ can be extended to simiplicial map ob |K| + |7-| by
xxx) = n
(A.29)
The map b; | + IK maps each point to its i-th barycentric coordinate. According to Proposition 6 there
exists a ReLU network No with depth 4 and size O(r-d'// /2 log 4)), such that d(x) = (x) for all x E |K].
Next we construct a network Np that projects M its simplicial approximation [K]. The point is projecting E M to its closest simplex xx- According to the proof of theorem 3 in Scconsheck et al. (2019), such projection can be represented as neural network N₂ with depth at most log + 1 and size at most O(n)). Lastly, by Theorem a neural network h with depth at most O(log (3) and size at most O o can approximate LM; with error R(h) S E1. And by Lemma 3 g = h o No o N, has depth at most
has depth at most Ollog 3 + d log + + log log 78) and size at most O + -d/2 log d/2 1 + Dr- log 4 Note that the 78
(log(n33) and size O(" dd + 4212 1o Tá + nD). Given n ~
1.
probability of the existence for such network is larger than (1 - 8)2 1 28 + 82 > 1- 1-26. We let.
21

---

Published in Transactions on Machine Learning Research
|
x
x
Extend M₁
M
M1
Figure A.2: For point x' E |1,] topological representative.
but x & M,, we extend Mi to make x' E M, The extended Mi is still
8 = 26, such that with probability larger than 1- 6, neural network g exists and g has depth at most Oloog dlog + loglog 1.) and size at most O d² + 72 log 78 Do 78)-
Bounding Approximation Error. Now it is time to bound the approximation error R(g). We split R(g) into two parts.
R(g) 1|g - IM,, (a2(0)
| No No Img o do Npllez + Mn o N, IMIllea(H)
(A.30)
1 + 12-
We first show that I2 = Note that Np :M + [K, and é | + [L]. We claim that for x E Mi, @ (x) E la and x E Mo. @o Np(x)= E Lo- This is true because Mi and M2 are disjoint and is homotopy equivalent M. Consequently, 41, o oo Np LM.. Given
MM o o No [MIllea(U) = || [ o N, - It, o o Npllez(a)
(A.31)
= 11 LM; [|<)(H))
The second equation is derived by letting p'(x') = oo (x)... Now it suffices to show [|4 - Lm [lan(r)) = 0. Note that pl distribution supported on [L], can be naturally extended to M' by sot p((x') = 0f M but x' $ 14]. For x' |4] but x' & MM like shown in Figure A.2, we extend Mi that. x' E M₁. And such extension always exists due to the construction of TT Note that [Ta] alpha complex constructed from a r'-cover, in a way that there will be an edge if and only if two covering balls have intersection. Hence, for any edge (x/, x,) E LLl, the length kij of it satisfies 4y < 2r <T'. And notice the radius of the inner circle should be at least r'. Otherwise, the reach will be less than r'. Consequently, the edge of [T] is always smaller than the radius of the innor circle. Therefore, one can always choose a Mi, so that Vx' E [La] but x' M'.
After the expansion, |L S Mi. As conclusion, 1|4,, Lmmllestr 0. Hereby, we have proved l2 0. Now we settle I1. Given No is an exact representation of the simplicial map d,
== |h IMq llxa(w))
(A.32)
According to Theorem 1 J 61 Combined together, we have
R(g) 61
(A.33)
Note that this incquality holds only with probability larger than 8 because that the probability we successfully recover the homology of M by the training set and construct simplicial homeomorphism. 7
22

---

Published in Transactions on Machine Learning Research (Apr/202)
Claim 1. E MERD is d-dimensional manifold from thickened 1-manifold family. Suppose there crists set {xi E EM and radius r, such that U = U, BP is a cover of M and has the same homology- Then there ezists a M' E Rd that is a topological representative of M. Denote the homeomorphism between them f. Then with probability larger than -,, 6, U U, (f(x)) has the same homology as M.
Proof. We let
vol(M) (cvol)))vol(B)
log vol(M) (coo f/8)
+ log 1
(r,T,M)
(A.34)
where 0, arcsin 87 02 aresin 107
and 0 < < 1/2. Given set (f(x)) apply proposition 3 to M'. If
n> c(r', M').
(A.35)
then with probability 1 1- 5, U' U; By (f(x.)) has the same homology M', with r' <'
Note that n already satisfy that n > c(r, M). it suffices to show c(r, r, M,) > c(r', T'r','', M'). Since M' is one of topological representatives of .M, we can always choose the radius of the fundamental members in M' and choose the distance between M and M2, to make sure that +' > 7 and vol(MM) < vol(M). Hence, we can choose r and r', such that B Br. With the same 8, we have proved that c(r,T,M) c
23


Reviews:
[{"review_id": "UZlVMNvvhO", "reviewer": "Reviewer_RNER", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The idea of considering how the topological complexity of inputs impacts the necessary expressivity of NNs operating on such data is novel and interesting.\n- The presentation is clear, with appropriate amounts of detail abstracted away/relegated to appendices and the remaining formalisms well described. This was really a non-trivial thing to do given the nature of the content and I applaud the author's for their efforts. \n\nWeaknesses:\n- Analysis is restricted to the family of thickened 1-manifold family: While the structure of this family facilitates the proof by construction the paper would be strengthened by giving some examples of the types of properties that can and cannot be modeled with or approximated by this family. \n- As far as I could tell, there are no arguments made that the derived bounds will be tight (though the empirics suggest this may be the case in a very simple setting). \n- Empirical evaluation is limited: experiments are limited to tori of different genera (so $\\beta$ varies) with a fixed dimension.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies how the minimum size of a ReLU network necessary to express the solution to a binary classification problem on a topological manifold changes as a function of the topological complexity (quantified by the sum of the Betti numbers). More precisely, the author's present a novel method for disentangling the impact of geometric complexity (quantified by the condition number of a manifold) and topological complexity on bounds for network size by: \n- considering a restricted family of manifolds (thickened 1-D manifolds),\n- constructing an architecture that first learns a homeomorphism between an input manifold and a \"topological representative.\" The size of a network needed to implement this function is  governed by the geometric complexity.\n-  proving that the required size for solving the classification problem on the topological representative is bounded by a term quadratic in the total Betti number. \n\nThe author's conduct an experiment to demonstrate that the relationship between the minimum network size and the square of the total Betti number (of an input dataset) is indeed linear (as predicted by the theory) in a simple setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In relation to the weaknesses mentioned above:\n- Could the author's add some more explicit examples of interesting manifolds in the thickened 1-manifold family? I appreciate that the connected sum and disjoint union operations make the family more expressive than one might appreciate at first glance, but think this could be better presented in the main text (I think figure A.1 could even be promoted to the main text). It would also be good to discuss what types of manifolds lie outside this family. \n- Can the author's explicitly acknowledge that the derived bound need not be tight (i.e., the relationship should not be thought of as a scaling law)? It would be particularly interesting if one could design a simple input set where you expect the relationship between network size and the square of the Betti number to be sublinear. Perhaps this really only makes sense to note in the discussion section?\n- If possible, it would be nice to expand the empirical evaluations. Ideally I think at least two types of input manifolds (which would each be distinct types of topological representatives) and varying dimensionality  should be considered. If the linearity observed in Fig 4c is preserved that would be quite interesting!\n\nTypo: in the proof sketch at the bottom of page 8:  \"...$\\mathcal{M}'_1$ and $\\mathcal{M}'_0$ are topological representatives of $\\mathcal{M}_1$ and $\\mathcal{M}_2$...\", should be $\\mathcal{M}_1$ and $\\mathcal{M}_0$. \n\nNone of the changes are required to recommend acceptance, but I do believe each would strengthen the work.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "t2aPwfQCec", "reviewer": "Reviewer_hzhS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\nThe theoretical contribution is novel and interesting. The authors took a promising direction on incorporating the topological complexity of data. \n\nCons:\nThe validity of modeling real data as thickened 1-manifolds needs more justification (as a separate section).\n\nThe practical applicability of computing the proposed bounds on real datasets needs more verification (as a separate section). However the current empirical results are only on a toy dataset and are insufficient. \n\nDue to these limitations, the paper needs more iterations before getting published. Moreover, the authors are encouraged to strengthen the empirical verification, and properly position this work in the literature of similar bounds.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The current paper explored how a classifier network size scales up with respect to the topological complexity (given by the Betti numbers) and curvature of the data manifold (given by the the reach) via a constructive proof.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please argue carefully the reasonableness of using the thickened 1-manifold to model real data.\n\nPlease explain in detail how to compute the Betti numbers in practice when the data is high dimensional and sparse.\n\nRelated work should be more carefully discussed as there are existing work on applying topological properties to neural network expressiveness.", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "e5WZ1G2dVT", "reviewer": "Reviewer_98WJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n * Data topology may provide a different perspective on the ability to perform classification, which is not captured in current methods, which mostly rely on geometry.\n * An interesting upper bound decouples the contributions of Betti numbers and curvature to the network's size.\n\nWeaknesses\n * The result seems to apply only to thickened 1d manifolds. It is unclear if it can be extended to more complicated manifolds or if more complicated ones can be somehow reduced to those simple ones.\n * The result can be interpreted as an upper bound, which may be vacuous, or as a scaling argument on the ability to perform classification. The supporting evidence in simulations is only for the first half, i.e., Theorem 1, laying out the contribution of topology. However, no support is provided for the second half, i.e., Theorem 2, combining the contributions of topology and geometry. The authors state Theorem 2 as their main contribution.\n * The decoupling argument used in Theorem 2 seems naive to yield a non-vacuous upper bound and should be rephrased as a naive upper bound or better supported by simulations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The manuscript presents an upper bound on the size of a ReLU network required to achieve a given error level in binary classification on data from a manifold representing two classes. The manifold is assumed to be a finite combination of thickened 1d manifolds (made of balls around all points in a line or a circle), and the bound is given in terms of its geometrical and topological properties, namely condition number (related to curvature) for geometric complexity and Betti numbers for topological complexity. The manuscript decouples the two properties by mapping the manifold to the latent space, using previous results on the network size needed for that given the geometric complexity, and then using the topologic complexity to analyse the needed network size to achieve the target error in that space. The scaling predicted by topology can be observed in simulations on synthetic data.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Is it possible to demonstrate in simulations how changes to the geometry of manifolds interfere with changes in topology? For example, repeat the experiment reported in Figure 4c on manifolds with the same dimension but higher or lower curvature. Then see if the interaction observed is in line with what is predicted by the results of the manuscript.\n * Clarify if the results in the paper should be interpreted as scaling laws or as upper bounds; if they are upper bounds, show how to apply them to results (in terms of the free parameters).\n * Missing references to manifold classification literature (e.g., https://doi.org/10.1103/PhysRevX.8.031003) and discussion of the different approaches.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PBfUtUpoMa", "reviewer": "Reviewer_KGYi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In my opinion, this is a high quality theory paper.\n- As supported by the experiment in section 5, this is highly relevant for the field and for practical neural networks. How manifold structure enables learnability is one of the greatest mysteries in ML, and the authors are correct that global (topological) properties are particularly understudied in this respect.\n- It is very well-written with a 5/5 for clarity. Even though its content is esoteric, the authors have clearly put a great deal of care into making it accessible with clear, intuitive prose and useful diagrams. Their ideas are well-distilled into key themes which are repeatedly emphasized throughout the paper.\n\nI did not read the proofs in the appendix in detail and cannot vouch for their correctness.\n\nThe only weakness I can point out is their strong assumptions on the data manifold. They authors write that \"this family may appear overly restrictive; however, we will explain why it actually represents a broad and versatile class of manifolds.\" I did not find any such explanation in the main text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is a theoretical work that proposes a new way of analyzing the relationship between the complexity of a data manifold and the capacity required for a neural network to perform classification on it. The authors focus on binary classification for this analysis. \n\nThe authors point out that past work in this vein has focused on geometric characteristics (especially local intrinsic dimension/LID) but not topological characteristics of the manifolds. The key theme and contribution of the work is about separating the geometric properties (here characterized by the condition number) and the topological properties (here characterized by the total Betti number $\\beta$).\n\nThis separation is achieved as follows:\n- First, a ReLU network is constructed to approximate a homeomorphism that maps the manifold into a union of $d$-balls and solid $d$-tori. The size of this network scales with the condition number (geometric complexity). This homeomorphism \"removes\" the geometric complexity of the data manifold, making it easy to characterize its topological complexity in the next step.\n- Second, another ReLU network is constructed on the codomain of the first which approximates the ground truth classifier and whose size scales with $\\beta$ (the topological complexity).\n\nThe authors provide a small experiment showing that classification on a synthetic manifold actually does require network size linear in $\\beta^2$, as predicted by their theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Typos\n- p5 \"Reach and *conditional* number\"\n- p8 \"*simiplicial* approximation\"\n- p18 \"proposition 7\" in the proof of Theorem 1 should read \"Lemma 7\"\n\nNot necessary for acceptance: Can you elaborate further on why the thickened 1-manifold family should be considered representative of true data manifolds?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After the rebuttal, three reviewers agree it now exceeds the bar for admission, while one reviewer provided more thoughtful critiques.

AE has carefully considered all raised concerns, and wanted to share why he believes this manuscript merits acceptance despite proposed reservations:

1. Scope and Nature of the Paper

The primary contribution of this work is theoretical rather than empirical. While the authors do offer illustrative experiments (and do plan to add additional clarifications/experiments in revision), their goal is to build new theoretical insight on how topological characteristics of data manifolds can affect the capacity requirements of neural networks. Hence, although real-data experimental validations are an asset, the chief strength of the submission—and the main reason for my favorable view—lies in its theoretical contribution.

2. Reasonableness of the Thickened 1-Manifold Assumption

While concerns about the restrictiveness of a 'thickened 1-manifold' are understandable, the authors' definition—which includes disjoint unions, connected sums, and homeomorphisms—provides considerable expressive power. As they note, this family serves as a tractable approximation of real manifolds, capturing essential topological features (specifically the first two Betti numbers). Although it omits higher-dimensional topology—which is often computationally infeasible—it remains expressive enough to represent real-world data manifolds. Importantly, it lays the groundwork for a rigorous, topology-aware theoretical framework for understanding neural network expressive power.

3. Verification of Betti Number Computation in the revised manuscript

The point about verifying the stated 9s computation on MNIST is well-taken. We shall encourage the authors to clarify or add this computation time in their final version.

Based on these points, AE feels that the paper's claims are already supported by evidence and there is a relevant audience, hence meriting TMLR acceptance. AE will, of course, encourage the authors to explicitly address the specific criticisms (for instance, by including empirical evaluation of Betti number computations, and by discussing limitations in modeling real data as thickened 1-manifolds).
Decision: Accept (poster)