# Sampling Complexity of Deep Approximation Spaces

Ahmed Abdeljawad11footnotemark: 1 and Philipp Grohs
<EMAIL_ADDRESS><EMAIL_ADDRESS>Johann Radon Institute
for Computational and Applied Mathematics (RICAM), Austrian Academy of
Sciences, Altenbergerstr. 69, 4040 Linz, AustriaFaculty of Mathematics,
University of Vienna, Oskar-Morgenstern-Platz 1, A-1090 Vienna,
AustriaResearch Platform Data Science @ Uni Vienna, Währinger Straße 29/S6,
A-1090 Vienna, Austria

###### Abstract

While it is well-known that neural networks enjoy excellent approximation
capabilities, it remains a big challenge to compute such approximations from
point samples. Based on tools from Information-based complexity, recent work
by Grohs and Voigtlaender [Journal of the FoCM (2023)] developed a rigorous
framework for assessing this so-called ”theory-to-practice gap”. More
precisely, in that work it is shown that there exist functions that can be
approximated by neural networks with ReLU activation function at an arbitrary
rate while requiring an exponentially growing (in the input dimension) number
of samples for their numerical computation. The present study extends these
findings by showing analogous results for the ReQU activation function.

##  1 Introduction

Deep learning has made remarkable impacts in a wide range of tasks such as
speech recognition, computer vision, natural language processing and many
others. A theoretical understanding of the reason behind the empirical success
of deep neural networks is still missing. This includes the question of
_expressivity_ , which has been studied and used since 1989’s, dating back to
the foundational works of Cybenko [12], Hornik, Stinchcombe and White [24] and
Hornic [23].

Recently, several researchers are focusing on the theoretical foundation of
neural networks from a mathematical point of view. Indeed, many papers treat
the role of depth, width, activation functions and architecture in
approximating a given function e.g., [1, 2, 3, 4, 5, 6, 9, 13, 15, 17, 18, 19,
21, 25, 26]. More recent works focus predominantly on the number of samples
necessary to reach certain accuracy while approximating a given function. Some
examples —without any claim of completeness— are [7], in which the minimal
number of training samples when training an algorithm (to guarantee a given
uniform accuracy when approximating functions with ReLU neural networks)
scales exponentially both in the depth and the input dimension of the network
architecture. Or [20] which considers the sampling complexity problem when
approximating or integrating functions that can be well approximated by ReLU
neural networks, where authors used different norms when they measured
accuracy. Following this line of work, we focus on the impact of the chosen
activation function on the problem of sample complexity where the accuracy is
measured with respect to the uniform norm.

Determining the sample complexity for an algorithm $\mathcal{A}$ in order to
achieve an optimal accuracy of $\epsilon$ while approximating a given function
$u$ with deep neural networks depends on several factors. For instance, the
space where the function $u$ belongs, the norm where the accuracy is measured
and the characteristics of the algorithm $\mathcal{A}$. Here the algorithm is
an element of so-called _neural network approximation spaces_
$A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}([0,1]^{d})$ which
classifies functions depending on the decay of the approximation error by
neural networks with respect to the number of non-zero weights.

Basically, a function $u$ belongs to the unit ball of
$A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}([0,1]^{d})$,
denoted by
$U^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}([0,1]^{d})$, if
for any $n\in\mathbb{N}$ there exists a ReQU neural network with at most $n$
nonzero weights of magnitude at most $\boldsymbol{c}(n)$ and at most
$\boldsymbol{\ell}(n)$ layers approximating $u$ with accuracy less than
$n^{-\alpha}$ in the $L^{p}([0,1]^{d})$ norm, see Section 2.2 for more
details. Roughly speaking, a function $u$ belongs to
$A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}([0,1]^{d})$ (for
large $\alpha$) means that $u$ can be well approximated by ReQU neural
networks. Neural networks approximation spaces were first introduced in [16]
and extended by Grohs and Voightlaender in [20] to more general settings
taking into account the magnitude of the network weights and the maximal depth
of the network.

In practice, deep neural networks use more parameters than samples while
training, and therefore have the capacity to overfit to the training set.
Usually one needs regularization during the training process, or
theoretically, more information about the characteristics of function that the
network is approximating. The latter can be encoded in the _target class_
$U\subset C([0,1]^{d})$ which contains the ground truth $u$. In the current
paper, we are interested in the complexity of approximating a given solution
mapping $S:U\rightarrow Y$, such that $U\subset C([0,1]^{d})$ and $Y$ is a
Banach space, that can be achieved by any algorithm using only $m$ samples.
Formally, an algorithm using $m$ samples can be described by a set of samples
given by $X=(X_{1},\dots,X_{m})$ such that $X_{i}\in[0,1]^{d}$ for any
$i\in\\{1,\dots,m\\}$ and a map $Q:\mathbb{R}^{m}\rightarrow Y$ such that

$A(u)=Q(u(X_{1}),\dots,u(X_{m})),\text{ for any }u\in U.$

The set of all such algorithms is denoted by $Alg_{m}(U,Y)$. Furthermore, the
optimal order for approximating the mapping $S:U\rightarrow Y$ using point
samples can be determined as follows:

$err(U,S):=\sup\left\\{\beta\geq 0:\exists C>0\;\forall
m\in\mathbb{N}:\inf_{A\in\operatorname{Alg}_{m}(U,Y)}\sup_{u\in
U}\|A(u)-S(u)\|_{Y}\leq C\cdot m^{-\beta}\right\\}.$

More details about the classes of algorithms that we consider in this paper
can be found in Section 2.3 below. The Banach space $Y$ gives information
about where one would like to measure the error, in our analysis we select the
uniform norm, that is, $Y:=L^{\infty}([0,1]^{d})$. The study of the
generalization error, that is, $Y:=L^{2}([0,1]^{d})$ is an interesting
question for future work. The choice of the activation function in the network
is very critical. Compared to the main theorems in [20, Section 4, Section 5],
our choice of ReQU as an activation function has a similar impact on the
sampling complexity. We see these observations in the following simplified
version of our main results in Theorem 4.2 and Theorem 5.1.

######  Theorem 1.1.

Let $\boldsymbol{c}:\mathbb{N}\rightarrow\mathbb{N}\cup\\{\infty\\}$ be of the
form $\boldsymbol{c}(n)\asymp n^{\theta}\cdot\left(\log(2n)\right)^{\kappa}$
for certain $\theta\geq 0$ and $\kappa\in\mathbb{R}$, and let
$\boldsymbol{\ell}:\mathbb{N}\rightarrow\mathbb{N}_{\geq 5}\cup\\{\infty\\}$
such that
$\boldsymbol{\ell}^{\ast}:=\sup_{n\in\mathbb{N}}\boldsymbol{\ell}(n)<\infty$.
Then, we get

$\frac{1}{d}\cdot\frac{\alpha}{\alpha+(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2)}\leq
err(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty})\leq\frac{64}{d}\cdot\frac{\alpha}{8\alpha+(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2)}.$

We expect that (a qualitatively similar version of) our result holds for
neural networks activated by Rectified Power Unit (RePU)
$x\mapsto\max(0,x)^{p}$, for any $p\in\mathbb{N}_{\geq 2}$, since, for any
integer $p\geq 2$ $\max(0,x)^{p}$ can be exactly represented with a certain
ReQU neural network. The sampling complexity of learning ReLU neural networks
has recently been studied in [14, 16, 20, 31]. In our paper we consider the
ReQU activation function, thereby going a first step towards considering
general activation functions.

###  1.1 Notation

For $n\in\mathbb{N}$, we write $\underline{n}:=\\{1,2,\dots,n\\}$. For any
finite set $I\neq\varnothing$ and any sequence $(a_{i})_{i\in
I}\subset\mathbb{R}$, we define
$\mathop{\mathchoice{{\vphantom{\leavevmode\hbox{$\displaystyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\displaystyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\textstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\textstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=8.00009pt}\cr$\scriptstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptscriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=6.00006pt}\cr$\scriptscriptstyle\sum$\cr}}}}\displaylimits_{i\in
I}a_{i}:=\frac{1}{|I|}\sum_{i\in I}a_{i}$. The expectation of a random
variable $X$ will be denoted by $\mathbb{E}[X]$. For a subset
$M\subset\mathbb{R}^{d}$, we write $\overline{M}$ for the closure of $M$ and
$M^{\circ}$ for the interior of $M$.

###  1.2 Organization of the Paper

The organization of this paper is as follows. In Section 2, we give a
mathematical definition of the architecture and the realization of ReQU neural
networks. Furthermore, we define notions of neural networks approximation
space with ReQU activation function. We recall the deterministic and Monte
Carlo optimal orders. In Section 3 we show that the unit ball of the ReQU
neural networks approximation space contains a large family of “hat functions”
constructed by the use of ReQU activation function. Our main results can be
found in Sections 5 and 4 where we develop error bounds and hardness results
for uniform approximation, in view of ReQU activation function.

##  2 Sampling complexity on neural network approximation spaces

In this section, we will introduce the abstract setup and necessary notation
that we will consider throughout this paper. First of all, we will define
neural networks from a mathematical point of view. We distinguish between a
neural network as a set of weights and the realization of the neural network
as the associated function. Furthermore, we formally introduce the neural
network approximation spaces
$A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}$. Then we briefly
recall the framework of information based complexity, such as the
deterministic and randomized (Monte Carlo) algorithms and the optimal order of
convergence with respect to point samples.

###  2.1 Mathematical definition of neural networks

From a functional analysis point of view, _neural networks_ are functions of
compositional form that result from repeatedly applying affine maps and a non
linear map called activation function. In the definition of neural network, we
differentiate between the _architecture_ which is a tuple of matrices and
vectors, describing the parameters of the neural network, and the
_realization_ which is the associated functions. Concretely, we make the
following definition:

######  Definition 2.1.

Let $L\in\mathbb{N}$ and $N_{0},\dots,N_{L}\in\mathbb{N}$. A neural network
$\Phi$ with input dimension $N_{0}$ and $L$ layers is a sequence of matrix-
vector tuples

${\Phi=\big{(}(A_{1},b_{1}),\dots,(A_{L},b_{L})\big{)}},$

where $A_{\ell}\in\mathbb{R}^{N_{\ell}\times N_{\ell-1}}$ and
$b_{\ell}\in\mathbb{R}^{N_{\ell}}$ for any $\ell\in\\{1,\dots,L\\}$.

We refer to $(N_{0},\dots,N_{L})\in\mathbb{N}^{L+1}$ as the _architecture_ of
$\Phi$. We call $L(\Phi):=L$ the _number of layers_ 111Note that the number of
_hidden_ layers is given by $H=L-1$. of $\Phi$, and
${W(\Phi):=\sum_{j=1}^{L}(\|A_{j}\|_{\ell^{0}}+\|b_{j}\|_{\ell^{0}})}$ denotes
the _number of (non-zero) weights_ of $\Phi$. We denote by $\|A\|_{\ell^{0}}$
the number of non-zero entries of a matrix (or vector) $A$. We write
$d_{\mathrm{in}}(\Phi):=N_{0}$ and $d_{\mathrm{out}}(\Phi):=N_{L}$ for the
_input and output dimension_ of $\Phi$, respectively. Let
$\|\Phi\|_{\mathcal{NN}}:=\max_{j=1,\dots,L}\max\\{\|A_{j}\|_{\infty},\|b_{j}\|_{\infty}\\}$,
where ${\|A\|_{\infty}:=\max_{i,j}|A_{i,j}|}$.

The _realization_ of $\Phi$ is the map $R_{\varrho}\Phi$, where $\varrho$ is
the so-called _activation function_. In this paper, we will consider the
_rectified Quadratic unit (ReQU)_
${\varrho_{2}:\mathbb{R}\to\mathbb{R},x\mapsto\max(0,x)^{2}}$. The function
$R_{\varrho_{2}}\Phi:\mathbb{R}^{N_{0}}\to\mathbb{R}^{N_{L}}$ computed by the
network $\Phi$ is given by

$R_{\varrho_{2}}\Phi:=T_{L}\circ(\varrho_{2}\circ
T_{L-1})\circ\cdots\circ(\varrho_{2}\circ T_{1})\quad\text{where}\quad
T_{\ell}\,x=A_{\ell}\,x+b_{\ell}.$

###  2.2 Neural network approximation spaces

The notion of _neural network approximation spaces_ was originally introduced
in [16], where $\Sigma_{n}$ was taken to be a family of neural networks of
increasing complexity. We use more restrictive class compared to the class in
[16]. Indeed, we impose some growth conditions on the size of the network
weights. In our paper we use a similar class of neural network approximation
spaces to the one given in [20]. Namely, given a fixed input dimension
$d\in\mathbb{N}$ and non-decreasing functions
${\boldsymbol{\ell}:\mathbb{N}\to\mathbb{N}_{\geq 3}\cup\\{\infty\\}}$ and
${\boldsymbol{c}}:\mathbb{N}\to\mathbb{N}\cup\\{\infty\\}$ called the depth-
growth function and the coefficient growth function, respectively. We define
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$ as follows:

$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}:=\Big{\\{}R_{\varrho_{2}}\Phi\,\,\colon\begin{array}[]{l}\Phi\text{
NN with }d_{\mathrm{in}}(\Phi)=d,d_{\mathrm{out}}(\Phi)=1,\\\ W(\Phi)\leq
n,L(\Phi)\leq{\boldsymbol{\ell}}(n),\|\Phi\|_{\mathcal{NN}}\leq{\boldsymbol{c}}(n)\end{array}\Big{\\}}.$

In order to characterize the best possible convergence rate with respect to
the number of samples we need to define the following quantities:

$\displaystyle{\boldsymbol{\ell}}^{\ast}$
$\displaystyle:=\sup_{n\in\mathbb{N}}{\boldsymbol{\ell}}(n)\in\mathbb{N}\cup\\{\infty\\};$
(2.1) $\displaystyle{\boldsymbol{c}}^{\ast}$
$\displaystyle:=\sup_{n\in\mathbb{N}}{\boldsymbol{c}}(n)\in\mathbb{N}\cup\\{\infty\\}.$
(2.2)

Furthermore, let

$\displaystyle\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})$
$\displaystyle:=\sup\Big{\\{}\gamma\geq
0\colon\exists\,L\in\mathbb{N}_{\leq{\boldsymbol{\ell}}^{\ast}},\,C>0,\forall\,n\in\mathbb{N}:$
$\displaystyle n^{\gamma}\leq C\,\boldsymbol{c}(n)^{2^{{L}}-1}\cdot
n^{(2^{{L}}-1)/2}\Big{\\}},$ (2.3)
$\displaystyle\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})$
$\displaystyle:=\inf\Big{\\{}\gamma\geq
0\colon\exists\;C>0\;\forall\,n\in\mathbb{N},\,L\in\mathbb{N}_{\leq{\boldsymbol{\ell}}^{\ast}}:$
$\displaystyle\boldsymbol{c}(n)^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}\leq
C\,n^{\gamma}\Big{\\}}.$

######  Remark 2.2.

In view of the construction of
$\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})$ and
$\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})$ it follows that

$\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})\leq\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}}).$

Furthermore, since we will only consider settings in which
${\boldsymbol{\ell}}^{\ast}\geq 5$, we always have

${\boldsymbol{\ell}}^{\ast}\leq\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})\leq\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}}).$

Obviously if ${\boldsymbol{\ell}}$ is unbounded, that is
${\boldsymbol{\ell}}^{\ast}=\infty$, then
$\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})=\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})=\infty$.
We remark that in the case where ${\boldsymbol{\ell}}^{\ast}<\infty$ and
$\boldsymbol{c}(n)\asymp n^{\theta}\cdot\left(\log(2n)\right)^{\kappa}$ for
certain $\theta\geq 0$ and $\kappa\in\mathbb{R}$, then

$\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})=\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})=(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2).$

Indeed, for a fixed $C\geq 1$ and any
$L\in\mathbb{N}_{\leq{\boldsymbol{\ell}}^{\ast}}$, we have

$\displaystyle\frac{C\,n^{\gamma}}{\boldsymbol{c}(n)^{2^{{L}}-1}\cdot
n^{(2^{{L}}-1)/2}}\geq\frac{C\,n^{\gamma}}{\boldsymbol{c}(n)^{2^{\boldsymbol{\ell}^{\ast}}-1}\cdot
n^{(2^{\boldsymbol{\ell}^{\ast}}-1)/2}}$

and that

$\displaystyle\frac{C\,n^{\gamma}}{\boldsymbol{c}(n)^{2^{\boldsymbol{\ell}^{\ast}}-1}\cdot
n^{(2^{\boldsymbol{\ell}^{\ast}}-1)/2}}\asymp\frac{C\,n^{\gamma}}{\log(2n)^{\kappa(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)}\cdot
n^{(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2)}}\xrightarrow[n]{}C\,n^{\gamma-(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2)}$

hence

$\inf\\{\gamma\geq
0:C\,n^{\gamma-(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2)}\geq
1\\}=(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2)=\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}}).$

Similar arguments imply that
$\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})=(2^{{{\boldsymbol{\ell}}^{\ast}}}-1)(\theta+1/2)$.

Let $\Omega\subset[-1,1]^{d}$ be a measurable subset, $p\in[1,\infty]$, and
$\alpha\in(0,\infty)$, for each measurable $u:\Omega\to\mathbb{R}$, we define

$\Gamma_{\alpha,p}^{\varrho_{2}}(u):=\max\Big{\\{}\|u\|_{L^{p}(\Omega)},\;\sup_{n\in\mathbb{N}}\big{[}n^{\alpha}\cdot
d_{p}\bigl{(}u,\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}\bigr{)}\big{]}\Big{\\}}\in[0,\infty],$

where $d_{p}(u,\Sigma):=\inf_{g\in\Sigma}\|u-g\|_{L^{p}(\Omega)}$.

The remaining issue is that since the set
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$ is in general
neither closed under addition nor under multiplication with scalars,
$\Gamma_{\alpha,p}^{\varrho_{2}}$ is _not a (quasi)-norm_. To resolve this
issue, taking inspiration from the theory of Orlicz spaces (see e.g. [29,
Theorem 3 in Section 3.2]), we define the _neural network approximation space
quasi-norm_
$\|\cdot\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}$ as

$\|u\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}:=\inf\bigl{\\{}\theta>0\,\,\colon\,\,\Gamma_{\alpha,p}^{\varrho_{2}}(u/\theta)\leq
1\bigr{\\}}\in[0,\infty],$

giving rise to the _approximation space_

$A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}:=A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}(\Omega):=\bigl{\\{}u\in
L^{p}(\Omega)\,\,\colon\,\,\|u\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}<\infty\bigr{\\}}.$

The following lemma summarizes the main elementary properties of these spaces,
the proof can be concluded in a similar way to [20, Appendix A.1.], hence it
is left to the reader to check the details.

######  Lemma 2.3.

Let $\varnothing\neq\Omega\subset[-1,1]^{d}$ be measurable, let
$p\in[1,\infty]$ and $\alpha\in(0,\infty)$. Then,
$A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}:=A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}(\Omega)$
satisfies the following properties:

  1. 1.

$(A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}},\|\cdot\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c}}})$
is a quasi-normed space. Precisely, given arbitrary measurable functions
$u,v:\Omega\to\mathbb{R}$, then there exists $C>0$ such that

$\|u+v\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}\leq
C\cdot(\|u\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}+\|v\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}).$

  2. 2.

We have
$\Gamma_{\alpha,p}^{\varrho_{2}}(cu)\leq|c|\,\Gamma_{\alpha,p}^{\varrho_{2}}(u)$
for $c\in[-1,1]$.

  3. 3.

$\Gamma_{\alpha,p}^{\varrho_{2}}(u)\leq 1$ if and only if
$\|u\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}\leq 1$.

  4. 4.

$\Gamma_{\alpha,p}^{\varrho_{2}}(u)<\infty$ if and only if
$\|u\|_{A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}<\infty$.

  5. 5.

$A^{\alpha,p}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}(\Omega)\hookrightarrow
L^{p}(\Omega)$. Furthermore, if $\Omega\subset\overline{\Omega^{\circ}}$, then
$A^{\alpha,\infty}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}(\Omega)\hookrightarrow
C_{b}(\Omega)$, where $C_{b}(\Omega)$ denotes the Banach space of continuous
functions that are bounded and extend continuously to the closure
$\overline{\Omega}$ of $\Omega$.

###### Proof.

Proof is provided in Appendix A. ∎

###  2.3 Deterministic and Monte Carlo optimal orders

In the current paper, we focus on the unit ball in the neural network
approximation space
$A^{\alpha,\infty}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}([0,1]^{d})$,
i.e.,

$U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}):=\big{\\{}u\in
A^{\alpha,\infty}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}([0,1]^{d})\,\,\colon\,\,\|u\|_{A^{\alpha,\infty}_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}}\leq
1\big{\\}}.$ (2.4)

Let $\varnothing\neq U\subset C([0,1]^{d})$ be bounded and $Y$ be a Banach
space. A deterministic method of order $m\in\mathbb{N}$ is a map $A:U\to Y$,
written as $A\in\operatorname{Alg}_{m}(U,Y)$), such that there exists a sample
points $X=(x_{1},\dots,x_{m})\in([0,1]^{d})^{m}$ and a map
$Q:\mathbb{R}^{m}\to Y$ with the following property:

$A(u)=Q\bigl{(}u(x_{1}),\dots,u(x_{m})\bigr{)}\qquad\forall\,u\in U.$

The optimal error for deterministically approximating $S:U\to Y$ using $m$
point samples is then

$e^{\mathrm{det}}_{m}(U,S):=\inf_{A\in\operatorname{Alg}_{m}(U,Y)}\sup_{u\in
U}\|A(u)-S(u)\|_{Y}.$

The optimal order for deterministically approximating $S:U\to Y$ using point
samples is given by

$err^{\mathrm{det}}(U,S):=\sup\big{\\{}\beta\geq
0\,\,\colon\,\,\exists\,C>0\,\,\forall\,m\in\mathbb{N}:\quad
e^{\mathrm{det}}_{m}(U,S)\leq C\cdot m^{-\beta}\big{\\}}.$ (2.5)

A Monte Carlo method using $m\in\mathbb{N}$ point samples is a tuple
$(\boldsymbol{A},\boldsymbol{m})$ where $\boldsymbol{A}$ is a family of map
$\boldsymbol{A}=(A_{\omega})_{\omega\in\Omega}$ and $A_{\omega}:U\to Y$
indexed by a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and
$\boldsymbol{m}:\Omega\to\mathbb{N}$, denoted by
$\operatorname{Alg}^{\mathrm{MC}}_{m}(U,Y)$, such that the following holds
true

  1. 1.

$\boldsymbol{m}$ is measurable and $\mathbb{E}[\boldsymbol{m}]\leq m$;

  2. 2.

for any $u\in U$, the map $\omega\mapsto A_{\omega}(u)$ is measurable with
respect to the Borel $\sigma$-algebra on $Y$;

  3. 3.

for each $\omega\in\Omega$, we have
$A_{\omega}\in\operatorname{Alg}_{\boldsymbol{m}(\omega)}(U,Y)$.

The optimal Monte Carlo error for approximating $S:U\to Y$ using $m$ point
samples is

$e_{m}^{\mathrm{MC}}(U,S):=\inf_{(\boldsymbol{A},\boldsymbol{m})\in\operatorname{Alg}^{\mathrm{MC}}_{m}(U,Y)}\sup_{u\in
U}\mathbb{E}_{\omega}\bigl{[}\|S(u)-A_{\omega}(u)\|_{Y}\bigr{]}.$

The optimal Monte Carlo order for approximating $S:U\to Y$ using point samples
is

$err^{\mathrm{MC}}(U,S):=\sup\big{\\{}\beta\geq
0\,\,\colon\,\,\exists\,C>0\,\,\forall\,m\in\mathbb{N}:\quad
e_{m}^{\mathrm{MC}}(U,S)\leq C\cdot m^{-\beta}\big{\\}}.$

The following lemma shows that if a hardness result holds for deterministic
algorithms _in the average case_ , then this implies a hardness result for
Monte Carlo algorithms. The proof can be found in [20, Subsection 2.4].

######  Lemma 2.4.

Let $\varnothing\neq U\subset C([0,1]^{d})$ be bounded, let $Y$ be a Banach
space, and let $S:U\to Y$. Assume that there exist $\lambda\in[0,\infty)$,
$\kappa>0$, and $m_{0}\in\mathbb{N}$ such that for every $m\in\mathbb{N}_{\geq
m_{0}}$ there exists a finite set $\Gamma_{m}\neq\varnothing$ and a family of
functions $(u_{\gamma})_{\gamma\in\Gamma_{m}}\subset U$ satisfying

$\mathop{\mathchoice{{\vphantom{\leavevmode\hbox{$\displaystyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\displaystyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\textstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\textstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=8.00009pt}\cr$\scriptstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptscriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=6.00006pt}\cr$\scriptscriptstyle\sum$\cr}}}}\displaylimits_{\gamma\in\Gamma_{m}}\|S(u_{\gamma})-A(u_{\gamma})\|_{Y}\geq\kappa\cdot
m^{-\lambda}\qquad\text{for any }\,A\in\operatorname{Alg}_{m}(U,Y).$ (2.6)

Then $err^{\mathrm{det}}(U,S),err^{\mathrm{MC}}(U,S)\leq\lambda$.

##  3 Properties of ReQU approximation spaces
$U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$

We start by introducing the so-called _indicator-like function_
$\lambda_{M,y}^{p}:\mathbb{R}\rightarrow[0,1]$, where $p\in\mathbb{N}$,
$y\in\mathbb{R}$ and $M>0$, as follows:

$\lambda_{M,y}^{p}(x)=\left\\{\begin{array}[]{ll}0&\text{if}\quad x\leq
y-1/M\\\ \left(1-(-M(x-y))^{p}\right)^{p}&\text{if}\quad y-1/M\leq x\leq y\\\
\left(1-(M(x-y))^{p}\right)^{p}&\text{if}\quad y\leq x\leq y+1/M\\\
0&\text{if}\quad x\geq y+1/M.\end{array}\right.$

The function $M^{-p^{2}}\lambda_{M,y}^{p}$ can be implemented by two hidden
layers RePU neural networks as follows:

$M^{-p^{2}}\lambda_{M,y}^{p}(x)=\varrho_{p}\Big{(}\frac{1}{M^{p}}-\big{(}\varrho_{p}(x-y)+\varrho_{p}(y-x)\big{)}\Big{)}.$
(3.1)

Note that, if $p=1$, then the indicator-like function $\lambda_{M,y}^{1}(x)$
represents the _hat function_. Moreover, when $p=2$, then
$\lambda_{M,y}^{2}(x)$ is a _bump function_. For
$x=(x_{1},\dots,x_{d})\in\mathbb{R}^{d}$, we denote by
$\Lambda_{M,y}^{p}:\mathbb{R}^{d}\rightarrow\mathbb{R},x\mapsto\lambda_{M,y}^{p}(x_{1})$.

The construction of the function
$\Lambda_{M,y}^{2}:\mathbb{R}^{d}\to\mathbb{R}$ clearly shows that it has a
controlled support with respect to the first variable $x_{1}$ and unbounded
support for the other variables $x_{2},\dots,x_{d}$. Similar to the
construction in [20] we modify the indicator-like function in order to get a
function with controlled support with respect to all variables
$x_{1},\dots,x_{d}$. To that aim we compose the indicator-like function, for
$p=2$, with a _Heaviside-like_ function. It is worth mentioning that all these
functions can be implemented by ReQU neural networks.

######  Lemma 3.1.

Given $d\in\mathbb{N}$, $M>0$ and $y\in\mathbb{R}^{d}$, define

$\displaystyle\theta:$ $\displaystyle\mathbb{R}\to[0,1],\quad$ $\displaystyle
x\mapsto 2(\varrho_{2}(x)-2\varrho_{2}(x-\tfrac{1}{2})+\varrho_{2}(x-1)),$
$\displaystyle\Delta_{M,y}:$ $\displaystyle\mathbb{R}^{d}\to\mathbb{R},\quad$
$\displaystyle
x\mapsto\bigg{[}\sum_{j=1}^{d}\lambda_{M,y_{j}}^{2}(x_{j})\bigg{]}-(d-1),$ and
$\displaystyle\vartheta_{M,y}:$ $\displaystyle\mathbb{R}^{d}\to[0,1],\quad$
$\displaystyle x\mapsto\theta\bigl{(}\Delta_{M,y}(x)\bigr{)}.$

Then the function $\vartheta_{M,y}$ has the following properties:

  1. 1)

$\vartheta_{M,y}(x)=0$ for all
$x\in\mathbb{R}^{d}\setminus\bigl{(}y+M^{-1}(-1,1)^{d}\bigr{)}$;

  2. 2)

$\|\vartheta_{M,y}\|_{L^{p}(\mathbb{R}^{d})}\leq(2/M)^{d/p}$ for arbitrary
$p\in(0,\infty]$;

  3. 3)

For any $p\in(0,\infty]$ there is a constant $C=C(d,p)>0$ satisfying

$\|\vartheta_{M,y}\|_{L^{p}([0,1]^{d})}\geq C\cdot M^{-d/p},\quad\text{for all
}\,y\in[0,1]^{d}\text{ and }M\geq\tfrac{1}{2d}.$

###### Proof.

The first and second points in the lemma can be deduced in a similar way as in
the proof of [20, Lemma 3.4], hence we left the details for the reader to
check. It remains to show the last assertion in the lemma. Therefore, we let
$T:=\frac{1}{2dM}\in(0,1]$ and $P:=y+[-T,T]^{d}$. For $x\in P$ and arbitrary
$j\in\underline{d}$, we have $|x_{j}-y_{j}|\leq\frac{1}{2dM}$. Using the fact
that $\lambda_{M,y_{j}}^{2}$ is continuously differentiable function with
bounded derivative such that

$\left(\lambda_{M,y_{j}}^{2}\right)^{\prime}(x_{1})=\left\\{\begin{array}[]{ll}-4M^{2}(x_{1}-y)\bigl{(}1-M^{2}(x_{1}-y)^{2}\bigr{)}&\text{if}\quad
y-1/M\leq x_{1}\leq y+1/M\\\\[4.30554pt] 0&\text{
otherwise}.\end{array}\right.$

Moreover, $\bigl{|}\left(\lambda_{M,y_{j}}^{2}\right)^{\prime}\bigr{|}$
attends its maximum at $y\pm\tfrac{1}{\sqrt{3}M}$ with value equal to
$\frac{8M}{3\sqrt{3}}$. Then, it follows that $\lambda_{M,y_{j}}^{2}$ is a
Lipschitz function with
$\operatorname{Lip}(\lambda_{M,y_{j}}^{2})\leq\frac{8M}{3\sqrt{3}}$.
Furthermore, $\lambda_{M,y_{j}}^{2}(y_{j})=1$, hence we get

$\lambda_{M,y_{j}}^{2}(x_{j})\geq\lambda_{M,y_{j}}^{2}(y_{j})-\bigl{|}\lambda_{M,y_{j}}^{2}(y_{j})-\lambda_{M,y_{j}}(x_{j})\bigr{|}\geq
1-\frac{8M}{3\sqrt{3}}\cdot\frac{1}{2dM}=1-\frac{4}{3\sqrt{3}d}.$

The fact that this holds for all $j\in\underline{d}$, implies that

${\Delta_{M,y}(x)=\sum_{j=1}^{d}\Lambda_{M,y_{j}}(x_{j})-(d\\!-\\!1)\geq
d\\!\cdot\\!(1-\frac{4}{3\sqrt{3}d})-(d\\!-\\!1)=1-\frac{4}{3\sqrt{3}},}$

and since $\theta$ is non-decreasing we get

$\vartheta_{M,y}(x)=\theta(\Delta_{M,y}(x))\geq\theta(1-\frac{4}{3\sqrt{3}})=\frac{2}{81}(9-4\sqrt{(}3))^{2}.$

All in all, using the previous estimate and [20, Lemma A.2], for any Lebesgue
measure $\boldsymbol{\mu}$, it follows that

$\boldsymbol{\mu}([0,1]^{d}\cap(x+[-T,T]^{d}))\geq 2^{-d}T^{d}\geq C_{1}\cdot
M^{-d}\text{ such that }C_{1}=C_{1}(d)>0.$

Finally, we get

$\|\vartheta_{M,y}\|_{L^{p}([0,1]^{d})}\geq\frac{2}{81}(9-4\sqrt{(}3))^{2}[\boldsymbol{\mu}([0,1]^{d}\cap(x+[-T,T]^{d}))]^{1/p}\geq
C^{1/p}M^{-d/p}.$

∎

In the next result we show that $\vartheta_{M,y}$ can be implemented by ReQU
neural networks.

######  Lemma 3.2.

Let ${\boldsymbol{\ell}}:\mathbb{N}\to\mathbb{N}_{\geq 5}\cup\\{\infty\\}$ and
${\boldsymbol{c}}:\mathbb{N}\to\mathbb{N}\cup\\{\infty\\}$ be non-decreasing.
Let $n\in\mathbb{N}$, $M\geq 1$ and $1\leq C\leq
C^{8}\leq{\boldsymbol{c}}(n)$, as well as $L\in\mathbb{N}_{\geq 5}$ with
$L\leq{\boldsymbol{\ell}}(n)$. Then

$\frac{C^{2^{L}-1}n^{(2^{L}-1)/2}}{4M^{8}}\cdot\vartheta_{M,y}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{16n^{8}d+7L},\quad\text{
for any }\,y\in[0,1]^{d}.$

###### Proof.

Let $y\in[0,1]^{d}$ be fixed. For $j\in\underline{d}$, denote by $e_{j,d}$ the
$j$-th standard basis vector in $\mathbb{R}^{d\times 1}$. Let
$\zeta:=\sqrt{\frac{d-1}{d}}$ and

$\displaystyle A_{1}$
$\displaystyle:=\Big{(}\underbrace{e_{1,d}\big{|}-e_{1,d},\big{|}\dots\big{|}e_{1,d}\big{|}-e_{1,d}}_{2n\text{
times}},\dots,\;\underbrace{e_{d,d}\big{|}-e_{d,d}\big{|}\dots\big{|}e_{d,d}\big{|}-e_{d,d}}_{2n\text{
times}}\Big{)}^{T}\in\mathbb{R}^{2nd\times d},$ $\displaystyle b_{1}$
$\displaystyle:=\Big{(}\underbrace{-y_{1},y_{1},\dots,-y_{1},y_{1}}_{2n\text{
times}},\;\dots,\;\underbrace{-y_{d},y_{d},\dots,-y_{d},y_{d}}_{2n\text{
times}}\Big{)}^{T}\in\mathbb{R}^{2nd},$

$\displaystyle A_{2}$
$\displaystyle:=\left(\begin{matrix}-1&-1&0&0&\dots&0&0\\\
0&0&0&0&\dots&0&0\\\ 0&0&0&0&\dots&0&0\\\ 0&0&-1&-1&\dots&0&0\\\
0&0&0&0&\dots&0&0\\\ 0&0&0&0&\dots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\ 0&0&\dots&0&0&-1&-1\\\
0&0&\dots&0&0&0&0\\\
0&0&\dots&0&0&0&0\end{matrix}\right)\in\mathbb{R}^{3n^{8}d\times 2nd},$
$\displaystyle b_{2}$
$\displaystyle:=\frac{1}{M^{2}}\cdot\Big{(}1,\zeta,\frac{C^{8}M^{2}}{\sqrt{d}},1,\zeta,\frac{C^{8}M^{2}}{\sqrt{d}},\dots,1,\zeta,\frac{C^{8}M^{2}}{\sqrt{d}}\Big{)}^{T}\in\mathbb{R}^{3n^{8}d\times
1},$

$\displaystyle A_{3}$
$\displaystyle:=\frac{1}{n^{8}}\cdot\left(\begin{matrix}1&-1&0&1&-1&0&\dots&1&-1&0\\\\[4.30554pt]
1&-1&0&1&-1&0&\dots&1&-1&0\\\\[4.30554pt]
1&-1&0&1&-1&0&\dots&1&-1&0\\\\[4.30554pt]
0&0&n^{8}&0&0&n^{8}&\dots&0&0&n^{8}\end{matrix}\right)\in\mathbb{R}^{4\times
3n^{8}d},$ $\displaystyle b_{3}$
$\displaystyle:=\frac{1}{M^{4}}\cdot\left(0,-\frac{1}{2},-1,0\right)^{T}\in\mathbb{R}^{4\times
1},$

$\displaystyle
D_{1}:=\frac{1}{2}\cdot\Bigg{(}\begin{matrix}1&-2&1&2/C\sqrt{n}\\\\[4.30554pt]
-1&2&-1&2/C\sqrt{n}\end{matrix}\Bigg{)}\in\mathbb{R}^{2\times 4},\qquad
D_{2}:=\frac{1}{2}\cdot\left(\begin{matrix}1&-2&1&0\\\\[4.30554pt]
-1&2&-1&0\\\\[4.30554pt] 0&0&0&2\end{matrix}\right)\in\mathbb{R}^{3\times 4},$

$\displaystyle A$
$\displaystyle:=\frac{1}{4}\cdot\Bigg{(}\begin{matrix}1&-1&0\\\ -1&1&0\\\
0&0&4\end{matrix}\Bigg{)}\in\mathbb{R}^{3\times 3},\qquad$
$\displaystyle\alpha:=\left(1,1,0\right)^{T}\in\mathbb{R}^{3\times 1},$
$\displaystyle K$
$\displaystyle:=\frac{1}{4}\cdot\Bigg{(}\begin{matrix}1&-1&{4}/{C\sqrt{n}}\\\\[4.30554pt]
-1&1&{4}/{C\sqrt{n}}\end{matrix}\Bigg{)}\in\mathbb{R}^{2\times 3},\qquad$
$\displaystyle E:=\frac{1}{4}\Big{(}1,-1\Big{)}\in R^{1\times 2}.$

For any $j\in\\{1,\dots,d\\}$, in view of (3.1) where $p=2$, we can represent
the function $\lambda_{M,y_{j}}^{2}(x_{j})$ through ReQU network

$\frac{1}{M^{4}}\cdot\lambda_{M,y_{j}}^{2}(x_{j})=\varrho_{2}\Big{(}\frac{1}{M^{2}}-\big{(}\varrho_{2}(x_{j}-y_{j})+\varrho_{2}(y_{j}-x_{j})\big{)}\Big{)}\text{
for any }x_{j},y_{j}\in\mathbb{R}.$

Consequently, for the realization of the architecture
$\phi_{3}=\left((A_{1},b_{1}),(A_{2},b_{2}),(A_{3},b_{3})\right)$ with respect
to the ReQU activation function, assuming that $\eta_{j}=x_{j}-y_{j}$ for any
$j\in\\{1,\dots,d\\}$, we have

$A_{1}x+b_{1}=\Bigg{(}\underbrace{\eta_{1},-\eta_{1},\dots,\eta_{1},-\eta_{1}}_{2n\text{
times}},\dots,\underbrace{\eta_{d},-\eta_{d},\dots,\eta_{d},-\eta_{d}}_{2n\text{
times}}\Bigg{)}^{T},$

and

$A_{2}\varrho_{2}\left(A_{1}x+b_{1}\right)+b_{2}=\\\
\Bigg{(}\underbrace{-\varrho_{2}(\eta_{1})-\varrho_{2}(-\eta_{1})+\frac{1}{M^{2}},\frac{\zeta}{M^{2}},\frac{C^{8}}{\sqrt{d}},\dots,-\varrho_{2}(\eta_{1})-\varrho_{2}(-\eta_{1})+\frac{1}{M^{2}},\frac{\zeta}{M^{2}},\frac{C^{8}}{\sqrt{d}}}_{3n^{8}\text{
times}},\\\\[4.30554pt] \dots,\\\
\underbrace{-\varrho_{2}(\eta_{d})-\varrho_{2}(-\eta_{d})+\frac{1}{M^{2}},\frac{\zeta}{M^{2}},\frac{C^{8}}{\sqrt{d}},\dots,-\varrho_{2}(\eta_{d})-\varrho_{2}(-\eta_{d})+\frac{1}{M^{2}},\frac{\zeta}{M^{2}},\frac{C^{8}}{\sqrt{d}}}_{3n^{8}\text{
times}}\Bigg{)}^{T}.$

$\displaystyle\Big{(}R_{\varrho_{2}}\phi_{3}(x)\Big{)}_{1}$
$\displaystyle=\Bigl{(}A_{3}\varrho_{2}\bigl{(}A_{2}\,\varrho_{2}(A_{1}x+b_{1})+b_{2}\bigr{)}+b_{3}\Bigr{)}_{1}$
$\displaystyle=\frac{1}{n^{8}}\cdot\sum_{j=1}^{d}\sum_{\ell=1}^{n^{8}}\Big{[}\varrho_{2}\Big{(}\frac{1}{M^{2}}-\left(\varrho_{2}\bigl{(}\langle
x,e_{j}\rangle-y_{j}\bigr{)}+\varrho_{2}\bigl{(}-\langle
x,e_{j}\rangle+y_{j})\right)\Big{)}-\varrho_{2}(\frac{\zeta}{M^{2}})\Big{]}$
$\displaystyle=\frac{1}{M^{4}}\cdot\sum_{j=1}^{d}\Big{[}\lambda_{M,y_{j}}^{2}(x_{j})-\frac{d-1}{d}\Big{]}=\frac{1}{M^{4}}\cdot\Delta_{M,y}(x).$

In the same way, we get

$\displaystyle\Big{(}R_{\varrho_{2}}\phi_{3}(x)\Big{)}_{2}$
$\displaystyle=\frac{1}{M^{4}}\cdot\left(\Delta_{M,y}(x)-\tfrac{1}{2}\right)$
$\displaystyle\Big{(}R_{\varrho_{2}}\phi_{3}(x)\Big{)}_{3}$
$\displaystyle=\frac{1}{M^{4}}\cdot\left(\Delta_{M,y}(x)-1\right)$ and
$\displaystyle\Big{(}R_{\varrho_{2}}\phi_{3}(x)\Big{)}_{4}$
$\displaystyle=C^{16}n^{8}=C^{2^{4}}n^{2^{3}}.$

Let
$\psi_{1}=\Big{(}(A_{1},b_{1}),(A_{2},b_{2}),(A_{3},b_{3}),(D_{1},0)\Big{)}$,
a straightforward computation shows that

$\displaystyle R_{\varrho_{2}}\psi_{1}(x)$
$\displaystyle=\frac{1}{2}\cdot\Bigg{(}\begin{matrix}1&-2&1&2/C\sqrt{n}\\\\[4.30554pt]
-1&2&-1&2/C\sqrt{n}\end{matrix}\Bigg{)}\left(\begin{matrix}\frac{1}{M^{8}}\cdot\varrho_{2}\left(\Delta_{M,y}(x)\right)\\\\[4.30554pt]
\frac{1}{M^{8}}\cdot\varrho_{2}\left(\Delta_{M,y}(x)-\frac{1}{2}\right)\\\\[4.30554pt]
\frac{1}{M^{8}}\cdot\varrho_{2}\left(\Delta_{M,y}(x)-1\right)\\\\[4.30554pt]
C^{2^{5}}n^{2^{4}}\end{matrix}\right),$

hence, we have

$\displaystyle\Big{(}R_{\varrho_{2}}\psi_{1}(x)\Big{)}_{1}$
$\displaystyle=\frac{1}{2M^{8}}\cdot\Big{(}\varrho_{2}\bigl{(}\Delta_{M,y}(x)\bigr{)}-2\varrho_{2}\bigl{(}\Delta_{M,y}(x)-\tfrac{1}{2}\bigr{)}+\varrho_{2}\bigl{(}\Delta_{M,y}(x)-1\bigr{)}\Big{)}+\frac{C^{2^{5}}n^{2^{4}}}{C\sqrt{n}}$
$\displaystyle=\frac{1}{4M^{8}}\cdot\theta(\Delta_{M,y}(x))+C^{2^{5}-1}n^{2^{4}-\frac{1}{2}}=\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{5}-1}n^{(2^{5}-1)/2}$
and $\displaystyle\Big{(}R_{\varrho_{2}}\psi_{1}(x)\Big{)}_{2}$
$\displaystyle=-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{5}-1}n^{(2^{5}-1)/2}.$

Then,

$R_{\varrho_{2}}\psi_{1}(x)=\left(\begin{matrix}\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{5}-1}n^{(2^{5}-1)/2}\\\\[8.61108pt]
-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{5}-1}n^{(2^{5}-1)/2}\end{matrix}\right).$

In a similar way, we let
$\psi_{2}=\Big{(}(A_{1},b_{1}),(A_{2},b_{2}),(A_{3},b_{3}),(D_{2},\alpha)\Big{)}$.
We then get

$R_{\varrho_{2}}\psi_{2}(x)=\left(\begin{matrix}\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\\\\[8.61108pt]
-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\\\\[8.61108pt]
C^{2^{5}}n^{2^{4}}\end{matrix}\right).$ (3.2)

Since $y\in[0,1]^{d},n\in\mathbb{N}$, $\zeta\leq 1\leq M$ and that $1\leq
C\leq C^{8}\leq\boldsymbol{c}(n)$ it is clear that the weights

$\|A_{1}\|_{\infty},\|A_{2}\|_{\infty},\|A_{3}\|_{\infty},\|D_{1}\|_{\infty},\|D_{2}\|_{\infty},\|A\|_{\infty},\|K\|_{\infty},\|E\|_{\infty}\leq\boldsymbol{c}(n)$

and the biases

$\|b_{1}\|_{\infty},\|b_{2}\|_{\infty},\|b_{3}\|_{\infty},\|\alpha\|_{\infty},\leq\boldsymbol{c}(n).$

Furthermore, we have

$\|A_{1}\|_{\ell^{0}}\leq 2nd,\;\|A_{2}\|_{\ell^{0}}\leq
2n^{8}d,\;\|A_{3}\|_{\ell^{0}}\leq 3\times 2n^{8}d+n^{8}d=7n^{8}d,$

and

$\displaystyle\|D_{1}\|_{\ell^{0}}$
$\displaystyle=8,\;\|D_{2}\|_{\ell^{0}}=7,$ $\displaystyle\|A\|_{\ell^{0}}$
$\displaystyle=5,\;\|K\|_{\ell^{0}}=6,\;\|E\|_{\ell^{0}}=2.$

Moreover, the biases satisfy

$\displaystyle\|b_{1}\|_{\ell^{0}}$ $\displaystyle\leq
2nd,\;\|b_{2}\|_{\ell^{0}}\leq 3n^{8}d$ $\displaystyle\|b_{3}\|_{\ell^{0}}$
$\displaystyle=\|\alpha\|_{\ell^{0}}=2.$

In order to prove the claim of the lemma, we distinguish two cases depending
on the depth of the network.

Case 1: $L=5$. Here we let $\Phi$ the chosen architecture such that

$\Phi:=\big{(}(A_{1},b_{1}),(A_{2},b_{2}),(A_{3},b_{3}),(D_{1},0),(E,0)\big{)}$

The ReQU realization of $\Phi$ shows that

$\displaystyle R_{\varrho_{2}}\Phi(x)$
$\displaystyle=\frac{1}{4}\big{(}1,-1\big{)}R_{\varrho_{2}}\psi_{1}(x)$
$\displaystyle=\frac{1}{4}\big{(}1,-1\big{)}\left(\begin{matrix}\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{5}-1}n^{(2^{5}-1)/2}\right)\\\\[8.61108pt]
\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{5}-1}n^{(2^{5}-1)/2}\right)\end{matrix}\right)$
since for any $x$, and $n,M,C\geq 1$ it holds that
$0\leq\dfrac{\vartheta_{M,y}(x)}{4M^{8}}\leq C^{2^{5}-1}n^{(2^{5}-1)/2}$, we
get $\displaystyle R_{\varrho_{2}}\Phi(x)$
$\displaystyle=\frac{C^{2^{5}-1}n^{(2^{5}-1)/2}}{4M^{8}}\cdot\vartheta_{M,y}(x)=\frac{C^{2^{L}-1}n^{(2^{L}-1)/2}}{4M^{8}}\cdot\vartheta_{M,y}(x).$

The monotonicity of the functions ${\boldsymbol{c}}$ and ${\boldsymbol{\ell}}$
and the fact that $L=5$ imply the complexity of the network $\Phi$, indeed

$\displaystyle W(\Phi)$
$\displaystyle=\sum_{k=1}^{3}\left(\|A_{k}\|_{\ell^{0}}+\|b_{k}\|_{\ell^{0}}\right)+\|D_{1}\|_{\ell^{0}}+\|E\|_{\ell^{0}}$
$\displaystyle\leq 2nd+2nd+2n^{8}d+3n^{8}d+7n^{8}d+2+8+2$ $\displaystyle\leq
12n^{8}d+4nd+12\leq 16n^{8}d+7L.$ $\displaystyle L(\Phi)$
$\displaystyle=L\leq\boldsymbol{\ell}(n)\leq\boldsymbol{\ell}(16n^{8}d+7L),$
$\displaystyle\left\|\Phi\right\|_{\mathcal{NN}}$ $\displaystyle\leq
C^{8}\leq\boldsymbol{c}(n)\leq\boldsymbol{c}(16n^{8}d+7L).$

We conclude that
$\frac{C^{2^{L}-1}n^{(2^{L}-1)/2}}{4M^{8}}\cdot\vartheta_{M,y}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{16n^{8}d+7L}$.

Case 2: $L\geq 6$. In this case, we recall that
$\psi_{2}=\left((A_{1},b_{1}),(A_{2},b_{2}),(A_{3},b_{3}),(D_{2},\alpha)\right)$
and let the architecture $\Phi$ given by

$\Phi=\Big{(}\psi_{2},\underbrace{(A,\alpha),\dots,(A,\alpha)}_{L-6\text{
times}},(K,0),(E,0).\Big{)}$

The fact that $0\leq\dfrac{\vartheta_{M,y}(x)}{4M^{8}}\leq 1$ implies that

$\frac{1}{4}\left(\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)-\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\right)=\dfrac{\vartheta_{M,y}(x)}{4M^{8}},$
(3.3)

Then, from (3.2) and (3.3), we get

$\displaystyle A\varrho_{2}\left(R_{\varrho_{2}}\psi_{2}(x)\right)+\alpha$
$\displaystyle=\frac{1}{4}\cdot\Bigg{(}\begin{matrix}1&-1&0\\\ -1&1&0\\\
0&0&4\end{matrix}\Bigg{)}\left(\begin{matrix}\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\\\\[8.61108pt]
\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\\\\[8.61108pt]
\varrho_{2}\left(C^{2^{5}}n^{2^{4}}\right)\end{matrix}\right)+\left(\begin{matrix}1\\\\[4.30554pt]
1\\\\[4.30554pt] 0\end{matrix}\right)$
$\displaystyle=\frac{1}{4}\left(\begin{matrix}\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)-\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\\\\[8.61108pt]
-\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)+\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\\\\[8.61108pt]
4\,C^{2^{6}}n^{2^{5}}\end{matrix}\right)+\left(\begin{matrix}1\\\\[4.30554pt]
1\\\\[4.30554pt] 0\end{matrix}\right)$
$\displaystyle=\left(\begin{matrix}\dfrac{\vartheta_{M,y}(x)}{4M^{8}}\\\\[8.61108pt]
-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}\\\\[8.61108pt]
C^{2^{6}}n^{2^{5}}\end{matrix}\right)+\left(\begin{matrix}1\\\\[4.30554pt]
1\\\\[4.30554pt]
0\end{matrix}\right)=\left(\begin{matrix}\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\\\\[8.61108pt]
-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\\\\[8.61108pt]
C^{2^{6}}n^{2^{5}}\end{matrix}\right).$

We define, for any $j\in\\{0,1,2,\dots\\}$, the architecture $\Phi_{j}$ as

$\Phi_{j}:=\begin{cases}\Big{(}\psi_{2},\underbrace{(A,\alpha),\dots,(A,\alpha)}_{j\text{
times}}\Big{)},\quad&\text{when }j\in\mathbb{N},\\\ \psi_{2},\quad&\text{when
}j=0.\end{cases}$

Thus, from the previous computations, we get

$R_{\varrho_{2}}\Phi_{j}(x)=\left(\begin{matrix}\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\\\\[8.61108pt]
-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\\\\[8.61108pt]
C^{2^{j+5}}n^{2^{j+4}}\end{matrix}\right).$

Applying $K\,\varrho_{2}(\bullet)$ to the previous equation, we get

$\displaystyle K\varrho_{2}$
$\displaystyle\left(R_{\varrho_{2}}\Phi_{j}(x)\right)=\frac{1}{4}\cdot\Bigg{(}\begin{matrix}1&-1&{4}/{C\sqrt{n}}\\\\[4.30554pt]
-1&1&{4}/{C\sqrt{n}}\end{matrix}\Bigg{)}\left(\begin{matrix}\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\\\\[8.61108pt]
\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\\\\[8.61108pt]
\varrho_{2}\left(C^{2^{j+5}}n^{2^{j+4}}\right)\end{matrix}\right)$
$\displaystyle=\left(\begin{matrix}\frac{1}{4}\left(\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)-\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\right)+C^{2^{j+6}}n^{2^{j+5}}/C\sqrt{n}\\\\[8.61108pt]
-\frac{1}{4}\left(\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)-\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+1\right)\right)+C^{2^{j+6}}n^{2^{j+5}}/C\sqrt{n}\end{matrix}\right)$
$\displaystyle=\left(\begin{matrix}\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{j+6}}n^{2^{j+5}}/C\sqrt{n}\\\\[8.61108pt]
-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{j+6}}n^{2^{j+5}}/C\sqrt{n}\end{matrix}\right)=\left(\begin{matrix}\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{j+6}-1}n^{(2^{j+6}-1)/2}\\\\[8.61108pt]
-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{j+6}-1}n^{(2^{j+6}-1)/2}\end{matrix}\right).$

Finally, we have

$\displaystyle R_{\varrho_{2}}\Phi(x)$
$\displaystyle=E\varrho_{2}\left(K\varrho_{2}\left(R_{\varrho_{2}}\Phi_{L-6}(x)\right)\right)=\frac{1}{4}\Big{(}1,-1\Big{)}\left(\begin{matrix}\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{L}-1}n^{(2^{L}-1)/2}\right)\\\\[4.30554pt]
\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{L}-1}n^{(2^{L}-1)/2}\right)\end{matrix}\right)$
$\displaystyle=\frac{1}{4}\left(\varrho_{2}\left(\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{L}-1}n^{(2^{L}-1)/2}\right)-\varrho_{2}\left(-\dfrac{\vartheta_{M,y}(x)}{4M^{8}}+C^{2^{L}-1}n^{(2^{L}-1)/2}\right)\right)$
$\displaystyle=\frac{C^{2^{L}-1}n^{(2^{L}-1)/2}}{4M^{8}}\cdot\vartheta_{M,y}(x).$

As in the previous case, we determine the complexity of the network $\Phi$
when $L\geq 6$

$\displaystyle W(\Phi)$
$\displaystyle=\sum_{k=1}^{3}\left(\|A_{k}\|_{\ell^{0}}+\|b_{k}\|_{\ell^{0}}\right)+\|D_{2}\|_{\ell^{0}}+\|\alpha\|_{\ell^{0}}+(L-6)\left(\|A\|_{\ell^{0}}+\|\alpha\|_{\ell^{0}}\right)+\|E\|_{\ell^{0}}$
$\displaystyle\leq 2nd+2nd+2n^{8}d+3n^{8}d+7n^{8}d+2+7+2+(L-6)(5+2)+2$
$\displaystyle\leq 4nd+12n^{8}d+13+(L-6)7\leq 12n^{8}d+4nd+7L-29$
$\displaystyle\leq 16n^{8}d+7L.$ $\displaystyle L(\phi)$
$\displaystyle=L\leq\boldsymbol{\ell}(n)\leq\boldsymbol{\ell}(16n^{8}d+7L),$
$\displaystyle\left\|\Phi\right\|_{\mathcal{NN}}$ $\displaystyle\leq
C^{8}\leq\boldsymbol{c}(n)\leq\boldsymbol{c}(16n^{8}d+7L).$

Consequently, we see that
$\frac{C^{2^{L}-1}n^{(2^{L}-1)/2}}{4M^{8}}\cdot\vartheta_{M,y}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{16n^{8}d+7L}$.
∎

######  Lemma 3.3.

Let
${\boldsymbol{\ell}},{\boldsymbol{c}}:\mathbb{N}\to\mathbb{N}\cup\\{\infty\\}$
be non-decreasing with ${\boldsymbol{\ell}}^{\ast}\geq 5$. Let
$d\in\mathbb{N}$, $\alpha\in(0,\infty)$, and
$0<\gamma<\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})$. Then there
exists a constant
$\kappa=\kappa(\gamma,\alpha,d,{\boldsymbol{\ell}},{\boldsymbol{c}})>0$ such
that for any $M\geq 1$, we have

$g_{M,y}:=\kappa\cdot M^{-64\alpha/(8\alpha+\gamma)}\,\vartheta_{M,y}\in
A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})\qquad\text{with}\qquad\big{\|}g_{M,y}\big{\|}_{A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})}\leq
1.$

###### Proof.

From the fact that
$\gamma<\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})$, it follows that
there exist
$L=L(\gamma,{\boldsymbol{\ell}},{\boldsymbol{c}})\in\mathbb{N}_{\leq{\boldsymbol{\ell}}^{\ast}}$
and $C_{1}=C_{1}(\gamma,{\boldsymbol{\ell}},{\boldsymbol{c}})>0$ where
$n^{\gamma}\leq C_{1}\cdot\boldsymbol{c}(n)^{2^{{L}}-1}\cdot
n^{(2^{{L}}-1)/2}$ for any $n\in\mathbb{N}$. Without loss of generality, in
view of the fact that ${\boldsymbol{\ell}}^{\ast}\geq 5$, we assume that
$L\geq 5$. Using Equations 2.1, 2.2 and 2.3, the fact that
$L\leq{\boldsymbol{\ell}}^{\ast}$ implies the existence of
$n_{0}\in\mathbb{N}$ depends on $\gamma,{\boldsymbol{\ell}}$ and
${\boldsymbol{c}}$ such that $L\leq{\boldsymbol{\ell}}(n_{0})$.

Furthermore, let $M\geq 1$ and set
$n:=n_{0}\cdot\big{\lceil}M^{8/(8\alpha+\gamma)}\big{\rceil}$, noting that
$n\geq n_{0}$. Since

$n^{\gamma}\leq C_{1}\cdot\boldsymbol{c}(n)^{2^{{L}}-1}\cdot
n^{(2^{{L}}-1)/2},$

there exists $1\leq C\leq C^{8}\leq{\boldsymbol{c}}(n)$ such that

$n^{\gamma}\leq C_{1}\cdot C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}.$

Let

$\kappa:=\min\\{\left((16d+7L)\cdot(2n_{0})^{8}\right)^{-\alpha},\,C_{1}^{-1}\\}>0,$

and note that $\kappa$ depends on $d,\alpha,\gamma,{\boldsymbol{\ell}}$ and
${\boldsymbol{c}}$. Moreover, we have $n\geq M^{8/(8\alpha+\gamma)}$ which
implies that

$\displaystyle\kappa\,M^{-64\alpha/(8\alpha+\gamma)}$
$\displaystyle=\frac{\kappa}{M^{8}}\,M^{{8\gamma}/({8\alpha+\gamma})}\leq\frac{\kappa}{M^{8}}\cdot
n^{\gamma}$ $\displaystyle\leq\frac{\kappa}{M^{8}}\cdot C_{1}\cdot
C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}$ $\displaystyle\leq\frac{1}{M^{8}}\cdot
C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}.$

Note that the inclusion
$c\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{t}\subset\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{t}$
holds true for any $c$ such that $c\in[-1,1]$. Consequently, in view of Lemma
3.2 and the fact that $5\leq
L\leq{\boldsymbol{\ell}}(n_{0})\leq{\boldsymbol{\ell}}(n)$ it follows that

$g_{M,y}=\kappa\,M^{-64\alpha/(8\alpha+\gamma)}\,\vartheta_{M,y}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{16n^{8}d+7L}.$

By construction it is clear that
$\|g_{M,y}\|_{L^{\infty}}\leq\|\vartheta_{M,y}\|_{L^{\infty}}\leq 1$.
Furthermore, for $t\in\mathbb{N}$, we distinguish two cases: First, $t\geq
16n^{8}d+7L$, we have
$g_{M,y}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{t}$, hence
$t^{\alpha}\,d_{\infty}(g_{M,y},\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{t})=0\leq
1$. On the other hand, if $t\leq 16n^{8}d+7L$, in view of the fact that

$n\leq 1+n_{0}\,M^{8/(8\alpha+\gamma)}\leq 2n_{0}\,M^{8/(8\alpha+\gamma)},$

we have

$\displaystyle
t^{\alpha}\,d_{\infty}(g_{M,y},\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{t})$
$\displaystyle\leq\bigl{(}16n^{8}d+7L\bigr{)}^{\alpha}\,\|g_{M,y}\|_{L^{\infty}}\leq\bigl{(}16d+7L\bigr{)}^{\alpha}\,n^{8\alpha}\,\|g_{M,y}\|_{L^{\infty}}$
$\displaystyle\leq\bigl{(}16d+7L\bigr{)}^{\alpha}\,n^{8\alpha}\,\kappa\,M^{-64\alpha/(8\alpha+\gamma)}$
$\displaystyle\leq\bigl{(}16d+7L\bigr{)}^{\alpha}\,(2n_{0})^{8\alpha}\,M^{64\alpha/(8\alpha+\gamma)}\,\kappa\,M^{-64\alpha/(8\alpha+\gamma)}$
$\displaystyle\leq 1.$

Hence, $\Gamma_{\alpha,\infty}^{\varrho_{2}}(g_{M,y})\leq 1$, consequently
Lemma 2.3 shows that
$\|g_{M,y}\|_{A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}}\leq
1$. ∎

##  4 Error bounds for uniform approximation

Theorem 4.2 is the main theorem in this section, where we characterize the
error bound based on samples complexity for the computational problem of
uniform approximation on the ReQU neural network approximation space
$A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$.
We need Lemma 4.1 in our main theorem, in this lemma we derive an upper bound
on Lipschitz constant of functions
$F\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$ on bounded
domain and ReQU activation function. For any matrix $A\in\mathbb{R}^{k\times
m}$, define $\|A\|_{\infty}:=\max_{i,j}\left|A_{i,j}\right|$ and denote by
$\|A\|_{\ell^{0}}$ the number of non-zero entries of $A$.

######  Lemma 4.1.

Let $B(0,R)$ be the ball of center $0$ and radius $R\geq 1$ in
$\mathbb{R}^{d}$,
${\boldsymbol{\ell}}:\mathbb{N}\to\mathbb{N}\cup\\{\infty\\}$ and
${\boldsymbol{c}}:\mathbb{N}\to[1,\infty]$. Let $n\in\mathbb{N}$ and assume
that $L:={\boldsymbol{\ell}}(n)$ and $C:={\boldsymbol{c}}(n)$ are finite. Then
each $F\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$
satisfies:

$\displaystyle\operatorname{Lip}_{(B(0,R),\|\cdot\|_{\ell^{1}})\to\mathbb{R}}(F)$
$\displaystyle\leq 2^{2^{{L}}+{L}-3}R^{2^{{L}-1}-1}\cdot C^{2^{{L}}-1}\cdot
n^{(2^{{L}}-1)/2}$ and
$\displaystyle\operatorname{Lip}_{(B(0,R),\|\cdot\|_{\ell^{\infty}})\to\mathbb{R}}(F)$
$\displaystyle\leq d\cdot 2^{2^{{L}}+{L}-3}R^{2^{{L}-1}-1}\cdot
C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}.$

Furthermore, we have

$\displaystyle\operatorname{Lip}_{([0,1]^{d},\|\cdot\|_{\ell^{1}})\to\mathbb{R}}(F)$
$\displaystyle\leq 2^{2^{{L}}+{L}-3}d^{(2^{{L}-1}-1)/2}\cdot
C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}$ and
$\displaystyle\operatorname{Lip}_{([0,1]^{d},\|\cdot\|_{\ell^{\infty}})\to\mathbb{R}}(F)$
$\displaystyle\leq d\cdot 2^{2^{{L}}+{L}-3}d^{(2^{{L}-1}-1)/2}\cdot
C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}.$

###### Proof.

Let $F$ be an element of
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$, $\Phi$ is a
network given by
$\Phi=\big{(}(A_{1},b_{1}),\dots,(A_{\widetilde{L}},b_{\widetilde{L}})\big{)}$
such that $F=R_{\varrho_{2}}\Phi$ where
$\widetilde{L}\leq{\boldsymbol{\ell}}(n)=L$ and
$\max\\{\|A_{j}\|_{\infty},\|b_{j}\|_{\infty}\\}\leq\|\Phi\|_{\mathcal{NN}}\leq{\boldsymbol{c}}(n)=C$,
as well as $(\|A_{j}\|_{\ell^{0}}+\|b_{j}\|_{\ell^{0}})\leq W(\Phi)\leq n$ for
all $j\in\underline{\widetilde{L}}$. Let $T_{j}$ be an affine function defined
as $T_{j}(x):=A_{j}\,x+b_{j}$, where $A_{j}\in\mathbb{R}^{N_{j}\times
N_{j-1}}$, $b_{j}\in\mathbb{R}^{N_{j}}$ and set

$p_{j}=\begin{cases}1,&\text{if }j\text{ is even},\\\ \infty,&\text{if
}j\text{ is odd}.\end{cases}$

We recall that $\|A\|_{\infty}:=\max_{i,j}\left|A_{i,j}\right|$ and that
$\|A\|_{\ell^{0}}$ is the number of non-zero entries of $A$, for any matrix
$A\in\mathbb{R}^{k\times m}$. In view of the Step 1 in the proof of [20, Lemma
4.1], the function
$T_{j}:\bigl{(}\mathbb{R}^{N_{j-1}},\|\cdot\|_{\ell^{p_{j-1}}}\bigr{)}\to\bigl{(}\mathbb{R}^{N_{j}},\|\cdot\|_{\ell^{p_{j}}}\bigr{)}$
is Lipschitz with

$\operatorname{Lip}(T_{j})=\|A_{j}\|_{\ell^{p_{j-1}}\to\ell^{p_{j}}}\leq\begin{cases}\|A_{j}\|_{\infty}\,\|A_{j}\|_{\ell^{0}}\leq
Cn,&\text{if }j\text{ is even},\\\ \|A_{j}\|_{\infty}\leq C,&\text{if }j\text{
is odd},\end{cases}$

we refer the reader to [20, Lemma 4.1] for more details concerning this step.

The major difference in our constructed network is that our activation
function is not globally Lipschitz, instead it is locally Lipschitz. Thus, it
is impossible to get the inequalities in Lemma 4.1 for unbounded domains of
$\mathbb{R}^{d}$, which is the main reason behind the restriction of our
result to bounded domains.

Since for any bounded set $K$ such that $K\subset\mathbb{R}^{N_{j-1}}$, we
have $\varrho_{2}(K)$ and $T_{j}(K)$ are bounded subsets of
$\mathbb{R}^{N_{j-1}}$, for any $j$. More precisely we have

$T_{j}(B(0,R))\subset B(0,2\sqrt{n}CR),$

indeed, for any fixed $x\in B(0,R)\subset\mathbb{R}^{N_{j-1}}$,
$A\in\mathbb{R}^{N_{j}\times N_{j-1}}$ and $b\in\mathbb{R}^{N_{j}}$, we have

$\|T_{j}(x)\|_{\ell^{2}}^{2}\\!\leq\\!\sum_{i=1}^{N_{j}}\left|\sum_{k=1}^{N_{j-1}}(A_{j})_{i,k}x_{k}+b_{i}\right|^{2}\\!\\!\\!\leq\\!\sum_{i=1}^{N_{j}}\left[\left|\sum_{k=1}^{N_{j-1}}(A_{j})_{i,k}x_{k}\right|^{2}\\!\\!+\\!2\left|\sum_{k}^{N_{j-1}}(A_{j})_{i,k}x_{k}\right||b_{i}|\\!+\\!|b_{i}|^{2}\right]\\\\[4.30554pt]
\leq\sum_{i=1}^{N_{j}}\left[\left(\sum_{k=1}^{N_{j-1}}|(A_{j})_{i,k}|^{2}\sum_{k=1}^{N_{j-1}}|x_{k}|^{2}\right)+2\left(\sum_{k=1}^{N_{j-1}}|(A_{j})_{i,k}|^{2}\right)^{1/2}\left(\sum_{k=1}^{N_{j-1}}|x_{k}|^{2}\right)^{1/2}|b_{i}|+|b_{i}|^{2}\right]\\\\[4.30554pt]
\leq\sum_{i=1}^{N_{j}}\left[\left(\sum_{k=1}^{N_{j-1}}|(A_{j})_{i,k}|^{2}R^{2}\right)+2\left(\sum_{k=1}^{N_{j-1}}|(A_{j})_{i,k}|^{2}\right)^{1/2}R|b_{i}|+|b_{i}|^{2}\right]\\\\[4.30554pt]
\leq\sum_{i=1}^{N_{j}}\\!\\!\left(\\!\|A_{j}\|_{\infty}^{2}R^{2}\sum_{k=1}^{N_{j-1}}\mathds{1}_{(A_{j})_{i,k}\neq
0}\\!\right)\\!\\!+\\!2\|A_{j}\|_{\infty}R\sum_{i=1}^{N_{j}}\left(\sum_{k=1}^{N_{j-1}}\mathds{1}_{(A_{j})_{i,k}\neq
0}\\!\right)^{1/2}\\!\\!|b_{i}|+\\!\|b\|_{\infty}^{2}\sum_{i=1}^{N_{j}}|\mathds{1}_{b_{i}\neq
0}\\\\[4.30554pt]
\leq\|A_{j}\|_{\infty}^{2}R^{2}\sum_{i=1}^{N_{j}}\sum_{k=1}^{N_{j-1}}\mathds{1}_{(A_{j})_{i,k}\neq
0}+2\|A_{j}\|_{\infty}\|b\|_{\infty}R\sum_{i=1}^{N_{j}}\sum_{k=1}^{N_{j-1}}\mathds{1}_{(A_{j})_{i,k}\neq
0}\mathds{1}_{b_{i}\neq
0}+\|b\|_{\infty}^{2}\sum_{i=1}^{N_{j}}|\mathds{1}_{b_{i}\neq
0}\\\\[4.30554pt] \leq C^{2}R^{2}n+2C^{2}Rn+C^{2}n=nC^{2}(R^{2}+2R+1)\leq
nC^{2}(R+1)^{2}\leq 4nC^{2}R^{2}$ (4.1)

where we used the fact that $C,R\geq 1$. Furthermore, since $R\geq 1$ we have

$\varrho_{2}(B(0,R))\subset B(0,R^{2}).$ (4.2)

For any $x,y\in B(0,R)$, we define $\\{X_{j}\\}_{j=1}^{\widetilde{L}-1}$ and
$\\{Y_{j}\\}_{j=1}^{\widetilde{L}-1}$, such that

$\displaystyle X_{1}$ $\displaystyle=T_{1}(x),$ $\displaystyle Y_{1}$
$\displaystyle=T_{1}(y),$ $\displaystyle X_{2}$
$\displaystyle=T_{2}\circ\varrho_{2}\circ T_{1}(x),$ $\displaystyle Y_{2}$
$\displaystyle=T_{2}\circ\varrho_{2}\circ T_{1}(y),$ $\displaystyle\vdots$
$\displaystyle\vdots$ $\displaystyle X_{\widetilde{L}-1}$
$\displaystyle=T_{\widetilde{L}-1}\circ\varrho_{2}\circ\dots\circ\varrho_{2}\circ
T_{1}(x),$ $\displaystyle Y_{\widetilde{L}-1}$
$\displaystyle=T_{\widetilde{L}-1}\circ\varrho_{2}\circ\dots\circ\varrho_{2}\circ
T_{1}(y).$

Using the fact that we can write the difference
$\varrho_{2}(X_{j})-\varrho_{2}(Y_{j})$ for any $X_{j},Y_{j}\in B(0,R_{j})$ as

$\varrho_{2}(X_{j})-\varrho_{2}(Y_{j})=2(X_{j}-Y_{j})\int_{0}^{1}\varrho_{1}(tX_{j}-(1-t)Y_{j})dt,$

where $2\varrho_{1}$ is the derivative of $\varrho_{2}$. Furthermore, we have

$\left|\varrho_{2}(X_{j})-\varrho_{2}(Y_{j})\right|\leq
2\sup_{t\in[0,1]}\varrho_{1}(tX_{j}-(1-t)Y_{j})|X_{j}-Y_{j}|\leq
4R_{j}|X_{j}-Y_{j}|,$

which implies that $\varrho_{2}$ is $4R_{j}$-Lipschitz function from
$(B(0,R_{j}),\|\cdot\|_{\ell^{q}})$ to $(B(0,R_{j}^{2}),\|\cdot\|_{\ell^{q}})$
for any $q\in[1,\infty]$. Here we need to find out the values of $R_{j}$ such
that $j\in\\{1,\dots,{\widetilde{L}-1}\\}$. In view of (4.1) and (4.2), we
characterize $R_{j}$ by the sequence

$R_{0}=R,\;R_{1}=2\sqrt{n}CR_{0},\;R_{2}=2\sqrt{n}CR_{1}^{2},\;\dots,\;R_{j}=2\sqrt{n}CR_{j-1}^{2},$

hence we can be write $R_{j}$ as

$R_{j}=\begin{cases}2\sqrt{n}CR,&j=1\\\\[4.30554pt]
2\sqrt{n}CR_{j-1}^{2},&j\geq 2.\end{cases}$

Next we give a characterization of $R_{j}$ depending on the layer number $j$.
Indeed, for any $j\in\\{1,\dots,{\widetilde{L}-1}\\}$ we have

$R_{j}=(2\sqrt{n}C)^{\sum_{k=1}^{j}2^{k-1}}R^{2^{j-1}}=(2\sqrt{n}C)^{2^{j}-1}R^{2^{j-1}}.$
(4.3)

Using (4.3), the result holds for
$R_{1}=(2\sqrt{n}C)^{{2^{1}-1}}R^{2^{0}}=2\sqrt{n}CR$ and
$R_{2}=(2\sqrt{n}C)^{{2^{2}-1}}R^{2}=(2\sqrt{n}C)^{3}R^{2}$, assuming that
$R_{j}$ is true, we have

$\displaystyle R_{j+1}$
$\displaystyle=2\sqrt{n}CR_{j}^{2}=2\sqrt{n}C\left((2\sqrt{n}C)^{2^{j}-1}R^{2^{j-1}}\right)^{2}$
$\displaystyle=(2\sqrt{n}C)\cdot((2\sqrt{n}C)^{2^{j}-1})^{2}(R^{2^{j-1}})^{2}=(2\sqrt{n}C)^{1+2^{j+1}-2}R^{2^{j}}$
$\displaystyle=(2\sqrt{n}C)^{2^{j+1}-1}R^{2^{j}},$

which concludes the induction argument. Consequently, our network

$F=R_{\varrho_{2}}\Phi=T_{\widetilde{L}}\circ({\varrho_{2}}\circ
T_{\widetilde{L}-1})\circ\cdots\circ({\varrho_{2}}\circ
T_{1}):\quad(B(0,R),\|\cdot\|_{\ell^{1}})\to(\mathbb{R},\|\cdot\|_{\ell^{p_{\widetilde{L}}}})=(\mathbb{R},|\cdot|)$

is Lipschitz continuous on $B(0,R)$ as a composition of Lipschitz maps. Then,
the overall Lipschitz constant for $R_{\varrho_{2}}\Phi$ is given by

$\displaystyle\operatorname{Lip}(R_{\varrho_{2}}\Phi)$ $\displaystyle\leq
C\cdot n_{\widetilde{L}}\prod_{j=1}^{\widetilde{L}-1}\bigl{(}4R_{j}C\cdot
n_{j}\bigr{)}\leq\left(\prod_{j=1}^{\widetilde{L}-1}4(2\sqrt{n}C)^{2^{j}-1}R^{2^{j-1}}\right)\cdot
C^{\widetilde{L}}\cdot n^{\lfloor\widetilde{L}/2\rfloor}$
$\displaystyle=4^{\widetilde{L}-1}(2\sqrt{n}C)^{\sum_{j=1}^{\widetilde{L}-1}(2^{j}-1)}R^{\sum_{j=1}^{\widetilde{L}-1}2^{j-1}}\cdot
C^{\widetilde{L}}\cdot n^{\lfloor\widetilde{L}/2\rfloor}$
$\displaystyle=4^{\widetilde{L}-1}(2\sqrt{n}C)^{(2^{\widetilde{L}}-\widetilde{L}-1)}R^{2^{\widetilde{L}-1}-1}\cdot
C^{\widetilde{L}}\cdot n^{\lfloor\widetilde{L}/2\rfloor}$
$\displaystyle=2^{2\widetilde{L}-2}2^{2^{\widetilde{L}}-\widetilde{L}-1}R^{2^{\widetilde{L}-1}-1}\cdot
C^{2^{\widetilde{L}}-\widetilde{L}-1+\widetilde{L}}\cdot
n^{\frac{1}{2}(2^{\widetilde{L}}-\widetilde{L}-1)+\lfloor\widetilde{L}/2\rfloor}$
$\displaystyle\leq
2^{2^{\widetilde{L}}+\widetilde{L}-3}R^{2^{\widetilde{L}-1}-1}\cdot
C^{2^{\widetilde{L}}-1}\cdot n^{(2^{\widetilde{L}}-1)/2}$ $\displaystyle\leq
2^{2^{{L}}+{L}-3}R^{2^{{L}-1}-1}\cdot C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}$

where we used the notation $n_{j}:=n$ if $j$ is even and $n_{j}:=1$ otherwise
and that $R,C\geq 1$. The final claim of the lemma holds, since
$\|x\|_{\ell^{1}}\leq d\cdot\|x\|_{\ell^{\infty}}$ for $x\in
B(0,R)\subset\mathbb{R}^{d}$.

The remaining part of the lemma is straightforward, since $[0,1]^{d}\subset
B(0,\sqrt{d})$. ∎

The bound in the previous lemma is the main reason for the choice of
$\gamma^{\flat}$ and $\gamma^{\sharp}$ in (2.3). Generalizing the upper bounds
in the previous lemma for different activation functions can be thought of as
a future line of research. Also one could investigate the impact of the
magnitude of the weights, for instance if
${\boldsymbol{c}}(n)\leq\frac{1}{\sqrt{n}}$ we remark that the upper bound in
the previous lemma depends only on the depth in the first case, while in the
second one it depends on the depth and the dimension of the data.

######  Theorem 4.2.

Let
${\boldsymbol{\ell}},{\boldsymbol{c}}:\mathbb{N}\to\mathbb{N}\cup\\{\infty\\}$
be non-decreasing, $d\in\mathbb{N}$ and $\alpha\in(0,\infty)$ be arbitrary and
suppose that $\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})<\infty$.
Let
$U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$
as in (2.4). Furthermore, let
$\iota_{\infty}:A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})\to
C([0,1]^{d}).$ Then, we have

$err^{\mathrm{det}}\bigl{(}U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty}\bigr{)},err^{\mathrm{MC}}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty})\geq\alpha/d(\alpha+\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})).$

###### Proof.

Using Remark 2.2 and the fact that
$\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})<\infty$, it follows
that $L:={\boldsymbol{\ell}}^{\ast}<\infty$. Let $\gamma\in\mathbb{R}$, such
that $1\leq\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})<\gamma$. In
view of the definition of
$\gamma^{\sharp}({\boldsymbol{\ell}},{\boldsymbol{c}})$ in (2.3), there exists
a constant $C_{0}=C_{0}(d,\gamma,{\boldsymbol{\ell}},{\boldsymbol{c}})>0$ such
that

$C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2}\leq C_{0}\cdot n^{\gamma}$ (4.4)

for all $n\in\mathbb{N}$. Suppose that

$N:=\big{\lfloor}m^{{1/d}}\big{\rfloor}\qquad\text{ and }\qquad
n:=\big{\lceil}m^{1/d(\alpha+\gamma)}\big{\rceil},$ (4.5)

for any $m\in\mathbb{N}$. In view of the previous construction, we get that
$N\geq 1$ and $n\in\mathbb{N}$. Furthermore, let

$I:=\bigl{\\{}0,\frac{1}{N},\dots,\frac{N-1}{N}\bigr{\\}}^{d},$

it follows that $I\subset[0,1]^{d}$. Let $C:={\boldsymbol{c}}(n)$ and

$\mu:=d\cdot 2^{2^{{L}}+{L}-3}d^{(2^{{L}-1}-1)/2}\cdot C^{2^{{L}}-1}\cdot
n^{(2^{{L}}-1)/2}.$

Using (4.4), we have

$\mu\leq d\cdot 2^{2^{{L}}+{L}-3}d^{(2^{{L}-1}-1)/2}\cdot C_{0}\cdot
n^{\gamma}=:C_{1}\,n^{\gamma}$

such that $C_{1}$ depends on $\gamma,{\boldsymbol{\ell}},{\boldsymbol{c}}$ and
$d$. Furthermore, we have that $|I|=N^{d}\leq m.$ Recalling that

$U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})=\bigl{\\{}f\in
A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})\colon\|f\|_{A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})}\leq
1\bigr{\\}}.$

Let
$\Lambda:=\Psi(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}))$
such that $\Psi$ defined as follows:

$\Psi:\quad C([0,1]^{d})\to\mathbb{R}^{I},\quad
f\mapsto\big{(}f(i)\big{)}_{i\in I}.$

For any element $z\in\Lambda$, $z$ can be written as $z=(z_{i})_{i\in I}$.
Moreover, there exits $f_{z}\in
U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$
such that $z=\Psi(f_{z})$. Furthermore, by construction of
$U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$
and the fact that $f_{z}\in
U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$,
we have
$\|f_{z}\|_{A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})}\leq
1$, which implies that $\Gamma_{\alpha,\infty}^{\varrho_{2}}(f_{z})\leq 1$ (
in view of Lemma 2.3). Consequently, by definition of
$\Gamma_{\alpha,\infty}^{\varrho_{2}}(f_{z})$ and the fact that
$\Gamma_{\alpha,\infty}^{\varrho_{2}}(f_{z})\leq 1$, there exists
$F_{z}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$ satisfying

$\|f_{z}-F_{z}\|_{L^{\infty}}\leq 2\cdot n^{-\alpha}.$

Given this choice, let

$\Xi:\quad\mathbb{R}^{I}\to C([0,1]^{d}),\quad
z\mapsto\begin{cases}F_{z},&\text{if }z\in\Lambda,\\\
0,&\text{otherwise}.\end{cases}$

Let $f\in
U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$
and $z:=\Psi(f)\in\Lambda$. Similar to the argument above, there exists
$F\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$ such that
$\|f-F\|_{L^{\infty}}\leq 2\cdot n^{-\alpha}$. Consequently, we have

$f(i)=(\Psi(f))_{i}=z_{i}=(\Psi(f_{z}))_{i}=f_{z}(i),\quad\text{for any}\;i\in
I$

which implies that

$|F(i)-F_{z}(i)|\leq|F(i)-f(i)|+|f_{z}(i)-F_{z}(i)|\leq\|F-f\|_{L^{\infty}}+\|f_{z}-F_{z}\|_{L^{\infty}}\leq
4\cdot n^{-\alpha}.$

In view of the fact that $F$ and $F_{z}$ belong to
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$, Lemma 4.1 implies
that $F$ and $F_{z}$ are $(d\cdot 2^{2^{{L}}+{L}-3}d^{(2^{{L}-1}-1)/2}\cdot
C^{2^{{L}}-1}\cdot n^{(2^{{L}}-1)/2})$ -Lipschitz from
$([0,1]^{d},\|\cdot\|_{\ell^{\infty}})$ to $(\mathbb{R},|\cdot|)$.

Then $F-F_{z}:([0,1]^{d},\|\cdot\|_{\ell^{\infty}})\to(\mathbb{R},|\cdot|)$ is
Lipschitz continuous with Lipschitz constant at most $2\mu$. Furthermore, for
any $x\in[0,1]^{d}$, we can choose $i=i(x)\in I$ such that
$\|x-i\|_{\ell^{\infty}}\leq N^{-1}$. Hence, we have

$\displaystyle|(F-F_{z})(x)|$
$\displaystyle\leq|(F-F_{z})(x)-(F-F_{z})(i)|+|(F-F_{z})(i)|$
$\displaystyle\leq\frac{2\mu}{N}+|(F-F_{z})(i)|\leq\frac{2\mu}{N}+4\,n^{-\alpha}.$

Consequently, we have

$\|F-F_{z}\|_{L^{\infty}}\leq\frac{2\mu}{N}+4\,n^{-\alpha}.$ (4.6)

Since $\Xi(\Psi(f))=\Xi(z)=F_{z}$, Equation 4.6 implies that

$\big{\|}f-\Xi(\Psi(f))\big{\|}_{L^{\infty}}\leq\|f-F\|_{L^{\infty}}+\|F-F_{z}\|_{L^{\infty}}\leq
6\,n^{-\alpha}+\frac{2\mu}{N}.$

It remains to note that our choice of $N$ in (4.5) implies that $m^{{1/d}}\leq
1+N\leq 2N$ and that $\frac{1}{N}\leq 2m^{-1/d}$. Moreover, in view of the
construction given in (4.5), we have

$n\leq 1+m^{1/d(\gamma+\alpha)}\leq 2\,m^{1/d(\gamma+\alpha)}.$

Hence, recalling that $\mu\leq C_{1}\,n^{\gamma}$, it follows that

$\displaystyle\frac{\mu}{N}$ $\displaystyle\leq 2m^{-1/d}\cdot\mu\leq
2m^{-1/d}\cdot C_{1}n^{\gamma}$ $\displaystyle\leq 2m^{-1/d}\cdot
C_{1}(2\,m^{1/d(\gamma+\alpha)})^{\gamma}=2^{\gamma+1}C_{1}m^{\gamma/d(\gamma+\alpha)-\frac{1}{d}}$
$\displaystyle=2^{\gamma+1}C_{1}m^{-\alpha/d(\gamma+\alpha)}.$

Observing that in view of (4.5), we have $n\geq m^{1/d(\gamma+\alpha)}$, which
implies that

$n^{-\alpha}\leq m^{-\alpha/d(\gamma+\alpha)}.$

Finally, using the previous approximations, we get the following upper bound

$\|f-\Xi(\Psi(f))\|_{L^{\infty}}\leq C_{2}\cdot m^{-\alpha/d(\gamma+\alpha)}$

where $C_{2}$ is a positive constant depends on $d,\gamma,{\boldsymbol{\ell}}$
and ${\boldsymbol{c}}$. It follows that

$err^{\mathrm{det}}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty})\geq\alpha/d(\gamma+\alpha).$

In order to conclude our proof we use [22, Proposition 3.3] which then implies
that

$err^{\mathrm{MC}}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty})\geq\alpha/d(\gamma+\alpha).$

hence the claim of the theorem holds. ∎

##  5 Hardness of uniform approximation

The following result is our second main result of the current paper. In
Theorem 5.1 we determine an upper bound for the best possible convergence rate
with respect to the number of samples.

######  Theorem 5.1.

Let ${\boldsymbol{\ell}}:\mathbb{N}\to\mathbb{N}_{\geq 5}\cup\\{\infty\\}$ and
${\boldsymbol{c}}:\mathbb{N}\to\mathbb{N}\cup\\{\infty\\}$ be non-decreasing
functions. Given $d\in\mathbb{N}$ and $\alpha\in(0,\infty)$, let
$U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$
be defined as in Equation 2.4,
$\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})$ from (2.3) and consider
the embedding
$\iota_{\infty}:A_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})\hookrightarrow
C([0,1]^{d})$. Then

$err^{\mathrm{det}}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty}),err^{\mathrm{MC}}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty})\leq{{64\alpha}/d({8\alpha+\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})})}.$

###### Proof.

Let $0<\gamma<\gamma^{\flat}({\boldsymbol{\ell}},{\boldsymbol{c}})$ and choose
an arbitrary $m\in\mathbb{N}$ and let $M:=4\lceil m^{1/d}\rceil$. Furthermore,
let $I_{m}:=\underline{2\lceil m^{1/d}\rceil}^{d}\times\\{\pm 1\\}$ and

$y^{(\boldsymbol{i})}:=\frac{2\left(\boldsymbol{i}-(1,\dots,1)\right)+(1,\dots,1)}{M}\in\mathbb{R}^{d}\quad\text{
for any }\boldsymbol{i}\in\underline{2\lceil m^{1/d}\rceil}^{d}.$

In view of the previous construction it follows that

$\displaystyle y^{(\boldsymbol{i})}+(-\frac{1}{M},\frac{1}{M})^{d}$
$\displaystyle=\frac{2\left(\boldsymbol{i}-(1,\dots,1)\right)+(1,\dots,1)}{M}+(-\frac{1}{M},\frac{1}{M})^{d}$
$\displaystyle=\frac{1}{M}\left({2\left(\boldsymbol{i}-(1,\dots,1)\right)+(1,\dots,1)}+(-1,1)^{d}\right)$
$\displaystyle=\frac{1}{M}\left(2\left(\boldsymbol{i}-(1,\dots,1)\right)+(0,2)^{d}\right)$
$\displaystyle=\frac{2}{M}\Big{(}\boldsymbol{i}-(1,\dots,1)+(0,1)^{d}\Big{)}\subset(0,1)^{d}.$

Using $\vartheta_{M,y^{(\boldsymbol{i})}}$ defined in Lemma 3.1, the fact that
$y^{(\boldsymbol{i})}+(-\frac{1}{M},\frac{1}{M})^{d}\subset(0,1)^{d}$ implies
that $\vartheta_{M,y^{(\boldsymbol{i})}}$ have disjoint supports contained in
$[0,1]^{d}$, for any $\boldsymbol{i}\in\underline{2\lceil m^{1/d}\rceil}^{d}$.
In view of Lemma 3.3 there exists a constant $\kappa_{1}>0$ depends on
$\gamma,\alpha,d,{\boldsymbol{\ell}}$ and ${\boldsymbol{c}}$ such that for any
$(\boldsymbol{i},\nu)\in I_{m}$ the following holds true:

$f_{\boldsymbol{i},\nu}:=\kappa_{1}\cdot
M^{-64\alpha/(8\alpha+\gamma)}\cdot\nu\cdot\vartheta_{M,y^{(\boldsymbol{i})}}\in
U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}).$

Let
$A\in\operatorname{Alg}_{m}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),C([0,1]^{d}))$
then, by definition, there exist $m$ sample points in $[0,1]^{d}$, i.e.,
$X=(x^{(1)},\dots,x^{(m)})\in\left([0,1]^{d}\right)^{m}$ and a function
$Q:\mathbb{R}^{m}\to\mathbb{R}$ with the property that

$A(f)=Q(f(x_{1}),\dots,f(x_{m}))\text{ for all }f\in
U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}).$

Furthermore, let $\Gamma_{X}:=\big{\\{}\boldsymbol{i}\in\underline{2\lceil
m^{1/d}\rceil}^{d}\colon\forall\,n\in\underline{m}:\vartheta_{M,y^{(\boldsymbol{i})}}(x_{n})=0\big{\\}}$
and denote the complement of the set $\Gamma_{X}$ in $\underline{2\lceil
m^{1/d}\rceil}^{d}$ by

$\mathcal{C}(\Gamma_{X},\underline{2\lceil
m^{1/d}\rceil}^{d})=\underline{2\lceil m^{1/d}\rceil}^{d}\setminus\Gamma_{X}.$

The definition of the previous set implies that for each
$\boldsymbol{i}\in\mathcal{C}(\Gamma_{X},\underline{2\lceil
m^{1/d}\rceil}^{d})$, there exists $n_{\boldsymbol{i}}\in\underline{m}$ such
that $\vartheta_{M,y^{(\boldsymbol{i})}}(x_{n_{\boldsymbol{i}}})\neq 0$.
Consequently, $\mathcal{C}(\Gamma_{X},\underline{2\lceil
m^{1/d}\rceil}^{d})\to\underline{m},\boldsymbol{i}\mapsto n_{\boldsymbol{i}}$
is an injective map, since
$\vartheta_{M,y^{(\boldsymbol{i})}}\vartheta_{M,y^{(\boldsymbol{j})}}=0$ for
$\boldsymbol{i},\boldsymbol{j}\in\underline{2\lceil m^{1/d}\rceil}^{d}$ with
$\boldsymbol{i}\neq\boldsymbol{j}$. Hence
$|\mathcal{C}(\Gamma_{X},\underline{2\lceil m^{1/d}\rceil}^{d})|\leq m$ which
implies that $|\Gamma_{X}|\geq({2\lceil m^{1/d}\rceil})^{d}-m\geq m$. Then for
any $\boldsymbol{i}\in\Gamma_{X}$ and $\nu\in\\{\pm 1\\}$, we have
$f_{\boldsymbol{i},\nu}(x_{n})=0$ for all $n\in\underline{m}$ and
$A(f_{\boldsymbol{i},\nu})=Q(0,\dots,0)$. Therefore for any
$\boldsymbol{i}\in\Gamma_{X}$ we have

$\begin{split}\mathop{\mathchoice{{\vphantom{\leavevmode\hbox{$\displaystyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\displaystyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\textstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\textstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=8.00009pt}\cr$\scriptstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptscriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=6.00006pt}\cr$\scriptscriptstyle\sum$\cr}}}}\displaylimits_{\nu\in\\{\pm
1\\}}\|f_{\boldsymbol{i},\nu}-A(f_{\boldsymbol{i},\nu})\|_{L^{\infty}}&=\frac{1}{2}\left(\|f_{\boldsymbol{i},1}-A(f_{\boldsymbol{i},1})\|_{L^{\infty}}+\|f_{\boldsymbol{i},-1}-A(f_{\boldsymbol{i},-1})\|_{L^{\infty}}\right)\\\
&=\frac{1}{2}\left(\|f_{\boldsymbol{i},1}-Q(0,\dots,0)\|_{L^{\infty}}+\|-f_{\boldsymbol{i},1}-Q(0,\dots,0)\|_{L^{\infty}}\right)\\\\[4.30554pt]
&=\frac{1}{2}\left(\|f_{\boldsymbol{i},1}-Q(0,\dots,0)\|_{L^{\infty}}+\|Q(0,\dots,0)+f_{\boldsymbol{i},1}\|_{L^{\infty}}\right)\\\\[4.30554pt]
&\geq\frac{1}{2}\left(\|f_{\boldsymbol{i},1}-Q(0,\dots,0)+Q(0,\dots,0)+f_{\boldsymbol{i},1}\|_{L^{\infty}}\right)\\\\[4.30554pt]
&=\|f_{\boldsymbol{i},1}\|_{L^{\infty}}=\kappa_{1}\cdot
M^{-64\alpha/(8\alpha+\gamma)}.\end{split}$ (5.1)

Recalling that $M=4{\lceil m^{1/d}\rceil}$ which implies that $M\leq
1+4{m^{1/d}}\leq 8m^{1/d}$, and hence

$M^{-{64\alpha}/({8\alpha+\gamma})}\geq
8^{-{64\alpha}/({8\alpha+\gamma})}m^{-{{64\alpha}}/{d(8\alpha+\gamma)}}\geq\frac{1}{8^{8}}m^{-{{64\alpha}}/{d(8\alpha+\gamma)}}.$

The fact that $|\Gamma_{X}|\geq m$, $\lceil m^{1/d}\rceil\leq 1+m^{1/d}\leq
2m^{1/d}$ and Equation 5.1 imply that

$\displaystyle\mathop{\mathchoice{{\vphantom{\leavevmode\hbox{$\displaystyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\displaystyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\textstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\textstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=8.00009pt}\cr$\scriptstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptscriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=6.00006pt}\cr$\scriptscriptstyle\sum$\cr}}}}\displaylimits_{(\boldsymbol{i},\nu)\in
I_{m}}\|f_{\boldsymbol{i},\nu}-A(f_{\boldsymbol{i},\nu})\|_{L^{\infty}}$
$\displaystyle\geq\frac{1}{(2\lceil
m^{1/d}\rceil)^{d}}\,\sum_{\boldsymbol{i}\in\Gamma_{X}}\mathop{\mathchoice{{\vphantom{\leavevmode\hbox{$\displaystyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\displaystyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\textstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\textstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=8.00009pt}\cr$\scriptstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptscriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=6.00006pt}\cr$\scriptscriptstyle\sum$\cr}}}}\displaylimits_{\nu\in\\{\pm
1\\}}\|f_{\boldsymbol{i},\nu}-A(f_{\boldsymbol{i},\nu})\|_{L^{\infty}}$
$\displaystyle\geq\frac{1}{(2\lceil
m^{1/d}\rceil)^{d}}\cdot|\Gamma_{X}|\cdot\kappa_{1}\cdot
M^{-64\alpha/(8\alpha+\gamma)}$
$\displaystyle\geq\frac{1}{4^{d}}\cdot\kappa_{1}\cdot
M^{-64\alpha/(8\alpha+\gamma)}$
$\displaystyle\geq\frac{1}{2^{2d}}\cdot\kappa_{1}\cdot\frac{1}{2^{24}}m^{-{64\alpha}/d({8\alpha+\gamma})}=\kappa\cdot
m^{-{64\alpha}/d({8\alpha+\gamma})},$

where $\kappa:=\frac{1}{2^{2d+24}}\cdot\kappa_{1}$. Consequently, we show that
there is a constant
$\kappa=\kappa(d,\alpha,\gamma,{\boldsymbol{\ell}},{\boldsymbol{c}})>0$ and a
family of functions $(f_{\boldsymbol{i},\nu})_{(\boldsymbol{i},\nu)\in
I_{m}}\subset
U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d})$
such that for any
$A\in\operatorname{Alg}_{m}\bigl{(}U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),C([0,1]^{d})\bigr{)}$
it follows that

$\mathop{\mathchoice{{\vphantom{\leavevmode\hbox{$\displaystyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\displaystyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\textstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=11.00012pt}\cr$\textstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=8.00009pt}\cr$\scriptstyle\sum$\cr}}}{{\vphantom{\leavevmode\hbox{$\scriptscriptstyle\sum$}}\ooalign{\smash{\vrule
height=1.0pt,depth=6.00006pt}\cr$\scriptscriptstyle\sum$\cr}}}}\displaylimits_{(\boldsymbol{i},\nu)\in
I_{m}}\big{\|}f_{\boldsymbol{i},\nu}-A(f_{\boldsymbol{i},\nu})\big{\|}_{L^{\infty}}\geq\kappa\cdot
m^{-{64\alpha}/d({8\alpha+\gamma})}.$ (5.2)

In view of Lemma 2.4 it follows that

$err^{\mathrm{det}}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty}),err^{\mathrm{MC}}(U_{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}^{\alpha,\infty}([0,1]^{d}),\iota_{\infty})\leq{{64\alpha}/d({8\alpha+\gamma})},$

which implies the claim of the theorem. ∎

## References

  * [1] A. Abdeljawad. Deep Neural Network Approximation For Hölder Functions. ArXiv:2201.03747, (2022).
  * [2] A. Abdeljawad and T. Dittrich. Space-Time Approximation with Shallow Neural Networks in Fourier Lebesgue spaces. ArXiv:2312.08461, (2023).
  * [3] A. Abdeljawad and P. Grohs. Approximations with deep neural networks in Sobolev time-space. Anal. Appl., 20, 499–541, (2022).
  * [4] C. Beck, S. Becker, P. Grohs, N. Jaafari, and A. Jentzen. Solving the Kolmogorov PDE by Means of Deep Learning. J. Sci. Comput. 88, 73 (2021).
  * [5] J. Berg and K. Nystrom. A unified deep artificial neural network approach to partial differential equations in complex geometries. Neurocomputing 317, 28–41 (2018).
  * [6] J. Berner, P. Grohs and A. Jentzen. Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black–Scholes Partial Differential Equations. SIAM Journal on Mathematics of Data Science 2, 3, 631–657 (2020).
  * [7] J. Berner, P. Grohs and F. Voigtlaender. Training ReLU networks to high uniform accuracy is intractable. ICLR (2023).
  * [8] 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(1):8–45, (2019).
  * [9] Y. Chen and J. W. Wan. Deep neural network framework based on backward stochastic differential equations for pricing and hedging American options in high dimensions. Quantitative Finance, 21:1, 45-67 (2021).
  * [10] C. K. Chui, S.-B. Lin, and D.-X. Zhou. Construction of neural networks for realization of localized deep learning. Frontiers in Applied Mathematics and Statistics, 4, (2018).
  * [11] C. K. Chui, S. B. Lin, and D. X. Zhou. Deep neural networks for rotation-invariance approximation and learning. Anal. Appl., 17: 737-772, (2019).
  * [12] G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signals Syst. 2(4), 303–314, (1989).
  * [13] D. Elbrächter, P. Grohs, A. Jentzen, and C. Schwab. DNN expression rate analysis of high-dimensional PDEs: Application to option pricing. Constr Approx 55, 3–71 (2022).
  * [14] N. Golowich, A. Rakhlin and O. Shamir. Size-Independent Sample Complexity of Neural Networks. Proceedings of the 31st Conference On Learning Theory, PMLR 75:297-299, (2018).
  * [15] L. Gonon, P. Grohs, A. Jentzen, D. Kofler and D. Šiška. Uniform error estimates for artificial neural network approximations for heat equations. IMA J. Numer. Anal., 42, 3, 1991–2054 (2022).
  * [16] R. Gribonval, G. Kutyniok, M. Nielsen, and F. Voigtlaender.  Approximation spaces of deep neural networks. Constr. Approx., 55, 259–367 (2022).
  * [17] P. Grohs and L. Herrmann. Deep neural network approximation for high-dimensional elliptic PDEs with boundary conditions. IMA J. Numer. Anal., 42, 3, 2055–2082 (2022).
  * [18] P. Grohs, F. Hornung, A. Jentzen and P. Zimmermann. Space-time error estimates for deep neural network approximations for differential equations. Adv Comput Math 49, 4 (2023).
  * [19] P. Grohs, D. Perekrestenko, D. Elbrächter, and H. Bölcskei. Deep neural network approximation theory. IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 67, NO. 5, MAY (2021).
  * [20] P. Grohs and F. Voigtlaender. Proof of the Theory-to-Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces. Found. Comput. Math. (2023).
  * [21] J. Hana, A. Jentzenb and W. E Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115 (34):8505-8510, (2018).
  * [22] S. Heinrich. Random approximation in numerical analysis. In Functional analysis (Essen, 1991), volume 150 of Lecture Notes in Pure and Appl. Math., 123-171. Dekker, New York, (1994).
  * [23] K. Hornik. Approximation capabilities of multilayer feedforward networks. Neural Netw. 4(2), 251–257 (1991).
  * [24] K. Hornik, M. Stinchcombe and H. White. Multilayer feedforward networks are universal approximators. Neural Netw. 2(5), 359–366 (1989).
  * [25] G. Kutyniok, P. Petersen, M. Raslan and R. Schneider. A theoretical analysis of deep neural networks and parametric pdes. Constr. Approx., 55, 73–125 (2022).
  * [26] M. Magill, F. Qureshi and H. W. de Haan. Neural networks trained to solve differential equations learn general representations. In Advances in Neural Information Processing Systems, 4071–4081 (2018).
  * [27] J. Opschoor, P. Petersen, and C. Schwab,  Deep ReLU networks and high-order finite element methods.  SAM, ETH Zürich, (2019).
  * [28] P. Petersen and F. Voigtländer.  Optimal approximation of piecewise smooth functions using deep ReLU neural networks.  Neural Networks, 108:296–330, (2018).
  * [29] M. M. Rao and Z. D. Ren. Theory of Orlicz spaces, volume 146 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York, (1991).
  * [30] D. Yarotsky.  Error bounds for approximations with deep ReLU networks.  Neural Networks, 94:103–114, (2017).
  * [31] X. Zhang, Y. Yu, L. Wang and Q. Gu. Learning One-hidden-layer ReLU Networks via Gradient Descent Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1524-1534 (2019).

##  Appendix A Appendix: Proof of Lemma 2.3

######  Lemma A.1.

Let $\widetilde{\boldsymbol{\ell}}(n):=\min\\{\boldsymbol{\ell}(n),n\\}$, for
any $n\in\mathbb{N}_{\geq 2}$, it follows that

$\displaystyle\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$
$\displaystyle=\Sigma^{\tilde{\boldsymbol{\ell}},\boldsymbol{c},\varrho_{2}}_{n}$
(A.1) furthermore, if the realization is bounded in $[-1,1]$, we get
$\displaystyle\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}+\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$
$\displaystyle\subset\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{9n},$
(A.2)

###### Proof.

We start by showing that
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}=\Sigma^{\tilde{\boldsymbol{\ell}},\boldsymbol{c},\varrho_{2}}_{n}$.
If $\widetilde{\boldsymbol{\ell}}(n)=\boldsymbol{\ell}(n)$ then the result is
trivial. Hence, let $n\in\mathbb{N}$ be fixed, then trough an induction
argument on $\ell\in\mathbb{N}_{\geq n}$ in order to show that
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}\subset\Sigma^{n,\boldsymbol{c},\varrho_{2}}_{n}$.
The case where $\ell=n$ is straightforward therefore it implies the first step
in the induction. Hence, we assume that
$\Sigma^{{\ell},\boldsymbol{c},\varrho_{2}}_{n}\subset\Sigma^{n,\boldsymbol{c},\varrho_{2}}_{n}$
for some $\ell\in\mathbb{N}_{\geq n}$. Let $\Phi$ be a network architecture
such that $\|\Phi\|_{\mathcal{NN}}\leq\boldsymbol{c}(n)$, $W(\Phi)\leq n$ and
$L(\Phi)\leq\ell+1$, hence
$R_{\varrho_{2}}\Phi\in\Sigma^{\ell+1,\boldsymbol{c},\varrho_{2}}_{n}$. In
view of the induction process, if $L(\Phi)\leq\ell$, it follows that
$R_{\varrho_{2}}\Phi\in\Sigma^{\ell,\boldsymbol{c},\varrho_{2}}_{n}\subset\Sigma^{n,\boldsymbol{c},\varrho_{2}}_{n}$.
Consequently, let $L(\Phi)=\ell+1$ hence
$\Phi=\big{(}(A_{1},b_{1}),\dots,(A_{\ell+1},b_{\ell+1})\big{)}$ where
$b_{j}\in\mathbb{R}^{N_{j}}$ and $A_{j}\in\mathbb{R}^{N_{j}\times N_{j-1}}$,
$j\in\\{1,\dots,\ell+1\\}$. Since
$W(\Phi)=\sum_{j=1}^{\ell+1}\bigl{(}\|A_{j}\|_{\ell^{0}}+\|b_{j}\|_{\ell^{0}}\bigr{)}\leq
n$ and that
$n+1\leq\ell+1\leq\sum_{j=1}^{\ell+1}\bigl{(}\|A_{j}\|_{\ell^{0}}+\|b_{j}\|_{\ell^{0}}\bigr{)}$
it follows that $n+1\leq n$. Hence for some $j_{0}\in\\{1,\dots,\ell+1\\}$, we
have $A_{j_{0}}=0_{\mathbb{R}^{N_{j_{0}}\times N_{{j_{0}}-1}}}$ and
$b_{j_{0}}=0_{\mathbb{R}^{N_{j_{0}}}}$. If $j=\ell+1$, then
$R_{\varrho_{2}}\Phi\equiv 0\in\Sigma^{n,\boldsymbol{c},\varrho_{2}}_{n}.$
Now, we assume that ${j_{0}}\leq\ell$ and we let

$\Phi_{j_{0}}:=\big{(}(0_{N_{{j_{0}}+1}\times
d},b_{{j_{0}}+1}),(A_{{j_{0}}+2},b_{{j_{0}}+2}),\dots,(A_{\ell+1},b_{\ell+1})\big{)}.$

The fact that $\varrho_{2}(0)=0$ and that
$(A_{j_{0}},b_{j_{0}})=(0_{\mathbb{R}^{N_{j_{0}}\times
N_{{j_{0}}-1}}},0_{\mathbb{R}^{N_{j_{0}}}})$ imply that
$R_{\varrho_{2}}{\Phi_{j_{0}}}=R_{\varrho_{2}}\Phi$. Furthermore, we have
$\|{{\Phi_{j_{0}}}}\|_{\mathcal{NN}}\leq\|{\Phi}\|_{\mathcal{NN}}\leq\boldsymbol{c}(n)$,
$W({\Phi_{j_{0}}})\leq W(\Phi)\leq n$ and $L({\Phi_{j_{0}}})\leq\ell-
j_{0}+1\leq\ell$, this implies
$R_{\varrho_{2}}\Phi\in\Sigma^{\ell,\boldsymbol{c},\varrho_{2}}_{n}\subset\Sigma^{n,\boldsymbol{c},\varrho_{2}}_{n}$,
where the last inclusion holds by induction. Then, we get
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}\subset\Sigma^{\tilde{\boldsymbol{\ell}},\boldsymbol{c},\varrho_{2}}_{n}$.
Now it remains to show that
$\Sigma^{\tilde{\boldsymbol{\ell}},\boldsymbol{c},\varrho_{2}}_{n}\subset\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}$.
This step is trivial since if
$R_{\varrho_{2}}\Phi\in\Sigma^{\tilde{\boldsymbol{\ell}},\boldsymbol{c},\varrho_{2}}_{n}$
it implies that for the network $\Phi$ we have $W(\Phi)\leq n$,
$\|{\Phi}\|_{\mathcal{NN}}\leq\boldsymbol{c}(n)$ and
$L(\Phi)\leq\tilde{\boldsymbol{\ell}}=\min\\{n,\boldsymbol{\ell}(n)\\}\leq\boldsymbol{\ell}(n),$
hence the result follows. All in all, we have
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}=\Sigma^{\tilde{\boldsymbol{\ell}},\boldsymbol{c},\varrho_{2}}_{n}$.

Now we are concerned with the second result of the lemma That is, we will show
that
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}+\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}\subset\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{9n}$.
For that aim, we let
$R_{\varrho_{2}}\Phi^{1},R_{\varrho_{2}}\Phi^{2}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}=\Sigma^{\min\\{n,\boldsymbol{\ell}\\},\boldsymbol{c},\varrho_{2}}_{n}$
(from (A.1)) hence both networks $\Phi^{1},\Phi^{2}$ satisfy

$\displaystyle W(\Phi^{1}),\;W(\Phi^{2})$ $\displaystyle\leq n$
$\displaystyle\|{\Phi^{1}}\|_{\mathcal{NN}},\;\|{\Phi^{2}}\|_{\mathcal{NN}}$
$\displaystyle\leq\boldsymbol{c}(n)$ and $\displaystyle
L(\Phi^{1}),\;L(\Phi^{2})$
$\displaystyle\leq\min\\{n,\boldsymbol{\ell}(n)\\},$

Without loss of generality, we can assume that $k:=L(\Phi^{1})$ and
$\ell:=L(\Phi^{2})$ such that $k\leq\ell$. Let

$\displaystyle\Phi^{1}$
$\displaystyle=\big{(}(A_{1}^{1},b_{1}^{1}),\dots,(A_{k}^{1},b_{k}^{1})\big{)}$
and $\displaystyle\Phi^{2}$
$\displaystyle=\big{(}(A_{1}^{2},b_{1}^{2}),\dots,(A_{\ell}^{2},b_{\ell}^{2})\big{)},$

such that $A_{i}^{1}\in\mathbb{R}^{N^{1}_{i}\times N^{1}_{i-1}}$
$A_{j}^{2}\in\mathbb{R}^{N^{2}_{j}\times N^{2}_{j-1}}$ and
$b_{i}^{1}\in\mathbb{R}^{N^{1}_{i}}$ and $b_{j}^{2}\in\mathbb{R}^{N^{2}_{j}}$,
$i\in\\{1,\dots,k\\}$ and $j\in\\{1,\dots,\ell\\}$ where
$N_{0}^{1}=N_{0}^{2}=d$ and $N_{k}^{1}=N_{\ell}^{2}=1$.

In order to sum up the two realizations $R_{\varrho_{2}}\Phi^{1}$ and
$R_{\varrho_{2}}\Phi^{2}$ first we need to parallelize them. Hence they need
to have the same number of layers. Consequently, we define
${\Phi^{e}}:=\Phi^{1}$ if $k=\ell$. If otherwise $k<\ell$, we let

$\Gamma:=\big{(}\tfrac{1}{4}\left(\begin{smallmatrix}1&-1\\\
-1&1\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
1\end{smallmatrix}\right)\big{)},\quad\Lambda:=\big{(}\tfrac{1}{4}(1,-1),0\big{)}$

and since $A_{k}\in\mathbb{R}^{1\times N_{k-1}}$ and $b_{k}\in\mathbb{R}^{1}$
we define

$\tilde{\Phi}^{1}\\!:=\\!\\!\bigg{(}(A_{1}^{1},b_{1}^{1}),\dots,(A_{k-2}^{1},b_{k-2}^{1}),\left(\left(\begin{smallmatrix}A_{k-1}^{1}\\\
0_{\mathbb{R}^{N_{k-2}}}\end{smallmatrix}\right),\left(\begin{smallmatrix}b_{k-1}^{1}\\\
1\end{smallmatrix}\right)\right),\left(\left(\begin{smallmatrix}A_{k}^{1},&1\\\
-A_{k}^{1},&1\end{smallmatrix}\right),\left(\begin{smallmatrix}b_{k}^{1}\\\
-b_{k}^{1}\end{smallmatrix}\right)\right),\Gamma,\dots,\Gamma,\Lambda\\!\bigg{)},$

where $\Gamma$ appears $\ell-k-1$ times, so that $L(\tilde{\Phi}^{1})=\ell$.
Where we use the fact that the realization $R_{\varrho_{2}}\Phi^{1}(x)$ is
bounded in $[-1,1]$ for any given date $x$. Hence
$R_{\varrho_{2}}\Gamma:[-1,1]^{2}\rightarrow[-1,1]^{2}$ represents the
identity in dimension $2$, that is

$R_{\varrho_{2}}\Gamma\left(\varrho_{2}\binom{R_{\varrho_{2}}\Phi^{1}(x)+1}{-R_{\varrho_{2}}\Phi^{1}(x)+1}\right)=\binom{R_{\varrho_{2}}\Phi^{1}(x)+1}{-R_{\varrho_{2}}\Phi^{1}(x)+1}.$

Hence the $j$-fold composition of $\Gamma$ is defined as
$\Gamma^{j}=\Big{(}\underbrace{\Gamma,\dots,\Gamma}_{j\text{ times}}\Big{)}$
hence the realization

$R_{\varrho_{2}}\Gamma^{j}\left(\varrho_{2}\binom{R_{\varrho_{2}}\Phi^{1}(x)+1}{-R_{\varrho_{2}}\Phi^{1}(x)+1}\right)=\binom{R_{\varrho_{2}}\Phi^{1}(x)+1}{-R_{\varrho_{2}}\Phi^{1}(x)+1}.$

Then, we have

$R_{\varrho_{2}}\Lambda\left(\varrho_{2}\binom{R_{\varrho_{2}}\Phi^{1}(x)+1}{-R_{\varrho_{2}}\Phi^{1}(x)+1}\right)=R_{\varrho_{2}}\Phi^{1}(x).$

In conclusion, we get
$R_{\varrho_{2}}\tilde{\Phi}^{1}=R_{\varrho_{2}}\Phi^{1}$, such that
$\|{\tilde{\Phi}^{1}}\|_{\mathcal{NN}}\leq\boldsymbol{c}(n)$ and
$W({\tilde{\Phi}^{1}})\leq 2W(\Phi^{1})+6(\ell-k-1)+2\leq 8n$.

We write
$\tilde{\Phi}^{1}=\big{(}(\tilde{A}_{1}^{1},\tilde{b}_{1}^{1}),\dots,(\tilde{A}_{\ell}^{1},\tilde{A}_{\ell}^{1})\big{)}$
such that
$\tilde{A}^{1}_{j}\in\mathbb{R}^{\tilde{N}_{j}\times\tilde{N}_{j-1}}$ and
$\tilde{b}^{1}_{j}\in\mathbb{R}^{\tilde{N}_{j}}$, $j\in\\{1,\dots,\ell\\}$
where $\tilde{N}_{0}=d$ and $\tilde{N}_{\ell}=1$. We define

$\Psi:=\Big{(}\Theta_{1},\dots,\Theta_{\ell-1},\big{(}(\tilde{A}^{1}_{\ell}\mid
A^{2}_{\ell}),\tilde{b}^{1}_{\ell}+b^{2}_{\ell}\big{)}\Big{)},$

where

$\Theta_{1}:=\left(\left(\begin{smallmatrix}\tilde{A}^{1}_{1}\\\
A_{1}^{2}\end{smallmatrix}\right),\left(\begin{smallmatrix}\tilde{b}^{1}_{1}\\\
b_{1}^{2}\end{smallmatrix}\right)\right)\text{and}\quad\Theta_{m}:=\left(\left(\begin{smallmatrix}\tilde{A}^{1}_{m}&0\\\
0&A_{m}^{2}\end{smallmatrix}\right),\left(\begin{smallmatrix}c_{m}\vphantom{\tilde{A}^{1}_{m}}\\\
e_{m}\vphantom{A_{m}^{2}}\end{smallmatrix}\right)\right)\text{for
}m\in\\{2,\dots,\ell-1\\}.$

We conclude that
$R_{\varrho_{2}}\Psi=R_{\varrho_{2}}\tilde{\Phi}^{1}+R_{\varrho_{2}}\Phi^{2}$.

Moreover, we have

$\displaystyle W(\Psi)$ $\displaystyle\leq
W(\widetilde{\Phi}^{1})+W(\Phi^{2})\leq 9n$
$\displaystyle\|{\Psi}\|_{\mathcal{NN}}$
$\displaystyle\leq\boldsymbol{c}(n)\leq\boldsymbol{c}(9n),$ $\displaystyle
L(\Psi)$
$\displaystyle=\ell\leq\boldsymbol{\ell}(n)\leq\boldsymbol{\ell}(9n),$

Where we used the fact that $\boldsymbol{\ell}$ and $\boldsymbol{c}$ are non-
decreasing and that $\ell\leq n$. All in all, it follows that
$\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}+\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{n}\in\Sigma^{\boldsymbol{\ell},\boldsymbol{c},\varrho_{2}}_{9n}$,
which conclude the lemma.

∎

###### Proof of Lemma 2.3.

The proof follows from Lemma A.1 and similar arguments as in the proof of [20,
Lemma 2.1]. The details are left for interesting reader to check. ∎