A Theoretical Study of Neural Network Expressive Power via Manifold Topology

## Abstract

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.

## 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 approximation theorems (Hornik, ; Cybenko, ; Leshno et al., ; Hanin, ) 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, ; van der Maaten & Hinton, ; Jolliffe & Cadima, ).
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 et al., ; Schmidt-Hieber, ).

However, the intrinsic dimension is only a 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 () 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 research has probed the geometry and topology of manifolds. Notably, Federer (); Amenta & Bern () introduce a pivotal curvature measure, which adeptly captures the global geometric nuances of manifolds and has been embraced in manifold learning studies (Narayanan & Niyogi, ; Narayanan & Mitter, ; Ramamurthy et al., ).
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, ; Bott et al., ; Munkres, ; Rieck et al., ). In their seminal work, Niyogi et al. () integrate manifold’s geometry and topology, setting forth conditions for topologically faithful 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., ; Schonsheck et al., ) bound network size with the geometry of manifolds. However, a 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, ; Naitzat et al., ) suggest that even with similar geometry, data with larger topological complexity requires a larger network. These empirical observations highlight the need for a theoretical 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 input 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 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 learning.
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 (); Amenta & Bern (), describing the manifold’s overall flatness.
See Figure 1 for illustrations of these measures.

Our main theoretical result is summarized informally below; the formal version is presented in Theorem 2.

###### Main Theorem .

(Informal)
Let ${\mathcal{M}}\subset\mathbb{R}^{D}$ be a $d$-dimensional manifold ($d\leq D$) from a family of thickened 1-manifold and has two classes. There exists a ReLU network classifier $g$ with depth at most $O(\log\beta+\log\frac{1}{\tau})$ and size at most $O(\beta^{2}+(\frac{1}{\tau})^{d^{2}/2})$, such that with large probability, the true risk of $g$ is small. $\beta$ is the sum of Betti numbers and $\frac{1}{\tau}$ is the inverse of reach.

According to our bound, the network size scales quadratically in terms of the sum of Betti numbers $\beta$.
Conversely, in terms of $\frac{1}{\tau}$, it scales as $O\left((\frac{1}{\tau})^{d^{2}/2}\right)$. 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.

Figure: (a)
Refer to caption: x1.png

In the following section, we discuss related works and compare our derived bounds with those previously established. In Section 3, 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 4, 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.

###### Main Theorem .

## 2 Related Works

Network size with manifold geometry. Multiple studies have formulated network size bounds across varied manifold learning contexts based on geometry. Schonsheck et al. () establish a bound of $O(LdD\epsilon^{-d-d^{2}/2}(-\log^{1+d/2}\epsilon))$ on the network size for manifold reconstruction tasks. $L$ is the covering number in terms of the injectivity radius, a geometric property. They utilize an auto-encoder, denoted as $D\circ E$, for the reconstruction of a manifold. Both the encoder $E$ and the decoder $D$ are designed to function as homeomorphisms. As a result, the overarching objective is the construction of a homeomorphism within the same space, which elucidates the absence of topological considerations in their outcomes. Our findings include not only the homeomorphism but also the classification network, with the latter being influenced by the manifold’s topology.
Chen et al. () demonstrate the existence of a network of size $O(\epsilon^{-d/n}\log\frac{1}{\epsilon}+D\log\frac{1}{\epsilon}+D\log 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 is to illustrate that, in manifold learning, the manifold dimension chiefly determines network size, with only a 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. () investigate network size in classification contexts. However, their foundational assumption is that a manifold’s essence can be distilled into just two parameters: a centroid and a 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. () establish a 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.
Guss & Salakhutdinov () 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 a more comprehensive theoretical understanding.

There are some intriguing studies not primarily centered on manifold learning. Specifically, Bianchini & Scarselli () 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 () explore the challenge of approximating the indicator function of a unit ball using a 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. () empirically examines the evolution of manifold topology as data traverses the layers of a proficiently trained neural network. We have adopted their concept of topological complexity. A number of studies, such as those by Hanin & Rolnick () and Grigsby & Lindsey (), 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.

## 3 Preliminaries

Topological Manifolds. In this paper, we focus on a specific class of manifolds called the *thickened 1-manifold family*, which are derived from operations on 1-manifolds. To lay the groundwork, we begin with the concept of a manifold. An n-dimensional manifold is a topological space where every point has a neighborhood that is homeomorphic (topologically equivalent) to $\mathbb{R}^{n}$. And an n-manifold with boundary allows for points that have neighborhoods homeomorphic to the half-space $\mathbb{R}_{\geq 0}\times\mathbb{R}^{n-1}$. For example, a circle ($s^{1}$) is a 1-manifold without boundary, known as a closed manifold, while a line segment ($I^{1}$) is 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, we consider *$d$-thickened 1-manifolds*, which are $(d+1)$-dimensional manifolds homeomorphic to $\mathcal{M}^{1}\times B^{d}$, where $\mathcal{M}^{1}$ is a compact 1-manifold (with or without boundary), and $B^{d}$ denotes a $d$-dimensional closed ball. Figure 2 illustrates the $1$-thickened $1$-manifold. According to the classification theorem for $1$-manifolds, ${\mathcal{M}}^{1}$ is homeomorphic to either a closed interval $I^{1}$ or a circle $S^{1}$. Consequently, a 1-thickened 1-manifold is homeomorphic to either $I^{1}\times B^{1}$ or $S^{1}\times B^{1}$.

Connected Sum and Disjoint Union. To construct more complex manifolds from simpler ones, we utilize operations such as the connected sum and disjoint union. The connected sum of two closed manifolds ${\mathcal{M}}$ and ${\mathcal{N}}$, denoted ${\mathcal{M}}\mathrel{\#}{\mathcal{N}}$, is formed by removing a small open ball from each manifold and then gluing them together along the resulting boundary sphere. The disjoint union ${\mathcal{M}}\sqcup{\mathcal{N}}$ 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, we utilize the fact that the boundary $\partial\mathcal{M}$ of a thickened 1-manifold $\mathcal{M}$ is a closed manifold. The connected sum of two thickened 1-manifolds is defined by performing the connected sum on 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 A.1 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 1 (Thickened $1$ -Manifold Family) .

Let ${\mathcal{M}}^{1}$ represent a compact $1$-manifold (with or without boundary). A $d$-thickened $1$-manifold is a $(d+1)$-manifold homeomorphic to ${\mathcal{M}}^{1}\times B^{d}$. The family of $d$-thickened 1-manifolds, denoted by ${\mathbb{M}}$, includes all such manifolds obtained via finite operations of connected sum and disjoint union.

Figure: Figure 2: An illustration of the 1-thickened 1-manifold in 2D space. The top row shows a manifold that has the same homotopy type as a closed interval $I^{1}$, while the bottom row shows a manifold that is homotopy equivalent to a circle $S^{1}$. The 1-thickened 1-manifold family contains all manifolds that can be obtained through the disjoint union and connected sum of these manifolds.
Refer to caption: x5.png

Betti numbers. We employ Betti number $\beta_{k}({\mathcal{M}})$ to quantify topology of a manifold ${\mathcal{M}}$. $k$ is the dimension of that Betti number. 0-dimension Betti number $\beta_{0}({\mathcal{M}})$ is the number of connected components in ${\mathcal{M}}$, and $\beta_{k}({\mathcal{M}})$ ($k\geq 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. (), we utilize the total Betti number of ${\mathcal{M}}$ as its topological complexity.

###### Definition 2 (Topological Complexity) .

${\mathcal{M}}$ is a $d$-dimensional manifold. $\beta_{k}({\mathcal{M}})$ is the $k$-dimensional Betti number of ${\mathcal{M}}$. The topological complexity is defined as

$$ $\beta({\mathcal{M}})=\sum_{k=0}^{d-1}\beta_{k}({\mathcal{M}}).$ (1) $$

Reach and conditional number. We then introduce metrics that encapsulate these geometric properties. For a compact manifold ${\mathcal{M}}$, the reach $\tau$ is the largest radius that the open normal bundle about ${\mathcal{M}}$ of radius $\tau$ is embedded in $\mathbb{R}^{d}$, i.e., no self-intersection.

###### Definition 3 (Reach and Condition Number) .

For a compact manifold ${\mathcal{M}}\subset\mathbb{R}^{D}$, let

$$ $G=\{{\mathbf{x}}\in\mathbb{R}^{D}|\exists{\mathbf{p}},{\mathbf{q}}\in{\mathcal {M}},{\mathbf{p}}\neq{\mathbf{q}},||{\mathbf{x}}-{\mathbf{p}}||=||{\mathbf{x}} -{\mathbf{q}}||=\inf_{{\mathbf{y}}\in{\mathcal{M}}}||{\mathbf{x}}-{\mathbf{y}} ||\}.$ (2) $$

The reach of ${\mathcal{M}}$ is defined as $\tau({\mathcal{M}})=\inf_{{\mathbf{x}}\in{\mathcal{M}},{\mathbf{y}}\in G}||{
\mathbf{x}}-{\mathbf{y}}||$. The condition number $\frac{1}{\tau}$ is the inverse of the reach.

Niyogi et al. () prove that the condition number controls the curvature of the manifold at every point. A modest condition number $1/\tau$ signifies a well-conditioned manifold exhibiting low curvature.

Problem setup. In this paper, we examine the topology and geometry of manifolds in the classification setting. We have access to a training dataset $\{({\mathbf{x}}_{i},y_{i})|{\mathbf{x}}_{i}\in{\mathcal{M}},y_{i}\in[L]\}_{i=1
}^{n}$, where ${\mathcal{M}}=\bigsqcup_{l=1}^{L}{\mathcal{M}}_{l}$. Each sample is drawn i.i.d. from a mixture distribution $\mu$ over $L$ disjoint manifolds with the corresponding label. For the simplification of notation, we build our theory on binary classification. It can be extended to multi-class without efforts in a one-verses-all setting. In binary case, the dataset is $\{({\mathbf{x}}_{i},y_{i})|{\mathbf{x}}_{i}\in{\mathcal{M}},y_{i}\in\{0,1\}\}_
{i=1}^{n}$, where ${\mathcal{M}}={\mathcal{M}}_{1}\sqcup{\mathcal{M}}_{0}\in\mathbb{R}^{D}$. ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{0}$ are two disjoint $d$-dimensional manifolds representing two classes. The label $y_{i}$ is determined by the indicator function

$$ $I_{{\mathcal{M}}_{1}}({\mathbf{x}})=\begin{cases}1,&{\mathbf{x}}\in{\mathcal{M }}_{1},\\ 0,&\text{otherwise}.\end{cases}$ (3) $$

A neural network $h({\mathbf{x}}):\mathbb{R}^{D}\to[0,1]$ approaches the classification problem by approximating the indicator function $I_{{\mathcal{M}}_{1}}({\mathbf{x}})$. In the scope of this study, we focus on neural networks utilizing the ReLU (Rectified Linear Unit) activation function.

###### Definition 4 (Adapted from Arora et al. ( 2018 ) ) .

A ReLU multi-layer feed-forward network $h:\mathbb{R}^{w_{0}}\to\mathbb{R}^{w_{k+1}}$ with $k+1$ layers is defined as

$$ $h({\mathbf{x}})=h_{k+1}\circ h_{k}\circ\dots\circ h_{1}({\mathbf{x}}),$ (4) $$

where $h_{i}:\mathbb{R}^{w_{i-1}}\to\mathbb{R}^{w_{i}},h_{i}({\mathbf{x}})=\sigma(W_{
i}{\mathbf{x}}+b_{i})$ for $1\leq i\leq k$ are ReLU layers, and $h_{k+1}:\mathbb{R}^{w_{k}}\to\mathbb{R}^{w_{k+1}},h_{k+1}({\mathbf{x}})=W_{k+1
}{\mathbf{x}}+b_{k+1}$ is a linear layer. $\sigma$ is the ReLU activation function. The depth of the ReLU network is defined as $k+1$. The width of the ReLU network is $\max\{w_{1},\dots,w_{k}\}$. The size of the ReLU network is $\sum_{i=1}^{k}w_{i}$.

The approximation error of a ReLU network is determined by the true risk.

###### Definition 5 (Approximation Error) .

Let’s consider the indicator function $I_{{\mathcal{M}}_{1}}$ for a manifold ${\mathcal{M}}_{1}$ in a binary classification problem where ${\mathcal{M}}={\mathcal{M}}_{1}\sqcup{\mathcal{M}}_{0}$. A neural network operates as a function $h({\mathbf{x}}):{\mathcal{M}}\to\mathbb{R}$. The approximation error of the neural network $h$ is then defined as:

$$ $\text{True Risk: }R(h)=\int_{{\mathcal{M}}}(h-I_{{\mathcal{M}}_{1}})^{2}\mu( \mathbf{x})d\mathbf{x}.$ (5) $$

$\mu$ is any continuous distribution over ${\mathcal{M}}$.

###### Definition 1 (Thickened 1 1 1 1 -Manifold Family) .

###### Definition 2 (Topological Complexity) .

###### Definition 3 (Reach and Condition Number) .

###### Definition 4 (Adapted from Arora et al. ( 2018 ) ) .

###### Definition 5 (Approximation Error) .

## 4 Main Results

In this section, we explore how the topology of manifolds influence network size in classification scenarios. Our results, derived methodically through construction, follow two steps.
First, we approximate a homeomorphism between the input manifold and a latent one; second, we 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 to gauge topological and geometric 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.

### 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 $B^{d}_{r}(\mathbf{c})$, and the solid $d$-tori, represented by $T^{d}_{r,R}$. The $d$-dimensional ball, $B^{d}_{r}(\mathbf{c})$, is characterized by a radius $r$ and is centered at $\mathbf{c}$, mathematically defined as

$$ $B^{d}_{r}(\mathbf{c})=\left\{\mathbf{x}\in\mathbb{R}^{d}:\Arrowvert\mathbf{x}- \mathbf{c}\Arrowvert_{2}\leq r\right\}.$ (6) $$

On the other hand, the solid $d$-torus, $T^{d}_{r,R}$, embodies a genus-1 torus with a tunnel radius of $r$ and a tunnel center radius of $R$, centered at $\mathbf{c}$. Its formula is given by

$$ $T^{d}_{r,R}({\mathbf{c}})=\left\{\mathbf{x}\in\mathbb{R}^{d}:(x_{d}-c_{d})^{2} +\left(\sqrt{\sum_{i=1}^{d-1}(x_{i}-c_{i})^{2}}-R\right)^{2}\leq r^{2}\right\}.$ (7) $$

It’s pertinent to acknowledge that the general structure of a $d$-torus becomes significantly more complex as $d$ increases. The provided equation for $T^{d}_{r,R}$ represents only one of its potential configurations. Nevertheless, this depiction suffices within the context of the thickened 1-manifold ensemble.

###### Lemma 1 (Topological Representative) .

Let ${\mathcal{M}}\subset{\mathbb{M}}$ be a $d$-dimensional manifold from the thickened 1-manifold family. There exist a set of $m_{1}$ $d$-balls ${\mathcal{B}}=\{B_{r_{i}}^{d}({\mathbf{c}}_{i})\}_{i=1}^{m_{1}}$ and a set of $m_{2}$ solid $d$-tori ${\mathcal{T}}=\{T_{r_{i},R_{i}}^{d}({\mathbf{c}}_{i})\}_{i=1}^{m_{2}}$, such that ${\mathcal{M}}$ is homeomorphic to the union $(\bigcup_{B\in{\mathcal{B}}}B)\cup(\bigcup_{T\in{\mathcal{T}}}T)$, where $m_{1}+m_{2}\leq\beta({\mathcal{M}})$ is a constant integer. We term ${\mathcal{M}}^{\prime}=(\bigcup_{B\in{\mathcal{B}}}B)\cup(\bigcup_{T\in{
\mathcal{T}}}T)$ as the topological representative of ${\mathcal{M}}$.

Given the classification theorem of 1-manifolds, compact 1-manifolds without boundary are homeomorphic to a circle, while compact 1-manifolds with boundary are homeomorphic to a closed interval. Therefore, the thickened 1-manifolds are homeomorphic to either a solid torus or a ball. Our preliminary analysis focuses on the network size associated with $d$-balls and $d$-tori. Using this as a foundation, we then explore how various topological configurations of thickened 1-manifold impact the size of neural networks. Proposition 1 determines the network size required to approximate a $\mathbb{R}^{d}$ ball. While the original result is found in Safran & Shamir (), our study utilizes fewer parameters and offers a different way to approximate the threshold function. Proposition 2 outlines a network size bound for the approximation of a solid torus.

###### Proposition 1 (Approximating a $\mathbb{R}^{d}$ Ball, adapted from Theorem 2 in Safran & Shamir ( 2016 ) ) .

Given $\epsilon>0$, there exists a ReLU network $h:{\mathbb{R}}^{d}\to{\mathbb{R}}$ with $3$ layers and with size at most $4d^{2}r^{2}/\epsilon+2d+2$, which can approximate the indicator function $I_{B^{d}_{r}}$ within error $R(h)\leq\epsilon$ for any continuous distribution $\mu({\mathbf{x}})$.

###### Proposition 2 (Approximating a Solid Torus) .

Given $\epsilon>0$, there exists a ReLU network $h:{\mathbb{R}}^{d}\to{\mathbb{R}}$ with $5$ layers and with size at most $\frac{2d}{\epsilon}(4(d-1)(R+r)^{2}+8r^{2}+\frac{r}{\sqrt{R-r}})+9$, which can approximate the indicator function $I_{T_{r,R}^{d}}$ within error $R(h)\leq\epsilon$ for any continuous distribution $\mu({\mathbf{x}})$.

Both proofs begin by expressing the indicator function as a composition of truncated power functions. Each truncated power function can be approximated by a piecewise linear function, which can be precisely represented by a 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 1 and 2 address the network size associated with approximating $B_{r}^{d}$ and $T_{r,R}^{d}$. 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 $B_{r}^{d}$ and $T_{r,R}^{d}$ with those of union operation. This consolidated insight is captured in Theorem 1.

###### Theorem 1 (Complexity Arising from Topology) .

Suppose ${\mathcal{M}}^{\prime}$ is the topological representative of $d$-manifold from the thickened $1$-manifold family. Given $\epsilon>0$, there exists a ReLU network $h:\mathbb{R}^{d}\to\mathbb{R}$ with depth at most $O(\log\beta)$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon})$, that can approximate the indicator function $I_{{\mathcal{M}}^{\prime}}$ with error $R(h)\leq\epsilon$ for any continuous distribution $\mu$ over $\mathbb{R}^{d}$. $\beta$ is the topological complexity of ${\mathcal{M}}^{\prime}$.

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 representative. It is important to note that this captures the full range of complexities arising from the topology of a manifold ${\mathcal{M}}\in{\mathbb{M}}$, given that ${\mathcal{M}}$ and ${\mathcal{M}}^{\prime}$ are homeomorphic. To the best of our knowledge, this is the first result bounding neural network size in terms of a manifold’s Betti numbers.

###### Lemma 1 (Topological Representative) .

###### Proposition 1 (Approximating a ℝ d superscript ℝ 𝑑 \mathbb{R}^{d} blackboard_R start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT Ball, adapted from Theorem 2 in Safran & Shamir ( 2016 ) ) .

###### Proposition 2 (Approximating a Solid Torus) .

###### Theorem 1 (Complexity Arising from Topology) .

### 4.2 Overall Complexity

For general manifolds in ${\mathcal{M}}\in{\mathbb{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, a continuous two-way transformation, between ${\mathcal{M}}$ and its corresponding topological representative ${\mathcal{M}}^{\prime}$. This method only alters the geometric properties, preserving the object’s topological attributes. Therefore, the network size in approximating the indicator function of ${\mathcal{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 geometry of manifold on classifiers. In this section, we aim to obtain the overall network size for a classifier.

To build a homeomorphism from ${\mathcal{M}}$, we first need to recover the homology of ${\mathcal{M}}$. The subsequent proposition outlines a lower limit for the number of points essential to recover the homology of the initial manifold ${\mathcal{M}}$.

###### Proposition 3 (Theorem 3.1 in Niyogi et al. ( 2008 ) ) .

Let ${\mathcal{M}}$ be a compact $d$-dimensional submanifold of $\mathbb{R}^{D}$ with condition number $1/\tau$. Let $X=\{{\mathbf{x}}_{1},{\mathbf{x}}_{2},..{\mathbf{x}}_{n}\}$ be a set of $n$ points drawn in i.i.d. fashion according to the uniform probability measure on ${\mathcal{M}}$. Let $0<\epsilon<\frac{\tau}{2}$. Let $U=\bigcup_{{\mathbf{x}}\in X}B_{\epsilon}({\mathbf{x}})$ be a corresponding random open subset of $\mathbb{R}^{D}$. Then for all

$$ $n>\lambda_{1}(log(\lambda_{2})+log(\frac{1}{\delta})),$ (8) $$

$U$ is a $\epsilon$-cover of ${\mathcal{M}}$, and the homology of $U$ equals the homology of ${\mathcal{M}}$ with high confidence (probability $>1-\delta$).
Here

$$ $\lambda_{1}=\frac{vol({\mathcal{M}})}{(cos^{d}\theta_{1})vol(B_{\epsilon/4}^{d })}\text{ and }\lambda_{2}=\frac{vol({\mathcal{M}})}{(cos^{d}\theta_{2})vol(B_ {\epsilon/8}^{d})},$ (9) $$

$\theta_{1}=arcsin(\epsilon/8\tau)$ and $\theta_{2}=arcsin(\epsilon/16\tau)$. $vol(B_{\epsilon}^{d})$ denotes the $d$-dimensional volume of the standard $d$-dimensional ball of radius $\epsilon$. $vol({\mathcal{M}})$ is the $d$-dimensional volume of ${\mathcal{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 ${\mathcal{M}}\in{\mathbb{M}}$ and its topological representative ${\mathcal{M}}^{\prime}$. However, directly constructing 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 1, we can construct a classification network for general manifolds in ${\mathbb{M}}$, as depicted in Figure 3. Initially, we project ${\mathcal{M}}$ to its simplicial approximation $|K|$ using a neural network $N_{p}$. This is succeeded by a network $N_{\phi}$ that facilitates the simplicial homeomorphism between $|K|$ and $|L|$, the latter being the simplicial approximation of the topological representative ${\mathcal{M}}^{\prime}$. Finally, a network $h$ is utilized to classify between $|L_{1}|$ and $|L_{0}|$. Consequently, the network’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 2, we design such a 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 the construction of a ReLU network, followed by an evaluation of the network’s size. Subsequently, we place bounds on the involved approximation errors.

Figure: Figure 3: Construction of the network $g$. The network first learns a low-dimensional embedding and then 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 ${\mathcal{M}}_{0}$ mirrors this operation identically.
Refer to caption: x6.png

###### Theorem 2 (Main Theorem) .

Let ${\mathcal{M}}={\mathcal{M}}_{1}\sqcup{\mathcal{M}}_{0}\subset\mathbb{R}^{D}$ be a $d$-dimensional manifold from the thickened $1$-manifold family. ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{0}$ are two disjoint sub-manifolds of ${\mathcal{M}}$ representing two classes. The condition number of ${\mathcal{M}}$ is $\frac{1}{\tau}$ and the total Betti number of ${\mathcal{M}}_{1}$ is $\beta$. Given a training set $\{({\mathbf{x}}_{i},y_{i})|{\mathbf{x}}_{i}\in{\mathcal{M}},y_{i}\in\{0,1\}\}_
{i=1}^{n}$, where ${\mathbf{x}}_{i}$ are sampled i.i.d. from ${\mathcal{M}}$ by a uniform distribution, and $y_{i}=I_{{\mathcal{M}}_{1}}({\mathbf{x}}_{i})$. For any $\delta>0$, if inequality (8) holds, then for any $\epsilon>0$, there exists a ReLU network $g$ with depth at most $O(\log\beta+d\log\frac{1}{\tau}+\log\log\frac{1}{\tau\delta})$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon}+\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau\delta
}+D\tau^{-d}\log\frac{1}{\tau\delta})$, such that

$$ $P(R(g)\leq\epsilon)>1-\delta,$ (10) $$

where $R(g)=\int_{{\mathcal{M}}}(g-I_{{\mathcal{M}}_{1}})^{2}\mu(\mathbf{x})d\mathbf{x}$ with any continuous distribution $\mu$.

Proof Sketch. Since ${\mathcal{M}}={\mathcal{M}}_{1}\sqcup{\mathcal{M}}_{0}$ is from thickened $1$-manifold family, it has a topological representative ${\mathcal{M}}^{\prime}={\mathcal{M}}^{\prime}_{1}\sqcup{\mathcal{M}}^{\prime}_
{0}\subset\mathbb{R}^{d}$, where ${\mathcal{M}}^{\prime}_{1}$ and ${\mathcal{M}}^{\prime}_{0}$ are topological representatives of ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$, respectively. The proof follows Figure 3, by first constructing simplicial approximations $|K|$ and $|L|$ of ${\mathcal{M}}$ and ${\mathcal{M}}^{\prime}$, respectively. Then we represent a simplicial homeomorphism $\phi:|K|\to|L|$ by a neural network $N_{\phi}$, where $K$ is constructed from ${\mathcal{M}}$ and $L$ from ${\mathcal{M}}^{\prime}$. Built on the top of this, a projection from ${\mathcal{M}}$ to its simiplicial approximation $|K|$ is represented by another network $N_{p}$. The overall network can be constructed by $g=h\circ N_{\phi}\circ N_{p}$. The proof is completed by first constructing the network $g$, and then bounding the approximation error.

Upon examining the depth and size of the neural network, it becomes evident that the topological complexity, denoted by $\beta$, and the geometric complexity, symbolized by $\tau$, are distinctly delineated. The topological complexity contributes $O\left(\frac{d^{2}\beta^{2}}{\epsilon}\right)$ to the overall network size. In contrast, geometry contributes $O\left(\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau\delta}+D\tau^{-d}\log\frac{1}{
\tau\delta}\right)$.

###### Proposition 3 (Theorem 3.1 in Niyogi et al. ( 2008 ) ) .

###### Theorem 2 (Main Theorem) .

## 5 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, it is important to also appreciate the manifold’s topological characteristics. These characteristics not only offer an alternative perspective on data structures but also influence network size in significant ways.

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 its applications in modern AI systems.

## Appendix A Appendix

In this section, we formally prove the theoretical findings presented in the primary manuscript. Initially, we utilize some necessary definitions and existing results. Then we prove the network size bound for fundamental solid manifolds and general topological representatives.

### A.1 Additional Definitions

The first definition is Betti number, 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 () but is tailed for simplification. We first define simplicial homology for simplicial complexes. (Actually for $\Delta$-complexes. we simplify it to avoid introducing $\Delta$-complexes.) Then extend it to singular homology that can be applied to manifolds.

Simplicial Homology. Let $K$ be a simplicial complex, and let $K^{k}$ be the set of all $k$-dimensional simplices in $K$. The set of $K^{k}$ together with the field $\mathbb{Z}_{2}$ forms a group $C_{k}(K)$. It is a vector space defined on $\mathbb{Z}_{2}$ with $K^{k}$ as a basis. The element of $C_{k}(K)$ is called a $k$-chain. Let $\sigma\in K^{k}$ be a $k$-simplex. The boundary $\partial_{k}(\sigma)$ is the collection of its $(k-1)$-dimensional faces, which is a $k-1$-simplicial complex. The boudnary operator is linear, i.e.

$$ $\partial_{k}(z_{1}\sigma_{1}+z_{2}\sigma_{2})=z_{1}\partial_{k}(\sigma_{1})+z_ {2}\partial_{k}(\sigma_{2}).$ $$

The boundary operator $\partial_{k}:C_{k}(K)\to C_{k-1}(K)$ introduces a chain complex

$$ $\cdots\xrightarrow[]{}C_{d}\xrightarrow[]{\partial_{d}}C_{d-1}\xrightarrow[]{ \partial_{d-1}}C_{d-2}\xrightarrow[]{}\cdots\xrightarrow[]{}C_{0}\xrightarrow[ ]{\partial_{0}}\emptyset.$ $$

$d$ is the maximum dimension of $K$. $\text{Ker}\,\partial_{k}$ is the collection of $k$-chains with empty boundary and $\text{Im}\,\partial_{k}$
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_{k}=\text{Ker}\,\partial_{k}/\text{Im}\,\partial_{k+1}$. The $k$-th Betti number is defined by

$$ $\beta_{k}=\text{rank}\,H_{k}.$ $$

Singular Homology. Given a topological space $X$, the $k$-th singular chain group $C_{k}(X)$ is defined as the free Abelian group generated by the continuous maps $\phi:K^{k}\to X$, where $K^{k}$ is the standard $k$-simplex in $\mathbb{R}^{k}$. Each such map is referred to as a singular $k$-simplex in $X$.

A boundary operator $\partial_{k}:C_{k}(X)\to C_{k-1}(X)$ can be defined as:

$$ $\partial\phi=\sum_{i=0}^{n}(-1)^{i}\phi|_{[v_{0},\cdots,\hat{v}_{i},\cdots,v_{ n}]},$ $$

where $\phi|_{[v_{0},\cdots,\hat{v}_{i},\cdots,v_{n}]}$ represents the restriction of $\sigma$ to the $i$-th face of $K^{k}$.

The $k$-th singular homology group $H_{k}(X)$ is then represented as the quotient:

$$ $H_{k}(X)=\text{Ker}\,\partial_{k}/\text{Im}\,\partial_{k+1}.$ $$

The $k$-th Betti number is still defined as $\beta_{k}=\text{rank}\,H_{k}(X)$.

Connected Sum of Thickened 1-Manifold. Let ${\mathcal{M}}={\mathcal{M}}^{1}\times B^{d}$ and ${\mathcal{N}}={\mathcal{N}}^{1}\times B^{d}$ be two $d$-thickened 1-manifolds, where ${\mathcal{M}}^{1}$ and ${\mathcal{N}}^{1}$ are compact 1-manifolds (with or without boundary), and $B^{d}$ is a $d$-dimensional closed ball. We define the *connected sum* ${\mathcal{M}}\#{\mathcal{N}}$ by performing connected sum on their boundaries and then extend the gluing to the interior. The process is defined as:

- 1.
The connected sum of boundaries. The boundaries of ${\mathcal{M}}$ and ${\mathcal{N}}$ are closed manifolds, where $\partial{\mathcal{M}}={\mathcal{M}}^{1}\times S^{d-1}$ and $\partial{\mathcal{N}}={\mathcal{N}}^{1}\times S^{d-1}$. Two open neighborhoods $U\subset\partial{\mathcal{M}}$ and $V\subset\partial{\mathcal{N}}$ are removed from the boundaries. Then a homeomorphism $h:\partial U\to\partial V$ is defined to match the resulting boundaries. Then glue $\partial{\mathcal{M}}\setminus U$ and $\partial{\mathcal{N}}\setminus V$ along $\partial U$ and $\partial V$ via $h$, forming $\partial({\mathcal{M}}\#{\mathcal{N}})$.
- 2.
Extend the gluing to the interiors of ${\mathcal{M}}$ and ${\mathcal{N}}$ by identifying corresponding points in the neighborhoods adjacent to $U$ and $V$.

Figure: Figure A.1: Illustration of connected sum.
Refer to caption: x7.png

### 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 et al. ( 2018 ) ) .

Given any piecewise linear function ${\mathbb{R}}\to{\mathbb{R}}$ with $p$ pieces there exists a 2-layer ReLU network with at most $p$ nodes that can represent $f$. Moreover, if the rightmost or leftmost piece of a the piecewise linear function has 0 0 slope, then we can compute such a $p$ piece function using a 2-layer ReLU network with size $p-1$.

###### Lemma 3 (Function Composition, Lemma D.1. in Arora et al. ( 2018 ) ) .

If $f_{1}:{\mathbb{R}}^{d}\to{\mathbb{R}}^{m}$ is represented by a ReLU DNN with depth $k_{1}+1$ and size $s_{1}$, and $f_{2}:{\mathbb{R}}^{m}\to{\mathbb{R}}^{n}$ is represented by a ReLU DNN with depth $k_{2}+1$ and size $s_{2}$, then $f_{2}\circ f_{1}$ can be represented by a ReLU DNN with depth $k_{1}+k_{2}+1$ and size $s_{1}+s_{2}$.

###### Lemma 4 (Function Addition, Lemma D.2. in Arora et al. ( 2018 ) ) .

If $f_{1}:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$ is represented by a ReLU DNN with depth $k+1$ and size $s_{1}$,and $f_{2}:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$ is represented by a ReLU DNN with depth $k+1$ and size $s_{2}$, then $f_{1}+f_{2}$ can be represented by a ReLU DNN with depth $k+1$ and size $s_{1}+s_{2}$.

###### Lemma 5 (Taking maximums, Lemma D.3. in Arora et al. ( 2018 ) ) .

Let $f_{1},...,f_{m}:\mathbb{R}^{n}\to\mathbb{R}$ be the functions that each can be represented by ReLU networks with depth $k_{i}+1$ and size $s_{i}$, $i=1,...,m$. Then the function $f:\mathbb{R}^{n}\to\mathbb{R}$ defined as $f=\max\{f_{1},...,f_{m}\}$ can be represented by a ReLU network of depth at most $\max\{k1,...,k_{m}\}+\log(m)+1$ and size at most $s_{1}+...+s_{m}+4(2m-1)$.

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 L-Lipschitz function $f:{\mathbb{R}}\to{\mathbb{R}}$ which is constant outside a bounded interval $[a,b]$, and for any $\epsilon>0$, there exits a two-layer ReLU network $h(x)$ with at most $\lceil L(b-a)/\epsilon\rceil+1$ nodes, such that

$$ $\sup_{x\in{\mathbb{R}}}|f(x)-h(x)|<\epsilon.$ $$

###### 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 $\epsilon$ and use a two-layer ReLU network to represent the piece-wise linear function.

We first cut the interval equally into $m$ sections $[a,b]=\bigcup_{i=1}^{m}[a+(i-1)\delta,a+i\delta]$, where $\delta=(b-a)/m$. For each interval $I_{i}=[a+(i-1)\delta,a+i\delta]$, we denote $f_{i}(x)=f|_{I_{i}}$. Then $\forall x_{1},x_{2}\in I_{i}$, $|f_{i}(x_{1})-f_{i}(x_{2})|\leq L|x_{1}-x_{2}|\leq L\delta$. Let $h_{i}(x)$ be the linear function defined on this interval and connect $(a+(i-1)\delta,f_{i}(a+(i-1)\delta))$ and $(a+i\delta,f_{i}(a+i\delta))$. Then we can bound the difference between $f_{i}(x)$ and $h_{i}(x)$ by

$$ $\displaystyle\begin{split}|f_{i}(x)-h_{i}(x)|&\leq\max\{|\max f_{i}(x)-\min h_ {i}(x)|,|\min f_{i}(x)-\max h_{i}(x)|\}\\ &=\max\{|\max f_{i}(x)-f_{i}(a+(i-1)\delta)|,|\min f_{i}(x)-f_{i}(a+i\delta))| \}\\ &\leq L\delta.\end{split}$ (A.1) $$

The second line assumes $h_{i}(x)$ is non-decreasing. The other case can also be easily verified. By setting $m=\lceil\frac{L(b-a)}{\epsilon}\rceil$, for every interval, the error is controlled by $\epsilon$. Let $h(x)$ be the collection of all $h_{i}$ and also the constant outside of $[a,b]$, so we have $\sup_{x\in{\mathbb{R}}}|f(x)-h(x)|<\epsilon$.

$h(x)$ is a piece-wise linear function with $m+2$ pieces. According to Lemma 2, there exists a 2-layer ReLU network with at most $m+1$ pieces that can represent $h(x)$. Proof done.
∎

###### Lemma 2 (Theorem 2.2. in Arora et al. ( 2018 ) ) .

###### Lemma 3 (Function Composition, Lemma D.1. in Arora et al. ( 2018 ) ) .

###### Lemma 4 (Function Addition, Lemma D.2. in Arora et al. ( 2018 ) ) .

###### Lemma 5 (Taking maximums, Lemma D.3. in Arora et al. ( 2018 ) ) .

###### Lemma 6 (Lipschitz Function Approximation, adapted from Lemma 11 in Eldan & Shamir ( 2016 ) ) .

###### Proof.

### A.3 Approximating Fundamental Solid Manifolds

Now we are in a good position to prove Proposition 1 and 2.

###### Proposition 1 (Approximating a $\mathbb{R}^{d}$ Ball, adapted from Theorem 2 in Safran & Shamir ( 2016 ) ) .

Given $\epsilon>0$, there exists a ReLU network $h:{\mathbb{R}}^{d}\to{\mathbb{R}}$ with $3$ layers and with size at most $4d^{2}r^{2}/\epsilon+2d+2$, which can approximate the indicator function $I_{B^{d}_{r}}$ within error $R(h)\leq\epsilon$ for any continuous distribution $\mu({\mathbf{x}})$.

###### Proof.

We generally follow the original proof but derive a slightly different bound with fewer parameters. The proof is organized by first using a non-linear layer to approximate a truncated square function and then using another non-linear layer to approximate a threshold function.
Consider the truncated square function

$$ $l(x;r)=\min\{x^{2},r^{2}\}.$ (A.2) $$

Clearly $l(x;r)$ is a Lipschitz function with Lipschitz constant $2r$. Applying Lemma 6, we have a 2-layer ReLU network $h_{11}$ that can approximate $l(x;r)$ with

$$ $\sup_{x\in\mathbb{R}}\big{|}h_{11}(x)-l(x)\big{|}\leq\epsilon_{1},$ (A.3) $$

with at most $2r^{2}/\epsilon_{1}+2$ nodes. Now for ${\mathbf{x}}\in\mathbb{R}^{d}$, let

$$ $h_{1}({\mathbf{x}})=\sum_{i=1}^{d}h_{1i}(x_{i}).$ (A.4) $$

Note that $h_{1}$ is also a 2-layer network because no extra non-linear operation is introduced in equation A.4, and has size at most $2dr^{2}/\epsilon_{1}+2d$. This can also be verified by Lemma 4. Let

$$ $L({\mathbf{x}})=\sum_{i}^{d}L(x_{i};r),$ (A.5) $$

and we have

$$ $\sup_{{\mathbf{x}}}\big{|}h_{1}({\mathbf{x}})-L({\mathbf{x}})\big{|}\leq d \epsilon_{1}.$ (A.6) $$

Let $\epsilon_{1}=d\epsilon_{1}$, then $h_{1}$ has size at most $2d^{2}r^{2}/\epsilon_{1}+2d$. Although $L({\mathbf{x}})$ is different from $\sum x_{i}^{2}$, the trick here is to show $B_{r}^{d}=\{{\mathbf{x}}:L({\mathbf{x}})\leq r^{2}\}$.

On the one hand, if $L(rvx)\leq r^{2}$, remember that

$$ $L({\mathbf{x}})=\sum_{i=1}^{d}\min\{x_{1}^{2},r^{2}\}\leq r^{2}.$ (A.7) $$

This means for all $x_{i}$, $x_{i}\leq r^{2}$. Therefore, $L({\mathbf{x}})=\sum_{i=1}^{d}x_{i}^{2}$.
On the other, $L({\mathbf{x}})>r^{2}$ only happens when there exists a $i$, such that $x_{i}^{2}>r^{2}$. Thus, ${\mathbf{x}}\notin B_{r}^{d}$. Consequently, one can represent $I_{B_{r}^{d}}$ by $L({\mathbf{x}})\leq r^{2}$.

The next step towards this proposition is to construct another 2-layer ReLU network to threshold $L({\mathbf{x}})$. Consider

$$ $f(x)=\begin{cases}1,&x<r^{2}-\delta,\\ \frac{r^{2}-x}{\delta},&x\in[r^{2}-\delta,r^{2}],\\ 0,&x>r^{2}.\end{cases}$ (A.8) $$

Note that $f$ is a 3-piece piece-wise linear function that approximates a threshold function. According to Lemma 2, a 2-layer ReLU network $h_{2}$ with size 2 can represent $f$. The function $f\circ L({\mathbf{x}})$ can then be estimated by a 3-layer network $h=h_{2}\circ h_{1}$, whose size is $2d^{2}r^{2}/\epsilon_{1}+2d+2$. The next step is to bound the error between $h$ and $I_{B_{r}^{d}}$. We consider the $L_{2}$-type bound $||h({\mathbf{x}})-I_{B_{r}^{d}}({\mathbf{x}})||_{L_{2}(\mu)}=\int_{\mathbb{R}^
{d}}(h({\mathbf{x}})-I_{B_{r}^{d}}({\mathbf{x}}))^{2}\mu({\mathbf{x}})d{
\mathbf{x}}$. We divide the integral into two parts

$$ $\displaystyle\begin{split}&||h({\mathbf{x}})-I_{B_{r}^{d}}({\mathbf{x}})||_{L_ {2}(\mu)}\\ &\leq||f\circ L({\mathbf{x}})-I_{B_{r}^{d}}({\mathbf{x}})||_{L_{2}(\mu)}+||f \circ L({\mathbf{x}})-h_{2}\circ h_{1}({\mathbf{x}})||_{L_{2}(\mu)}\\ &=I_{1}+I_{2}.\end{split}$ (A.9) $$

Since $\mu({\mathbf{x}})$ is continuous, there exists $\delta$ such that

$$ $\int_{S_{\delta}}\mu({\mathbf{x}})d{\mathbf{x}}\leq\epsilon_{2}.$ (A.10) $$

$S_{\delta}=\{{\mathbf{x}}\in{\mathbb{R}}^{d}:r^{2}-\delta\leq\sum_{i=1}^{d}x_{
i}^{2}\leq r^{2}\}$. Combine equation A.8 we have

$$ $\displaystyle\begin{split}I_{1}&=\int_{{\mathbb{R}}^{d}}(f\circ L({\mathbf{x}} )-I_{B_{r}^{d}}({\mathbf{x}}))^{2}\mu({\mathbf{x}})d{\mathbf{x}}\\ &=\int_{S_{\delta}}(f\circ L({\mathbf{x}})-I_{B_{r}^{d}}({\mathbf{x}}))^{2}\mu ({\mathbf{x}})d{\mathbf{x}}\\ &=\int_{S_{\delta}}(f\circ L({\mathbf{x}})-1)^{2}\mu({\mathbf{x}})d{\mathbf{x} }\\ &\leq\int_{S_{\delta}}\mu({\mathbf{x}})d{\mathbf{x}}\\ &\leq\epsilon_{2}.\end{split}$ (A.11) $$

The first inequality is because $f\in[0,1]$, such that $(f\circ L({\mathbf{x}})-1)^{2}\leq 1$.
The second part of the error can be easily bounded by its infinity norm.

$$ $I_{2}=||f\circ L({\mathbf{x}})-h_{2}\circ h_{1}({\mathbf{x}})||_{L_{2}(\mu)} \leq||f\circ L({\mathbf{x}})-h_{2}\circ h_{1}({\mathbf{x}})||_{\infty}\leq \epsilon_{1}.$ (A.12) $$

The last inequality is because $h_{2}$ is the exact representation of $f$, the error only occurs between $L({\mathbf{x}})$ and $h_{1}$.
Combine A.11 and A.12, and let $\epsilon_{1}=\epsilon_{2}=\epsilon/2$, we have

$$ $||h({\mathbf{x}})-I({\mathbf{x}})||_{L_{2}(\mu)}\leq\epsilon.$ (A.13) $$

The size of network $h$ is then bounded by $4d^{2}r^{2}/\epsilon+2d+2$.
∎

###### Proposition 2 (Approximating a Solid Torus) .

Given $\epsilon>0$, there exists a ReLU network $h:{\mathbb{R}}^{d}\to{\mathbb{R}}$ with $5$ layers and with size at most $\frac{2d}{\epsilon}(4(d-1)(R+r)^{2}+8r^{2}+\frac{r}{\sqrt{R-r}})+9$, which can approximate the indicator function $I_{T_{r,R}^{d}}$ within error $R(h)\leq\epsilon$ for any continuous distribution $\mu({\mathbf{x}})$.

###### Proof.

The proof is 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,

$$ $\displaystyle l_{1}(x;\gamma)=\min\{x^{2},\gamma^{2}\},$ $\displaystyle l_{2}(x;\gamma_{1},\gamma_{2})=\min\{\max\{\sqrt{x},\gamma_{1}\} ,\gamma_{2}\},(\gamma_{1}<\gamma_{2}).$ $$

The Lipschitz constants for $l_{1}$ and $l_{2}$ are $2\gamma$ and $\frac{1}{2\sqrt{\gamma_{1}}}$, respectively. By Lemma 6, there is a 2-layer ReLU network to approximate $l_{1}$ and $l_{2}$ with size $\lceil 4\gamma^{2}/\epsilon_{1}\rceil+1$ and $\lceil(\gamma_{2}-\gamma_{1})/(2\epsilon_{1}\sqrt{\gamma_{1}})\rceil+1$, respectively. Let

$$ $L({\mathbf{x}})=l_{1}(x_{d};r)+l_{1}(l_{2}(\sum_{i=1}^{d-1}l_{1}(x_{i};R+r);R- r,R+r)-R;r).$ (A.14) $$

Then it is time to show $T^{d}_{r,R}=\left\{\mathbf{x}\in\mathbb{R}^{d}:x_{d}^{2}+\left(\sqrt{\sum_{i=1
}^{d-1}x_{i}^{2}}-R\right)^{2}\leq r^{2}\right\}=\{{\mathbf{x}}:L({\mathbf{x}}
)\leq r^{2}\}$.
For ${\mathbf{x}}\in I_{T^{d}_{r,R}}({\mathbf{x}})$, the following inequalities hold

$$ $\displaystyle x_{i}^{2}\leq(R+r)^{2},1\leq i\leq d-1,$ (A.15) $\displaystyle R+r\geq\sqrt{\sum_{i=1}^{d-1}x_{i}^{2}}\geq R-r,$ (A.16) $\displaystyle x_{d}^{2}\leq r^{2},(\sqrt{\sum_{i=1}^{d-1}x_{i}^{2}}-R)^{2}\leq r ^{2}.$ (A.17) $$

These indicate that $L({\mathbf{x}})=x_{d}^{2}+\left(\sqrt{\sum_{i=1}^{d-1}x_{i}^{2}}-R\right)^{2}
\leq r^{2}$, when ${\mathbf{x}}\in T^{d}_{r,R}$. And when ${\mathbf{x}}\notin T^{d}_{r,R}$, if $L({\mathbf{x}})=x_{d}^{2}+\left(\sqrt{\sum_{i=1}^{d-1}x_{i}^{2}}-R\right)^{2}$ still holds, clearly $L({\mathbf{x}})>r^{2}$. Otherwise, one of the inequalities in A.15, A.16 and A.17 must break. If one of A.17 breaks, then clearly $L({\mathbf{x}})>r^{2}$. If A.16 does not hold, then $(\sqrt{x_{1}^{2}+x_{2}^{2}}-R)^{2}>r^{2}$, resulting $L({\mathbf{x}})>r^{2}$. The violation of A.15 resulting violation of A.16, which then leads to $L({\mathbf{x}})>r^{2}$.

To see how a ReLU network can estimate $L({\mathbf{x}})$, we start by estimating each of its component. We define the following 2-layer networks.
To make the overall network take ${\mathbf{x}}\in{\mathbb{R}}^{d}$ as input, we consider the structure in figure A.2.

Figure: Figure A.2: Network construction.

The size of parts in the network is provided in table A.1.

**Table A.1: Sub-network Size.**
| Network | Target | Size |
| --- | --- | --- |
| $h_{1i}$ | $l_{1}(x_{i};R+r)$ | $s_{1i}=\lceil 4(R+r)^{2}/\epsilon_{1}\rceil+1$ |
| $h_{2}$ | $l_{2}(x;R-r,R+r)$ | $s_{2}=\lceil r/(\epsilon_{1}\sqrt{R-r})\rceil+1$ |
| $h_{31}$ | $l_{1}(x;,r)$ | $s_{31}=\lceil 4r^{2}/\epsilon_{1}\rceil+1$ |
| $h_{32}$ | $l_{1}(x_{d};,r)$ | $s_{32}=\lceil 4r^{2}/\epsilon_{1}\rceil+1$ |

By Lemma 4 and Lemma 3 and the given structure, a ReLU network $\tilde{L}$ with depth $4$ and size $(d-1)s_{11}+s_{2}+s_{31}+s_{32}+2$, where $d=3$, can approximate $L({\mathbf{x}})$ such that

$$ $\sup_{{\mathbf{x}}}|L({\mathbf{x}})-\tilde{L}({\mathbf{x}})|\leq d\epsilon_{1}.$ (A.18) $$

The next step is to threshold $L({\mathbf{x}})$. Consider a function

$$ $f(x)=\begin{cases}1,&x<r^{2}-\delta,\\ \frac{r^{2}-x}{\delta},&x\in[r^{2}-\delta,r^{2}],\\ 0,&x>r^{2}.\end{cases}$ (A.19) $$

This function approximates a thresholding function $I[x\leq r^{2}]$ but with error inside the interval $[r^{2}-\delta,r^{2}]$. By Lemma 2, a 2-layer ReLU network $\tilde{f}$ with size $2$ can represent $f(x)$. Then $\tilde{f}\circ\tilde{L}$ is a ReLU network with depth 5 and size $(d-1)s_{11}+s_{2}+s_{31}+s_{32}+4$, such that

$$ $\sup_{{\mathbf{x}}}|f\circ L({\mathbf{x}})-\tilde{f}\circ\tilde{L}({\mathbf{x} })|\leq\epsilon_{1},$ (A.20) $$

with letting $\epsilon_{1}=\epsilon_{1}/d$.

Let $h({\mathbf{x}})=\tilde{f}\circ\tilde{L}({\mathbf{x}})$. We claim that $h({\mathbf{x}})$ is the desired network with depth 5 and size

$$ $\displaystyle\begin{split}&(d-1)s_{11}+s_{2}+s_{31}+s_{32}+4\\ &=\frac{d}{\epsilon_{1}}(4(d-1)(R+r)^{2}+8r^{2}+\frac{r}{\sqrt{R-r}})+9\\ &=O(\frac{d^{2}}{\epsilon_{1}}).\end{split}$ (A.21) $$

To finalize our proof, we just need to bound the error $||h({\mathbf{x}})-I_{T^{d}_{r,R}}({\mathbf{x}})||_{L_{2}(\mu)}$. The proof follows proof of Proposition 1. The error is divided into two parts and is bounded separately. The only difference is we define $S_{\delta}$ to be
$S_{\delta}=\left\{{\mathbf{x}}\in{\mathbb{R}}^{d}:r^{2}-\delta\leq x_{d}^{2}+
\left(\sqrt{\sum_{i=1}^{d-1}x_{i}^{2}}-R\right)^{2}\leq r^{2}\right\}$, such that

$$ $\int_{S_{\delta}}\mu({\mathbf{x}})d{\mathbf{x}}\leq\epsilon_{2}.$ (A.22) $$

We can get $I_{1}\leq\epsilon_{2}$, and $I_{2}\leq\epsilon_{1}$. Let $\epsilon_{1}=\epsilon_{2}=\epsilon/2$, we have

$$ $||h({\mathbf{x}})-I({\mathbf{x}})||_{L_{2}(\mu)}\leq\epsilon.$ (A.23) $$

And $h$ has size at most $\frac{2d}{\epsilon}(4(d-1)(R+r)^{2}+8r^{2}+\frac{r}{\sqrt{R-r}})+9$.
∎

###### Proposition 1 (Approximating a ℝ d superscript ℝ 𝑑 \mathbb{R}^{d} blackboard_R start_POSTSUPERSCRIPT italic_d end_POSTSUPERSCRIPT Ball, adapted from Theorem 2 in Safran & Shamir ( 2016 ) ) .

###### Proof.

###### Proposition 2 (Approximating a Solid Torus) .

###### Proof.

### 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 1 (Topological Representative) .

Let ${\mathcal{M}}\subset{\mathbb{M}}$ be a $d$-dimensional manifold from the thickened 1-manifold family. There exist a set of $m_{1}$ $d$-balls ${\mathcal{B}}=\{B_{r_{i}}^{d}({\mathbf{c}}_{i})\}_{i=1}^{m_{1}}$ and a set of $m_{2}$ solid $d$-tori ${\mathcal{T}}=\{T_{r_{i},R_{i}}^{d}({\mathbf{c}}_{i})\}_{i=1}^{m_{2}}$, such that ${\mathcal{M}}$ is homeomorphic to the union $(\bigcup_{B\in{\mathcal{B}}}B)\cup(\bigcup_{T\in{\mathcal{T}}}T)$, where $m_{1}+m_{2}\leq\beta({\mathcal{M}})$ is a constant integer. We term ${\mathcal{M}}^{\prime}=(\bigcup_{B\in{\mathcal{B}}}B)\cup(\bigcup_{T\in{
\mathcal{T}}}T)$ as the topological representative of ${\mathcal{M}}$.

###### Proof.

Since ${\mathcal{M}}\subset{\mathbb{M}}$, regarding the definition, ${\mathcal{M}}$ is homeomorphic to connect sum or disjoint union of $m$ thickened 1-manifolds. A thickened $1$-manifold is denoted as ${\mathcal{M}}^{1}\times B^{d-1}$. And based on the classification theorem of $1$-manifold, ${\mathcal{M}}^{1}$ is homeomorphic either to a circle $S^{1}$ or $I=[0,1]$. If ${\mathcal{M}}^{1}\sim S^{1}$, then ${\mathcal{M}}^{1}\times B^{d-1}\sim S^{1}\times B^{d-1}\sim T_{r,R}^{d}$. If ${\mathcal{M}}^{1}\sim I$, then ${\mathcal{M}}^{1}\times B^{d-1}\sim I\times B^{d-1}\sim B_{r}^{d}$. Now let ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$ be two thickened $1$-manifold, the connected sum of ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$, denoted by ${\mathcal{M}}_{1}\oplus{\mathcal{M}}_{2}$, can be represented by the union of two manifolds ${\mathcal{M}}_{1}\cup{\mathcal{M}}_{2}$. Since ${\mathcal{M}}$ is homeomorphic to connect sum or disjoint union of $m$ thickened 1-manifolds, suppose $m_{1}$ of them are homeomorphic to $B_{r}^{d}$ and $m_{2}$ of them are homeomorphic to $T_{r,R}^{d}$. Therefore, ${\mathcal{M}}\sim(\bigcup_{B\in{\mathcal{B}}}B)\cup(\bigcup_{T\in{\mathcal{T}}
}T)$.

Notice that among ${\mathcal{B}}$, the union is disjoint union, otherwise the union is still homeomorphic to a $B_{r}^{d}$. Similarly, the union between ${\mathcal{B}}$ and ${\mathcal{T}}$ is also disjoint union, otherwise the union is still homeomorphic to a solid torus $T_{r,R}^{d}$. The union among ${\mathcal{T}}$ could be joint union or disjoint union. For two solid tori $T_{1}^{d}$ and $T_{2}^{d}$, $\beta(T_{1}^{d})=\beta(T_{1}^{d})=2$. $\beta(T_{1}^{d}\cup T_{2}^{d})\geq 3>2$. Overall, $\beta({\mathcal{M}})\geq m_{1}+m_{2}$.

∎

###### Lemma 7 (Manifold Union) .

${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$ are two manifolds in $\mathbb{R}^{d}$. $I_{{\mathcal{M}}_{1}}$ can be approximated by a ReLU network $h_{1}$ with depth $d_{1}+1$ and size at most $s_{1}$ with error $R(h_{1})<\epsilon_{1}$, $I_{{\mathcal{M}}_{2}}$ can be approximated by a ReLU network $h_{2}$ with depth $d_{2}+1$ and size at most $s_{2}$ with error $R(h_{2})<\epsilon_{2}$. Then $I_{{\mathcal{M}}_{1}\cup{\mathcal{M}}_{2}}$ can be approximated within error $\epsilon_{1}+\epsilon_{2}$ by a ReLU network with depth at most $\max\{d_{1},d_{2}\}+2$ and size at most $s_{1}+s_{2}+2$.

###### Proof.

We represent $I_{{\mathcal{M}}_{1}\cup{\mathcal{M}}_{2}}=I_{x>0}\circ(I_{{\mathcal{M}}_{1}}+
I_{{\mathcal{M}}_{2}})$ by a threshold function $I_{x>0}$. The threshold function can be approximate by a function

$$ $f(x)=\begin{cases}0,&x\leq 0\\ \frac{x}{\delta},&x\in(0,\delta)\\ 1,&x\geq\delta.\end{cases}$ (A.24) $$

with errors only in $(0,\delta)$. $f$ can be represented by a 2-layer ReLU network $h_{f}$ with size $2$. Then if let $h=h_{f}\circ(h_{1}+h_{2})$, according to Lemma 4 and 3, $h$ is a neural network with depth $\max\{d_{1},d_{2}\}+2$ and size $s_{1}+s_{2}+2$. Then we bound the error

$$ $\displaystyle\begin{split}||h-I_{{\mathcal{M}}_{1}\cup{\mathcal{M}}_{2}}||_{L_ {2}(\mu)}&=||h_{f}\circ(h_{1}+h_{2})-I_{x>0}\circ(I_{{\mathcal{M}}_{1}}+I_{{ \mathcal{M}}_{2}})||_{L_{2}(\mu)}\\ &\leq||h_{f}\circ(h_{1}+h_{2})-f\circ(I_{{\mathcal{M}}_{1}}+I_{{\mathcal{M}}_{ 2}})||_{L_{2}(\mu)}\\ &+||f\circ(I_{{\mathcal{M}}_{1}}+I_{{\mathcal{M}}_{2}})-I_{x>0}\circ(I_{{ \mathcal{M}}_{1}}+I_{{\mathcal{M}}_{2}})||_{L_{2}(\mu)}\\ &\leq||h_{f}\circ(h_{1}+h_{2})-h_{f}\circ(I_{{\mathcal{M}}_{1}}+I_{{\mathcal{M }}_{2}})||_{L_{2}(\mu)}\\ &\leq||h_{f}||_{\infty}||(h_{1}+h_{2})-(I_{{\mathcal{M}}_{1}}+I_{{\mathcal{M}} _{2}})||_{L_{2}(\mu)}\\ &\leq||(h_{1}+h_{2})-(I_{{\mathcal{M}}_{1}}+I_{{\mathcal{M}}_{2}})||_{L_{2}( \mu)}\\ &\leq\epsilon_{1}+\epsilon_{2}\end{split}$ (A.25) $$

∎

###### Theorem 1 (Complexity Arising from Topology) .

Suppose ${\mathcal{M}}^{\prime}$ is the topological representative of $d$-manifold from the thickened $1$-manifold family. Given $\epsilon>0$, there exists a ReLU network $h:\mathbb{R}^{d}\to\mathbb{R}$ with depth at most $O(\log\beta)$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon})$, that can approximate the indicator function $I_{{\mathcal{M}}^{\prime}}$ with error $R(h)\leq\epsilon$ for any continuous distribution $\mu$ over $\mathbb{R}^{d}$. $\beta$ is the topological complexity of ${\mathcal{M}}^{\prime}$.

###### Proof.

Since ${\mathcal{M}}^{\prime}$ is a topological representative, according to Lemma 1, there exist a set of $m_{1}$ $d$-balls ${\mathcal{B}}=\{B_{r_{i}}^{d}({\mathbf{c}}_{i})\}_{i=1}^{m_{1}}$ and a set of $m_{2}$ solid $d$-tori ${\mathcal{T}}=\{T_{r_{i},R_{i}}^{d}({\mathbf{c}}_{i})\}_{i=1}^{m_{2}}$, such that ${\mathcal{M}}^{\prime}=(\bigcup_{B\in{\mathcal{B}}}B)\cup(\bigcup_{T\in{
\mathcal{T}}}T)$. Let $m=m_{1}+m_{2}$. According to proposition 7, $I_{{\mathcal{M}}^{\prime}}$ can be approximated by a ReLU network $h$ with depth at most $\max\{d_{1},d_{2},...,d_{m}\}+\log m$ and size at most $\sum_{i=1}^{m}s_{i}+\log m$, with error $R(h)\leq\sum_{i=1}^{m}\epsilon_{i}$. Then according to Proposition 1 and 2, $s_{i}\sim O(d^{2}/\epsilon_{i})$, $d_{i}\sim O(1)$ and take $\epsilon_{i}$ to be all the same for all $i=[m]$. Let $\epsilon=m\epsilon_{i}$ and note that $m\leq\beta$. We have $h$ has depth at most $O(\log\beta)$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon})$, and can approximate $I_{{\mathcal{M}}^{\prime}}$ with error $R(h)\leq\epsilon$.
∎

###### Lemma 1 (Topological Representative) .

###### Proof.

###### Lemma 7 (Manifold Union) .

###### Proof.

###### Theorem 1 (Complexity Arising from Topology) .

###### Proof.

### A.5 Overall Complexity

We present a result from Gonzalez-Diaz et al. (), which gives a bound of network size to represent a simplicial map.

###### Proposition 6 (Adapted from Theorem 4 in Gonzalez-Diaz et al. ( 2019 ) ) .

Let us consider a simplicial map $\phi_{c}:|K|\to|L|$ between the underlying space of two finite pure simplicial complexes $K$ and $L$. Then a two-hidden-layer feed-forward network ${\mathcal{N}}_{\phi}$ such that $\phi_{c}(x)={\mathcal{N}}_{\phi}(x)$ for all $x\in|K|$ can be explicitly defined. The size of $N_{f}$ is $D+d+k(D+1)+l(d+1)$, where $D=\text{dim}(|K|)$ and $d=\text{dim}(|L|)$, $k$ and $l$ are the number of simplices in $K$ and $L$, respectively.

###### Theorem 2 (Main Theorem) .

Let ${\mathcal{M}}={\mathcal{M}}_{1}\sqcup{\mathcal{M}}_{0}\subset\mathbb{R}^{D}$ be a $d$-dimensional manifold from the thickened $1$-manifold family. ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{0}$ are two disjoint sub-manifolds of ${\mathcal{M}}$ representing two classes. The condition number of ${\mathcal{M}}$ is $\frac{1}{\tau}$ and the total Betti number of ${\mathcal{M}}_{1}$ is $\beta$. Given a training set $\{({\mathbf{x}}_{i},y_{i})|{\mathbf{x}}_{i}\in{\mathcal{M}},y_{i}\in\{0,1\}\}_
{i=1}^{n}$, where ${\mathbf{x}}_{i}$ are sampled i.i.d. from ${\mathcal{M}}$ by a uniform distribution, and $y_{i}=I_{{\mathcal{M}}_{1}}({\mathbf{x}}_{i})$. For any $\delta>0$, if inequality (8) holds, then for any $\epsilon>0$, there exists a ReLU network $g$ with depth at most $O(\log\beta+d\log\frac{1}{\tau}+\log\log\frac{1}{\tau\delta})$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon}+\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau\delta
}+D\tau^{-d}\log\frac{1}{\tau\delta})$, such that

$$ $P(R(g)\leq\epsilon)>1-\delta,$ (A.26) $$

where $R(g)=\int_{{\mathcal{M}}}(g-I_{{\mathcal{M}}_{1}})^{2}\mu(\mathbf{x})d\mathbf{x}$ with any continuous distribution $\mu$.

###### Proof.

Since ${\mathcal{M}}={\mathcal{M}}_{1}\sqcup{\mathcal{M}}_{0}$ is from thickened $1$-manifold family, it has a topological representative ${\mathcal{M}}^{\prime}={\mathcal{M}}^{\prime}_{1}\sqcup{\mathcal{M}}^{\prime}_
{0}\subset\mathbb{R}^{d}$, where ${\mathcal{M}}^{\prime}_{1}$ and ${\mathcal{M}}^{\prime}_{0}$ are topological representatives of ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$, respectively.

The proof follows by first constructing simplicial approximations $|K|$ and $|L|$ of ${\mathcal{M}}$ and ${\mathcal{M}}^{\prime}$, respectively. Then we represent a simplicial homeomorphism $\phi:|K|\to|L|$ by a neural network $N_{\phi}$, where $K$ is constructed from ${\mathcal{M}}$ and $L$ from ${\mathcal{M}}^{\prime}$. Built on the top of this, a projection from ${\mathcal{M}}$ to its simiplicial approximation $|K|$ is represented by another network $N_{p}$. The overall network can be constructed by $g=h\circ N_{\phi}\circ N_{p}$. Note that $h$ is the function to approximate $I_{{\mathcal{M}}^{\prime}_{1}}$, but the data after projection and homeomorphism is from $|L_{1}|$. There should be an error in this approximation. However, we will show that by using the true risk, having $|L_{1}|\subseteq{\mathcal{M}}^{\prime}_{1}$ will make sure $||I_{|L_{1}|}-I_{{\mathcal{M}}^{\prime}_{1}}||_{L_{2}(\mu^{\prime})}=0$. We move ahead by first constructing the network $g$, and then bounding the approximation error.

Network Construction. Given ${\mathcal{M}}$ is a compact submanifold of $\mathbb{R}^{D}$ and ${\mathbf{x}}_{i}$ are sampled according to a uniform distribution, by Proposition 3, for all $0<r<\tau/2$ and $n>\lambda_{1}(log(\lambda_{2})+log(\frac{1}{\delta}))$ ($n\sim O(\tau^{-d}\log(1/\tau\delta))$), $U=\bigcup_{i}B_{r}^{D}({\mathbf{x}}_{i})$ has the same homology as ${\mathcal{M}}$ with probability higher than $1-\delta$. Note that every $B_{r}^{D}({\mathbf{x}}_{i})$ is contractible because $r\leq\tau$. Therefore by the nerve theorem (Edelsbrunner & Harer, ), the nerve of $U$ is homotopy equivalent to ${\mathcal{M}}$. Note that $U$ is a collection of $\epsilon$-balls. The nerve of $U$ is the Čech complex, which is an abstract complex constructed as $\text{\v{C}ech}(r)=\{\sigma\subseteq X|\bigcap_{{\mathbf{x}}\in\sigma}B_{r}({
\mathbf{x}})\neq 0\}$. But since the dimension of ${\mathcal{M}}$ is $d$, it suffices to only consider simplices with dimension $\leq 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, $R_{{\mathbf{x}}}(r)=B_{r}({\mathbf{x}})\cap V_{{\mathbf{x}}}$. The alpha complex is defined by

$$ $\text{Alpha}(r)=\{\sigma\subseteq X|\bigcap_{{\mathbf{x}}\in\sigma}R_{{\mathbf {x}}}(r)\neq 0\}.$ (A.27) $$

Based on the construction, $\text{Alpha}(r)$ also has the same homotopy type as $U$. Bern et al. () provided the number of simplices in a Delaunay complex of $n$ vertices is bounded by $O(n^{\lceil d/2\rceil})$. Since the Alpha complex is a sub-complex of Delaunay complex, the number of simplices in $\text{Alpha}(r)$ is also bounded by

$$ $O(n^{\lceil d/2\rceil})=O(\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau\delta})$ (A.28) $$

Denote $K=\text{Alpha}(r)$.

We claim that there exists a a vertex map $\phi:{\mathbf{x}}_{i}\to{\mathbf{x}}^{\prime}_{i}$ for $i=1,...,n$, such that with probability higher than $1-\delta$, $U^{\prime}=\bigcup_{i}B_{r^{\prime}}^{d}({\mathbf{x}}_{i}^{\prime})$ has the same homology of ${\mathcal{M}}$. We prove this claim after the proof.
We can construct an alpha complex from $\{{\mathbf{x}}^{\prime}_{i}\}_{i=1}^{n}$ in a similar way, $L=\text{Alpha}(r)$. The number of simiplices is also bounded by $O(\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau\delta})$.

$\phi$ can be extended to a simiplicial map $\phi:|K|\to|L|$ by

$$ $\phi({\mathbf{x}})=\sum_{i=1}^{n}b_{i}({\mathbf{x}})\phi({\mathbf{x}}_{i}).$ (A.29) $$

The map $b_{i}:|K|\to\mathbb{R}$ maps each point to its $i$-th barycentric coordinate. According to Proposition 6, there exists a ReLU network $N_{\phi}$ with depth $4$ and size $O(\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau\delta})$, such that $\phi({\mathbf{x}})=N_{\phi}({\mathbf{x}})$ for all ${\mathbf{x}}\in|K|$.

Next we construct a network $N_{p}$ that projects ${\mathcal{M}}$ to its simplicial approximation $|K|$. The point is projecting ${\mathbf{x}}\in{\mathcal{M}}$ to its closest simplex $\sigma_{{\mathbf{x}}}$. According to the proof of theorem 3 in Schonsheck et al. (), such projection can be represented as a neural network $N_{p}$ with depth at most $\log n+1$ and size at most $O(nD)$. Lastly, by Theorem 1, a neural network $h$ with depth at most $O(\log\beta)$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon_{1}})$ can approximate $I_{{\mathcal{M}}^{\prime}_{1}}$ with error $R(h)\leq\epsilon_{1}$. And by Lemma 3, $g=h\circ N_{\phi}\circ N_{p}$ has depth at most $O(\log(n\beta))$ and size $O(\frac{d^{2}\beta^{2}}{\epsilon_{1}}+\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau
\delta}+nD)$. Given $n\sim O(\tau^{-d}\log(1/\tau\delta))$, $g$ has depth at most $O(\log\beta+d\log\frac{1}{\tau}+\log\log\frac{1}{\tau\delta})$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon_{1}}+\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau
\delta}+D\tau^{-d}\log\frac{1}{\tau\delta})$. Note that the probability of the existence for such network is larger than $(1-\delta)^{2}=1-2\delta+\delta^{2}>1-2\delta$. We let $\delta=2\delta$, such that with probability larger than $1-\delta$, neural network $g$ exists and $g$ has depth at most $O(\log\beta+d\log\frac{1}{\tau}+\log\log\frac{1}{\tau\delta})$ and size at most $O(\frac{d^{2}\beta^{2}}{\epsilon_{1}}+\tau^{-d^{2}/2}\log^{d/2}\frac{1}{\tau
\delta}+D\tau^{-d}\log\frac{1}{\tau\delta})$.

Bounding Approximation Error. Now it is time to bound the approximation error $R(g)$. We split $R(g)$ into two parts.

$$ $\displaystyle\begin{split}R(g)&=||g-I_{{\mathcal{M}}_{1}}||_{L_{2}(\mu)}\\ &\leq||h\circ N_{\phi}\circ N_{p}-I_{{\mathcal{M}}^{\prime}_{1}}\circ\phi\circ N _{p}||_{L_{2}(\mu)}+||I_{{\mathcal{M}}^{\prime}_{1}}\circ\phi\circ N_{p}-I_{{ \mathcal{M}}_{1}}||_{L_{2}(\mu)}\\ &=I_{1}+I_{2}.\end{split}$ (A.30) $$

We first show that $I_{2}=0$. Note that $N_{p}:{\mathcal{M}}\to|K|$, and $\phi:|K|\to|L|$. We claim that for ${\mathbf{x}}\in{\mathcal{M}}_{1}$, $\phi\circ N_{p}({\mathbf{x}})\in L_{1}$ and if ${\mathbf{x}}\in{\mathcal{M}}_{0}$, $\phi\circ N_{p}({\mathbf{x}})\in L_{0}$. This is true because ${\mathcal{M}}_{1}$ and ${\mathcal{M}}_{2}$ are disjoint and $L$ is homotopy equivalent to ${\mathcal{M}}$. Consequently, $I_{L_{1}}\circ\phi\circ N_{p}=I_{{\mathcal{M}}_{1}}$. Given

$$ $\displaystyle\begin{split}||I_{{\mathcal{M}}^{\prime}_{1}}\circ\phi\circ N_{p} -I_{{\mathcal{M}}_{1}}||_{L_{2}(\mu)}&=||I_{{\mathcal{M}}^{\prime}_{1}}\circ \phi\circ N_{p}-I_{L_{1}}\circ\phi\circ N_{p}||_{L_{2}(\mu)}\\ &=||I_{L_{1}}-I_{{\mathcal{M}}^{\prime}_{1}}||_{L_{2}(\mu^{\prime})}.\end{split}$ (A.31) $$

The second equation is derived by letting $\mu^{\prime}({\mathbf{x}}^{\prime})=\mu\circ\phi\circ N_{p}({\mathbf{x}})$.
Now it suffices to show $||I_{L_{1}}-I_{{\mathcal{M}}^{\prime}_{1}}||_{L_{2}(\mu^{\prime})}=0$. Note that $\mu^{\prime}$ is a distribution supported on $|L|$, it can be naturally extended to ${\mathcal{M}}^{\prime}$ by set $\mu^{\prime}({\mathbf{x}}^{\prime})=0$ if ${\mathbf{x}}^{\prime}\in{\mathcal{M}}^{\prime}$ but ${\mathbf{x}}^{\prime}\notin|L|$. For ${\mathbf{x}}^{\prime}\in|L_{1}|$ but ${\mathbf{x}}^{\prime}\notin{\mathcal{M}}^{\prime}_{1}$, like shown in Figure A.3, we extend ${\mathcal{M}}_{1}^{\prime}$ so that ${\mathbf{x}}^{\prime}\in{\mathcal{M}}^{\prime}_{1}$. And such extension always exists due to the construction of $|L_{1}|$. Note that $|L_{1}|$ is a alpha complex constructed from a $r^{\prime}$-cover, in a way that there will be an edge if and only if two covering balls have intersection. Hence, for any edge $({\mathbf{x}}^{\prime}_{i},{\mathbf{x}}^{\prime}_{j})\in|L_{1}|$, the length $l_{ij}$ of it satisfies $l_{ij}<2r^{\prime}<\tau^{\prime}$. And notice the radius of the inner circle should be at least $\tau^{\prime}$. Otherwise, the reach will be less than $\tau^{\prime}$. Consequently, the edge of $|L_{1}|$ is always smaller than the radius of the inner circle. Therefore, one can always choose a ${\mathcal{M}}_{1}^{\prime}$, so that $\forall{\mathbf{x}}^{\prime}\in|L_{1}|$ but ${\mathbf{x}}^{\prime}\in{\mathcal{M}}^{\prime}_{1}$.

Figure: Figure A.3: For a point ${\mathbf{x}}^{\prime}\in|L_{1}|$ but ${\mathbf{x}}^{\prime}\notin{\mathcal{M}}^{\prime}_{1}$, we extend ${\mathcal{M}}^{\prime}_{1}$ to make ${\mathbf{x}}^{\prime}\in{\mathcal{M}}^{\prime}_{1}$. The extended ${\mathcal{M}}^{\prime}_{1}$ is still a topological representative.
Refer to caption: x8.png

After the expansion, $|L_{1}|\subseteq{\mathcal{M}}^{\prime}_{1}$. As a conclusion, $||I_{L_{1}}-I_{{\mathcal{M}}^{\prime}_{1}}||_{L_{2}(\mu^{\prime})}=0$. Hereby, we have proved $I_{2}=0$.

Now we settle $I_{1}$. Given $N_{\phi}$ is an exact representation of the simplicial map $\phi$,

$$ $I_{1}=||h-I_{{\mathcal{M}}^{\prime}_{1}}||_{L_{2}(\mu^{\prime})}.$ (A.32) $$

According to Theorem 1, $I_{1}\leq\epsilon_{1}$. Combined together, we have

$$ $R(g)\leq\epsilon_{1}.$ (A.33) $$

Note that this inequality holds only with probability larger than $1-\delta$ because that is the probability we successfully recover the homology of ${\mathcal{M}}$ by the training set and construct a simplicial homeomorphism.
∎

###### Claim 1 .

${\mathcal{M}}\in\mathbb{R}^{D}$ is a $d$-dimensional manifold from thickened $1$-manifold family. Suppose there exists a set $\{{\mathbf{x}}_{i}\in{\mathcal{M}}\}_{i=1}^{n}$ and radius $r$, such that $U=\bigcup_{i}B_{r}^{D}({\mathbf{x}}_{i})$ is a cover of ${\mathcal{M}}$ and has the same homology. Then there exists a ${\mathcal{M}}^{\prime}\in\mathbb{R}^{d}$ that is a topological representative of ${\mathcal{M}}$. Denote the homeomorphism between them $f$. Then with probability larger than $1-\delta$, $U^{\prime}=\bigcup_{i}B_{r^{\prime}}^{d}(f({\mathbf{x}}_{i}))$ has the same homology as ${\mathcal{M}}$.

###### Proof.

We let

$$ $c(r,\tau,{\mathcal{M}})=\frac{vol({\mathcal{M}})}{(cos^{d}\theta_{1})vol(B_{r/ 4}^{d})}\left(\log\frac{vol({\mathcal{M}})}{(cos^{d}\theta_{2})vol(B_{r/8}^{d} )}+\log\frac{1}{\delta}\right),$ (A.34) $$

where $\theta_{1}=\arcsin{\frac{r}{8\tau}}$, $\theta_{2}=\arcsin{\frac{r}{16\tau}}$ and $0<r<\tau/2$.
Given a set $\{f({\mathbf{x}}_{i})\}_{i=1}^{n}$, apply proposition 3 to ${\mathcal{M}}^{\prime}$. If

$$ $n>c(r^{\prime},\tau^{\prime},{\mathcal{M}}^{\prime}),$ (A.35) $$

then with probability $1-\delta$, $U^{\prime}=\bigcup_{i}B_{r^{\prime}}^{d}(f({\mathbf{x}}_{i}))$ has the same homology as ${\mathcal{M}}^{\prime}$, with $r^{\prime}<\tau^{\prime}/2$.

Note that $n$ already satisfy that $n>c(r,\tau,{\mathcal{M}})$, it suffices to show $c(r,\tau,{\mathcal{M}})>c(r^{\prime},\tau^{\prime},{\mathcal{M}}^{\prime})$. Since ${\mathcal{M}}^{\prime}$ is one of topological representatives of ${\mathcal{M}}$, we can always choose the radius of the fundamental members in ${\mathcal{M}}^{\prime}$ and choose the distance between ${\mathcal{M}}^{\prime}_{1}$ and ${\mathcal{M}}^{\prime}_{2}$, to make sure that $\tau^{\prime}>\tau$ and $vol({\mathcal{M}}^{\prime})<vol({\mathcal{M}})$. Hence, we can choose $r$ and $r^{\prime}$, such that $B_{r^{\prime}}^{d}>B_{r}^{d}$. With the same $\delta$, we have proved that $c(r,\tau,{\mathcal{M}})>c(r^{\prime},\tau^{\prime},{\mathcal{M}}^{\prime})$.

∎

###### Proposition 6 (Adapted from Theorem 4 in Gonzalez-Diaz et al. ( 2019 ) ) .

###### Theorem 2 (Main Theorem) .

###### Proof.

###### Claim 1 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. On the Upper Bound Dependency: Could the authors clarify whether the dependence on the manifold dimension d in the Main Theorem is a consequence of the upper bound’s conservativeness? Specifically, might the condition number be introducing an artificial inflation in the bound?
2. Empirical Justification: Are there plans to include practical or toy examples of neural network training on manifolds with varying topological complexities, beyond the “construction” cases in the paper? Such examples could help verify the utility of the theoretical bounds.
3. Potential Applications: Could the authors share any insights or speculations on how their findings might extend to practical applications? For example, how might this framework influence neural network design choices in contexts such as feature or representational learning?
soundness: 3
strengths: * The theory presented is well-structured and mathematically elegant, making effective use of both topological and geometric complexity measures, notably Betti numbers and the reach. This duality could be beneficial for refining future analyses in manifold learning and deep learning.
* The construction of a neural network classification framework that factors in manifold topology is innovative, especially in how it leverages topological representatives for improved upper bounds.
summary: This paper explores the relationship between neural network size and the topology and geometry of data manifolds, providing a theoretical framework that integrates these manifold properties into network size bounds. The authors present an upper bound on neural network size based on Betti numbers and the reach (inverse of the condition number), representing topological and geometric aspects of the data manifold, respectively. This work aims to address the gap in the literature regarding how topological complexity influences network size, which has been previously underexplored compared to geometric factors. The theoretical results, exemplified through the construction of topological representatives, offer a novel perspective on data manifolds and potential implications for future neural network architectures.
weaknesses: 1. Relevance to Neural Representations: While the theoretical results are indeed intriguing, there is limited discussion on their practical relevance for the study of neural representations. Without a thorough analysis of how these bounds translate into tighter or more representative metrics, the applicability of these results to real-world neural networks may be difficult to gauge. Further connections to neural representations in active fields like feature or metric learning would enhance this work’s value to the ICLR community.
2. Upper Bound Tightness: The paper provides an upper bound on network size influenced by manifold topology and condition number, but it does not clarify the tightness of this bound. The condition number could potentially introduce loose dependencies on manifold dimensions, especially since only an upper bound is given without a complementary lower bound or empirical justification. It would be useful if the authors could discuss the conservatism of their bound and any assumptions that might affect its applicability.
3. Lack of Empirical Examples: Although the paper includes theoretical constructs (such as Figure 3), there is a noticeable lack of concrete examples or even toy simulations that showcase the behavior of neural networks with varying topological complexities. Empirical demonstrations—even simple ones—would support the theoretical claims and help readers better understand the practical implications of the upper bound.
4. Connection to Broader Research Themes: Given the potential implications of this work for a range of ML themes (e.g., representational learning, metric learning, compositional modeling, reinforcement learning), the authors could benefit from speculating on or directly addressing possible applications of their results. It would be insightful to hear how they envision the integration of these theoretical insights with active areas like uncertainty quantification, large-scale learning, and non-convex optimization.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 4
questions: Why is TDA not used in this paper?  Is there empirical evidence that real datasets can be modelled as 1-manifolds? There are no experimental results in the paper.
soundness: 3
strengths: The paper is very well written. The introduction surveys the field and the current state of the art. The authors provide a nice overview of their problem with many references. The authors provide explicit and intuitive background on all the mathematical objects they intend to use. Their description of their family of thickened 1-manifolds is clear. They clearly state their problem and provide a reasonable answer.
summary: The paper investigates a NN's expressive power in relation to the data manifolds underlying geometry and topology. They provide theoretical bounds on the size of ReLU classifiers in terms of the manifold's Betti and condition numbers. The condition number measures how much a manifold "curves" in its ambient space.
weaknesses: The theory seems to be a bit backwards. It appears the authors found something they could prove about a small class of manifolds, and then tried to write a paper about this class. They claim that the thickened 1-manifolds are representative of data manifolds, but provide no empirical nor theoretical proof here.  
The geometric and topological characteristics they use are also somewhat random. The reach (or condition number) is a min over the entire manifold, and as such only captures geometry at a single point. The authors bemoan how difficult it is to incorporate topological information because of its discrete nature, but the data is discrete so they should be able to use TDA to assist them here.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1) Can you provide with some easy example elucidating your main results? Even proof of concept is ok.

2) In particular (refinement of question 1), can you provide a specific example or case study demonstrating how thickened 1-manifolds relate to real-world machine learning problems? Can you illustrate how the theoretical results apply to a practical ML task?
This would help elucidate the importance of this concept in machine learning.

3) Regarding weakness (2). Can you provide with a specific experiment on benchmark datasets for binary classification that can demonstrate the practical advantages of the authors' approach compared to the ICLR 2016 work? This would provide an empirical validation now missing.

4) Can you explain better how topology (Betti numbers) and differential structure (condition number) can be considered together as means of bounding the complexity of a network for a task? (here binary classification)

5) In particular (refinement of question 4), how do you reconcile the use of condition number (a geometric property) with topological invariants as the Bettin numbers? More specifically, explain how the homeomorphism affects the condition number and how this impacts their theoretical results.
soundness: 2
strengths: 1) This is a novel topological approach to the expressive power of neural networks.

2) The main result (Theorem 2) is an improvement of existing bound pushing the result in ICLR 2016.
summary: This paper discusses geometrical and topological aspects of the latent manifold in relation
with the expressibility power of neural network.

The main results state as follows. Theorem 1 gives an upper bound on the network size required
to approximate the indicator function of a certain manifold linked topologically to the data.
Theorem 2 given another bound on complexity by again the network size.

The paper is reasonably written and enough readable, examples are presented with figures to help the intuition, concepts like Betti numbers are communicated in a satisfactory way also to non specialists.

However since the authors mix differential geometry techniques as the condition number linked to the curvature of a manifold with respect to its embedding in R^D with purely topological concepts, as the Betti numbers, which are a topological invariant of a manifold, thus making the reader confused about the purpose of the paper.

Moreover results are presented without giving a clear connection with possible applications in the machine learning domain, not even
with a small practical example that could elucidate, as proof of concept, a future application of their main result.
weaknesses: 1) I have some concerns about practical relevance, since I am unable to see the importance of thickened 1-manifolds in machine learning especially in connection with the latent manifold. Perhaps (see questions below) the authors could explain a simple example, like as proof of concept, to elucidate their finding in some simple application. There is no evidence in this paper that the topological structure of thickened 1-manifolds plays a role in a better practical description of the latent manifold.

2) Though the authors generalize the work  "Depth-width tradeoffs in approximating natural functions
with neural networks" published in ICLR 2016, they are not providing any experimental evidence that what they do
go beyond the results in there from a practical point of view.

3) Technical remark: the condition number is linked with the Riemannian structure (curvature etc), while this paper is focussing mostly on
topology. Once we take homeomorphism, we are changing the condition number of a manifold, then I am not sure about the soundness of the arguments regarding condition number and topology.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1) In the paper you define the size of the network as $\sum_l w_l$ where $1\leq l < k+1$. Why do you not take into account the biases and layer $k+1$ when determining the size of the network?

2) From Proposition 3 we can approximate the simplex by only taking $n$ samples from $M$. However, the number of samples is dependent upon the volume of the $d$-dimensional $\epsilon$-balls in the covering. If $d$ is very large, then the volume of the balls is almost zero (depending on the metric used). Therefore, $n$ could also be very large and even bigger than the number of samples present. What should be done in this case? Have you tried to use this method with high-dimensional data?

3) As was mentioned, it is currently intractable to calculate high dimensional Betti numbers for even a few thousand sample points. Have you used or do you recommend using some sort of approximation or heuristic to calculate the Betti numbers?

4) Could you elaborate on any potential theoretical or analytical insight from employing this method, given that it may not be practical in all scenarios?

5) Also, is this method easily extensible to other objectives like regression?
soundness: 4
strengths: The authors offer some originality in their use of topological descriptors to give upper bounds on the size of neural networks, which is an oversight in other methods that seem to ignore the topology of data manifolds altogether.

The paper is well written in that it makes use of various results from previous authors with relevant related work. The relevant citations are present and their inclusion has a clear purpose. The authors also give ample justification for their results in the form of mathematical proofs.

Being able to determine an upper bound on the size of a neural network given a data manifold (for classification problems) is significant, given that the size of a neural network is a major factor in determining its efficacy, trainability and usability. Therefore, in that respect this paper makes a significant contribution in a narrow domain (see Weaknesses).
summary: The paper presents a novel bound on the size of ReLU neural networks which, as presented in the paper, are fully-connected feed forward neural networks (NNs) with ReLU activations. Previous work has focused on geometric descriptors in order to offer bounds on the size of NNs, but this work's novel contribution adds topological descriptors in order to calculate upper bounds on the size. In particular, the size is bounded by a function of the square of the sum of the Betti numbers of the manifold, among other variables.

The paper restricts itself to characterization of manifolds that are described as being from the family of thickened 1-manifolds, which are essentially the combinations (i.e. connected sums and disjoint unions) of spheres and tori. Defining an overall network size then is simply the aggregation of the network sizes on these individual ‘pieces’.

The main result is given as a constructive proof and offers a method for creating a ReLU neural network capable of approximating the indicator function of the class labels within a given error of $\epsilon$ with probability $1 - \delta$. It’s important to point out that the class of manifolds which this works for are assumed to be from disjoint sub-manifolds of the classes, e.g., $M = M_1 \sqcup M_0$ where it’s assumed that the objective is binary classification.
weaknesses: Weaknesses in this particular method spring from two main sources: 1) computational complexity of computing Betti numbers and 2) its applicability and usability.

Betti Numbers: a well known problem with computing Betti numbers is their computational time-complexity, which is dependent on the size of the input and the dimension to which we wish to compute. In the paper the authors define the total topological complexity of the manifold as $\beta(M) = \sum_{i=1}^{d-1}\beta_i(M)$, where $\beta_i(M)$ is the $i$-th Betti number of the manifold. Given that we must compute the Betti numbers out to dimension $(d-1)$ is a serious limitation assuming that our manifold is even a few thousand points big. Therefore, computing the proposed upper bound given that we must first compute $\beta(M)$ is already infeasible for most real world applications.


The paper describes the main process as working for classification problems only. While the number of classification problems is significant, this is a serious limitation for anyone wanting to perform regression or any other objective. Further, given that this process is already computationally infeasible, it seems that practitioners are better off by simply increasing the size of their model, training it and then iterating if results aren’t good enough, instead of taking more time to find out the worst case size that their network would need to be.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: Please see the weaknesses.
soundness: 3
strengths: I like the ideas in this paper relating data, the network and the classification task. Although preliminary, the results can be used to derive further bounds that encompass other aspects of deep learning .
summary: The paper provides results on:
- an upper bound on the network size required to approximate the indicator function of a union of balls / solids
- a lower bound for the training set size necessary to learn the homeomorphism between a complex data manifold and union of balls / solids, approximating it by a simplicial homeomorphism
- disentangling topological and geometric complexities reasoning on two properties rather than a single quantity. 

The main theorem brings these together.
weaknesses: - Since the setting is not defined until the Main Thm, the statement remains very hard to grasp. For example, which manifold is this theorem talking about? Some manifold constructed from the network weights/architecture or the data manifold? This doesn't become clear until the problem setup. Why don't we define the RELU network already?

- The following two works (uncited currently) present the connection between the intrinsic dimension and the topology of weight trajectories:
    * Andreeva et al. Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms. NeurIPS 2024
    * Birdal et al. Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks. NeurIPS 2021

  This is also why I believe that the claim in Ln. 72 should be softened, e.g. we can say 'data topology' instead of topology. 

- This paper only investigates network size in regards to data topology. However, other crucial elements such as the optimizer, task and the network architecture are disregarded. I don't see how the simplistic view of this paper can fully capture the intricate nature of expressive power.

- Betti numbers are quantities that are somehow hard to work with. Can we use for example silhouettes or other descriptors extracted from the persistent homology? This also better relates the paper to the existing literature. Note that PH is also computed through gradual thickening.

- Can we have a better name for 'topological complexity' as this notion is extremely general and does not explain the particular notion in this paper. 

- Unfortunately, we cannot see any empirical validation of the bounds presented. Could we validate at least the approximation errors, maybe on toy set-ups? Do the estimated quantities correlate well with the actual expressive power?

Meta-review: The current paper explored how the network size scales up with respect to the topological complexity and curvature of the data manifold via a constructive proof. All reviewers acknowledged that the theoretical contribution is novel and interesting, and that the authors took a promising direction on incorporating the topological complexity of data. The reviewers are still concerned on the validity of modeling real data as thickened 1-manifolds, and on the practical applicability of computing the proposed bounds. Due to these limitations, the paper needs more iterations before getting published. Moreover, the authors are encouraged to strengthen the empirical verification as the reviewers have suggested, and properly position this work in the literature in future revisions.

Decision: Reject