Data Topology-Dependent Upper Bounds of Neural Network Widths
This paper investigates the relationship between the universal approximation
property of deep neural networks and topological characteristics of datasets.
Our primary contribution is to introduce data topology-dependent upper bounds
on the network width. Specifically, we first show that a three-layer neural
network, applying a ReLU activation function and max pooling, can be designed
to approximate an indicator function over a compact set, one that is
encompassed by a tight convex polytope. This is then extended to a simplicial
complex, deriving width upper bounds based on its topological structure.
Further, we calculate upper bounds in relation to the Betti numbers of select
topological spaces. Finally, we prove the universal approximation property of
three-layer ReLU networks using our topological approach. We also verify that
gradient descent converges to the network structure proposed in our study.
Sangmin Lee, Jong Chul Ye
# Data Topology-Dependent Upper Bounds of Neural Network Widths

###### Abstract

This paper investigates the relationship between the universal approximation property of deep neural networks and topological characteristics of datasets. Our primary contribution is to introduce data topology-dependent upper bounds on the network width. Specifically, we first show that a three-layer neural network, applying a ReLU activation function and max pooling, can be designed to approximate an indicator function over a compact set, one that is encompassed by a tight convex polytope. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. Further, we calculate upper bounds in relation to the Betti numbers of select topological spaces. Finally, we prove the universal approximation property of three-layer ReLU networks using our topological approach. We also verify that gradient descent converges to the network structure proposed in our study.

## 1 Introduction

This paper addresses a fundamental question in machine learning: for any \(p\geq 1\), \(d\in\mathbb{N}\), and \(f^{*}\in L^{p}([0,1]^{d})\), what is the necessary depth and width of a neural network to approximate \(f^{*}\) within a small error? This constitutes the universal approximation property (UAP) of deep neural networks (DNNs). Since Cybenko's seminal work in 1989 [6], demonstrating the UAP of two-layer networks with non-polynomial activation functions, subsequent research has extended these results to various settings.

In the context of deep ReLU networks, recent literature establishes that the minimal depth is \(2\) (given sufficient width), and the minimal width is \(\max\{d_{x},d_{y}\}\) assuming adequate depth over a compact domain for some function classes where \(d_{x}\) and \(d_{y}\) are input and output dimensions [21; 34]. However, these UAP results on a compact domain have limitations for classifiers or discriminators. For instance, a discriminator used in generative adversarial network (GAN) training receives both training data and output from a generator, which is not confined to a specific bounded domain [15; 20; 24; 26; 35; 36].

There are recent UAP results for neural networks concerning unbounded input domains (like \(\mathbb{R}^{d}\)). Notably, a study by Wang et al. [45] demonstrates that two-layer ReLU networks fail to serve as universal approximators on \(\mathbb{R}^{2}\). As such, to approximate compactly supported functions in \(\mathbb{R}^{d}\), the required minimum depth is at least 3. While Wang et al. [45] affirmed that three-layer ReLU networks are universal approximators in \(L^{p}(\mathbb{R}^{d})\), they only establish the existence of such networks, leaving open the questions of their construction and the number of required hidden neurons. This paper addresses these questions specifically for the class of discriminator functions.

Specifically, we explore the following question: _given dataset \(\mathcal{X}\), \(\varepsilon>0\) and \(p\geq 1\), how can we construct a neural network \(\mathcal{N}\) such that \(\left\|\mathcal{N}(\mathbf{x})-\mathbb{1}_{\{\mathcal{X}\}}(\mathbf{x})\right\|_{L^{p} (\mathbb{R}^{d})}<\varepsilon\)?_ Intuitively, the answer is closely tied to the topological structure of the dataset \(\mathcal{X}\). The manifold assumption in machine
learning suggests that dataset \(\mathcal{X}\) adheres to a low-dimensional manifold, representable by simple topological features [4; 10; 28; 30; 33]. Consequently, if \(\mathcal{X}\) has a'simple' topological structure, the required depth and width to approximate \(\mathbbm{1}_{\{\mathcal{X}\}}\) would be minimal. Numerous experimental and theoretical results indeed show a strong correlation between the required width of neural networks and the topology of training dataset \(\mathcal{X}\)[8; 12; 30; 42; 43; 46]. Despite this, no research has specifically addressed how to architect neural networks based on the topological structure of the dataset. For instance, Betti numbers in Topological data analysis (TDA) represent the topological structure of dataset \(\mathcal{X}\), but no previous work has linked this quantity with network architecture.

Therefore, this paper is to bridge this gap by constructing three or four-layer neural networks with bounded widths determined by the topological features of the dataset \(\mathcal{X}\). Our contributions are summarized below.

* Motivated by the results of Wang et al. [45], we generalize their negative result for two-layer ReLU networks on \(\mathbb{R}^{d}\) with \(d\geq 2\). The proof is in Appendix B. **Proposition 1.1**.: _Let \(f^{*}:\mathbb{R}^{d}\to\mathbb{R}\) be a nonzero compactly supported function. Then for \(p\geq 1\) and \(d\geq 2\), two-layer ReLU networks cannot universally approximate \(f^{*}\) in \(L^{p}(\mathbb{R}^{d})\)._
* For a compact set \(\mathcal{X}\subset\mathbb{R}^{d}\), we develop a three-layer neural network \(\mathcal{N}\) approximating the indicator function \(\mathbbm{1}_{\{\mathcal{X}\}}\) over \(\mathbb{R}^{d}\) under a given \(\varepsilon\) error. The network's width is bound by a number related to a convex polytope cover of \(\mathcal{X}\) (as stated in Proposition 3.1). We further refine this result for a four-layer ReLU network when \(\mathcal{X}\) is represented by the difference of two unions of convex polytopes (Theorem 3.2).
* When \(\mathcal{X}\) forms an \(m\)-simplicial complex with \(k\) facets in \(\mathbb{R}^{d}\), we derive a similar result. Here, we establish upper bounds of the width in terms of \(d,k\), and \(m\), introducing novel data topology-dependent bounds (Theorem 3.3). If \(\mathcal{X}\) is a topological space represented by the difference of \(k\)-dimensional disjoint cuboids, we propose a four-layer ReLU network that can approximate \(\mathbbm{1}_{\{\mathcal{X}\}}\), where the widths are bound by terms of the Betti number of \(\mathcal{X}\) (Theorem 3.5). This underscores the significant impact of Betti numbers on the network architecture, a novel contribution in this field.
* As a practical application, we prove that the set of three-layer ReLU networks is dense in \(L^{p}(\mathbb{R}^{d_{x}},[0,1]^{d_{y}})\) for \(p\geq 1\), confirming the UAP of three-layer ReLU networks over an unbounded domain (Theorem 4.1). In conjunction with Proposition 1.1, this confirms that the minimal depth of deep ReLU networks in \(L^{p}(\mathbb{R}^{d\geq 2})\) is exactly \(3\). Furthermore, for a Lipschitz function \(f^{*}:[0,1]^{d_{x}}\to[0,1]^{d_{y}}\), we offer upper bounds of width by \(O(\varepsilon^{-d_{x}})\), where \(\varepsilon\) represents the error bound.

## 2 Related Works

In this section, we will review studies that relate to topological approaches in deep learning, compactly supported DNNs, and the universal approximation property (UAP) along with width bounds for small depth neural networks.

Topological approach in deep learning.Although few studies have explored the connection between neural network architecture and the topological features of the training data, their findings hold significant implications. [32] conducted experiments demonstrating the rapid reduction of Betti numbers of the data topology during training with deep ReLU layers. [12] attempted to correlate the architecture and data topology by increasing the complexity of the training data to guide the selection of deep neural network architecture. [46] offered upper bounds on the Betti numbers for the preimage of a layer in deep neural networks and compared them with the Betti numbers of the dataset to inform network architecture selection. Further experiments have underscored the relevance of topology-dependent neural network architecture [13; 14; 30; 42]. For an in-depth review of topological deep learning, refer to [19; 47].

Compactly supported DNNs.The construction of compactly supported subnetworks for use as building blocks in DNNs has been a focus in several studies, often with the aim of approximating a compactly supported function [1; 16; 40]. For instance, [22] proposed a 'TRLU function' for approximating constant or piecewise linear functions on a compact domain, and [23] further examined the resulting neural networks, considering open convex polytopes as the partition of input space.
This concept aligns closely with Lemma C.2 which we used to construct desired neural networks. Additionally, [26] studied the UAP for deep neural networks with ReLU and pooling layers over compactly-supported integrable functions, providing bounds of width, depth, and the number of pooling layers. Our work aligns with these studies as we explicitly construct small depth (three or four-layer) neural networks using ReLU activation and pooling layers to approximate the indicator function over a given topological space.

UAP and width bounds for small depth neural networks.The Universal Approximation Property (UAP) of shallow neural networks and the width bounds associated with them have been a subject of extensive study under various conditions [2; 18; 25; 37]. Recently, [20] utilized tropical geometry [29] and polyhedral theory to prove the UAP of two-layer neural networks, a method analogous to our approach in this paper. They also provided width and depth bounds to approximate a function that is the difference of two convex functions, a result we replicate for indicator functions over the difference of unions of convex polytopes.

Addressing unbounded domain \(\mathbb{R}^{d}\), [7] proposed a radial function that two-layer networks fail to approximate. [45] further contributed to this dialogue by presenting both negative and positive results on unbounded domains. They demonstrated that two-layer ReLU neural networks cannot universally approximate on the Euclidean plane \(\mathbb{R}^{2}\). However, they also proved that three-layer ReLU networks can serve as universal approximators in \(L^{p}(\mathbb{R}^{d})\). Drawing inspiration from these findings, we extend their initial result by illustrating that two-layer ReLU networks cannot serve as universal approximators on \(L^{p}(\mathbb{R}^{d})\) for \(p\geq 1\) and \(d\geq 2\) (Proposition 1.1).

On a different note, [5] deduced that any Lipschitz function over a compact set can be approximated by a three-layer neural network with a novel activation function. This research bears similarity to our result in Section 4, albeit with a slightly different conclusion. While they introduced a new activation function and focused on the boundedness of matrix norm, we exclusively employ the ReLU activation function and provide the upper bound of widths. Additionally, [26] explored the UAP of DNNs approximating compactly supported Lipschitz functions through ReLU and pooling layers.

In this paper, we merge these approaches to establish data-topology dependent width bounds and to validate the UAP of three-layer ReLU networks on \(\mathbb{R}^{d}\).

## 3 Data-Topology Dependent Upper Bounds of Widths

### Preliminaries

Notation.In this article, scalars are denoted by lowercase letters, vectors by boldface lowercase letters, and matrices by boldface uppercase letters. The \(L^{p}\)-norm in function spaces is represented as \(\left\|\cdot\right\|_{L^{p}}\). For a positive integer \(m\), \([m]\) is used to represent the set \(\{1,2,\cdots,m\}\). The ReLU activation function is denoted by \(\sigma(x):=\text{ReLU}(x)=\max\{0,x\}\), and it is applied to a vector coordinate-wise. The sigmoid activation function is denoted as \(\texttt{SIG}(x)=\frac{1}{1+e^{-x}}\). The max pooling operation is represented as \(\texttt{MAX}:\mathbb{R}^{d}\rightarrow\mathbb{R}\), returning the maximum value among the elements of a given vector. \(B_{\varepsilon}(\mathbf{x}_{0}):=\{\mathbf{x}:\left\|\mathbf{x}-\mathbf{x}_{0}\right\|_{2}<\varepsilon\}\) denotes the epsilon neighborhood of \(\mathbf{x}_{0}\). The \(\varepsilon\) neighborhood of a compact set \(\mathcal{X}\) is defined by \(B_{\varepsilon}(\mathcal{X}):=\{\mathbf{x}:\min_{\mathbf{y}\in\mathcal{X}}\left\|\mathbf{x }-\mathbf{y}\right\|_{2}<\varepsilon\}\). Lebesgue measure in \(\mathbb{R}^{d}\) is represented by \(\mu_{d}\), or simply \(\mu\) when \(d\) is apparent in the context. For a given set \(\mathcal{X}\subset\mathbb{R}^{d}\), the indicator function over \(\mathcal{X}\) is denoted as follows:

\[\mathbbm{1}_{\{\mathcal{X}\}}(\mathbf{x}):=\begin{cases}1,&\quad\text{if }\mathbf{x}\in\mathcal{X},\\ 0,&\quad\text{otherwise.}\end{cases}\]

Deep neural networks.We use the following notation to represent the architecture of a \(k\)-layer neural network \(\mathcal{N}:\mathbb{R}^{d}\rightarrow\mathbb{R}\) with widths \(d_{1},d_{2},\cdots,d_{k-1}\) and activation functions \(\texttt{ACT}_{1},\texttt{ACT}_{2},\cdots,\texttt{ACT}_{k}\) on each hidden layer: \(d\overset{\texttt{ACT}}{\rightarrow}d_{1}\overset{\texttt{ACT}}{\rightarrow}d _{2}\overset{\texttt{ACT}_{2}}{\rightarrow}\cdots\overset{\texttt{ACT}_{k-1}} {\rightarrow}d_{k-1}\overset{\texttt{ACT}_{k}}{\rightarrow}1\). When the activation function is identity, we denote nothing on the arrow. For example, consider a three-layer fully connected network \(\mathcal{N}\) with ReLU activation functions on hidden layers and a max pooling operation for the last layer, defined by

\[\mathcal{N}(\mathbf{x})=\texttt{MAX}\left[\sigma(\mathbf{W}_{2}\sigma(\mathbf{W}_{1}\mathbf{x} +\mathbf{b}_{1})+\mathbf{b}_{2})\right].\]

Then its architecture is denoted by \(d\overset{\sigma}{\rightarrow}d_{1}\overset{\sigma}{\rightarrow}d_{2} \overset{\texttt{MAX}}{\rightarrow}1\).
The objective of this paper is to construct a neural network \(\mathcal{N}\) such that, given \(\varepsilon>0\), \(p\geq 1\), and a compact set \(\mathcal{X}\subset\mathbb{R}^{d}\), the following inequality holds: \(\left\|\mathcal{N}(\mathbf{x})-\mathbb{1}_{\{\mathcal{X}\}}(\mathbf{x})\right\|_{L^{p} (\mathbb{R}^{d})}<\varepsilon\). By Proposition C.1, it is sufficient to construct a neural network \(\mathcal{N}\) that satisfies the following three conditions: \(\mathbf{A}\). \(\mathcal{N}(\mathbb{R}^{d})\subset[0,1]\), \(\mathbf{B}\). \(\mathcal{N}(\mathbf{x})=1\) if \(\mathbf{x}\in\mathcal{X}\), and \(\mathbf{C}\). \(\mathcal{N}(\mathbf{x})=0\) if \(\mathbf{x}\not\in B_{\varepsilon^{\prime}}(\mathcal{X})\), for a given \(\varepsilon^{\prime}>0\). In other words, the desired network should output a constant value of \(1\) over the given manifold \(\mathcal{X}\) and vanish for inputs farther than \(\varepsilon^{\prime}\) from \(\mathcal{X}\). This is a property desired for classifiers or discriminators.

### Main Theoretical Findings

#### 3.2.1 Upper bounds of the widths for compact sets

Consider \(\mathcal{X}\subset\mathbb{R}^{d}\), a compact set, and the task of approximating its indicator function \(\mathbb{1}_{\{\mathcal{X}\}}\) within \(\mathbb{R}^{d}\). As per Proposition 1.1, a minimum of three layers is required for this task. Intriguingly, if \(\mathcal{X}\) can be encapsulated within a collection of convex polytopes, a three-layer neural network employing ReLU activation and max pooling operations can be constructed. The following proposition outlines not just the feasibility of such a neural network, but also provides a method for its construction.

**Proposition 3.1**.: _Let \(\mathcal{X}\subset\mathbb{R}^{d}\) be a compact set. For a given \(\varepsilon>0\), suppose there exists a finite collection of convex polytopes \(\mathcal{C}\) such that \(\mathcal{X}\subset\bigcup_{C\in\mathcal{C}}C\subset B_{\varepsilon}(\mathcal{ X})\). Let \(k:=|\mathcal{C}|\) be the caldinality of \(\mathcal{C}\), and \(l\) be the total sum of number of faces of each polytope in \(\mathcal{C}\). Then, there exists a three-layer neural network \(\mathcal{N}\) with the architecture \(d\xrightarrow{\sigma}l\xrightarrow{\sigma}k\xrightarrow{\mathbf{x}}1\) such that \(\mathcal{N}(\mathbb{R}^{d})=[0,1]\) and_

\[\mathcal{N}(\mathbf{x}) =1 \text{if }\mathbf{x}\in\mathcal{X},\] \[\mathcal{N}(\mathbf{x}) =0 \text{if }\mathbf{x}\not\in B_{\varepsilon}(\mathcal{X}).\]

Proof.: Let \(\mathcal{C}=\{C_{1},\cdots,C_{k}\}\) and \(l_{i}\) be the number of faces of \(C_{i}\). By Lemma C.2, for each \(C_{i}\in\mathcal{C}\), there exists a two-layer ReLU network \(\mathcal{T}_{i}\) with the architecture \(d\xrightarrow{\sigma}l_{i}\to 1\) such that \(\mathcal{T}_{i}(\mathbf{x})=1\) for \(\mathbf{x}\in C_{i}\) and \(\mathcal{T}_{i}(\mathbf{x})<0\) for \(\mathbf{x}\not\in B_{\varepsilon}(C)\). Therefore, \(\sigma(\mathcal{T}_{i}(\mathbf{x}))=1\) for \(\mathbf{x}\in C_{i}\) and \(\sigma(\mathcal{T}_{i}(\mathbf{x}))=0\) for \(\mathbf{x}\not\in B_{\varepsilon}(C_{i})\). Now, we take max pooling operation to define a three-layer neural network \(\mathcal{N}\).

\[\mathcal{N}(\mathbf{x}):=\texttt{MAX}(\mathcal{T}_{1}(\mathbf{x}),\cdots,\mathcal{T}_ {k}(\mathbf{x})).\]

Then it is easy to verify that \(\mathcal{N}(\mathbf{x})\) is the desired three-layer neural network which has the architecture \(d\xrightarrow{\sigma}l\xrightarrow{\sigma}k\xrightarrow{\texttt{MAX}}1\), where \(l=l_{1}+\cdots+l_{k}\). 

Proposition 3.1 confirms the universal approximation property of three-layer neural networks for indicator functions over a compact set, granted it can be closely covered by finite convex polytopes. It is crucial to highlight that the upper bound on the neural network's widths is dictated by the covering \(\mathcal{C}\), specifically the number of constituents \(k\) and the cumulative number of all faces \(l\). Given that a single compact set \(\mathcal{X}\) may have multiple potential convex polytope coverings, deciding on the optimal covering method becomes a significant consideration. If \(\varepsilon\) is significantly large, we can opt for a loose cover of \(\mathcal{X}\) with smaller values of \(k\) and \(l\). However, a smaller \(\varepsilon\) necessitates larger values for both \(k\) and \(l\).

This brings us to an extension of the original proposition to address the issue of a high count of convex polytopes in the covering of \(\mathcal{X}\), which can occur due to the set's intricate characteristics. The subsequent theorem tackles this problem by increasing depth: if \(\mathcal{X}\) can be enveloped by the difference between two unions of convex polytopes, then a four-layer ReLU network can effectively approximate \(\mathbb{1}_{\{\mathcal{X}\}}\).

**Theorem 3.2**.: _Let \(\mathcal{X}\subset\mathbb{R}^{d}\) be a compact set. Suppose there exists a finite collection of convex polytopes \(\mathcal{C}=\{P_{1},\cdots,P_{n_{P}},Q_{1},\cdots,Q_{n_{Q}}\}\) such that the set difference \(D:=\bigcup_{i\in[n_{P}]}P_{i}-\bigcup_{j\in[n_{Q}]}Q_{j}\) satisfies \(\mathcal{X}\subset D\subset B_{\varepsilon}(\mathcal{X})\). Let \(l\) denote the total number of faces of the convex polytopes in \(\mathcal{C}\). Then, there exists a four-layer ReLU network \(\mathcal{N}\) with the architecture \(d\xrightarrow{\sigma}l\xrightarrow{\sigma}(n_{P}+n_{Q})\xrightarrow{\sigma}2 \xrightarrow{\sigma}1\) such that \(\mathcal{N}(\mathbb{R}^{d})=[0,1]\) and_

\[\mathcal{N}(\mathbf{x}) =1 \text{if }\mathbf{x}\in\mathcal{X},\] \[\mathcal{N}(\mathbf{x}) =0 \text{if }\mathbf{x}\not\in B_{\varepsilon}(\mathcal{X}).\]
Proof.: By Lemma C.2, for each \(A\in\mathcal{C}=\{P_{1},\cdots,P_{n_{P}},Q_{1},\cdots,Q_{n_{Q}}\}\), we can construct a two-layer ReLU network \(\mathcal{T}_{A}\) such that \(\mathcal{T}_{A}(\mathbf{x})=1\) for \(\mathbf{x}\in A\) and \(\mathcal{T}_{A}(\mathbf{x})=0\) for \(\mathbf{x}\not\in B_{\varepsilon}(A)\). Let \(a_{i}:=\mathcal{T}_{P_{i}}\) for \(i\in[n_{P}]\) and \(b_{j}:=\mathcal{T}_{Q_{j}}\) for \(j\in[n_{Q}]\). Define two neurons in the third layer by

\[a:=\sigma(1-a_{1}-\cdots-a_{n_{P}})\qquad\text{and}\qquad b:=\sigma(1-b_{1}- \cdots-b_{n_{Q}}).\]

Finally, defining the last layer by \(\sigma(b-a)\), we obtain the desired network \(\mathcal{N}\). The architecture of this network is \(d\xrightarrow{\sigma}\xrightarrow{\sigma}(n_{P}+n_{Q})\xrightarrow{\sigma}2 \xrightarrow{\sigma}1\). 

The primary advantage of this theorem is the reduction in the width of neural networks. While Proposition 3.1 requires the covering of \(\mathcal{X}\) solely through the union of convex polytopes, Theorem 3.2 relaxes this requirement by allowing the difference between two unions of convex polytopes. This can decrease the necessary number of neurons, given that a compact set might be covered by the difference of two unions of fewer convex polytopes, as we will illustrate in Example 3.4 (Figure 1).

However, a persisting challenge is that there is no general method known for covering a compact set using convex polytopes, or their differences. To address this, in the following section, we present general upper bounds of widths in three-layer neural networks when \(\mathcal{X}\) forms a simplicial complex.

#### 3.2.2 Upper bounds of widths for simplicial \(m\)-complexes

Before delving into the theorem, we recall some definitions. A simplicial \(m\)-complex is a type of simplicial complex where the highest dimension of any simplex equals \(m\). For a given simplicial complex \(K\), a facet of \(K\) is a maximal simplex which does not serve as a face of any larger simplex. With these definitions in mind, in the following theorem, we showcase the architecture of three-layer neural networks that can approximate \(1_{\{\mathcal{X}\}}\) for a given simplicial complex \(\mathcal{X}\).

**Theorem 3.3**.: _Let \(\mathcal{X}\subset\mathbb{R}^{d}\) be a simplicial \(m\)-complex consists of \(k\) facets, and let \(k_{j}\) be the number of \(j\)-dimensional facets of \(\mathcal{X}\). Then, for a given \(\varepsilon>0\), there exists a three-layer neural network \(\mathcal{N}\) with the architecture \(d\xrightarrow{\sigma}d_{1}\xrightarrow{\sigma}k\xrightarrow{\mathbf{ML}}1\) such that \(\mathcal{N}(\mathbb{R}^{d})=[0,1]\), \(\mathcal{N}(\mathbf{x})=1\), for \(\mathbf{x}\in\mathcal{X}\), and \(\mathcal{N}(\mathbf{x})=0\) for \(\mathbf{x}\not\in B_{\varepsilon}(\mathcal{X})\). Furthermore, \(d_{1}\) is bounded by_

\[d_{1}\leq\min\left\{k(d+1)-(d-1)\left\lfloor\sum_{j<\frac{d}{2}}\frac{k_{j}}{ 2}\right\rfloor,\;(d+1)\left[\sum_{j\leq\frac{d}{2}}\left(k_{j}\frac{j+2}{d-j} +\frac{j+2}{j+1}\right)+\sum_{j>\frac{d}{2}}k_{j}\right]\right\}. \tag{1}\]

Proof Sketch.: Let \(X_{1},X_{2},\cdots,X_{k}\) be \(k\) facets of \(\mathcal{X}\). For each facet \(X_{i}\), consider a \(d\)-simplex cover appeared in Lemma C.3. Then Proposition 3.1 provides the neural network \(\mathcal{N}\) with the architecture \(d\xrightarrow{\sigma}(d+1)k\xrightarrow{\sigma}k\xrightarrow{\mathbf{ML}}1\). Lastly, removing the neurons in the first layer that can be overlapped, we get a slightly improved bound. The full proof can be found in Appendix B. 

Theorem 3.3 reveals that the width is restricted by the dimension \(m\) and the number of facets \(k\) of a provided simplicial complex. Looking at this from a topological perspective, it is generally intuitive that a smaller number of facets signifies a simpler structure of the simplicial complex. This notion is mathematically expressed in (1), which suggests that when \(m<\frac{d}{2}\) is fixed, the first maximum value in (1) results in \(d_{1}\lesssim k(d+1)-(d-1)\frac{k}{2}=\frac{k}{2}(d+3)\), which magnifies as \(k\) increases. Similarly, if \(k\) is fixed and \(\mathcal{X}\) consists of \(m\)-simplices with \(m<\frac{d}{2}\), the summation in the second maximum value in (1) reduces to \(d_{1}\lesssim(d+1)\left(k\frac{m+2}{d-m}+2\right)\), which rapidly diminishes as \(m\) decreases. This suggests that a smaller dimension \(m\) demands smaller widths, which aligns with the intuition that a low-dimensional manifold could be approximated with fewer neurons. To our knowledge, this is the first upper bound of the width of neural networks that depends on the topological data structure.

Theorem 3.3 is a 'universal' approximation result since the width bounds presented in (1) apply to any simplicial complex. However, being a general upper bound, there might be a smaller network architecture that can approximate a given simplicial complex. Proposition 3.1 and Theorem 3.2 show that the width upper bounds are determined by a convex polytope covering, which is heavily dependent on the topological features of \(\mathcal{X}\). In the upcoming toy example, we clarify how the upper bounds of width can vary based on the choice of covering, for the same topological space \(\mathcal{X}\).
**Example 3.4** (Comparison of Proposition 3.1, Theorem 3.2, and Theorem 3.3).: Let \(\mathcal{X}\) be the boundary of a regular \(k\)-gon in \(\mathbb{R}^{2}\). (b) A triangle covering of \(\mathcal{X}\) is given. Proposition 3.1 provides the network architecture \(2\overset{\sigma}{\to}3k\overset{\sigma}{\to}k\overset{\text{\tiny{MA}}}{ \to}1\). (c) \(B_{\varepsilon}(\mathcal{X})\) can be covered by the difference of two \(k\)-gon \(P\) and \(Q\). Then, Theorem 3.2 guarantees that a network with the architecture \(2\overset{\sigma}{\to}2k\overset{\sigma}{\to}2\overset{\sigma}{\to}2\overset{ \sigma}{\to}1\) can approximate \(\mathbbm{1}_{\{\mathcal{X}\}}\).

**Example 3.4** (Comparison of Proposition 3.1, Theorem 3.2, and Theorem 3.3).: Let \(\mathcal{X}\) be the boundary of a regular \(k\)-gon in \(\mathbb{R}^{2}\) as shown in Figure 1(a). First, consider a convex polytope covering \(\mathcal{C}\) that consists of \(k\) green triangles in Figure 1(b). Proposition 3.1 shows that a three layer network with the architecture \(2\overset{\sigma}{\to}3k\overset{\sigma}{\to}k\overset{\text{\tiny{MA}}}{ \to}1\) can approximate \(\mathbbm{1}_{\{\mathcal{X}\}}\). Since \(\mathcal{X}\) can be regarded as a simplicial \(2\)-complex with \(k\) facets, Theorem 3.3 provides a slightly better bound \(2\overset{\sigma}{\to}\left(3k-\left\lfloor\frac{1}{2}k\right\rfloor\right) \overset{\sigma}{\to}k\overset{\text{\tiny{MA}}}{\to}1\), but both networks still have \(O(k)\) widths for two hidden layers. However, from its special structure of \(\mathcal{X}\), it can be covered by difference of two solid \(k\)-gons \(P\) and \(Q\) (Figure 1(c)). Then, Theorem 3.2 provides a four-layer ReLU network with the architecture \(2\overset{\sigma}{\to}2k\overset{\sigma}{\to}2\overset{\sigma}{\to}2\overset{ \sigma}{\to}1\), which has only one \(O(k)\) width. This example helps understand the benefits of depth from a topological perspective, akin to the advantages of depth studied in previous works [3, 39, 41, 44, 45]. It is also important to note that the high number of neurons in the first layer is inevitable, as described in [12] and [46].

It is remarkable that our findings can be extended to various other neural network architectures. In Appendix A, we broaden our results to encompass deep ReLU networks (as seen in Corollary A.1) and networks using sigmoid activation function at last (as presented in Corollary A.2).

#### 3.2.3 Upper bounds of widths in terms of Betti numbers

The Betti number is a key metric used in TDA to denote the number of \(k\)-dimensional 'holes' in a data distribution. Owing to its homotopy invariance, Betti numbers are frequently employed to study the topological features of a given topological space. Interestingly, our prior results can be leveraged to ascertain a neural network architecture with width bounds defined in terms of the Betti numbers, given that the dataset \(\mathcal{X}\) exhibits certain structural characteristics.

Specifically, Theorem 3.2 offers upper width bounds when \(\mathcal{X}\) can be depicted as a difference between unions of convex sets. Consequently, if \(\mathcal{X}\) is convex and only contains 'convex-shaped holes', we can derive a network width bound in relation to its Betti numbers. This concept is further explicated in the following theorem and example.

**Theorem 3.5**.: _Suppose \(\mathcal{X}\subset\mathbb{R}^{d}\) is a topological space obtained by removing some disjoint rectangular prisms from a \(d\)-dimensional cuboid. Let \(\beta_{0},\beta_{1},\cdots,\beta_{d}\) be the Betti numbers of \(\mathcal{X}\). Then for any \(\varepsilon>0\), there exists a four-layer ReLU network \(\mathcal{N}\) with the architecture_

\[d\ \overset{\sigma}{\to}\ 2\left(d-1+\sum_{k=0}^{d}(k+1)\beta_{k}\right) \ \overset{\sigma}{\to}\ \left(\sum_{k=0}^{d}\beta_{k}\right)\ \overset{\sigma}{\to}2\ \overset{\sigma}{\to}1 \tag{2}\]

_such that \(\mathcal{N}(\mathbb{R}^{d})=[0,1]\), \(\mathcal{N}(\mathbf{x})=1\) for \(\mathbf{x}\in\mathcal{X}\), and \(\mathcal{N}(\mathbf{x})=0\) for \(\mathbf{x}\not\in B_{\varepsilon}(\mathcal{X})\)._

Proof Sketch.: Since each \(k\)-dimensional hole is a rectangular prism, we can consider it as convex polytopes. The result is deduced from Theorem 3.2 by computing the required number of faces of polytopes. The full proof can be found in Appendix B.
**Example 3.6**.: Let \(\mathcal{X}\) be a topological space in \(\mathbb{R}^{3}\) shown in Figure 2(a), which has three nonzero Betti numbers \(\beta_{0}=\beta_{1}=2\) and \(\beta_{2}=3\). Then we can consider the homotopy equivalent topological space \(\mathcal{X}^{\prime}\subset\mathbb{R}^{3}\) that satisfies the assumptions in Theorem 3.5: \(\mathcal{X}^{\prime}\) is obtained by 'cutting out' a plate (orange), 'punching' two rectangular prisms (green), and 'hollowing out' three small cubes (red) from a large cuboid (blue) as described in Figure 2(c). Then, Theorem 3.5 shows that a four-layer ReLU network with the architecture \(3\overset{\sigma}{\to}34\overset{\sigma}{\to}7\overset{\sigma}{\to}2\overset{ \sigma}{\to}1\) can approximate \(\mathbbm{1}_{\{\mathcal{X}^{\prime}\}}\) arbitrarily closely.

Theorem 3.5 and Example 3.6 illustrate how the Betti numbers of a topological space \(\mathcal{X}\) can contribute to defining upper bounds for the widths of neural networks. However, it's important to note that two homotopy equivalent spaces may require differing network architectures. In Proposition C.4, we prove that the indicator function over a crown-shaped topological space (Figure 5(a)) in \(\mathbb{R}^{2}\) cannot be approximated by a two-layer ReLU network with the architecture \(2\overset{\sigma}{\to}3\to 1\), while a triangle can be approximated by Proposition 3.1. Since these two spaces have the same Betti numbers \(\beta_{0}=1\), this example suggests that a neural network architecture cannot be solely determined by Betti numbers.

Nevertheless, Theorem 3.5 provides an upper bound on the widths of four-layer ReLU networks in terms of Betti numbers of \(\mathcal{X}\), under the conditions stipulated. This is another novel result linking the topological characteristics of a dataset with upper bounds on widths. It is worth noting that similar results can be achieved when the cuboid assumptions in Theorem 3.5 are modified to other convex polytopes, using the same proof strategy.

We further elaborate on the topic of network architecture. Intriguingly, the sum of Betti numbers \(\sum_{k=0}^{d}\beta_{k}\) that appears in the third layer in (2) is termed the _topological complexity_ of \(\mathcal{X}\). This quantity is recognized as a measure of the complexity of a given topological space [32]. This value has connections with other fields, for example, it has some lower and upper bounds from Morse theory [31] and Gromov's Betti number Theorem [11]. In the context of topological data analysis, consider a Cech complex constructed on a dataset \(\mathcal{X}\) consisting of \(n\) points, using a filtration parameter \(\varepsilon\). Its topological complexity fluctuates from \(n\) (when \(\varepsilon=0\)) to \(1\) (when \(\varepsilon>\text{diam}(\mathcal{X})\)) as \(\varepsilon\) increases. This implies that the architecture in Theorem 3.5 is dictated by the filtration number \(\varepsilon\), which controls the topological structure of the given dataset. We believe this approach could inspire novel investigative methods in TDA, which we propose as an avenue for future research.

## 4 Universal Approximation Property of Three-Layer ReLU Networks

In the preceding section, we demonstrated how indicator functions over certain topological spaces can be approximated by three-layer neural networks. Interestingly, this topological result has an application in proving the Universal Approximation Property (UAP) of three-layer ReLU networks. Moreover, we can derive upper bounds on the widths in three-layer ReLU networks for approximating Lipschitz functions. We present this result in the upcoming theorem.

**Theorem 4.1**.: _Let \(d_{x},d_{y}\in\mathbb{N}\) and \(p\geq 1\). Then, the set of three-layer ReLU networks is dense in \(L^{p}(\mathbb{R}^{d_{x}},[0,1]^{d_{y}})\). Furthermore, let \(f:\mathbb{R}^{d_{x}}\to[0,1]^{d_{y}}\) be a compactly supported Lipschitz function. Then for any \(\varepsilon>0\), there exists a three-layer ReLU network \(\mathcal{N}\) with the architecture_

\[d_{x}\overset{\sigma}{\to}(2nd_{x}d_{y})\overset{\sigma}{\to}(nd_{y})\ \to d_{y}\]

_such that \(\left\|\mathcal{N}-f\right\|_{L^{p}(\mathbb{R}^{d_{x}})}<\varepsilon\). Here, \(n=O(\varepsilon^{-d_{x}})\)._

Figure 2: An illustration of the correlation between Betti numbers and the network architecture (Example 3.6). (a) A topological space \(\mathcal{X}\subset\mathbb{R}^{3}\) is given, whose Betti numbers are \(\beta_{0}=\beta_{1}=2\) and \(\beta_{2}=3\). (b) A homotopy equivalent space \(\mathcal{X}^{\prime}\) is presented, obtained by removing several small cuboids from a larger one. (c) The removed cuboids from \(\mathcal{X}^{\prime}\) are shown. Theorem 3.5 demonstrates that a four-layer ReLU network with the architecture \(3\overset{\sigma}{\to}34\overset{\sigma}{\to}7\overset{\sigma}{\to}2 \overset{\sigma}{\to}1\) can approximate \(\mathbbm{1}_{\{\mathcal{X}^{\prime}\}}\).
Proof Sketch.: The first assertion is a consequence of the second one. Regarding the second assertion, note that \(f^{*}\), being Lipschitz, is continuous and Riemann integrable. Consequently, we can construct a linear combination of indicator functions that approximates \(f^{*}\), which are known as simple functions in Lebesgue theory [38]. Each of these indicator functions can be implemented by a three-layer ReLU network using Proposition 3.1. The complete proof can be found in Appendix B. 

Theorem 4.1 makes two assertions. The first one affirms that the set of three-layer ReLU networks is dense in \(L^{p}(\mathbb{R}^{d_{x}},[0,1]^{d_{y}})\), aligning with the findings presented in [45]. Considering that we have also demonstrated that the set of two-layer ReLU networks cannot universally approximate a compactly supported function (as per Proposition 1.1), we can conclude that the minimum depth of DNNs to achieve universal approximation in \(L^{p}(\mathbb{R}^{d_{x}})\) is precisely 3. This conclusion refines the results shown in [45]. Moreover, while [45] merely demonstrates the possibility of approximating functions using three-layer ReLU networks, the second assertion of Theorem 4.1 provides upper bounds on the widths, which are \(O(\varepsilon^{-d_{x}})\), when the function to be approximated, \(f^{*}\), is Lipschitz and compactly supported. As far as we are aware, this is the first work to present an upper bound on the width of three-layer ReLU networks for UAP.

These findings open a potential path to extend our topological results. We expect that for certain classes of functions, the width bounds could be reduced by adding more layers to the network, as demonstrated in Theorem 3.2 and Example 3.4. However, we leave this as an area for future research.

## 5 Experimental Results

In Section 3, we introduced a construction for three or four-layer neural networks that can approximate \(\mathbb{I}_{\{\mathcal{X}\}}\) for any given topological space \(\mathcal{X}\) with a sufficient degree of accuracy. Naturally, this leads us to the question of whether these networks can be produced using a gradient method. While most prior theoretical studies concerning the existence of neural networks have not included experimental verification [22; 23; 25; 34], the issue of experimental verification remains an important one, as noted in [44]. In this section, we will provide experimental evidence that gradient descent can indeed converge to the neural networks that we constructed in Section 3.

We consider two illustrative manifolds, \(\mathcal{X}_{1}\) and \(\mathcal{X}_{2}\), depicted in Figure 3(a) and (d) respectively. The first compact set \(\mathcal{X}_{1}\) is a simplicial \(2\)-complex in \(\mathbb{R}^{2}\) comprised of two triangles. The second compact set \(\mathcal{X}_{2}\) is a hexagon with a pentagonal hole, which is not a simplicial complex but a compact manifold. The datasets are constructed by selecting 1600 equidistant lattice points in the domain \([-20,20]\times[-20,20]\subset\mathbb{R}^{2}\), where each point has label '\(1\)' if it lies on the manifold \(\mathcal{X}_{i}\), and '\(0\)' otherwise. We undertake both regression and classification tasks, using mean square error (MSE) loss and binary cross entropy (BCE) loss respectively. For the BCE loss task, we adhere to the architecture proposed in Corollary A.2 to ensure trainability. We employ the gradient descent algorithm for training our networks. For a clearer visualization of weight vectors in each layer, we plot the lines of vanishing points for each layer in blue (1st layer), red (2nd layer), etc. The grayscale color denotes the output range of the trained network.

For the first data manifold \(\mathcal{X}_{1}\), Theorem 3.3 suggests that a network with the architecture \(2\overset{\sigma}{\rightarrow}6\overset{\sigma}{\rightarrow}2\overset{ \text{MAX}}{\rightarrow}1\) can precisely represent \(\mathbb{I}_{\{\mathcal{X}_{1}\}}\). As depicted in Figure 3(b), the trained network indeed converges exactly to the network proposed in the theorem under MSE loss. The weight vectors in the first layer encapsulate the two triangles, reflecting the topology of \(\mathcal{X}_{1}\). A similar result can be observed for a network with the architecture \(2\overset{\sigma}{\rightarrow}6\overset{\sigma}{\rightarrow}2\overset{ \text{STG}}{\rightarrow}1\), as suggested by Corollary A.2. For the second data manifold \(\mathcal{X}_{2}\), Theorem 3.2 suggests that a network with the architecture \(2\overset{\sigma}{\rightarrow}11\overset{\sigma}{\rightarrow}2\overset{ \sigma}{\rightarrow}2\overset{\sigma}{\rightarrow}1\) can fit this manifold, and Figure 3(e) verifies this under MSE loss. The architecture \(2\overset{\sigma}{\rightarrow}11\overset{\sigma}{\rightarrow}2\overset{ \text{STG}}{\rightarrow}1\) also converges to the network proposed in Corollary A.2, as shown in Figure 3(f). More specifically, the eleven weight vectors in the first layer align with the eleven boundaries of the outer hexagon and the inner pentagon, with two neurons in the second layer encapsulating each polygon.

These experimental results provide evidence that the networks proposed in Section 3 can indeed be reached as the global minima by gradient descent, under both MSE loss and BCE loss. However, we must stress the importance of initialization. Although we observe successful convergence to the expected networks, the results are heavily dependent on the initialization. For instance, under random initialization, it is known that all neurons in a layer may 'die' at initialization with a nonzero
probability [27], leading to a poor network performance. We provide further experimental results concerning different initializations in Appendix D. The key takeaway from this section is that _the networks proposed in Section 3 can indeed be reached by gradient descent_, a fact not demonstrated by prior studies on UAP, even in the context of toy examples.

## 6 Conclusions

While many previous studies have explored the universal approximation property of DNNs, they have largely overlooked the connection with the topological features of datasets. In this paper, we have addressed this gap by providing data topology-dependent upper bounds on the width of DNNs. We have shown that for a dataset \(\mathcal{X}\) that can be tightly covered by convex polytopes, a three-layer network architecture can be derived to approximate the indicator function \(\mathbbm{1}_{\{\mathcal{X}\}}\). We also extended this to four-layer ReLU networks for \(\mathcal{X}\) that can be covered by the difference of two unions of convex polytopes. We further generalized this to simplicial \(m\)-complexes and demonstrated the construction of a three-layer neural network with ReLU activation and max pooling operation. Imposing further assumptions on \(\mathcal{X}\), we proposed the architecture of four-layer ReLU networks whose widths are bounded in terms of Betti numbers, a novel result in this field. Finally, we demonstrated that to approximate a compactly supported Lipschitz function in \(\mathbb{R}^{d_{x}}\) by a three-layer ReLU network under an \(\varepsilon\) error, a width of \(O(\varepsilon^{-d_{x}})\) is sufficient. Through our experiments, we showed that gradient descent indeed converges to the networks we proposed.

Limitations and Future WorksThere are several limitations. Firstly, although we experimentally showed convergence to the constructed network, we did not provide a rigorous guarantee for this convergence here. To overcome this and to ensure both existence and convergence, it would be valuable to prove a convergence result under specific conditions. Secondly, further research is needed to investigate the relationship between the network architecture and Betti numbers of the given topological spaces. The results in Theorem 3.5 suggest that it may be possible to expand our findings or reduce some assumptions on the given topological space. Since Betti numbers are commonly used features to characterize topological features of data manifolds in Topological Data Analysis (TDA), we believe that this line of research could yield significant insights.

Figure 3: Experimental verification of convergence of gradient descent. (a) and (d) exhibit the shape of two data manifolds, which are ‘two triangles’ and ‘a hexagon with a pentagon hole’. (b) and (e) show the converged networks by gradient descent, when the loss function is given by the mean square error (MSE) loss. Similarly, (e) and (f) show the results for the binary cross entropy (BCE) loss. These results verify that gradient descent indeed converges to the networks we proposed in Section 3.