Minimum Width of Leaky-ReLU Neural Networks for Uniform Universal
  Approximation
The study of universal approximation properties (UAP) for neural networks
(NN) has a long history. When the network width is unlimited, only a single
hidden layer is sufficient for UAP. In contrast, when the depth is unlimited,
the width for UAP needs to be not less than the critical width
$w^*_{\min}=\max(d_x,d_y)$, where $d_x$ and $d_y$ are the dimensions of the
input and output, respectively. Recently, \cite{cai2022achieve} shows that a
leaky-ReLU NN with this critical width can achieve UAP for $L^p$ functions on a
compact domain ${K}$, \emph{i.e.,} the UAP for $L^p({K},\mathbb{R}^{d_y})$.
This paper examines a uniform UAP for the function class
$C({K},\mathbb{R}^{d_y})$ and gives the exact minimum width of the leaky-ReLU
NN as $w_{\min}=\max(d_x,d_y)+\Delta (d_x, d_y)$, where $\Delta (d_x, d_y)$ is
the additional dimensions for approximating continuous functions with
diffeomorphisms via embedding. To obtain this result, we propose a novel
lift-flow-discretization approach that shows that the uniform UAP has a deep
connection with topological theory.
Li'ang Li, Yifei Duan, Guanghua Ji, Yongqiang Cai
# Minimum Width of Leaky-ReLU Neural Networks

###### Abstract

The study of universal approximation properties (UAP) for neural networks (NN) has a long history. When the network width is unlimited, only a single hidden layer is sufficient for UAP. In contrast, when the depth is unlimited, the width for UAP needs to be not less than the critical width \(w_{\min}^{*}=\max(d_{x},d_{y})\), where \(d_{x}\) and \(d_{y}\) are the dimensions of the input and output, respectively. Recently, (Cai, 2022) shows that a leaky-ReLU NN with this critical width can achieve UAP for \(L^{p}\) functions on a compact domain \(\mathcal{K}\), _i.e.,_ the UAP for \(L^{p}(\mathcal{K},\mathbb{R}^{d_{y}})\). This paper examines a uniform UAP for the function class \(C(\mathcal{K},\mathbb{R}^{d_{y}})\) and gives the exact minimum width of the leaky-ReLU NN as \(w_{\min}=\max(d_{x}+1,d_{y})+1_{d_{y}=d_{x}+1}\), which involves the effects of the output dimensions. To obtain this result, we propose a novel lift-flow-discretization approach that shows that the uniform UAP has a deep connection with topological theory.

Machine Learning, Neural Networks, Uniform Universal Approximation

## 1 Introduction

The universal approximation theorem is important for the development of artificial neural networks. Artificial neural networks can approximate functions with arbitrary precision, this fact reveals the great potential of neural networks, and provides important guarantees for its development. (Cybenko, 1989) produces the original universal approximation theorem, stating that an arbitrarily wide feedforward neural network with a single hidden layer and sigmoid activation function can arbitrarily approximate continuous function. (Hornik, 1991) later demonstrated that the key to the universal approximation property lies in the multilayer and neuron architecture rather than the choice of an activation function. Then, (Leshno et al., 1993) show that for a continuous activation function \(f:X\to R^{d_{y}}\) defined on a compact set \(X\subseteq R^{d_{x}}\) can be approximated by a single hidden layer neural network, if and only if, the activation function is a nonpolynomial function.

After solving the activation function's theoretical problem, the field of vision naturally shifted to a consideration of the width and depth of the neural network. With the gradual development of deep neural networks, researchers have begun to pay attention to how to theoretically analyze the expressiveness of networks. (Daniely, 2017) simplifies the proof that the expressive ability of the three-layer neural network is superior to that of the two-layer neural network. For any positive integer \(k\), (Telgarsky, 2016) shows that there are neural networks with \(\Theta(k^{3})\) layers and fixed widths that cannot be approximated by networks with \(\mathcal{O}(k)\) layers unless they have \(\Omega(2^{k})\) nodes 1. The universal approximation theorem explains that deep-bounded neural networks with suitable activation functions are universal approximators. (Lu et al., 2017) explained that a neural network with a bounded width can also be a universal approximator, such as the width-\((d_{x}+4)\) ReLU networks, where \(d_{x}\) is the input dimension. (Lu et al., 2017) also shows that a ReLU network of width \(d_{x}\) cannot be used for universal approximation.

Footnote 1: \(\Theta(k^{3})\) means that it is bound both above and below by \(k^{3}\) asymptotically; \(\mathcal{O}(k)\) means that it is bounded above by \(k\) asymptotically; \(\Omega(2^{k})\) means that it is bounded below by \(2^{k}\) asymptotically.

Many studies, such as (Beise & Da Cruz, 2020; Hanin & Sellke, 2018; Park et al., 2021), have shown that for a narrow neural network (the width is not greater than the input dimension), it is difficult to attain the UAP. (Nguyen et al., 2018) noted that deep neural networks with a specific type of activation function generally need to have a width larger than the input dimension to guarantee that the network can produce disconnected decision regions. For ReLU networks, (Park et al., 2021) proved that the minimum width for \(L^{p}\)-UAP is \(w_{\min}=\max(d_{x}+1,d_{y})\) and summarized the known upper/lower bounds on the minimum width for universal approximation. Furthermore, conclusions related to the UAP of continuous functions have yet to be studied.
(Park et al., 2021) and (Cai, 2022) demonstrate the minimum width of some neural networks for \(C\)-UAP using noncontinuous activation functions. If only continuous monotonically increasing activation functions are used, the known minimum width is restricted to the ReLU NN for function class \(\mathcal{C}([0,1],\mathbb{R}^{2})\), where the critical width is \(w_{\min}=3\). Table 1 provides a summary of the known minimum width for UAP.

To determine the minimum width of uniform UAP on \(\mathcal{C}(\mathcal{K},\mathbb{R}^{d_{y}})\), we introduce a novel scheme called _lift-flow-discretization approach_. Based on the close relationship between uniform UAP and topology, the functions are embedded in high-dimensional diffeomorphisms, and feedforward neural networks are used to approximate these flow maps. Finally, we determine the minimum width of leaky-ReLU neural networks for \(C\)-UAP on \(\mathcal{C}(\mathcal{K},\mathbb{R}^{d_{y}})\) to be \(w_{\min}=\max(d_{x}+1,d_{y})+1_{d_{y}=d_{x}+1}\).

### Contributions

1. Theorem 2.2 states that the minimum width of leaky-ReLU networks for \(\mathcal{C}(\mathcal{K},\mathbb{R}^{d_{y}})\) is exactly \(\max(d_{x}+1,d_{y})+1_{d_{y}=d_{x}+1}\). This is the first time that the minimum width for the universal approximation of leaky-ReLU networks is fully provided. It is worth mentioning that the previous results for the minimum width for the uniform approximation are based on discontinuous activation functions. The conclusion of this paper is based on continuous activation functions such as the leaky-ReLU function.
2. Section 3 presents a novel approach for approximating continuous functions using a feedforward neural network from the perspective of topology. The lift-flow-discretization approach of combining topology and neural network approximation is the key to the proof in this paper. Our approach is generic for strictly monotone continuous activations, as they all correspond to diffeomorphisms.

### Related work

**Width and depth bounds.** Theoretical analyses of the expressive power of neural networks have taken place over the years. (Cybenko, 1989) proposed a prototype of the early classic universal approximation theorem. Continuous univariate functions over bounded domains can be fitted with arbitrary precision using the sigmoid activation function. (Hornik et al., 1989; Leshno et al., 1993; Barron, 1994) obtained similar conclusions and extended them to a large class of activation functions, revealing the relationship between universal approximation and network structure.

The effect of neural network width on expressiveness is an enduring question. (Sutskever and Hinton, 2008; Le Roux and Bengio, 2008) and (Montufar, 2014) reveal the impact of depth and width, especially width, on the general approximation of belief networks, and networks with too narrow a width cannot complete the approximation task. The width has important research value for many emerging networks and different activation functions. Conventional conclusions tell us that networks with appropriate activation functions under bounded depths are universal approximators. Correspondingly, (Lu et al., 2017) proposed a general approximation theorem for ReLU networks with bounded widths. (Hanin and Sellke, 2018) also studied in the ReLU network, whose input dimension is \(d_{x}\), hidden layer width is at most \(w\) and depth is not limited. To fit any continuous real-valued function, the minimum value of \(w\) is exactly \(d_{x}+1\).

For a deep neural network that satisfies the activation function \(\sigma(\mathbb{R})=\mathbb{R}\), to learn the disconnected regions, it is usually necessary to make the network width larger than the input dimension. If the network is narrow, the paths connecting the disconnected regions yield high-confidence predictions (Nguyen et al., 2018). (Chong, 2020) gives a direct algebraic proof of the universal approximation theorem, and (Beise et al., 2021) reveals the fundamental reason why the universal approximation of network functions with width \(w\leq d_{x}\) from \(\mathbb{R}^{d_{x}}\) to \(\mathbb{R}\) is impossible.

(Park et al., 2021) gives the first definitive results for the

\begin{table}
\begin{tabular}{c c c c} \hline \hline References & Functions & Activation & Minimum width \\ \hline (Hanin and Sellke, 2018) & \(\mathcal{C}(\mathcal{K},\mathbb{R})\) & ReLU & \(w_{\min}=d_{x}+1\) \\ \hline (Park et al., 2021) & \(L^{p}(\mathbb{R}^{d_{x}},\mathbb{R}^{d_{y}})\) & ReLU & \(w_{\min}=\max(d_{x}+1,d_{y})\) \\ (Park et al., 2021) & \(\mathcal{C}([0,1],\mathbb{R}^{2})\) & ReLU & \(w_{min}=3\) \\ (Park et al., 2021) & \(\mathcal{C}(\mathcal{K},\mathbb{R}^{d_{y}})\) & ReLU + STEP & \(w_{\min}=\max(d_{x}+1,d_{y})\) \\ \hline (Cai, 2022) & \(D^{p}(\mathcal{K},\mathbb{R}^{d_{y}})\) & Leaky-ReLU & \(w_{\min}=\max(d_{x},d_{y},2)\) \\ (Cai, 2022) & \(\mathcal{C}(\mathcal{K},\mathbb{R}^{d_{y}})\) & ReLU + FLOOR & \(w_{\min}=\max(d_{x},d_{y},2)\) \\ \hline Ours (Theorem 2.2) & \(\mathcal{C}(\mathcal{K},\mathbb{R}^{d_{y}})\) & Leaky-ReLU & \(w_{\min}=\max(d_{x}+1,d_{y})+1_{d_{y}=d_{x}+1}\) \\ Ours (Lemma 2.4) & \(\mathcal{C}(\mathcal{K},\mathbb{R}^{d_{x}})\) & Leaky-ReLU & \(w_{\min}=d_{x}+1\) \\ \hline \hline \end{tabular}

\(\dagger\)\(d_{x}\) and \(d_{y}\) are the input and output dimensions, respectively. \(\mathcal{K}\subset\mathbb{R}^{d_{x}}\) is a compact domain and \(p\in[1,\infty)\).

\end{table}
Table 1: A summary of the known minimum width of feed-forward neural networks for universal approximation. \({}^{\dagger}\)
critical width enabling the universal approximation of width-bounded networks. The minimum width for the \(L^{p}\) functions is \(\max(d_{x}+1,d_{y})\) using the ReLU activation functions. (Park et al., 2021) also shows that this conclusion is unsuitable for the uniform approximation of the ReLU network, but it still holds using the ReLU+STEP activation function. (Cai, 2022) shows that minimum widths for the \(C\)-UAP and \(L^{p}\)-UAP on compact domains have a universal lower bound \(w_{min}=\max(d_{x},d_{y})\). (Cai, 2022) also shows the minimum width for the uniform approximation with some additional threshold activation functions.

**Homeomorphism properties of networks.** Residual networks (ResNets) are an advanced deep learning architecture for supervised learning problems. (Rousseau & Fablet, 2018) shows that a continuous flow of diffeomorphisms governed by ordinary differential equations can be numerically implemented using the mapping component of ResNets.

Neural ordinary differential equations (neural ODEs) turn the neural network training problem into a problem of solving differential equations and can make the discrete ResNet continuous. As a deep learning method, (Teshima et al., 2020) shows the universality of discrete neural ODEs with the condition that the source vectors \(f_{i}(z)\in\mathcal{H}\), where \(\mathcal{H}\) is a universal approximator for the Lipschitz functions. (Ruiz-Balet & Zuazua, 2021) provide \(L^{2}\)-UAP for neural ODE \(\dot{x}=W\sigma(Ax+b)\). (Zhang et al., 2019) shows that neural ODEs with extra dimensions are universal approximators for homeomorphisms.

Invertible neural networks have diffeomorphic properties, and many flow models can also be used as universal approximators. (Huang et al., 2018) shows that neural autoregressive flows are universal approximators for continuous probability distributions. (Teshima et al., 2020) indicates that normalizing flow models based on affine coupling also have UAP. (Kong & Chaudhuri, 2021) shows that residual flows are universal approximators in maximum mean discrepancies.

### Organization

We first define the necessary notation and the main results and give the proof ideas in Section 2. In Section 3, we present our _lift-flow-discretization approach_ demonstrating the minimum width to achieve \(C\)-UAP. The detailed proof process is given in Section 4. Considering the influence of the output dimension, the final proof is divided into four parts. In Section 5, we give an outlook on the direction of our current work. All formal proofs are provided in the appendix.

## 2 Main results

We consider the standard feedforward neural network with the same number of neurons at each hidden layer. We say a \(\sigma\)-NN with depth \(L\) is a function with inputs \(x\in\mathbb{R}^{d_{x}}\) and outputs \(y\in\mathbb{R}^{d_{y}}\), which has the following form:

\[y =f_{NN,L}(x)=y_{L} \tag{1}\] \[=W_{L+1}\sigma\left(W_{L}\left(\cdots\sigma\left(W_{1}x+b_{1} \right)+\cdots\right)+b_{L}\right)+b_{L+1},\]

where \(b_{i}\) are vectors, \(W_{i}\) are matrices and \(\sigma(\cdot)\) is the activation function. We mainly consider the number of neurons in all the layers to be the same \(N\). In this case, \(W_{i}\in\mathbb{R}^{N\times N},b_{i}\in\mathbb{R}^{N},i\in\{1,\cdots,L+1\}\), except \(W_{1}\in\mathbb{R}^{N\times d_{x}}\), \(W_{L+1}\in\mathbb{R}^{d_{y}\times N}\) and \(b_{L+1}\in\mathbb{R}^{d_{y}}\). We denote the set of all networks in Eq. (1) as \(\mathcal{N}_{N,L}(\sigma)\), and \(\mathcal{N}_{N}(\sigma)=\bigcup_{L}\mathcal{N}_{N,L}(\sigma)\). The activation function is crucial for the approximation power of the neural network. Our main results are for the following leaky-ReLU activations function with a fixed parameter \(\alpha\in\mathbb{R}^{+}\setminus\{1\}\),

\[\sigma(x)=\sigma_{\alpha}(x)=\begin{cases}x,&x>0,\\ \alpha x,&x\leq 0.\end{cases} \tag{2}\]

### Main theorem

Our main theorem is the following Theorem 2.2, which provides the exact minimum width of the leaky-ReLU networks that process uniform universal approximations.

**Definition 2.1**.: We say the leaky-ReLU networks with width \(N\) have \(C\)-UAP or \(L^{p}\)-UAP if the set \(\mathcal{N}_{N}(\sigma)\) is dense in \(C(\mathcal{K},\mathbb{R}^{d_{y}})\) or \(L^{p}(\mathcal{K},\mathbb{R}^{d_{y}})\), respectively.

**Theorem 2.2**.: _Let \(\mathcal{K}\subset\mathbb{R}^{d_{x}}\) be a compact set; then, for the continuous function class \(C(\mathcal{K},\mathbb{R}^{d_{y}})\), the minimum width \(w_{\min}\) of leaky-ReLU neural networks having \(C\)-UAP is exactly \(w_{\min}=\max(d_{x}+1,d_{y})+1_{d_{y}=d_{x}+1}\). Thus, \(\mathcal{N}_{N}(\sigma)\) is dense in \(C(\mathcal{K},\mathbb{R}^{d_{y}})\) if and only if \(N\geq w_{\min}\)._

Before giving the proof, let's emphasize the points of Theorem 2.2. First, if the width \(N\) of the leaky-ReLU networks is smaller than \(w_{\min}\), then there is a continuous function \(f^{*}\in C(\mathcal{K},\mathbb{R}^{d_{y}})\) that cannot be well approximated, _i.e._ there is a positive constant \(\varepsilon>0\) such that \(\|f-f^{*}\|>\varepsilon\) for all \(f\in\mathcal{N}_{N}(\sigma)\). For the case of \(\mathcal{K}=[-1,1]^{d_{x}},d_{y}=1\), the function \(f^{*}\) can be chosen as \(f^{*}(x)=\|x\|^{2}\). The reason will be given in the next section, which is based on the topological properties of the level sets (Johnson, 2019).

Second, if \(N=w_{\min}\), then for any \(f^{*}\in C(\mathcal{K},\mathbb{R}^{d_{y}})\) and any \(\varepsilon>0\), we can construct a leaky-ReLU network \(f_{L}\) with width \(N\) and depth \(L\) such that \(\|f-f^{*}\|<\varepsilon\). We will introduce the construction scheme later.

Lastly, the formula of \(w_{\min}\) includes a characteristic func
tion \(1_{d_{y}=d_{x}+1}\),

\[1_{d_{y}=d_{x}+1}=\begin{cases}1,&d_{y}=d_{x}+1,\\ 0,&d_{y}\neq d_{x}+1,\end{cases}\]

which indicates that there is an obstacle of dimension. In fact, this is caused by the topology of the manifolds.

### Proof ideas

Now, we provide the proof scheme, while the details will be given in the next section. As illustrated in Figure 1, the result of Theorem 2.2 is split into four parts: Part 1 and Part 2 give a lower bound and an upper bound for the general dimensions, Part 3 considers the exceptional case of \(d_{y}=d_{x}+1\), and Part 4 considers the case of \(d_{y}\geq d_{x}+2\).

Part 1 is based on the following lemma, which results in a lower bound of leaky-ReLU network to be \(w_{\min}\geq\max(d_{x}+1,d_{y})\).

**Lemma 2.3**.: _For any compact domain \(\mathcal{K}\subset\mathbb{R}^{d_{x}}\), the leaky-ReLU networks with width \(N<\max(d_{x}+1,d_{y})\) do not have UAP for \(C(\mathcal{K},\mathbb{R}^{d_{y}})\), i.e. \(\mathcal{N}_{N}(\sigma)\) is not dense in \(C(\mathcal{K},\mathbb{R}^{d_{y}})\)._

The proof is based on the result of (Cai, 2022), which shows a universal lower bound \(w_{\min}\geq\max(d_{x},d_{y})\) for arbitrary activations, and (Johnson, 2019), which shows that \(w_{\min}\geq d_{x}+1\) for monotone and continuous activations such as leaky-ReLU is sufficient.

Part 2 is based on the following lemma, which considers the case of \(d_{x}=d_{y}=d\). If \(d_{x}\) and \(d_{y}\) are not the same, we can lift them to dimension \(d=\max(d_{x},d_{y})\) by filling in zeros for the auxiliary dimensions.

**Lemma 2.4**.: _For any continuous function \(f^{*}\in C(\mathcal{K},\mathbb{R}^{d})\) on compact domain \(\mathcal{K}\subset\mathbb{R}^{d}\), and \(\varepsilon>0\), there is a leaky-ReLU network \(f_{L}(x)\) with depth \(L\) and width \(d+1\) such that \(\|f_{L}(x)-f^{*}(x)\|\leq\varepsilon\) for all \(x\) in \(\mathcal{K}\)._

Lemma 2.4 is our main result for Part 2, which shows that leaky-ReLU neural network with width \(d+1\) has enough expressive power to approximate continuous function \(f^{*}\) with \(d_{x}=d_{y}=d\). The proof of Lemma 2.4 will be given in Section 3 as it is based on our lift-flow-discretization approach given in the next section.

The gap between the lower bound \(w_{\min}\geq\max(d_{x}+1,d_{y})\) and the upper bound \(w_{\min}\leq\max(d_{x}+1,d_{y}+1)\) is at most one. When \(d_{y}\leq d_{x}\), it directly implies that \(w_{\min}=\max(d_{x}+1,d_{y})\). Then, we consider the case of \(d_{y}\geq d_{x}+1\). In this case, the lower and upper bounds read \(d_{y}\leq w_{\min}\leq d_{y}+1\), and the question is whether width \(N=d_{y}\) is sufficient for \(C\)-UAP.

Part 3 and Part 4 of our main result answer the question by showing that width \(d_{y}\) is enough for the case of \(d_{y}\geq d_{x}+2\) but not for the case of \(d_{y}=d_{x}+1\). The two cases are heavily related to topology theory. Here, we give a short example to show this phenomenon. Let \(f^{*}\in C([0,1],\mathbb{R}^{2})\) be a parameterized curve shaped like '4', which has a self intersecting point. Then, \(f^{*}\) cannot be approximated by curve homeomorphic to a line segment. However, if \(f^{*}\in C([0,1],\mathbb{R}^{3})\), the approximation is possible according to our lift-flow-discretization approach. We will show this example in detail in Section 4.

## 3 Lift-flow-discretization approach

Before presenting our proof of Part 3 and Part 4, we will first provide our key approach for proving Part 3 and Part 4 in Figure 1 which is called the lift-flow-discretization approach in this section. We reformulate network (1) as follows:

\[f_{L}(x)=W_{L+1}\Phi_{L}(W_{1}x+b_{1})+b_{L+1}, \tag{3}\]

where \(\Phi_{L}\) is a map from \(\mathbb{R}^{N}\) to \(\mathbb{R}^{N}\) and \(W_{1}x+b_{1}\) and \(W_{L+1}\Phi+b_{L+1}\) are linear maps. Since we use the leaky-ReLU activation and the weight matrix in (1), it can be

Figure 1: Minimum width of leaky-ReLU networks for universal approximation. (a) Example of function from \(\mathcal{K}\subset\mathbb{R}^{d_{x}}\) to \(\mathbb{R}^{d_{y}}\). (b) Feedforward neural networks with depth \(L\) and width \(N\). (c) The minimum width of leaky-ReLU networks to reach UAP. (d) Proof parts of the main result.
assumed to be nonsingular, the map \(\Phi_{L}\) is a homeomorphism. Motivated by the recent work of (Duan et al., 2022), which shows that leaky-ReLU networks can approximate flow maps, we propose an approach to approximate functions \(f^{*}\) in \(C(\mathcal{K},\mathbb{R}^{d_{y}})\) by lifting it as a diffeomorphism \(\Phi\) and then we approximate \(\Phi\) by flow maps and neural networks.

For any function \(f^{*}\) in \(C(\mathcal{K},\mathbb{R}^{d_{y}})\) and any \(\varepsilon>0\), our lift-flow-discretization approach includes three parts:

1. **(Lift)** A lift map \(\Phi\in C(\mathbb{R}^{N},\mathbb{R}^{N})\), which is an orientation preserving (OP) diffeomorphism such that \[\|f^{*}(x)-\beta\circ\Phi\circ\alpha(x)\|\leq\varepsilon/3,\quad\forall x\in \mathcal{K},\] (4) where \(\alpha\) and \(\beta\) are two linear maps. Without loss of generality, we can assume that the Lipschitz constants of \(\alpha\) and \(\beta\) are less than one. Within this notation, we say the map \(\Phi\) is a lift of \(f^{*}\).
2. **(Flow)** A flow map \(\phi^{\tau}\in C(\mathbb{R}^{N},\mathbb{R}^{N})\) corresponding to a neural ODE \[z^{\prime}(t)=v(z(t),t),t\in(0,\tau),\quad z(0)=x,\] (5) which satisfies \(\|\Phi(x)-\phi^{\tau}(x)\|\leq\varepsilon/3\) for all \(x\) in \(\alpha(\mathcal{K})\).
3. **(Discretization)** A discretization map \(\psi\in C(\mathbb{R}^{N},\mathbb{R}^{N})\) is a leaky-ReLU network in \(\mathcal{N}_{N}(\sigma)\) that approximates \(\phi^{\tau}\) such that \(\|\psi(x)-\phi^{\tau}(x)\|\leq\varepsilon/3\) for all \(x\) in \(\alpha(\mathcal{K})\).

As a result, the composition \(\beta\circ\psi\circ\alpha=:f_{L}\) is a leaky-ReLU network with width \(N\), which approximates the target function \(f^{*}\) such that

\[\|f^{*}(x)-\beta\circ\psi\circ\alpha(x)\|\leq\varepsilon,\quad\forall x\in \mathcal{K}. \tag{6}\]

### Theory of the lift-flow-discretization approach

Note that the existence of \(\phi^{\tau}\) and \(\psi\) are guaranteed by the following lemmas based on the results of (Caponigro, 2011) and (Duan et al., 2022). We need to construct the lift map \(\Phi\), which will be constructed case by case.

**Lemma 3.1**.: _Let \(\Phi\) be an orientation preserving diffeomorphism of \(\mathbb{R}^{N}\), \(\Omega\) be a compact set in \(\mathbb{R}^{N}\) and \(\varepsilon>0\). Then, there is an ODE with tanh neural fields, whose flow map is denoted by \(\phi^{\tau}(x_{0})=z(\tau)\),_

\[\dot{x}(t) =v(x(t),t) \tag{7}\] \[\equiv\sum_{i=1}^{M}a_{i}(t)\tanh(w_{i}(t)\cdot x(t)+b_{i}(t)),t \in[0,\tau],\] \[x(0) =x_{0}\in\mathbb{R}^{N},\quad M\in\mathbb{Z}^{+},\]

_where \(a_{i},w_{i}\in\mathbb{R}^{N}\) and \(b_{i}\in\mathbb{R}\) are piecewise constant functions of \(t\), such that \(\|\phi^{\tau}(x_{0})-\Phi(x_{0})\|<\varepsilon\) for all \(x_{0}\) in \(\Omega\)._

Lemma 3.1 ensures Step 2 ('flow') of our lift-flow-discretization approach, where we use the flow map of a neural ODE to approximate a given orientation preserving diffeomorphism.

The formal proof of the lemma can be seen in the appendix. Here, we provide the main idea of the proof. First, we refer to (Caponigro, 2011) to prove that for any \(\varepsilon>0\), there exists a flow map at the endpoint of time \(\tilde{\phi}^{\tau}(x)\) of an ODE such that \(\|\tilde{\phi}^{\tau}(x)-\Phi(x)\|<\varepsilon/2\) for all \(x\in\alpha(\mathcal{K})\), then we use neural ODE (7) to approximate \(\tilde{\phi}^{\tau}(x)\), there exist \((a,w,b)\) such that the flow map (denoted as \(\phi^{\tau}(x)\)) of Eq. (7) satisfies \(\|\phi^{\tau}(x)-\tilde{\phi}^{\tau}(x)\|<\varepsilon/2\), then \(\|\phi^{\tau}(x)-\Phi(x)\|<\varepsilon\).

**Lemma 3.2**.: _Let \(\phi^{\tau}\in C(\mathbb{R}^{N},\mathbb{R}^{N})\) be the flow map in Lemma 3.1 and \(\Omega\) be a compact set in \(\mathbb{R}^{N}\) and \(\varepsilon>0\). Then, there is a leaky-ReLU network \(\psi\in\mathcal{N}_{N}(\sigma)\) with width \(N\) and depth \(L\) such that \(\|\phi^{\tau}(x_{0})-\psi(x_{0})\|<\varepsilon\) for all \(x_{0}\) in \(\Omega\)._

This lemma ensures Step 3 (discretization) of our lift-flow-discretization approach, where we find a neural network to approximate \(\phi^{\tau}\) in Step 2.

The formal proof, motivated by (Duan et al., 2022), can be seen in the appendix. The main idea is to solve the ODE (7) by a splitting method and then approximate each split step by leaky-ReLU networks. Consider the following splitting for \(v\) in (7), \(v(x,t)\equiv\sum_{i=1}^{N}\sum_{j=1}^{d}v_{ij}(x,t)e_{j}\) with \(v_{ij}(x,t)=a_{i}^{(j)}(t)\tanh(w_{i}(t)\cdot x+b_{i}(t))\in\mathbb{R}\). Then, the flow map can be approximated by an iteration with time step \(\Delta t=\tau/n\), \(n\in\mathbb{Z}^{+}\) large enough,

\[\phi^{\tau}(x_{0})\approx x_{n} =T_{n}(x_{n-1})=T_{n}\circ\cdots\circ T_{1}(x_{0}),\] \[=T_{n}^{(N,d)}\circ\cdots\circ T_{n}^{(1,2)}\circ T_{n}^{(1,1)} \circ\cdots\circ\] \[T_{1}^{(N,d)}\circ\cdots\circ T_{1}^{(1,2)}\circ T_{1}^{(1,1)}(x_ {0}).\]

where the \(k\)-th iteration is \(x_{k+1}=T_{k}x_{k}=T_{k}^{(N,d)}\circ\cdots\circ\)

Figure 2: Sketch of the lift-flow-discretization approach. The target map \(\Phi(x)\) is approximated by a flow map \(\tilde{\phi}^{\tau}(x)\) of an ODE, which is further approximated by a flow map \(\phi^{\tau}(x)\) of a neural ODE (7).
\(T_{k}^{(1,2)}\circ T_{k}^{(1,1)}(x_{k})\), The map \(T_{k}^{(i,j)}:x\to y\) in each split step is:

\[T_{k}^{(i,j)}:\begin{cases}y^{(l)}=x^{(l)},l=1,2,..,j-1,j+1,...,d,\\ y^{(j)}=x^{(j)}+\Delta tv_{ij}(x,k\Delta t).\end{cases}\]

Combining all the approximation networks, we have \(\|\phi^{\tau}(x_{0})-\psi(x_{0})\|<\varepsilon\) for all \(x_{0}\in\Omega\).

Having reached the above conclusion, if the lift map \(\Phi\) in Step 1 (lift) is constructed, we can obtain the following corollary.

**Corollary 3.3**.: _Let \(f^{*}\in C(\mathcal{K},\mathbb{R}^{d})(\mathcal{K}\subset\mathbb{R}^{d})\) and \(N\in\mathbb{Z}^{+}\). If for any \(\varepsilon>0\), there is an orientation preserving diffeomorphism \(\Phi\) of \(\mathbb{R}^{N}\) and two linear maps \(\alpha\) and \(\beta\) such that \(\|f^{*}(x)-\beta\circ\Phi\circ\alpha(x)\|<\varepsilon\) for all \(x\in\mathcal{K}\), then there is a leaky-ReLU network \(f_{L}\in\mathcal{N}_{N}(\sigma)\) with width \(N\) and depth \(L\) such that \(\|f_{L}(x)-f^{*}(x)\|<\varepsilon\) for all \(x\in\mathcal{K}\)._

This corollary shows the expressive power of the leaky-ReLU neural network, and it is our main result for Part 3 and Part 4, in Section 4, we will show that it holds for Part 4 (\(d_{y}\geq d_{x}+2\)) while failing for Part 3 (\(d_{y}=d_{x}+1\)).

### Proof idea of Lemma 2.4

We can prove Lemma 2.4 by designing a proper lift map. According to the lift-flow-discretization approach, we only need to construct two linear maps and an orientation preserving diffeomorphism with \(N=d+1\), which satisfies the condition of Corollary 3.3. For any continuous function \(f^{*}\in C(\mathcal{K},\mathbb{R}^{d})\) on compact domain \(\mathcal{K}\subset\mathbb{R}^{d}\), and \(\varepsilon>0\), there is a locally Lipschitz smooth function \(p\) such that \(\|f^{*}(x)-p(x)\|<\varepsilon\) for all \(x\in\mathcal{K}\). The function \(p\) can be chosen as a polynomial according to the well-known Stone-Weierstrass theorem. Then, the maps \(\alpha:\mathbb{R}^{d}\to\mathbb{R}^{d+1},\beta:\mathbb{R}^{d+1}\to\mathbb{R}^ {d}\) and \(\Phi:\mathbb{R}^{d+1}\to\mathbb{R}^{d+1}\) can be chosen as follows:

\[\alpha(x)=\begin{pmatrix}I_{d}\\ \mathbf{1}^{T}\end{pmatrix}x,\quad\Phi\begin{pmatrix}x\\ x_{d+1}\end{pmatrix}=\begin{pmatrix}p(x)+\kappa\mathbf{1}\mathbf{1}^{T}\\ x_{d+1}\end{pmatrix}, \tag{8}\] \[\beta\begin{pmatrix}x\\ x_{d+1}\end{pmatrix}=(I,-\kappa\mathbf{1})\begin{pmatrix}x\\ x_{d+1}\end{pmatrix}=x-\kappa\mathbf{1}x_{d+1}, \tag{9}\]

where \(\mathbf{1}\in\mathbb{R}^{d}\) is a column vector with all being elements one, \(\kappa\) is a number larger than the Lipschitz constant of \(p\) on \(\mathcal{K}\), and \(x_{d+1}\) is the coordinate of the auxiliary dimension. It is obvious that the maps \(\alpha\) and \(\beta\) are linear and \(p(x)=\beta\circ\Phi\circ\alpha(x)\). Our proof is constructive, and the formal proof is in appendix.

Our 'lift-flow-discretization' approach deeply connects the minimal width to topology theory, providing that the activation is a one-dimensional diffeomorphism.

## 4 Effect of the output dimension

Now we turn to Part 3 and Part 4 of the main results which consider the case of \(d_{y}\geq d_{x}+1\). We examine the approximation power of leaky-ReLU networks with width \(N=d_{y}\).

We emphasize the homeomorphism properties. In fact, leaky-ReLU, the nonsingular linear transformer and their inverse are continuous and homeomorphic. Since compositions of homeomorphism are also homeomorphism, we have the input-output map as a homeomorphism. Note that a singular matrix can be approximated by nonsingular matrixes, therefore we can restrict the weight matrix in neural networks as nonsingular.

When \(d_{y}>d_{x}\), we can reformulate the leaky-ReLU network with width \(N=d_{y}\) as \(f_{L}(x)=\psi(W_{1}x+b_{1}),W_{1}\in\mathbb{R}^{d_{x}\times d_{y}},b\in\mathbb{ R}^{d_{y}}\), where \(\psi(\cdot)\) is a homeomorphism in dimension \(d_{y}\).

### The particular dimension \(d_{y}=d_{x}+1\)

The following lemma shows that width \(N=d_{y}\) is not enough for \(C\)-UAP which implies that \(w_{\min}\geq d_{y}+1\) when \(d_{y}=d_{x}+1\).

**Lemma 4.1**.: _If \(d_{y}=d_{x}+1\), there exists a continuous function \(f^{*}(x)\in C(\mathcal{K},\mathbb{R}^{d_{y}})\) which can NOT be uniformly approximated by functions like \(\psi(W_{1}x+b_{1})\) with homeomorphism maps \(\psi:\mathbb{R}^{d_{y}}\to\mathbb{R}^{d_{y}}\)._

In order to prove this lemma, the counterexample (Figure 4(a)) we constructed seems very intuitive. In the counterexample, we need to prove that given target function \(g(t):\mathbb{R}\to\mathbb{R}^{2}\), for a sufficiently small \(\varepsilon>0\), \(h\) satisfying \(\|g(t)-h(t)\|<\varepsilon\) for any \(t\in[0,\tau]\) has a self-intersection point, we just need to prove that the curve starting from \((0,1)\) to \((0,1)\) and the curve starting from \((-1,0)\) to \((1,0)\) within \([0,1]\times[0,1]\) have at least one intersection within \([0,1]\times[0,1]\). This conclusion is so intuitive that even non-mathematics can also see at a glance that the two curves must have intersections. While the proof may seem complicated because we need knowledge of topology. Interested readers can refer to the proof in the appendix.

### The case of \(d_{y}\geq d_{x}+2\)

Note that we only need to consider the case of \(d_{y}=d_{x}+2\). The reason is that when \(d_{y}>d_{x}+2\), we can increase \(d_{x}\) by adding some auxiliary dimensions to the input. Then, employing the lift-flow-discretization approach, we only need to show that any \(f^{*}\in C(\mathcal{K},\mathbb{R}^{d_{x}+2})\) can be approximated by functions formulated as \(\psi(Wx)\), where \(\psi(\cdot)\) is an orientation preserving diffeomorphism in dimension \(d_{x}+2\).

**Lemma 4.2**.: _For any \(f^{*}\in C(\mathcal{K},\mathbb{R}^{d_{x}+2})\) and \(\varepsilon>0\), there is a matrix \(W\in\mathbb{R}^{(d_{x}+2)\times d_{x}}\) and an OP diffeomorphism map \(\Phi\) such that \(\|\Phi(Wx)-f^{*}(x)\|<\varepsilon\) for all \(x\) in \(\mathcal{K}\)._
Here, we provide the main ideas. Let \(f^{*}:I^{d}:=[0,1]^{d}\rightarrow\mathbb{R}^{d+2}\) be a continuous map. Then, let \(f^{*}\) be the locally smooth homeomorphism and the transversal intersection at all the self-intersection points. Denote the set of self-intersection points of f as \(\mathcal{A}\). We can prove that \(\mathcal{A}\) is a compactly closed subset. For \(\forall x\in\mathcal{A}\), there is an open neighborhood \(U\) of \(x\); then, we can make perturbations in \(U\) to make the maps disjoint and not create new intersections. Thus, we obtain a smooth approximation \(f\) of \(f^{*}\) without intersections, which is the desired diffeomorphism approximation.

Because \(f\) is the embedding of \(I^{d}\rightarrow\mathbb{R}^{d+2}\), it can be written as the composition of linear mapping and differential homeomorphism, which is \(f(x)=\Phi(Wx),W\in\mathbb{R}^{(d_{x}+2)\times d_{x}}\). According to the lift and flow steps, there exists a flow map \(\phi^{\tau}\in\mathcal{C}(\mathbb{R}^{d_{x}+2},\mathbb{R}^{d_{x}+2})\) satisfying \(\|\phi^{\tau}(x)-f(x)\|<\varepsilon/2\). According to the discretization step, there exists a leaky-ReLU network \(\psi\in\mathcal{C}(\mathbb{R}^{d_{x}+2},\mathbb{R}^{d_{x}+2})\) that satisfies \(\|\psi(x)-\phi^{\tau}(x)\|<\varepsilon/2\).

By employing lift-flow-discretization approach, we can arrive at the desired result. To understand the result, we show an example of the case of \(d_{y}\geq d_{x}+2\). We have shown that a continuous function \(f^{*}\) from \([0,1]^{d_{x}}\rightarrow\mathbb{R}^{d_{x}+2}\) can be uniformly approximated by a diffeomorphism, we take a '4'-shape curve corresponding to a continuous function \(f^{*}(t)\) from \([0,1]\rightarrow\mathbb{R}^{3}\) as an example.

From Figure 3, we lift the four vertices of the '4'-shape curve as \((-1,0,0),(1,0,0),(0,-1,0),(0,1,0)\), and connect them in turn to form a polyline, which is our target function \(f^{*}(t),t\in[0,1]\). Then, we construct a curve without self-intersection points by changing one of the \(z\)-axis coordinates of the points to \(\varepsilon\) (such as \(\varepsilon=0.1\)), the approximation function \(f\) is the curve connected by 4 vertices as \((-1,0,\varepsilon),(1,0,0),(0,-1,0),(0,1,0)\) in sequence, in Figure 3(b). Now the approximation function becomes a curve \(\tilde{f}(t)\) without self-intersecting points, corresponding to a homeomorphic mapping \(\Phi\) in \(\mathbb{R}^{3}\) with \(\tilde{f}(t)=\Phi(wt)\) for some \(w\in\mathbb{R}^{3}\). Employing the flow and discretization steps, we can approximate \(\Phi\) by leaky-ReLU networks. Consequently, we can conclude that the '4'-shape curve in Figure 3 can be approximated by leaky-ReLU networks.

## 5 Discussion

**General Activation**. It should be noted that our 'lift-flow-discretization' approach is generic for strictly monotone continuous activations. For example, our results are valid for strict monotone piecewise linear activations. We focus on leaky-ReLU networks mainly because 1) it is the simplest demo to prove our concept, and 2) the results of (Caponigro, 2011) and (Duan et al., 2022) allow us to finish the 'flow' and 'discretization' steps easily.

We also note that our result may not hold for ReLU networks as the ReLU function is not invertible. ReLU networks can be regarded as the limits of leaky-ReLU networks with parameter \(\alpha\) tending to \(0\). However, in our construction, some weights of the network are \(O(1/\alpha)\), which tend to \(\infty\) as \(\alpha\to 0\). This suggests that the narrow ReLU and leaky-ReLU networks are different. How to rediscuss these issues under the ReLU network, and show the differences between the two more clearly, maybe a very interesting topic.

\(L^{p}\)**-UAP and \(C\)-UAP**. Leaky-ReLU activation has been studied by (Duan et al., 2022) and (Cai, 2022) to connect neural ODEs, flow maps, and the minimum width of neural networks. However, the previous results are for the UAP under the \(L^{p}\) norm, which simplified the analysis because the diffeomorphisms are \(L^{p}\) approximations of maps (Brenier and Gangbo, 2003). Our 'lift-flow-discretization' approach can deeply connect the minimal width to the topology theory, properly lift the target function to higher dimensions and employ facts from topology theory to further obtain sharp bounds of width for the uniform/\(C\)-UAP.

**Approximation rate**. Determining the number of weights or layers to achieve \(\varepsilon\) approximation error is related to the approximation rate or the error-bound problems. Estimating the error bound of all three steps in our lift-flow-discretization approach is challenging since the error in the 'flow' step is hard to estimate. This may need to establish new construction tools. We leave it as future work.

## Acknowledgments

We are grateful to Mr. Ziyi Lei for the helpful discussion on the proof of Lemma 4.2. We are also grateful to the anonymous reviewers for their useful comments and suggestions. This work was supported by the National Natural Science Foundation of China (Grant No. 12201053) and the National Natural Science Foundation of China (Grant No. 11871105).

Figure 3: Example of \(d_{x}=1\). Approximate the ‘4’-shape curve (a) in \(\mathbb{R}^{2}\) by lifting it to the three-dimensional curve (b) in \(\mathbb{R}^{3}\).