On the uniform approximation estimation of deep ReLU networks via frequency decomposition

1.   Introduction

The approximation theory of neural networks has been widely concerned in recent years ^{[6,12,18,21,22,24,25,26,27,30,31,32,33,34,35]}. There are two widely accepted advantages of neural networks, one is that neural network can overcome the curse of dimensionality ^{[1,4,5,7,9,11,15,16,17]}, the other is that as the number of layers increases, deep neural networks can fit high-oscillation or high-frequency functions ^{[3,17,18,19,21,23]}. For the bandlimited functions, the approximation complexity of deep ReLU networks has been studied ^[3,17] in the MSE sense. Compared with the results of the shallow neural networks ^[1], these results show deep ReLU networks can approximate the ultrawide bandwidth high-dimensional signals with very low complexity. In this paper, we continue this line of research, we estimate the approximation complexity of deep ReLU networks in the $L_{\infty}$ sense, thus, this estimate is significantly better than the previous results ^[3,17]. It worths mentioning that the approximate complexity estimations of the shallow neural networks are significantly different for different error norms ^[9,13]. Similarly, for the deep ReLU networks, we can not resort to the Maurey's theorem ^[20] in the $L_{\infty}$ case. We need to use the fat-shattering dimension theory ^[8] to establish a frequency decomposition lemma which is our main result.

Lemma 1.1. Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a bandlimited function of the form

and

there exist $2l$ frequencies

and $2l$ coefficients

satisfying

and

such that

where $C$ is some universal constant, $0 < \epsilon < 1/2$, $D$ is any bounded subset of $\mathbb{R}^d$ and

On the other hand, a feedforward neural network $\tilde{X}$ consists of layers of nodes, each node of the form

where $\{x_{k}:k = 1, 2, \dots, N\}$ are nodes in the previous layers, and $\sigma$ is a activation function. If $\sigma(x) = \max (x, 0)$, the multilayer feedforward neural network is the deep ReLU (Rectified Linear Unit) network. The complexity of deep neural networks approximating to sinusoidal functions has been discussed ^[3,17,19].

Lemma 1.2. (^[3]) There exists a deep ReLU network $\tilde{X}_{\epsilon }$ with $O(\log (C_{D}M)\log_{2}^2 (1/\epsilon))$ layers and $O(\log C_{D}M \log_{2}^3 (1/\epsilon))$ nodes such that

Based on Lemma 1.1 and Lemma 1.2, the following main theorem can be obtained.

Theorem 1.3. Let $f: D \rightarrow \mathbb{R}$ be a bandlimited function of the form

and

there exists a deep ReLU network $\tilde{X}_{\epsilon }$ with

layers and

nodes such that

2.   Proof of the Lemma 1.1

For any complex value $z\in\mathbb{C}$, $\Re z$ and $\Im z$ denote the real part and the imaginary part of $z$, respectively. We denote by $C_j, j = 1, 2, \dots$ some universal constants.

To prove Lemma 1.1, some notations and lemmas are needed. Given a class $\mathcal{H}$ of real-valued functions defined on $X$ and a real number $\gamma \ge 0$. The fat-shattering dimension of $\mathcal{H},$ denoted $\operatorname{fat}_{H}(\gamma),$ is the largest integer $m$ satisfying the following property: There exist $V = \left\{x_{1}, x_{2}, \ldots, x_{m}\right\}$ is a subset of the domain $X,$ and the real numbers $r_{1}, r_{2}, \ldots, r_{m}$ such that for all $b \in\{0, 1\}^{m}$ there is a function $f_{b}$ in $\mathcal{H}$ with $f_{b}\left(x_{i}\right) \geq r_{i}+\gamma\quad \rm { if }\quad b_{i} = 1$ and $f_{b}\left(x_{i}\right) < r_{i}-\gamma\quad \rm { if }\quad b_{i} = 0$ for $1 \leq i \leq m.$ Fat-shattering dimension is a generalization of Vapnik-Chervonenkis dimension ^[29] which is often used to estimate approximation complexity ^[10,14,35].

Lemma 2.1. (^[2]) Let $\mathcal{H}$ be a class of functions from some domain $X$ into $[0, 1].$ Then for all distributions $\mathbb{P}$ over $X$ and for all $0 < \epsilon, \delta < 1/2$

where $\left\{x_{i}\right\}_{i = 1}^{l}$ are $l$ independent draws from $\mathbb{P}$, $\operatorname{Pr}_{x_1, x_2, \dots, x_l}$ denotes the joint probability distribution function for random variables $x_1, x_2, \dots, x_l$ and

Lemma 2.2. (^[28]) Let $p_1, p_2, \dots, p_{l}$ be d-variable real polynomials of degree at most $q$. If $l\ge d$, then the number of vectors

is at most $(4elq/d)^d$, where ${\rm sgn}(x): = \left\{\begin{array}{ll} 1, & x\ge 0, \\ -1, &x < 0.\end{array}\right.$

By the Taylor expansion, the sines and cosines can be approximation by polynomials.

Lemma 2.3. Let $0 < \epsilon < 1$, $a > 0$ and $f(x) = \sin(x) \ {{or}}\ \cos(x)$. Then there exist $C_1 > 0$ and a polynomial $Q$ of order less than or equal to $C_1(a+\log(1/\epsilon))$ such that $\sup_{x\in[-a, a]}|f(x)-Q(x)|\le \epsilon$.

Proof. The Taylor expansion for an $n$ times differentiable function $f$ at $0$ with the Lagrange remainder is given by

where $x_0$ is between $0$ and $x$, $f^{(j)}$ denotes the derivative of order $j$, and the factorial $n! = n(n-1)\cdots 1$. Applying the Stirling formula to $n!$, we have

Note that $|\sin^{(n)}(x)|\le 1$ and $|\cos^{(n)}(x)|\le 1$ for all $x\in\mathbb{R}$. Thus, by (2.1) and (2.2), we have for all $n\ge \max\{2ea, \frac{1}{\log 2}\log(\frac{1}{\epsilon})\}$

The proof is hence complete.

Proof of Lemma 1.1. Since $f$ is a real-valued function, we have for all $x\in\mathbb{R}^{d}$

where

Let $F_1: = \max(0, \Re \widehat{f})$. Without loss of generality, we assume that

We only discuss the approximation for the first term

The other three terms $f_2, f_3, f_4$ in (2.3) can be handled in a similar manner. Observe that

By Lemma 2.3, there exists $C_2 > 0$ and a polynomial $Q$ of degree $C_2(C_{D}M+\log(1/\epsilon))$ such that

Let

Then, we get

Set

and

By Lemma 2.2, the number of vectors

is at most $(4elC_{2}(C_{D}M+\log(1/\epsilon))/d)^d.$ Thus,

that is

Note that

then

By Lemma 2.1, choosing $\delta < 1/4$ and

we have

where $\left\{w_{i}\right\}_{i = 1}^{l}$ obeys the probability distribution generated by the density function

Therefore, there exist $w_1, w_2, \dots, w_l$ such that

The approximation for $f_2$ is similar to $f_1$ given as in (2.6). Hence, we can obtain an approximation for $f_3$ or $f_4$ by the linear combination of sines. The sum of $2l$ coefficients in (1.1) is bounded by

The proof is hence complete.

3.   Conclusions

In this paper we prove an interesting frequency decomposition lemma, as a corollary, we establish the uniform approximation estimation of bandlimited functions via deep ReLU networks. We will discuss the learnability of neural networks for bandlimied functions in the following work. These theoretical results will deepen the understanding of machine learning methods in signal processing.

Acknowledgements

The authors are thankful to their Universities for their support. This work was supported by the National Natural Science Foundation of China (No. 11661065).

Conflict of interest

The authors declare that they have no competing interests.