# Data Topology-Dependent Upper Bounds of
Neural Network Widths

Sangmin Lee1 Jong Chul Ye2
1 Department of Mathematical Science, KAIST
2 Kim Jaechul Graduate School of AI, KAIST
{leeleesang<EMAIL_ADDRESS>
###### 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}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{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}\rightarrow{\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}}\rightarrow[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

###  3.1 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):=\textup{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}({\bm{x}}_{0}):=\\{{\bm{x}}:\left\|{\bm{x}}-{\bm{x}}_{0}\right\|_{2}<\varepsilon\\}$
denotes the epsilon neighborhood of ${\bm{x}}_{0}$. The $\varepsilon$
neighborhood of a compact set $\mathcal{X}$ is defined by
$B_{\varepsilon}(\mathcal{X}):=\\{{\bm{x}}:\min_{{\bm{y}}\in\mathcal{X}}\left\|{\bm{x}}-{\bm{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:

$\displaystyle\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{x}}):=\begin{cases}1,\qquad\text{if
}{\bm{x}}\in\mathcal{X},\\\ 0,\qquad\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\stackrel{{\scriptstyle\texttt{ACT}_{1}}}{{\rightarrow}}d_{1}\stackrel{{\scriptstyle\texttt{ACT}_{2}}}{{\rightarrow}}d_{2}\stackrel{{\scriptstyle\texttt{ACT}_{3}}}{{\rightarrow}}\cdots\stackrel{{\scriptstyle\texttt{ACT}_{k-1}}}{{\rightarrow}}d_{k-1}\stackrel{{\scriptstyle\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

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

Then its architecture is denoted by
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{1}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{2}\stackrel{{\scriptstyle\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}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{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: A.
$\mathcal{N}({\mathbb{R}}^{d})\subset[0,1]$, B. $\mathcal{N}({\bm{x}})=1$ if
${\bm{x}}\in\mathcal{X}$, and C. $\mathcal{N}({\bm{x}})=0$ if ${\bm{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.

###  3.2 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 $\mathbbm{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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}l\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}1$
such that $\mathcal{N}({\mathbb{R}}^{d})=[0,1]$ and

$\displaystyle\mathcal{N}({\bm{x}})$ $\displaystyle=1\qquad\text{if
}{\bm{x}}\in\mathcal{X},$ $\displaystyle\mathcal{N}({\bm{x}})$
$\displaystyle=0\qquad\text{if }{\bm{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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}l_{i}\rightarrow 1$ such that
$\mathcal{T}_{i}({\bm{x}})=1$ for ${\bm{x}}\in C_{i}$ and
$\mathcal{T}_{i}({\bm{x}})<0$ for ${\bm{x}}\not\in B_{\varepsilon}(C)$.
Therefore, $\sigma(\mathcal{T}_{i}({\bm{x}}))=1$ for ${\bm{x}}\in C_{i}$ and
$\sigma(\mathcal{T}_{i}({\bm{x}}))=0$ for ${\bm{x}}\not\in
B_{\varepsilon}(C_{i})$. Now, we take max pooling operation to define a three-
layer neural network $\mathcal{N}$.

$\displaystyle\mathcal{N}({\bm{x}}):=\texttt{MAX}(\mathcal{T}_{1}({\bm{x}}),\cdots,\mathcal{T}_{k}({\bm{x}})).$

Then it is easy to verify that $\mathcal{N}({\bm{x}})$ is the desired three-
layer neural network which has the architecture
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}l\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}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
$\mathbbm{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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}l\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(n_{P}+n_{Q})\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$
such that $\mathcal{N}({\mathbb{R}}^{d})=[0,1]$ and

$\displaystyle\mathcal{N}({\bm{x}})$ $\displaystyle=1\qquad\text{if
}{\bm{x}}\in\mathcal{X},$ $\displaystyle\mathcal{N}({\bm{x}})$
$\displaystyle=0\qquad\text{if }{\bm{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}({\bm{x}})=1$ for ${\bm{x}}\in A$ and
$\mathcal{T}_{A}({\bm{x}})=0$ for ${\bm{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

$\displaystyle 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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}l\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(n_{P}+n_{Q})\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}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
$\mathbbm{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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{1}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}1$
such that $\mathcal{N}({\mathbb{R}}^{d})=[0,1]$, $\mathcal{N}({\bm{x}})=1$,
for ${\bm{x}}\in\mathcal{X}$, and $\mathcal{N}({\bm{x}})=0$ for
${\bm{x}}\not\in B_{\varepsilon}(\mathcal{X})$. Furthermore, $d_{1}$ is
bounded by

$\displaystyle
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\\}.$
(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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(d+1)k\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}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$-simplicies 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}$.

(a)

(b)

(c)

Figure 1: A comparison of Proposition 3.1, Theorem 3.2, and Theorem 3.3 in
Example 3.4. (a) 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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}3k\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2k\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}3k\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}\left(3k-\left\lfloor\frac{1}{2}k\right\rfloor\right)\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2k\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}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

$\displaystyle
d\;\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}\;2\left(d-1+\sum_{k=0}^{d}(k+1)\beta_{k}\right)\;\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}\;\left(\sum_{k=0}^{d}\beta_{k}\right)\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$
(2)

such that $\mathcal{N}({\mathbb{R}}^{d})=[0,1]$, $\mathcal{N}({\bm{x}})=1\;$
for ${\bm{x}}\in\mathcal{X}$, and $\mathcal{N}({\bm{x}})=0\;$ for
${\bm{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. ∎

(a)

(b)

(c)

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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}34\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}7\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$
can approximate $\mathbbm{1}_{\\{\mathcal{X}^{\prime}\\}}$.

######  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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}34\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}7\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}3\rightarrow 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 C̆ech
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}}\rightarrow[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

$\displaystyle
d_{x}\;\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}\;(2nd_{x}d_{y})\;\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}\;(nd_{y})\;\rightarrow
d_{y}$

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

###### 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 $\mathbbm{1}_{\\{\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.

(a)

(b)

(c)

(d)

(e)

(f)

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.

For the first data manifold $\mathcal{X}_{1}$, Theorem 3.3 suggests that a
network with the architecture
$2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}6\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}1$
can precisely represent $\mathbbm{1}_{\\{\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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}6\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\texttt{SIG}}}{{\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\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}11\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$
can fit this manifold, and Figure 3(e) verifies this under MSE loss. The
architecture
$2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}11\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\texttt{SIG}}}{{\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 Works

There 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.

## References

  * [1] Adrian Barbu and Hongyu Mou.  The compact support neural network.  Sensors, 21(24):8494, 2021.
  * [2] Andrew R Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  IEEE Transactions on Information theory, 39(3):930–945, 1993.
  * [3] Kaifeng Bu, Yaobo Zhang, and Qingxian Luo.  Depth-width trade-offs for neural networks via topological entropy.  arXiv preprint arXiv:2010.07587, 2020.
  * [4] Gunnar Carlsson.  Topological pattern recognition for point cloud data.  Acta Numerica, 23:289–368, 2014.
  * [5] Jeremy EJ Cohen, Todd Huster, and Ra Cohen.  Universal lipschitz approximation in bounded depth neural networks.  arXiv preprint arXiv:1904.04861, 2019.
  * [6] George Cybenko.  Approximation by superpositions of a sigmoidal function.  Mathematics of control, signals and systems, 2(4):303–314, 1989\.
  * [7] Ronen Eldan and Ohad Shamir.  The power of depth for feedforward neural networks.  In Conference on learning theory, pages 907–940. PMLR, 2016.
  * [8] Stanislav Fort, Ekin Dogus Cubuk, Surya Ganguli, and Samuel S Schoenholz.  What does a deep neural network confidently perceive? the effective dimension of high certainty class manifolds and their low confidence boundaries.  arXiv preprint arXiv:2210.05546, 2022.
  * [9] Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249–256. JMLR Workshop and Conference Proceedings, 2010.
  * [10] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.
  * [11] Michael Gromov.  Curvature, diameter and betti numbers.  Commentarii Mathematici Helvetici, 56:179–195, 1981.
  * [12] William H Guss and Ruslan Salakhutdinov.  On characterizing the capacity of neural networks using algebraic topology.  arXiv preprint arXiv:1802.04443, 2018.
  * [13] Mustafa Hajij and Kyle Istvan.  A topological framework for deep learning.  arXiv preprint arXiv:2008.13697, 2020.
  * [14] Mustafa Hajij and Kyle Istvan.  Topological deep learning: Classification neural networks.  arXiv preprint arXiv:2102.08354, 2021.
  * [15] Boris Hanin.  Universal function approximation by deep neural nets with bounded width and relu activations.  Mathematics, 7(10):992, 2019.
  * [16] Juncai He, Lin Li, Jinchao Xu, and Chunyue Zheng.  Relu deep neural networks and linear finite elements.  arXiv preprint arXiv:1807.03973, 2018.
  * [17] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE international conference on computer vision, pages 1026–1034, 2015.
  * [18] Robert Hecht-Nielsen.  Kolmogorov’s mapping neural network existence theorem.  In Proceedings of the international conference on Neural Networks, volume 3, pages 11–14. IEEE Press New York, NY, USA, 1987.
  * [19] Felix Hensel, Michael Moor, and Bastian Rieck.  A survey of topological machine learning methods.  Frontiers in Artificial Intelligence, 4:681108, 2021.
  * [20] Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella.  Towards lower bounds on the depth of relu neural networks.  Advances in Neural Information Processing Systems, 34:3336–3348, 2021.
  * [21] Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  Neural networks, 4(2):251–257, 1991.
  * [22] Changcun Huang.  Relu networks are universal approximators via piecewise linear or constant functions.  Neural Computation, 32(11):2249–2278, 2020.
  * [23] Changcun Huang.  Theoretical exploration of solutions of feedforward relu networks.  arXiv preprint arXiv:2202.01919, 2022.
  * [24] Geonho Hwang, Myungjoo Kang, et al.  Minimal width for universal property of deep rnn.  arXiv preprint arXiv:2211.13866, 2022.
  * [25] Vugar Ismailov.  A three layer neural network can represent any multivariate function.  arXiv preprint arXiv:2012.03016, 2020.
  * [26] Anastasis Kratsios and Behnoosh Zamanlooy.  Do relu networks have an edge when approximating compactly-supported functions?  Transactions on Machine Learning Research, 2022.
  * [27] Lu Lu, Yeonjong Shin, Yanhui Su, and George Em Karniadakis.  Dying relu and initialization: Theory and numerical examples.  arXiv preprint arXiv:1903.06733, 2019.
  * [28] Pek Y Lum, Gurjeet Singh, Alan Lehman, Tigran Ishkanov, Mikael Vejdemo-Johansson, Muthu Alagappan, John Carlsson, and Gunnar Carlsson.  Extracting insights from the shape of complex data using topology.  Scientific reports, 3(1):1–8, 2013.
  * [29] Diane Maclagan and Bernd Sturmfels.  Introduction to tropical geometry, volume 161.  American Mathematical Society, 2021.
  * [30] German Magai and Anton Ayzenberg.  Topology and geometry of data manifold in deep learning.  arXiv preprint arXiv:2204.08624, 2022.
  * [31] John Willard Milnor, Michael Spivak, Robert Wells, and Robert Wells.  Morse theory.  Princeton university press, 1963.
  * [32] Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim.  Topology of deep neural networks.  The Journal of Machine Learning Research, 21(1):7503–7542, 2020\.
  * [33] Monica Nicolau, Arnold J Levine, and Gunnar Carlsson.  Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival.  Proceedings of the National Academy of Sciences, 108(17):7265–7270, 2011.
  * [34] Sejun Park, Chulhee Yun, Jaeho Lee, and Jinwoo Shin.  Minimum width for universal approximation.  arXiv preprint arXiv:2006.08859, 2020.
  * [35] Dmytro Perekrestenko, Philipp Grohs, Dennis Elbrächter, and Helmut Bölcskei.  The universal approximation power of finite-width deep relu networks.  arXiv preprint arXiv:1806.01528, 2018.
  * [36] Dmytro Perekrestenko, Stephan Müller, and Helmut Bölcskei.  Constructive universal high-dimensional distribution generation through deep relu networks.  In International Conference on Machine Learning, pages 7610–7619. PMLR, 2020.
  * [37] Allan Pinkus.  Approximation theory of the mlp model in neural networks.  Acta numerica, 8:143–195, 1999.
  * [38] Walter Rudin et al.  Principles of mathematical analysis, volume 3.  McGraw-hill New York, 1976.
  * [39] Itay Safran and Ohad Shamir.  Depth-width tradeoffs in approximating natural functions with neural networks.  In International conference on machine learning, pages 2979–2987. PMLR, 2017.
  * [40] Linhao Song, Jun Fan, Di-Rong Chen, and Ding-Xuan Zhou.  Approximation of nonlinear functionals using deep relu networks.  arXiv preprint arXiv:2304.04443, 2023.
  * [41] Matus Telgarsky.  Benefits of depth in neural networks.  In Conference on learning theory, pages 1517–1539. PMLR, 2016.
  * [42] Saket Tiwari and George Konidaris.  Effects of data geometry in early deep learning.  arXiv preprint arXiv:2301.00008, 2022.
  * [43] Ilya Trofimov, Daniil Cherniavskii, Eduard Tulchinskii, Nikita Balabin, Evgeny Burnaev, and Serguei Barannikov.  Learning topology-preserving data representations.  arXiv preprint arXiv:2302.00136, 2023.
  * [44] Gal Vardi, Gilad Yehudai, and Ohad Shamir.  Width is less important than depth in relu neural networks.  In Conference on Learning Theory, pages 1249–1281. PMLR, 2022.
  * [45] Ming-Xi Wang and Yang Qu.  Approximation capabilities of neural networks on unbounded domains.  Neural Networks, 145:56–67, 2022.
  * [46] Ji Yang, Lu Sang, and Daniel Cremers.  Dive into layers: Neural network capacity bounding using algebraic geometry.  arXiv preprint arXiv:2109.01461, 2021.
  * [47] Ali Zia, Abdelwahed Khamis, James Nichols, Zeeshan Hayder, Vivien Rolland, and Lars Petersson.  Topological deep learning: A review of an emerging paradigm.  arXiv preprint arXiv:2302.03836, 2023.

Appendix

##  Appendix A Extension to Deep ReLU Networks and Cross Entropy Loss

In Section 3, we presented a variety of three and four-layer neural networks
utilizing ReLU activation and max pooling operations. In this section, due to
its unique structure, we extend our discussion to other neural network
architectures. Particularly, we focus on networks that exclusively use ReLU
activations, which are prevalent and effective in practical applications.

Interestingly, the principle outlined in Lemma C.2 enables us to replace the
MAX operation in the final layer with an additional ReLU layer. This
revelation lays the groundwork for the following corollary, which directly
stems from Proposition 3.1 and Theorem 3.3

######  Corollary A.1 (Four-layer ReLU networks).

The three-layer neural network in Proposition 3.1 or Theorem 3.3 can be
changed to a four-layer ReLU network with the architecture
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{1}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{2}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1\rightarrow
1$, where $d_{1}$ and $d_{2}$ are exhibited in the proposition or theorem.

###### Proof.

Consider the three-layer neural network proposed in Proposition 3.1 or Theorem
3.3 which has the architecture
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{1}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{2}\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}1$.
Let $a_{1},\cdots,a_{d_{2}}$ be the input of the last layer, thus the output
of the second layer. Since $a_{1},\cdots,a_{d_{2}}\in[0,1]$ from the
construction, we get
$\texttt{MAX}(a_{1},\cdots,a_{k})=1-\sigma(1-a_{1}-\cdots-a_{k})$. This
completes the proof. ∎

We now turn our attention to neural networks trained under binary cross
entropy (BCE) loss. For a single pair of data ${\bm{x}}$ and its corresponding
label $y$, the BCE loss is defined as
$\ell({\bm{x}},y):=y\log(\mathcal{N}({\bm{x}}))+(1-y)\log(1-\mathcal{N}({\bm{x}}))$.
Hence, during training, the output of the neural network must neither be zero
nor exceed $1$. This requirement is the primary reason classifiers utilize the
sigmoid activation function $\texttt{SIG}(x):=\frac{1}{1+e^{-x}}$.

In light of this, we extend our findings to accommodate a network that employs
sigmoid activation in the final layer. This adjustment can be readily achieved
using our previous results, as detailed in Corollary A.1. Notably, this
expansion does not necessitate extra layers, unlike in Corollary A.1. The
outcome is presented in the subsequent corollary.

######  Corollary A.2 (Cross entropy loss).

Let $\mathcal{N}$ be the neural network proposed in one of Proposition 3.1,
Theorem 3.2, Theorem 3.3, or Theorem 3.5. Then, the last activation function
of $\mathcal{N}$ can be replaced by SIG, with $\mathcal{N}$ satisfying

$\displaystyle\mathcal{N}({\bm{x}})$ $\displaystyle>1-\delta$
$\displaystyle\text{if }{\bm{x}}\in\mathcal{X},$
$\displaystyle\mathcal{N}({\bm{x}})$ $\displaystyle<\delta$
$\displaystyle\text{if }{\bm{x}}\not\in B_{\varepsilon}(\mathcal{X})$

for any given $\delta>0$.

###### Proof.

The proof is similar with the proof of Corollary A.1. If the last layer has
MAX activation, then for the inputs $a_{1},a_{2},\cdots,a_{k}$, replace
$\texttt{MAX}(a_{1},\cdots,a_{k})$ to
$\texttt{SIG}(M(-1+a_{1}+a_{2}+\cdots+a_{k}))$ with sufficiently large $M>0$.
If the last layer has ReLU activation, then for the inputs $a$ and $b$,
replace $\sigma(a-b)$ to $\texttt{SIG}(M(a-b-\frac{1}{2}))$ with sufficiently
large $M>0$. It is easy to verify that these substitutions satisfy the desired
property. ∎

##  Appendix B Proofs of Propositions and Theorems

###### Proof of Proposition 1.1.

We prove by contradiction: suppose two-layer ReLU networks are dense in
$L^{p}({\mathbb{R}}^{d})$. Then for a nonzero function $f^{*}$ and
$\varepsilon>0$, there exists a nonzero two-layer ReLU network
$f=\sum_{i=1}^{k}v_{i}\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+b_{0}$ such
that $\left\|f-f^{*}\right\|_{L^{p}({\mathbb{R}}^{d})}<\varepsilon$. Without
loss of generality, we can assume that all $v_{i},{\bm{w}}_{i}$ are nonzero,
i.e., $f$ has the minimal representation. Now, let $K$ be a compact (thus
bounded) set that contains the support of $f^{*}$. Since $f$ is piecewise
linear and defined on the unbounded domain ${\mathbb{R}}^{d}$, we can choose
an unbounded partition $A\subset{\mathbb{R}}^{d}$ such that $f$ is linear in
$A$ and $A\cap K^{c}$ is unbounded. By re-ordering of indices if needed, there
exists $k_{A}\in{\mathbb{N}}$ such that ${\bm{w}}_{i}^{\top}{\bm{x}}+b_{i}\geq
0$ if and only if $i\in[k_{A}]$. Then for ${{\bm{x}}\in A}$,
$f({\bm{x}})=\sum_{i=1}^{k_{A}}v_{i}({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+b_{0}$
and we get

$\displaystyle\left\|f-f^{*}\right\|_{L^{p}({\mathbb{R}}^{d})}^{p}$
$\displaystyle=\int_{{\mathbb{R}}^{d}}|f-f^{*}|^{p}d\mu$
$\displaystyle\geq\int_{A\cap K^{c}}|f-f^{*}|^{p}d\mu$
$\displaystyle\geq\left(\inf_{{\bm{x}}\in A\cap
K^{c}}{|f({\bm{x}})|^{p}}\right)\cdot\mu(A\cap K^{c})$

where $\mu(\cdot)$ denotes the Lebesgue measure on ${\mathbb{R}}^{d}$. Since
$K$ is compact and $A$ is unbounded, $\mu(A\cap K^{c})=\infty$ conclude that
$\inf\limits_{{\bm{x}}\in A\cap K^{c}}|f({\bm{x}})|=0$ for ${\bm{x}}\in A\cap
K^{c}$. Since
$f({\bm{x}})=\sum\limits_{i=1}^{k_{A}}v_{i}({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+b_{0}$
is linear on $A$, we have

$\displaystyle\sum_{i=1}^{k_{A}}v_{i}{\bm{w}}_{i}=\mathbf{0}\qquad\text{and}\qquad
b_{0}+\sum_{i=1}^{k_{A}}v_{i}b_{i}=0.$ (3)

Now consider the adjacent unbounded partition $B$ such that $f$ is linear in
$B$ and $B\cap K^{c}$ is also unbounded (such partition $B$ can be chosen by a
linear partition of $f$ in $A^{c}\cap K^{c}$). Through the exactly same
arguments, we obtain the similar conclusion with (3) on $B$.

$\displaystyle\sum_{i=1}^{k_{B}}v_{i}{\bm{w}}_{i}=0\qquad\text{and}\qquad
b_{0}+\sum_{i=1}^{k_{B}}v_{i}b_{i}=0.$ (4)

However, since $B$ is the adjacent partition of $A$, exactly one neuron (call
$v^{\prime},{\bm{w}}^{\prime}$) is either activated or deactivated in $B$.
Comparing (3) and (4), we get either $v^{\prime}=0$ or
${\bm{w}}^{\prime}=\mathbf{0}$, which contradicts to the minimality
assumption. This completes the proof. ∎

###### Proof of Theorem 3.3.

Let $X_{1},X_{2},\cdots,X_{k}$ be the $k$ facets of $\mathcal{X}$. For each
facet $X_{i}$, we can construct a two-layer ReLU network $\mathcal{T}_{i}$
such that $\mathcal{T}_{i}({\bm{x}})=1$ for ${\bm{x}}\in X_{i}$ and
$\mathcal{T}_{i}({\bm{x}})<0$ ${\bm{x}}\not\in B_{\varepsilon}(X_{i})$ by
Lemma C.3. Then Proposition 3.1 gives a neural network $\mathcal{N}$ with the
architecture
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{1}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\stackrel{{\scriptstyle\texttt{MAX}}}{{\rightarrow}}1$
with $d_{1}\leq k(d+1)$, such that $\mathcal{N}$ can approximate
$\mathbbm{1}_{\\{\mathcal{X}\\}}$ arbitrarily close. The remaining goal is to
reduce the width of the first layer.

From the construction, recall that $d_{1}\leq k(d+1)$ comes from the fact that
each simplex $X_{i}$ is covered by a $d$-simplex which has $(d+1)$
hyperplanes. Now consider two $m$-simplices in ${\mathbb{R}}^{d}$. If
$2m+2\leq d+1$, then we can connect all points of the two $m$-simplices in
${\mathbb{R}}^{d}$, and it becomes a $(2m+2)$-simplex $\Delta^{2m+2}$. Now
construct a $d$-simplex $\Delta^{d+1}$ by choosing $(d+1)-(2m+2)$ points in
$B_{\varepsilon}(\Delta^{2m+2})$, whose base is this $(2m+2)$-simplex. Then,
by adding two distinguishing hyperplanes at last, we totally consume $d+3$
hyperplanes to separate two $m$-simplices.

Now we apply this argument to each pair of two simplices. The above argument
shows that two $m$-simplices separately covered by $2(d+1)$ hyperplanes can be
re-covered by $(d+3)$ hyperplanes if
$m\leq\left\lfloor\frac{d-1}{2}\right\rfloor$, which reduces $(d-1)$ number of
hyperplanes. In other words, we can save $(d-1)$ hyperplanes for each pair of
two $m$-simplices whenever $m\leq\left\lfloor\frac{d-1}{2}\right\rfloor$. This
provides one improved upper bound of $d_{1}$:

$\displaystyle d_{1}\quad\leq\quad
k(d+1)-(d-1)\left\lfloor\frac{1}{2}\sum_{j=0}^{\left\lfloor\frac{d-1}{2}\right\rfloor}k_{j}\right\rfloor.$
(5)

Now, we consider another pairing. For $0\leq j\leq m$, $\mathcal{X}$ has
$k_{j}$ $j$-simplex facets. Recall that each $j$-simplex has $(j+1)$ points,
and a $d$-simplex consists of $(d+1)$-points. Therefore, all points in
$\left\lfloor\frac{d+1}{j+1}\right\rfloor$ $j$-simplices can be contained in
one $d$-simplex. In this case, these $j$-simplices can be covered by adding
$\left\lfloor\frac{d+1}{j+1}\right\rfloor$ hyperplanes more. Thus if we have
$k_{j}$ $j$-simplices, then the required number of hyperplanes to separatedly
encapsulate the $j$-simplices is less than or equal to

$\displaystyle\\#\left(\text{the number of }d\text{-simplices}\right)$
$\displaystyle\cdot\\#\left(\text{the required number of hyperplanes in each
$d$-simplex}\right)$
$\displaystyle=\left(\left\lfloor\frac{k_{j}}{\left\lfloor\frac{d+1}{j+1}\right\rfloor}\right\rfloor+1\right)\cdot\left(d+1+\left\lfloor\frac{d+1}{j+1}\right\rfloor\right)$
$\displaystyle\leq\left(k_{j}\frac{j+1}{d-j}+1\right)\cdot\left(d+1+\frac{d+1}{j+1}\right)$
$\displaystyle<(d+1)\left(\frac{j+2}{j+1}\right)\left(k_{j}\frac{j+1}{d-j}+1\right)$
$\displaystyle=(d+1)\left(k_{j}\frac{j+2}{d-j}+\frac{j+2}{j+1}\right)$ (6)

where the inequality is reduced from the property of the floor function:
$a-1<\left\lfloor a\right\rfloor\leq a<\left\lfloor a\right\rfloor+1$ for any
$a\in{\mathbb{R}}$. Then another upper bound of $d_{1}$ is obtained by
applying (6) for all $j\leq m$. However, also note that (6) is greater than
the known upper bound $k(d+1)$ if $j>\frac{d}{2}$ ; the sharing of covering
simplex is impossible in this case. Therefore, the upper bound of $d_{1}$ is
given by

$\displaystyle d_{1}\quad$
$\displaystyle\leq(d+1)\sum_{j\leq\frac{d}{2}}\left(k_{j}\frac{j+2}{d-j}+\frac{j+2}{j+1}\right)+(d+1)\sum_{j>\frac{d}{2}}k_{j}$
$\displaystyle=(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]$
(7)

Therefore, from (5) and (7), we get

$\displaystyle
d_{1}\leq\min\left\\{k(d+1)-(d-1)\left\lfloor\frac{1}{2}\sum_{j=0}^{\left\lfloor\frac{d-1}{2}\right\rfloor}k_{j}\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\\}.$

∎

###### Proof of Theorem 3.5.

The proof is achieved by applying Theorem 3.2, where each removed rectangular
prisms corresponds to a convex polytope $Q_{j}$. We proceed the proof by
following the Betti numbers. Before we start, we set $P$ to the largest
cuboid, which is enveloped by $2d$ hyperplanes.

First, consider $\beta_{0}$, the number of connected components. To
distinguish two connected components, we need $2$ hyperplanes for one cutting
plane (Figure 2(c)). This is directly generalized to $\beta_{0}$ connected
components, which needs $\beta_{0}-1$ cutting planes. Therefore, the number of
required hyperplanes is $2(\beta_{0}-1)$.

Second, consider $\beta_{1}$. By the similar argument, these long rectangular
prism has a rectangle base enveloped by $2\times 2$ additional hyperplanes,
where other hyperplanes are shared from the large cuboid $P$. Then, the
required number of hyperplanes is $2\cdot 2\beta_{1}$.

Now we generalize this argument. In the $d$-dimensional cuboid $P$, a
$k$-dimensional hole (associated to the Betti number $\beta_{k}$) with $k\geq
1$ is made by $2(k+1)$ additional hyperplanes and other hyperplanes of $P$.
Since all ‘hole’s are disjoint, each hole is independently created. Therefore,
the total number of required hyperplane is

$\displaystyle 2d+2(\beta_{0}-1)+2\sum_{k=1}^{d}(k+1)\beta_{k}\quad=\quad
2\left(d-1+\sum_{k=0}^{d}(k+1)\beta_{k}\right).$

Clearly, from the construction, the number of removed polytopes is
$\beta_{0}-1+\sum_{k=1}^{d}\beta_{k}$, which corresponds to $n_{Q}$ in Theorem
3.2. Since $n_{P}=1$, we obtained the width of the third layer by
$n_{P}+n_{Q}=\sum_{k=0}^{d}\beta_{k}$. Therefore, Theorem 3.2 guarantees that
there exists a four-layer ReLU network with the architecture

$\displaystyle
2\;\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}\;2\left(d-1+\sum_{k=0}^{d}(k+1)\beta_{k}\right)\;\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}\;\left(\sum_{k=0}^{d}\beta_{k}\right)\;\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$

that can approximate $\mathbbm{1}_{\\{\mathcal{X}\\}}$ arbitrarily close. ∎

###### Proof of Theorem 4.1.

Fist we recall one result in real analysis: “the set of compactly supported
continuous functions is dense in $L^{p}({\mathbb{R}}^{d_{x}})$ for $p\geq 1$
[38, Theorem 3.14].” Therefore, it is enough to prove the second statement;
“any compactly supported Lipschitz function can be universally approximated by
a three-layer ReLU network.”

We consider $d_{y}=1$ case first. Let $f:{\mathbb{R}}^{d_{x}}\rightarrow[0,1]$
be a Lipschitz function with the Lipschitz constant $L$. Without loss of
generality, suppose the support of $f$ is contained in $[0,1]^{d_{x}}$. Let
$\delta>0$ be a small unit fraction which will be determined later. We
partition $[0,1]^{d_{x}}$ by regular $d_{x}$-dimensional cubes with length
$\delta$. Now, consider estimating a definite integral by a Riemann sum over
these cubes. The total number of cubes is $n:=(\frac{1}{\delta})^{d_{x}}$, and
we number the cube by $C_{1},C_{2},\cdots,C_{n}$. In each cube $C_{i}$, by
Lemma C.2, we can define a two-layer ReLU network $\mathcal{T}_{i}$ with the
architecture
$d_{x}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}2d_{x}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$
such that $\mathcal{T}_{i}({\bm{x}})=1$ for ${\bm{x}}\in C_{i}$ and
$\mathcal{T}_{i}({\bm{x}})=0$ for ${\bm{x}}\not\in B_{r}(C_{i})$ with
$r:=\frac{1}{2d_{x}}\frac{\delta^{p+1}}{1+\delta^{p}}$. Then for any
${\bm{x}}_{i}\in C_{i}$, we get

$\displaystyle\int_{B_{r}(C_{i})}|f-f({\bm{x}}_{i})\mathcal{T}_{i}|^{p}\;d\mu$
$\displaystyle=\int_{C_{i}}|f-f({\bm{x}}_{i})\mathcal{T}_{i}|^{p}\;d\mu+\int_{B_{r}(C_{i})\backslash
C_{i}}|f-f({\bm{x}}_{i})\mathcal{T}_{i}|^{p}\;d\mu$
$\displaystyle\leq\int_{C_{i}}(\sqrt{d_{x}}L\delta)^{p}\;d\mu+\int_{B_{r}(C_{i})\backslash
C_{i}}1^{p}\;d\mu$
$\displaystyle\leq(\sqrt{d_{x}}L\delta)^{p}\cdot\delta^{d_{x}}+\left[(\delta+2r)^{d_{x}}-\delta^{d_{x}}\right]$
$\displaystyle=(\sqrt{d_{x}}L)^{p}\cdot\delta^{d_{x}+p}+\left[\left(1+\frac{2r}{\delta}\right)^{d_{x}}-1\right]\delta^{d_{x}}$
$\displaystyle<\left[(\sqrt{d_{x}}L)^{p}+1\right]\delta^{d_{x}+p}.$

Note that we use two inequalities, $|f({\bm{x}})-f({\bm{x}}_{i})|\leq
L\left\|{\bm{x}}-{\bm{x}}_{i}\right\|\leq L\sqrt{d_{x}}\delta$ for
${\bm{x}}\in C_{i}$ and $(1+a)^{k}<\frac{1}{1-ak}$ for $0<a<\frac{1}{k}$.
Then, the above equation implies the $L^{p}$ distance between $f$ and
$f({\bm{x}}_{i})\mathcal{T}_{i}$ in $B_{r}(C_{i})$ is bounded by the above
value. Now we define a three-layer neural network $\mathcal{N}$ by

$\displaystyle\mathcal{N}({\bm{x}}):=\sum_{i=1}^{n}f({\bm{x}}_{i})\mathcal{T}_{i}({\bm{x}}),$

which is the Riemann sum over the $n$ cubes. Then $\mathcal{N}$ has the
architecture
${d_{x}}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(2nd_{x})\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}n\rightarrow
1$ and satisfies

$\displaystyle\int_{{\mathbb{R}}^{d_{x}}}|f-\mathcal{N}|^{p}d\mu$
$\displaystyle=\int_{B_{r}([0,1]^{d_{x}})}|f-\mathcal{N}|^{p}\;d\mu$
$\displaystyle<\sum_{i=1}^{n}\int_{B_{r}(C_{i})}|f-f({\bm{x}}_{i})\mathcal{T}_{i}|^{p}\;d\mu$
$\displaystyle\leq\left[(\sqrt{d_{x}}L)^{p}+1\right]n\delta^{d_{x}+p}.$
$\displaystyle=\left[(\sqrt{d_{x}}L)^{p}+1\right]\delta^{p}.$

Therefore, choose the unit fraction $\delta$ to satisfy
$\delta<\varepsilon\left[1+(\sqrt{d_{x}}L)^{p}\right]^{-\frac{1}{p}}$ for the
given $\varepsilon$, we conclude that
$\left\|f-\mathcal{N}\right\|_{L^{p}([0,1]^{d_{x}})}<\varepsilon$. From this
choice of $\delta$, we get

$\displaystyle n=\delta^{-d_{x}}=O(\varepsilon^{-d_{x}}).$

Lastly, for $d_{y}>1$, we can obtain the desired network by concatenating
$d_{y}$ networks. Therefore, the architecture of such neural network is

$\displaystyle{d_{x}}\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(2nd_{x}d_{y})\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(nd_{y})\rightarrow
d_{y}.$

∎

##  Appendix C Additional Propositions and Lemmas

######  Proposition C.1.

Let $\mathcal{X}$ be a compact set in ${\mathbb{R}}^{d}$. For arbitrary
$\delta>0$ and $p>0$, suppose there exists a function
$f_{\delta}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$ such that
$f_{\delta}({\mathbb{R}}^{d})=[0,1]$ and

$\displaystyle f_{\delta}({\bm{x}})$ $\displaystyle=1\qquad\text{if
}{\bm{x}}\in\mathcal{X},$ $\displaystyle f_{\delta}({\bm{x}})$
$\displaystyle=0\qquad\text{if }{\bm{x}}\not\in B_{\delta}(\mathcal{X}).$

Then, for arbitrary $\varepsilon>0$, there exists a function
$\mathcal{N}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$ such that

$\displaystyle\left\|\mathcal{N}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{x}})\right\|_{L^{p}({\mathbb{R}}^{d})}<\varepsilon.$
(8)

###### Proof.

Let $\mu$ be the Lebesgue measure in ${\mathbb{R}}^{d}$. First note that

$\displaystyle\lim\limits_{\delta\rightarrow
0^{+}}\mu(B_{\delta}(\mathcal{X})-\mathcal{X})=\mu(\bar{\mathcal{X}}\backslash\mathcal{X})=0.$

Therefore, for a given $\varepsilon$, there exists $\delta>0$ such that

$\displaystyle\mu\left(B_{\delta}(\mathcal{X})-\mathcal{X}\right)<\varepsilon^{p}.$

From the assumption, for such $\delta$, there exists a function
$f_{\delta}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$ that satisfies
$f_{\delta}({\mathbb{R}}^{d})=[0,1]$, $f_{\delta}({\bm{x}})=1$ for
${\bm{x}}\in\mathcal{X}$, and $f_{\delta}({\bm{x}})=0$ if ${\bm{x}}\not\in
B_{\delta}(\mathcal{X})$. Now, define $\mathcal{N}:=f_{\delta}$. Then,

$\displaystyle\left\|\mathcal{N}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{x}})\right\|_{L^{p}({\mathbb{R}}^{d})}^{p}$
$\displaystyle=\int_{{\mathbb{R}}^{d}}|\mathcal{N}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{x}})|^{p}\;d\mu$
$\displaystyle=\int_{B_{\delta}(\mathcal{X})}|\mathcal{N}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{x}})|^{p}\;d\mu$
$\displaystyle=\int_{B_{\delta}(\mathcal{X})\backslash\mathcal{X}}|\mathcal{N}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{x}})|^{p}\;d\mu$
$\displaystyle\leq
1^{p}\cdot\mu\left({B_{\delta}(\mathcal{X})\backslash\mathcal{X}}\right)$
$\displaystyle<\varepsilon^{p}.$

Therefore, $\mathcal{N}$ is the desired function satisfying (8). ∎

######  Lemma C.2.

Let $C\subset{\mathbb{R}}^{d}$ be a closed convex polytope enclosed by $k$
hyperplanes, which has finite positive Lebesgue measure in ${\mathbb{R}}^{d}$.
Then, for any $\varepsilon>0$, there exists a two-layer ReLU network
$\mathcal{T}$ with the architecture
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\rightarrow 1$ such that

$\displaystyle\mathcal{T}({\bm{x}})$ $\displaystyle=1\qquad\text{if
}{\bm{x}}\in C,$ $\displaystyle\mathcal{T}({\bm{x}})$
$\displaystyle<1\qquad\text{if }{\bm{x}}\in B_{\varepsilon}(C)-C.$
$\displaystyle\mathcal{T}({\bm{x}})$ $\displaystyle<0\qquad\text{if
}{\bm{x}}\not\in B_{\varepsilon}(C).$

(a)

(b)

Figure 4: Proof of Lemma C.2. (a) A closed convex polytope
$C\subset{\mathbb{R}}^{d}$ enclosed by $k$ hyperplanes. The volume of $C$ is
the sum of volume of $k$ cones. (b) The architecture of the desired two-layer
ReLU network $\mathcal{T}$:
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\rightarrow 1$.

###### Proof.

Let $h_{1},\cdots,h_{k}$ be the $k$ hyperplanes enclosing $C$. Let
${\bm{w}}_{i}$ be the unit normal vector of the $i$-th hyperplane $h_{i}$
oriented inside $C$. Then the equation of the $i$-th hyperplane $h_{i}$ is
given by $h_{i}:\\{{\bm{x}}~{}|~{}{\bm{w}}_{i}^{\top}{\bm{x}}+b_{i}=0\\}$ for
some $b_{i}\in{\mathbb{R}}$. Let $A_{i}$ be the intersection of the hyperplane
$h_{i}$ and $C$, which is a face of the polytope $C$. Let ${\bm{x}}$ be a
point in $C$. Since ${\bm{w}}_{i}$ is a unit normal vector,
${\bm{w}}_{i}^{\top}{\bm{x}}+b_{i}$ refers the distance between the hyperplane
$h_{i}$ and the point ${\bm{x}}$. Therefore, the $d$-dimensional Lebesgue
measure of $C$ is computed by

$\displaystyle\mu_{d}(C)=\frac{1}{d}\sum_{i=1}^{k}({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})\cdot\mu_{d-1}(A_{i})$
(9)

where $\mu_{d-1}$ and $\mu_{d}$ refer the $(d-1)$ and $d$-dimensional Lebesgue
measures, respectively. Note that (9) comes from the volume formula of a cone.
Then LHS of (9) is constant, which does not depend on the choice of
${\bm{x}}\in{\mathbb{R}}^{d}$. Now, we define a two-layer ReLU network
$\mathcal{T}$ with the architecture
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\rightarrow 1$ by

$\displaystyle\mathcal{T}({\bm{x}}):=1+M\left(\mu_{d}(C)-\sum_{i=1}^{k}\frac{1}{d}\mu_{d-1}(A_{i})\cdot\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})\right)$
(10)

where $M>0$ is a constant would be determined later. Note that we have
$\mathcal{T}({\bm{x}})=1$ for ${\bm{x}}\in C$ from the construction. It is
worth noting that the equation (9) also holds for ${\bm{x}}\not\in C$. For
${\bm{x}}\not\in C$, (10) deduces

$\displaystyle\mathcal{T}({\bm{x}})$
$\displaystyle=1+M\left(\mu_{d}(C)-\sum_{i=1}^{k}\frac{1}{d}\mu_{d-1}(A_{i})\cdot\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})\right)$
$\displaystyle=1+M\left(\mu_{d}(C)-\sum_{i=1}^{k}\frac{1}{d}\mu_{d-1}(A_{i})\cdot({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+\sum_{\\{i~{}:~{}{\bm{w}}_{i}^{\top}{\bm{x}}+b_{i}<0\\}}\frac{1}{d}\mu_{d-1}(A_{i})\cdot({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})\right)$
$\displaystyle=1+M\sum_{\\{i~{}:~{}{\bm{w}}_{i}^{\top}{\bm{x}}+b_{i}<0\\}}\frac{1}{d}\mu_{d-1}(A_{i})\cdot({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})$
$\displaystyle<1.$

Therefore, we conclude

$\displaystyle\mathcal{T}({\bm{x}})$ $\displaystyle=1\qquad\text{if
}{\bm{x}}\in C,$ $\displaystyle\mathcal{T}({\bm{x}})$
$\displaystyle<1\qquad\text{otherwise}.$

Lastly, we determine the constant $M$ in $\mathcal{T}$ to satisfy the remained
property. For the given $\varepsilon>0$, consider the closure of complement of
the $\frac{\varepsilon}{2}$-neighborhood of $C$;
$D:=\overline{\left(B_{{\varepsilon}/{2}}(C)\right)^{c}}$. Then the previsous
result shows that

$\displaystyle\frac{1}{M}(\mathcal{T}({\bm{x}})-1)=\mu_{d}(C)-\sum_{i=1}^{k}\frac{1}{d}\mu_{d-1}(A_{i})\cdot\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})$
(11)

is bounded above by $0$. Furthermore, (11) is continuous piecewise linear, and
has the maximum $0$ if and only if ${\bm{x}}\in C$. Since $D$ is closed and
(11) is strictly bounded above by $0$ on $D$, (11) has the finite maximum
$m<0$ on $D$.

$\displaystyle\frac{1}{M}(\mathcal{T}({\bm{x}})-1)\leq m<0\qquad\text{for
}{\bm{x}}\in D.$

Now, choose $M$ to satisfy $M>-\frac{1}{m}$. Then if ${\bm{x}}\not\in
B_{\varepsilon}(C)$, we have ${\bm{x}}\in D$, thus

$\displaystyle\mathcal{T}({\bm{x}})$
$\displaystyle=1+M\left(\mu_{d}(C)-\sum_{i=1}^{k}\frac{1}{d}\mu_{d-1}(A_{i})\cdot\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})\right)$
$\displaystyle\leq 1+M\cdot m$ $\displaystyle<0.$

Therefore, we have constructed a two-layer ReLU network $\mathcal{T}$ with the
structure $d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}k\rightarrow 1$ such
that

$\displaystyle\mathcal{T}({\bm{x}})$ $\displaystyle=1\qquad\text{if
}{\bm{x}}\in C,$ $\displaystyle\mathcal{T}({\bm{x}})$
$\displaystyle<1\qquad\text{if }{\bm{x}}\in C^{c}.$
$\displaystyle\mathcal{T}({\bm{x}})$ $\displaystyle<0\qquad\text{if
}{\bm{x}}\not\in B_{\varepsilon}(C).$

which completes the proof. ∎

######  Lemma C.3.

Let $0\leq m\leq d$ be integers, and $\Delta^{m}$ be an $m$-simplex in
${\mathbb{R}}^{d}$. For a given $\varepsilon>0$, there exists a two-layer ReLU
network $\mathcal{T}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$ with the
architecture $d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}(d+1)\rightarrow
1$ such that

$\displaystyle\mathcal{T}({\bm{x}})$ $\displaystyle=1\qquad\text{if
}{\bm{x}}\in\Delta^{m},$ $\displaystyle\mathcal{T}({\bm{x}})$
$\displaystyle\leq 1\qquad\text{if }{\bm{x}}\in B_{\varepsilon}(\Delta^{m}),$
$\displaystyle\mathcal{T}({\bm{x}})$ $\displaystyle<0\qquad\text{if
}{\bm{x}}\not\in B_{\varepsilon}(\Delta^{m}).$

Furthermore, the minimal width of such two-layer ReLU networks with the
architecture $d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{1}\rightarrow
1$ is exactly $d_{1}=d+1$.

###### Proof.

We prove the existence part first. For the given $m$-simplex $\Delta^{m}$,
pick $(d-m)$ distinct points in $B_{\varepsilon}(\Delta^{m})$. By connecting
all these points with the points of $\Delta^{m}$, we obtain a $d$-simplex
contained in $B_{\varepsilon}(\Delta^{m})$, which is a convex polytope. By
Lemma C.2, there exists a neural network
$\mathcal{T}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$ with the architecture
$d\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}d_{1}\rightarrow 1$ that
satisfies the desired properties.

Now, we prove the minimality part. For every $\varepsilon>0$, suppose there
exists a two-layer ReLU network
$\mathcal{T}({\bm{x}}):=\sum_{i=1}^{d_{1}}v_{i}\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+v_{0}$
with $d_{1}\leq d$ such that $\mathcal{T}({\bm{x}})=1$ for
${\bm{x}}\in\Delta^{m}$ and $\mathcal{T}({\bm{x}})<0$ for ${\bm{x}}\not\in
B_{\varepsilon}(\Delta^{m})$. First, we claim that the set of weight vectors
$\\{{\bm{w}}_{1},\cdots,{\bm{w}}_{d_{1}}\\}$ spans ${\mathbb{R}}^{d}$. If the
set cannot span ${\mathbb{R}}^{d}$, then there exists a nonzero vector
${\bm{u}}\in{\mathbb{R}}^{d}-\text{span}<{\bm{w}}_{1},\cdots,{\bm{w}}_{d_{1}}>$.
Then, from $\mathcal{T}({\bm{x}})=1$ for ${\bm{x}}\in\Delta^{m}$, we get

$\displaystyle\mathcal{T}({\bm{x}}+t{\bm{u}})$
$\displaystyle=\sum_{i=1}^{d_{1}}v_{i}\sigma({\bm{w}}_{i}^{\top}({\bm{x}}+t{\bm{u}})+b_{i})+v_{0}$
$\displaystyle=\sum_{i=1}^{d_{1}}v_{i}\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+v_{0}$
$\displaystyle=\mathcal{T}({\bm{x}})$ $\displaystyle=1$

for any $t\in{\mathbb{R}}$. This contradicts to the condition
$\mathcal{T}({\bm{x}})<0$ for ${\bm{x}}\not\in B_{\varepsilon}(\Delta^{m})$.
Therefore, the set of weight vectors must span ${\mathbb{R}}^{d}$.

From the above claim, we further deduce that $d_{1}\geq d$. Since we start
with the assumption $d_{1}\leq d$, thus $d_{1}=d$. Then, we conclude that the
set of weight vectors $\\{{\bm{w}}_{1},\cdots,{\bm{w}}_{d_{1}}\\}$ is a basis
of ${\mathbb{R}}^{d}$. Now, we focus on the sign of $v_{0}$. Suppose
$v_{0}\geq 0$. Define

$\displaystyle
A:=\bigcap_{i=1}^{d_{1}}\\{{\bm{x}}~{}|~{}{\bm{w}}_{i}^{\top}{\bm{x}}+b_{i}<0\\},$

which is an unbounded set since the set $\\{{\bm{w}}_{i}\\}$ is linearly
independent. Then for ${\bm{x}}\in A$, we get $\mathcal{T}({\bm{x}})=v_{0}\geq
0$. This contradicts to the assumption $\mathcal{T}({\bm{x}})<0$ for all
${\bm{x}}\not\in B_{\varepsilon}(\Delta^{m})$. Therefore, $v_{0}<0$.

Lastly, we consider the sign of $v_{i}$. Since $\mathcal{T}({\bm{x}})=1>0$ for
${\bm{x}}\in\Delta^{m}$ and $v_{0}<0$, there exists some positive $v_{i}>0$,
say, $v_{1}>0$. Similar to the above argument, we define

$\displaystyle
B:=\left\\{{\bm{x}}~{}|~{}v_{1}{\bm{w}}_{1}^{\top}{\bm{x}}+b_{1}+v_{0}>0\right\\}\;\bigcap_{i=2}^{d_{1}}\left\\{{\bm{x}}~{}|~{}{\bm{w}}_{i}^{\top}{\bm{x}}+b_{i}<0\right\\},$

which is also nonempty and unbounded. Then, for ${\bm{x}}\in B$, we have

$\displaystyle\mathcal{T}({\bm{x}})$
$\displaystyle=\sum_{i=1}^{d_{1}}v_{i}\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+v_{0}$
$\displaystyle=v_{1}{\bm{w}}_{1}^{\top}{\bm{x}}+b_{1}+v_{0}$
$\displaystyle>0.$

Since $B$ is unbounded, this implies that $\mathcal{T}({\bm{x}})>0$ over the
unbounded subset in ${\mathbb{R}}^{d}$, which contradicts to the condition
$\mathcal{T}({\bm{x}})<0$ for all ${\bm{x}}\not\in
B_{\varepsilon}(\Delta^{m})$. This completes the whole proof, which shows that
the minimum width of two-layer ReLU network is exactly $d+1$. ∎

(a)

(b)

(c)

Figure 5: Proof of Proposition C.4. (a) $\mathcal{X}$ is a crown-shaped
topological space in ${\mathbb{R}}^{2}$. A straight line $\ell$ through the
top of the crown. (b) The pre-activation $\mathcal{T}({\bm{x}})$ along the
line $\ell$ must experience six sign changes, which needs at least five non-
differentiable points. (c) However, any straight line in ${\mathbb{R}}^{2}$
can meet at most three non-differentiable points of $\mathcal{T}({\bm{x}})$.

######  Proposition C.4.

Let $\mathcal{X}$ be a crown-shaped topological space in ${\mathbb{R}}^{2}$,
as shown in Figure 5(a). Then, for some $\varepsilon>0$, there is no two-layer
ReLU network $\mathcal{N}$ with the architecture
$2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}3\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$
such that

$\displaystyle\left\|\mathcal{N}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}({\bm{x}})\right\|_{L^{p}({\mathbb{R}}^{2})}<\varepsilon.$
(12)

###### Proof.

We use proof by contradiction. For every $\varepsilon>0$, suppose there exists
a two-layer ReLU network
$\mathcal{N}({\bm{x}})=\sigma(\sum_{i=1}^{3}v_{i}\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+v_{0})$
that satisfies (12). Let
$\mathcal{T}({\bm{x}}):=\sum_{i=1}^{k}v_{i}\sigma({\bm{w}}_{i}^{\top}{\bm{x}}+b_{i})+v_{0}$
be the pre-activation of the $\mathcal{N}({\bm{x}})$.

Now, consider a straight line $\ell$ that through the sawtooth part of
$\mathcal{X}$, as described in 5(a). Since $\mathcal{T}({\bm{x}})$ is
piecewise linear, it is still piecewise linear on the line $\ell$. However,
since $\mathcal{N}({\bm{x}})$ is a sufficiently good approximator of
$\mathbbm{1}_{\\{\mathcal{X}\\}}$, we have
$|\mathcal{N}({\bm{x}})-\mathbbm{1}_{\\{\mathcal{X}\\}}|$ is small, which
implies $\mathcal{T}({\bm{x}})\leq 0$ for
${\bm{x}}\not\in\bm{B}_{\varepsilon}(\mathcal{X})$ and
$\mathcal{T}({\bm{x}})>0$ for ${\bm{x}}\in\mathcal{N}({\bm{x}})$. Therefore,
$\mathcal{T}({\bm{x}})$ on the line $\ell$ must have alternative negative and
positive values as shown in 5(a). More precisely,
$\mathcal{T}({\bm{x}})|_{{\bm{x}}\in\ell}$ has four negative parts and three
positive parts. Since it is piecewise linear, to change the sign six times, it
requires at least five flipping points as shown in Figure 5(b). In other
words, $\mathcal{T}({\bm{x}})$ has at least five non-differentiable points.
However, $\mathcal{T}({\bm{x}})$ can have at most three non-differentiable
points on any straight line because it has only three ReLU neurons (Figure
5(c)). This contradiction proves that there is no two-layer ReLU network
$\mathcal{N}$ with the architecture
$2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}3\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$
that can approximate $\mathbbm{1}_{\\{\mathcal{X}\\}}$ arbitrarily close. ∎

######  Remark C.5.

Proposition 3.1 and Proposition C.4 demonstrate that the minimum widths of
neural networks can vary for two topologically equivalent spaces. In
${\mathbb{R}}^{2}$, Proposition 3.1 illustrates that the indicator function on
a solid triangle can be approximated by a network with the architecture
$2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}3\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$.
However, Proposition C.4 shows that the indicator function on a crown-shaped
topological space cannot be approximated by a neural network with the
architecture
$2\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}3\stackrel{{\scriptstyle\sigma}}{{\rightarrow}}1$.
Despite the two topological spaces being homotopy equivalent and having the
same Betti numbers, the minimum architecture of the neural networks are
different.

##  Appendix D Further Experimental Results

In this section, we present additional experimental results that specifically
investigate the effect of initialization. We use the two datasets
$\mathcal{X}_{1}$ and $\mathcal{X}_{2}$ described in Figure 3(a) and (d). For
three or four-layer ReLU networks employing the MSE loss during training,
which exhibit ReLU or MAX activation at the final layer, the networks often
encounter dying ReLU initialization issue (constant output) as mentioned in
[27]. Therefore, we have excluded these cases from our analysis.

In Figure 6 and 7, we present the experimental results for various
initialization schemes. The first and third columns represent the
initialization state of the network, where the second and fourth columns show
the trained network. Each row has the same initialization schemes, which are
uniform initialization $U([0,1])$, normal initialization $N(0,{\bm{I}})$,
Xavier uniform and normal initialization [9], He uniform and normal
initialization [17], small-norm initialization, and manually initialized
weight and bias, from top to bottom. Note that the last row represents
manually initialized case, which are intended to converge to the network we
constructed in the proof of Proposition 3.1 and Theorem 3.2. Indeed, weight
vectors in the first layer of the converged networks enclose each manifold
$\mathcal{X}_{i}$. This experimental results show that our proposed networks
can be achieved by gradient descent under specific initialization.

###  D.1 Detail setup of experiments

We outline the detailed setup of the experiments here. All experiments were
executed using Pytorch on a GeForce GTX 1080 Ti. For each task, the training
dataset was generated from $40\times 40=1600$ lattice points in the
$[-20,20]\times[-20,20]\subset{\mathbb{R}}^{2}$ range, where each point was
labeled ‘1’ if the point was in $\mathcal{X}$, and ‘0’ otherwise.

We utilized two types of loss functions. For the training set
${({\bm{x}}_{i},y_{i})}_{i=1}^{n}$, the mean square error (MSE) loss is
defined as:

$\displaystyle
L_{MSE}(\theta):=\frac{1}{n}\sum_{i=1}^{n}\left[\mathcal{N}_{\theta}({\bm{x}}_{i})-y_{i})\right]^{2}.$

The binary cross entropy (BCE) loss is given by:

$\displaystyle
L_{BCE}(\theta):=\frac{1}{n}\sum_{i=1}^{n}\left[y_{i}\log(\mathcal{N}_{\theta}({\bm{x}}_{i}))+(1-y_{i})\log(1-\mathcal{N}_{\theta}({\bm{x}}_{i}))\right].$

It should be noted that the input of the BCE loss must satisfy
$0<\mathcal{N}_{\theta}({\bm{x}}_{i})<1$, which necessitates the use of the
sigmoid activation function in the last layer.

The optimization method employed was full-batch gradient descent, with
learning rates set at 0.005 for $\mathcal{X}_{1}$ (two triangles) and 0.001
for $\mathcal{X}_{2}$ (a hexagon with a pentagon hole). The total number of
epochs was flexibly determined for each experiment, ensuring a sufficient
number to achieve convergence.

Figure 6: Initialization and convergence results to approximate
$\mathbbm{1}_{\\{\mathcal{X}_{2}\\}}$ via gradient descent. The first and
third columns present the network initialization, and the second and fourth
columns present the trained network under MSE and BCE loss, respectively. Each
row has the same initialization scheme, which is given by uniform
initialization $U([0,1])$, normal initialization $N(0,{\bm{I}})$, Xavier
uniform and normal initialization [9], He uniform and normal initialization
[17], small-norm initialization, and manually initialized weights and bias,
from top to bottom.

Figure 7: Initialization and convergence results to approximate
$\mathbbm{1}_{\\{\mathcal{X}_{2}\\}}$ via gradient descent. The first and
third columns present the network initialization, and the second and fourth
columns present the trained network under MSE and BCE loss, respectively. Each
row has the same initialization scheme, which is given by uniform
initialization $U([0,1])$, normal initialization $N(0,{\bm{I}})$, Xavier
uniform and normal initialization [9], He uniform and normal initialization
[17], small-norm initialization, and manually initialized weights and bias,
from top to bottom.