# Theory of Deep Convolutional Neural Networks III: Approximating Radial
Functions

Tong Mao, Zhongjie Shi, and Ding-Xuan Zhou
School of Data Science, City University of Hong Kong
Kowloon, Hong Kong
Email<EMAIL_ADDRESS>
###### Abstract

We consider a family of deep neural networks consisting of two groups of
convolutional layers, a downsampling operator, and a fully connected layer.
The network structure depends on two structural parameters which determine the
numbers of convolutional layers and the width of the fully connected layer. We
establish an approximation theory with explicit approximation rates when the
approximated function takes a composite form $f\circ Q$ with a feature
polynomial $Q$ and a univariate function $f$. In particular, we prove that
such a network can outperform fully connected shallow networks in
approximating radial functions with $Q(x)=|x|^{2}$, when the dimension $d$ of
data from $\mathbb{R}^{d}$ is large. This gives the first rigorous proof for
the superiority of deep convolutional neural networks in approximating
functions with special structures. Then we carry out generalization analysis
for empirical risk minimization with such a deep network in a regression
framework with the regression function of the form $f\circ Q$. Our network
structure which does not use any composite information or the functions $Q$
and $f$ can automatically extract features and make use of the composite
nature of the regression function via tuning the structural parameters. Our
analysis provides an error bound which decreases with the network depth to a
minimum and then increases, verifying theoretically a trade-off phenomenon
observed for network depths in many practical applications.

Keywords: deep learning, convolutional neural networks, rates of
approximation, radial functions, generalization analysis

##  1 Introduction

Deep learning has been a powerful tool for processing big data from many
fields of science and technology [8]. It started with an important family of
deep network architectures called deep convolutional neural networks (DCNNs)
which are very efficient for speech recognition, image classification, and
many other practical tasks [10, 15]. Compared with their great success in
practice and some analysis of algorithms for training parameters like
stochastic gradient descent, DCNNs are not fully understood yet in terms of
their approximation, modelling and generalization abilities. Recently we
confirm universality of DCNNs in [37] and show in [38] that DCNNs can perform
in representing functions at least as well as fully connected neural networks.
But it is open in general whether they can perform better in learning and
approximating some classes of functions with special structures used in
practical applications, though there have been some attempts in [19, 38, 7].

The first purpose of this paper is to answer the above open question by
proving in Theorem 3 below that DCNNs followed by one fully connected layer
can approximate radial functions $f(|x|^{2})$ much faster than fully connected
shallow neural networks where $|x|=\sqrt{x_{1}^{2}+\ldots+x_{d}^{2}}$ is the
norm of an input vector $x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}$. In fact, we
present dimension-independent rates of approximating radial functions in
Theorem 2 below. Moreover, we develop a theory of DCNNs for approximating
efficiently functions of the form $f\circ Q(x)=f(Q(x))$ with a polynomial $Q$
on $\mathbb{R}^{d}$ and a univariate function $f$, both unknown. Radial
functions have such a form with a known quadratic polynomial
$Q(x)=x_{1}^{2}+\ldots+x_{d}^{2}$. They arise naturally in statistical
physics, early warning of earthquakes, 3-D point-cloud segmentation, and image
rendering, and their learning by fully connected neural networks was studied
in [20, 3, 4].

The second purpose of this paper is to conduct generalization analysis of a
learning algorithm for regression induced by DCNNs and to show for regression
functions of the form $f\circ Q$ that the rates of estimation error (which
equals the excess generalization error) decrease to some optimal value and
then increase as the depth of the deep network becomes large. This is
consistent with observations made in many practical applications of deep
neural networks.

Our last purpose is to show that DCNNs in our network structure determined
completely by two parameters can automatically extract features and make use
of the composite nature of the target function in learning for regression via
tuning values of the two parameters, though our network structure is generic
and does not use any composite information or the functions $Q$ and $f$. The
activation function for our networks is the rectified linear unit (ReLU)
$\sigma$ given by $\sigma(u)=\max\\{u,0\\}$ for $u\in\mathbb{R}$.

A classical multi-layer fully connected neural network
$\\{h^{(j)}(x)\\}_{j=0}^{J}$ of widths $\\{d_{j}\in\mathbb{N}\\}$ takes an
iterative form with $h^{(0)}(x)=x\in\mathbb{R}^{d}$ and $d_{0}=d$ given by

$h^{(j)}(x)=\sigma\left(F^{(j)}h^{(j-1)}(x)-b^{(j)}\right),\qquad
j=1,\dots,J,$ (1.1)

where $b^{(j)}\in\mathbb{R}^{d_{j}}$ and $F^{(j)}$ is a $d_{j}\times d_{j-1}$
full connection matrix reflecting the fully connected nature. The number
$d_{j}d_{j-1}$ of free parameters in the connection matrix $F^{(j)}$ is too
large when the input dimension $d$ increases. A core idea of deep learning is
to reduce the number of free parameters at individual layers and channels by
imposing special structures on the connection matrices. The special structure
imposed on DCNNs is induced by convolutions. The 1-D convolution of a sequence
$w=(w_{k})_{k\in\mathbb{Z}}$ on $\mathbb{Z}$ supported in $\\{0,1,\ldots,s\\}$
and another $x=(x_{k})_{k\in\mathbb{Z}}$ supported in $\\{1,2,\ldots,D\\}$ is
given by

$\left(w{*}x\right)_{i}=\sum_{k\in\mathbb{Z}}w_{i-k}x_{k}=\sum_{k=1}^{D}w_{i-k}x_{k},\qquad
i\in\mathbb{Z}.$

This is a sequence supported in $\\{1,2,\ldots,D+s\\}$. By restricting the
index $i$ onto this set, we know that the possibly nonzero entries of the
convoluted sequence $w{*}x$ can be expressed in a vector form as

$\left[\begin{array}[]{c}\left(w{*}x\right)_{1}\\\ \left(w{*}x\right)_{2}\\\
\vdots\\\ \left(w{*}x\right)_{D}\\\ \vdots\\\
\left(w{*}x\right)_{D+s}\end{array}\right]=T^{w}\left[\begin{array}[]{c}x_{1}\\\
x_{2}\\\ \vdots\\\ x_{D}\end{array}\right],\quad
T^{w}:=\left[\begin{array}[]{ccccccc}w_{0}&0&0&0&\dots&0&0\\\
w_{1}&w_{0}&0&0&\dots&0&0\\\
\vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\\
w_{s}&w_{s-1}&\dots&w_{0}&\dots&0&0\\\ 0&w_{s}&\dots&w_{1}&\ddots&\vdots&0\\\
\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\\
\dots&\dots&0&w_{s}&\dots&w_{1}&w_{0}\\\
\dots&\dots&\dots&0&w_{s}&\dots&w_{1}\\\
\vdots&\dots&\dots&\ddots&\ddots&\ddots&\vdots\\\
0&\dots&\dots&\dots&\dots&0&w_{s}\end{array}\right].$ (1.2)

Here the Toeplitz type matrix $T^{w}$ is induced by the 1-D convolution and is
called a convolutional matrix. The number of parameters
$\\{w_{k}\\}_{k=0}^{s}$ contained in this structured connection matrix is
$s+1$, much smaller than the number of entries $D(D+s)$ of a full connection
matrix of the same size. This great reduction at individual layers allows
DCNNs to have large depths. In this paper, we construct a deep neural network
consisting of a group of $J_{1}\in\mathbb{Z}_{+}$ comvolutional layers
followed by a downsampling operation, and another group of $J_{2}-J_{1}$
convolutional layers followed by a fully connected layer. The depth $J_{2}$ of
the DCNNs and the width of the last fully connected layer depend on an integer
parameter $N\in\mathbb{N}$ explicitly. For $u\geq 0$, we use $\lfloor
u\rfloor$ to denote the integer part of $u$, and $\lceil u\rceil$ the smallest
integer greater than or equal to $u$.

######  Definition 1.

Let $x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}$ be the input data vector,
$s\in\mathbb{N}$ be the filter length, and
$J_{1}\in\mathbb{Z}_{+},N\in\mathbb{N}$. The DCNN
$\\{h^{(j)}:\mathbb{R}^{d}\to\mathbb{R}^{d_{j}}\\}_{j=1}^{J_{2}}$ with widths
$\\{d_{j}\\}_{j=1}^{J_{2}}$ given by $d_{0}=d$,
$d_{J_{1}}=\left\lfloor\frac{d+J_{1}s}{d}\right\rfloor$ and the iteration
relation

$d_{j}=d_{j-1}+s,\qquad j\in\\{1,\ldots,J_{2}\\}\setminus\\{J_{1}\\}$

has depth $J_{2}:=J_{1}+\left\lceil\frac{(2N+3)d_{J_{1}}}{s-1}\right\rceil$
and is defined iteratively by $h^{(0)}(x)=x$ and

$h^{(j)}(x)=\left\\{\begin{array}[]{ll}\sigma\left(T^{(j)}h^{(j-1)}(x)-b^{(j)}\right),&\hbox{if}\
j=\\{1,\dots,J_{2}\\}\setminus\\{J_{1}\\},\\\
\mathfrak{D}_{d}\left(\sigma\left(T^{(j)}h^{(j-1)}(x)-b^{(j)}\right)\right),&\hbox{if}\
j=J_{1},\end{array}\right.$ (1.3)

where $\\{T^{(j)}:=T^{w^{(j)}}\\}$ are the convolutional matrices induced by
the sequence of filters ${\bf w}:=\\{w^{(j)}\\}_{j=1}^{J_{2}}$ each supported
in $\\{0,1,\dots,s\\}$,
$\mathfrak{D}_{d}:\mathbb{R}^{d+J_{1}s}\to\mathbb{R}^{\lfloor\frac{d+J_{1}s}{d}\rfloor}$
is the downsampling operator acting at the $J_{1}$-th layer given by

$\mathfrak{D}_{d}(v)=\left(v_{id}\right)_{i=1}^{\lfloor\frac{d+J_{1}s}{d}\rfloor},\qquad
v=\left(v_{i}\right)_{i=1}^{d+J_{1}s}\in\mathbb{R}^{d+J_{1}s},$

and $\\{b^{(j)}\in\mathbb{R}^{d_{j}}\\}_{j=1}^{J_{2}}$ are bias vectors
satisfying

$(b^{(j)})_{s+1}=(b^{(j)})_{s+2}=\ldots=(b^{(j)})_{d_{j-1}},\qquad
j=1,2,\ldots,J_{2}-1.$ (1.4)

The last layer $h^{(J_{2}+1)}:\mathbb{R}^{d}\to\mathbb{R}^{2N+3}$ is produced
with a connection matrix $F^{[J_{2}+1]}\in\mathbb{R}^{(2N+3)\times d_{J_{2}}}$
of identical rows and a bias vector $b^{(J_{2}+1)}\in\mathbb{R}^{2N+3}$ as

$h^{(J_{2}+1)}(x)=\sigma\left(F^{[J_{2}+1]}h^{(J_{2})}(x)-b^{(J_{2}+1)}\right).$

The hypothesis space ${\mathcal{H}}_{N}$ for learning and approximation
consists of all output functions depending on ${\bf w}$, $F^{[J_{2}+1]}$, and
the bias sequence ${\bf b}=\\{b^{(j)}\\}_{j=1}^{J_{2}+1}$ as

${\mathcal{H}}_{N}=\left\\{c\cdot h^{(J_{2}+1)}(x):c\in\mathbb{R}^{2N+3},\
{\bf w},\ {\bf b},\ F^{[J_{2}+1]}\right\\}.$ (1.5)

The restriction (1.4) on the bias vectors $\\{b^{(j)}\\}_{j=1}^{J_{2}-1}$ is
imposed based on the observation that the sums of the rows in the middle of
the convolutional matrix $T^{w}$ in (1.2) are equal to $\sum_{k=0}^{s}w_{k}$.

If we introduce an activated affine map with a matrix $F$ and vector $b$ as

$\mathcal{A}_{F,b}(v)=\sigma(Fv-b),\qquad v\in\mathbb{R}^{d_{j-1}},$

then the last layer $h^{(J_{2}+1)}(x)$ of our network can be expressed as

$\mathcal{A}_{F^{[J_{2}+1]},b^{(J_{2}+1)}}\circ\mathcal{A}_{T^{(J_{2})},b^{(J_{2})}}\circ\ldots\circ\mathcal{A}_{T^{(J_{1}+1)},b^{(J_{1}+1)}}\circ\mathfrak{D}_{d}\circ\mathcal{A}_{T^{(J_{1})},b^{(J_{1})}}\circ\ldots\circ\mathcal{A}_{T^{(1)},b^{(1)}}(x).$
(1.6)

The structure of the deep neural network in Definition 1 is completely
determined by the two parameters $J_{1},N$ which are called structural
parameters. This network structure does not involve any feature or composite
information of the target functions. Once the structural parameters are
chosen, the other parameters in (1.5), ${\bf w},{\bf b},F^{[J_{2}+1]}$ and $c$
can be trained with stochastic configuration networks [34], stochastic
gradient descent, or some other randomized methods, and are called training
parameters.

Traditional machine learning algorithms are often implemented in two steps of
feature extraction and task-oriented learning. In many practical applications,
the first step of feature extraction is carried out with carefully designed
preprocessing pipelines and data transformations and is labor intensive,
involving feature engineering techniques, human ingenuity and practical domain
knowledge.

It has been believed from the great success of deep learning in practical
applications that structures imposed on deep neural networks enable deep
learning algorithms to combine automatically the two steps of extracting
features and producing satisfactory outputs for desired learning tasks. We aim
at verifying this belief for the convolutional structure imposed for CNNs in
learning composite functions of the form $f\circ Q$. On one hand, the
structure of our CNN network stated in Definition 1 does not depend on the
composite information of $f\circ Q$ or the functions $f,Q$; it is generic and
determined only by two parameters $J_{1},N$. On the other hand, if the target
function takes the from $f\circ Q$, the convolutions enable our network to
extract automatically the polynomial feature $Q$ and then learn the composite
target function well, with tuned parameters $J_{1},N$ of our unified DCNN
model. We expect that our CNN network can extract some other nonlinear
features and learn functions efficiently via tuning the two structural
parameters.

To analyze the learning ability of the algorithm induced by our network, we
use two novel ideas in estimating the approximation error and sample error. In
our previous work [37, 38], we have shown how to realize linear features
$\\{\xi_{k}\cdot x\\}$ by a group of convolutional layers. In this paper we
demonstrate how another group of convolutional layers together with a fully
connected layer can be used to approximate ridge monomials $\\{(\xi_{k}\cdot
x)^{\ell}:1\leq k\leq n_{q},1\leq\ell\leq q\\}$ and then the polynomial $Q$.
Here $n_{q}=\left(\begin{array}[]{c}d-1+q\\\ q\end{array}\right)$ is the
dimension of the space of homogeneous polynomials on $\mathbb{R}^{d}$ of
degree $q$, and $J_{1}=\lceil\frac{n_{q}d-1}{s-1}\rceil$ is the number of
convolutional layers in the first group. Applying convolutional layers to
extracting nonlinear (polynomial) features is the first novelty of this paper.
The second novelty is to bound the training parameters $c,{\bf w},{\bf
b},F^{[J_{2}+1]}$ in the expression (1.5) of the approximator in the
approximation error part so that a bounded subset ${\mathcal{H}}_{R,N}$ of
${\mathcal{H}}_{N}$ (defined in (2.10) below) contains the approximator and
the covering numbers of the bounded hypothesis space ${\mathcal{H}}_{R,N}$ can
be estimated for bounding the sample error. This is achieved by applying
Cauchy’ bound of polynomial roots and Vieta’s formula of polynomial
coefficients to bounding the filters constructed in convolutional
factorizations of sequences.

##  2 Main Results

In this section we state our main results which will be proved in Sections 4,
5, and 6. The approximation theorems given in the first two subsections show
that if the target function has the composite form $f\circ Q$ with a
Lipschitz-$\alpha$ function $f$, then the CNN network in Definition 1 achieves
an approximation accuracy $\epsilon>0$ when the structural parameter $N$ is of
order $O\left(\epsilon^{-\frac{1}{\alpha}}\right)$, a level for approximating
univariate functions by neural networks. The learning rates stated in our last
main result realized by the learning algorithm induced by our network for
regression are of dimension-independent order
$O\left(m^{-\frac{\alpha}{1+\alpha}}\right)$ for a sample of size $m$. These
results tell us that the generic CNN network in Definition 1 has the ability
of automatically extracting the polynomial feature and making use of the
composite nature of the target function via tuning the structural parameters
$N,J_{1}$ in the learning process, even though the network does not involve
any information about the polynomial or composition.

###  2.1 Rates of approximating composite functions

Without loss of generality we take the domain of definition of the
approximated function to be a subset of the unit ball
$\Omega\subseteq{\mathbb{B}}:=\\{x\in\mathbb{R}^{d}:|x|\leq 1\\}$. Denote
$B_{Q}=\|Q\|_{C(\Omega)}$. The univariate function $f$ in the composite form
$f\circ Q$ of the approximated function is assumed to be in
$C^{0,\alpha}[-B_{Q},B_{Q}]$ with $0<\alpha\leq 1$, the space of
Lipschitz-$\alpha$ functions on $[-B_{Q},B_{Q}]$ with semi-norm
$|f|_{C^{0,\alpha}}:=\sup\limits_{x_{1}\not=x_{2}\in[-B_{Q},B_{Q}]}\frac{|f(x_{1})-f(x_{2})|}{|x_{1}-x_{2}|^{\alpha}}$.

To achieve desired estimates for the approximation error to be used in our
generalization analysis, we shall construct an approximator from
${\mathcal{H}}_{N}$ and choose some training parameters explicitly in terms of
the degree of the feature polynomial $Q$: the filters
$\\{w^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$ by (4.10) and (4.11), connection matrix
$F^{[J_{2}+1]}$ and bias vector $b^{(J_{2}+1)}$ by (4.20) in Section 4. This
reduces the total number of implicit training parameters which are called free
parameters in our approximator construction, to distinguish them from the
training parameters in Definition 1 and our generalization analysis.

Our first main result provides rates of approximating $f\circ Q$ by DCNNs with
a downsampling operation followed by a fully connected layer.

######  Theorem 1.

Let $2\leq s\leq d$, $Q$ be a polynomial on $\Omega$ of degree at most
$q\in\mathbb{N}$, and $f\in C^{0,\alpha}[-B_{Q},B_{Q}]$ for some $0<\alpha\leq
1$. Take $J_{1}=\lceil\frac{n_{q}d-1}{s-1}\rceil$. Then for any
$N\in\mathbb{N}$, there exists a deep network stated in Definition 1 with
$\\{w^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$, $F^{[J_{2}+1]}$ and $b^{(J_{2}+1)}$
explicitly constructed (given in Sections 4) such that

$\inf\left\\{\left\|c\cdot h^{(J_{2}+1)}-f\circ
Q\right\|_{C(\Omega)}:\|c\|_{\infty}\leq\frac{4\|f\|_{\infty}N}{\widehat{B}_{Q}}\right\\}\leq\frac{C_{Q,\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}},$
(2.1)

where $\widehat{B}_{Q}$ is a constant depending only on $Q$ and $C_{Q,\alpha}$
is another one only on $Q,\alpha$.

The total number ${\mathcal{N}}$ of free parameters in this network can be
bounded as

${\mathcal{N}}\leq\left(30+28n_{q}\right)N+(8d+q+44)n_{q}+4s+49.$

To achieve the approximation accuracy $0<\epsilon\leq 1$, we only need

${\mathcal{N}}\leq\left(C_{Q,\alpha,|f|_{C^{0,\alpha}}}+d\right)d^{q}\epsilon^{-\frac{1}{\alpha}}$
(2.2)

free parameters by taking $N=\left\lceil
C_{Q,\alpha}^{\frac{1}{\alpha}}|f|_{C^{0,\alpha}}^{\frac{1}{\alpha}}\epsilon^{-\frac{1}{\alpha}}\right\rceil,$
where $C_{Q,\alpha,|f|_{C^{0,\alpha}}}$ is a constant depending on
$Q,\alpha,|f|_{C^{0,\alpha}}$, but not on $d$ or $\epsilon$.

Theorem 1 tells us that the total number of free parameters in the constructed
network for achieving the approximation accuracy $\epsilon$ is
$O\left(\epsilon^{-\frac{1}{\alpha}}\right)$, which has the same complexity as
that of a fully connected shallow network (1.1) with $J=1$ for approximating a
univariate Lipschitz-$\alpha$ function. But the constant term in the bound
(2.2) demonstrates the role of the polynomial feature $Q$ and the data
dimension $d$ in the network complexity.

###  2.2 Rates of approximating radial functions

When the feature polynomial is the special one $Q(x)=|x|^{2}$ for learning
radial functions, we only need the second group of convolutional layers
without downsampling by taking the parameter value $J_{1}=0$.

If we apply Theorem 1 to a radial function $f(|x|^{2})$ with $Q(x)=|x|^{2}$,
we see that the constant in the complexity bound (2.2) is at least of order
$O\left(d^{3}\right)$ with respect to the data dimension $d$. The constructed
network for achieving the complexity in Theorem 1 uses the degree of the
feature polynomial $Q$, not the exact form of $Q$. However, the quadratic
polynomial $Q$ for a radial function $f(|x|^{2})$ is known. Making use of this
exact form of $Q$ enables us to reduce the depth of the network for
approximating radial functions and improve the constant in the complexity
bound to an order $O\left(d^{2}\right)$.

######  Theorem 2.

Let $2\leq s\leq d$ and $f\in C^{0,\alpha}[0,1]$ for some $0<\alpha\leq 1$.
Then for any $N\in\mathbb{N}$, there exists a deep network stated in
Definition 1 with
$J_{1}=0,J_{2}=J:=\left\lceil\frac{(2N+3)d}{s-1}\right\rceil$ and
$\\{w^{(j)}\\}_{j=1}^{J}$, $F^{[J+1]}$ and $b^{(J+1)}$ explicitly constructed
(given in Sections 4) such that the last layer

$h^{(J+1)}(x)=\mathcal{A}_{F^{[J+1]},b^{(J+1)}}\circ\mathcal{A}_{T^{(J)},b^{(J)}}\circ\ldots\circ\mathcal{A}_{T^{(1)},b^{(1)}}(x)$

satisfies

$\inf\left\\{\left\|c\cdot
h^{(J+1)}(x)-f(|x|^{2})\right\|_{C(\Omega)}:\left\|c\right\|_{\infty}\leq\frac{4N\|f\|_{\infty}}{1+4d}\right\\}\leq
3\left(1+4d\right)^{\alpha}|f|_{C^{0,\alpha}}N^{-\alpha}.$ (2.3)

The total number ${\mathcal{N}}$ of free parameters in this network can be
bounded as

${\mathcal{N}}\leq(14d+2)N+22d+s+1.$

To achieve the accuracy $0<\epsilon\leq 1$, by taking
$N=\left\lceil\left(1+4d\right)\left(3|f|_{C^{0,\alpha}}\right)^{\frac{1}{\alpha}}\epsilon^{-\frac{1}{\alpha}}\right\rceil$
we know that the total number of free parameters can be bounded as

${\mathcal{N}}\leq
15\left(5\left(3|f|_{C^{0,\alpha}}\right)^{\frac{1}{\alpha}}+1\right)d^{2}\epsilon^{-\frac{1}{\alpha}}+22d+s+1.$

###  2.3 Super efficiency in approximating radial functions

Our third main result demonstrates that deep neural networks have super
efficiency in approximating radial functions, compared with shallow networks.
Consider the set of radial functions in the unit ball of the space
$C^{0,1}({\mathbb{B}})$ of Lipschitz functions on ${\mathbb{B}}$ defined by

${\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right):=\left\\{f(|\cdot|^{2}):\|f(|\cdot|^{2})\|_{C^{0,1}({\mathbb{B}})}\leq
1\right\\},$ (2.4)

where $\|f(|\cdot|^{2})\|_{C^{0,1}({\mathbb{B}})}$ is the Lipschitz-$1$ norm
of the function $f(|\cdot|^{2})$ defined for functions $g$ on ${\mathbb{B}}$
by

$\|g\|_{C^{0,1}({\mathbb{B}})}=\sup_{x\not=y\in{\mathbb{B}}}\frac{\left|g(x)-g(y)\right|}{|x-y|}+\sup_{x\in{\mathbb{B}}}\left|g(x)\right|.$
(2.5)

Denote the span of $N$ ridge functions as

${\mathcal{S}}_{N}=\left\\{\sum_{k=1}^{N}c_{k}\sigma_{k}(a_{k}\cdot x-b_{k}):\
\sigma_{k}\in C(\mathbb{R}),\ a_{k}\in\mathbb{R}^{d},\
c_{k},b_{k}\in\mathbb{R}\right\\}.$ (2.6)

Recall the hypothesis space generated by a shallow neural network is a subset
of ${\mathcal{S}}_{N}$ consisting of functions with
$\sigma_{1}=\ldots=\sigma_{N}$ being an activation function.

The efficiency of a neural network generating a hypothesis space $V$ in
approximating a set $U$ of functions on $\Omega={\mathbb{B}}$ uniformly is
measured by the quantity

$\hbox{dist}(U,V):=\sup_{f\in U}\inf_{g\in
V}\|f-g\|_{L_{\infty}({\mathbb{B}})}$ (2.7)

which is the deviations of $U$ from $V$ in $L_{\infty}({\mathbb{B}})$.

######  Theorem 3.

Let $2\leq s\leq d$. We have

$\hbox{dist}\left({\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right),{\mathcal{S}}_{N}\right)\geq
c_{d}N^{-\frac{1}{d-1}},\qquad\forall N\in\mathbb{N}$ (2.8)

with a constant $c_{d}$ independent of $N$; while for the hypothesis space
${\mathcal{H}}_{N}$ generated by the deep network constructed in Theorem 2,
there holds

$\hbox{dist}\left({\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right),{\mathcal{H}}_{N}\right)\leq
3\sqrt{1+4d}N^{-\frac{1}{2}},\qquad\forall N\in\mathbb{N}.$ (2.9)

By Theorem 3, we know that the total number of free parameters in our DCNN
network for achieving an accuracy $\epsilon>0$ in approximating functions from
the class ${\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right)$ is $O(\epsilon^{-2})$
while that of a fully connected shallow network is $O(\epsilon^{-(d-1)})$.
This shows that deep neural networks are much more efficient than shallow
networks in approximating radial functions when the dimension $d>3$ is large.

###  2.4 Generalization analysis of DCNNs

Our last main result is analysis of the generalization ability of the commonly
used empirical risk minimization (ERM) algorithm over a bounded hypothesis
space ${\mathcal{H}}_{R,N}$ generated by our deep neural network. Here $R>0$
is used for bounding the parameters of the output functions from the
hypothesis space ${\mathcal{H}}_{N}$ as

$\displaystyle{\mathcal{H}}_{R,N}=$ $\displaystyle\Big{\\{}c\cdot
h^{(J+1)}(x):\ \|w^{(j)}\|_{\infty}\leq
R,\|b^{(j)}\|_{\infty}\leq(2(s+1)R)^{j},\ \forall j,\ \|c\|_{\infty}\leq NR,$
(2.10) $\displaystyle F^{[J_{2}+1]}\ \hbox{has identical rows with norm}\
\|F^{[J_{2}+1]}\|_{\infty}\leq N^{2}R\Big{\\}},$

where $\|F^{[J_{2}+1]}\|_{\infty}$ is the norm of the matrix $F^{[J_{2}+1]}$
as a linear operator from
$\left(\mathbb{R}^{d_{J_{2}}},\|\cdot\|_{\infty}\right)$ to
$\left(\mathbb{R}^{2N+3},\|\cdot\|_{\infty}\right)$ which equals the maximum
of the $\ell_{1}$-norms of its rows.

We follow the classical learning framework for regression which can be found
in [5]. A data sample $D=\\{(x_{i},y_{i})\\}^{m}_{i=1}\subset\mathcal{Z}^{m}$
is independently drawn from a Borel probability measure $\rho$ on
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$ with $\mathcal{X}=\Omega$ and
$\mathcal{Y}\subseteq[-M,M]$ for some $M>0$. The target function for learning
is the regression function $f_{\rho}$ on $\mathcal{X}$ defined by
$f_{\rho}(x)=\int_{\mathcal{Y}}yd\rho(y|x)$ minimizing the generalization
error $\mathcal{E}(f):=\int_{\mathcal{Z}}(f(x)-y)^{2}d\rho$, where $\rho(y|x)$
denotes the conditional distribution at $x\in\mathcal{X}$ induced by $\rho$.
Denote by $\rho_{X}$ the marginal distribution of $\rho$ on $\mathcal{X}$ and
by $(L^{2}_{\rho_{X}},\parallel\cdot\parallel_{\rho})$ the Hilbert space of
square integrable functions with respect to $\rho_{X}$.

The ERM algorithm defined on the bounded hypothesis space (2.10) learns an
empirical target function as

$f_{D,R,N}:=\arg\min_{f\in{\mathcal{H}}_{R,N}}\dfrac{1}{m}\sum_{i=1}^{m}(f(x_{i})-y_{i})^{2}.$
(2.11)

Let us emphasize again that the structure of the network for defining the
bounded hypothesis space in the above algorithm is completely determined by
the two parameters $J_{1}$ and $N$, and it does use any property of the
regression function. However, if the regression function takes a composite
form $f_{\rho}=f\circ Q$, the learning algorithm (2.11) has the ability of
automatically extracting features and making use of the composite property via
tuning $J_{1},N$ so that the empirical target function $f_{D,R,N}$ can learn
$f_{\rho}$ in the same learning rates as for learning univariate functions.

Since $\mathcal{Y}\subseteq[-M,M]$, we project the output function onto the
interval $[-M,M]$ and introduce the truncated empirical target function

$\pi_{M}f_{D,R,N}(x):=\left\\{\begin{array}[]{ll}f_{D,R,N}(x),&\hbox{if}\
|f_{D,R,N}(x)|\leq M,\\\ M,&\hbox{if}\ f_{D,R,N}(x)>M,\\\ -M,&\hbox{if}\
f_{D,R,N}(x)<-M.\end{array}\right.$

######  Theorem 4.

Let $2\leq s\leq d$ and $Q$ be a polynomial on $\Omega$ of degree at most
$q\in\mathbb{N}$. If $f_{\rho}=f\circ Q$ for some $f\in
C^{0,\alpha}[-B_{Q},B_{Q}]$ with some $0<\alpha\leq 1$, then for
$N\in\mathbb{N}$ and $R\geq R_{q,d,s,Q,\|f\|_{\infty}}$, we have

$\mathbb{E}\left[\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}\right]\leq
C_{Q,s,d,\alpha,M,|f|_{C^{0,\alpha}}}\log\left(2(s+1)R\right)\max\left\\{N^{-2\alpha},\
\frac{N^{2}}{m}\right\\},$ (2.12)

where $C_{Q,s,d,\alpha,M,|f|_{C^{0,\alpha}}}$ is a constant independent of
$m,N$ or $R$, and $R_{q,d,s,Q,\|f\|_{\infty}}$ is a constant depending on
$q,s,d,Q,\|f\|_{\infty}$ (given explicitly in Lemma 8 below). In particular,
by choosing $N=\left\lceil m^{\frac{1}{2+2\alpha}}\right\rceil$, we have

$\mathbb{E}\left[\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}\right]\leq
4C_{Q,s,d,\alpha,M,|f|_{C^{0,\alpha}}}\log\left(2(s+1)R\right)m^{-\frac{\alpha}{1+\alpha}}.$

Observe from Theorem 1 that the approximation error bound (2.1) always
decreases as the depth of the network $J_{2}+1\approx N$ increases. On the
other hand, the capacity of the hypothesis space ${\mathcal{H}}_{R,N}$
increases with the depth, which leads to larger sample error. Combining these
two terms of error, we see from Theorem 4 that the estimation error bound
(2.12) decreases to a minimum as the network depth increases to an optimal
value, and then increases as the depth becomes larger. This trade-off
phenomenon is common in many applications of deep learning algorithms.

##  3 Comparisons and Discussion

Establishing a solid theoretical foundation for deep learning is greatly
desired. A core challenge is to prove that structured deep neural networks
used in deep learning can outperform the classical fully connected networks
and automatically extract features when the data or target functions take
forms involving some special features. The main difficulty lies in the
approximation theory of structured deep neural networks like DCNNs which is
totally different from the nice theory for fully connected networks developed
about $30$ years ago. For example, a typical approximation rate in [21]
obtained by a localized Taylor expansion approach for shallow network (1.1) of
width $N$ with $J=1$ is $\inf_{c}\left\|c\cdot
h^{(1)}-f\right\|_{C([-1,1]^{d})}=O(N^{-\alpha/d})$ for $f\in
W_{\infty}^{\alpha}([-1,1]^{d})$, when the activation function $\sigma$ is
$C^{\infty}$ sigmoid type satisfying for some $b\in{\mathbb{R}}$ and some
integer $\ell\in\mathbb{N}\setminus\\{1\\}$, a restriction
$\sigma^{(k)}(b)\not=0$ for all $k\in\mathbb{Z}_{+}$ and an asymptotic
condition $\lim_{u\to\infty}\sigma(u)/u^{\ell}=1$. Such approximation rates
were recently proved for ReLU shallow networks in [12] for functions
satisfying a decay condition for the Fourier transform [1], and were extended
to ReLU deep networks in [28, 33, 35, 2, 25, 23, 31, 32] for functions from
$W_{\infty}^{\alpha}([-1,1]^{d})$ with $0<\alpha\leq 2$, and in [30] for
approximation on manifolds, all for fully connected networks. In particular,
it was shown in [28, 35] that an accuracy $\epsilon>0$ for approximating
functions from $W_{\infty}^{\alpha}([-1,1]^{d})$ can be achieved by a deep
ReLU fully connected network of depth $\frac{C_{0}d}{4}(\log(1/\epsilon)+d)$
with $C_{0}>0$ and $2^{d}\epsilon^{-d/\alpha}$ free parameters which has the
same order of complexity as required by shallow sigmoid networks.

Deep CNNs use convolutional matrices (1.2) which have a special structure with
sparsity, making their approximation theory totally different. We show in [37]
that an accuracy $\epsilon>0$ for approximating a function from
$W^{\alpha}_{2}\left([-1,1]^{d}\right)$ with an integer index $\alpha>2+d/2$
can be achieved by a DCNN of depth
$4\lceil\frac{1}{\epsilon^{2}}\log\frac{1}{\epsilon^{2}}\rceil$ and a linearly
increasing number of
$\lceil\frac{75}{\epsilon^{2}}\log\frac{1}{\epsilon^{2}}\rceil d$ free
parameters which improves the bound in Theorem 1 of [35] with respect to the
data dimension $d$. The restriction $\alpha>2+d/2$ on the smoothness was
relaxed by a spherical analysis approach in our recent work [7] when the data
are from the unit sphere of $\mathbb{R}^{d}$. We also show in [38] that DCNNs
can realize the output layer of any fully-connected neural network with the
same order of complexity. This observation was made for periodized DCNNs with
different architectures and connection matrices in [24, 26].

All the above estimates on approximation by deep neural networks, structured
or fully connected, are stated in terms of the smoothness of the approximated
function. Approximating radial functions by fully-connected neural networks
was studied in [20, 3, 4], while representing functions with variables having
given compositional structures by fully-connected networks designed based on
the known compositional structures was considered in [22, 27].

In this paper we present estimates for learning compositional functions
$f\circ Q$ with polynomial features $Q$ by an ERM algorithm with hypothesis
spaces generated by DCNNs without involving any composite property or
functions $f,Q$. We verify that our generic DCNN network can automatically
make use of the composite nature of the target function and the polynomial
feature $Q$ by tuning two parameters $J_{1},N$. We show rigorously that DCNNs
can outperform fully connected shallow networks in approximating the class of
radial functions when the data dimension $d>3$ is large. To our best
knowledge, this is the first proof for the superiority of DCNNs in
approximating functions with structures, though some hints were provided in
our previous work [38, 7] on approximating ridge functions or additive ridge
functions of the form $\sum_{k=1}^{K}g_{k}(\xi_{k}\cdot x)$ with
$\xi_{k}\in\mathbb{R}^{d}$. It would be interesting to apply our ideas to some
other learning problems [6, 9, 17], and to investigate more function
structures and features for which DCNNs combined with pooling, channels, and
other network architectures [39] can demonstrate super efficiency in feature
extraction, approximations and representations of multivariate functions.

Generalization analysis for ERM with fully connected neural networks has been
well developed in the literature [13, 29, 3]. For composite functions, deep
fully connected ReLU networks were constructed in [29] based on composite
dimensions and some ideas from [35] to achieve optimal learning rates. In
particular, it was shown by (26) there that a network output function $f^{*}$
yields $\left\|f^{*}-f\circ
Q\right\|_{C(\Omega)}=O\left({\mathcal{N}}^{-\alpha}\right)$ in approximating
$f\circ Q$ with $f\in C^{0,\alpha}$. This rate of approximation by deep fully
connected networks is the same as (2.1) in our Theorem 1 for approximation by
deep CNNs, while the dimension dependence of the constant in our estimate is
better, as seen more explicitly in (2.3) of Theorem 2 for approximating radial
functions. Together with sample error estimates, our approximation theory
gives generalization analysis with error bound (2.12) for ERM with DCNNs
followed by a fully connected layer. The bound decreases with the depth to a
minimum and then increases, which verifies a trade-off phenomenon observed in
practice.

##  4 Constructing Deep Network for Approximation

In this section, we construct a deep neural network with downsampled deep
convolutional layers followed by a fully connected layer for approximating a
composite function $f\circ Q$ which will be used to prove our first two main
results. Our construction makes full use of the special structure of the
approximated function induced by the polynomial $Q$ and the univariate
function $f$. It is based on an important fact [16, 18] on the space
${\mathcal{P}}_{q}^{h}(\mathbb{R}^{d})$ of homogeneous polynomials on
$\mathbb{R}^{d}$ of degree $q$ that ${\mathcal{P}}_{q}^{h}(\mathbb{R}^{d})$
has a basis $\\{(\xi_{k}\cdot x)^{q}\\}_{k=1}^{n_{q}}$ for some vector set
$\\{\xi_{k}\\}_{k=1}^{n_{q}}\subset\mathbb{R}^{d}\setminus\\{0\\}$ and this
vector set can even be chosen in such way that the homogeneous polynomial set
$\\{(\xi_{k}\cdot x)^{\ell}\\}_{k=1}^{n_{q}}$ spans the space
${\mathcal{P}}_{\ell}^{h}(\mathbb{R}^{d})$ for every
$\ell\in\\{1,\ldots,q-1\\}$. Applying this fact to the polynomial $Q$ of
degree $q$ yields the following lemma stated in [36]. Take
$J_{1}=\lceil\frac{n_{q}d-1}{s-1}\rceil$ in this section except in the proof
of Theorem 2.

######  Lemma 1.

Let $d\in\mathbb{N}$ and $q\in\mathbb{N}$. Then there exists a set
$\\{\xi_{k}\\}_{k=1}^{n_{q}}\subset\\{\xi\in\mathbb{R}^{d}:|\xi|=1\\}$ of
vectors with $\ell_{2}$-norm $1$ such that for any
$Q\in{\mathcal{P}}_{q}(\mathbb{R}^{d})$ we can find a set of coefficients
$\\{\beta_{k,\ell}:k=1,\ldots,n_{q},\ell=1,\ldots,q\\}\subset\mathbb{R}$ such
that

$Q(x)=Q(0)+\sum_{k=1}^{n_{q}}\sum_{\ell=1}^{q}\beta_{k,\ell}(\xi_{k}\cdot
x)^{\ell},\qquad x\in\mathbb{R}^{d}.$ (4.1)

Our deep neural network consists of two groups of CNN layers and one fully
connected layer: the first group with a downsampling operation for realizing
the linear features $\\{\xi_{k}\cdot x\\}_{k}$, the second for produce ridge
functions $\\{\sigma(\xi_{k}\cdot x-t_{j})\\}_{k,j}$ leading to realizing
$\\{(\xi_{k}\cdot x)^{\ell}\\}_{k,\ell}$ in (4.1), and the last fully
connected layer for approximating the univariate function $f$ to achieve an
approximation of $f(Q(x))$.

###  4.1 Realizing linear features by DCNNs

To realize the linear features $\\{\xi_{k}\cdot x\\}_{k=1}^{n_{q}}$, we apply
the following lemma from [36, 38].

######  Lemma 2.

Let $s\geq 2$ and $W=(W_{k})_{k=-\infty}^{\infty}$ be a sequence supported in
$\\{0,\ldots,{\mathcal{M}}\\}$ with ${\mathcal{M}}\geq 0$. Then there exists a
finite sequence of filters $\\{w^{(j)}\\}_{j=1}^{p}$ each supported in
$\\{0,\ldots,s\\}$ with $p\leq\lceil\frac{{\mathcal{M}}}{s-1}\rceil$ such that
the following convolutional factorization holds true

$W=w^{(p)}{*}w^{(p-1)}{*}\ldots{*}w^{(2)}{*}w^{(1)}.$ (4.2)

We show that the components of $h^{(J_{1})}(x)$ can realize the linear
features $\\{\xi_{k}\cdot x\\}_{k=1}^{n_{q}}$.

######  Lemma 3.

Let $\\{\xi_{k}\\}_{k=1}^{n_{q}}\subset\\{\xi\in\mathbb{R}^{d}:|\xi|=1\\}$.
There exist filters $\\{w^{(j)}\\}_{j=1}^{J_{1}}$ each supported in
$\\{0,\ldots,s\\}$ with $J_{1}=\lceil\frac{n_{q}d-1}{s-1}\rceil$ and bias
vectors $\\{b^{(j)}\\}_{j=1}^{J_{1}}$ each satisfying the restriction in (1.4)
such that the $J_{1}$-th layer after downsampling is

$h^{(J_{1})}(x)=\left[\begin{array}[]{c}\xi_{1}\cdot x\\\ \vdots\\\
\xi_{n_{q}}\cdot x\\\ \vdots\\\ \xi_{d_{J_{1}}}\cdot x\end{array}\right]+B{\bf
1}_{d_{J_{1}}},$ (4.3)

where $\\{\xi_{k}\\}_{k=n_{q}+1}^{d_{J_{1}}}\subset\mathbb{R}^{d}$, $B$ is a
positive constant, and ${\bf 1}_{d_{J_{1}}}$ the constant $1$ vector in
$\mathbb{R}^{d_{J_{1}}}$. Moreover, we have

$\left|\xi_{k}\cdot x\right|\leq B,\qquad\forall
x\in\Omega,k=1,\ldots,d_{J_{1}}.$ (4.4)

The number ${\mathcal{N}}_{1}$ of free parameters in the first $J_{1}$ layers
is

${\mathcal{N}}_{1}=(3s+2)J_{1}=(3s+2)\left\lceil\frac{n_{q}d-1}{s-1}\right\rceil.$

###### Proof.

We use some ideas and results from [38] to prove our conclusion.

First, we define a sequence $W$ supported in $\\{0,1,\ldots,n_{q}d-1\\}$ by
stacking the vectors $\\{\xi_{k}\\}_{k=1}^{n_{q}}$ (with the components of
each vector reversed) as

$W_{j+(k-1)d}=\left(\xi_{k}\right)_{d-j},\qquad j=0,1,\ldots,d-1,\
k=1,2,\ldots,n_{q}.$

Then

$\left[W_{d-1+(k-1)d}\ \ldots\ W_{1+(k-1)d}\
W_{(k-1)d}\right]=\xi_{k}^{T},\qquad k=1,2,\ldots,n_{q}.$ (4.5)

By Lemma 2, there exist filters $\\{w^{(j)}\\}_{j=1}^{p}$ each supported in
$\\{0,\ldots,s\\}$ with $p\leq\lceil\frac{n_{q}d-1}{s-1}\rceil$ such that
(4.2) holds true. Taking $\\{w^{(j)}\\}_{j=p+1}^{J_{1}}$ to be the delta
sequence $\delta_{0}$ given by $\left(\delta_{0}\right)_{i}=0$ for
$i\in\mathbb{Z}\setminus\\{0\\}$ and $\left(\delta_{0}\right)_{0}=1$ yields

$W=w^{(J_{1})}{*}w^{(J_{1}-1)}{*}\ldots{*}w^{(2)}{*}w^{(1)}.$ (4.6)

Hence we know from [38, Lemma 1] that the filters
$\\{w^{(j)}\\}_{j=1}^{J_{1}}$ induce Toeplitz type matrices
$\\{T^{(j)}\in\mathbb{R}^{(d_{j-1}+s)\times d_{j-1}}\\}_{j=1}^{J_{1}}$ which
satisfy the matrix product identity

$T^{(J_{1})}T^{(J_{1}-1)}\ldots
T^{(2)}T^{(1)}=\left(W_{i-k}\right)_{i=1,\ldots,d+J_{1}s,\ k=1,\ldots,d}.$
(4.7)

Here the matrix on the right-hand side takes the form

$\left[\begin{array}[]{llll}W_{0}&0&\cdots&0\\\ W_{1}&W_{0}&\ddots&0\\\
\vdots&\ddots&\ddots&\vdots\\\ W_{d-1}&\cdots&W_{1}&W_{0}\\\
W_{d}&W_{d-1}&\cdots&W_{1}\\\ \vdots&\ddots&\ddots&\vdots\\\
W_{J_{1}s}&\cdots&\ddots&\vdots\\\ 0&W_{J_{1}s}&\cdots&\vdots\\\
\vdots&\ddots&\ddots&\vdots\\\ 0&\cdots&0&W_{J_{1}s}\end{array}\right].$ (4.8)

Note that $d+J_{1}s=d+\lceil\frac{n_{q}d-1}{s-1}\rceil s\geq
d+\frac{n_{q}d-1}{s-1}s\geq d+n_{q}d$ which implies

$d_{J_{1}}=\left\lfloor\frac{d+J_{1}s}{d}\right\rfloor\geq n_{q}+1.$

Then we choose the bias vectors $\\{b^{(j)}\\}_{j=1}^{J_{1}}$ by
$b^{(1)}=-\|w^{(1)}\|_{1}{\bf 1}_{d_{1}}$ and

$b^{(j)}=\left(\Pi_{p=1}^{j-1}\|w^{(p)}\|_{1}\right)T^{(j)}{\bf
1}_{d_{j-1}}-\left(\Pi_{p=1}^{j}\|w^{(p)}\|_{1}\right){\bf
1}_{d_{j-1}+s},\qquad j=2,\ldots,J_{1},$

where $\|w\|_{1}=\sum_{k\in{\mathbb{Z}}}|w_{k}|$ denotes the $\ell^{1}$-norm
of a finitely supported sequence $w$. With this choice we know from [38, Lemma
3] that

$h^{(J_{1})}(x)={\mathfrak{D}}_{d}\left(T^{(J_{1})}T^{(J_{1}-1)}\ldots
T^{(2)}T^{(1)}x+\left(\Pi_{p=1}^{J_{1}}\|w^{(p)}\|_{1}\right){\bf
1}_{d_{J_{1}}}\right).$

Combining this with (4.5) and (4.7), we see that the $k$-th component of
$h^{(J_{1})}(x)$ equals

$\left[W_{d-1+(k-1)d}\ \ldots\ W_{1+(k-1)d}\
W_{(k-1)d}\right]x+\Pi_{p=1}^{J_{1}}\|w^{(p)}\|_{1}=\xi_{k}\cdot
x+\Pi_{p=1}^{J_{1}}\|w^{(p)}\|_{1},$

where the vectors $\xi_{k}$ with $k=1,\ldots,n_{q}$ coincide with those from
the given set $\\{\xi_{k}\\}_{k=n_{q}+1}^{d_{J_{1}}}\subset\mathbb{R}^{d}$.
This verifies the desired expression (4.3) with the constant
$B=\Pi_{p=1}^{J_{1}}\|w^{(p)}\|_{1}$ and $\xi_{k}=\left[W_{kd-1}\ W_{kd-2}\
\ldots W_{kd-d}\right]^{T}\in\mathbb{R}^{d}$ for $k>n_{q}.$ We also see that
(4.4) holds true.

Observe that each filter $w^{(j)}$ has $s+1$ free parameters to be determined
and each bias vector $b^{(j)}$ has $2s+1$ free parameters. Then the stated
expression for ${\mathcal{N}}_{1}$ is valid. This proves the lemma. ∎

###  4.2 Producing ridge functions by DCNNs

The second group of convolutional layers in our network is used to produce
ridge functions $\\{\sigma(\xi_{k}\cdot
x-t_{j}):k=1,\ldots,n_{q},j=1,\ldots,2N+3\\}$ with $N\in\mathbb{N}$ where

$t_{j}=-1+\frac{j-2}{N},\qquad j=1,\ldots,2N+3.$ (4.9)

This is done by conducting a convolutional factorization of a sequence
$W^{[1]}$ supported on $\\{0,\ldots,(2N+3)d_{J_{1}}\\}$ given by

$W^{[1]}_{i}=\left\\{\begin{array}[]{ll}1,&\hbox{if}\
i\in\\{kd_{J_{1}}\\}_{k=0}^{2N+3},\\\ 0,&\hbox{otherwise.}\end{array}\right.$
(4.10)

If we denote the symbol $\tilde{u}$ of a filter $u$ supported in
$\mathbb{Z}_{+}$ to be a polynomial on $\mathbb{C}$ given by
$\tilde{u}(z)=\sum_{k\in\mathbb{Z}}u_{k}z^{k}$, then the symbol
$\widetilde{W^{[1]}}$ of the sequence $W^{[1]}$ is given by

$\widetilde{W^{[1]}}(z)=\sum_{k=0}^{2N+3}z^{kd_{J_{1}}},\qquad
z\in\mathbb{C}.$

It has $(2N+3)d_{J_{1}}$ complex roots

$e^{\frac{i2\ell\pi}{d_{J_{1}}(2N+4)}},\qquad 1\leq\ell\leq
d_{J_{1}}(2N+4)-1,\ (2N+4)\not|\ell.$

Applying a procedure for convolutional factorization stated in [38], we can
find explicit expressions without free parameters involved for the filters
$\\{w^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$, each supported in $\\{0,\ldots,s\\}$,
with $J_{2}=J_{1}+\left\lceil\frac{(2N+3)d_{J_{1}}}{s-1}\right\rceil$ such
that

$W^{[1]}=w^{(J_{2})}{*}\ldots{*}w^{(J_{1}+2)}{*}w^{(J_{1}+1)}.$ (4.11)

Then the second group of convolutional layers is constructed as follows.

######  Lemma 4.

For $h^{(J_{1})}(x)$ given by (4.3), $N\in\mathbb{N}$, and the filters
$\\{w^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$ explicitly constructed above satisfying
(4.10) and (4.11), there exist bias vectors
$\\{b^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$ satisfying (1.4) such that

$\left(h^{(J_{2})}(x)\right)_{(j-1)d_{J_{1}}+k}=\left\\{\begin{array}[]{ll}\sigma\left(\xi_{k}\cdot
x-t_{j}\right),&\hbox{if}\ 1\leq k\leq n_{q},1\leq j\leq 2N+3,\\\
0,&\hbox{otherwise.}\end{array}\right.$ (4.12)

The number ${\mathcal{N}}_{2}$ of free parameters in the second group of
$J_{2}-J_{1}$ convolutional layers is

${\mathcal{N}}_{2}=d_{J_{1}}+(3s+1)\left\lceil\frac{(2N+3)d_{J_{1}}}{s-1}\right\rceil-(2s+1).$

###### Proof.

As in the proof of Lemma 3, we choose the bias vectors
$\\{b^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$ by

$b^{(j)}=B\left(\Pi_{p=J_{1}+1}^{j-1}\|w^{(p)}\|_{1}\right)T^{(j)}{\bf
1}_{d_{j-1}}-B\left(\Pi_{p=J_{1}+1}^{j}\|w^{(p)}\|_{1}\right){\bf
1}_{d_{j-1}+s}$

for $j=J_{1}+1,\ldots,J_{2}-1$. Then we know from [38, Lemma 1 and Lemma 3]
again that

$h^{(J_{2}-1)}(x)=T^{(J_{2}-1)}\ldots
T^{(J_{1}+2)}T^{(J_{1}+1)}\left[\xi_{\ell}\cdot
x\right]_{\ell=1}^{d_{J_{1}}}+B\left(\Pi_{p=J_{1}+1}^{J_{2}-1}\|w^{(p)}\|_{1}\right){\bf
1}_{d_{J_{2}-1}}$

and

$T^{(J_{2})}T^{(J_{2}-1)}\ldots
T^{(J_{1}+2)}T^{(J_{1}+1)}=\left(W^{[1]}_{i-k}\right)_{i=1,\ldots,d_{J_{1}}+(J_{2}-J_{1})s,\
k=1,\ldots,d_{J_{1}}}$

which has entry $(i,k)$ with
$i\in\\{1,\ldots,d_{J_{2}}\\},k\in\\{1,\ldots,d_{J_{1}}\\}$ given by

$W^{[1]}_{i-k}=\left\\{\begin{array}[]{ll}1,&\hbox{if}\
i=k,k+d_{J_{1}},k+2d_{J_{1}},\ldots,k+(2N+2)d_{J_{1}},\\\
0,&\hbox{otherwise.}\end{array}\right.$

It follows that the submatrix of $T^{(J_{2})}T^{(J_{2}-1)}\ldots
T^{(J_{1}+2)}T^{(J_{1}+1)}$ consisting of the first $(2N+3)d_{J_{1}}$ rows can
be expressed as a $(2N+3)\times 1$ block matrix with each block being the
$d_{J_{1}}\times d_{J_{1}}$ identity matrix. Thus by choosing the bias vector
$b^{(J_{2})}$ as

$\displaystyle\left(b^{(J_{2})}\right)_{i}$ $\displaystyle=$ $\displaystyle
B\left(\Pi_{p=J_{1}+1}^{J_{2}-1}\|w^{(p)}\|_{1}\right)\left(T^{(J_{2})}{\bf
1}_{d_{J_{2}-1}}\right)_{i}$
$\displaystyle+\left\\{\begin{array}[]{ll}t_{j},&\hbox{if}\
(j-1)d_{J_{1}}+1\leq i\leq(j-1)d_{J_{1}}+n_{q},1\leq j\leq 2N+3,\\\
B,&\hbox{otherwise,}\end{array}\right.$

we see that (4.12) holds true.

Since the filters $\\{w^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$ are explicitly
constructed without free parameters involved, the free parameters required in
the second group of $J_{2}-J_{1}$ layers are those from the bias vectors
$\\{b^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$ and the number is

${\mathcal{N}}_{2}=(2s+1)(J_{2}-J_{1}-1)+d_{J_{2}}=d_{J_{1}}+(3s+1)\left\lceil\frac{(2N+3)d_{J_{1}}}{s-1}\right\rceil-(2s+1),$

which verifies the stated expression for ${\mathcal{N}}_{2}$. This proves the
lemma. ∎

###  4.3 Approximating $f\circ Q$ with a fully connected layer

Recall that the layer $h^{(J_{2})}$ expressed in (4.12) can be written as

$h^{(J_{2})}(x)=\left[H_{1}^{T}\ H_{2}^{T}\ \ldots H^{T}_{2N+3}\ 0\ \ldots\
0\right]^{T},$

where for $j=1,2,\ldots,2N+3$,

$H_{j}^{T}=\left[\sigma\left(\xi_{1}\cdot x-t_{j}\right)\
\sigma\left(\xi_{2}\cdot x-t_{j}\right)\ \ldots\ \sigma\left(\xi_{n_{q}}\cdot
x-t_{j}\right)\ 0\ldots 0\right]\in\mathbb{R}^{d_{J_{1}}}.$

Then we can construct a fully connected layer to realize $(\xi_{k}\cdot
x)^{\ell},1\leq\ell\leq q,$ for approximating the polynomial $Q$ and then the
function $f(Q(x))$. To this end, we need the following well-known scheme of
approximating univariate functions by continuous piecewise linear functions
(splines) spanned by $\\{\sigma(\cdot-t_{i})\\}^{2N+3}_{i=1}$ with
$t_{i}=-1+\frac{i-2}{N}$, which can be found in [36, Lemma 6].

######  Lemma 5.

For $N\in\mathbb{N}$, let
$\textbf{t}=\\{t_{i}:=-1+\frac{i-2}{N}\\}_{i=1}^{2N+3}$ be the uniform mesh on
$\left[-1-\frac{1}{N},1+\frac{1}{N}\right]$, $L_{\textbf{t}}$ be a linear
operator on $C[-1,1]$ given by

$L_{\textbf{t}}(g)(u)=\sum_{i=2}^{2N+2}g(t_{i})\delta_{i}(u),\quad
u\in[-1,1],\,g\in C[-1,1],$

with the hat functions $\delta_{i}\in C(\mathbb{R})$, $i=2,\ldots,2N+2$, given
by

$\delta_{i}(u)=N(\sigma\left(u-t_{i-1}\right)-2\sigma\left(u-t_{i}\right)+\sigma\left(u-t_{i+1}\right)),\qquad
u\in\mathbb{R}.$

Then for $g\in C[-1,1]$, we have
$\left\|L_{\mathbf{t}}(g)\right\|_{C\left[-1,1\right]}\leq\left\|g\right\|_{C\left[-1,1\right]}$
and

$\left\|L_{\mathbf{t}}(g)-g\right\|_{C\left[-1,1\right]}\leq
2\omega\left(g,1/N\right)$

where $\omega(g,\mu)$ is the modulus of continuity of $g$ given for
$\mu\in(0,1]$ by

$\omega(g,\mu)=\sup_{|t|\leq\mu}\left\\{|g(v)-g(v+t)|:v,v+t\in[-1,1]\right\\}.$

For convenience, we introduce a linear operator
${\mathcal{L}}_{N}:\mathbb{R}^{2N+1}\to\mathbb{R}^{2N+3}$ given for
$\zeta=(\zeta_{i})_{i=2}^{2N+2}\in\mathbb{R}^{2N+1}$ by

$\left({\mathcal{L}}_{N}(\zeta)\right)_{i}=\begin{cases}\zeta_{2},&\text{for}~{}i=1,\\\
\zeta_{3}-2\zeta_{2},&\text{for}~{}i=2,\\\
\zeta_{i-1}-2\zeta_{i}+\zeta_{i+1},&\text{for}~{}3\leq i\leq 2N+1,\\\
\zeta_{2N+1}-2\zeta_{2N+2},&\text{for}~{}i=2N+2,\\\
\zeta_{2N+2},&\text{for}~{}i=2N+3.\end{cases}$ (4.14)

It enables us to express the operator $L_{\textbf{t}}$ on $C[-1,1]$ in terms
of $\\{\sigma\left(\cdot-t_{j}\right)\\}_{j=1}^{2N+3}$ as

$L_{\textbf{t}}(g)=N\sum_{i=1}^{2N+3}\left({\mathcal{L}}_{N}\left(\left\\{g(t_{k})\right\\}_{k=2}^{2N+2}\right)\right)_{i}\sigma\left(\cdot-
t_{i}\right),\qquad g\in C[-1,1].$

In particular, for a homogeneous polynomial $g(u)=u^{\ell}$ with
$\ell\in\\{1,\ldots,q\\}$ and a vector
$v^{[\ell]}={\mathcal{L}}_{N}\left(\left\\{t_{k}^{\ell}\right\\}_{k=2}^{2N+2}\right)\in\mathbb{R}^{2N+3}$,
we have

$\sup_{u\in[-1,1]}\left|N\sum_{j=1}^{2N+3}v^{[\ell]}_{j}\sigma\left(u-t_{j}\right)-u^{\ell}\right|\leq\frac{2\ell}{N}.$
(4.15)

Denote the $n_{q}\times(d_{J_{1}}-n_{q})$ zero matrix as $O$, the
$n_{q}\times(d_{J_{2}}-(2N+2)d_{J_{1}}-n_{q})$ zero matrix as $\widehat{O}$,
and

$F^{(N)}=N\left[\begin{array}[]{ccccccc}v^{[1]}_{1}I_{n_{q}}&O&v^{[1]}_{2}I_{n_{q}}&O&\ldots&v^{[1]}_{2N+3}I_{n_{q}}&\widehat{O}\\\
v^{[2]}_{1}I_{n_{q}}&O&v^{[2]}_{2}I_{n_{q}}&O&\ldots&v^{[2]}_{2N+3}I_{n_{q}}&\widehat{O}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
v^{[q]}_{1}I_{n_{q}}&O&v^{[q]}_{2}I_{n_{q}}&O&\ldots&v^{[q]}_{2N+3}I_{n_{q}}&\widehat{O}\end{array}\right]\in\mathbb{R}^{(qn_{q})\times
d_{J_{2}}}.$ (4.16)

Then

$F^{(N)}h^{(J_{2})}(x)=\left[P_{1}^{T}\ P_{2}^{T}\ \ldots
P^{T}_{q}\right]^{T},$

where for $\ell=1,2,\ldots,q$, $P_{\ell}$ is a vector with $n_{q}$ components
given by

$P_{\ell}^{T}=\left[N\sum_{j=1}^{2N+3}v^{[\ell]}_{j}\sigma\left(\xi_{1}\cdot
x-t_{j}\right)\ \ldots\
N\sum_{j=1}^{2N+3}v^{[\ell]}_{j}\sigma\left(\xi_{n_{q}}\cdot
x-t_{j}\right)\right].$

If we denote a row vector $\gamma$ of size $qn_{q}$ as

$\gamma=\left[\gamma_{1,1}\ \gamma_{2,1}\ \ldots,\gamma_{n_{q},1}\
\gamma_{1,2}\ \gamma_{2,2}\ \ldots,\gamma_{n_{q},2}\ \ldots\ \gamma_{1,q}\
\gamma_{2,q}\ \ldots,\gamma_{n_{q},q}\right],$

then we have

$\gamma
F^{(N)}h^{(J_{2})}(x)=\sum_{k=1}^{n_{q}}\sum_{\ell=1}^{q}\gamma_{k,\ell}N\sum_{j=1}^{2N_{1}+3}v^{[\ell]}_{j}\sigma\left(\xi_{k}\cdot
x-t_{j}\right)$

and by (4.15),

$\sup_{|x|\leq 1}\left|\gamma
F^{(N)}h^{(J_{2})}(x)-\sum_{k=1}^{n_{q}}\sum_{\ell=1}^{q}\gamma_{k,\ell}\left(\xi_{k}\cdot
x\right)^{\ell}\right|\leq\frac{2q\|\gamma\|_{1}}{N}.$

In particular, by taking $\gamma$ to be the coefficient vector $\beta$ given
in Lemma 1, if we denote

$\widehat{Q}(x)=\beta F^{(N)}h^{(J_{2})}(x)+Q(0),$ (4.17)

then we have

$\sup_{|x|\leq
1}\left|\widehat{Q}(x)-Q(x)\right|\leq\frac{2q\|\beta\|_{1}}{N},$ (4.18)

which implies

$\left\|\widehat{Q}\right\|_{C(\Omega)}\leq\widehat{B}_{Q}:=B_{Q}+2q\|\beta\|_{1}.$
(4.19)

Now we can construct the fully connected layer of width $2N+3$ to approximate
the function $f(Q(x))$.

######  Lemma 6.

Let $q,N\in\mathbb{N}$, $Q$ be a polynomial on $\Omega$ of degree at most $q$,
$f\in C^{0,\alpha}[-B_{Q},B_{Q}]$ for some $0<\alpha\leq 1$, and
$h^{(J_{2})}(x)$ be given by (4.12). Then for the last layer
$h^{(J_{2}+1)}(x)=\sigma\left(F^{[J_{2}+1]}h^{(J_{2})}(x)-b^{(J_{2}+1)}\right)$
of width $2N+3$ with

$F^{[J_{2}+1]}=\left[\begin{array}[]{c}\beta\\\ \vdots\\\
\beta\end{array}\right]F^{(N)},\qquad b^{(J_{2}+1)}=-Q(0){\bf
1}_{2N+3}+\widehat{B}_{Q}\left[\begin{array}[]{c}t_{1}\\\ \vdots\\\
t_{2N+3}\end{array}\right],$ (4.20)

by taking the coefficient vector
$c=\frac{N}{\widehat{B}_{Q}}{\mathcal{L}}_{N}\left(\left\\{f\left(\widehat{B}_{Q}t_{k}\right)\right\\}_{k=2}^{2N+2}\right)\in\mathbb{R}^{2N+3}$,
we have

$\left\|\sum_{j=1}^{2N+3}c_{j}\left(h^{(J_{2}+1)}(x)\right)_{j}-f\left(Q(x)\right)\right\|_{C(\Omega)}\leq\frac{4\widehat{B}_{Q}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}$
(4.21)

and

$\|c\|_{\infty}\leq\frac{4\|f\|_{\infty}N}{\widehat{B}_{Q}}.$ (4.22)

The total number ${\mathcal{N}}_{3}$ of free parameters in the last layer is

${\mathcal{N}}_{3}=2N+qn_{q}+3.$

###### Proof.

With the stated connection matrix $F^{[J_{2}+1]}$ and bias vector
$b^{(J_{2}+1)}$, the last layer
$h^{(J_{2}+1)}(x)=\sigma\left(F^{[J_{2}+1]}h^{(J_{2})}(x)-b^{(J_{2}+1)}\right)$
has components

$\left(h^{(J_{2}+1)}(x)\right)_{j}=\sigma\left(\beta
F^{(N)}h^{(J_{2})}(x)+Q(0)-\widehat{B}_{Q}t_{j}\right)=\sigma\left(\widehat{Q}(x)-\widehat{B}_{Q}t_{j}\right)$
(4.23)

with $j=1,\ldots,2N+3.$

Apply Lemma 5 to the function $g(u)=f\left(\widehat{B}_{Q}u\right)$ on
$[-1,1]$ where $f$ has been extended outside $[-B_{Q},B_{Q}]$ as
$f(u)=f(\hbox{sgn}(u)B_{Q})$ for $|u|>B_{Q}$, which keeps the same semi-norm
$|f|_{C^{0,\alpha}}$. Then $g$ is Lipschitz-$\alpha$ with semi-norm
$|g|_{C^{0,\alpha}[-1,1]}\leq\widehat{B}_{Q}^{\alpha}|f|_{C^{0,\alpha}}$, and
we know with
$\widehat{c}={\mathcal{L}}_{N}\left(\left\\{f\left(\widehat{B}_{Q}t_{k}\right)\right\\}_{k=2}^{2N+2}\right)$,
there holds

$\sup_{u\in[-1,1]}\left|N\sum_{j=1}^{2N+3}\widehat{c}_{j}\sigma\left(u-t_{j}\right)-f\left(\widehat{B}_{Q}u\right)\right|\leq\frac{2\widehat{B}_{Q}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}.$

Since (4.19) implies $u=\widehat{Q}(x)/\widehat{B}_{Q}\in[-1,1]$ for all
$x\in\Omega$ and
$\sigma\left(v/\widehat{B}_{Q}\right)=\frac{1}{\widehat{B}_{Q}}\sigma\left(v\right)$
for all $v\in\mathbb{R}$, we have

$\sup_{x\in\Omega}\left|\frac{N}{\widehat{B}_{Q}}\sum_{j=1}^{2N+3}\widehat{c}_{j}\sigma\left(\widehat{Q}(x)-\widehat{B}_{Q}t_{j}\right)-f\left(\widehat{Q}(x)\right)\right|\leq\frac{2\widehat{B}_{Q}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}.$

Combining this estimate with (4.23), (4.23), (4.18) and the Lipschitz-$\alpha$
property of $f$ yields

$\displaystyle\sup_{x\in\Omega}\left|\sum_{j=1}^{2N+3}c_{j}\left(h^{(J_{2}+1)}(x)\right)_{j}-f\left(Q(x)\right)\right|$
$\displaystyle\leq$
$\displaystyle\frac{2\widehat{B}_{Q}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}+\sup_{x\in\Omega}\left|f\left(\widehat{Q}(x)\right)-f\left(Q(x)\right)\right|$
$\displaystyle\leq$
$\displaystyle\frac{2\widehat{B}_{Q}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}+|f|_{C^{0,\alpha}}\left(\frac{2q\|\beta\|_{1}}{N}\right)^{\alpha}.$

So the desired bound (4.21) follows. From the expression
$c=\frac{N}{\widehat{B}_{Q}}{\mathcal{L}}_{N}\left(\left\\{f\left(\widehat{B}_{Q}t_{k}\right)\right\\}_{k=2}^{2N+2}\right)$
of the coefficient vector, we find (4.22) is valid.

Since the matrix $F^{(N)}$ is constructed explicitly, the free parameters in
the last layer are those from $\beta$, and the numbers $Q(0)$ and
$\widehat{B}_{Q}$. Together with the coefficients
$\left\\{f\left(\widehat{B}_{Q}t_{k}\right)\right\\}_{k=2}^{2N+2}$, the total
number of free parameters in the last layer to get the approximation is

${\mathcal{N}}_{3}=qn_{q}+2+2N+1=2N+qn_{q}+3.$

This proves the lemma. ∎

###  4.4 Deriving rates of approximation

Now we can prove our first two main results.

###### Proof of Theorem 1.

First, we construct the first group of
$J_{1}=\lceil\frac{n_{q}d-1}{s-1}\rceil$ convolutional layers followed by a
downsampling operation as in subsection 4.1 and get $h^{(J_{1})}(x)$ of linear
features expressed in (4.3) of Lemma 3.

Next, we construct the second group of
$J_{2}-J_{1}=\left\lceil\frac{(2N+3)d_{J_{1}}}{s-1}\right\rceil$ convolutional
layers as in subsection 4.2 and get $h^{(J_{2})}(x)$ of ridge functions
$\\{\sigma\left(\xi_{k}\cdot x-t_{j}\right)\\}_{k,j}$ expressed in (4.12) of
Lemma 4.

Then we use the last layer
$h^{(J_{2}+1)}(x)=\sigma\left(F^{[J_{2}+1]}h^{(J_{2})}(x)-b^{(J_{2}+1)}\right)$
of width $2N+3$ constructed in subsection 4.3 with a matrix $F^{[J_{2}+1]}$ of
identical rows, and know from (4.21) of Lemma 6 that (2.1) holds true with
$C_{Q,\alpha}=4\widehat{B}_{Q}^{\alpha}$ and $c$ satisfying
$\|c\|_{\infty}\leq\frac{4\|f\|_{\infty}N}{\widehat{B}_{Q}}$.

The total number
${\mathcal{N}}={\mathcal{N}}_{1}+{\mathcal{N}}_{2}+{\mathcal{N}}_{3}$ of free
parameters in this network is

$(3s+2)J_{1}+d_{J_{1}}+(3s+1)\left\lceil\frac{(2N+3)d_{J_{1}}}{s-1}\right\rceil-(2s+1)+2N+qn_{q}+3.$

Since $s\geq 2$ and $\lceil\frac{n}{s-1}\rceil\leq\frac{n+s-2}{s-1}$ for any
integer $n\in\mathbb{N}$, we see that

$J_{1}=\left\lceil\frac{n_{q}d-1}{s-1}\right\rceil\leq\frac{n_{q}d-2}{s-1}+1$

and

$d_{J_{1}}=\left\lfloor\frac{d+J_{1}s}{d}\right\rfloor\leq
1+\frac{s}{d}J_{1}.$ (4.24)

Hence

$\displaystyle{\mathcal{N}}$ $\displaystyle\leq$
$\displaystyle\left(3s+2+\frac{s}{d}+\frac{s}{d}7(2N+3)\right)J_{1}+7(2N+3)+s+4+2N+qn_{q}$
$\displaystyle\leq$
$\displaystyle\left(30+28n_{q}\right)N+(8d+q+44)n_{q}+4s+49.$

To achieve the approximation accuracy $0<\epsilon\leq 1$, by using the bound
$n_{q}\leq d^{q}$ and taking

$N=\left\lceil
C_{Q,\alpha}^{\frac{1}{\alpha}}|f|_{C^{0,\alpha}}^{\frac{1}{\alpha}}\epsilon^{-\frac{1}{\alpha}}\right\rceil,$

we know that

$N\leq
C_{Q,\alpha}^{\frac{1}{\alpha}}|f|_{C^{0,\alpha}}^{\frac{1}{\alpha}}\epsilon^{-\frac{1}{\alpha}}+1\leq\left(C_{Q,\alpha}^{\frac{1}{\alpha}}|f|_{C^{0,\alpha}}^{\frac{1}{\alpha}}+1\right)\epsilon^{-\frac{1}{\alpha}}$

and thereby

${\mathcal{N}}\leq
43\left(C_{Q,\alpha}^{\frac{1}{\alpha}}|f|_{C^{0,\alpha}}^{\frac{1}{\alpha}}+1\right)d^{q}\epsilon^{-\frac{1}{\alpha}}+(45+q)d^{q+1}.$

This proves the stated complexity with the constant

$C_{Q,\alpha,|f|_{C^{0,\alpha}}}=22\left(C_{Q,\alpha}^{\frac{1}{\alpha}}|f|_{C^{0,\alpha}}^{\frac{1}{\alpha}}+1\right)+45+q.$

The proof of Theorem 1 is complete. ∎

###### Proof of Theorem 2.

The special radial form of the approximated function enables us to skip the
first group of convolutional layers in subsection 4.1 by taking $J_{1}=0$, and
to construct a group of $J=\left\lceil\frac{(2N+3)d}{s-1}\right\rceil$
convolutional layers as in subsection 4.2 by replacing $d_{J_{1}}$ and $n_{q}$
by the size $d$ of the input data $x=[x_{1}\ldots x_{d}]^{T}$, and the
constant $B$ by $1$. Then $h^{(J)}$ has width $d_{J}=d+Js$ and we have

$\left(h^{(J)}(x)\right)_{(j-1)d+k}=\left\\{\begin{array}[]{ll}\sigma\left(x_{k}-t_{j}\right),&\hbox{if}\
1\leq k\leq d,1\leq j\leq 2N+3,\\\ 0,&\hbox{otherwise}\end{array}\right.$

and the number ${\mathcal{N}}_{1}$ of free parameters in the convolutional
layers is

${\mathcal{N}}_{1}=d+(3s+1)\left\lceil\frac{(2N+3)d}{s-1}\right\rceil-(2s+1),$

which is similar to the expressions in Lemma 4.

Besides the reduction of the first groups of convolutional layers for
approximating $f\circ Q$ with a general unknown feature polynomial $Q$, the
second reduction for approximating the radial function $f(|x|^{2})$ is to take
only one row block of the matrix $F^{(N_{1})}$ corresponding to $\ell=2$ as

$F^{(N)}=N\left[v^{[2]}_{1}I_{d}\ \ v^{[2]}_{2}I_{d}\ \ldots\
v^{[2]}_{2N+3}I_{d}\ \widehat{O}\right]\in\mathbb{R}^{d\times d_{J}}$

with the $d\times(d_{J}-(2N+3)d)$ zero matrix $\widehat{O}$, and to take a row
vector $\beta={\bf 1}_{d}$ of size $d$ from the norm square
$|x|^{2}=\sum_{k=1}^{d}x_{k}^{2}$. Then for $\widehat{Q}(x)=\beta
F^{(N)}h^{(J)}(x)$, by Lemma 5 we have

$\sup_{|x|\leq
1}\left|\widehat{Q}(x)-|x|^{2}\right|\leq\frac{4d}{N}\quad\hbox{which
implies}\ \left\|\widehat{Q}\right\|_{C(\Omega)}\leq\widehat{B}:=1+4d.$ (4.25)

Finally we use the last layer
$h^{(J+1)}(x)=\sigma\left(F^{[J+1]}h^{(J)}(x)-b^{(J+1)}\right)$ of width
$2N+3$ constructed in subsection 4.3 with

$F^{[J+1]}=\left[\begin{array}[]{c}\beta\\\ \vdots\\\
\beta\end{array}\right]F^{(N)},\qquad
b^{(J+1)}=\widehat{B}\left[\begin{array}[]{c}t_{1}\\\ \vdots\\\
t_{2N_{2}+3}\end{array}\right].$

Then $\left(h^{(J+1)}(x)\right)_{j}=\sigma\left(\beta
F^{(N)}h^{(J)}(x)-\widehat{B}t_{j}\right)=\sigma\left(\widehat{Q}(x)-\widehat{B}t_{j}\right)$
for $j=1,\ldots,2N+3$.

As in the proof of Lemma 6, we apply Lemma 5 to the function
$f\left(\widehat{B}\cdot\right)$ on $[-1,1]$ where $f$ has been extended
outside $[0,1]$ as $f(u)=f(1)$ for $u>1$ and $f(u)=f(0)$ for $u<0$, which
keeps the same semi-norm $|f|_{C^{0,\alpha}}$. Then we take
$\widehat{c}={\mathcal{L}}_{N}\left(\left\\{f\left(\widehat{B}t_{k}\right)\right\\}_{k=2}^{2N+2}\right)$
and get

$\sup_{u\in[-1,1]}\left|N\sum_{j=1}^{2N+3}\widehat{c}_{j}\sigma\left(u-t_{j}\right)-f\left(\widehat{B}u\right)\right|\leq\frac{2\widehat{B}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}.$

Taking $u=\widehat{Q}(x)/\widehat{B}\in[-1,1]$ with $x\in\Omega$ yields

$\sup_{x\in\Omega}\left|\frac{N}{\widehat{B}}\sum_{j=1}^{2N+3}\widehat{c}_{j}\sigma\left(\widehat{Q}(x)-\widehat{B}t_{j}\right)-f\left(\widehat{Q}(x)\right)\right|\leq\frac{2\widehat{B}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}.$

Combining this estimate with (4.25) and the Lipschitz-$\alpha$ property of $f$
gives

$\displaystyle\sup_{x\in\Omega}\left|\sum_{j=1}^{2N+3}\frac{N}{\widehat{B}}\widehat{c}_{j}\left(h^{(J_{2}+1)}(x)\right)_{j}-f\left(|x|^{2}\right)\right|$
$\displaystyle\leq$
$\displaystyle\frac{2\widehat{B}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}+\sup_{x\in\Omega}\left|f\left(\widehat{Q}(x)\right)-f\left(|x|^{2}\right)\right|$
$\displaystyle\leq$
$\displaystyle\frac{2\widehat{B}^{\alpha}|f|_{C^{0,\alpha}}}{N^{\alpha}}+|f|_{C^{0,\alpha}}\left(\frac{4d}{N}\right)^{\alpha}.$

This together with
$\left\|\frac{N}{\widehat{B}}\widehat{c}\right\|_{\infty}\leq\frac{4N\|f\|_{\infty}}{1+4d}$
verifies the desired bound (2.3).

The free parameters in the last layer are only from
$\left\\{f\left(\widehat{B}t_{k}\right)\right\\}_{k=2}^{2N_{2}+2}$ with the
total number

${\mathcal{N}}_{2}=2N+1.$

Thus the total number of free parameters of our network is

${\mathcal{N}}={\mathcal{N}}_{1}+{\mathcal{N}}_{2}\leq
d+7(2N+3)d+s+2N+1\leq(14d+2)N+22d+s+1.$

The bound for ${\mathcal{N}}$ when
$N=\left\lceil\left(1+4d\right)\left(3|f|_{C^{0,\alpha}}\right)^{\frac{1}{\alpha}}\epsilon^{-\frac{1}{\alpha}}\right\rceil$
is seen easily. This completes the proof of Theorem 2. ∎

##  5 Deep Networks Approximate Much Faster

In this section we prove out third main result which demonstrates the super
efficiency of deep neural networks in approximating radial functions.

###### Proof of Theorem 3.

We introduce another hypothesis space spanned by ridge functions on
${\mathbb{B}}$ as

${\mathcal{R}}_{N,\infty}=\left\\{\sum_{k=1}^{N}r_{k}(\theta_{k}\cdot
x):|\theta_{k}|=1,r_{k}\in L_{\infty}[-1,1]\right\\}.$ (5.1)

Each function from the hypothesis space ${\mathcal{S}}_{N}$ can be expressed
as

$\sum_{k=1}^{N}c_{k}\sigma_{k}(a_{k}\cdot
x-b_{k})=\sum_{k=1}^{N}r_{k}(\theta_{k}\cdot x),$

where the univariate function $r_{k}$ on $[-1,1]$ are given by

$\left\\{\begin{array}[]{ll}r_{k}(u)=c_{k}\sigma_{k}(|a_{k}|u-b_{k}),\
\theta_{k}=\frac{1}{|a_{k}|}a_{k},&\hbox{if}\ |a_{k}|\not=0,\\\ r_{k}(u)\equiv
c_{k}\sigma_{k}(-b_{k}),\ \theta_{k}=(1,0,\ldots,0)^{T},&\hbox{if}\
|a_{k}|=0.\end{array}\right.$

Note that $r_{k}\in L_{\infty}[-1,1]$ for each $k$. Thus we find
${\mathcal{S}}_{N}\subseteq{\mathcal{R}}_{N,\infty}$ and

$\hbox{dist}\left({\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right),{\mathcal{S}}_{N}\right)\geq\hbox{dist}\left({\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right),{\mathcal{R}}_{N,\infty}\right).$

Now we apply [14, Corollary 3], with $p=q=\infty$, $r=1$ and functions
extended continuously from $\\{x\in\mathbb{R}^{d}:|x|<1\\}$ to ${\mathbb{B}}$
by the Lipschitz property, which asserts that when $d>1$,

$c^{\prime}_{d}N^{-\frac{1}{d-1}}\geq\hbox{dist}\left({\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right),{\mathcal{R}}_{N,\infty}\right)\geq
c_{d}N^{-\frac{1}{d-1}},\qquad\forall N\in\mathbb{N},$

where $c_{d},c^{\prime}_{d}$ are positive constants independent of
$N\in\mathbb{N}$. Then the first desired bound (2.8) follows.

On the other hand, for each function
$f(|\cdot|^{2})\in{\mathcal{B}}\left(C^{0,1}_{|\cdot|}\right)$ with a function
$f$ on $[0,1]$, we see that for $s\not=t\in[0,1]$,

$\displaystyle\left|f(s)-f(t)\right|=\left|f\left(|(\sqrt{s},0\ldots,0)|^{2}\right)-f\left(|(\sqrt{t},0\ldots,0)|^{2}\right)\right|$
$\displaystyle\quad\leq\|f(|\cdot|^{2})\|_{C^{0,1}({\mathbb{B}})}|(\sqrt{s},0\ldots,0)-(\sqrt{t},0\ldots,0)|\leq|\sqrt{s}-\sqrt{t}|\leq\sqrt{|s-t|}.$

It follows that $f\in C^{0,1/2}[0,1]$ and $|f|_{C^{0,1/2}}\leq 1$. Thus, by
Theorem 2 with $\alpha=\frac{1}{2}$, we have

$\inf_{g\in{\mathcal{H}}_{N}}\|f(|\cdot|^{2})-g\|_{L_{\infty}({\mathbb{B}})}\leq
3\sqrt{1+4d}N^{-\frac{1}{2}}.$

This implies the second desired bound (2.9) and proves the theorem. ∎

##  6 Generalization Analysis

In this section, we conduct generalization analysis of the deep learning
algorithm induced by our constructed deep neural network. To this end, we need
to analyse the approximation ability of the hypothesis space in the ERM
algorithm by showing that the filters, the full connection matrix, and biases
of the deep neural network can be bounded as required in the hypothesis space
and then to derive an estimation error bound by applying a covering number
argument.

###  6.1 Bounding the filters and connection matrix

To bound the filters of the convolutional layers and the full connection
matrix for the fully connected layer, we need the following simple consequence
of the classical Cauchy’ bound of polynomial roots in terms of coefficients
and Vieta’s formula of polynomial coefficients in terms of roots.

######  Lemma 7.

If $w=\\{w_{j}\\}_{j\in\mathbb{Z}}$ is a real sequence supported in
$\\{0,\ldots,K\\}$ with $w_{K}=1$, then all the complex roots of its symbol
$\widetilde{w}(z)=\sum_{j=0}^{K}w_{j}z^{j}$ are located in the disk of radius
$1+\max_{j=0,\ldots,K-1}|w_{j}|$, the Cauchy bound of $\widetilde{w}$.

If we factorize $\widetilde{w}$ into monic polynomials of degree at most $s$,
then all the coefficients of these factor polynomials are bounded by
$s^{\frac{s}{2}}\left(1+\max_{j=0,\ldots,K-1}|w_{j}|\right)^{s}\leq
s^{\frac{s}{2}}\left(1+\|w\|_{\infty}\right)^{s}$.

######  Lemma 8.

Let $2\leq s\leq d$, $q,N\in\mathbb{N}$, $Q$ be a polynomial on $\Omega$ of
degree at most $q$, $f\in C[-B_{Q},B_{Q}]$. Then for the deep neural network
constructed in Section 4, there exists a constant
$R=R_{q,d,s,Q,\|f\|_{\infty}}\geq|Q(0)|+2B_{Q}$ depending on
$q,d,s,Q,\|f\|_{\infty}$ such that

$\left\|w^{(j)}\right\|_{\infty}\leq R,\qquad j=1,\ldots,J_{2},$

and

$\left\|F^{[J_{2}+1]}\right\|_{\infty}\leq N^{2}R,\qquad\|c\|_{\infty}\leq
NR.$

###### Proof.

Since $|\xi_{n_{q}}|=1$, there exists some $\ell\in\\{1,\ldots,d\\}$ such that
$\left(\xi_{n_{q}}\right)_{\ell}\not=0$ and $\left(\xi_{n_{q}}\right)_{i}=0$
for any $i<\ell$. Then we see that the sequence $W$ constructed in the proof
of Lemma 3 is supported in $\\{0,\ldots,n_{q}d-\ell\\}$ with
$W_{n_{q}d-\ell}=\left(\xi_{n_{q}}\right)_{\ell}\not=0$. Set a sequence
$w=\frac{1}{\left(\xi_{n_{q}}\right)_{\ell}}W$. Then $w$ satisfies the
condition in Lemma 7 with $K=n_{q}d-\ell$. So by Lemma 7, all the complex
roots of $\widetilde{w}$ are located in the disk of radius
$1+\|w\|_{\infty}=1+\frac{1}{\left|\left(\xi_{n_{q}}\right)_{\ell}\right|}\max_{k=1,\ldots,n_{q}}\|\xi_{k}\|_{\infty}\leq
1+\frac{1}{\left|\left(\xi_{n_{q}}\right)_{\ell}\right|}$, and the filters
$\\{w^{(j)}\\}_{j=1}^{J_{1}}$ satisfying (4.5) and (4.6) constructed in Lemma
3 can be bounded as

$\left\|w^{(j)}\right\|_{\infty}\leq
s^{s/2}\left(1+\left|\left(\xi_{n_{q}}\right)_{\ell}\right|\right)\left(1+\frac{1}{\left|\left(\xi_{n_{q}}\right)_{\ell}\right|}\right)^{s},\qquad
j=1,\ldots,J_{1}.$

For the second layer of CNNs, we observe that the sequence $W^{[1]}$ satisfies
the condition in Lemma 7 with $K=(2N+3)d_{J_{1}}$ and
$\left\|W^{[1]}\right\|_{\infty}=1$. Then by Lemma 7, the filters
$\\{w^{(j)}\\}_{j=J_{1}+1}^{J_{2}}$ defined by (4.10) and (4.11) can be
bounded as

$\|w^{(j)}\|_{\infty}\leq s^{\frac{s}{2}}2^{s},\qquad j=J_{1}+1,\ldots,J_{2}.$

For the connection matrix $F^{[J_{2}+1]}$ of the fully connected layer defined
by (4.16) and (4.20), from the bound $\|v^{[\ell]}\|_{\infty}\leq 4$, we know
that the $\ell_{1}$-norm of each row of $F^{[J_{2}+1]}$ is bounded by
$4N(2N+3)\|\beta\|_{1}$. Hence $\left\|F^{[J_{2}+1]}\right\|_{\infty}\leq
4N(2N+3)\|\beta\|_{1}$.

The above estimates together with (4.22) verify the desired bounds with the
constant $R=R_{q,d,s,Q,\|f\|_{\infty}}$ depending on $q,d,s,Q,\|f\|_{\infty}$
given explicitly by

$R=\max\left\\{s^{s/2}\left(1+\left|\left(\xi_{n_{q}}\right)_{\ell}\right|\right)\left(1+\frac{1}{\left|\left(\xi_{n_{q}}\right)_{\ell}\right|}\right)^{s},s^{\frac{s}{2}}2^{s},20\|\beta\|_{1},\frac{4\|f\|_{\infty}}{\widehat{B}_{Q}},|Q(0)|+2B_{Q}\right\\}.$

This proves the lemma. ∎

###  6.2 Bounding the biases

Applying the bounds for the filters, we can bound the biases as follows.

######  Lemma 9.

In the setting of Lemma 8, for the deep neural network constructed in Section
4, with the constant $R=R_{q,d,s,Q,\|f\|_{\infty}}$ given in Lemma 8 there
holds

$\left\|b^{(j)}\right\|_{\infty}\leq\left(2(s+1)R\right)^{j},\qquad
j=1,\ldots,J_{2}+1.$

###### Proof.

The bias vectors $\\{b^{(j)}\\}_{j=1}^{J_{1}}$ of the first group of CNNs are
chosen in the proof of Lemma 3 as $b^{(1)}=-\|w^{(1)}\|_{1}{\bf 1}_{d_{1}}$
and $b^{(j)}=\left(\Pi_{p=1}^{j-1}\|w^{(p)}\|_{1}\right)T^{(j)}{\bf
1}_{d_{j-1}}-\left(\Pi_{p=1}^{j}\|w^{(p)}\|_{1}\right){\bf 1}_{d_{j-1}+s}$,
for $j=2,\ldots,J_{1}$. By the special structure of Toeplitz matrix of the
convolutional filters and Lemma 8, we find $\|b^{(j)}\|_{\infty}\leq
2\left((s+1)R\right)^{j}$ for $j=1,2,\ldots,J_{1}$.

The bias vectors $\\{b^{(j)}\\}_{j=J_{1}+1}^{J_{2}-1}$ of the second group of
CNNs are chosen in the proof of lemma 4 to be
$b^{(j)}=B\left(\Pi_{p=J_{1}+1}^{j-1}\|w^{(p)}\|_{1}\right)T^{(j)}{\bf
1}_{d_{j-1}}-B\left(\Pi_{p=J_{1}+1}^{j}\|w^{(p)}\|_{1}\right){\bf
1}_{d_{j-1}+s}$, where
$B=\Pi_{p=1}^{J_{1}}\|w^{(p)}\|_{1}\leq\left((s+1)R\right)^{J_{1}}$. Hence we
also have $\|b^{(j)}\|_{\infty}\leq 2\left((s+1)R\right)^{j}$ for
$j=J_{1}+1,\ldots,J_{2}-1$.

The bias vector in the $J_{2}$-th layer is given in the proof of Lemma 4 by

$\displaystyle\left(b^{(J_{2})}\right)_{i}$ $\displaystyle=$ $\displaystyle
B\left(\Pi_{p=J_{1}+1}^{J_{2}-1}\|w^{(p)}\|_{1}\right)\left(T^{(J_{2})}{\bf
1}_{d_{J_{2}-1}}\right)_{i}$
$\displaystyle+\left\\{\begin{array}[]{ll}t_{j},&\hbox{if}\
(j-2)d_{J_{1}}+1\leq i\leq(j-2)d_{J_{1}}+n_{q},1\leq j\leq 2N_{1}+3,\\\
B,&\hbox{otherwise.}\end{array}\right.$

As $|t_{j}|\leq 2$, we also have $\|b^{(j)}\|_{\infty}\leq
2\left((s+1)R\right)^{j}$ for $j=J_{2}$.

Finally, the bias vector in the $J_{2}+1$-th layer is given in Lemma 6 as
$b^{(J_{2}+1)}=-Q(0){\bf
1}_{2N_{2}+3}+B_{Q}\left[t_{1},\dots,t_{2N_{2}+3}\right]^{T}$. Its entries can
be bounded by $|Q(0)|+2B_{Q}$, a constant depending only on $Q$. That is,
$\|b^{(j)}\|_{\infty}\leq|Q(0)|+2B_{Q}$ for $j=J_{2}+1$. But
$|Q(0)|+2B_{Q}\leq R$. Then the desired bounds holds. The proof of the lemma
is complete. ∎

###  6.3 Bounding covering numbers

Recall that the covering number $\mathcal{N}\left(\eta,{\mathcal{H}}\right)$
of a compact subset ${\mathcal{H}}$ of $C(\Omega)$ is defined for $\eta>0$ to
be the smallest integer $\ell$ such that ${\mathcal{H}}$ is contained in the
union of $\ell$ balls in $C(\Omega)$ of radius $\eta$. Covering numbers can be
used to measure the capacity of a hypothesis space and hence the learning
performance of the induced ERM algorithms. For our generalization analysis, we
need to estimate the covering numbers of the bounded hypothesis space
${\mathcal{H}}_{R,N}$.

######  Lemma 10.

For $R\geq 2,N\in\mathbb{N}$, with two constants $A_{1},A_{2}$ depending only
on $d,q,s$, there holds

$\log\mathcal{N}\left(\eta,{\mathcal{H}}_{R,N}\right)\leq
A_{1}N\log\left(2/\eta\right)+A_{2}N^{2}\log\left(2(s+1)R\right),\qquad\forall\
0<\eta\leq 1.$

###### Proof.

For a vector $h=(h_{i}(x))_{i=1}^{K}$ of functions on $\Omega$, denote
$\|h\|_{\infty}=\max_{i=1,\ldots,K}\|h_{i}\|_{\infty}$.

If ${\bf w},{\bf b},F^{[J_{2}+1]}$ and $c$ satisfy the restrictions in (2.10),
then from the iteration relation (1.3), the linear increment of ReLU
$\sigma(u)\leq|u|$, and the special form of the rows of the Toeplitz type
matrix $T^{(j)}$, we have

$\|h^{(j)}(x)\|_{\infty}\leq(s+1)R\|h^{(j-1)}(x)\|_{\infty}+\left(2(s+1)R\right)^{j},\qquad
j=1,\ldots,J_{2},$

which together with the input bound $\|h^{(0)}\|_{\infty}\leq 1$ implies by
induction

$\|h^{(j)}(x)\|_{\infty}\leq 2\left(2(s+1)R\right)^{j},\qquad
j=1,\ldots,J_{2},$ (6.2)

and

$\|h^{(J_{2}+1)}(x)\|_{\infty}\leq N^{2}\left(2(s+1)R\right)^{J_{2}+1}.$ (6.3)

If $\widehat{c}\cdot\widehat{h}^{(J_{2}+1)}(x)$ is another function from the
hypothesis space ${\mathcal{H}}_{R,N}$ induced by $\widehat{{\bf
w}},\widehat{{\bf b}},\widehat{F}^{[J_{2}+1]}$, $\widehat{c}$ satisfying the
restrictions in (2.10) and

$\|w^{(j)}-\widehat{w}^{(j)}\|_{\infty}\leq\eta,\
\|b^{(j)}-\widehat{b}^{(j)}\|_{\infty}\leq\eta,\
\|c-\widehat{c}\|_{\infty}\leq\eta,\
\|F^{[J_{2}+1]}-\widehat{F}^{[J_{2}+1]}\|_{\infty}\leq\eta,$

then for $j=1,\ldots,J_{2}$, by the Lipschitz property of ReLU, we have

$\displaystyle\|h^{(j)}-\widehat{h}^{(j)}\|_{\infty}=\left\|\sigma\left(T^{w^{(j)}}h^{(j-1)}(x)-b^{(j)}\right)-\sigma\left(T^{\widehat{w}^{(j)}}\widehat{h}^{(j-1)}(x)-\widehat{b}^{(j)}\right)\right\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\left\|\left(T^{w^{(j)}}h^{(j-1)}(x)-b^{(j)}\right)-\left(T^{\widehat{w}^{(j)}}\widehat{h}^{(j-1)}(x)-\widehat{b}^{(j)}\right)\right\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\left\|T^{w^{(j)}}\left(h^{(j-1)}(x)-\widehat{h}^{(j-1)}(x)\right)\right\|_{\infty}+\left\|\left(T^{w^{(j)}}-T^{\widehat{w}^{(j)}}\right)\widehat{h}^{(j-1)}(x)\right\|_{\infty}+\eta.$

Combining this with (6.2) and the special form of the rows of the Toeplitz
type matrices $T^{w^{(j)}}$ and
$T^{w^{(j)}}-T^{\widehat{w}^{(j)}}=T^{w^{(j)}-\widehat{w}^{(j)}}$, we find

$\|h^{(j)}-\widehat{h}^{(j)}\|_{\infty}\leq(s+1)R\left\|h^{(j-1)}-\widehat{h}^{(j-1)}\right\|_{\infty}+(s+1)\eta
2\left(2(s+1)R\right)^{j-1}+\eta.$

This together with the fact $R\geq 2$ and $h^{(0)}-\widehat{h}^{(0)}=0$
implies by induction

$\|h^{(j)}-\widehat{h}^{(j)}\|_{\infty}\leq
2\left(2(s+1)R\right)^{j}\eta,\qquad j=1,\ldots,J_{2}.$

In the same way, for the fully connected layer, we know that
$\|h^{(J_{2}+1)}-\widehat{h}^{(J_{2}+1)}\|_{\infty}$ is bounded by

$\displaystyle\left\|\left(F^{[J_{2}+1]}h^{(J_{2})}(x)-b^{(J_{2}+1)}\right)-\left(\widehat{F}^{[J_{2}+1]}\widehat{h}^{(J_{2})}(x)-\widehat{b}^{(J_{2}+1)}\right)\right\|_{\infty}$
$\displaystyle\leq$
$\displaystyle\left\|F^{[J_{2}+1]}\left(h^{(J_{2})}(x)-\widehat{h}^{(J_{2})}(x)\right)\right\|_{\infty}+\left\|\left(F^{[J_{2}+1]}-\widehat{F}^{[J_{2}+1]}\right)\widehat{h}^{(J_{2})}(x)\right\|_{\infty}+\eta$
$\displaystyle\leq$ $\displaystyle
N^{2}R2\left(2(s+1)R\right)^{J_{2}}\eta+\eta
2\left(2(s+1)R\right)^{J_{2}}+\eta\leq
N^{2}\left(2(s+1)R\right)^{J_{2}+1}\eta.$

Combining this with (6.3) yields

$\displaystyle\|c\cdot
h^{(J_{2}+1)}-\widehat{c}\cdot\widehat{h}^{(J_{2}+1)}\|_{\infty}\leq\left\|c\cdot\left(h^{(J_{2}+1)}-\widehat{h}^{(J_{2}+1)}\right)\right\|_{\infty}+\left\|\left(c-\widehat{c}\right)\cdot\widehat{h}^{(J_{2}+1)}\right\|_{\infty}$
$\displaystyle\leq$
$\displaystyle(2N+3)NR\left\|h^{(J_{2}+1)}-\widehat{h}^{(J_{2}+1)}\right\|_{\infty}+(2N+3)\eta\left\|\widehat{h}^{(J_{2}+1)}\right\|_{\infty}$
$\displaystyle\leq$
$\displaystyle(2N+3)NRN^{2}\left(2(s+1)R\right)^{J_{2}+1}\eta+(2N+3)\eta
N^{2}\left(2(s+1)R\right)^{J_{2}+1}$ $\displaystyle\leq$ $\displaystyle
N^{2}(2N+3)(N+1)R\left(2(s+1)R\right)^{J_{2}+1}\eta.$

Recall that $J_{1}\leq\frac{n_{q}d-2}{s-1}+1\leq n_{q}d-1$ and the bound
$d_{J_{1}}\leq 1+\frac{s}{d}J_{1}$ in (4.24). Then

$d_{J_{1}}\leq 1+\frac{s}{d}\left(\frac{n_{q}d-2}{s-1}+1\right)\leq
2+\frac{s}{s-1}\frac{n_{q}d-2}{d}<2+2n_{q}.$

Hence $d_{J_{1}}\leq 2n_{q}+1$. This together with the definition of $J_{2}$
yields

$J_{2}<J_{1}+\left(\frac{(2N+3)d_{J_{1}}}{s-1}+1\right)\leq
n_{q}d+(2N+3)(1+2n_{q})$

and thereby

$J_{2}\leq\left(4+(10+d)n_{q}\right)N.$

Also,

$d_{J_{2}}\leq
d_{J_{1}}+s\left(\frac{(2N+3)d_{J_{1}}+s-2}{s-1}\right)<(4N+7)d_{J_{1}}+s-1$

which gives

$d_{J_{2}}\leq(2n_{q}+1)(s+9)N.$

Therefore,

$\|c\cdot h^{(J_{2}+1)}-\widehat{c}\cdot\widehat{h}^{(J_{2}+1)}\|_{\infty}\leq
10RN^{4}\left(2(s+1)R\right)^{\left(5+(10+d)n_{q}\right)N}\eta=:\widehat{\eta}.$

Thus, by taking an $\eta$-net for each of $w^{(j)},b^{(j)},c,F^{[J_{2}+1]}$,
we know that the covering number of the hypothesis space ${\mathcal{H}}_{R,N}$
with the radius $\widehat{\eta}\in(0,1]$ can be bounded as

$\displaystyle\mathcal{N}\left(\widehat{\eta},{\mathcal{H}}_{R,N}\right)\leq\left\lceil
2R/\eta\right\rceil^{(s+1)J_{2}}\Pi_{j=1}^{J_{2}-1}\left\lceil
2(2(s+1)R)^{j}/\eta\right\rceil^{2s+1}\left\lceil
2(2(s+1)R)^{J_{2}}/\eta\right\rceil^{d_{J_{2}}}$
$\displaystyle\qquad\left\lceil
2(2(s+1)R)^{J_{2}+1}/\eta\right\rceil^{2N+3}\left\lceil
2NR/\eta\right\rceil^{2N+3}\left\lceil 2N^{2}R/\eta\right\rceil^{d_{J_{2}}}$
$\displaystyle\leq\left(3R/\eta\right)^{(3s+2)J_{2}+4N+6+2d_{J_{2}}}N^{2N+3+2d_{J_{2}}}\left(2(s+1)R\right)^{(2s+1)\frac{J_{2}(J_{2}-1)}{2}+J_{2}d_{J_{2}}+(J_{2}+1)(2N+3)}.$

It follows that

$\mathcal{N}\left(\widehat{\eta},{\mathcal{H}}_{R,N}\right)\leq\left(30R^{2}/\widehat{\eta}\right)^{A_{1}N}N^{6A_{1}N}\left(2(s+1)R\right)^{A^{\prime}_{2}N^{2}},$

where

$A_{1}=(3s+2)\left(4+(10+d)n_{q}\right)+10+2(2n_{q}+1)(s+9),\quad$

and

$A^{\prime}_{2}=\left(5+(10+d)n_{q}\right)A_{1}+(s+9)\left(4+(10+d)n_{q}\right)\left(5+(12+d)n_{q}\right).$

But $15R^{2}\leq\left(2(s+1)R\right)^{2}$, $\log N\leq N$, and
$A^{\prime}_{2}\geq 8A_{1}$. So we have

$\log\mathcal{N}\left(\widehat{\eta},{\mathcal{H}}_{R,N}\right)\leq
A_{1}N\log\left(2/\widehat{\eta}\right)+2A^{\prime}_{2}N^{2}\log\left(2(s+1)R\right).$

This verifies the desired bound for the covering numbers with
$A_{2}=2A^{\prime}_{2}$ and completes the proof of the lemma. ∎

###  6.4 Deriving learning rates of the ERM algorithm

The proof of Theorem 4 follows from our approximation error estimate in
Theorem 1 and the following general inequality for the ERM algorithm

$f_{D,\mathcal{H}}=\arg\min_{f\in\mathcal{H}}\frac{1}{m}\sum_{i=1}^{m}(f(x_{i})-y_{i})^{2}$

over a compact subset $\mathcal{H}$ of $C(\mathcal{X})$, which can be verified
with the same proof as that of [4, Theorem 2].

######  Lemma 11.

Suppose there exist constants $n^{\prime},\mathcal{U},n^{\prime\prime}>0$ such
that

$\log\mathcal{N}(\epsilon,\mathcal{H})\leq
n^{\prime}\log\frac{\mathcal{U}}{\epsilon}+n^{\prime\prime},\qquad\forall\epsilon>0.$
(6.4)

Then for any $h^{*}\in\mathcal{H}$ and $\epsilon>0$,

$\displaystyle\hbox{Prob}\left\\{\|\pi_{M}f_{D,\mathcal{H}}-f_{\rho}\|_{\rho}^{2}>\epsilon+2\|h^{*}-f_{\rho}\|_{\rho}^{2}\right\\}\leq\exp{\left\\{n^{\prime}\log\frac{16\mathcal{U}M}{\epsilon}+n^{\prime\prime}-\frac{3m\epsilon}{512M^{2}}\right\\}}$
(6.5)
$\displaystyle+\exp{\left\\{\frac{-3m\epsilon^{2}}{16(3M+\|h^{*}\|_{L_{\infty}(\mathcal{X})})^{2}(6\|h^{*}-f_{\rho}\|_{\rho}^{2}+\epsilon)}\right\\}}$

We are in a position to prove our last main result.

###### Proof of Theorem 4.

Let $R\geq R_{q,d,s,Q,\|f\|_{\infty}}$ with the constant
$R_{q,d,s,Q,\|f\|_{\infty}}$ given in Lemma 8. By Lemmas 8 and 9, we know from
Theorem 1 that there exists some $h\in{\mathcal{H}}_{R,N}$ and
$C^{*}_{1}:=C_{Q,\alpha}|f_{\rho}|_{C^{0,\alpha}}$ such that

$\|h-f_{\rho}\|_{\rho}\leq\|h-f_{\rho}\|_{C(\Omega)}\leq
C_{1}^{*}N^{-\alpha}.$

Since $|y|\leq M$ almost surely, $\|f_{\rho}\|_{C(\Omega)}\leq M$, then

$\|h\|_{C(\Omega)}\leq M+C_{1}^{*}.$

According to Lemma 10, we know that (6.4) holds true for
$\mathcal{H}=\mathcal{H}_{R,N}$ with $n^{\prime}=A_{1}N$, $\mathcal{U}=2$, and
$n^{\prime\prime}=A_{3}N^{2}$ where we denote
$A_{3}=A_{2}\log\left(2(s+1)R\right)$. Applying Lemma 11 to this hypothesis
space and $h^{*}=h$, we see that for any $\epsilon>0$,

$\displaystyle\hbox{Prob}\left\\{\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}>\epsilon+2\|h-f_{\rho}\|_{\rho}^{2}\right\\}$
$\displaystyle\leq\exp{\left\\{A_{1}N\log\frac{32M}{\epsilon}+A_{3}N^{2}-\frac{3m\epsilon}{512M^{2}}\right\\}}+\exp{\left\\{\frac{-3m\epsilon^{2}}{16(4M+C_{1}^{*})^{2}(6(C_{1}^{*})^{2}N^{-2\alpha}+\epsilon)}\right\\}}.$

If we restrict

$\epsilon\geq 6{C_{1}^{*}}^{2}N^{-2\alpha}$ (6.6)

and apply $\log N\leq N$, then we have

$\hbox{Prob}\left\\{\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}>2\epsilon\right\\}\leq\exp{\left\\{A_{4}N^{2}-\frac{3m\epsilon}{512M^{2}}\right\\}}+\exp{\left\\{\frac{-3m\epsilon}{32(4M+C_{1}^{*})^{2}}\right\\}},$

where

$A_{4}=A_{1}\log\frac{32M}{6{C_{1}^{*}}^{2}}+2A_{1}+A_{3}.$

If we set a further restriction condition on $\epsilon$ as

$\epsilon\geq\frac{1024M^{2}A_{4}N^{2}}{3m},$ (6.7)

then we have

$\hbox{Prob}\left\\{\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}>2\epsilon\right\\}\leq\exp{\left\\{-\frac{3m\epsilon}{1024M^{2}}\right\\}}+\exp{\left\\{\frac{-3m\epsilon}{32(4M+C_{1}^{*})^{2}}\right\\}}.$

By setting $t=2\epsilon$ and

$A_{5}:=\max\left\\{12{C_{1}^{*}}^{2},683M^{2}A_{4},\
22(4M+C_{1}^{*})^{2}\right\\},$

this yields

$\hbox{Prob}\left\\{\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}>t\right\\}\leq
2\exp{\left\\{-\frac{mt}{A_{5}}\right\\}},\qquad\forall t\geq
A_{5}\max\left\\{N^{-2\alpha},\ \frac{N^{2}}{m}\right\\}.$ (6.8)

It follows that for any $0<\delta<1$, with confidence at least $1-\delta$,
there holds

$\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}\leq A_{5}\max\left\\{N^{-2\alpha},\
\frac{N^{2}}{m},\ \frac{\log(2/\delta)}{m}\right\\}.$

If we apply the formula for the mean of the non-negative random variables
$\xi=\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}$:

$\mathbb{E}[\xi]=\int_{0}^{\infty}\hbox{Prob}\left[\xi>t\right]dt,$

we see from (6.8) that with $\Delta:=A_{5}\max\left\\{N^{-2\alpha},\
\frac{N^{2}}{m}\right\\}$, there holds

$\displaystyle\mathbb{E}\left[\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}\right]$
$\displaystyle=\left(\int_{0}^{\Delta}+\int_{\Delta}^{\infty}\right)\hbox{Prob}\left\\{\|\pi_{M}f_{D,R,N}-f_{\rho}\|_{\rho}^{2}>t\right\\}dt$
$\displaystyle\leq\Delta+\int_{\Delta}^{\infty}2\exp{\left\\{-\frac{mt}{A_{5}}\right\\}}dt\leq\Delta+\frac{2A_{5}}{m}\leq
3\Delta.$

Observe that

$3A_{5}\leq C_{Q,s,d,\alpha,M,|f|_{C^{0,\alpha}}}\log\left(2(s+1)R\right),$

where $C_{Q,s,d,\alpha,M,|f|_{C^{0,\alpha}}}$ is a constant independent of
$m,N$ or $R$ given by

$3\max\left\\{12{C_{1}^{*}}^{2},683M^{2}\left(A_{1}\log\frac{32M}{6{C_{1}^{*}}^{2}}+2A_{1}+A_{2}\right),\
22(4M+C_{1}^{*})^{2}\right\\}.$

Then the desired error bound follows. The proof of Theorem 4 is complete. ∎

## Acknowledgments

We thank the anonymous referees for their constructive suggestions. The last
author is supported partially by the Research Grants Council of Hong Kong
[Project # CityU 11307319], Hong Kong Institute for Data Science, InnoHK, and
National Natural Science Foundation of China [Project No. 12061160462]. The
paper was revised when the last author visited SAMSI/Duke during his
sabbatical leave. He would like to express his gratitude to their hospitality
and financial support.

## References

  * [1] A. R. Barron, Universal approximation bounds for superpositions of a sigmoidal function, IEEE Trans. Inform. Theory 39 (1993), 930–945.
  * [2] H. Bölcskei, P. Grohs, G. Kutyniok, and P. Petersen, Optimal approximation with sparsely connected deep neural networks, SIAM Journal on Mathematics of Data Science 1 (2019), 8–45.
  * [3] C. K. Chui, S. B. Lin, D. X. Zhou, Deep neural networks for rotation-invariance approximation and learning, Anal. Appl. 17 (2019), 737–772.
  * [4] C. K. Chui, S. B. Lin, D. X. Zhou, Deep net tree structure for balance of capacity and approximation ability, Front. Appl. Math. Stat., 2019, https://doi.org/10.3389/fams.2019.00046.
  * [5] F. Cucker and D. X. Zhou. Learning Theory: An Approximation Theory Viewpoint, Cambridge University Press, Cambridge, MA, 2007.
  * [6] J. Fan, T. Hu, Q. Wu and D. X. Zhou, Consistency analysis of an empirical minimum error entropy algorithm, Appl. Comput. Harmonic Anal. 41 (2016), 164–189.
  * [7] Z. Y. Fang, H. Feng, S. Huang, and D. X. Zhou, Theory of deep convolutional neural networks II: Spherical analysis, Neural Networks 131 (2020), 154–162.
  * [8] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning, MIT Press, 2016.
  * [9] Z. C. Guo, D. H. Xiang, X. Guo, and D. X. Zhou, Thresholded spectral algorithms for sparse approximations, Anal. Appl. 15 (2017), 433–455.
  * [10] G. E. Hinton, S. Osindero, Y. W. Teh, A fast learning algorithm for deep belief nets, Neural Comput. 18 (2006), 1527–1554.
  * [11] M. Imaizumi and K. Fukumizu, Deep neural networks learn non-smooth functions effectively, in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
  * [12] J. Klusowski and A. Barron, Approximation by combinations of ReLU and squared ReLU ridge functions with $\ell^{1}$ and $\ell^{0}$ controls, IEEE Transactions on Information Theory 64 (2018), 7649–7656.
  * [13] M. Kohler and A. Krzyzak, Nonparametric regression based on hierarchical interaction models, IEEE Trans. Inform. Theory 63 (2017), 1620–1630.
  * [14] V. N. Konovalov, D. Leviatan, and V. E. Maiorov, Approximation of Sobolev classes by polynomials and ridge functions, J. Approx. Theory 159 (2009), 97–108.
  * [15] A. Krizhevsky, I. Sutskever, and G. Hinton G, Imagenet classification with deep convolutional neural networks, NIPS (2012): 1097–1105.
  * [16] Y. V. Lin and A. Pinkus, Fundamentality of ridge functions, J. Approx. Theory 75 (1993), 295–311.
  * [17] S. B. Lin and D. X. Zhou, Distributed kernel gradient descent algorithms, Constr. Approx. 47 (2018), 249–276.
  * [18] V. E. Maiorov, On best approximation by ridge functions, J. Approx. Theory 99 (1999), 68–94.
  * [19] S. Mallat, Understanding deep convolutional networks, Phil. Trans. Royal Soc. A 374:20150203.
  * [20] B. McCane and L. Szymanski, Efficiency of deep networks for radially symmetric functions, Neurocomputing 313 (2018), 119–124.
  * [21] H. N. Mhaskar, Approximation properties of a multilayered feedforward artificial neural network, Adv. Comput. Math. 1 (1993), 61-80.
  * [22] H. N. Mhaskar, T. Poggio, Deep vs. shallow networks: An approximation theory perspective, Anal. Appl., 2016 (14), 829-848.
  * [23] R. Nakada and M. Imaizumi, Adaptive approximation and estimation of deep neural network to intrinsic dimensionality, arXiv preprint arXiv: 1907.02177, 2019.
  * [24] K. Oono and T. Suzuki, Approximation and non-parametric estimation of ResNet-type convolutional neural networks, in Proceedings of the 36th International Conference on Machine Learning (PMLR) 97:4922-4931, 2019.
  * [25] P. Petersen and V. Voigtlaender, Optimal approximation of piecewise smooth functions using deep ReLU neural networks, Neural Networks 108 (2018), 296–330.
  * [26] P. Petersen and F. Voigtlaender, Equivalence of approximation by convolutional neural networks and fully-connected networks, Proceedings of the American Mathematical Society 148 (2020), 1567-1581.
  * [27] T. Poggio, A. Banburski, and Q. Liao, Theoretical issues in deep networks, PNAS 117 (2020), 30039-30045.
  * [28] I. Safran and O. Shamir, Depth-width tradeoffs in approximating natural functions withneural networks, in International Conference on Machine Learning 2017, 2979-2987.
  * [29] J. Schmidt-Hieber, Nonparametric regression using deep neural networks with ReLU activation function, Ann. Stat. 48 (2020), 1875-1897.
  * [30] U. Shaham, A. Cloninger, and R. Coifman, Provable approximation properties for deep neural networks, Appl. Comput. Harmonic Anal. 44 (2018), 537–557.
  * [31] S. Sonoda and N. Murata, Neural network with unbounded activation functions is universal approximator, Applied and Computational Harmonic Analysis, 43 (2017), 233-268.
  * [32] T. Suzuki, Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality, in Proceedings of the International Conference on Learning Representations (ICLR), 2019.
  * [33] M. Telgarsky, Benefits of depth in neural networks, COLT, 2016.
  * [34] D. Wang and M. Li, Stochastic configuration networks: Fundamentals and algorithms, IEEE Transactions on Cybernetics 47 (2017), 3466-3479.
  * [35] D. Yarotsky, Error bounds for approximations with deep ReLU networks, Neural Networks 94 (2017), 103–114.
  * [36] D. X. Zhou, Deep distributed convolutional neural networks: universality, Anal. Appl. 16 (2018), 895–919.
  * [37] D. X. Zhou, Universality of deep convolutional neural networks, Appl. Comput. Harmonic Anal. 48 (2020), 787-794.
  * [38] D. X. Zhou, Theory of deep convolutional neural networks: Downsampling, Neural Networks 124 (2020), 319-327.
  * [39] T. Y. Zhou and D. X. Zhou, Theory of deep CNNs induced by 2D convolutions, preprint, 2020.