Rates of Approximation by ReLU Shallow Neural Networks
Neural networks activated by the rectified linear unit (ReLU) play a central
role in the recent development of deep learning. The topic of approximating
functions from H\"older spaces by these networks is crucial for understanding
the efficiency of the induced learning algorithms. Although the topic has been
well investigated in the setting of deep neural networks with many layers of
hidden neurons, it is still open for shallow networks having only one hidden
layer. In this paper, we provide rates of uniform approximation by these
networks. We show that ReLU shallow neural networks with $m$ hidden neurons can
uniformly approximate functions from the H\"older space $W_\infty^r([-1, 1]^d)$
with rates $O((\log m)^{\frac{1}{2} +d}m^{-\frac{r}{d}\frac{d+2}{d+4}})$ when
$r<d/2 +2$. Such rates are very close to the optimal one $O(m^{-\frac{r}{d}})$
in the sense that $\frac{d+2}{d+4}$ is close to $1$, when the dimension $d$ is
large.
Tong Mao, Ding-Xuan Zhou
# Rates of Approximation by ReLU Shallow Neural Networks

###### Abstract

Neural networks activated by the rectified linear unit (ReLU) play a central role in the recent development of deep learning. The topic of approximating functions from Holder spaces by these networks is crucial for understanding the efficiency of the induced learning algorithms. Although the topic has been well investigated in the setting of deep neural networks with many layers of hidden neurons, it is still open for shallow networks having only one hidden layer. In this paper, we provide rates of uniform approximation by these networks. We show that ReLU shallow neural networks with \(m\) hidden neurons can uniformly approximate functions from the Holder space \(W_{\infty}^{r}([-1,1]^{d})\) with rates \(O((\log m)^{\frac{1}{2}+d}m^{-\frac{r}{d}\frac{d+2}{d+4}})\) when \(r<d/2+2\). Such rates are very close to the optimal one \(O(m^{-\frac{r}{d}})\) in the sense that \(\frac{d+2}{d+4}\) is close to \(1\), when the dimension \(d\) is large.

_Keywords_: deep learning, shallow neural networks, ReLU, rates of uniform approximation, Holder space

_Mathematics Subject Classification (2020)_: 68T07, 41A25, 68Q32

## 1 Introduction

The exploration of approximating functions by neural networks has a history of over 30 years. Let \(x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}\) be the data vector and \(m\in\mathbb{N}\). A shallow neural
network of width \(m\) associated with a continuous activation function \(\sigma:\mathbb{R}\to\mathbb{R}\) is defined by

\[f_{m}(x)=\sum_{i=1}^{m}\beta_{i}\sigma(\alpha_{i}\cdot x-b_{i}), \tag{1.1}\]

where \(\{\alpha_{i}\}_{i=1}^{m}\subset\mathbb{R}^{d}\) are connection vectors, \(\{\beta_{i}\}_{i=1}^{m}\subset\mathbb{R}\) weights and \(\{b_{i}\}_{i=1}^{m}\subset\mathbb{R}\) biases. The universality of shallow networks [7; 18; 31] asserts for any non-polynomial activation that any continuous function on any compact subset of \(\mathbb{R}^{d}\) can be approximated by output functions of the form (1.1) to an arbitrary accuracy when the number \(m\) of hidden neurons is large enough. Rates of approximation by such output functions from the hypothesis space

\[H_{m}=\left\{\sum_{i=1}^{m}\beta_{i}\sigma(\alpha_{i}\cdot x-b_{i}):\ \alpha_{i}\in \mathbb{R}^{d},\ \beta_{i}\in\mathbb{R},\ b_{i}\in\mathbb{R}\right\}. \tag{1.2}\]

were also studied in a large literature when \(\sigma\) is a sigmoid type \(C^{\infty}\) activation function. In [2] it was proved that a function \(f\) on \(\mathbb{R}^{d}\) with its Fourier transform \(\hat{f}\) satisfying \(\int_{\mathbb{R}^{d}}\lvert\omega\rvert\lvert\hat{f}(\omega)\rvert d\omega<\infty\) can be approximated uniformly on \([-1,1]^{d}\) by \(f_{m}\in H_{m}\) with rates \(O(m^{-1/2})\). The error rate is proved (e.g. [25]) to be \(O(m^{-r/d})\) for functions from the Holder space \(W_{\infty}^{r}([-1,1]^{d})\) defined as follows.

**Definition 1**.: _Let \(r\in\mathbb{N}\), \(d\in\mathbb{N}\), and \(\Omega\subset\mathbb{R}^{d}\) be a compact domain with non-empty interior. The Holder space \(W_{\infty}^{r}(\Omega)\) is defined by_

\[W_{\infty}^{r}(\Omega)=\{f\in C(\Omega):\ \max_{0\leq\|\alpha\|_{1}\leq r}\|D^{ \alpha}f\|_{L_{\infty}(\Omega)}<\infty\} \tag{1.3}\]

_with the norm \(\|f\|_{W_{\infty}^{r}(\Omega)}=\max_{0\leq\|\alpha\|_{1}\leq r}\lVert D^{ \alpha}f\rVert_{L_{\infty}(\Omega)}\) defined with the partial derivatives \(D^{\alpha}f\) of order \(\alpha=(\alpha_{1},\cdots,\alpha_{d})\in\mathbb{Z}_{+}^{d}\)._

When training network parameters with gradient descent methods in deep learning, the classical neural networks with sigmoid type \(C^{\infty}\) activation functions often encounter the **gradient vanishing problem**. To solve this problem, in most neural networks used for deep learning applications, the classical sigmoid type \(C^{\infty}\) activation functions are replaced by the **rectified linear unit** (ReLU) \(\sigma\) defined as

\[\sigma(x)=\max\{0,x\},\qquad x\in\mathbb{R}.\]

Within the last few years, rates of function approximation by ReLU deep neural networks have been obtained when the network has many layers with depth increasing with the number \(m\) of hidden neurons. D. Yarotsky [36] observed that iterates of ReLU can be used to realize piecewise linear interpolations of the univariate quadratic function \(\varphi(u)=u^{2}\) with few parameters. Based on this observation,
he proved that ReLU deep neural networks with \(O(\log m)\) layers and \(O(m\log m)\) neurons can achieve an almost optimal error rate \(O(m^{-r/d})\) for approximating functions from \(W_{\infty}^{r}([-1,1]^{d})\). For approximating smooth functions and piecewise-smooth functions, upper bounds were given in [30, 4, 13, 16]. Applying Yarotsky's method to functions from the Korobov space, a deep neural network with \(O(\log m)\) layers and \(O(m(\log m)^{\frac{3}{2}(d-1)+1})\) neurons, which achieves the rate \(O(m^{-2})\), was constructed in [29].

All the above mentioned results are for ReLU deep neural networks with many layers. Furthermore, in [32], it was proved that on a smooth \(d\)-dimensional compact manifold without boundary, \(C^{2}\) functions can be approximated by a deep network of depth \(4\) with a rate \(O(m^{-2/d})\), which is optimal. Rates of approximation by networks induced by ReLU type activation functions such as \(\left(\max\{0,x\}\right)^{\alpha}\) with \(\alpha>1\) were also obtained in [1, 26]. This recent literaure on ReLU type networks and the classical work on sigmoid shallow networks lead to a natural open question whether one can derive rates of function approximation by ReLU shallow networks of one hidden layer.

The purpose of this paper is to answer the above open question and present rates of approximating functions from Holder spaces uniformly by **ReLU shallow neural networks**. An approximation theory about shallow neural networks plays a fundamental role in understanding ReLU networks as a benchmark. It has some other applications such as those for convolutional neural networks to be discussed below. Similar analysis was conducted in [28, Theorem 4.1] for sigmoid networks which demonstrates how to deduce approximation rates of a sigmoid deep neural network by using those of sigmoid shallow networks.

A nice study for ReLU shallow networks was carried out by Klusowski and Barron [21]. They gave rates \(O(m^{-\frac{1}{2}-\frac{1}{d}})\) of approximating functions \(f\) whose Fourier transform \(\hat{f}\) satisfies \(\int_{\mathbb{R}^{d}}\lvert\hat{f}(\omega)\rvert\lVert\omega\rVert_{1}^{2}d \omega<\infty\). If we want to apply this result to the Holder space \(W_{\infty}^{r}(\Omega)\), then the regularity index \(r\) must satisfy \(r>d/2\), as discussed in [38], which might be too large for some learning problems dealing with data of large dimensions \(d>>1\).

A possible way to overcome this barrier is using an intermediate function \(f_{R}(x)=\int_{\lvert\omega\rvert\leq R}\hat{f}(\omega)e^{i\omega x}d\omega\) and estimate the error \(\lVert f-f_{R}\rVert_{\infty}\) and \(\lVert f_{R}-f_{m}\rVert_{\infty}\), where \(f_{m}\) is the function in [21] which approximates \(f_{R}\). However, this method does not make full use of frequency domain properties of the Fourier transform. One can only obtain a rate \(O(m^{-\frac{r}{2d}})\), which is much worse than the optimal rate \(O(m^{-r/d})\).

In this paper, we use a novel idea motivated by tools from Fourier analysis [12, 34, 5] to carry out time-frequency analysis for partial sums of Fourier series and decompose the error into multi-level parts according to various frequevely levels. Then we are able to show that the error of approximating functions from \(W_{\infty}^{r}([-1,1]^{d})\) by ReLU shallow neural networks can be estimated with rates \(O((\log m)^{\frac{1}{2}+d}m^{-\frac{r}{d}\frac{d+2}{d+4}})\)
when \(r<d/2+2\). This rate of approximation is very close to the optimal one \(O(m^{-r/d})\) when the dimension \(d\) is large. In fact, \(O(m^{-r/d})\) is the lower bound for the approximation by any neural network with \(m\) parameters, which was proved in [8] and will be discussed in Section 5. Throughout the paper we take the domain \(D=[-1,1]^{d}\) of functions for approximation and \(\sigma\) to be the ReLU activation function.

## 2 Main Results

The following theorem, to be proved in Section 4, is our first main result. It gives an upper bound for approximating functions from \(W_{\infty}^{r}(D)\) uniformly by ReLU shallow neural networks.

**Theorem 1**.: _Let \(d,r\in\mathbb{N}\). Then there exists a constant \(C(d,r)\) depending only on \(d\) and \(r\) such that for any \(F\in W_{\infty}^{r}(D)\) and \(m\in\mathbb{N}\), there holds_

\[\inf_{f_{m}\in H_{m}}\|F-f_{m}\|_{L_{\infty}(D)}\leq C(d,r)\|F\|_{W_{\infty}^{ r}(D)}\left\{\begin{array}{ll}(\log m)^{\frac{1}{2}+d}m^{-\frac{r}{d}\frac{d+2}{d +4}},&\qquad\text{if }r<\frac{d}{2}+2,\\ (\log m)^{\frac{3}{2}+d}m^{-\frac{r}{d}\frac{d+2}{d+4}},&\qquad\text{if }r=\frac{d}{2}+2,\\ (\log m)^{\frac{1}{2}}m^{-\frac{1}{2}-\frac{1}{d}},&\qquad\text{if }r>\frac{d}{2}+2. \end{array}\right. \tag{2.1}\]

As all the existing approximation results on ReLU networks are either for deep networks with multiple layers or for shallow networks [21] with a large regularity index \(r>d/2\), Theorem 1 establishes the first approximation theory with almost optimal rates for approximating functions from Holder spaces by ReLU shallow networks.

Theorem 1 holds true only for the Holder space \(W_{\infty}^{r}(D)\) with an integer regularity index \(r\). The restriction on \(r\) is due to a technique in our proof for estimating a quantity involving multplications of a Fourier series with polynomial sequences. It would be interesting to extend Theorem 1 to Holder spaces with non-integer regularity indices and Sobolev spaces \(W_{p}^{r}(D)\) which would allow Holder and Sobolev spaces to be defined spectrally [6] and thereby more general approximation estimates given in terms of moduli of smoothness.

Theorem 1 may be applied to various ReLU networks. One example is the important family of convolutional neural networks (CNNs), which are widely applied in speech recognition, image classification and many other tasks [17, 22].

Given a sequence \(w=(w_{k})_{k\in\mathbb{Z}}\) on \(\mathbb{Z}\) supported in \(\{0,1,\ldots,s\}\) and another one \(x=(x_{k})_{k\in\mathbb{Z}}\) supported in \(\{1,2,\ldots,t\}\), the convolution of \(w\) and \(x\) is a sequence supported in \(\{1,2,\ldots,t+s\}\) given by

\[(w{*}x)_{i}=\sum_{k\in\mathbb{Z}}w_{i-k}x_{k}=\sum_{k=1}^{t}w_{i-k}x_{k}, \qquad i\in\mathbb{Z}.\]
This convolutional operation induces a convolutional Toeplitz matrix

\[T^{w}:=(w_{i-k})_{1\leq i\leq t+s,1\leq k\leq t}\]

with the size \((t+s)\times t\) depending on that of the input vector in \(\mathbb{R}^{t}\) which corresponds to the zero-padding approach in convolutional networks.

**Definition 2**.: _Let \(x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}\) be the input data vector, \(s,J\in\mathbb{N}\), and \(\{d_{j}\}_{j=1}^{J}\) given by \(d_{0}=d\),_

\[d_{j}=d_{j-1}+s,\qquad j\in\{1,\ldots,J\}.\]

_The **deep CNN**\(\{h^{(j)}:\mathbb{R}^{d}\to\mathbb{R}^{d_{j}}\}_{j=1}^{J}\) with widths \(\{d_{j}\}_{j=1}^{J}\), sequences of filters \(\mathbf{w}:=\{w^{(j)}:\ \mathbb{Z}\to\mathbb{R}\}_{j=1}^{J}\) supported in \(\{0,\ldots,s\}\), and biases \(\mathbf{b}:=\{b^{(j)}\in\mathbb{R}^{d_{j}}\}_{j=1}^{J}\) is defined by_

\[h^{(j)}(x)=\mathcal{A}_{j}\circ\ldots\circ\mathcal{A}_{1}(x),\qquad j=1,\ldots,J, \tag{2.2}\]

_where \(\mathcal{A}_{j}\) is a map from \(\mathbb{R}^{d_{j-1}}\) to \(\mathbb{R}^{d_{j}}\) defined with the \(d_{j}\times d_{j-1}\) convolutional matrix \(T^{w^{(j)}}\) by acting \(\sigma\) componentwise as_

\[\mathcal{A}_{j}(v)=\sigma(T^{w^{(j)}}v-b^{(j)}),\qquad v\in\mathbb{R}^{d_{j-1 }}.\]

It was proved in [38] that when \(r>d/2+2\), deep CNNs can approximate functions from \(W_{\infty}^{r}(D)\) uniformly with rate \(O(\sqrt{\log J}J^{-1/2-1/d})\). In this paper, we can use Theorem 1 to derive rates of approximating by deep CNNs functions from the Holder space with a smaller index \(r\leq d/2+2\), which is our second main result, to be proved in Section 4.

**Corollary 1**.: _Let \(d,\ s\in\mathbb{N}\) and \(F\in W_{\infty}^{r}(D)\) for some integer \(r\in\mathbb{N}\). Then for any \(J\in\mathbb{N}\), there exist \(\mathbf{w}=\{w^{(j)}\}_{j=1}^{J}\) and \(\mathbf{b}=\{b^{(j)}\}_{j=1}^{J}\) such that the space_

\[\mathcal{H}_{J}^{\mathbf{w},\mathbf{b}}=\left\{c\cdot h^{(J)}(x):\ c\in \mathbb{R}^{d_{J}}\right\}\]

_contains an element \(f_{J}^{\mathbf{w},\mathbf{b}}\) satisfying_

\[\|F-f_{J}^{\mathbf{w},\mathbf{b}}\|_{C(D)}\leq\left\{\begin{array}{ll}C_{1} (d,r)\|F\|_{W_{\infty}^{r}(D)}(\log J)^{d+1/2}J^{-\frac{r}{d}\frac{d+2}{d+4}},&\text{if }r<\frac{d}{2}+2,\\ C_{1}(d,r)\|F\|_{W_{\infty}^{r}(D)}(\log J)^{d+3/2}J^{-\frac{r}{d}\frac{d+2}{d+ 4}},&\text{if }r=\frac{d}{2}+2,\\ C_{1}(d,r)\|F\|_{W_{\infty}^{r}(D)}(\log J)^{1/2}J^{-\frac{1}{2}-\frac{1}{d}},&\text{if }r>\frac{d}{2}+2,\end{array}\right.\]

_where \(C_{1}(d,r)\) depends only on \(d\) and \(r\)._

The rates of approximation presented in Corollary 1 are stated in terms of the depth \(J\) or number of layers of the CNN. In many applications of CNNs, the depth \(J\) is large. Some relations between deep CNNs of large depth and fully-connected
networks have been observed recently. In [39], it was proved that the last layer of any fully-connected network is identical to that of a deep CNN with at most 8 times number of free parameters. For approximating or learning ridge function [10], radial functions [23], and functions from Korobov spaces [24], deep CNNs can be achieve the same accuracy with much smaller number of free parameters than fully-connected networks. In a recent application of CNNs to readability of Chinese texts [11], it is found that one layer or two is already efficient. Conducting analysis for approximation and learning by CNNs with small depths would be an interesting task.

## 3 Error Decomposition and Preliminary Analysis

To prove Theorem 1, we need an error decomposition: first we extend \(F\) to a \(2\pi\)-periodic function \(f\) on \(\mathbb{R}^{d}\), then we decompose the error between \(F\) and \(f_{m}\) into two parts, involving the (high-order) Jackson operator.

By the well-known extension theorem (e.g. [33, Chapter 6]), \(F\) can be extended to a \(2\pi\)-periodic continuous function \(f\) on \(\mathbb{R}^{d}\) such that \(F=f\) on \(D\) and

\[\|f\|_{W_{\infty}(\mathbb{T}^{d})}\leq C_{2}(d,r)\|F\|_{W_{\infty}^{r}(D)},\]

where \(C_{2}(d,r)\) is a constant that only depends on \(d\) and \(r\) and \(\mathbb{T}^{d}=[-\pi,\pi]^{d}\).

The periodic function \(f\) has a Fourier series expansion

\[f(x)=\sum_{k\in\mathbb{Z}^{d}}\hat{f}(k)e^{ik\cdot x},\qquad x\in\mathbb{R}^{ d},\]

where \(\left\{\hat{f}(k)=(2\pi)^{-d}\int_{\mathbb{T}^{d}}f(x)e^{-ik\cdot x}dx:k\in \mathbb{Z}^{d}\right\}\) are the Fourier coefficients of \(f\).

Let \(N\) be an integer. We use the Jackson operator \(J_{N,r}\) to approximate \(f\).

We first introduce the univariate Jackson kernel as

\[K_{N,r}^{[1]}(t)=\lambda_{N,r}\left(\frac{\sin Mt/2}{\sin t/2}\right)^{2r}, \qquad t\in\mathbb{R},\]

where \(M:=\lfloor N/r\rfloor+1\) with \(\lfloor u\rfloor\) being the integer part of \(u>0\) and \(\lambda_{N,r}=\left[\int_{\mathbb{T}}(\frac{\sin Mt/2}{\sin t/2})^{2r}dt \right]^{-1}\). The function \(K_{N,r}^{[1]}\) is real-valued and \(2\pi\)-periodic. It also has an expression

\[K_{N,r}^{[1]}(t)=\sum_{k\in\mathbb{Z}}\tilde{a}_{k,N}^{[1]}e^{ikt}=\tilde{a}_ {0,N}^{[1]}+\sum_{k\in\mathbb{N}}2\tilde{a}_{k,N}^{[1]}\cos kt,\]

where \(\{\tilde{a}_{k,N}^{[1]}\}_{k\in\mathbb{Z}}\) is a real-valued even sequence supported in \(\{-N,\ldots,N\}\). To see this, using prosthaphaeresis formulae and the standard expressions of the \(M\)-th Fejer kernel

\[\frac{1}{2M}\left(\frac{\sin Mt/2}{\sin t/2}\right)^{2}=\sum_{\ell=0}^{M-1}b_{ \ell}\cos\ell t,\]
where \(b_{j}=1-\frac{j}{M}\) for \(j\geq 1\) and \(b_{0}=\frac{1}{2}\), we can deduce

\[K_{N,r}^{[1]}(t)=\lambda_{N,r}(2M)^{r}\sum\limits_{k=0}^{r(M-1)}\left(\sum \limits_{\epsilon\in\{-1,1\}^{r}}\sum\limits_{0\leq\ell_{i}\leq M-1,\ \forall i\ i=1}\prod\limits_{i=1}^{r}b_{\ell_{i}}\right)\frac{\cos kt}{2^{r}}. \tag{3.1}\]

The asymptotic behavior \(\lambda_{n,r}\sim n^{-2r+1}\) can be found in the literature (e.g., [9, Chapter 7, Lemma 2.1]) and seen easily from the identity \(\int_{\mathbb{T}}(\frac{\sin Mt/2}{\sin t/2})^{2r}dt=2\int_{0}^{\pi}(\frac{ \sin Mt/2}{\sin t/2})^{2r}dt\) and

\[\int_{0}^{\pi}(\frac{\sin Mt/2}{t/2})^{2r}dt\leq\int_{0}^{\pi}(\frac{\sin Mt/2 }{\sin t/2})^{2r}dt\leq\int_{0}^{\pi}(\frac{\sin Mt/2}{(2/\pi)\cdot(t/2)})^{2r}dt\]

by bounding the integral \(\int_{0}^{\pi}(\frac{\sin Mt/2}{t})^{2r}dt=\left(\frac{2}{M}\right)^{1-2r} \int_{0}^{M\pi/2}(\frac{\sin u}{u})^{2r}du\) as

\[\int_{\pi/6}^{5\pi/6}(\frac{\sin u}{u})^{2r}du\leq\int_{0}^{M\pi/2}(\frac{\sin u }{u})^{2r}du\leq\sum\limits_{k=0}^{\infty}\int_{0}^{2\pi}\frac{(\sin u)^{2r}} {(u+2k\pi)^{2r}}du\leq 2\pi+\sum\limits_{k=1}^{\infty}\frac{1}{k^{2r}}.\]

Thus, we can bound \(\tilde{a}_{k,N}^{[1]}\) as

\[|\tilde{a}_{k,N}^{[1]}|\leq 2^{r}\sup\limits_{n\in\mathbb{N}}(\lambda_{n,r}n^{ 2r-1}):=C_{3}(r),\qquad\forall k\in\mathbb{Z}.\]

The classical Jackson Theorem (e.g., (2.8) and (2.11) in [9, Chapter 7]) asserts that for the univariate Jackson operator \(J_{N,r}^{[1]}\) on \(L_{\infty}(\mathbb{T})\) given by

\[J_{N,r}^{[1]}(g,x):=\int_{\mathbb{T}}\left[\sum\limits_{\ell=1}^{r}(-1)^{\ell -1}\binom{r}{\ell}g(x+\ell y)\right]K_{N,r}^{[1]}(y)dy, \tag{3.2}\]

there exists a constant \(C_{4}(r)\) depending only on \(r\) such that

\[\|J_{N,r}^{[1]}(g)-g\|_{L_{\infty}(\mathbb{T})}\leq C_{4}(r)\|g^{(r)}\|_{L_{ \infty}(\mathbb{T})}N^{-r},\qquad\forall g\in W_{\infty}^{r}(\mathbb{T}),\ N\in \mathbb{N}. \tag{3.3}\]

Since \(\|K_{N,r}^{[1]}\|_{L_{1}(\mathbb{T})}=1\), (3.2) implies

\[\|J_{N,r}^{[1]}(g)\|_{L_{\infty}(\mathbb{T})}\leq\sum\limits_{\ell=1}^{r}\binom {r}{\ell}\|g\|_{L_{\infty}(\mathbb{T})}\|K_{N,r}^{[1]}\|_{L_{1}(\mathbb{T})} \leq 2^{r}\|g\|_{L_{\infty}(\mathbb{T})},\quad\forall g\in L_{\infty}(\mathbb{ T}). \tag{3.4}\]

Observe from a change of variable and the \(2\pi\)-periodicity of \(g\) that

\[J_{N,r}^{[1]}(g,x)= \sum\limits_{\ell=1}^{r}(-1)^{\ell-1}\binom{r}{\ell}\frac{1}{ \ell}\int_{0}^{2\ell\pi}g(x+t)\sum\limits_{k\in\mathbb{Z}}\tilde{a}_{k,N}^{[1] }e^{ikt/\ell}dt\] \[= \sum\limits_{\ell=1}^{r}(-1)^{\ell-1}\binom{r}{\ell}\frac{1}{ \ell}\int_{0}^{2\pi}g(x+t)\sum\limits_{k\in\mathbb{Z}}\tilde{a}_{k,N}^{[1]} \sum\limits_{\alpha=0}^{\ell-1}e^{ik(t+2\alpha\pi)/\ell}dt.\]
Notice that the summation \(\sum\limits_{\alpha=0}^{\ell-1}e^{ik(t+2\alpha\pi)/\ell}=e^{ikt/\ell}\sum\limits_{ \alpha=0}^{\ell-1}\left(e^{i2k\pi/\ell}\right)^{\alpha}\) vanishes when \(k\not\in\ell\mathbb{Z}\) and equals \(\ell e^{ikt/\ell}\) otherwise. Henece

\[J_{N,r}^{[1]}(g,x)= \sum\limits_{\ell=1}^{r}(-1)^{\ell-1}\binom{r}{\ell}\int_{0}^{2 \pi}g(x+t)\sum\limits_{k^{\prime}\in\mathbb{Z}}\tilde{a}_{k^{\prime}\ell,N}^{ [1]}e^{ik^{\prime}t}dt\] \[= \int_{\mathbb{T}}g(x-y)\sum\limits_{k^{\prime}\in\mathbb{Z}}\sum \limits_{\ell=1}^{r}(-1)^{\ell-1}\binom{r}{\ell}\tilde{a}_{-k^{\prime}\ell,N} ^{[1]}e^{ik^{\prime}y}dy.\]

Thus, by introducing a \(2\pi\)-periodic kernel \(G_{N,r}^{[1]}(t)=\sum\limits_{k\in\mathbb{Z}}a_{k,N}^{[1]}e^{ikt}\) with an even sequence of coefficients

\[a_{k,N}^{[1]}=\sum\limits_{\ell=1}^{r}(-1)^{\ell-1}\binom{r}{\ell}\tilde{a}_ {-k\ell,N}^{[1]},\qquad k\in\mathbb{Z},\]

we see that the Jackson operator can be expressed as

\[J_{N,r}^{[1]}(g,x)=\int_{\mathbb{T}}G_{N,r}^{[1]}(y)g(x-y)dy=\int_{\mathbb{T}} G_{N,r}^{[1]}(x-y)g(y)dy.\]

The coefficients of the kernel \(G_{N,r}^{[1]}\) can be bounded as

\[|a_{k,N}^{[1]}|\leq 2^{r}C_{3}(r). \tag{3.5}\]

Now we can define a multidimensional \(2\pi\)-periodic kernel \(G_{N,r}\) on \(\mathbb{R}^{d}\) by

\[G_{N,r}(x)=\prod\limits_{j=1}^{d}G_{N,r}^{[1]}(x_{j})=\sum\limits_{k\in \mathbb{Z}^{d}}a_{k,N}e^{ik\cdot x}. \tag{3.6}\]

where \(a_{k,N}=\prod\limits_{j=1}^{d}a_{k_{j},N}^{[1]}\) for \(k=(k_{1},\ldots,k_{d})\in\mathbb{Z}^{d}\). By means of this kernel, we define the Jackson operator on \(L_{\infty}(\mathbb{T}^{d})\) by

\[J_{N,r}(g,x):=\int_{\mathbb{T}^{d}}G_{N,r}(x-y)g(y)dy=\sum\limits_{\|k\|_{ \infty}\leq N}(2\pi)^{d}a_{k,N}\hat{g}(k)e^{ik\cdot x},\qquad x\in\mathbb{T}^ {d}. \tag{3.7}\]

To approximate the function \(f\), we write \(J_{N,r}(f)\) in terms of the multidimensional kernel (3.6) as \(J_{N,r}(f,x)=\int_{\mathbb{T}^{d}}\prod\limits_{\ell=1}^{d}G_{N,r}^{[1]}(x_{ \ell}-y_{\ell})f(y_{1},\ldots,y_{d})dy_{1}\ldots dy_{d}\). It is a special case with \(j=d\) of the intermediate functions

\[\left\{\int_{\mathbb{T}^{j}}\prod\limits_{\ell=1}^{j}G_{N,r}^{[1]}(x_{\ell}-y _{\ell})f(y_{1},\ldots,y_{j-1},y_{j},x_{j+1},\ldots,x_{d})dy_{1}\ldots dy_{j} \right\}_{j=0}^{d}\]
while \(f(x)=f(x_{1},\ldots,x_{d})\) corresponds to the case with \(j=0\). Then by subtracting and adding the intermediate functions with \(j=d-1,\ldots,1\), we find that the error of approximation \(J_{N,r}(f)-f\) can be expressed as

\[J_{N,r}(f,x)-f(x)=\sum_{j=1}^{d}\int_{\mathbb{T}^{j-1}}\prod_{\ell=1}^{j-1}G_{N,r}^{[1]}(x_{\ell}-y_{\ell})I_{x_{j},\ldots,x_{d}}(y_{1},\ldots,y_{j-1})dy_{1} \ldots dy_{j-1}\]

where \(I_{x_{j},\ldots,x_{d}}(y_{1},\ldots,y_{j-1})\) is a function on \(\mathbb{T}^{j-1}\) indexed by \(x_{j},\ldots,x_{d}\in\mathbb{R}\) given by

\[\int_{\mathbb{T}}G_{N,r}^{[1]}(x_{j}-y_{j})f(y_{1},\ldots,y_{j-1},y_{j},x_{j+1 },\ldots,x_{d})dy_{j}-f(y_{1},\ldots,y_{j-1},x_{j},x_{j+1},\ldots,x_{d}).\]

Applying (3.4) to the function \(\int_{\mathbb{T}^{j-2}}\prod_{\ell=2}^{j-1}G_{N,r}^{[1]}(x_{\ell}-y_{\ell})I_ {x_{j},\ldots,x_{d}}(y_{1},\ldots,y_{j-1})dy_{2}\ldots dy_{j-1}\) of the single variable \(y_{1}\), we see that

\[\sup_{x_{1}\in\mathbb{T}}\left|\int_{\mathbb{T}^{j-1}}\prod_{\ell =1}^{j-1}G_{N,r}^{[1]}(x_{\ell}-y_{\ell})I_{x_{j},\ldots,x_{d}}(y_{1},\ldots,y _{j-1})dy_{1}\ldots dy_{j-1}\right|\] \[\leq 2^{r}\sup_{y_{1}\in\mathbb{T}}\left|\int_{\mathbb{T}^{j-2}}\prod _{\ell=2}^{j-1}G_{N,r}^{[1]}(x_{\ell}-y_{\ell})I_{x_{j},\ldots,x_{d}}(y_{1}, \ldots,y_{j-1})dy_{2}\ldots dy_{j-1}\right|.\]

We have by iteration

\[\sup_{x_{1},\ldots,x_{j-1}\in\mathbb{T}}\left|\int_{\mathbb{T}^{ j-1}}\prod_{\ell=1}^{j-1}G_{N,r}^{[1]}(x_{\ell}-y_{\ell})I_{x_{j},\ldots,x_{d}}(y _{1},\ldots,y_{j-1})dy_{1}\ldots dy_{j-1}\right|\] \[\leq 2^{r(j-1)}\sup_{y_{1},\ldots,y_{j-1}\in\mathbb{T}}\left|I_{x_{j},\ldots,x_{d}}(y_{1},\ldots,y_{j-1})\right|.\]

But \(I_{x_{j},\ldots,x_{d}}(y_{1},\ldots,y_{j-1})=J_{N,r}^{[1]}(h,x_{j})-h(x_{j})\) where \(h\) is the univariate function \(h=f(y_{1},\ldots,y_{j-1},\cdot,x_{j+1},\ldots,x_{d})\) indexed by \(y_{1},\ldots,y_{j-1},x_{j+1},\ldots,x_{d}\). Hence, by (3.3),

\[\left|I_{x_{j},\ldots,x_{d}}(y_{1},\ldots,y_{j-1})\right|\leq C_{4}(r)\|h^{(r )}\|_{L_{\infty}(\mathbb{T})}N^{-r}.\]

Observe that \(\|h^{(r)}\|_{L_{\infty}(\mathbb{T})}\leq\|f\|_{W^{r}_{\infty}(\mathbb{T}^{d})}\). Therefore, the bound \(C_{4}(r)\|f\|_{W^{r}_{\infty}(\mathbb{T}^{d})}N^{-r}\) for \(\left|I_{x_{j},\ldots,x_{d}}(y_{1},\ldots,y_{j-1})\right|\) is independent of \(y_{1},\ldots,y_{j-1},x_{j},\ldots,x_{d}\), and we obtain

\[\|J_{N,r}(f)-f\|_{L_{\infty}(\mathbb{T}^{d})}\leq\sum_{j=1}^{d}2^{r(j-1)}C_{4 }(r)\|f\|_{W^{r}_{\infty}(\mathbb{T}^{d})}N^{-r}\leq d2^{rd}C_{4}(r)\|f\|_{W^{r }_{\infty}(\mathbb{T}^{d})}N^{-r}. \tag{3.8}\]

Shallow ReLU neural networks can approximate the function \(J_{N,r}(f)\) well with error bounds stated in terms of its Fourier coefficients.
**Lemma 1**.: _For \(k\in\mathbb{Z}^{d}\), let \(\widehat{J_{N}}(k)\) be the Fourier coefficient of \(J_{N,r}(f)\) at \(k\) satisfying_

\[J_{N,r}(f,x)=\sum\limits_{k\in\mathbb{Z}^{d}}\widehat{J_{N}}(k)e^{ik\cdot x}.\]

_Then for each \(m\in\mathbb{N}\), there exists a function \(f_{m}(x)=\sum\limits_{k=1}^{m}\beta_{k}\sigma(\alpha_{k}\cdot x-b_{k})\in H_{m}\) such that_

\[\|J_{N,r}(f)-f_{m}\|_{L_{\infty}(D)}\leq C_{5}v_{J_{N},2}\max\left\{\sqrt{\log m },\sqrt{d}\right\}m^{-\frac{1}{2}-\frac{1}{d}}, \tag{3.9}\]

_where \(C_{5}\) is an absolute constant,_

\[v_{J_{N},2}:=\sum\limits_{k\in\mathbb{Z}^{d}}|\widehat{J_{N}}(k)|\|k\|_{1}^{2}, \tag{3.10}\]

_and \(\beta_{k},b_{k}\in\mathbb{R}\), \(\alpha_{k}\in\mathbb{R}^{d}\) can be bounded as_

\[|\beta_{k}|\leq\frac{8\pi^{2}v_{J_{N},2}}{m},\qquad\|\alpha_{k}\|_{1}\leq 1, \qquad 0\leq b_{k}\leq 1,\qquad\forall\ k=1,\ldots,m.\]

The proof of Lemma 1 is similar to that in [21] and is given in details in the appendix.

The Jackson operator used in this paper may be replaced by some other approximation schemes of the form \(I_{N}(f)=\int_{\mathbb{T}^{d}}G_{N}(\cdot,y)f(y)dy\), where \(G_{N}\) is a family of kernels with a scaling index \(N\). What is challenging is to approximate \(I_{N}(f)\) by the output \(f_{m}\) of a shallow network induced by ReLU and to estimate the error. This is realized in our approach by a key identity (5.3) for the function \(e^{iz}\) valid in the range \(|z|\leq c\) and a concentration inequality for suprema of empirical processes followed by a novel bound for the quantity \(v_{J_{N},2}\) given in the next section. Another possible approach [27] is to use some kernels defined by formulae (6.1), (6.26) in [6] and then apply the related estimates given in Lemma 6.1 and Proposition 4.1 there. It would be interesting to use such an approach and derive rates of approximating \(F\in W_{\infty}^{r}(D)\) with a non-integer index \(r>0\), which extends our result in Theorem 1.

## 4 Proof of the Main Results by Fourier Analysis

The key analysis of this paper concentrates on estimating the quantity \(v_{J_{N},2}\).

Recall \(\widehat{J_{N}}(k)=(2\pi)^{d}a_{k,N}\hat{f}(k)\) is nonzero only when \(\|k\|_{\infty}\leq N\) by (3.7). Let \(L=\lceil\log_{2}N\rceil\), where \(\lceil u\rceil\) denotes the smallest integer no less than \(u>0\). Then \(N\leq 2^{L}\leq 2N\). Applying (3.5) to \(a_{k,N}=\prod\limits_{j=1}^{d}a_{k_{j},N}^{[1]}\) and noticing the term with \(k=0\) vanishes, we have

\[v_{J_{N},2}\leq(2^{r+1}\pi C_{3}(r))^{d}\sum\limits_{k\in\mathbb{Z}^{d}}|\hat {f}(k)|\|k\|_{1}^{2}\leq(2^{r+1}\pi C_{3}(r))^{d}\sum\limits_{\ell=0}^{L}\sum \limits_{2^{\ell-1}<\|k\|_{\infty}\leq 2^{\ell}}|\hat{f}(k)|\|k\|_{1}^{2}.\]
If \(r\geq 2\), by \(\|k\|_{1}\geq\|k\|_{\infty}\), we have \(\|k\|_{1}^{2-r}\leq\|k\|_{\infty}^{2-r}\leq(2^{\ell-1})^{2-r}\) when \(2^{\ell-1}<\|k\|_{\infty}\leq 2^{\ell}\). If \(r=1\), we also have \(\|k\|_{1}^{2-r}\leq d\|k\|_{\infty}^{2-r}\leq d(2^{\ell})=2d(2^{\ell-1})^{2-r}\) when \(2^{\ell-1}<\|k\|_{\infty}\leq 2^{\ell}\). Hence, in either case,

\[v_{J_{N},2}\leq 2d(2^{r+1}\pi C_{3}(r))^{d}\sum_{\ell=0}^{L}(2^{\ell-1})^{2-r} \sum_{2^{\ell-1}<\|k\|_{\infty}\leq 2^{\ell}}|\hat{f}(k)|\|k\|_{1}^{r}. \tag{4.1}\]

Inspired by some methods in harmonic analysis [12, 34, 5, 14], we define a collection of new functions on \(\mathbb{T}^{d}\), which is the novelty of our time-frequency anlaysis and plays a key role in our error decomposition: for \(\ell=1,\ldots,L\), let

\[T_{\ell}f(x)=\sum_{\|k\|_{\infty}\leq 2^{\ell}}\hat{f}(k)\|k\|_{1}^{r}e^{ik \cdot x},\qquad x\in\mathbb{T}^{d}.\]

The problem of bounding \(v_{J_{N},2}\) is then transformed to that of bounding \(\sum\limits_{k\in\mathbb{Z}^{d}}|\widehat{T_{\ell}f}(k)|\), where \(\widehat{T_{\ell}f}(k)=\hat{f}(k)\|k\|_{1}^{r}\) are the Fourier coefficients of \(T_{\ell}f\).

By Parseval's identity,

\[(2\pi)^{-d}\int_{\mathbb{T}^{d}}|T_{\ell}f(x)|^{2}dx=\sum_{k\in\mathbb{Z}^{d}} |\widehat{T_{\ell}f}(k)|^{2},\]

we have

\[\sum_{k\in\mathbb{Z}^{d}}|\widehat{T_{\ell}f}(k)|= \sum_{\|k\|_{\infty}\leq 2^{\ell}}|\widehat{T_{\ell}f}(k)|\leq \left(\sum_{\|k\|_{\infty}\leq 2^{\ell}}|\widehat{T_{\ell}f}(k)|^{2}\right)^{1/2} \left(\sum_{\|k\|_{\infty}\leq 2^{\ell}}1^{2}\right)^{1/2}\] \[\leq \left(2^{\ell+1}+1\right)^{\frac{d}{2}}\left((2\pi)^{-d}\int_{ \mathbb{T}^{d}}|T_{\ell}f(x)|^{2}dx\right)^{1/2}\leq(2^{\ell+1}+1)^{\frac{d}{2 }}\|T_{\ell}f\|_{\infty}. \tag{4.2}\]

Thus we only need to estimate \(\|T_{\ell}f\|_{\infty}\) to obtain an upper bound for \(v_{J_{N},2}\). This is the main analysis in the proof of our main results. It would be interesting to extend our analysis to some other machine learning algorithms which involve spectral decompositions and frequency analysis [15, 19, 20].

Proof of Theorem 1.: Our analysis is based on dividing the set

\[U_{\ell}:=\left\{-2^{\ell},-2^{\ell}+1,\ldots,2^{\ell}-1,2^{\ell}\right\}^{d}\]

into disjoint subsets according to the signs of its components as

\[U_{\ell}=\bigcup_{\epsilon\in\{-1,0,1\}^{d}}\Xi_{\epsilon}, \tag{4.3}\]
where for each \(\epsilon=(\epsilon_{1},\ldots,\epsilon_{d})\in\{-1,0,1\}^{d}\),

\[\Xi_{\epsilon}=\left\{k=(k_{1},\ldots,k_{d})\in U_{\ell}:\ \operatorname{sgn}(k_{j})= \epsilon_{j},\ \forall j=1,\ldots,d\right\}.\]

Then

\[T_{\ell}f(x)=\sum\limits_{\epsilon\in\{-1,0,1\}^{d}}\sum\limits_{k\in\Xi_{ \epsilon}}\hat{f}(k)\|k\|_{1}^{r}e^{ik\cdot x}.\]

Observe from the multinomial formula that for \(k\in\Xi_{\epsilon}\),

\[\|k\|_{1}^{r} =\left(\sum\limits_{j=1}^{d}|k_{j}|\right)^{r}=\left(\sum\limits_{ j=1}^{d}\epsilon_{j}k_{j}\right)^{r}\] \[=\sum\limits_{\begin{subarray}{c}\alpha_{1}+\cdots+\alpha_{d}=r \\ \alpha_{1},\ldots,\alpha_{d}\in\mathbb{Z}_{+}\end{subarray}}\frac{r!}{\alpha_{ 1}!\ldots\alpha_{d}!}\prod\limits_{j=1}^{d}(\epsilon_{j}k_{j})^{\alpha_{j}},\]

where \(\epsilon_{j}^{\alpha_{j}}\) denotes \(1\) when \(\epsilon_{j}=0\), \(\alpha_{j}=0\). So, for each \(\epsilon\in\{-1,0,1\}^{d}\),

\[\sum\limits_{k\in\Xi_{\epsilon}}\hat{f}(k)\|k\|_{1}^{r}e^{ik\cdot x}\] \[=\sum\limits_{\begin{subarray}{c}\alpha_{1}+\cdots+\alpha_{d}=r \\ \alpha_{1},\ldots,\alpha_{d}\in\mathbb{Z}_{+}\end{subarray}}\frac{r!}{\alpha_{ 1}!\ldots\alpha_{d}!}\left(\prod\limits_{j=1}^{d}\epsilon_{j}^{\alpha_{j}} \right)\left(\sum\limits_{k\in\Xi_{\epsilon}}\left(\prod\limits_{j=1}^{d}k_{j }^{\alpha_{j}}\right)\hat{f}(k)e^{ik\cdot x}\right). \tag{4.4}\]

Putting \(\hat{f}(k)=(2\pi)^{-d}\int_{\mathbb{T}^{d}}f(t)e^{-ik\cdot t}dt\) into the above sum over \(\Xi_{\epsilon}\), we have

\[\sum\limits_{k\in\Xi_{\epsilon}}\left(\prod\limits_{j=1}^{d}k_{j }^{\alpha_{j}}\right)\hat{f}(k)e^{ik\cdot x}=(2\pi)^{-d}\sum\limits_{k\in\Xi_ {\epsilon}}e^{ik\cdot x}\int_{\mathbb{T}^{d}}\left(\prod\limits_{j=1}^{d}k_{j }^{\alpha_{j}}\right)f(t)e^{-ik\cdot t}dt\] \[= (2\pi)^{-d}\sum\limits_{k\in\Xi_{\epsilon}}\int_{\mathbb{T}^{d} }(-i)^{r}\frac{\partial^{r}f}{\partial x_{1}^{\alpha_{1}}\ldots\partial x_{d}^ {\alpha_{d}}}(t)e^{ik\cdot(x-t)}dt\] \[= (2\pi)^{-d}(-i)^{r}\int_{\mathbb{T}^{d}}\frac{\partial^{r}f}{ \partial x_{d}^{\alpha_{d}}\ldots\partial x_{1}^{\alpha_{1}}}(t)\prod\limits _{j=1}^{d}\left(\sum\limits_{k_{j}\in\Xi_{\epsilon}^{[j]}}e^{ik_{j}(x_{j}-t_{ j})}\right)dt, \tag{4.5}\]

where \(\widetilde{\Xi}_{\epsilon}^{[j]}=\left\{\gamma\in\{-2^{\ell},\ldots,2^{\ell} \}:\ \operatorname{sgn}(\gamma)=\epsilon_{j}\right\}\) for \(j\in\{1,\ldots,d\}\).

If \(\epsilon_{j}=1\) or \(-1\), then \(\sum\limits_{k_{j}\in\Xi_{\epsilon}^{[j]}}e^{ik_{j}(x_{j}-t_{j})}\) equals to \(\sum\limits_{\beta=1}^{2^{\ell}}e^{i\epsilon_{j}\beta(x_{j}-t_{j})}\). Observe that

\[\int_{\mathbb{T}}\left|\sum\limits_{\beta=1}^{2^{\ell}}e^{i\beta t }\right|dt \leq \int_{\mathbb{T}}\left|\sum\limits_{\beta=1}^{2^{\ell}}\cos\beta t \right|dt+\int_{\mathbb{T}}\left|\sum\limits_{\beta=1}^{2^{\ell}}\sin\beta t \right|dt\] \[= \int_{\mathbb{T}}\left|\sum\limits_{\beta=1}^{2^{\ell}}\cos\beta t \right|dt+\int_{\mathbb{T}}\left|\frac{2\sin\frac{2^{\ell}+1}{2}t}{2\sin\frac{ t}{2}}\sin 2^{\ell-1}t\right|dt.\]
Hence

\[\int_{\mathbb{T}}\left|\sum_{\beta=1}^{2^{\ell}}e^{i\beta t}\right|dt \leq \int_{\mathbb{T}}\left|\frac{1}{2}+\sum_{\beta=1}^{2^{\ell}}\cos \beta t-\frac{1}{2}\right|dt+\int_{\mathbb{T}}\left|\frac{\sin\frac{2^{\ell}+1}{ 2}t}{\sin\frac{t}{2}}\right|dt\] \[\leq \int_{\mathbb{T}}\left|\frac{1}{2}D_{2^{\ell}}(t)-\frac{1}{2} \right|dt+\int_{\mathbb{T}}\left|D_{2^{\ell-1}}(t)\right|dt,\]

where \(D_{n}\) with \(n\in\mathbb{N}\) is the Dirichlet kernel on \(\mathbb{T}\) given by \(D_{n}(t)=1+2\sum\limits_{k=1}^{n}\cos kt\). Since the Dirichlet kernel can be bounded [9] as \(\|D_{n}\|_{1}\leq(\frac{4}{\pi}\log n+2\pi+1)\), we have

\[\int_{\mathbb{T}}\left|\sum_{k_{j}\in\Xi_{\epsilon}^{[j]}}e^{ik_{j}(x_{j}-t_{j })}\right|dt=\int_{\mathbb{T}}\left|\sum_{\beta=1}^{2^{\ell}}e^{i\beta t} \right|dt\leq\pi+\frac{1}{2}\|D_{2^{\ell}}\|_{1}+\|D_{2^{\ell-1}}\|_{1}\leq( 4\pi+2)(\ell+1).\]

If \(\epsilon_{j}=0\), the term in (4.4) with \(\alpha_{j}>0\) vanishes. When \(\alpha_{j}=0\), by (3.5),

\[\sum_{k_{j}\in\Xi_{\epsilon}^{[j]}}e^{ik_{j}(x_{j}-t_{j})}=1.\]

Therefore, we can bound the \(L_{1}\)-norm of the product term in (4.5) as

\[\int_{\mathbb{T}^{d}}\left|\prod_{j=1}^{d}\left(\sum_{k_{j}\in\Xi_{\epsilon}^{ [j]}}e^{ik_{j}(x_{j}-t_{j})}\right)\right|dt=\prod_{j=1}^{d}\int_{\mathbb{T}} \left|\sum_{k_{j}\in\Xi_{\epsilon}^{[j]}}e^{ik_{j}(x_{j}-t_{j})}\right|dt_{j} \leq(4\pi+2)^{d}(\ell+1)^{d}.\]

Combining this with (4.4) and (4.5), we obtain

\[\left|\sum_{k\in\Xi_{\epsilon}}\hat{f}(k)\|k\|_{1}^{r}e^{ik\cdot x }\right|\leq\sum_{\begin{subarray}{c}\alpha_{1}+\cdots+\alpha_{d}=r\\ \alpha_{1},\ldots,\alpha_{d}\in\mathbb{Z}_{+}\end{subarray}}\frac{r!}{\alpha _{1}!\ldots\alpha_{d}!}\left|\sum_{k\in\Xi_{\epsilon}}\prod_{j=1}^{d}\epsilon _{j}^{\alpha_{j}}k_{j}^{\alpha_{j}}\hat{f}(k)e^{ik\cdot x}\right|\] \[\leq (2\pi)^{-d}\sum_{\begin{subarray}{c}\alpha_{1}+\cdots+\alpha_{d }=r\\ \alpha_{1},\ldots,\alpha_{d}\in\mathbb{Z}_{+}\end{subarray}}\frac{r!}{\alpha_{ 1}!\ldots\alpha_{d}!}(4\pi+2)^{d}\left\|\frac{\partial^{r}f}{\partial x_{d}^{ \alpha_{d}}\ldots\partial x_{1}^{\alpha_{1}}}\right\|_{\infty}(\ell+1)^{d}.\]

It follows that

\[\|T_{\ell}f\|_{\infty}\leq C_{6}(d,r)\|f\|_{W^{r}_{\infty}(\mathbb{T}^{d})}( \ell+1)^{d}, \tag{4.6}\]

where \(C_{6}(d,r):=3^{d}(2\pi)^{-d}\sum\limits_{\begin{subarray}{c}\alpha_{1}+\cdots +\alpha_{d}=r\\ \alpha_{1},\ldots,\alpha_{d}\in\mathbb{Z}_{+}\end{subarray}}\frac{r!}{\alpha _{1}!\ldots\alpha_{d}!}(4\pi+2)^{d}=(\frac{3}{\pi}+6)^{d}d^{r}\).
Combining (4.1), (4.2), and (4.6) yields

\[v_{J_{N},2} \leq 2d(2^{r+1}\pi C_{3}(r))^{d}\sum_{\ell=0}^{L}(2^{\ell-1})^{2-r}\sum_ {k\in\mathbb{Z}^{d}}|\widehat{T_{\ell}f}(k)|\] \[\leq 2d(2^{r+1}\pi C_{3}(r))^{d}C_{6}(d,r)\|f\|_{W^{r}_{\infty}( \mathbb{T}^{d})}\sum_{\ell=0}^{L}(2^{\ell-1})^{2-r}(2^{\ell+1}+1)^{\frac{d}{2}} (\ell+1)^{d}\] \[\leq 2d(2^{r+1}\pi C_{3}(r))^{d}C_{6}(d,r)\|f\|_{W^{r}_{\infty}( \mathbb{T}^{d})}2^{r-2}\times 3^{\frac{d}{2}}\sum_{\ell=0}^{L}(\ell+1)^{d}(2^{ \ell})^{\frac{d}{2}+2-r}.\]

For \(r<\frac{d}{2}+2\), we have \(\frac{d}{2}+2-r>0\). But \(r\in\mathbb{N}\). Hence \(\frac{d}{2}+2-r\geq\frac{1}{2}\). It follows that

\[\sum_{\ell=0}^{L}(\ell+1)^{d}(2^{\ell})^{\frac{d}{2}+2-r}\leq(L+1 )^{d}\sum_{\ell=0}^{L}(2^{\ell})^{\frac{d}{2}+2-r}\] \[= (L+1)^{d}\frac{2^{\frac{d}{2}+2-r}}{2^{\frac{d}{2}+2-r}-1}\cdot \frac{\left(2^{\frac{d}{2}+2-r}\right)^{L+1}-1}{2^{\frac{d}{2}+2-r}}\leq(\log _{2}N+2)^{d}\frac{\sqrt{2}}{\sqrt{2}-1}(2^{\frac{d}{2}+2-r})^{L}\] \[\leq \frac{\sqrt{2}}{\sqrt{2}-1}(\log_{2}N+2)^{d}(2N)^{\frac{d}{2}+2- r}.\]

For \(r=\frac{d}{2}+2\),

\[\sum_{\ell=0}^{L}(\ell+1)^{d}(2^{\ell})^{\frac{d}{2}+2-r}=\sum_{\ell=0}^{L}( \ell+1)^{d}\leq(L+1)^{d+1}\leq(\log_{2}N+2)^{d+1}.\]

For \(r>\frac{d}{2}+2\), we estimate the sum

\[\sum_{\ell=0}^{L}(\ell+1)^{d}(2^{\ell})^{\frac{d}{2}+2-r}=\sum_{\ell=0}^{L} \left\{(\ell+1)^{d}\left[2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}\right]^{- \ell}\cdot\left[2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}\right]^{-\ell}\right\}\]

via bounding the factor \((\ell+1)^{d}\left[2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}\right]^{-\ell}\), \(\ell\in\{0,1,\ldots,L\}\), by \(\max_{0\leq\ell\leq L}\left\{(\ell+1)^{d}\left[2^{\frac{1}{2}\left(r-\frac{d}{ 2}-2\right)}\right]^{-\ell}\right\}\), and the sum of the remaining terms as

\[\sum_{\ell=0}^{L}\left[2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}\right]^{- \ell}\leq 1+\int_{0}^{L}\left[2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)} \right]^{-t}dt\leq 1+\frac{2}{(r-2-\frac{d}{2})\log 2}.\]

To estimate the above maximum value, we consider a function \(h:(-1,\infty)\rightarrow\mathbb{R}\) given by

\[h(t)=(t+1)^{d}\left[2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}\right]^{-t}.\]
From the derivative \(h^{\prime}(t)=(t+1)^{d-1}\left[2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}\right]^ {-t}\left\{d-(t+1)\log 2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}\right\}\), we see that \(h\) increases on \((-1,t^{*})\) with \(t^{*}=-1+d/\left(\frac{1}{2}\left(r-\frac{d}{2}-2\right)\log 2\right)\), achieves its maximum value at \(t^{*}\), and then decreases on \((t^{*},\infty)\). Hence

\[\max_{0\leq\ell\leq L}\left\{(\ell+1)^{d}\left[2^{\frac{1}{2}\left(r-\frac{d}{ 2}-2\right)}\right]^{-\ell}\right\}\leq h(t^{*})\leq\left(\frac{2d}{\left(r- \frac{d}{2}-2\right)\log 2}\right)^{d}2^{\frac{1}{2}\left(r-\frac{d}{2}-2 \right)}.\]

Therefore,

\[\sum_{\ell=0}^{L}(\ell+1)^{d}(2^{\ell})^{\frac{d}{2}+2-r}\leq\left(1+\frac{2} {\left(r-2-\frac{d}{2}\right)\log 2}\right)\left(\frac{2d}{\left(r-\frac{d}{2}-2 \right)\log 2}\right)^{d}2^{\frac{1}{2}\left(r-\frac{d}{2}-2\right)}.\]

Together with (3.8) and (3.9), the above estimates yield

\[\|f-f_{m}\|_{L_{\infty}(D)} \leq \|f-J_{N,r}(f)\|_{L_{\infty}(D)}+\|J_{N,r}(f)-f_{m}\|_{L_{\infty}( D)}\] \[\leq d2^{rd}C_{4}(r)\|f\|_{W^{r}_{\infty}(\mathbb{T}^{d})}N^{-r}+ \frac{2\sqrt{2}}{\sqrt{2}-1}d6^{\frac{d}{2}}(2^{r+1}\pi C_{3}(r))^{d}C_{5}C_{6 }(d,r)\] \[\times \|f\|_{W^{r}_{\infty}(\mathbb{T}^{d})}\max\left\{\sqrt{d},\sqrt{ \log m}\right\}m^{-\frac{1}{2}-\frac{1}{d}}\] \[\times \left\{\begin{array}{ll}(\log_{2}N+2)^{d}N^{\frac{d}{2}+2-r},& \mbox{if }r<\frac{d}{2}+2,\\ (\log_{2}N+2)^{d+1},&\mbox{if }r=\frac{d}{2}+2,\\ \left(1+\frac{2}{\left(r-2-\frac{d}{2}\right)\log 2}\right)\left(\frac{2d}{ \left(r-\frac{d}{2}-2\right)\log 2}\right)^{d}2^{\frac{3}{2}\left(r-\frac{d}{2}-2 \right)},&\mbox{if }r>\frac{d}{2}+2.\end{array}\right.\]

Finally, by choosing \(N=\lfloor m^{\frac{1}{d}(\frac{d+2}{\max\left(2r,d+4\right)})}\rfloor\) and noting \(\|f\|_{W^{r}_{\infty}(\mathbb{T}^{d})}\leq C_{2}(d,r)\|F\|_{W^{r}_{\infty}(D)}\), we have

\[\|f-f_{m}\|_{L_{\infty}(D)}\leq C(d,r)\|F\|_{W^{r}_{\infty}(D)}\left\{ \begin{array}{ll}(\log m)^{\frac{1}{2}+d}m^{-\frac{r}{d}\frac{d+2}{d+4}},& \mbox{if }r<\frac{d}{2}+2,\\ (\log m)^{\frac{3}{2}+d}m^{-\frac{r}{d}\frac{d+2}{d+4}},&\mbox{if }r=\frac{d}{2}+2,\\ (\log m)^{\frac{1}{2}}m^{-\frac{1}{2}-\frac{1}{d}},&\mbox{if }r>\frac{d}{2}+2, \end{array}\right.\]

where

\[C(d,r)= 2dC_{2}(d,r)2^{rd}C_{4}(r)+\frac{2\sqrt{2}d}{\sqrt{2}-1}6^{ \frac{d}{2}}C_{2}(d,r)(2^{r+1}\pi C_{3}(r))^{d}C_{5}C_{6}(d,r)\sqrt{d}\] \[\times\left\{\begin{array}{ll}1,&\mbox{if }r\leq\frac{d}{2}+2,\\ \left(1+\frac{2}{\left(r-2-\frac{d}{2}\right)\log 2}\right)\left(\frac{2d}{ \left(r-\frac{d}{2}-2\right)\log 2}\right)^{d}2^{\frac{3}{2}\left(r-\frac{d}{2}-2 \right)},&\mbox{if }r>\frac{d}{2}+2.\end{array}\right.\]

Since \(f=F\) on \(D\), this verifies the desired estimate (2.1) and completes the proof of the theorem.
As pointed out by a referee, another way to bound \(T_{\ell}f(x)\) is to view \(e^{ik\cdot x}\) as a univiate function of the variable \(k\cdot x\) and express it using a \(2\pi\) periodic function which equals the hat function on \([-1,1]\) and vanishes on \([-\pi,\pi]\setminus[-1,1]\). Then some probability estimates might be used to carry out the analysis.

We can now apply Theorem 1 and the construction in [38, 37, 39] to prove our rates of approximation by deep CNNs.

Proof of Corollary 1.: Let \(J\geq\frac{2d}{s-1}\) and \(m=\lfloor\frac{(s-1)J}{d}-1\rfloor\). By Theorem 1, we have \(f_{m}\in H_{m}\) with \(f_{m}(x)=\sum\limits_{i=1}^{m}\beta_{i}\sigma(\alpha_{i}\cdot x-t_{i})\) on \(D\) such that

\[\|F-f_{m}\|_{L_{\infty}(D)}\leq\left\{\begin{array}{ll}C(d,r)\|F\|_{W^{r}_{ \infty}(D)}(\log m)^{\frac{1}{2}+d}m^{-\frac{r}{d}\frac{d+2}{d+4}},&\mbox{if $r< \frac{d}{2}+2$},\\ C(d,r)\|F\|_{W^{r}_{\infty}(D)}(\log m)^{\frac{3}{2}+d}m^{-\frac{r}{d}\frac{d+ 2}{d+4}},&\mbox{if $r=\frac{d}{2}+2$},\\ C(d,r)\|F\|_{W^{r}_{\infty}(D)}(\log m)^{\frac{1}{2}}m^{-\frac{1}{2}-\frac{1}{ d}},&\mbox{if $r>\frac{d}{2}+2$}.\end{array}\right.\]

Now we realize \(f_{m}\) by an output function \(f_{J}^{\mathbf{w},\mathbf{b}}\) of a deep CNN of depth \(J\) constructed in [38, Proof of Theorem 2]. Precisely, first applying [38, Theorem 3] to the sequence \(W=(W_{k})_{-\infty}^{\infty}\) supported in \(\{0,\ldots,md-1\}\) with

\[[W_{md-1}\;\ldots\;W_{1}\;W_{0}]=[\alpha_{m}^{\top}\;\ldots\;\alpha_{2}^{\top }\;\alpha_{1}^{\top}],\]

adding delta filter sequences at the end if necessary, we can obtain filters \(\mathbf{w}=\{w^{(j)}\}_{j=1}^{J}\) supported in \(\{0,\ldots,s\}\) such that \(W=w^{(J)}*w^{(J-1)}*\cdots*w^{(2)}*w^{(1)}\).

Next, taking \(\mathbf{b}=\{b^{(j)}\}_{j=1}^{J-1}\) such that for \(j\in\{1,\ldots,J-1\}\) and \(x\in D\), the components of \(T^{w^{(j)}}h^{(j-1)}(x)-b^{(j)}\) are positive.

Finally, for \(k=1,\ldots,m\), let \(b^{(J)}_{kd}\) be the number which makes the constant term of \(\big{(}h^{(J)}(x)\big{)}_{kd}\) equals to \(t_{k}\). Taking \(c=\left(\sum\limits_{k=1}^{m}\beta_{k}\delta_{kd}(j)\right)_{j=1}^{d_{J}}\) with \(\delta_{i}\) being the delta sequence at \(i\) yields \(f_{J}^{\mathbf{w},\mathbf{b}}\). Then we have \(f_{J}^{\mathbf{w},\mathbf{b}}=f_{m}\). Combining this identity with the fact that \(\frac{1}{2}(s-1)J\leq md\leq(s-1)J\) gives

\[\|F-f_{J}^{\mathbf{w},\mathbf{b}}\|_{C(\Omega)}\leq\left\{\begin{array}{ll} C_{1}(d,r)\|F\|_{W^{r}_{\infty}(D)}(\log J)^{d+1/2}J^{-\frac{r}{d}\frac{d+2}{d+4}},& \mbox{if $r<\frac{d}{2}+2$},\\ C_{1}(d,r)\|F\|_{W^{r}_{\infty}(D)}(\log J)^{d+3/2}J^{-\frac{r}{d}\frac{d+2}{d+4} },&\mbox{if $r=\frac{d}{2}+2$},\\ C_{1}(d,r)\|F\|_{W^{r}_{\infty}(D)}(\log m)^{\frac{1}{2}}m^{-\frac{1}{2}-\frac{ 1}{d}},&\mbox{if $r>\frac{d}{2}+2$},\end{array}\right.\]

where \(C_{1}(d,r)=C(d,r)(2d)^{\frac{r}{d}\frac{d+2}{d+4}}\). This proves Corollary 1. 

## 5 Discussion

The rate of uniformly approximating functions \(f\in W^{r}_{\infty}([-1,1]^{d}))\) given in Theorem 1 is very close to the following lower bound [8, Theorem 4.2] for neural networks when the data dimension \(d\) is large:
_Let \(d,r\in\mathbb{N}\). Then there exists a constant \(c_{r}\) depending only on \(r\) such that for any \(n\in\mathbb{N}\), map \(\eta:\mathbb{R}^{n}\to C(D)\), and continuous map \(M:W^{r}_{\infty}([-1,1]^{d})\to\mathbb{R}^{n}\) there holds_

\[\sup_{\|f\|_{W^{r}_{\infty}([-1,1]^{d})}\leq 1}\|f-\eta(M(f))\|_{\infty}\geq c_{r}n^{-r/ d}.\]

We apply this lower bound to our setting. If we denote \(H^{p}_{m}\) with \(m\in\mathbb{N}\) to be the set of output functions \(f_{m}\) on \(D\) constructed by ReLU deep neural networks of depth \(p\) with \((d+1)m\) free parameters, then \(H^{1}_{m}=H_{m}\). Let \(A_{m}\) be the collection of these parameters. If there exists a continuous map \(M:W^{r}_{\infty}(D)\mapsto A_{m}\), then for any map \(\eta:A_{m}\to C(D)\) which together with \(M\) produces \(f_{m}=\eta(M(F))\) there holds

\[\sup_{\|F\|_{W^{r}_{\infty}(D)}\leq 1}\|F-f_{m}\|_{L_{\infty}(D)}\geq c_{r}m^{- \frac{r}{d}}. \tag{5.1}\]

We end our discussion by remarking that when \(r>d/2+2\), our main result correponds to that in [21]. This was used in [38]. To make it explicit, let

\[W^{r}_{2}(\mathbb{R}^{d}):=\left\{f\in L_{2}(\mathbb{R}^{d}):\ \|f\|_{W^{r}_{2}( \mathbb{R}^{d})}:=\int_{\mathbb{R}^{d}}\lvert\hat{f}(\omega)\rvert^{2}(1+| \omega|^{2r})d\omega<\infty\right\},\]

where \(\hat{f}(\omega)=(2\pi)^{-d}\int_{\mathbb{R}^{d}}f(x)e^{-i\omega\cdot x}d\omega\) is the Fourier transform of \(f\).

By the extension theorem, there exists a constant \(C_{7}(d,r)\) depending only on \(d\) and \(r\) such that each \(F\in W^{r}_{\infty}(D)\) can be extended to a function \(f\) in \(W^{r}_{2}(\mathbb{R}^{d})\) with

\[\|f\|_{W^{r}_{2}(\mathbb{R}^{d})}\leq C_{7}(d,r)\|F\|_{W^{r}_{2}(D)}\leq(2\pi)^ {d/2}C_{7}(d,r)\|F\|_{W^{r}_{\infty}(D)}.\]

Then \(r>d/2+2\) is a sufficient condition for the finiteness of \(v_{f,2}\) defined in [21] as

\[v_{f,2}:=\int_{\mathbb{R}^{d}}\lvert\hat{f}(\omega)\rvert\|\omega\|_{1}^{2}d \omega<\infty.\]

In fact, we have

\[v_{f,2}= \int_{D}\lvert\hat{f}(\omega)\rvert\|\omega\|_{1}^{2}d\omega+ \int_{\mathbb{R}^{d}\setminus D}\lvert\hat{f}(\omega)\rvert\|\omega\|_{1}^{2}d\omega\] \[\leq \left(\int_{D}d^{2}\lvert\hat{f}(\omega)\rvert^{2}\left|\omega \right|^{4}d\omega\cdot\int_{D}1d\omega\right)^{1/2}\] \[+\left(\int_{\mathbb{R}^{d}\setminus D}d^{2r}\lvert\hat{f}(\omega )\rvert^{2}\left|\omega\right|^{2r}d\omega\cdot\int_{\mathbb{R}^{d}\setminus D }\lVert\omega\rVert_{1}^{4-2r}d\omega\right)^{1/2}\] \[\leq C_{8}(d,r)\left(\int_{\mathbb{R}^{d}}\lvert\hat{f}(\omega) \rvert^{2}\left(1+|\omega|^{2r}\right)d\omega\right)^{1/2}\leq(2\pi)^{d/2}C_{ 7}(d,r)C_{8}(d,r)\|F\|_{W^{r}_{\infty}(D)},\]

where \(C_{8}(d,r)\) is a constant depending only on \(d\) and \(r\). Then for \(f\in W^{r}_{\infty}(D)\),

\[\inf_{f_{m}\in H_{m}}\lVert f-f_{m}\rVert_{L_{\infty}(D)}\leq C_{9}(d,r)\|f\|_{W^ {r}_{\infty}(D)}(\log m)^{\frac{1}{2}}m^{-\frac{1}{2}-\frac{1}{d}}, \tag{5.2}\]
where \(C_{9}(d,r)\) only depends on \(d\) and \(r\). This is the rate of approximation we obtained in (2.1).

When \(r=d/2+2\), we have \(-\frac{r}{d}\frac{d+2}{d+4}=-\frac{1}{2}-\frac{1}{d}\). Then the upper bound in Theorem 1 is the same as that in [21] up to a logarithmic term.

## Appendix

In this appendix, we provide a detailed proof of Lemma 1 for completeness. The method of the proof is borrowed from [21]. Here is an outline of the proof: we first represent the Fourier series basis function \(e^{ik\cdot x}\) as an integral of the shifts \(\sigma(k\cdot x-u)\) of the ReLU multiplied with \(e^{iu}\). Then we express the value at \(x\in D\) of the Jackson operator \(J_{N,r}(f,x)\) as the expectation of a random variable. Finally, we approximate the expectation by an empirical mean. The key part of the proof is to conduct Rademacher analysis for estimating the error between the expectation and the empirical mean, uniformly for \(x\in D\), by applying a concentration inequality for suprema of empirical processes to a collection of random variables indexed by the set \(D\times\{-1,0,1\}\).

Proof of Lemma 1.: The following identity stated as Equation (19) in [21]

\[e^{iz}-iz-1=-\int_{0}^{c}\sigma(z-u)e^{iu}+\sigma(-z-u)e^{-iu}du,\qquad|z|\leq c \tag{5.3}\]

applied to \(c=\|\pi k\|_{1}\) and \(z=k\cdot x\) with \(k\in\mathbb{Z}^{d}\setminus\{0\}\) yields

\[e^{ik\cdot x}=-\int_{0}^{\|\pi k\|_{1}}\sigma(k\cdot x-u)e^{iu}+\sigma(-k\cdot x -u)e^{-iu}du+ik\cdot x+1.\]

Changing the variable \(u\) by \(t=\frac{u}{\|\pi k\|_{1}}\) and using \(\frac{1}{\|\pi k\|_{1}}\sigma(v)=\sigma(\frac{v}{\|\pi k\|_{1}})\) for \(v\in\mathbb{R}\), we have

\[e^{ik\cdot x}=-\|\pi k\|_{1}^{2}\int_{0}^{1}\sigma\left(\frac{k}{\|\pi k\|_{1 }}\cdot x-t\right)e^{i\|\pi k\|_{1}t}+\sigma\left(-\frac{k}{\|\pi k\|_{1}} \cdot x-t\right)e^{-i\|\pi k\|_{1}t}dt+ik\cdot x+1.\]

Putting this expression into the Jackson operator \(J_{N,r}(f,x)=\sum\limits_{k\in\mathbb{Z}^{d}}\widehat{J_{N}}(k)e^{ik\cdot x}\), we find

\[J_{N,r}(f,x) = \sum\limits_{k\in\mathbb{Z}^{d}}\widehat{J_{N}}(k)\bigg{\{}-\|\pi k \|_{1}^{2}\int_{0}^{1}\sigma\left(\frac{k}{\|\pi k\|_{1}}\cdot x-t\right)e^{i \|\pi k\|_{1}t}\] \[+\sigma\left(-\frac{k}{\|\pi k\|_{1}}\cdot x-t\right)e^{-i\|\pi k \|_{1}t}dt\bigg{\}}+\sum\limits_{k\in\mathbb{Z}^{d}}\widehat{J_{N}}(k)(ik\cdot x +1).\]
Take a phase \(b(k)\in(-\pi,\pi]\) of the complex number \(\widehat{J_{N}}(k)\) satisfying

\[\widehat{J_{N}}(k)=|\widehat{J_{N}}(k)|e^{ib(k)}.\]

Then \(\widehat{J_{N}}(k)e^{\pm i\|\pi k\|_{1}t}=|\widehat{J_{N}}(k)|e^{i(\pm\|\pi k\|_ {1}t+b(k))}\). Notice that \(J_{N,r}(f,x)\) is a real number. Then by taking its real part, we have

\[J_{N,r}(f,x) = -\pi^{2}\sum_{k\in\mathbb{Z}^{d}\setminus\{0\}}|\widehat{J_{N}}(k )|\|k\|_{1}^{2}\int_{0}^{1}\sigma\left(\frac{k}{\|\pi k\|_{1}}\cdot x-t\right) \cos(\|\pi k\|_{1}t+b(k))dt\] \[-\pi^{2}\sum_{k\in\mathbb{Z}^{d}\setminus\{0\}}|\widehat{J_{N}}( k)|\|k\|_{1}^{2}\int_{0}^{1}\sigma\left(-\frac{k}{\|\pi k\|_{1}}\cdot x-t \right)\cos(-\|\pi k\|_{1}t+b(k))dt\] \[-\left[\sum_{k\in\mathbb{Z}^{d}}\mathrm{Im}(\widehat{J_{N}}(k)) k\right]\cdot x+\sum_{k\in\mathbb{Z}^{d}}\mathrm{Re}(\widehat{J_{N}}(k)).\]

To approximate the function \(J_{N,r}(f,x)\) by the output \(f_{m}(x)=\sum\limits_{k=1}^{m}\beta_{k}\sigma(\alpha_{k}\cdot x-b_{k})\in H_{m}\) of a shallow network, we regard \(J_{N,r}(f,x)\) as the expectation of a random variable, discretize it, and then estimate the error by a concentration inequality. Here \(x\in D\) is used as an index of a collection of random vaiables.

We first take a probability measure \(P\) on \(\{-1,1\}\times[0,1]\times\left(\mathbb{Z}^{d}\setminus\{0\}\right)\) by setting for \(z\in\{-1,1\},k\in\mathbb{Z}^{d}\setminus\{0\}\) the density as

\[p(z,t,k)=\frac{\pi^{2}}{v}|\widehat{J_{N}}(k)|\ \|k\|_{1}^{2}\ |\cos(z\|\pi k\|_{1} t+b(k))|,\qquad t\in[0,1],\]

where \(v\) is the normalization constant

\[v=\pi^{2}\sum_{k\in\mathbb{Z}^{d}}\left[\|k\|_{1}^{2}|\widehat{J_{N}}(k)|\int_ {0}^{1}|\cos(\|\pi k\|_{1}t+b(k))|+|\cos(-\|\pi k\|_{1}t+b(k))|dt\right]\leq 2 \pi^{2}v_{J_{N},2}.\]

We then define a collection of random variables \(\{h_{x}\}_{x\in D}\) on \(\{-1,1\}\times[0,1]\times\left(\mathbb{Z}^{d}\setminus\{0\}\right)\) given by

\[h_{x}(z,t,k)=\sigma(z\alpha\cdot x-t)s(zt,k),\qquad z\in\{-1,1\},t\in[0,1],k \in\mathbb{Z}^{d}\setminus\{0\}, \tag{5.4}\]

where \(\alpha=\alpha_{k}:=\frac{k}{\|\pi k\|_{1}}\) and \(s(t,k):=-\mathrm{sgn}(\cos(\|\pi k\|_{1}t+b(k)))\). For each \(x\in D\), the expected value \(\mathbb{E}_{P}[h_{x}]=\int_{\{-1,1\}\times[0,1]\times\left(\mathbb{Z}^{d} \setminus\{0\}\right)}h_{x}(z,t,k)dP(z,t,k)\) of the random variables \(h_{x}\) satisfies

\[J_{N,r}(f,x)+\left[\sum_{k\in\mathbb{Z}^{d}}\mathrm{Im}(\widehat {J_{N}}(k))k\right]\cdot x-\sum_{k\in\mathbb{Z}^{d}}\mathrm{Re}(\widehat{J_{N }}(k))\] \[= v\int_{\{-1,1\}\times[0,1]\times\mathbb{Z}^{d}\setminus\{0\}}h_{ x}(z,t,k)dP(z,t,k)=:g_{x}.\]
The rest of the proof is analogous to [21, Proof of Theorem 1], and we replace \(m\) by \(m^{\prime}=\lceil m/4\rceil\) here.

Let \(\epsilon>0\) to be determined later. We can partition the set \(\{(z,t,\alpha)\in\{-1,1\}\times[0,1]\times\mathbb{R}^{d}:\ \|\alpha\|_{1}=\pi^{-1}\}\) into a family of subsets \(\{\mathcal{A}_{j}\}_{j=1}^{M^{\prime}}\) of \(\ell^{\infty}\)-diameter at most \(\frac{\epsilon}{d+1}\), where the number \(M^{\prime}\) of the subsets in this family can be chosen to be the integer part of \(2\left(\frac{2d+2}{\pi}\right)^{d-1}(d+1)\epsilon^{-d}\). The diamater restriction yields

\[\sup_{(z,t,\alpha),(\tilde{z},\tilde{t},\tilde{\alpha})\in\mathcal{A}_{j}}\|( z,t,\alpha)-(\tilde{z},\tilde{t},\tilde{\alpha})\|_{\infty}\leq\frac{\epsilon}{d+ 1},\quad j=1,\ldots,M^{\prime},\]

which together with the Lipschitz property of \(\sigma\) implies

\[\sup_{x\in D}\left|\sigma(z\alpha\cdot x-t)-\sigma(\tilde{z}\tilde{\alpha} \cdot x-\tilde{t})\right|\leq\epsilon,\quad\forall(z,t,\alpha),(\tilde{z}, \tilde{t},\tilde{\alpha})\in\mathcal{A}_{j}.\]

For each \(j\), we denote two subsets of \(\{-1,1\}\times[0,1]\times\left(\mathbb{Z}^{d}\setminus\{0\}\right)\) as

\[\mathcal{A}_{j,-} = \left\{(z,t,k):\ \left(z,t,\frac{k}{\|\pi k\|_{1}}\right)\in \mathcal{A}_{j},\ s(zt,k)=-1\right\},\] \[\mathcal{A}_{j,+} = \left\{(z,t,k):\ \left(z,t,\frac{k}{\|\pi k\|_{1}}\right)\in \mathcal{A}_{j},\ s(zt,k)=1\right\},\]

and set the collection \(\{\mathcal{A}_{j,-},\mathcal{A}_{j,+}:j=1,\ldots,M^{\prime}\}\) as \(\{\mathcal{B}_{i}\}_{j=1}^{M}\) with \(M=2M^{\prime}\). Then \(\{\mathcal{B}_{1},\ldots,\mathcal{B}_{M}\}\) form a partition of the set \(\Lambda=\{-1,1\}\times[0,1]\times\left(\mathbb{Z}^{d}\setminus\{0\}\right)\) and satisfy

\[\sup_{(z,t,k),(\tilde{z},\tilde{t},\tilde{k})\in\mathcal{B}_{i}}\sup_{x\in D }\left|h_{x}\left(\tilde{z},\tilde{t},\tilde{k}\right)-h_{x}\left(z,t,k\right) \right|\leq\epsilon,\quad i=1,\ldots,M. \tag{5.5}\]

We restrict the probability measure \(P\) onto the subsets in this partition and define a collection of probability measures \(\{P_{i}\}_{i=1}^{M}\) on \(\Lambda\) by

\[dP_{i}(z,t,k)=\frac{1}{L_{i}}dP(z,t,k)\mathbf{1}\{(z,t,k)\in\mathcal{B}_{i}\},\]

where \(L_{i}=\int_{\mathcal{B}_{i}}dP(z,t,k)\) is the normalization constant to make \(P_{i}\) a probability measure. Correspondingly, we set \(m_{i}=m^{\prime}L_{i}\) and take a random sample

\[\underline{a}=\{(z_{j,i},t_{j,i},k_{j,i})\}_{1\leq j\leq n_{i},\ 1\leq i\leq M}\]

of sizes \(\{n_{i}=\lceil m_{i}\rceil\}\) independently according to \(\{P_{i}\}_{i=1}^{M}\). Thus, we split the population domain \(\Lambda\) into \(M\) "strata" \(\mathcal{B}_{1},\ldots,\mathcal{B}_{M}\) and allocate the number of within-stratum samples to be proportional to the "size" of the stratum \(m_{1},\ldots,m_{M}\) (i.e., proportionate allocation). Note from \(\sum\limits_{i=1}^{M}L_{i}=1\) that

\[\sum\limits_{i=1}^{M}n_{i}\leq m^{\prime}+M. \tag{5.6}\]
Let

\[g_{i,x}=\frac{v}{n_{i}}\sum_{j=1}^{n_{i}}h_{x}(z_{j,i},t_{j,i},k_{j,i}),\qquad i=1, \ldots,M\]

and

\[\overline{g}_{x}=\sum_{i=1}^{M}\frac{m_{i}}{m^{\prime}}g_{i,x}.\]

We apply \(L_{i}=m_{i}/m^{\prime}\) to get

\[\mathbb{E}\left[\sup_{x\in D}|\overline{g}_{x}-g_{x}|\right]= \mathbb{E}\left[\sup_{x\in D}\left|\sum_{i=1}^{M}L_{i}g_{i,x}-v\sum_{i=1}^{M}L_ {i}\int_{\mathcal{B}_{i}}h_{x}(z,t,k)dP_{i}(z,t,k)\right|\right] \tag{5.7}\] \[= \frac{v}{m^{\prime}}\mathbb{E}\left[\sup_{x\in D}\left|\sum_{i=1 }^{M}\frac{m_{i}}{n_{i}}\sum_{j=1}^{n_{i}}\left(h_{x}(z_{j,i},t_{j,i},k_{j,i}) -\mathbb{E}_{P_{i}}[h_{x}]\right)\right|\right].\]

To carry out Rademacher analysis for the quantity in (5.7), we let \(\underline{\sigma}=\{\sigma_{j,i}\}\) be a sequence of independent identically distributed Rademacher variables and \(\{\mu_{i}\}_{i=1}^{M}\) be a sequence of functions defined on \(D\) by \(\mu_{i}(x)=h_{x}(z_{i},t_{i},k_{i})\) with a random sample \((z_{i},t_{i},k_{i})\in\mathcal{B}_{i}\) drawn according to \(P_{i}\). We get from [35, Lemma 2.3.6] that

\[\mathbb{E}\left[\sup_{x\in D}\left|\sum_{i=1}^{M}\frac{m_{i}}{n_{ i}}\sum_{j=1}^{n_{i}}\left(h_{x}(z_{j,i},t_{j,i},k_{j,i})-\mathbb{E}_{P_{i}}[h_{ x}]\right)\right|\right] \tag{5.8}\] \[\leq 2\mathbb{E}\left[\sup_{x\in D}\left|\sum_{i=1}^{M}\frac{m_{i}}{ n_{i}}\sum_{j=1}^{n_{i}}\sigma_{j,i}\left(h_{x}(z_{j,i},t_{j,i},k_{j,i})-\mu_{i}(x) \right)\right|\right].\]

For notational brevity, we denote \(\tilde{h}_{j,i}(x)=\frac{m_{i}}{n_{i}}(h_{x}(z_{j,i},t_{j,i},k_{j,i})-\mu_{i}( x))\). Observe that \(\sup_{y\in\{-1,0,1\}}\left(\sum_{i=1}^{M}\sum_{j=1}^{n_{i}}\sigma_{j,i}y \tilde{h}_{j,i}(x)\right)=\left|\sum_{i=1}^{M}\sum_{j=1}^{n_{i}}\sigma_{j,i} \tilde{h}_{j,i}(x)\right|\). Fix \(\underline{a}\). We apply a concentration inequality [3, Corollary 13.2] for suprema of empirical processes involving a collection of random variables \(\left\{\sum\limits_{k=1}^{n}\alpha_{k,t}\epsilon_{k}:t\in\mathcal{T}\right\}\) induced by a sequence of independent Rademacher variables \(\{\epsilon_{k}\}_{k=1}^{n}\) and a collection of coefficient sequences \(\{\alpha_{k,t}\}_{k=1}^{n}\) indexed by a set \(\mathcal{T}\) with the distance \(\mbox{dist}(t,t^{\prime})=\left\{\sum_{k=1}^{n}\left(\alpha_{k,t}-\alpha_{k,t^ {\prime}}\right)^{2}\right\}^{1/2}\) for \(t,t^{\prime}\in\mathcal{T}\). In our situation, \(\underline{\sigma}=\{\sigma_{j,i}\}\) is the sequence of independent Rademacher variables. The collection of coefficient sequences is \(\left\{\left(y\tilde{h}_{j,i}(x)\right)_{j,i}:(x,y)\in\mathcal{T}\right\}\) indexed by the set \(\mathcal{T}:=D\times\{-1,0,1\}\) with the distance \(\kappa\) given by

\[\kappa\left((x,y),(x^{\prime},y^{\prime})\right)=\left(\sum_{i=1}^{M}\sum_{j=1 }^{n_{i}}\left(y\tilde{h}_{j,i}(x)-y^{\prime}\tilde{h}_{j,i}(x^{\prime})\right) ^{2}\right)^{1/2},\qquad(x,y),(x^{\prime},y^{\prime})\in\mathcal{T}.\]
Hence we can apply [3, Corollary 13.2] and obtain

\[\mathbb{E}_{\underline{\sigma}}\left[\sup_{x\in D}\left|\sum_{i=1}^ {M}\sum_{j=1}^{n_{i}}\sigma_{j,i}\tilde{h}_{j,i}(x)\right|\right] \tag{5.9}\] \[= \mathbb{E}_{\underline{\sigma}}\left[\sup_{(x,y)\in D\times\{-1, 0,1\}}\left(\sum_{i=1}^{M}\sum_{j=1}^{n_{i}}\sigma_{j,i}\tilde{y}\tilde{h}_{j, i}(x)\right)-0\right]\] \[\leq 12\int_{0}^{\delta/2}\sqrt{N(u,\mathcal{T})}du,\]

where \(N(u,\mathcal{T})\) is the \(u\)-metric entropy of \(\mathcal{T}\) with respect to the metric \(\kappa\) (i.e., the logarithm of the smallest size of \(u\)-nets that cover \(\mathcal{T}\) with respect to \(\kappa\)) and \(\delta=\left(\sup_{(x,y)\in D\times\{-1,0,1\}}\sum_{i=1}^{M}\sum_{j=1}^{n_{i}} \left(y\tilde{h}_{j,i}(x)\right)^{2}\right)^{1/2}\).

To estimate the metric entropy \(N(u,\mathcal{T})\), we observe from a simple covering of the interval \([-1,1]\) by \(1+1/\eta\) intervals of radius \(\eta>0\) that the cube \(D=[-1,1]^{d}\) can be covered by \((1+1/\eta)^{d}\leq(2/\eta)^{d}\) balls of radius \(\eta\) in the \(\ell_{\infty}\)-norm for \(\eta\leq 1\). Combining this with a metric relation

\[\kappa\left((x,y),(x^{\prime},y)\right)=|y|\left(\sum_{i=1}^{M}\sum_{j=1}^{n_{ i}}\left(\tilde{h}_{j,i}(x)-\tilde{h}_{j,i}(x^{\prime})\right)^{2}\right)^{1/2} \leq 2\sqrt{m^{\prime}+M}\|x-x^{\prime}\|_{\infty}\]

seen from the Lipschitz property of \(\sigma\) and the definition of \(\tilde{h}_{j,i}\), we find that any \(\eta\)-covering of \(D\) with respect to the \(\ell_{\infty}\)-norm induces a \(2\sqrt{m^{\prime}+M}\eta\) covering of \(D\times\{y\}\) with respect to the \(\kappa\)-metric. Therefore, by taking \(\eta=u/(2\sqrt{m^{\prime}+M})\leq\frac{\delta}{2}/(2\sqrt{m^{\prime}+M})<1\), for the covering numbers \(\mathcal{N}(u,D\times\{y\})\) and \(\mathcal{N}(u,\mathcal{T})\), we have

\[\mathcal{N}(u,D\times\{y\})\leq(2/\eta)^{d}\leq\left(\frac{4\sqrt{m^{\prime}+ M}}{u}\right)^{d}\]

and

\[\mathcal{N}(u,\mathcal{T})\leq\sum_{y\in\{1,0,-1\}}\mathcal{N}(u,D\times\{y\}) \leq 3\left(\frac{4\sqrt{m^{\prime}+M}}{u}\right)^{d}. \tag{5.10}\]

It follows from (5.5) and (5.6) that \(\delta\leq\sqrt{m^{\prime}+M}\epsilon\) and from (5.10) that \(N(u,\mathcal{T})\leq d\log\left(4\sqrt{m^{\prime}+M}/u\right)+\log 3\).

Now we determine \(\epsilon>0\) by

\[\epsilon=\frac{2(d+1)\pi^{-1+1/d}}{\lceil m/4\rceil^{1/d}}.\]
This choice together with the definition of \(M^{\prime}\) gives \(M^{\prime}=2\left((2d+2)/\pi\right)^{d-1}\left(d+1\right)\epsilon^{-d}=\lceil m/4\rceil\). Hence \(M^{\prime}=m^{\prime}=\lceil m/4\rceil\) and \(M=2M^{\prime}=2\lceil m/4\rceil\). Then by evaluating the integral, we can bound (5.9) as

\[\mathbb{E}_{\underline{\sigma}}\left[\sup_{x\in D}\left|\sum_{i=1}^{M}\sum_{j=1 }^{n_{i}}\sigma_{j,i}\tilde{h}_{j,i}(x)\right|\right]\leq 12(3+2\sqrt{\log m}) \sqrt{d}\sqrt{\frac{m}{2}}\epsilon. \tag{5.11}\]

Thus by taking expection over \(\underline{a}\in\Lambda\), we obtain

\[\mathbb{E}\left[\sup_{x\in D}\left|\sum_{i=1}^{M}\frac{m_{i}}{n_ {i}}\sum_{j=1}^{n_{i}}\sigma_{j,i}\left(h_{x}(z_{j,i},t_{j,i},k_{j,i})-\mu_{i }(x)\right)\right|\right] \tag{5.12}\] \[= \mathbb{E}_{\underline{a}}\mathbb{E}_{\underline{\sigma}}\left[ \sup_{x\in D}\left|\sum_{i=1}^{M}\sum_{j=1}^{n_{i}}\sigma_{j,i}\tilde{h}_{j,i }(x)\right|\right]\leq 12(3+2\sqrt{\log m})\sqrt{d}\sqrt{\frac{m}{2}}\epsilon.\]

Together with (5.7) and (5.8), we conclude that

\[\mathbb{E}\left[\sup_{x\in D}|\overline{g}_{x}-g_{x}|\right]\leq\frac{C_{5}}{ 2\pi^{2}}vd^{3/2}\sqrt{\log mm}^{-\frac{1}{2}-\frac{1}{d}} \tag{5.13}\]

holds for some absolute constant \(C_{5}\). Since this inequation holds on average, by (5.6) we know that there is a realization

\[\overline{g}_{x}=\sum_{i=1}^{M}\sum_{j=1}^{n_{i}}\frac{vm_{i}}{m^{\prime}n_{i} }h_{x}(z_{j,i},t_{j,i},\omega_{j,i})=:\sum_{k=1}^{3\lceil m/4\rceil}\beta_{k} \sigma(\alpha_{k}\cdot x-b_{k})\in H_{3\lceil m/4\rceil}\]

such that

\[\sup_{x\in D}\left|J_{N,r}(f,x)+\left[\sum_{k\in\mathbb{Z}^{d}} \operatorname{Im}(\widehat{J_{N}}(k))k\right]\cdot x-\sum_{k\in\mathbb{Z}^{d} }\operatorname{Re}(\widehat{J_{N}}(k))-\overline{g}_{x}\right|\] \[\leq C_{5}v_{J_{N},2}d^{3/2}\sqrt{\log mm}^{-\frac{1}{2}-\frac{1}{d}}.\]

Moreover, from the definition (5.4) of \(h_{x}\), we can get bounds of the parameters as

\[|\beta_{k}|\leq\frac{v}{\lceil m/4\rceil}\leq\frac{8\pi^{2}v_{J_{N},2}}{m}, \qquad\|\alpha_{k}\|_{1}\leq 1,\qquad 0\leq b_{k}\leq 1.\]

To complete the proof, notice \(u=\sigma(u)-\sigma(-u)\) for \(u\in\mathbb{R}\), then for \(m\geq 20\), a function of the form \(\sum\limits_{k=3\lceil m/4\rceil+1}^{m}\beta_{k}\sigma(\alpha_{k}\cdot x-b_{k})\) can realize the affine function \(\left[\sum\limits_{k\in\mathbb{Z}^{d}}\operatorname{Im}(\widehat{J_{N}}(k))k \right]\cdot x-\sum\limits_{k\in\mathbb{Z}^{d}}\operatorname{Re}(\widehat{J_ {N}}(k))\) with the parameters bounded as

\[|\beta_{k}|\leq\frac{8v_{J_{N},2}}{m},\qquad\|\alpha_{k}\|_{1}\leq 1,\qquad 0 \leq b_{k}\leq 1,\]

and the desired bound (3.9) is verified. The bound is trivially true for \(m<20\). This completes the proof of Lemma 1.
## Acknowledgments

The first version of the paper was written when the authors were at City University of Hong Kong, supported partially by NSFC/RGC Joint Research Scheme [RGC Project No. N_CityU102/20 and NSFC Project No. 12061160462], Germany/Hong Kong Joint Research Scheme [Project No. G-CityU101/20], Hong Kong Institute for Data Science, and InnoHK initiative, The Government of the HKSAR, and Laboratory for AI-Powered Financial Technologies. The authors would like to thank Hrushikesh Mhaskar and the referees for their constructive comments and suggestions.
