ReLU Network with Bounded Width Is a Universal Approximator in View of an Approximate Identity

Abstract

Deep neural networks have shown very successful performance in a wide range of tasks, but a theory of why they work so well is in the early stage. Recently, the expressive power of neural networks, important for understanding deep learning, has received considerable attention. Classic results, provided by Cybenko, Barron, etc., state that a network with a single hidden layer and suitable activation functions is a universal approximator. A few years ago, one started to study how width affects the expressiveness of neural networks, i.e., a universal approximation theorem for a deep neural network with a Rectified Linear Unit (ReLU) activation function and bounded width. Here, we show how any continuous function on a compact set of ${\mathbb{R}}^{n_{in}},n_{in}\in \mathbb{N}$ can be approximated by a ReLU network having hidden layers with at most $n_{in}+5$ nodes in view of an approximate identity.

1. Introduction

Over the past several years, deep neural networks have achieved state-of-the-art performance in a wide range of tasks such as image recognition/segmentation and machine translation (see the review article [1] and recent book [2] for more background). In spite of their outstanding successes, many aspects of why they work so well are still not well understood. Some works to date have focused on the problem of explaining and quantifying the expressivity of a deep neural network [3,4,5].

This line of research about the expressive power of neural networks, its ability to approximate functions, dates back to at least the work of Cybenko [6], in which a fully connected neural network with a sigmoid activation function and one single hidden layer can approximate any continuous univariate function on a bounded domain with an arbitrarily small error. Barron [7], Hornik et al. [8], and Funahashi [9] generalized the sigmoid function to a large class of activation functions to get universal approximation. However, they do not consider the number of nodes of a hidden layer; actually, the number of nodes of a hidden layer can be exponentially increased in the input dimension.

Because the outstanding performance of deep neural networks has recently been exhibited, there is a lot of literature concerning their expressive power theoretically. In 2011, Delalleau and Bengio [10] gave a family of functions which can be represented much more efficiently with a deep network than with a neural network with one hidden layer. Mhaskar and Poggio [4] provided conditions under which deep convolutional neural networks perform much better in function approximation than a neural network with one hidden layer. Eldan and Shamir [11] constructed a three-layer network which cannot be realized by any 2-layer if the number of nodes of an output layer is no more than an exponential bound.

Actually, the Rectified Linear Units (ReLU) activation function is the most popular choice in practical use of the neural network [12]. In this reason, most of the recent results on the universal approximation theory is about the ReLU network [5,13,14,15,16,17,18,19,20]. Cohen et al. [13] provided the deep convolutional neural network with the ReLU activation function that cannot be realized by a shallow network if the number of nodes of its hidden layer is no more than an exponential bound.

Lu et al. [14] presented a universal approximation theorem for deep neural networks with ReLU activation functions and hidden layers with a bounded width in 2017, since the expressive power of depth in ReLU networks with a bounded width has received a lot of attention. Hanin proved universal approximation theorem using convex function theory in [15,16], and Lin and Jegelka showed this theorem for residual networks with one-neuron hidden layers in [19].

Ohn and Kim [18] showed that the ReLU activation function can be represented by a linear combination of piecewise linear activation function and, using this fact, extended many results in [5,17,20] to any continuous piecewise linear activation function. However, their results are not about the bounded width.

Here, we study a universal approximation theorem for ReLU networks in view of approximate identity by constructing a network having $n_{in}{k}^{n_{in}}+1$ hidden layers with width of at most $n_{in}+5$. As a measure of approximation error, we adopt the supremum norm and $L^p$ distance.

The remainder of the paper is organized as follows: in the next subsection, we introduce some notations. Section 2 and Section 3 are devoted to our theorem statement and its proof, respectively. Finally, Section 4 offers a conclusion.

Notations

Let ${\mathbb{Z}}_k=\{1,2,\cdots ,k\}$ and $\mathbf{x}=(x_1,x_2,\cdots ,x_n)\in {\mathbb{R}}^n$ be the input. The network architecture $(l,\mathbf{n})$ consists of several hidden layers $l\in \mathbb{N}$ and a width vector $\mathbf{n}=(n_0,n_1,\cdots ,n_{l+1})\in {\mathbb{N}}^{l+2},n_0=n_{in}$ [20]. A neural network with network architecture $(l,\mathbf{n})$ is then any function of the form

$$\begin{array}{c}{f}_{(l,\mathbf{n})}:{\mathbb{R}}^{n_0}\to {\mathbb{R}}^{n_{l+1}},\hfill \\ f_{(l,\mathbf{n})}\left(\mathbf{x}\right)=L^{l+1}\circ ReLU\circ L^l\circ ReLU\circ \cdots \circ L^2\circ ReLU\circ L^1\left(\mathbf{x}\right),\hfill \end{array}$$

where

$$\begin{array}{c}{L}^i:{\mathbb{R}}^{n_{i-1}}\to {\mathbb{R}}^{n_i}i=1,\cdots ,l+1,\hfill \end{array}$$

and $ReLU\left(x\right)=max\{x,0\}$,

$$\begin{array}{c}ReLU(x_1,x_2,\cdots ,x_m)=(ReLU\left(x_1\right),ReLU\left(x_2\right),\cdots ,ReLU\left(x_m\right)).\hfill \end{array}$$

Here, we set $n_{l+1}=1$. To this end, we define the space of network functions with the given network architecture

$$\mathcal{F}(l,\mathbf{n}):=\{f_{(l,\mathbf{n})}:f_{(l,\mathbf{n})}\left(\mathbf{x}\right)=L^{l+1}\circ \cdots \circ ReLU\circ L^1\left(\mathbf{x}\right),(l,\mathbf{n})\in \mathbb{N}\times {\mathbb{N}}^{l+2}\}.$$

Our network of interest is ‘a feedforward neural network’ which is an artificial neural network wherein connections between the nodes do not form a cycle. That is, in this network, the information moves in a forward direction, from the input nodes to the output nodes through the hidden nodes (if any).

For later discussion, we introduce the positive part $f_{+}=max(f,0)$ and negative parts $f_{-}=max(-f,0)$ of a function f. Then, $f_{+}-f_{-}$ is equal to f.

2. Main Result

Here is our universal approximation theorem for a ReLU network with a bounded width:

Theorem 1.

For any $M>0$ and $n_{in}\in \mathbb{N}$, let $f:{[-M,M]}^{n_{in}}\to \mathbb{R}$ be a continuous function. For $ϵ>0$, there exists $k\in \mathbb{N}$ such that $f_{(l,\mathbf{n})}\in \mathcal{F}(n_{in}{k}^{n_{in}}+1,n_{in},n_{in}+5,\cdots ,n_{in}+5,2,1)$ satisfies

$$\underset{\mathbf{x}\in {[-M,M]}^n}{sup}|f\left(\mathbf{x}\right)-f_{(l,\mathbf{n})}\left(\mathbf{x}\right)|<ϵ.$$

To prove this theorem, we explicitly construct a ReLU network with a bounded width in Section 3.2. In our construction, each of the first $n_{in}+3$ nodes in each hidden layer is connected to only one node of the previous layer, and each, only for two $n_{in}+4$ and $n_{in}+5$ nodes in each hidden layer, is connected to less than four nodes of the previous layer (for more details, see Section 3.2). This means that the non-fully connected ReLU network can be working.

We can show that there is a feed-forward neural network that approximates any $f\in L^p\left({\mathbb{R}}^{n_{in}}\right)$:

Corollary 1.

Let $n_{in}\in \mathbb{N}$ and $f\in L^p\left({\mathbb{R}}^{n_{in}}\right),1\le p<\infty$. For $ϵ>0$, there exists $k\in \mathbb{N}$ such that $f_{(l,\mathbf{n})}\in \mathcal{F}(n_{in}{k}^{n_{in}}+1,n_{in},n_{in}+5,\cdots ,n_{in}+5,2,1)$ satisfies

$$\left|\right|f\left(\mathbf{x}\right)-f_{(l,\mathbf{n})}\left(\mathbf{x}\right){\left|\right|}_p<ϵ.$$

Proof. 

For any $ϵ>0$, there is a continuous function $f_c$ on ${\mathbb{R}}^{n_{in}}$ with compact support in ${[-M,M]}^{n_{in}}$ such that

$$\underset{{\mathbb{R}}^{n_{in}}}{\int }{|f\left(\mathbf{x}\right)-f_c\left(\mathbf{x}\right)|}^p\mathrm{d}\mathbf{x}<\frac{{ϵ}^p}{2^p}.$$

Using Theorem 1, we can find $k\in \mathbb{N}$ such that a ReLU neural network architecture $(l,\mathbf{n})$ with a represented function $f_{(l,\mathbf{n})}$ satisfying

$$\underset{\mathbf{x}\in {[-M,M]}^{n_{in}}}{sup}|f_c\left(\mathbf{x}\right)-f_{(l,\mathbf{n})}\left(\mathbf{x}\right)|<\frac{ϵ}{2^{n_{in}+1}{M}^{n_{in}}}.$$

Therefore, we have

$$\left|\right|f\left(\mathbf{x}\right)-f_{(l,\mathbf{n})}{\left(\mathbf{x}\right)\left|\right|}_p\le \left|\right|f\left(\mathbf{x}\right)-f_c{\left(\mathbf{x}\right)\left|\right|}_p+\left|\right|f_c\left(\mathbf{x}\right)-f_{(l,\mathbf{n})}\left(\mathbf{x}\right){\left|\right|}_p<ϵ.$$

□

3. Proof of Theorem 1

To convey our idea more clearly, we first construct a ReLU network with $n_{in}=1$ and $k+1$ hidden layers with width at most 6. Then, we construct a ReLU network with general $n_{in}$.

3.1. One-Dimensional, Input

Let $L^{1,temp}:\mathbb{R}\to {\mathbb{R}}^3$ and $L^{2,temp}:{\mathbb{R}}^3\to \mathbb{R}$ with $L^{1,temp}\left(x\right)=(x-1,x,x+1)$ and $L^{2,temp}(x_1,x_2,x_3)=x_1-2x_2+x_3$. Then, the function $f_{(1,1,3,1)}$ represented by $L^{2,temp}\circ ReLU\circ L^{1,temp}$ is

$$\begin{array}{cc}{f}_{(1,1,3,1)}\left(\mathbf{x}\right)\hfill & =L^{2,temp}\circ ReLU\circ L^{1,temp}\left(x\right)\hfill \\ & =ReLU(x-1)-2ReLU\left(x\right)+ReLU(x+1)\hfill \\ & =\left\{\begin{array}{cc}0\hfill & \mathrm{if}\left|x\right|>1,\hfill \\ 1-\left|x\right|\hfill & \mathrm{if}-1<x<1.\hfill \end{array}\right.\hfill \end{array}$$

We notice that, for a (B-spline) function $g\left(x\right)=L^{2,temp}\circ ReLU\circ L^{1,temp}\left(x\right)$ and $\lambda >0$, $g_{\lambda }\left(x\right)={\lambda }^{-1}g\left({\lambda }^{-1}x\right)$ is an approximate identity: for any continuous function $f\left(x\right)$ on $[-M,M]$, $f\ast g_{\lambda }$ converges to $f\left(x\right)$ uniformly. For any $ϵ>0$, there is $\lambda >0$ such that ${sup}_{-M\le x\le M}|f\ast g_{\lambda }\left(x\right)-f\left(x\right)|<ϵ/2.$ By mensuration by division, there is $k\in \mathbb{N}$ such that

$${\displaystyle \underset{-M\le x\le M}{sup}\left|\begin{array}{c}\hfill {\displaystyle f\ast g_{\lambda }\left(x\right)-\sum _{j=1}^k\frac{2M}{k}f\left(-M+\frac{2Mj}{k}\right)g_{\lambda }\left(x-\left(-M+\frac{2Mj}{k}\right)\right)}\end{array}\right|<ϵ/2}$$

and thus

$${\displaystyle \underset{-M\le x\le M}{sup}\left|\begin{array}{c}\hfill {\displaystyle f\left(x\right)-\sum _{j=1}^k\frac{2M}{k}f\left(-M+\frac{2Mj}{k}\right)g_{\lambda }\left(x-\left(-M+\frac{2Mj}{k}\right)\right)}\end{array}\right|<ϵ.}$$

Now, for a fixed $k\in \mathbb{N}$, we can make a network architecture $(l,\mathbf{n})=(k+1,1,6,6,\cdots ,6,2,1)$ with ReLU activations, input, and output dimensions 1, and $k+1$ hidden layer width at most 6, such that

$$\underset{-M\le x\le M}{sup}\left|f\left(x\right)-f_{(l,\mathbf{n})}\left(x\right)\right|<ϵ.$$

Let $L^{1,1}:\mathbb{R}\to {\mathbb{R}}^6$, $L^{1,j}:{\mathbb{R}}^6\to {\mathbb{R}}^6,j=2,\cdots ,k$, $L^{k+1}:{\mathbb{R}}^6\to {\mathbb{R}}^2$, and $L^{k+2}:{\mathbb{R}}^2\to \mathbb{R}$ with

$$\begin{array}{c}{L}^{1,1}\left(x\right)=\left(\begin{array}{c}x+M\hfill \\ {\lambda }^{-1}(x-(-M+2M/k))-1\hfill \\ {\lambda }^{-1}(x-(-M+2M/k))\hfill \\ {\lambda }^{-1}(x-(-M+2M/k))+1\hfill \\ 0\hfill \\ 0\hfill \end{array}\right),\hfill \\ L^{1,j}\left(\mathbf{x}\right)=\left(\begin{array}{c}{\displaystyle x_1}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2Mj}{k}))-1}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2Mj}{k}))}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2Mj}{k}))+1}\hfill \\ {\displaystyle x_5+\frac{2M}{k\lambda }{f}_{+}(-M+\frac{2M(j-1)}{k})(x_2-2x_3+x_4)}\hfill \\ {\displaystyle x_6+\frac{2M}{k\lambda }{f}_{-}(-M+\frac{2M(j-1)}{k})(x_2-2x_3+x_4)}\hfill \end{array}\right)\mathrm{for}j=2,\cdots ,k,\hfill \\ L^{k+1}\left(\mathbf{x}\right)=\left(\begin{array}{c}{\displaystyle x_5+\frac{M}{k\lambda }{f}_{+}\left(M\right)(x_2-2x_3+x_4)}\hfill \\ {\displaystyle x_6+\frac{M}{k\lambda }{f}_{-}\left(M\right)(x_2-2x_3+x_4)}\hfill \end{array}\right),\mathrm{and}\hfill \\ {\displaystyle L^{k+2}\left(\mathbf{x}\right)=(x_1-x_2).}\hfill \end{array}$$

(The index 1 in our index $(1,j)$ is unnecessary, but it is included because it suggests how to generalize to input of arbitrary dimension.) We note that

$$\begin{array}{c}{L}^{1,2}\circ ReLU\circ L^{1,1}\left(x\right)=\left(\begin{array}{c}{\displaystyle x+M}\hfill \\ {\displaystyle {\lambda }^{-1}(x-(-M+\frac{2M}{k}))-1}\hfill \\ {\displaystyle {\lambda }^{-1}(x-(-M+\frac{2M}{k}))}\hfill \\ {\displaystyle {\lambda }^{-1}(x-(-M+\frac{2M}{k}))+1}\hfill \\ {\displaystyle \frac{2M}{k\lambda }{f}_{+}(-M+\frac{2M}{k})g({\lambda }^{-1}x-{\lambda }^{-1}(-M+\frac{2M}{k}))}\hfill \\ {\displaystyle \frac{2M}{k\lambda }{f}_{-}(-M+\frac{2M}{k})g({\lambda }^{-1}x-{\lambda }^{-1}(-M+\frac{2M}{k}))}\hfill \end{array}\right).\hfill \end{array}$$

and the fifth and sixth components of $L^{1,j}$ are non-negative. Since for a non-negative function $h:\mathbb{R}\to \mathbb{R}$, $ReLU\left(h\right)=h$, we have for $\alpha \ge 0$,

$$\begin{array}{c}\hfill ReLU\left(h\left(x\right)+\alpha g_{\lambda }\left(x-\left(-M+\frac{2Mj}{k}\right)\right)\right)=h\left(x\right)+\alpha g_{\lambda }\left(x-\left(-M+\frac{2Mj}{k}\right)\right)\end{array}$$

and thus (inductively) we have

$$\begin{array}{cc}\hfill & L^{k+2}\circ \cdots \circ ReLU\circ L^{1,1}\left(x\right)\hfill \\ \hfill & {\displaystyle =\sum _{j=1}^k\frac{2M}{k}{f}_{+}\left(-M+\frac{2Mj}{k}\right)g_{\lambda }\left(x-\left(-M+\frac{2Mj}{k}\right)\right)}\hfill \\ \hfill & {\displaystyle -\sum _{j=1}^k\frac{2M}{k}{f}_{-}\left(-M+\frac{2Mj}{k}\right)g_{\lambda }\left(x-\left(-M+\frac{2Mj}{k}\right)\right)}\hfill \\ \hfill & {\displaystyle =\sum _{j=1}^k\frac{2M}{k}f\left(-M+\frac{2Mj}{k}\right)g_{\lambda }\left(x-\left(-M+\frac{2Mj}{k}\right)\right).}\hfill \end{array}$$

3.2. General-Dimensional Input

To generalize our idea on input dimension 1 to general input dimension $n_{in}$, the main difficult part is how to make a ReLU network an approximate identity, for example, a kind of a B-spline function on ${\mathbb{R}}^2$. We emphasize that we need a function with the shape of a B-spline function, not an exact B-spline function on ${\mathbb{R}}^2$ (see Figure 1). For $n=2$, we have

$$\begin{array}{c}ReLU(x_2+(ReLU(x_1+1)-2ReLU\left(x_1\right)+ReLU(x_1-1)))-2ReLU\left(x_2\right)\hfill \\ +ReLU(x_2-(ReLU(x_1+1)-2ReLU\left(x_1\right)+ReLU(x_1-1)))\hfill \\ =\left\{\begin{array}{cc}0\hfill & \mathrm{if}|x_1|+|x_2|>1\hfill \\ 1-|x_1|-|x_2|\hfill & \mathrm{if}|x_1|+|x_2|<1.\hfill \end{array}\right.\hfill \end{array}$$

In general,

Lemma 1.

For $b\in \mathbb{R}$, let $h(x_1,b)=ReLU(x_1+b)-2ReLU\left(x_1\right)+ReLU(x_1-b)$. Then, we have

$$\begin{array}{c}h(x_n,h(x_{n-1},h(x_{n-2},\cdots ,h(x_1,1))))=\left\{\begin{array}{cc}0\hfill & {\displaystyle if\sum _{j=1}^n\left|x_j\right|\ge 1,}\hfill \\ {\displaystyle 1-\sum _{j=1}^n\left|x_j\right|}\hfill & {\displaystyle if\sum _{j=1}^n\left|x_j\right|<1.}\hfill \end{array}\right.\hfill \end{array}$$

In addition, we have

$$\underset{{\mathbb{R}}^n}{\int }h(x_n,h(x_{n-1},h(x_{n-2},\cdots ,h(x_1,1))))\mathrm{d}\mathbf{x}=\frac{2^n}{(n+1)!}.$$

(1)

We notice that for

$$g\left(\mathbf{x}\right)=h(x_n,h(x_{n-1},h(x_{n-2},\cdots ,h(x_1,1)))),\mathbf{x}\in {\mathbb{R}}^n$$

(see Figure 1) and $\frac{(n+1)!}{2^n}{g}_{\lambda }\left(\mathbf{x}\right)=\frac{(n+1)!}{2^n{\lambda }^n}g\left({\lambda }^{-1}\mathbf{x}\right)$, $\lambda >0$ is an approximate identity: for a continuous function f on ${[-M,M]}^n$, $\frac{(n+1)!}{2^n}f\ast g_{\lambda }$ converges to $f\left(\mathbf{x}\right)$ uniformly. For any $ϵ>0$, there is $\lambda >0$ such that

$$\underset{\mathbf{x}\in {[-M,M]}^{n_{in}}}{sup}\left|\frac{(n+1)!}{2^n}f\ast g_{\lambda }\left(\mathbf{x}\right)-f\left(\mathbf{x}\right)\right|<\frac{ϵ}{2}.$$

(2)

Proof. 

We will use mathematical induction on n. We have already shown the case of $n=1$. Suppose

$$\begin{array}{c}h(x_n,h(x_{n-1},\cdots ,h(x_1,1)))=\left\{\begin{array}{cc}0\hfill & {\displaystyle \mathrm{if}\sum _{j=1}^n\left|x_j\right|\ge 1,}\hfill \\ {\displaystyle 1-\sum _{j=1}^n\left|x_j\right|}\hfill & {\displaystyle \mathrm{if}\sum _{j=1}^n\left|x_j\right|<1.}\hfill \end{array}\right.\hfill \end{array}$$

For simplicity, let $g\left(\mathbf{x}\right)=h(x_n,h(x_{n-1},\cdots ,h(x_1,1)))$, $\mathbf{x}\in {\mathbb{R}}^n$. If ${\sum }_{j=1}^{n+1}\left|x_j\right|\ge 1$, then $|x_{n+1}|\ge 1-{\sum }_{j=1}^n\left|x_j\right|$ and thus $|x_{n+1}|\ge g\left(\mathbf{x}\right)$. For $x_{n+1}\ge 0$,

$$\begin{array}{cc}h(x_{n+1},g\left(\mathbf{x}\right))\hfill & =ReLU(x_{n+1}+g\left(\mathbf{x}\right))-2ReLU\left(x_{n+1}\right)+ReLU(x_{n+1}-g\left(\mathbf{x}\right))\hfill \\ & =(x_{n+1}+g\left(\mathbf{x}\right))-2x_{n+1}+(x_{n+1}-g\left(\mathbf{x}\right))\hfill \end{array}$$

is equal to zero. In addition, for $x_{n+1}<0$, we can show that $h(x_{n+1},g\left(\mathbf{x}\right))$ is also zero. Now, we consider ${\sum }_{j=1}^{n+1}\left|x_j\right|<1$. Then, by hypothesis, $g\left(\mathbf{x}\right)=1-{\sum }_{j=1}^n\left|x_j\right|$. For $x_{n+1}>0$, we have

$$\begin{array}{cc}\hfill h(x_{n+1},g\left(\mathbf{x}\right))& {\displaystyle =ReLU(x_{n+1}+g\left(\mathbf{x}\right))-2ReLU\left(x_{n+1}\right)+ReLU(x_{n+1}-g\left(\mathbf{x}\right))}\hfill \\ \hfill & {\displaystyle =x_{n+1}+1-\sum _{j=1}^n|x_j|-2x_{n+1}=1-\sum _{j=1}^{n+1}\left|x_j\right|,}\hfill \end{array}$$

since $x_{n+1}-1+{\sum }_{j=1}^n\left|x_j\right|<0$. Similarly, for $x_{n+1}<0$, we have

$$\begin{array}{c}{\displaystyle h(x_{n+1},g\left(\mathbf{x}\right))=x_{n+1}+1-\sum _{j=1}^n|x_j|=1-\sum _{j=1}^{n+1}\left|x_j\right|.}\hfill \end{array}$$

Direct integral calculation follows (1). □

Again, similar to the one-dimensional case, by mensuration by division, there is $k\in \mathbb{N}$ such that

$$\underset{\mathbf{x}\in {[-M,M]}^{n_{in}}}{sup}\left|\begin{array}{c}\hfill {\displaystyle \frac{(n_{in}+1)!}{2^{n_{in}}}f\ast g_{\lambda }\left(\mathbf{x}\right)-\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}}\sum _{\mathbf{j}\in {\mathbb{Z}}_k^{n_{in}}}f\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)}\\ \hfill {\displaystyle \times g_{\lambda }\left(\mathbf{x}-\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right)}\end{array}\right|<\frac{ϵ}{2}$$

and thus, with (2), we have for some $\lambda >0\mathrm{and}k\in \mathbb{N}$,

$$\left|\begin{array}{c}\hfill {\displaystyle f\left(\mathbf{x}\right)-\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}}\sum _{\mathbf{j}\in {\mathbb{Z}}_k^{n_{in}}}f\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)}\\ \hfill {\displaystyle \times g_{\lambda }\left(\mathbf{x}-\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right)}\end{array}\right|<ϵ.$$

Now, our goal is to construct a ReLU network satisfying

$$\begin{array}{c}{f}_{(l,\mathbf{n})}\left(\mathbf{x}\right)\hfill \\ {\displaystyle =\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}}\sum _{\mathbf{j}\in {\mathbb{Z}}_k^{n_{in}}}f\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)g_{\lambda }\left(\mathbf{x}-\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right).}\hfill \end{array}$$

Since we have an approximate identity $\frac{(n_{in}+1)!}{2^{n_{in}}}g$, how to make the ReLU network remains. Here, the indexing part is not difficult, but it is slightly cumbersome. Similarly to the case $n_{in}=1$, for

$$\begin{array}{c}(i,\mathbf{j})=(i,j_1,j_2,\cdots ,j_{n_{in}})\in {\{1,\cdots ,n_{in}\}}^{}\times {\mathbb{Z}}_k^{n_{in}}\setminus \left\{(1,1,\cdots ,1)\right\}\hfill \end{array}$$

(i index for dimension and $\mathbf{j}$ index for mensuration by division), let

$$\begin{array}{cc}\hfill & L^{1,\cdots ,1}:{\mathbb{R}}^{n_{in}}\to {\mathbb{R}}^{n_{in}+5},L^{i,\mathbf{j}}:{\mathbb{R}}^{n_{in}+5}\to {\mathbb{R}}^{n_{in}+5},\hfill \\ \hfill & L^{n_{in}{k}^{n_{in}}+1}:{\mathbb{R}}^{n_{in}+5}\to {\mathbb{R}}^2,and{L}^{n_{in}{k}^{n_{in}}+2}:{\mathbb{R}}^2\to \mathbb{R}\hfill \end{array}$$

with

$$\begin{array}{c}{L}^{1,1,\cdots ,1}\left(\mathbf{x}\right)=\left(\begin{array}{c}{x}_1+M\hfill \\ x_2+M\hfill \\ ⋮\hfill \\ x_{n_{in}}+M\hfill \\ {\lambda }^{-1}(x_1-(-M+2M/k))-1\hfill \\ {\lambda }^{-1}(x_1-(-(M+2M/k))\hfill \\ {\lambda }^{-1}(x_1-(-(M+2M/k))+1\hfill \\ 0\hfill \\ 0\hfill \end{array}\right),\hfill \end{array}$$

$$\begin{array}{c}{L}^{i,\mathbf{j}}\left(\mathbf{x}\right)=\left(\begin{array}{c}{x}_1\hfill \\ ⋮\hfill \\ x_{n_{in}}\hfill \\ {\displaystyle {\lambda }^{-1}(x_i-M-(-M+2M{j}_i/k))-(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \\ {\displaystyle {\lambda }^{-1}(x_i-M-(-M+2M{j}_i/k))}\hfill \\ {\displaystyle {\lambda }^{-1}(x_i-M-(-M+2M{j}_i/k))+(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \\ x_{n_{in}+4}\hfill \\ x_{n_{in}+5}\hfill \end{array}\right)\hfill \\ \mathrm{for}i=2,\cdots ,n_{in},\hfill \end{array}$$

$$\begin{array}{c}{L}^{1,\mathbf{j}}\left(\mathbf{x}\right)=\left(\begin{array}{c}{x}_1\hfill \\ ⋮\hfill \\ x_{n_{in}}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2M{j}_1}{k}))-(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2M{j}_1}{k}))}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2M{j}_1}{k}))+(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \\ {\displaystyle x_{n_{in}+4}+\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{+}\left(-(M,\cdots ,M)+\frac{2M(\mathbf{j}-{\mathbf{1}}_{\mathbf{j}})}{k}\right)}\hfill \\ {\displaystyle \times (x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3}))}\hfill \\ {\displaystyle x_{n_{in}+5}+\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{-}\left(-(M,\cdots ,M)+\frac{2M(\mathbf{j}-{\mathbf{1}}_{\mathbf{j}})}{k}\right)}\hfill \\ {\displaystyle \times (x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \end{array}\right),\hfill \\ (\mathbf{j}\ne (1,1,\cdots ,1\left)\right)\hfill \end{array}$$

$$\begin{array}{c}{L}^{n_{in}{k}^{n_{in}}+1}\left(\mathbf{x}\right)\hfill \\ =\left(\begin{array}{c}{\displaystyle x_{n_{in}+4}+\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{+}(M,\cdots ,M)(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \\ {\displaystyle x_{n_{in}+5}+\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{-}(M,\cdots ,M)(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \end{array}\right),\hfill \\ \mathrm{and}{L}^{n_{in}{k}^{n_{in}}+2}\left(\mathbf{x}\right)=(x_1-x_2).\hfill \end{array}$$

Here,

$$\begin{array}{c}{1}_j=\left\{\begin{array}{cc}(1,0,\cdots ,0)\hfill & \mathrm{if}{j}_1\ne 1,\hfill \\ (k-1,1,0\cdots ,0)\hfill & \mathrm{if}{j}_1=1\mathrm{and}{j}_2\ne 1,\hfill \\ ⋮\hfill \\ (k-1,k-1,\cdots ,k-1,\underset{l+1-th}{\underline{1}},0,\cdots ,0)\hfill & \mathrm{if}{j}_1=j_2=\cdots =j_l=1\mathrm{and}{j}_{l+1}\ne 1,\hfill \\ ⋮\hfill \\ (k-1,k-1,\cdots ,k-1,1)\hfill & \mathrm{if}{j}_1=\cdots =j_{n_{in}-1}=1\mathrm{and}{j}_{n_{in}}\ne 1.\hfill \end{array}\right.\hfill \end{array}$$

.

We stack in such a way that the index i is increased, and then the second index $j_1$ is increased, and then $j_2$, and so on:

$$\begin{array}{cccc}(1,1,1,\cdots ,1),(2,1,1,\cdots ,1),\hfill & (3,1,1,\cdots ,1),& \hfill \cdots ,& \hfill (n_{in},1,1,\cdots ,1),\\ (1,2,1,\cdots ,1),(2,2,1,\cdots ,1),\hfill & & \hfill \cdots ,& \hfill (n_{in},2,1,\cdots ,1),\\ & ⋮\\ (1,k,1,\cdots ,1),\hfill & & \hfill \cdots ,& \hfill (n_{in},k,1,\cdots ,1),\\ (1,1,2,1\cdots ,1),\hfill & & \hfill \cdots ,& \hfill (n_{in},1,2,1\cdots ,1),\\ & ⋮\\ (1,k,2,1,\cdots ,1),\hfill & & \hfill \cdots ,& \hfill (n_{in},k,2,1,\cdots ,1),\\ (1,1,3,1,\cdots ,1),\hfill & & \hfill \cdots ,& \hfill (n_{in},1,3,1,\cdots ,1),\\ & ⋮\\ (1,k,k,1,\cdots ,1),\hfill & & \hfill \cdots ,& \hfill (n_{in},k,k,1,\cdots ,1),\\ (1,1,1,2,1\cdots ,1),\hfill & & \hfill \cdots ,& \hfill (n_{in},1,1,2,1\cdots ,1),\\ & ⋮\\ (1,k-1,k,k,k\cdots ,k),\hfill & & \hfill \cdots ,& \hfill (n_{in},k-1,k,k,k\cdots ,k),\\ (1,k,k,k,k\cdots ,k),\hfill & & \hfill \cdots ,& \hfill (n_{in},k,k,k,k\cdots ,k)\end{array}$$

(which means that the index i is the first one where we increase) and, if we omit the index i, then

$$\begin{array}{cccc}(1,1,1,\cdots ,1),\hfill & (2,1,1,\cdots ,1),& \hfill (3,1,1,\cdots ,1),\cdots ,& \hfill (k,1,1,\cdots ,1),\\ (1,2,1,\cdots ,1),\hfill & (2,2,1,\cdots ,1),& \hfill \cdots ,& \hfill (k,2,1,\cdots ,1),\\ \hfill & ⋮\\ (1,k,1,\cdots ,1),\hfill & (2,k,1,\cdots ,1),& \hfill \cdots ,(k-1,k,1,\cdots ,1),& \hfill (k,k,1,\cdots ,1),\\ (1,1,2,\cdots ,1),\hfill & (2,1,2,\cdots ,1),& \hfill \cdots ,(k-1,1,2,\cdots ,1),& \hfill (k,1,2,\cdots ,1),\\ \hfill & ⋮\\ (1,k,\cdots ,k,k-1,k),\hfill & \cdots ,& \hfill (k-1,k,\cdots ,k-1,k),& \hfill (k,\cdots ,k-1,k),\\ (1,k,k\cdots ,k,k),\hfill & \cdots ,& \hfill (k-1,k,k,\cdots ,k,k),& \hfill (k,k\cdots ,k,k).\end{array}$$

(3)

In the second terms of the $n_{in}+4$ and $n_{in}+5$-th components of $L^{1,\mathbf{j}},$ $\mathbf{j}\ne (1,1,\cdots ,1)$

$$f_{\pm }\left(-(M,\cdots ,M)+\frac{2M(\mathbf{j}-{\mathbf{1}}_{\mathbf{j}})}{k}\right)(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3}),$$

we want the value at the previous step and thus $\mathbf{j}-{\mathbf{1}}_{\mathbf{j}}$ is the exact previous one step of $\mathbf{j}$.

We want to notice the $n_{in}+1$, $n_{in}+2$, and $n_{in}+3$-th components of a function $f_{1,n_{in},n_{in}+5,n_{in}+5}\left(\mathbf{x}\right)$ represented by $L^{2,1,1,\cdots ,1}\circ ReLU\circ L^{1,1,1,\cdots ,1}\left(\mathbf{x}\right)$ are

$$\begin{array}{c}{\displaystyle {\lambda }^{-1}\left(x_2-M-\left(-M+\frac{2M}{k}\right)\right)-h\left({\lambda }^{-1}\left(x_1-\left(-M+\frac{2M}{k}\right)\right),1\right)}\hfill \\ {\displaystyle {\lambda }^{-1}\left(x_2-M-\left(-M+\frac{2M}{k}\right)\right)}\hfill \\ {\displaystyle {\lambda }^{-1}\left(x_2-M-\left(-M+\frac{2M}{k}\right)\right)+h\left({\lambda }^{-1}\left(x_1-\left(-M+\frac{2M}{k}\right)\right),1\right),}\hfill \end{array}$$

and thus $n_{in}+1$, $n_{in}+2$, and $n_{in}+3$-th components of a function $f_{2,n_{in},n_{in}+5,n_{in}+5,n_{in}+5}\left(\mathbf{x}\right)$ becomes

$$\begin{array}{c}{\displaystyle {\lambda }^{-1}\left(x_3-M-\left(-M+\frac{2M}{k}\right)\right)-\overline{g}\left({\lambda }^{-1}\left((x_1,x_2)-\left(-(M,M)+\frac{2M(1,1)}{k}\right)\right)\right)}\hfill \\ {\displaystyle {\lambda }^{-1}\left(x_3-M-\left(-M+\frac{2M}{k}\right)\right)}\hfill \\ {\displaystyle {\lambda }^{-1}\left(x_3-M-\left(-M+\frac{2M}{k}\right)\right)+\overline{g}\left({\lambda }^{-1}\left((x_1,x_2)-\left(-(M,M)+\frac{2M(1,1)}{k}\right)\right)\right),}\hfill \end{array}$$

where $\overline{g}(x_1,x_2)=h(x_2,h(x_1,1))$. Thus, a function $f_{n_{in},n_{in},n_{in}+5,\cdots ,n_{in}+5}\left(\mathbf{x}\right)$ represented by $L^{1,2,1,\cdots ,1}\circ \cdots \circ ReLU\circ L^{1,1,\cdots ,1}\left(\mathbf{x}\right)$ is equal to

$$\left(\begin{array}{c}{x}_1+M\hfill \\ ⋮\hfill \\ x_{n_{in}}+M\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2M}{k}))-(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2M}{k}))}\hfill \\ {\displaystyle {\lambda }^{-1}(x_1-M-(-M+\frac{2M}{k}))+(x_{n_{in}+1}-2x_{n_{in}+2}+x_{n_{in}+3})}\hfill \\ {\displaystyle \frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{+}\left(-(M,\cdots ,M)+\frac{2M(1,\cdots ,1)}{k}\right)}\hfill \\ {\displaystyle \times g\left({\lambda }^{-1}\mathbf{x}-{\lambda }^{-1}\left(-(M,\cdots ,M)+\frac{2M(1,\cdots ,1)}{k}\right)\right)}\hfill \\ {\displaystyle \frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{-}\left(-(M,\cdots ,M)+\frac{2M(1,\cdots ,1)}{k}\right)}\hfill \\ {\displaystyle \times g\left({\lambda }^{-1}\mathbf{x}-{\lambda }^{-1}\left(-(M,\cdots ,M)+\frac{2M(1,\cdots ,1)}{k}\right)\right)}\hfill \end{array}\right),$$

since, for a non-negative function h, $ReLU\left(h\right(x\left)\right)=h\left(x\right)$. Then, the $n_{in}+4$ and $n_{in}+5$-th components of $f_{l,\mathbf{n}}\left(\mathbf{x}\right)$ represented by $L^{1,\overline{\mathbf{j}}}\circ \cdots \circ ReLU\circ L^{1,1,1,\cdots ,1}\left(\mathbf{x}\right)$ are

$$\left(\begin{array}{c}{\displaystyle \sum _{\mathbf{j}<\overline{\mathbf{j}}}\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{+}\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)}\hfill \\ {\displaystyle \times g\left({\lambda }^{-1}\mathbf{x}-{\lambda }^{-1}\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right)}\hfill \\ {\displaystyle \sum _{\mathbf{j}<\overline{\mathbf{j}}}\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}{\lambda }^{n_{in}}}{f}_{-}\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)}\hfill \\ {\displaystyle \times g\left({\lambda }^{-1}\mathbf{x}-{\lambda }^{-1}\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right)}\hfill \end{array}\right),$$

where $\mathbf{j}\le \overline{\mathbf{j}}$ means when we give the well order to $\mathbf{j}$ in ordering like in (3) (for example, $(3,1,1,\cdots ,1)\le (1,2,1,\cdots ,1)$).

Therefore, we have

$$\begin{array}{cc}\hfill & L^{k{n}_{in}+2}\circ ReLU\circ L^{k{n}_{in}+1}\circ ReLU\circ L^{(n_{in},k,\cdots ,k)}\circ \cdots \circ L^{2,1,1,\cdots ,1}\circ ReLU\circ L^{1,1,\cdots ,1}\left(\mathbf{x}\right)\hfill \\ \hfill & \begin{array}{ccc}\hfill & =\hfill & \hfill {\displaystyle \frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}}\sum _{\mathbf{j}\in {\mathbb{Z}}_k^{n_{in}}}{f}_{+}\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)g_{\lambda }\left(\mathbf{x}-\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right)}\\ \hfill & \hfill & \hfill {\displaystyle -\frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}}\sum _{\mathbf{j}\in {\mathbb{Z}}_k^{n_{in}}}{f}_{-}\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)g_{\lambda }\left(\mathbf{x}-\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right)}\\ \hfill & =\hfill & \hfill {\displaystyle \frac{(n_{in}+1)!M^{n_{in}}}{k^{n_{in}}}\sum _{\mathbf{j}\in {\mathbb{Z}}_k^{n_{in}}}f\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)g_{\lambda }\left(\mathbf{x}-\left(-(M,\cdots ,M)+\frac{2M\mathbf{j}}{k}\right)\right).}\end{array}\hfill \end{array}$$

4. Conclusions

The universal approximation theorem is the mathematical theory of artificial neural networks and the classic one states that a feed-forward network with a hidden layer and some activation function can approximate continuous functions on compact subsets. Here, we show that, for a given continuous functions on compact subsets, the ReLU network with $n_{in}{k}^{n_{in}}+1$ hidden layers of at most $n_{in}+5$ nodes and proper weights can approximate to the function using the approximate identity. To show this, we explicitly give connection and weights. Our construction is rather partially rather than fully connected; especially, each of the first $n_{in}+3$ nodes in each hidden layer is connected to only one node of the previous layer. This means that actually we don’t need a fully connected network.

Actually, we are interested in the relation between the parameter k and error bound $ϵ$ because, if we know this, we can estimate how many hidden layers should be constructed to get the allowable error. Thus, the error estimate depending on the parameter k is our next research line.