#  Approximation Error and Complexity Bounds for ReLU Networks
on Low-Regular Function Spaces

Owen Davis corresponding author<EMAIL_ADDRESS><EMAIL_ADDRESS>2738
Hyder Ave SE, Albuquerque, NM, USA 81706 Department of Mathematics and
Statistics, The University of New Mexico, Albuquerque, NM, USA  Sandia
National Laboratories Department of Optimization and Uncertainty
Quantification, Albuquerque, NM, USA  Gianluca Geraci<EMAIL_ADDRESS>Sandia National Laboratories Department of Optimization and Uncertainty
Quantification, Albuquerque, NM, USA  Mohammad Motamed<EMAIL_ADDRESS>Department of Mathematics and Statistics, The University of New Mexico,
Albuquerque, NM, USA

###### Abstract

In this work, we consider the approximation of a large class of bounded
functions, with minimal regularity assumptions, by ReLU neural networks. We
show that the approximation error can be bounded from above by a quantity
proportional to the uniform norm of the target function and inversely
proportional to the product of network width and depth. We inherit this
approximation error bound from Fourier features residual networks, a type of
neural network that uses complex exponential activation functions. Our proof
is constructive and proceeds by conducting a careful complexity analysis
associated with the approximation of a Fourier features residual network by a
ReLU network.

keywords: ReLU neural networks, Fourier features neural networks, error
bounds, complexity bounds, constructive approximation

MSC subject classification: 41A25, 41A30, 41A46, 68T07

##  1 Introduction

Over the past couple decades, the study of approximation error in deep
feedforward neural networks has been an active area of research due to their
empirically observed success in approximating a large class of target
functions of varying regularity and dimension; see e.g.,[13]. Early research
into neural network approximation capability [3, 11, 14, 17, 2] resulted in
universal approximation theorems that showed the existence of neural networks
that approximate target functions in various function spaces to any desired
accuracy. For example, in [3] and [11] it was shown that feedforward networks
with sigmoid activation are universal approximators of respectively continuous
and Borel measurable functions defined on compact finite dimensional sets.
Furthermore, in [17] it was shown that the universal approximation of
continuous functions by feedforward networks is equivalent to the use of a
non-polynomial activation function.

Results such as these are foundational in justifying the use of deep neural
networks for function approximation tasks, but they do not provide insight
into the rate of approximation with respect to variables such as the
complexity of the network (width and depth), the regularity and dimension of
the target function, and the size of the target function measured in some
proper norm. Some of the first work of this kind includes [2], where it was
shown that for feedfoward networks with sigmoid activation targeting functions
belonging to Barron space, the approximation error is inversely proportional
to the network degree of freedom and proportional to the Barron norm of the
target function. Additional results concerning the approximation of target
functions belonging to Barron space were obtained for general activation
functions in [20].

Much of the contemporary work; see e.g., [24, 16, 18, 19, 21], focuses on
neural networks using the ReLU activation function due to their empirically
observed success in real world applications [13] and their theoretical
advantage over other conventional forms of non-linear approximation such as
free knot linear splines [4, 15, 1]. Moreover, many of these contemporary
results are concerned with the derivation of optimal approximation rates in
the limit of infinite training data as a function of network complexity,
target function size, and regularity. For example, in [24], optimal
approximation rates are derived for continuous functions that depend on the
modulus of continuity of the target function and the complexity of the
approximating network. Similar results are derived for piecewise smooth target
functions in [16] and Hölder continuous target functions in [18]. Moreover,
optimal approximation rates for target functions belonging to Sobolev spaces
which depend on the Sobolev norm of the target function and the complexity of
the approximating network are derived in [19, 23].

In the present work, we further study the approximation properties of ReLU
networks, but we depart from contemporary works on ReLU networks by focusing
on a large class of target functions with minimal regularity assumptions.
Precisely, we consider target functions belonging to

$S=\\{f:\Theta=[0,1]^{d}\mapsto\mathbb{R}:||f||_{L^{\infty}(\Theta)}\leq||\hat{f}||_{L^{1}(\mathbb{R}^{d})}<\infty\\},$
(1)

where $\hat{f}$ is the Fourier transform of $f$. The condition
$||\hat{f}||_{L^{1}(\mathbb{R}^{d})}<\infty$ guarantees that the target
function has an integrable Fourier transform. Furthermore, the inequality
$||f||_{L^{\infty}(\Theta)}\leq||\hat{f}||_{L^{1}(\mathbb{R}^{d})}$ is always
true following from Holder’s inequality and the definition of the Fourier
transform,

$||f||_{L^{\infty}(\Theta)}=\bigg{|}\bigg{|}\int_{\mathbb{R}^{d}}\hat{f}(\bm{\omega})e^{i2\pi\bm{\omega}\cdot\bm{\theta}}\>d\bm{\omega}\bigg{|}\bigg{|}_{L^{\infty}(\Theta)}\leq\int_{\mathbb{R}^{d}}|\hat{f}(\bm{\omega})|\>d\bm{\omega}=||\hat{f}||_{L^{1}(\mathbb{R}^{d})}.$

Overall, the space $S$ can be described as real scalar valued functions
defined on the compact set $\Theta$ that have absolutely integrable Fourier
transform. Importantly, functions in $S$ do not need to be continuous
everywhere; they rather need to be continuous almost everywhere, and there is
no requirement of differetiability. Hence, we may view $S$ as a low-regular
function space, relaxing the classical regularity assumptions. As an
illustrative example of a function belonging to $S$, consider the regularized
sine discontinuity pictured in Figure 1 and defined by

$f(\theta)=\text{Si}\left(\frac{\theta-0.5}{10^{-2}}\right)e^{-(\theta-0.5)^{2}/2},\qquad\theta\in[0,1],\qquad\text{Si}(x)=\int_{0}^{x}\frac{\sin(t)}{t}\>dt.$
(2)

Figure 1: An example of a target function in $S$

.

The novel contributions of this work are twofold.

  1. 1.

We constructively derive both complexity and approximation error estimates for
ReLU networks approximating target functions belonging to $S$ as defined in
(1). Specifically, we show that the approximation error is proportional to the
uniform norm of the target function and inversely proportional to the product
of network width and depth. To the best of the authors’ knowledge, this
approximation error estimate is unique in relating approximation error
directly to the uniform norm of the target function, and in simultaneously
applying to such a large class of low-regular, bounded functions. This task
relies on conducting careful complexity analyses associated with forming
linear combinations and compositions of ReLU networks using both standard and
residual network type architectures [10]. For this we borrow strategies from
both [6] and [4]. In particular, the latter work introduces _special ReLU
networks_ that are theoretically useful in combining and composing standard
ReLU networks taking one-dimensional input in $[0,1]$.

  2. 2.

We extend this concept of special ReLU networks to accommodate multi-
dimensional inputs, and we additionally introduce a generalization of special
ReLU networks that facilitates recursive network linear combination and
composition, which will be necessary to prove our main theoretical results.

It is to be noted that the present work is motivated by [12], where target
functions belonging to the same space $S$ are approximated by neural networks
with a non-ReLU activation, referred to as Fourier feature activation; see
Section 4.1 for a rigorous definition of Fourier feature networks. Our
constructive proof is indeed based on approximating a Fourier feature network
by a ReLU network, followed by conducting a careful error-complexity analysis
of the approximation. We also refer the readers to [5], where the derived
estimates are exploited and combined with residual modeling to build a ReLU
network based multifidelity modeling paradigm.

The rest of the paper proceeds as follows. In Section 2, we define ReLU
networks and set the notation that will be used throughout the paper. In
Section 3, we state and discuss our main theoretical results. In Section 4, we
begin by introducing all mathematical tools that will be used in proving our
main theoretical results, which includes our generalization of special ReLU
networks and a series of lemmas on ReLU network composition and linear
combination. We then leverage the developed tools to prove our main
theoretical results in Section 5. Concluding remarks and directions for future
work can then be found in Section 6.

##  2 ReLU networks

We start with defining the type of ReLU networks that we consider in this
work. We follow notation conventions closely related to [4] and depart from
this only when necessary.

For any $m\in\mathbb{N}$ we define the ReLU activation function
$\sigma:\mathbb{R}^{m}\mapsto\mathbb{R}^{m}$ by

$\sigma(\bm{x})=(\max\\{0,x^{(1)}\\},\dotsc,\max\\{0,x^{(m)}\\}),\qquad\bm{x}=(x^{(1)},\dotsc,x^{(m)})\in\mathbb{R}^{m},$
(3)

where $\bm{x}$ represents a generic $m$-dimensional input. Then for any
$d\in\mathbb{N}$ and $D_{1},D_{2}\in\mathbb{R}$ with $D_{1}<D_{2}$, we
consider feedforward ReLU networks defined on the hypercube
$[D_{1},D_{2}]^{d}\subset\mathbb{R}^{d}$ with $d$ input neurons, one output
neuron, a fixed width $W\in\mathbb{N}$, and fixed depth $L\in\mathbb{N}$. The
depth here refers to the number of hidden layers (excluding the input and
output layers), and the width refers to the number of neurons in each hidden
layer. The ReLU activation function as defined in Equation (3) is applied to
all neurons in each hidden layer, and no activation function will be applied
on the output neuron. Such a network is uniquely represented by a collection
of $L+1$ weight matrices and bias vectors (or a set of matrix-vector tuples),

$\Psi:=\\{(M^{(0)},\bm{b}^{(0)}),(M^{(1)},\bm{b}^{(1)}),\dotsc,(M^{(L)},b^{(L)})\\}\in{\mathbb{R}}^{(L-1)W^{2}+(d+1)W}\times{\mathbb{R}}^{LW+1},$

where

$M^{(0)}\in{\mathbb{R}}^{W\times d},\qquad
M^{(1)},\dotsc,M^{(L-1)}\in{\mathbb{R}}^{W\times W},\qquad
M^{(L)}\in{\mathbb{R}}^{1\times W},$

and

$\qquad\bm{b}^{(0)},\dotsc,\bm{b}^{(L-1)}\in{\mathbb{R}}^{W\times 1},\qquad
b^{(L)}\in{\mathbb{R}}.$

We denote by $f_{\Psi}$ the real-valued function that the network $\Psi$
realizes,

$f_{\Psi}(\bm{\theta})=A^{(L)}\circ\sigma\circ
A^{(L-1)}\circ\dotsc\circ\sigma\circ
A^{(0)}(\bm{\theta}),\qquad\bm{\theta}\in[D_{1},D_{2}]^{d},$

with affine maps (i.e., a map formed by a linear transformation followed by a
translation),

$A^{(\ell)}(\bm{x})=M^{(\ell)}\bm{x}+\bm{b}^{(\ell)},\qquad\ell=0,1,\dotsc,L.$

Here $\bm{x}$ denotes a generic output vector from a hidden layer.

Figure 2: ReLU network $\Psi=\\{(M^{(\ell)},\bm{b}^{(\ell))}\\}_{\ell=0}^{3}$
realizing a function $f_{\Psi}\in\mathcal{N}^{D_{1},D_{2},1}_{3,3}$

Overall, we denote by ${\mathcal{N}}^{D_{1},D_{2},d}_{W,L}$ the set of all
functions generated by standard uniform-width ReLU networks, i.e., functions
produced by all possible choices of weights and biases,

${\mathcal{N}}^{D_{1},D_{2},d}_{W,L}=\\{f_{\Psi}:[D_{1},D_{2}]^{d}\mapsto{\mathbb{R}},\
\Psi\in{\mathbb{R}}^{(L-1)W^{2}+(d+1)W}\times{\mathbb{R}}^{LW+1}\\}.$ (4)

To fully clarify the notation we provide an example of a ReLU network
$\Psi=\\{(M^{(\ell)},\bm{b}^{(\ell))}\\}_{\ell=0}^{3}$ realizing a function
$f_{\Psi}\in\mathcal{N}^{D_{1},D_{2},1}_{3,3}$ in Figure 2.

######  Remark 2.1.

In this work, we always consider the width $W$ to be fixed across all layers.
This assumption helps considerably to de-clutter the analysis associated with
neural network based constructive approximation, and is standard across the
neural network approximation theory literature. Moreover, the assumption is
not restrictive. Any neural network can be modified to have fixed width
without changing its output. Conservatively, the width of all layers can be
increased to that of the maximum width layer in the network by adding an
appropriate number of _dead neurons_ to the deficient hidden layers. Here dead
neurons are those with bias zero and with incoming and/or outgoing weights
also equal to zero.

##  3 Main theoretical results and discussion

In this section, we state and discuss our main theoretical results for ReLU
networks.

###  3.1 Main theorems

######  Theorem 1 (Main Complexity Result).

Consider a target function $f\in S$ as defined in (1). Then for any
$\varepsilon_{\text{TOL}}\in(0,1/2)$ there exists a ReLU network $\Psi$
realizing the function $f_{\Psi}\in\mathcal{N}^{0,1,d}_{W,L}$ with $L\geq 2$,
$W\geq 2d+2$, and satisfying

$||f-f_{\Psi}||_{L^{2}(\Theta)}\leq\varepsilon_{\text{TOL}}.$ (5)

Moreover, there exists a constant $C>0$ such that

$WL\leq
Cd\frac{||f||^{2}_{L^{\infty}(\Theta)}}{\varepsilon^{2}_{\text{TOL}}}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R}^{d})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2}\log_{2}^{2}(\varepsilon_{\text{TOL}}^{-1}).$
(6)

######  Remark 3.1.

The architecture bounds $L\geq 2$ and $W\geq 2d+2$ in Theorem 1 are the result
of our proof strategy, which involves a constructive approximation of a
Fourier features residual network by a ReLU network. We remark here that the
linear dependence of $W$ on the target function input dimension $d$ is
expected and required for finite width ReLU network approximation results.
Indeed it was shown in shown in [9] that universal approximation of continuous
functions by ReLU networks of finite width requires that width be strictly
greater than input dimension.

Given the complexity result in Thoerem 1 we can immediately prove the
following theorem concerning ReLU network approximation error.

######  Theorem 2 (Main approximation error result).

Consider a target function $f\in S$ as defined in (1). Then there exists a
constant $C>0$ such that the error
$\varepsilon:=||f-f_{\Psi}||_{L^{2}(\Theta)}<1/2$ in the approximation of $f$
by a ReLU network $f_{\Psi}\in\mathcal{N}^{0,1,d}_{W,L}$ with $L\geq 2$ and
$W\geq 2d+2$ satisfies

$\varepsilon^{2+\alpha(\varepsilon)}\leq
Cd\frac{||f||^{2}_{L^{\infty}(\Theta)}}{WL}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R}^{d})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2},$
(7)

where
$\alpha(\varepsilon)=(-\log_{2}(\log_{2}^{2}(\varepsilon^{-1})))/\log_{2}(\varepsilon)$.
Additionally, as $\varepsilon\to 0^{+}$ we have

$\varepsilon^{2}\leq
Cd\frac{||f||^{2}_{L^{\infty}(\Theta)}}{WL}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R}^{d})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2}.$

###### Proof.

The proof is a direct consequence of the main complexity result, so we present
it here. From Theorem 1, we know that for any
$\varepsilon_{\text{TOL}}\in(0,1/2)$ there exists a ReLU network $\Psi$
realizing the function $f_{\Psi}\in\mathcal{N}^{0,1,d}_{W,L}$ such that

$\varepsilon:=||f-f_{\Psi}||_{L^{2}(\Theta)}\leq\varepsilon_{\text{TOL}},$ (8)

and that the complexity of this network satisfies (6) for some $C>0$. Assuming
equality in (8) and rearranging (6) we find

$\frac{\varepsilon^{2}}{\log_{2}^{2}(\varepsilon^{-1})}\leq
Cd\frac{||f||^{2}_{L^{\infty}(\Theta)}}{WL}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R}^{d})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2}.$

Now we solve the inequality
$\varepsilon^{2+\alpha}\leq\frac{\varepsilon^{2}}{\log_{2}^{2}(\varepsilon^{-1})}$
and find

$\alpha(\varepsilon)\geq\frac{-\log_{2}(\log_{2}^{2}(\varepsilon^{-1}))}{\log_{2}(\varepsilon)}.$
(9)

Taking equality in (9), a straightforward limit calculation shows
$\lim_{\varepsilon\to 0^{+}}(\alpha(\varepsilon))=0$. ∎

###  3.2 Discussion

Both Theorem 1 and Theorem 2 tell a similar story concerning the interplay
between ReLU network approximation error and complexity, so without loss of
generality we focus this discussion on main approximation error result in
Theorem 2.

The estimate (7) shows that for ReLU networks of uniform width approximating a
target function $f\in S$, the approximation error can be bounded above by a
quantity proportional to $d||f||^{2}_{L^{\infty}(\Theta)}$ and inversely
proportional to $WL$. Moreover, as shown in Section 5, the constant of
proportionality $C$ is a function of

$\max\\{\log_{2}(\omega_{max}+\pi/2),\log_{2}(\omega_{max}||f||_{L^{\infty}}+\pi/2)\\},$

where $\omega_{max}$ is the largest frequency present in the target function.
Although this could make $C$ infinite, we note that the set

$S_{c}:=\\{f\in S:\hat{f}\text{ has compact support}\\}$

is dense in the set $S$ with respect to the $L^{p}$ norm for any $1\leq
p<\infty$. The proof for this relies on convolution properties of the Fourier
transform and approximate identities, and can be found in full detail in
Appendix B. Importantly, since target functions in $S$ can be discontinuous,
we cannot recover density with respect to $L^{\infty}$, and we cannot expect
functions in $S_{c}$ to uniformly approximate functions in $S$. This is in no
conflict with the estimate (7) which considers approximation error in the
$L^{2}$ norm, but we highlight it here for practitioners, and we remark that
pointwise behavior cannot be inferred directly from the estimate (7). Overall,
given the density of $S_{c}$ in $S$ we we may simultaneously assume
$\omega_{max}<\infty$ (and hence $C<\infty$) and still approximate target
functions in $S$ to any chosen tolerance with respect to the $L^{p}$ norm for
any $1\leq p<\infty$.

Additionally, the constant $C$ scales weakly with the target function
regularity. Precisely, the Fourier transform of a function $f$ with integrable
partial derivatives of order up to $m$ decays like
$|\hat{f}|\sim\mathcal{O}(|\bm{\omega}|^{-m})$ [8]. Further results relating
function regularity to the decay of its Fourier transform are available, and
we direct the reader to [8] for a comprehensive discussion. Overall,
approximating target functions of lower regularity will generally require
larger frequencies and vice versa. Importantly, $\omega_{max}$ could still be
very large for functions of high regularity, but with isolated high-frequency
content; for example, any single high-frequency sinusoid is infinitely
differentiable, but will still have a large maximum frequency.

We note here as well that the the value $\alpha(\varepsilon)$ required to
prove the estimate (7) over the full error tolerance range $(0,1/2)$ is
$\alpha(2^{-e})\approx 1.061$. In practice, $\alpha$ depends weakly and
continuously on the desired approximation error, and the conservative choice
$\alpha=1.061$ is only required when (7) needs to hold for larger tolerances.
In Table 1, we provide minimum values $\alpha(\varepsilon)$ for several
benchmark tolerances $\varepsilon$ ranging from $10^{-1}$ to $10^{-10}$.

$\varepsilon$ | $10^{-1}$ | $10^{-2}$ | $10^{-3}$ | $10^{-4}$ | $10^{-5}$ | $10^{-6}$ | $10^{-7}$ | $10^{-8}$ | $10^{-9}$ | $10^{-10}$
---|---|---|---|---|---|---|---|---|---|---
$\alpha(\varepsilon)$ | $1.043$ | $0.823$ | $0.667$ | $0.562$ | $0.489$ | $0.434$ | $0.391$ | $0.357$ | $0.328$ | $0.305$
Table 1: Values $\alpha(\varepsilon)$ for benchmark tolerances $\varepsilon$

Notice that even for moderate tolerances $\alpha(\varepsilon)$ can be chosen
considerably smaller than the maximum value $\alpha=1.061$.

To conclude, we note that the the error bound (7) is likely not sharp for all
target functions. Indeed our proof, see Section 5, leverages the existing
Fourier features residual network estimate (13), which is not sharp for all
target functions [12].

##  4 Background for the proof

In this section, we provide all necessary background to prove our main
theoretical results. We begin in Section 4.1 with the definition of Fourier
features residual networks [12], which to the best of the authors’ knowledge
is the only type of neural network for which there are existing approximation
error estimates in the space $S$. Our overarching proof strategy is then to
conduct a constructive approximation of a Fourier features residual network by
a ReLU network thereby recovering approximation error and complexity estimates
for ReLU networks approximating functions in $S$. To accomplish this, in
Section 4.2, we introduce and extend the neural network constructive
approximation tool known as special ReLU networks first introduced in [4],
which facilitates network linear combination and composition. Finally, in
Section 4.3, we present all foundational lemmas necessary to tackle Theorem 1.
These include a lemma from [6], which shows that a one-dimensional cosine
function can be well approximated by a ReLU network of bounded complexity, and
a series of lemmas which explain how to form linear combinations and
compositions of ReLU networks both directly and through the use of related
special ReLU networks.

###  4.1 Fourier features residual networks

Following [12], for any $m\in\mathbb{N}$ we define the Fourier features
activation function $s:\mathbb{R}^{m}\times\mathbb{R}^{m}\mapsto\mathbb{C}$ by

$s(\bm{\omega},\bm{x})=e^{i\bm{\omega}\cdot\bm{x}},\qquad(\bm{\omega},\bm{x})\in\mathbb{R}^{m}\times\mathbb{R}^{m}.$

Then for any $d\in\mathbb{N}$ and $D_{1},D_{2}\in\mathbb{R}$ with
$D_{1}<D_{2}$, we define a Fourier features residual network $\Phi$ of depth
$L_{FF}\geq 2$ and fixed width $W_{FF}\in\mathbb{N}$ as having $L_{FF}$ hidden
layers, $W_{FF}$ neurons in the first hidden later, $2W_{FF}$ neurons in each
remaining hidden layer, and realizing the function

$f_{\Phi}(\bm{\theta})=\Re\sum_{k=1}^{W_{FF}}b_{0k}\,s(\bm{\omega}_{0k},\bm{\theta})+z_{L_{FF}}(\bm{\theta}),\qquad\bm{\theta}\in[D_{1},D_{2}]^{d},$

where $z_{L_{FF}}$ results from the following recursive scheme:

$z_{1}=0,\qquad
z_{\ell+1}(\bm{\theta})=z_{\ell}(\bm{\theta})+\Re\sum_{k=1}^{W_{FF}}b_{\ell
k}\,s(\bm{\omega}_{\ell k},\bm{\theta})+\Re\sum_{k=1}^{W_{FF}}b_{\ell
k}^{\prime}\,s(\omega_{\ell
k}^{\prime},z_{\ell}(\bm{\theta})),\qquad\ell=1,\dotsc,L_{FF}-1,$

and where for all $\ell=0,\dotsc,L_{FF}-1$, $\bm{\omega}_{\ell
k}\in\mathbb{R}^{W_{FF}}_{\geq 0}$, $\omega_{\ell
k}^{\prime}\in\mathbb{R}_{\geq 0}$ and $b_{\ell k},b_{\ell
k}^{\prime}\in\mathbb{C}$ are respectively frequency and amplitude parameters.
For our purposes it will be useful to introduce a more compact notation and to
express these Fourier features residual networks directly as linear
combinations of cosine and sine functions. To accomplish this we can
equivalently view the network as realizing the function

$f_{\Phi}(\bm{\theta})=\beta_{0}(\bm{\theta})+z_{L_{FF}}(\bm{\theta}),$

where $z_{L_{FF}}$ results from the procedure:

$z_{1}=0,\hskip
14.22636ptz_{\ell+1}(\bm{\theta})=z_{\ell}(\bm{\theta})+\beta_{\ell}(\bm{\theta})+\beta_{\ell}^{\prime}(z_{\ell}(\bm{\theta})),\hskip
14.22636pt\ell=1,\dots,L_{FF}-1,$ (10)

and where

$\displaystyle\beta_{\ell}(\bm{\theta})$
$\displaystyle=\sum_{k=1}^{W_{FF}}\Re(b_{\ell k})\cos(\bm{\omega}_{\ell
k}\cdot\bm{\theta})-\Im(b_{\ell k})\sin(\bm{\omega}_{\ell
k}\cdot\bm{\theta});$ $\displaystyle\beta_{\ell}^{\prime}(\bm{\theta})$
$\displaystyle=\sum_{k=1}^{W_{FF}}\Re(b_{\ell
k}^{\prime})\cos(\bm{\omega}_{\ell k}^{\prime}\cdot\bm{\theta})-\Im(b_{\ell
k}^{\prime})\sin(\bm{\omega}_{\ell k}^{\prime}\cdot\bm{\theta}),$

for $\ell=0,\dotsc,L_{FF}-1$. We make one final simplification by writing
$\beta_{\ell}$ and $\beta_{\ell}^{\prime}$ in terms of only the cosine
function as

$\displaystyle\beta_{\ell}(\bm{\theta})$
$\displaystyle=\sum_{k=1}^{W_{FF}}|b_{\ell k}|\cos\left(\bm{\omega}_{\ell
k}\cdot\bm{\theta}-\tan^{-1}\left(\frac{-\Im(b_{\ell k})}{\Re(b_{\ell
k})}\right)\right);$ (11) $\displaystyle\beta_{\ell}^{\prime}(\bm{\theta})$
$\displaystyle=\sum_{k=1}^{W_{FF}}|b_{\ell
k}^{\prime}|\cos\left(\bm{\omega}^{\prime}_{\ell
k}\cdot\bm{\theta}-\tan^{-1}\left(\frac{-\Im(b_{\ell k}^{\prime})}{\Re(b_{\ell
k}^{\prime})}\right)\right),$ (12)

where $|\cdot|$ is the complex modulus. Finally, to draw a parallel between
Fourier features residual networks and our definition of ReLU networks in
Section 2, we may alternatively represent a Fourier features residual network
by a sequence of frequency-amplitude tuples

$\Phi:=\\{(\bm{\omega}_{0},\bm{b}_{0}),\dotsc,(\bm{\omega}_{L_{FF}-1},\bm{b}_{L_{FF}-1}),(\bm{\omega}^{\prime}_{1},\bm{b}_{1}^{\prime}),\dotsc,(\bm{\omega}_{L_{FF}-1}^{\prime},\bm{b}_{L_{FF}-1}^{\prime})\\},$
$\bm{\omega}_{\ell}\in{\mathbb{R}}_{\geq
0}^{W_{FF}d},\quad\bm{\omega}_{\ell}^{\prime}\in{\mathbb{R}}_{\geq
0}^{W_{FF}},\quad\bm{b}_{\ell},\bm{b}_{\ell}^{\prime}\in{\mathbb{C}}^{W_{FF}}.$

For clarity, in Figure 3 we include a graphical representation of a Fourier
feature residual network with $W_{FF}=1$ and $L_{FF}=2$ approximating a uni-
variate target function $f$.

Figure 3: Graphical representation of Fourier features residual network with
$W_{FF}=1$ and $L_{FF}=3$ approximating a uni-variate target function $f$

In Figure 3, notice the skip-connections that pass along the output of one
hidden layer to the output of the next without any computation. These skip-
connections are characteristic of residual network architectures pioneered in
[10]. They enforce that each layer learns a correction on the previous layer
as opposed to the identity map plus a correction. This has been shown to help
in avoiding stagnating error in training very deep networks. Moreover, notice
that the hidden layers of a Fourier features network are essentially
disconnected aside from these skip-connections. The first layer learns a
$W_{FF}$ term Fourier sum approximation $\beta_{0}$ of the target function
$f$. Next, $z_{L_{FF}}$ approximates $f-\beta_{0}$ by a sequence of $L_{FF}-1$
hidden layers, where each hidden layer learns a correction on the previous
layer. Precisely, $z_{1}=0$, and then each $z_{j}$ for $j=2,\dotsc,L_{FF}$ is
an approximation of $f-\beta_{0}$, but where the learned quantity at layer
$j+1$ is $f-\beta_{0}-z_{j}$.

####  4.1.1 A known theoretical result for Fourier features residual networks

The following was proved in [12].

######  Theorem 3 (Approximation error in Fourier features residual network
[12]).

Let $f\in S$ as defined in (1). Then there exists a Fourier features residual
network $\Phi$ of depth $L_{FF}\geq 2$, width
$W_{FF}=\mathcal{O}(L_{FF}^{2})$, realizing the function $f_{\Phi}$, and
constant $C>0$ such that

$||f-f_{\Phi}||_{L^{2}(\Theta)}^{2}\leq
C\frac{||f||^{2}_{L^{\infty}(\Theta)}}{W_{FF}L_{FF}}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R}^{d})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2}.$
(13)

To the best of the authors’ knowledge, Theorem 3, derived specifically for
Fourier features residual networks, is unique in relating neural network
approximation error to the uniform norm of the target function. The primary
goal of this work is to leverage Theorem 3 to derive a similar result for ReLU
networks, which are commonly used in scientific machine learning applications.

###  4.2 Special ReLU networks

Motivated by [4], we introduce special ReLU networks, which can be considered
a special subset of standard ReLU networks with the same depth, comparable
width, and where special roles are reserved for the top and bottom neurons of
each hidden layer. Specifically, we define four types of channels that appear
in special ReLU networks.

  1. (a)

A _source channel_ formed by the top $d$ neurons in each hidden layer that are
assumed to be ReLU-free with unimodular weights and zero bias. The neurons in
a source channel do not take any input from neurons in other channels and do
not do any computation. This channel simply carries forward the input
$\bm{\theta}$. The blue highlighted neurons in Figure 4 are an example of a
source channel.

  2. (b)

A _collation channel_ formed by the bottom neuron in each hidden layer that
are also assumed to be ReLU-free. This channel is used to collect intermediate
computations, i.e., outputs of hidden layers. The neurons in a collation
channel do not feed into subsequent calculations. They only take outputs of
neurons in previous layers and carry them over with unit weight to subsequent
bottom neurons. An example of a collation channel are the red highlighted
neurons in left network of Figure 4.

  3. (c)

A collation channel akin to channel type (b) but with the added stipulation
that the collected intermediate computations in each of the neurons in the
collation channel can be fed back into the next immediate layer of the
standard computational channel. Note that these outgoing connections from the
collation neurons to the main computational channel are not required to happen
at every layer. An example of such a channel are the red highlighted neurons
in the right network of Figure 4.

  4. (d)

Standard computational channels with ReLU activation. The neurons without
color in Figure 4 are an example of standard computational channels.

We now define two types of special networks:

  * •

Type 1 special ReLU network: a network consisting of channel types (a), (b),
and (d);

  * •

Type 2 special ReLU network: a network consisting of channel types (a), (c),
and (d).

Type 1 special networks taking input in $[0,1]$ were introduced in [4]. A
graphical representation of both type 1 and type 2 networks is displayed in
Figure 4. The difference between type 1 and type 2 special ReLU networks is
that type 2 networks allow the collected intermediate computations in the
neurons of the collation channel to be fed back into the standard
computational channels of the network; this type of channel will be key to
implementing recursive summation and composition of networks which will be
necessary for the proof of Theorem 1. For clarity, the source channel and its
outgoing neuron connections are highlighted in blue, and the collation channel
and its outgoing neuron connections are highlighted in red. In general,
channels of type (b) are a subset of channels of type (c) where weights
emanating from collation neurons back into the computational channels of the
network are zero. Hence type 1 special networks are a subset of type 2 special
networks.

Figure 4: Graph representations of type 1 (left) and type 2 (right) special
ReLU networks in $\tilde{\mathcal{N}}^{D_{1},D_{2},1}_{4,3}$. The source
channels are highlighted in blue while the collation channels are highlighted
in red.

Let $\tilde{\Psi}$ and $f_{\tilde{\Psi}}$ be respectively the set of matrix-
vector tuples and realized function of a special ReLU network. We denote by
$\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,L}$ the set of all functions generated
by special ReLU networks

$\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,L}=\\{f_{\tilde{\Psi}}:\bm{\theta}\in[D_{1},D_{2}]^{d}\rightarrow{\mathbb{R}}\
\ \text{produced by a special network with $W\geq 4$, $L\geq 2$}\\}.$

It is to be noted that since the source and collation channels are ReLU-free,
special networks do not form a direct subset of ReLU networks. However, given
any function $f_{\tilde{\Psi}}\in\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,L}$
corresponding to a special network
$\tilde{\Psi}=\\{\tilde{M}^{(\ell)},\tilde{\bm{b}}^{(\ell)}\\}_{\ell=0}^{L}$,
a standard ReLU network $\Psi$ can be constructed that produces the same
function $f_{\Psi}\equiv f_{\tilde{\Psi}}$, but with,

$f_{\Psi}\in\begin{cases}\mathcal{N}^{D_{1},D_{2},d}_{W+d,L},&\exists\>\bm{\theta}\in[D_{1},D_{2}]^{d}\text{
containing negative components}\\\
\mathcal{N}^{D_{1},D_{2},d}_{W,L},&\text{otherwise}.\end{cases}$

The parameters $\Psi=\\{{M}^{(\ell)},\bm{b}^{(\ell)}\\}_{\ell=0}^{L}$ of such
a standard ReLU network are given in terms of the parameters of the special
network $\tilde{\Psi}$, and depend on whether the special network is type 1 or
type 2 and whether any $\bm{\theta}\in[D_{1},D_{2}]^{d}$ contains negative
components. The interested reader can find the mathematically rigorous
conversions between special and standard networks for each of these cases in
Appendix A.

###  4.3 Foundational Lemmas on ReLU network composition and combination

In this section, we introduce a series of lemmas which show how to form linear
combinations and compositions of ReLU networks both directly and through the
use of related special networks. We finish this section with a Lemma from [6]
which shows that a one dimensional cosine function can be well approximated by
a ReLU network of bounded complexity. To promote readability, the proofs of
the lemmas in this section are relegated to Appendix B.

We begin with Lemma 1, which shows how to form compositions of standard ReLU
networks without the use of special networks.

######  Lemma 1.

For $d\in\mathbb{N}$ and $D^{(j)}_{1},D^{(j)}_{2}\in\mathbb{R}$, with
$D_{1}^{(j)}<D_{2}^{(j)}$, $j=1,\dotsc J$, and

$f_{\Psi_{j}}\in\begin{cases}\mathcal{N}^{D_{1}^{(j)},D_{2}^{(j)},d}_{W,L_{j}},&j=1\\\
{\mathcal{N}}^{D^{(j)}_{1},D^{(j)}_{2},1}_{W,L_{j}},&j=2,\dotsc,J\end{cases}$

such that the composition $f_{{\Psi}_{J}}\circ\dotsc\circ f_{{\Psi}_{1}}$ is
well defined (i.e. the constituent networks $f_{\Psi_{j}}$ have compatible
domains and ranges for composition) the following holds:

$f_{{\Psi}_{J}}\circ\dotsc\circ
f_{{\Psi}_{1}}\in{\mathcal{N}}^{D^{(1)}_{1},D_{2}^{(1)},d}_{W,L_{1}+\dotsc+L_{J}}.$

###### Proof.

In [4], an analogous result is presented with the assumption that all
$f_{\Psi_{j}}\in\mathcal{N}^{0,1,1}_{W,L_{j}}$. The proof extends naturally
for the case of a dimension $d>1$ input space and for an arbitrary choice of
$D_{1},D_{2}$, so we omit the proof here. ∎

######  Remark 4.1.

Lemma 1 requires the composed neural networks to be of the same width. This
requirement is not restrictive since for any two ReLU networks of different
width, the width of the smaller network can be increased without changing the
overall network output by adding an appropriate amount of dead neurons to each
of its hidden layers.

In addition to composition, we will need to form linear combinations of ReLU
networks and bound their resulting complexity. Using just standard networks,
this can be accomplished by absorbing the complexity associated with the
linear combination into network width while keeping the depth fixed. This
procedure is outlined in Lemma 2.

######  Lemma 2.

For any $d\in\mathbb{N}$ and $D_{1},D_{2}\in\mathbb{R}$, with $D_{1}<D_{2}$,
and $f_{\Psi_{j}}\in\mathcal{N}^{D_{1},D_{2},d}_{W_{j},L}$,
$a_{j}\in\mathbb{R}$ for $j=1,\cdots,J$, the following holds,

$\sum_{j=1}^{J}a_{j}f_{\Psi_{j}}\in\mathcal{N}^{D_{1},D_{2},d}_{W,L},$

where $W=\sum_{j}W_{j}$.

###### Proof.

See Appendix B. ∎

######  Remark 4.2.

In Lemma 2, we make the assumption that all networks in the linear combination
have the same depth $L$. This requirement can be relaxed. Given any ReLU
network $f_{\Psi}\in\mathcal{N}^{D_{1},D_{2},d}_{W,L}$, its depth can be
extended indefinitely without changing the network output by appending hidden
layers that accomplish identity mapping. Identity mapping in ReLU networks
makes use of the relation
$\sigma(\bm{\theta})-\sigma(-\bm{\theta})=\bm{\theta}$, and for networks with
one-dimensional output, as those considered in this work, this identity
mapping can always be accomplished by a layer of width $2$. Let
$\bm{g}(\bm{\theta})$ be the vector containing the output of each neuron in
the final hidden layer, $b^{(L)}$ the output bias, and $M^{(L)}$ be the output
weights, so that the output of the original network is given by
$M^{(L)}\bm{g}(\bm{\theta})+b^{(L)}$. Then depth can be extended indefinitely
with a sequence of width 2 layers as pictured in Figure 5.

Figure 5: Extending network depth using identity mapping hidden layers

A direct calculation shows that the output of the network of extended depth is
$\sigma(M^{(L)}\bm{g}(\bm{\theta}))-\sigma(-M^{(L)}\bm{g}(\bm{\theta}))+b^{(L)}=M^{(L)}\bm{g}(\bm{\theta})+b^{(L)}$
as desired.

Having shown in Lemmas 1 and 2 how to form linear combinations and
compositions of standard ReLU networks, we now move to showing how these
operations can alternatively be realized using related special networks. We
begin with Lemma 3, which shows how basic arithmetic is carried out on special
networks.

######  Lemma 3.

Special ReLU networks of both type 1 and type 2 have the following properties:

  * (i)

For every $\
W,L_{1},L_{2}:\qquad\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,L_{1}}+\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,L_{2}}\subset\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,L_{1}+L_{2}}$.

  * (ii)

For $L<P:\ \ \
\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,L}\subset\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W,P}$.

###### Proof.

In [4], this is proved for type 1 special networks taking input in $[0,1]$.
Extending this proof for arbitrary multi-dimensional domains
$[D_{1},D_{2}]^{d}$ and type 2 networks is straightforward with the help of
Lemma 11, so we omit it here. ∎

Next, in Lemmas 4 and 5 we show how to accomplish basic network linear
combination and composition using type 1 special networks.

######  Lemma 4.

Let $W\geq 2$ and $D_{1},D_{2}\in\mathbb{R}$ with $D_{1}<D_{2}$. Then for any
$f_{{\Psi}_{j}}\in{\mathcal{N}}^{D_{1},D_{2},d}_{W,L_{j}}$ with
$j=1,\dotsc,J$, the following holds:

$f_{{\Psi}_{1}}+\dotsc+f_{{\Psi}_{J}}\in\tilde{\mathcal{N}}_{W+1+d,L_{1}+\dotsc+L_{J}},$

where the special networks realizing the network summation are of type 1.

###### Proof.

This result is proved in [4] for type 1 special networks taking input in
$[0,1]$. The proof can be readily extended for a network domain
$[D_{1},D_{2}]^{d}$ with $d>1$, so we omit it here. ∎

######  Lemma 5.

Let $D_{1},D_{2}\in\mathbb{R}$ with $D_{1}<D_{2}$. Then for any
$h\in{\mathcal{N}}^{D_{1},D_{2},1}_{W,L}$ with the added stipulation that $h$
maps into $[D_{1},D_{2}]$, i.e., the composition of $h$ with itself is well
defined, we have

$a_{0}\,\theta+\sum_{j=1}^{m}a_{j}\,h^{\circ
j}(\theta)\in\tilde{\mathcal{N}}^{D_{1},D_{2},1}_{W+2,mL},$

where the special networks realizing the network summation is of type 1.

###### Proof.

See Appendix B. ∎

######  Remark 4.3.

Considering Lemmas 4 and 5 together, we see that special ReLU networks provide
a way to form linear combinations of standard ReLU networks where the added
complexity associated with forming this linear combination is entirely
absorbed in network depth. This is the opposite of the strategy used in Lemma
2 where the complexity of the linear combination is entirely absorbed in
width. In general, we hypothesize that the benefit of using one of these
strategies over the other is task specific, and for example, in the proof of
our main theoretical results we use a combination of these strategies.

So far we have only considered ReLU network operations that require type 1
special networks. In Lemma 6, we introduce a recursive summation and
composition of ReLU networks that will be useful in the proof of our main
theoretical result and which relies on type 2 special networks.

######  Lemma 6.

Let $D_{1},D_{1}^{\prime},D_{2},D_{2}^{\prime}\in\mathbb{R}$ with
$D_{1}<D_{2}$ and $D_{1}^{\prime}<D_{2}^{\prime}$, and let $d\in\mathbb{N}$.
Further let $h_{j}\in\mathcal{N}_{W,L_{j}}^{D_{1},D_{2},d}$ and
$h_{j}^{\prime}\in\mathcal{N}_{W,L_{j}^{\prime}}^{D_{1}^{\prime},D_{2}^{\prime},1}$
for all $j=1,\dotsc J-1$. Let $p_{1}=0$ and suppose $p_{J}$ results from the
recursive scheme

$p_{j+1}(\bm{\theta})=p_{j}(\bm{\theta})+h_{j}(\bm{\theta})+h_{j}^{\prime}(p_{j}(\bm{\theta})),\qquad
j=1,...,J-1,\qquad\bm{\theta}\in[D_{1},D_{2}]^{d},$

with the added stipulation that $p_{j}(\bm{\theta})$ maps into
$[D_{1}^{\prime},D_{2}^{\prime}]$ for all $\bm{\theta}$ and $j=1,\dotsc J-1$;
i.e., the composition $h_{j}^{\prime}(p_{j}(\bm{\theta}))$ is well defined.
Then
$p_{J}\in\tilde{\mathcal{N}}^{D_{1},D_{2},d}_{W+d+1,\sum_{j}(L_{j}+L_{j}^{\prime})}$
where the special network is type 2.

###### Proof.

See Appendix B. ∎

The recursive network composition and combination encountered in Lemma 6
parallels the structure of Fourier features. Important to the proof of Theorem
1 will also be Lemma 7 which asserts that a ReLU network of bounded complexity
can well approximate an arbitrary one dimensional cosine function.

######  Lemma 7.

Let $a,v\in\mathbb{R},D>0$, $\theta\in[-D,D]$, and $\varepsilon\in(0,1/2)$.
Then there exists a constant $C>0$ and a ReLU network
$f_{\Psi}\in\mathcal{N}^{-D,D,1}_{W,L}$ with $W\leq 9$, $L\leq
C(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil aD+|v|\rceil)$, and
satisfying

$||f_{\Psi}(\theta)-\cos(a\theta+v)||_{L^{\infty}([-D,D])}\leq\varepsilon.$

###### Proof.

For the proof we refer to Corollary III.9 in [6]. By carefully leveraging
special networks, an alternate proof can be obtained where the upper bound on
$W$ is reduced to $8$, but for brevity we omit this discussion. ∎

##  5 Proof of Theorem 1

In this section, we present the proof of Theorem 1. To enhance readability we
start with a proof sketch, and then we proceed to provide full details for the
one-dimensional case in Section 5.1 and the multi-dimensional case in Section
5.2.

Theorem 1 proof sketch: Let $\varepsilon_{TOL}\in(0,1/2)$. Let $\Phi$ be a
Fourier features residual network of depth $L_{FF}$, width $W_{FF}$, realizing
the function $f_{\Phi}$, and approximating $f$. Let $\Psi$ be a ReLU network
realizing the function $f_{\Psi}$ and approximating $f_{\Phi}$. Then by the
triangle inequality we can write

$\displaystyle||f-f_{\Psi}||_{L^{2}(\Theta)}$
$\displaystyle\leq||f-f_{\Phi}||_{L^{2}(\Theta)}+||f_{\Phi}-f_{\Psi}||_{L^{2}(\Theta)}$
(14) $\displaystyle\leq\underbrace{||f-f_{\Phi}||_{L^{2}(\Theta)}}_{\text{term
1}}+\underbrace{||f_{\Phi}-f_{\Psi}||_{L^{\infty}(\Theta)}}_{\text{term 2}}.$
(15)

Now according to Theorem 3, term 1 can be made arbitrarily small with the
depth and width of $\Phi$ satisfying

$W_{FF}L_{FF}=\mathcal{O}\left(\frac{||f||^{2}_{L^{\infty}(\Theta)}}{\varepsilon_{TOL}^{2}}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2}\right),$
(16)

From here, the primary task of the proof is to show that there exists a ReLU
network $\Psi$ realizing the function $f_{\Psi}$ such that term 2 can be made
arbitrarily small with $WL=\mathcal{O}(dW_{FF}L_{FF})$. Once this is
accomplished, the result follows. We accomplish this through a constructive
approximation of a Fourier features residual network by a ReLU network.

###  5.1 Proof of Theorem 1 for univariable target function

In this section, we provide a rigorous proof for Theorem 1 for a target
function $f\in S$ as defined in (1) with a one-dimensional input, that is
$\theta\in\Theta=[0,1]$. For simplicity, we make a slight abuse of notation
and denote by $\Psi$ both a ReLU network and the function it realizes, and by
$\Phi$ both a Fourier features residual network and the function it realizes.
The primary task of this proof is to show that a Fourier features residual
network approximating $f\in S$ can be approximated well by a ReLU network of
bounded complexity. Recall from Section 4.1 that a Fourier features network of
depth $L_{FF}$ is built as a linear combination and composition of functions
of the form $\beta_{\ell}$, $\beta_{\ell}^{\prime}$, and $z_{\ell}$ for
$\ell=0,\dotsc,L_{FF}-1$. The proof proceeds as a sequence of lemmas. We begin
in Lemma 8 by showing that functions of the form $\beta_{\ell}$ and
$\beta_{\ell}^{\prime}$, defined respectively by Equations (11) and (12), can
be approximated well by ReLU networks of bounded complexity.

######  Lemma 8 (ReLU network approximation of $\beta_{\ell}$ and
$\beta^{\prime}_{\ell}$).

Let $\ell\in\mathbb{N}\cup\\{0\\}$ and $D>0$. Consider the function
$\beta_{\ell}:\theta\in[-D,D]\mapsto\mathbb{R}$ as defined in (11). Then for
any $\varepsilon\in(0,1/2)$ there exists a ReLU network
$\Psi_{\beta_{\ell}}\in\mathcal{N}^{-D,D,1}_{W,L}$ with $L\geq 2$ and $W\geq
1+d$ such that

$||\beta_{\ell}(\theta)-\Psi_{\beta_{\ell}}(\theta)||_{L^{\infty}([-D,D])}\leq\varepsilon.$

Moreover, there exists constants $C_{\ell}>0,\omega_{\ell}\in\mathbb{R}_{\geq
0}$ such that the width and depth of $\Psi_{\beta_{\ell}}$ satisfy

$\displaystyle L(\Psi_{\beta_{\ell}})$ $\displaystyle\leq
C_{\ell}(\log^{2}_{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega_{\ell}D+\pi/2\rceil))$
$\displaystyle W(\Psi_{\beta_{\ell}})$ $\displaystyle\leq 9W_{FF}$

###### Proof.

Let $\varepsilon\in(0,1/2)$. Recall that $\beta_{\ell}$ is of the form

$\beta_{\ell}(\theta)=\sum_{k=1}^{W_{FF}}|b_{\ell k}|\cos\left(\omega_{\ell
k}\theta-\tan^{-1}\left(\frac{-\Im(b_{\ell k})}{\Re(b_{\ell
k})}\right)\right).$

From Lemma 7 we have that for each $k=1,\dots W_{FF}$, there exists a constant
$C^{\cos}_{\ell k}>0$ and ReLU networks $\Psi^{\cos}_{\omega_{\ell k}}$ such
that

$\bigg{|}\bigg{|}\Psi^{\cos}_{\omega_{\ell k}}(\theta)-\cos\left(\omega_{\ell
k}\theta-\tan^{-1}\left(\frac{-\Im(b_{\ell k})}{\Re(b_{\ell
k})}\right)\right)\bigg{|}\bigg{|}_{L^{\infty}([0,1])}\leq\frac{\varepsilon}{W_{FF}|b_{\ell
k}|},$ (17)

with network width and depth satisfying

$\displaystyle L(\Psi^{\cos}_{\omega_{\ell k}})$ $\displaystyle\leq C_{\ell
k}\left(\log^{2}_{2}(\varepsilon^{-1})+\log_{2}\left(\bigg{\lceil}\omega_{\ell
k}D+\left|\tan^{-1}\left(\frac{-\Im(b_{\ell k})}{\Re(b_{\ell
k})}\right)\right|\bigg{\rceil}\right)\right);$ (18) $\displaystyle
W(\Psi^{\cos}_{\omega_{\ell k}})$ $\displaystyle\leq 9.$ (19)

Now using Lemma 2 we generate a ReLU network $\Psi_{\beta_{\ell}}$ that
realizes the linear combination

$\Psi_{\beta_{\ell}}(\theta)=\sum_{k=1}^{W_{FF}}|b_{\ell
k}|\Psi^{\cos}_{\omega_{\ell k}}(\theta).$

This linear combination requires that we equalize the depth the constituent
networks $\Psi^{\cos}_{\omega_{\ell k}}$ for $k=1,\dotsc,W_{FF}$, which we do
using the strategy explained in Remark 4.2. Furthermore, in accordance with
Lemma 2, the width of the resulting network is the sum of the widths of the
constituent networks. Overall, the resulting width and equalized depth can be
bounded above as

$\displaystyle L(\Psi_{\beta_{\ell}})$ $\displaystyle\leq
C_{\ell}(\log^{2}_{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega_{\ell}D+\pi/2\rceil));$
$\displaystyle W(\Psi_{\beta_{\ell}})$ $\displaystyle\leq 9W_{FF},$

where $\omega_{\ell}=\max_{k}\\{\omega_{\ell k}\\}$,
$C_{\ell}=\max_{k}\\{C_{\ell k}\\}$, and $|\tan^{-1}\left(-\Im(b_{\ell
k})/\Re(b_{\ell k})\right)|\leq\pi/2$ for all $k=1,\dotsc,W_{FF}$.
Additionally, using (17) along with the triangle inequality we find

$||\beta_{\ell}(\theta)-\Psi_{\beta_{\ell}}(\theta)||_{L^{\infty}(\Theta)}\leq\varepsilon.\qed$

######  Remark 5.1.

In the proof of Lemma 8, we use the network linear combination strategy
outlined in Lemma 2 to absorb the complexity associated with the linear
combination into width. The result is a ReLU width $W$ linearly dependent on
the Fourier features width $W_{FF}$ and a ReLU depth $L$ independent of the
Fourier features network architecture. We can alternatively use network linear
combination via special ReLU networks as outlined in Lemma 4 to absorb the
complexity associated with the linear combination into depth. This results in
a ReLU network width independent of the Fourier features network architecture
and a ReLU depth $L$ linearly dependent on the Fourier features width
$W_{FF}$. We return to this observation later in Remark 5.3 when we discuss
network architecture suppositions in our main theoretical results.
Furthermore, the lower bound $W\geq 1+d$ is necessary because it was shown in
[9] that universal approximation of continuous functions by ReLU networks of
finite width requires that width be strictly greater than input dimension.
Finally, note that $\beta_{\ell}$ and $\beta_{\ell}^{\prime}$ are of the same
form, so Lemma 8 and its proof remain valid when replacing $\beta_{\ell}$ by
$\beta_{\ell}^{\prime}$.

Next, in Lemma 9 we leverage Lemma 8 to show that for any
$L_{FF}\in\mathbb{N}$ a function of the form $z_{L_{FF}}$ as defined in
Equation (10) can be approximated well by a ReLU network of bounded
complexity.

######  Lemma 9 (ReLU network approximation of $z_{L_{FF}}$).

Let $L_{FF}\in\mathbb{N}$ and consider the function
$z_{L_{FF}}:\theta\in\Theta\mapsto\mathbb{R}$ as defined in Equation (10).
Then for any $\varepsilon\in(0,1/2)$ and $L_{FF}\in\mathbb{N}$, there exists a
ReLU network $\Psi_{z_{L_{FF}}}\in\mathcal{N}^{0,1,1}_{W,L}$ with $L\geq 2$
and $W\geq 2d+2$ such that

$||z_{L_{FF}}(\theta)-\Psi_{z_{L_{FF}}}(\theta)||_{L^{\infty}([\Theta])}\leq\varepsilon.$
(20)

Moreover, there exists constants $\bar{C}>0,\bar{\omega}\in\mathbb{R}_{\geq
0}$ such that the width and depth of $\Psi_{z_{L_{FF}}}$ satisfy

$\displaystyle L(\Psi_{z_{L_{FF}}})$
$\displaystyle\leq\bar{C}(L_{FF}-1)(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\bar{\omega}+\pi/2\rceil));$
(21) $\displaystyle W(\Psi_{z_{L_{FF}}})$ $\displaystyle\leq 9W_{FF}+2.$ (22)

###### Proof.

Unless otherwise specified, in what follows we define
$||\cdot||:=||\cdot||_{L^{\infty}(\Theta)}$. Let $\varepsilon\in(0,1/2)$. We
now proceed by induction on $L_{FF}$. First, for $L_{FF}=1$ we have
$\Psi_{z_{1}}\equiv z_{1}\equiv 0$. Hence $z_{1}$ can be represented exactly
by a single neuron of bias zero. Next, for our base case we consider
$L_{FF}=2$, and we recall that

$z_{2}(\theta)=z_{1}(\theta)+\beta_{1}(\theta)+\beta_{1}^{\prime}(z_{1}(\theta))=\beta_{1}(\theta)+\beta_{1}^{\prime}(0).$

Then from Lemma 8 we know there exists ReLU networks $\Psi_{\beta_{1}}$ and
$\Psi_{\beta_{1}^{\prime}}$ such that

$\displaystyle||\beta_{1}(\theta)-\Psi_{\beta_{1}}(\theta)||_{L^{\infty}(\Theta)}$
$\displaystyle\leq\frac{\varepsilon}{2};$ (23)
$\displaystyle||\hat{\beta}_{1}(\theta)-\Psi_{\beta_{1}^{\prime}}(\theta)||_{L^{\infty}(\Theta)}$
$\displaystyle\leq\frac{\varepsilon}{2}.$ (24)

Employing Lemma 6, we form the type 2 special network
$\tilde{\Psi}_{z_{2}}(\theta)=z_{1}(\theta)+\Psi_{\beta_{1}}(\theta)+\Psi_{\beta_{1}^{\prime}}(z_{1})$
displayed in Figure 6. By construction, the width of $\tilde{\Psi}_{z_{2}}$ is
$2$ more than the maximum of the widths of $\Psi_{\beta_{1}^{\prime}}$ and
$\Psi_{\beta_{1}}$, where the additional neurons are due to the width $1$
source and collation channels.

Figure 6: Network diagram for $\tilde{\Psi}_{z_{2}}$

Then from Section 4.2 we know there exists a standard ReLU network
$\Psi_{z_{2}}$ such that $\Psi_{z_{2}}(\theta)=\tilde{\Psi}_{z_{2}}(\theta)$
for all $\theta\in[0,1]$. Furthermore, since only $\Psi_{\beta_{1}}$ takes
input from the source channel, and since $\Psi_{\beta_{1}}$ need only accept
non-negative inputs, the conversion from special to standard network requires
no source channel modification, and the width of $\Psi_{z_{2}}$ is equivalent
to that of $\tilde{\Psi}_{z_{2}}$. Now, leveraging (23) and (24), using the
fact that $z_{1}(\theta)=0$, and employing the triangle inequality we
calculate

$\displaystyle||z_{2}(\theta)-\Psi_{z_{2}}(\theta)||$
$\displaystyle=||\beta_{1}(\theta)+\beta_{1}^{\prime}(0)-\Psi_{\beta_{1}}(\theta)-\Psi_{\beta_{1}^{\prime}}(0)||$
$\displaystyle\leq||\beta_{1}(\theta)-\Psi_{\beta_{1}}(\theta)||+||\beta_{1}^{\prime}(0)-\Psi_{\beta_{1}^{\prime}}(0)||$
$\displaystyle\leq\varepsilon.$

Moreover, the complexity of $\Psi_{z_{2}}$ can be calculated directly as

$\displaystyle L(\Psi_{z_{2}})$
$\displaystyle=L(\Psi_{\beta_{1}})+L(\Psi_{\beta_{1}^{\prime}})$
$\displaystyle\leq
C_{1}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega_{1}+\pi/2\rceil))+C_{1}^{\prime}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega_{1}^{\prime}+\pi/2\rceil))$
$\displaystyle\leq\bar{C}\log_{2}^{2}(\varepsilon^{-1}+\log_{2}(\lceil\bar{\omega}+\pi/2\rceil));$
$\displaystyle W(\Psi_{z_{2}})$
$\displaystyle\leq\max\\{W(\Psi_{\beta_{1}}),W(\Psi_{\beta_{1}^{\prime}})\\}+2$
$\displaystyle\leq 9W_{FF}+2,$

where $C_{1},\omega_{1}$ and $C_{1}^{\prime},\omega_{1}^{\prime}$ are the
constants present in the complexity bounds for respectively $\Psi_{\beta_{1}}$
and $\Psi_{\beta_{1}^{\prime}}$ guaranteed to exist by Lemma 8, and where
$\bar{C}=C_{1}+C_{1}^{\prime}>0$,
$\bar{\omega}=\max\\{\omega_{1},\omega_{1}^{\prime}\\}\in\mathbb{R}_{\geq 0}$.

Next, let $L_{FF}=\ell\in\mathbb{N}$ with $\ell>2$. Recall that the function
$z_{L_{FF}}$ results from the recursive scheme

$z_{1}=0,\qquad
z_{j+1}(\theta)=z_{j}(\theta)+\beta_{j}(\theta)+\beta_{j}^{\prime}(z_{j}(\theta)),\qquad
j=1,\dotsc,\ell-1.$

Hence there exists functions $z_{j}:\Theta\mapsto\mathbb{R}$ for all
$j=1,\dotsc\ell$. Since each $z_{j}$ is continuous on the compact set
$\Theta$, there exists a constant $D\in\mathbb{R}_{\geq 0}$ such that
$|z_{j}(\theta)|\leq D$ for all $\theta\in\Theta$ and all $j=1,\cdots\ell$.

Now notice that $\beta_{j}^{\prime}$ is continuous everywhere and therefore
uniformly continuous on the compact set $[-(D+1/8),D+1/8]$ for any
$j=1,\cdots,\ell$. Thus there exists $\delta_{j}>0$ such that for any
$\theta_{1},\theta_{2}\in[-(D+1/8),(D+1/8)]$ where
$|\theta_{1}-\theta_{2}|\leq\delta_{j}$, we have
$|\beta_{j}^{\prime}(\theta_{1})-\beta_{j}^{\prime}(\theta_{2})|\leq\varepsilon/4$.
In particular, this holds for $\beta_{\ell}^{\prime}$. Continuing, from Lemma
8 there exists $\Psi_{\beta_{j}}$ and $\Psi_{\beta_{j}^{\prime}}$ such that

$\displaystyle||\beta_{j}(\theta)-\Psi_{\beta_{\ell}}(\theta)||_{L^{\infty}(\Theta)}$
$\displaystyle\leq\frac{\varepsilon}{4};$ (25)
$\displaystyle||\beta_{j}^{\prime}(\theta)-\Psi_{\beta_{\ell}^{\prime}}(\theta)||_{L^{\infty}([-(D+1/8),D+1/8])}$
$\displaystyle\leq\frac{\varepsilon}{4}.$ (26)

Notice that we require $\Psi_{\beta_{j}^{\prime}}$ to take inputs in
$[-(D+1/8),D+1/8]$ whereas $\Psi_{\beta_{j}}$ need only take inputs in
$\Theta$. The reasoning for this requirement will be clear momentarily. Now
for our inductive hypothesis assume $\Psi_{z_{j}}$ exists for all
$j=1,\dotsc,\ell$ and satisfies

$||z_{j}(\theta)-\Psi_{z_{j}}(\theta)||\leq\min\\{\delta_{j},\varepsilon/4\\}.$
(27)

Now we leverage Lemma 6 to construct the type 2 special ReLU network
$\tilde{\Psi}_{z_{\ell+1}}$, displayed in Figure 7, that realizes the
recursive summation and composition

$\Psi_{z_{1}}=z_{1}=0,\qquad\Psi_{z_{j+1}}(\theta)=\Psi_{z_{j}}(\theta)+\Psi_{\beta_{j}}(\theta)+\Psi_{\beta_{j}^{\prime}}(\Psi_{z_{j}}(\theta)),\qquad
j=1,\dotsc,\ell.$

Notice that the inductive hypothesis (27) guarantees that each $\Psi_{z_{j}}$
maps into $[-(D+1/8),D+1/8]$ for any $\varepsilon\in(0,1/2)$, which in turn
makes the compositions $\Psi_{\beta_{j}}^{\prime}(\Psi_{z_{j}}(\theta))$ well
defined for all $\theta\in\Theta$ and all $j=1,\dotsc\ell$. Analogous to the
handling of $\tilde{\Psi}_{z_{2}}$, the width of $\tilde{\Psi}_{z_{\ell+1}}$
will be $2$ more than the maximum width of $\Psi_{\beta_{j}}$ and
$\Psi_{\beta_{j}^{\prime}}$ for any $j=1,\dotsc,\ell$, where the additional
neurons are due to width $1$ source and collation channels.

Figure 7: Network diagram for $\tilde{\Psi}_{z_{\ell+1}}$

There then exists a standard ReLU network, $\Psi_{z_{\ell+1}}$, such that
$\Psi_{z_{\ell+1}}(\theta)=\tilde{\Psi}_{z_{\ell+1}}(\theta)$ for all
$\theta\in\Theta$, and just like before, since only the $\Psi_{\beta_{j}}$
accept inputs from the source channel, and since their inputs are non-
negative, the conversion between special and standard network requires no
source channel modification, and the width of $\Psi_{z_{\ell+1}}$ is equal to
the width of $\tilde{\Psi}_{z_{\ell+1}}$. Using (25), (26), and (27) we
calculate

$\displaystyle||z_{\ell+1}(\theta)-\Psi_{z_{\ell+1}}(\theta)||$
$\displaystyle=||z_{\ell}+\beta_{\ell}(\theta)+\beta_{\ell}^{\prime}(z_{\ell}(\theta))-\Psi_{z_{\ell}}-\Psi_{\beta_{\ell}}(\theta)-\Psi_{\beta_{\ell}^{\prime}}(\Psi_{z_{\ell}}(\theta))||$
$\displaystyle\leq||z_{\ell}(\theta)-\Psi_{z_{\ell}}(\theta)||+||\beta_{\ell}(\theta)-\Psi_{\beta_{\ell}}(\theta)||+||\beta_{\ell}^{\prime}(z_{\ell}(\theta))-\Psi_{\beta_{\ell}^{\prime}}(\Psi_{z_{\ell}}(\theta))||$
$\displaystyle\leq\frac{\varepsilon}{4}+\frac{\varepsilon}{4}+||\beta_{\ell}^{\prime}(z_{\ell}(\theta))-\beta_{\ell}^{\prime}(\Psi_{z_{\ell}}(\theta))+\beta_{\ell}^{\prime}(\Psi_{z_{\ell}}(\theta))-\Psi_{\beta_{\ell}^{\prime}}(\Psi_{z_{\ell}}(\theta))||$
$\displaystyle\leq\frac{\varepsilon}{2}+||\beta_{\ell}^{\prime}(z_{\ell}(\theta))-\beta_{\ell}^{\prime}(\Psi_{z_{\ell}}(\theta))||+||\beta_{\ell}^{\prime}(\Psi_{z_{\ell}}(\theta))-\Psi_{\beta_{\ell}^{\prime}}(\Psi_{z_{\ell}}(\theta))||$
$\displaystyle\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{4}+\frac{\varepsilon}{4}$
$\displaystyle=\varepsilon.$

To this point, given $L_{FF}\in\mathbb{N}$, we have shown how to
constructively generate a network $\Psi_{z_{L_{FF}}}$ that satisfies the error
tolerance (20). Finally, given the constructive nature of the proof, the
complexity of $\Psi_{z_{L_{FF}}}$ can be bounded as follows:

$\displaystyle L(\Psi_{z_{L_{FF}}})$
$\displaystyle=\sum_{\ell=1}^{L_{FF}-1}(L(\Psi_{\beta_{\ell}})+L(\Psi_{\beta_{\ell}^{\prime}}))$
$\displaystyle=\sum_{\ell=1}^{L_{FF}-1}\big{(}C_{\ell}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega_{\ell}+\pi/2\rceil))$
$\displaystyle\qquad+C^{\prime}_{\ell}(\log_{2}^{2}(\varepsilon^{-1})+\max\\{\log_{2}(\lceil\omega^{\prime}_{\ell}+\pi/2\rceil),\log_{2}(\lceil\omega_{\ell}^{\prime}(D+1/8)+\pi/2\rceil)\\})\big{)}$
$\displaystyle\leq\bar{C}(L_{FF}-1)(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\bar{\omega}+\pi/2\rceil)),$
(28)

where $C_{\ell},C^{\prime}_{\ell}>0$ and
$\omega_{\ell},\omega^{\prime}_{\ell}\in\mathbb{R}_{\geq 0}$ are guaranteed to
exist by Lemma 8, and where
$\bar{C}=\max_{\ell}\\{C_{\ell}+C_{\ell}^{\prime}\\}$ and
$\bar{\omega}=\max_{\ell}\\{\omega_{\ell},\omega_{\ell}^{\prime},\omega_{\ell}^{\prime}(D+1/8)\\}$.
Additionally, the width of $\Psi_{z_{L}}$ satisfies

$W(\Psi_{z_{L}})\leq\max\\{W(\Psi_{\beta_{\ell}}),W(\Psi_{\beta_{\ell}^{\prime}}):\ell=1,\dots,L_{FF}-1\\}+2\leq
9W_{FF}+2.\qed$

######  Remark 5.2.

The constant $D$ appearing in the proof of Lemma 9 is a uniform upper bound on
the the functions $z_{j}$ for $j=1,\dotsc,L_{FF}-1$. In the context of
approximating a target function $f\in S$ by a Fourier features residual
network we have $z_{1}=0$, and then for $j=2,\dotsc,L_{FF}$, $z_{j}\approx
f-\beta_{0}$ where $\beta_{0}$ is a $W_{FF}$ term Fourier approximation of
$f$. Hence conservatively we can assume $D\leq||f||_{L^{\infty}(\Theta)}$. In
practice, we anticipate that $D$ is often small, and in some cases even much
less than $1$. For example, any $f\in S$ that is continuous can be uniformly
approximated to any small tolerance by the $W_{FF}$ term Fourier sum
$\beta_{0}$ as $W_{FF}\to\infty$ [8]. Hence for sufficiently large $W_{FF}$ we
expect that the quantity $f-\beta_{0}$ learned by $z_{j}$ to satisfy
$||f-\beta_{0}||_{L^{\infty}}\ll||f||_{L^{\infty}}$ for any
$j=2,\dotsc,L_{FF}$.

We additionally remark that the $d+1$ increase in the lower-bound on $W$ is
required due to our use of special networks which introduce a width $d$ source
channel and width 1 collation channel to the overall network.

Now, leveraging Lemmas 8 and 9 we show that an arbitrary Fourier features
network can be approximated by a ReLU network of bounded complexity.

######  Lemma 10 (Approximation of Fourier features residual network by ReLU
Network).

Let $\Phi$ be a Fourier features residual network with width
$W_{FF}\in\mathbb{N}$ and depth $L_{FF}\geq 2$, and let
$f_{\Phi}:\theta\in\Theta\mapsto\mathbb{R}$ be the function it realizes. Then
for any $\varepsilon\in(0,1/2)$ there exists a ReLU network
$\Psi_{f_{\Phi}}\in\mathcal{N}^{0,1,1}_{W,L}$ with $L\geq 2$ and $W\geq 2d+2$
such that

$||f_{\Phi}-\Psi_{f_{\Phi}}||_{L^{\infty}(\Theta)}\leq\varepsilon.$ (29)

Moreover, there exists constants $C>0,\omega\in\mathbb{R}_{\geq 0}$ such that
the width and depth of $\Psi_{f_{\Phi}}$ satisfy

$\displaystyle L(\Psi_{f_{\Psi}})$ $\displaystyle\leq
CL_{FF}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega+\pi/2\rceil));$
(30) $\displaystyle W(\Psi_{f_{\Phi}})$ $\displaystyle\leq 9W_{FF}+2.$ (31)

###### Proof.

Let $\epsilon\in(0,1/2)$. By Lemma 8 and Lemma 9 respectively there exists
ReLU networks $\Psi_{\beta_{0}}$ and $\Psi_{z_{L_{FF}}}$ that satisfy

$\displaystyle||\beta_{0}(\theta)-\Psi_{\beta_{0}}(\theta)||_{L^{\infty}(\Theta)}$
$\displaystyle\leq\frac{\varepsilon}{2};$ (32)
$\displaystyle||z_{L_{FF}}(\theta)-\Psi_{z_{L_{FF}}}(\theta)||_{L^{\infty}(\Theta)}$
$\displaystyle\leq\frac{\varepsilon}{2},$ (33)

with bounds on width and depth given respectively in Lemmas 8 and 9.
Furthermore, we may assume that $\Psi_{z_{L_{FF}}}$ is constructed as a
standard ReLU network equivalent to a type 2 special network
$\tilde{\Psi}_{z_{L_{FF}}}$ as appears in Lemma 9. We now construct the type 2
special network $\tilde{\Psi}_{f_{\Phi}}$ pictured in Figure 8 by appending
the network $\Psi_{\beta_{0}}$ to the special network
$\tilde{\Psi}_{z_{L_{FF}}}$.

Figure 8: Type 2 special network $\tilde{\Psi}_{f_{\Phi}}$

In doing this we add a width $1$ source and collation channel to
$\Psi_{\beta_{0}}$, and if necessary we equalize the width between
$\tilde{\Psi}_{z_{L_{FF}}}$ and $\Psi_{\beta_{0}}$ by adding dead neurons to
the hidden layers of the smaller network. By construction
$\tilde{\Psi}_{f_{\Phi}}$ realizes the sum
$\Psi_{z_{L_{FF}}}(\theta)+\Psi_{\beta_{0}}(\theta)$.

We now define $\Psi_{f_{\Phi}}$ as the standard ReLU network equivalent to
$\tilde{\Psi}_{f_{\Phi}}$, and using (32) and (33) we calculate

$\displaystyle||f_{\Phi}(\theta)-\Psi_{f_{\Phi}}(\theta)||_{L^{\infty}(\Theta)}$
$\displaystyle\leq||\beta_{0}(\theta)-\Psi_{\beta_{0}}(\theta)||_{L^{\infty}(\Theta)}+||z_{L}(\theta)-\Psi_{z_{L}}(\theta)||_{L^{\infty}(\Theta)}$
$\displaystyle\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}$
$\displaystyle=\varepsilon.$

Finally, the constructive nature of the proof allows us to bound the
complexity of $\Psi_{f_{\Phi}}$ as

$\displaystyle L(\Psi_{f_{\Phi}})$
$\displaystyle=L(\Psi_{\beta_{0}})+L(\Psi_{z_{L_{FF}}})$ $\displaystyle\leq
CL_{FF}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega+\pi/2\rceil));$
$\displaystyle W(\Psi_{f_{\Phi}})$
$\displaystyle\leq\max\\{W(\Psi_{\beta_{0}}),W(\Psi_{z_{L_{FF}}})-2\\}+2$
$\displaystyle\leq 9W_{FF}+2,$

where $C=\max\\{C_{0},\bar{C}\\}$ and
$\omega=\max\\{\omega_{0},\bar{\omega}\\}$. Here $C_{0}>0$ and
$\omega_{0}\in\mathbb{R}_{\geq 0}$ are the constants present in the complexity
bounds for $\Psi_{\beta_{0}}$ guaranteed by Lemma 8, and $\bar{C}>0$ and
$\bar{\omega}\in\mathbb{R}_{\geq 0}$ are the constants present in the
complexity bounds for $\Psi_{z_{L_{FF}}}$ guaranteed by Lemma 9. ∎

######  Remark 5.3.

In Lemma 10, we show that an arbitrary Fourier features residual network of
width $W_{FF}$ and depth $L_{FF}$ can be well approximated by a ReLU network
where ReLU width and depth are respectively linearly dependent on Fourier
features width and depth; i.e., $W=\mathcal{O}(W_{FF})$ and
$L=\mathcal{O}(L_{FF})$. Modifying the proof of Lemma 8 according to Remark
5.1, we can alternatively approximate a Fourier features residual network by a
ReLU network with $L=\mathcal{O}(W_{FF}L_{FF})$ and $W$ independent of the
Fourier features network architecture. Recall that the Fourier features
approximation error estimate in Theorem 3 requires
$W_{FF}=\mathcal{O}(L_{FF}^{2})$. The above discussion tells us that this
network aspect ratio requirement is not necessary for either of our derived
theoretical results on ReLU networks.

We are now ready to prove the main complexity theorem.

Proof of Theorem 1. Recall in this section that $d=1$, and hence
$\Theta=[0,1]$. Let $\varepsilon\in(0,1/2)$. From Theorem 3 there exists a
constant $C_{1}>0$ and a Fourier features residual network $\Phi$ realizing
the function $f_{\Phi}$ with the product of width and depth satisfying

$W_{FF}L_{FF}=C_{1}\frac{||f||^{2}_{L^{\infty}(\Theta)}}{\varepsilon^{2}}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2},$
(34)

and satisfying the error tolerance

$||f_{\Phi}-f||_{L^{2}(\Theta)}\leq\frac{\varepsilon}{2}.$

Then from Lemma 10 there exists constants $C_{2}>0,\omega\in\mathbb{R}_{\geq
0}$ and ReLU network $f_{\Psi}\in\mathcal{N}^{0,1,1}_{W,L}$ with complexity
bounds

$\displaystyle L$ $\displaystyle\leq
C_{2}L_{FF}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\omega+\pi/2\rceil));$
(35) $\displaystyle W$ $\displaystyle\leq 9W_{FF}+2,$ (36)

and satisfying
$||f_{\Psi}-{f_{\Phi}}||_{L^{\infty}(\Theta)}\leq\varepsilon/2$. Now employing
the triangle inequality as well as the compactness of the set $\Theta$ we find

$\displaystyle||f-f_{\Psi}||_{L^{2}(\Theta)}$
$\displaystyle\leq||f-f_{\Phi}||_{L^{2}(\Theta)}+||f_{\Phi}-f_{\Psi}||_{L^{2}(\Theta)}$
$\displaystyle\leq||f-f_{\Phi}||_{L^{2}(\Theta)}+||f_{\Phi}-f_{\Psi}||_{L^{\infty}(\Theta)}$
$\displaystyle\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}$
$\displaystyle=\varepsilon.$

The expression for $L$ can be further bounded above as

$L\leq C_{3}L_{FF}\log_{2}^{2}(\varepsilon^{-1}),$ (37)

where $C_{3}=C_{2}\cdot(1+\log_{2}(\lceil\omega+\pi/2\rceil)>0.$ Then
multiplying (37) and (36) we find

$WL\leq C_{4}W_{FF}L_{FF}\log_{2}^{2}(\varepsilon^{-1}),$ (38)

where $C_{4}=11C_{3}>0$. Further, using the expression for $W_{FF}L_{FF}$ in
(34) we can write

$WL\leq
C\frac{||f||_{L^{\infty}(\Theta)}^{2}}{\varepsilon^{2}}\left(1+\ln\left(\frac{||\hat{f}||_{L^{1}(\mathbb{R})}}{||f||_{L^{\infty}(\Theta)}}\right)\right)^{2}\log_{2}^{2}(\varepsilon^{-1}),$

where $C=C_{4}C_{1}>0$. ∎

###  5.2 Extending the proof of Theorem 1 for a multivariable target function

The proof presented for $d=1$ can be generalized in the case of a multi-
dimensional parameter space. In this section we follow the structure of the
one dimensional proof and highlight the necessary modifications.

Suppose $\bm{\theta}\in\Theta=[0,1]^{d}$ with $d\geq 2$. We begin by showing
how Lemma 8 can be modified to accommodate this higher dimensional input
$\bm{\theta}$. Recall the form of the function $\beta_{\ell}$ in (11)

$\beta_{\ell}(\bm{\theta})=\sum_{k=1}^{W_{FF}}|b_{\ell
k}|\cos\left(\bm{\omega}_{\ell
k}\cdot\bm{\theta}-\tan^{-1}\left(\frac{-\text{Im}(b_{\ell
k})}{\text{Re}(b_{\ell k})}\right)\right).$

Using the identity $\sigma(\bm{\theta})-\sigma(-\bm{\theta})=\bm{\theta}$, the
argument
$\bm{\omega}_{\ell,k}\cdot\bm{\theta}-\tan^{-1}\left(\frac{-\text{Im}(b_{\ell
k})}{\text{Re}(b_{\ell k})}\right)$ for $\bm{\theta}\in[0,1]^{d}$ and
$\bm{\omega}_{\ell k}\in\mathbb{R}^{d}$ can be represented exactly by a ReLU
network $\Psi_{\bm{\theta}\cdot\bm{\omega}_{\ell k}}$ with a single hidden
layer containing $2$ neurons. An example of such a network for $d=3$ is
pictured in Figure 9.

Figure 9: ReLU network realizing $\bm{\omega}_{\ell
k}\cdot\bm{\theta}-\tan^{-1}\left(\frac{-\text{Im}(b_{\ell
k})}{\text{Re}(b_{\ell k})}\right)$ for
$\bm{\theta}\in[0,1]^{3},\bm{\omega}_{\ell k}\in\mathbb{R}_{\geq 0}^{3}$

.

Next, let

$\Omega_{\ell}=\max_{k}\\{\left|\bm{\omega}_{\ell
k}\cdot\bm{\theta}\right|+\pi/2\\}\geq\max_{k}\bigg{\\{}\left|\bm{\omega}_{\ell
k}\cdot\bm{\theta}-\tan^{-1}\left(\frac{-\text{Im}(b_{\ell
k})}{\text{Re}(b_{\ell k})}\right)\right|\bigg{\\}}.$

Then from Lemma 7, for any $\varepsilon\in(0,1/2)$ there exists a ReLU network
$\Psi^{\cos}:\theta\in[-\Omega_{\ell},\Omega_{\ell}]\mapsto\mathbb{R}$ such
that
$||\Psi^{\cos}(\theta)-\cos(\theta)||_{L^{\infty}([-\Omega_{\ell},\Omega_{\ell}])}\leq\varepsilon$.
Moreover, there exists a constant $A_{\ell}>0$ such that the width and depth
of $\Psi^{\cos}$ satisfy

$\displaystyle L(\Psi^{\cos})$ $\displaystyle\leq
A_{\ell}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\Omega_{\ell}\rceil));$
(39) $\displaystyle W(\Psi^{\cos})$ $\displaystyle\leq 9.$ (40)

Next, consider the composition network $\Psi^{\cos}_{\omega_{\ell
k}}:=\Psi^{\cos}\circ\Psi_{\bm{\theta}\cdot\bm{\omega}_{\ell
k}}:\bm{\theta}\in\Theta\mapsto\mathbb{R}$. Note that although $\Psi^{\cos}$
and $\Psi_{\bm{\theta}\cdot\bm{\omega}_{\ell k}}$ may have different widths,
they can be composed as explained in Remark 4.1. Then for any
$\ell\in\mathbb{N}\cup\\{0\\}$ and $k\in\mathbb{N}$ the ReLU network
$\Psi:=\Psi^{\cos}\circ\Psi_{\bm{\theta}\cdot\bm{\omega}_{\ell k}}$
approximates the function $\cos\left(\bm{\omega}_{\ell
k}\cdot\bm{\theta}-\tan^{-1}\left(\frac{-\text{Im}(b_{\ell
k})}{\text{Re}(b_{\ell k})}\right)\right)$ to tolerance $\varepsilon$ with
width and depth satisfying (40) and (39) and with $A_{\ell}$ replaced by
$C_{\ell}=(1+A_{\ell})>1.$

Having shown this, the construction of a neural network approximating
$\beta_{\ell}$ to tolerance $\varepsilon$ with bounded complexity proceeds as
in Lemma 8. We use the network linear combination strategy outlined in Lemma 2
and find that the overall network complexity of $\Psi_{\beta_{\ell}}$
satisfies

$\displaystyle L(\Psi_{\beta_{\ell}})$ $\displaystyle\leq
C_{\ell}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\Omega_{\ell}\rceil));$
$\displaystyle W(\Psi_{\beta_{\ell}})$ $\displaystyle\leq 9W_{FF}.$

Now consider an extension of Lemma 9 in the case $d\geq 2$. We construct a
standard ReLU network $\Psi_{z_{L_{FF}}}\approx z_{L_{FF}}$ equivalent to a
type 2 special ReLU network $\tilde{\Psi}_{z_{L_{FF}}}$ that realizes the
recursive linear combination and composition of networks
$\Psi_{\beta_{\ell}}:\bm{\theta}\in\Theta\mapsto\mathbb{R}$ and
$\Psi_{\beta_{\ell}^{\prime}}:\Psi_{z_{\ell}}(\bm{\theta})\in\mathbb{R}\mapsto\mathbb{R}$
for $\ell=1,\dotsc,L_{FF}-1$. The construction of the network
$\Psi_{z_{L_{FF}}}$ itself is analogous to the one dimensional case, but the
source channel now has width $d$ to accommodate the $d$-dimensional input
$\bm{\theta}$. Hence the overall complexity can be bounded as

$\displaystyle L(\Psi_{z_{L_{FF}}})$
$\displaystyle\leq\bar{C}(L_{FF}-1)(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\bar{\Omega}\rceil));$
$\displaystyle W(\Psi_{z_{L_{FF}}})$ $\displaystyle\leq 9W_{FF}+d+1,$

for constants $\bar{C}>1,\bar{\Omega}\geq\pi/2$.

Continuing, the proof of Lemma 10 for $d=1$ extends naturally in the case
$d\geq 2$. In particular, we find that a Fourier features network $\Phi$
realizing the function $f_{\Phi}$ and approximating $f\in S$ can in turn be
approximated to a tolerance $\varepsilon$ by a ReLU network $\Psi_{f_{\Phi}}$
with complexity satisfying

$\displaystyle L(\Psi_{f_{\Phi}})$ $\displaystyle\leq
CL_{FF}(\log_{2}^{2}(\varepsilon^{-1})+\log_{2}(\lceil\Omega\rceil));$
$\displaystyle W(\Psi_{f_{\Phi}})$ $\displaystyle\leq 9W_{FF}+d+1,$

for constants $\Omega\geq\pi/2,C>1$. From here the proof of Theorem 1 in the
case $d\geq 2$ is analogous to that for $d=1$.

##  6 Conclusion

In this work, we derived error and complexity estimates for ReLU networks
applicable to target functions with absolutely integrable Fourier transforms.
In particular, we showed that the network approximation error can be bounded
above by a quantity proportional to the uniform norm of the target function,
inversely proportional to the product of network width and depth, and with
constant of proportionality that scales weakly with the regularity of the
target function. Our proof involved the constructive approximation of a
Fourier features residual network by a ReLU network of quantifiable
complexity. This task was facilitated by our extension of the neural network
constructive approximation tool known as special ReLU networks, first
developed in [4], to handle neural networks with multidimensional input spaces
and also to facilitate recursive network linear combination and composition.

Similar to other neural network approximation error and complexity estimates,
Theorem 1 and Theorem 2 are only provable in the limit of infinite training
data, and so their justified use in real world approximation tasks will
require a preponderance of empirical evidence evaluating their efficacy under
different data sparsity conditions. In this vein, these estimates have already
been successfully used to develop a ReLU network based multifidelity modeling
paradigm [5], and we direct readers to that work for numerical illustration of
the proved estimates. Further numerical verification will be the subject of
future work. In particular, we hypothesize that our derived estimates could be
useful in general scientific machine learning tasks where target function
regularity is unknown and training data is relatively sparse. Under these
conditions, we posit that the computation of the uniform norm, which appears
in both our approximation error and complexity estimates, will be more
accurately and reliably computable compared to quantities such as the modulus
of continuity, Barron norm, or Sobolev norm which appear in other estimates in
the literature.

Acknowledgements The authors would like to acknowledge the work of Anders
Szepessy and co-authors in [12] and thank him for introducing us to the
existing approximation error estimate for Fourier features residual networks.

This article has been authored by an employee of National Technology &
Engineering Solutions of Sandia, LLC under Contract No. DE-NA0003525 with the
U.S. Department of Energy (DOE). The employee owns all right, title and
interest in and to the article and is solely responsible for its contents. The
United States Government retains and the publisher, by accepting the article
for publication, acknowledges that the United States Government retains a non-
exclusive, paid-up, irrevocable, world-wide license to publish or reproduce
the published form of this article or allow others to do so, for United States
Government purposes. The DOE will provide public access to these results of
federally sponsored research in accordance with the DOE Public Access Plan
https://www.energy.gov/downloads/doe-public-access-plan.

## References

  * [1] Raman Arora, Amitabh Basu, Poorya Mianjy and Anirbit Mukherjee  “Understanding deep neural networks with rectified linear units”  In _arXiv preprint arXiv:1611.01491_ , 2016
  * [2] Andrew R Barron  “Universal approximation bounds for superpositions of a sigmoidal function”  In _IEEE Transactions on Information theory_ 39.3 IEEE, 1993, pp. 930–945
  * [3] George Cybenko  “Approximation by superpositions of a sigmoidal function”  In _Mathematics of Control, Signals and Systems_ 2.4 Springer, 1989, pp. 303–314
  * [4] Ingrid Daubechies et al.  “Nonlinear approximation and (deep) ReLU networks”  In _Constructive Approximation_ 55.1 Springer, 2022, pp. 127–172
  * [5] Owen Davis, Mohammad Motamed and Raúl Tempone  “Residual Multi-Fidelity Neural Network Computing”  In _arXiv preprint arXiv:2310.03572_ , 2023
  * [6] Dennis Elbrächter, Dmytro Perekrestenko, Philipp Grohs and Helmut Bölcskei  “Deep neural network approximation theory”  In _IEEE Transactions on Information Theory_ 67.5 IEEE, 2021, pp. 2581–2623
  * [7] Gerald B Folland  “Real analysis: modern techniques and their applications”  John Wiley & Sons, 1999
  * [8] Loukas Grafakos  “Classical Fourier analysis”  Springer, 2008
  * [9] Boris Hanin  “Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations”  In _Mathematics_ 7.10 MDPI AG, 2019, pp. 992  DOI: 10.3390/math7100992
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep residual learning for image recognition”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778
  * [11] Kurt Hornik, Maxwell Stinchcombe and Halbert White  “Multilayer feedforward networks are universal approximators”  In _Neural Networks_ 2.5 Elsevier, 1989, pp. 359–366
  * [12] Aku Kammonen et al.  “Smaller generalization error derived for a deep residual neural network compared with shallow networks”  In _IMA Journal of Numerical Analysis_ 43.5 Oxford University Press, 2023, pp. 2585–2632
  * [13] Yann LeCun, Yoshua Bengio and Geoffrey Hinton  “Deep Learning”  In _nature_ 521.7553 Nature Publishing Group UK London, 2015, pp. 436–444
  * [14] Moshe Leshno, Vladimir Ya Lin, Allan Pinkus and Shimon Schocken  “Multilayer feedforward networks with a nonpolynomial activation function can approximate any function”  In _Neural Networks_ 6.6 Elsevier, 1993, pp. 861–867
  * [15] Mohammad Motamed  “Approximation Power of Deep Neural Networks: an explanatory mathematical survey”  In _arXiv:2207.09511_ , 2022  arXiv:2207.09511 [cs.LG]
  * [16] P. Petersen and F. Voigtlaender  “Optimal approximation of piecewise smooth functions using deep ReLU neural networks”  In _Neural Networks_ 108, 2018, pp. 296–330
  * [17] Allan Pinkus  “Approximation theory of the MLP model in neural networks”  In _Acta Numerica_ 8 Cambridge University Press, 1999, pp. 143–195
  * [18] Zuowei Shen, Haizhao Yang and Shijun Zhang  “Optimal approximation rate of ReLU networks in terms of width and depth”  In _Journal de Mathématiques Pures et Appliquées_ 157 Elsevier, 2022, pp. 101–135
  * [19] Jonathan W Siegel  “Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev Spaces”  In _arXiv preprint arXiv:2211.14400_ , 2022
  * [20] Jonathan W Siegel and Jinchao Xu  “Approximation rates for neural networks with general activation functions”  In _Neural Networks_ 128 Elsevier, 2020, pp. 313–321
  * [21] Jonathan W Siegel and Jinchao Xu  “High-order approximation rates for shallow neural networks with cosine and ReLUk activation functions”  In _Applied and Computational Harmonic Analysis_ 58 Elsevier, 2022, pp. 1–26
  * [22] Elias M Stein and Rami Shakarchi  “Real analysis: measure theory, integration, and Hilbert spaces”  Princeton University Press, 2009
  * [23] Dmitry Yarotsky  “Error bounds for approximations with deep ReLU networks”  In _Neural Networks_ 94 Elsevier, 2017, pp. 103–114
  * [24] Dmitry Yarotsky  “Optimal approximation of continuous functions by very deep ReLU networks”  In _Conference on Learning Theory_ , 2018, pp. 639–649  PMLR

##  Appendix A Conversions between special and standard ReLU networks

Consider converting a special ReLU network
$\tilde{f}_{\Psi}\in\mathcal{N}^{D_{1},D_{2},d}_{W,L}$ to a standard ReLU
network. Such an operation relies on the following observations.

  * •

If $\bm{\theta}\in[D_{1},D_{2}]^{d}$ contains only non-negative components,
then $\bm{\theta}=\sigma(\bm{\theta})$, and the assumption that the source
channel is ReLU free is not restrictive. However, if there are one or more
negative components present in any $\bm{\theta}$, then converting from a
special network to a standard network requires increasing the width of the
source channel from $d$ to $2d$ and making use of the identity
$\sigma(\bm{\theta)}-\sigma(-\bm{\theta})=\bm{\theta}$. An example of such a
modification for a one dimensional input $\theta$ is pictured in Figure 10.

Figure 10: Source channel modification

The circular neurons represent the source channel while the rectangles
represent the main computational channels of the network. We increase the
width of the source channel from $1$ to $2$ and make use of the identity
$\sigma(\theta)-\sigma(-\theta)=\theta$ to provide for identity mapping of the
input $\theta$.

  * •

The first bottom neuron takes $0$, and since $\sigma(0)=0$ the ReLU free
assumption is not restrictive. Any bottom neuron in the remaining $L-1$ hidden
layers ($\ell=1,\dotsc,L-1$) takes an input function $g_{\ell}(\bm{\theta})$
that depends continuously on $\bm{\theta}$. Hence there exists a constant
$C_{\ell}$ such that $g_{\ell}(\bm{\theta})+C_{\ell}\geq 0$ for every
$\bm{\theta}\in[D_{1},D_{2}]^{d}$, e.g. we may set
$C_{\ell}:=-\min_{\bm{\theta}}g_{\ell}(\bm{\theta})$. This implies that
$g_{\ell}(\bm{\theta})=\sigma(g_{\ell}(\bm{\theta})+C_{\ell})-C_{\ell}$. Using
this procedure to modify the bias in each of the collation neurons and
subtracting $\sum_{\ell}C_{\ell}$ from the bias in the output neuron yields a
re-paremeterization of a type 1 special network into a standard ReLU network.
Such a re-parameterization scheme was first introduced in [4]. For type 2
networks, the same modification of the biases in the collation and output
neuron(s) is required in addition to a slightly more complicated procedure
that relies on Lemma 11 below.

######  Lemma 11 (Shifted input re-parameterization).

Let $D_{1},D_{2}\in\mathbb{R}$ with $D_{1}<D_{2}$ and $W,L\in\mathbb{N}$. Let
$\Psi_{1}$ be a neural network realizing the function
$f_{\Psi_{1}}\in\mathcal{N}^{D_{1},D_{2},1}_{W,L}$. Then for any
$C\in\mathbb{R}$, there exists a ReLU network $\Psi_{2}$ realizing the
function $f_{\Psi_{2}}\in\mathcal{N}^{D_{1}+C,D_{2}+C,1}_{W,L}$ such that for
any $\theta\in[D_{1},D_{2}]$, $f_{\Psi_{1}}(\theta)=f_{\Psi_{2}}(\theta+C)$.

###### Proof.

The proof is constructive. The parameters
$\Psi_{2}=\\{M_{\Psi_{2}}^{(\ell)},\bm{b}_{\Psi_{2}}^{(\ell)}\\}_{\ell=0}^{L}$
of the network $f_{\Psi_{2}}$ can be determined as a function of the
parameters
$\Psi_{1}=\\{M_{\Psi_{1}}^{(\ell)},\bm{b}_{\Psi_{1}}^{(\ell)}\\}_{\ell=0}^{L}$
of $f_{\Psi_{1}}$ and the constant $C$. Indeed, the weight matrices and bias
vectors associated with $f_{\Psi_{1}}$ and $f_{\Psi_{2}}$ can be taken
identical aside from the small modification

$\bm{b}^{(0)}_{\Psi_{2}}=\bm{b}^{(0)}_{\Psi_{1}}-CM^{(0)}_{\Psi_{1}}.$

In doing this modification, the output of the first hidden layer of the
network $f_{\Psi_{2}}$ is

$\sigma(M^{(0)}_{\Psi_{1}}(\theta+C)+\bm{b}^{(0)}_{\Psi_{1}}-M^{(0)}_{\Psi_{1}}C)=\sigma(M^{(0)}_{\Psi_{1}}\theta+\bm{b}^{(0)}_{\Psi_{1}}),$

which is identical to the output of the first hidden layer of $f_{\Psi_{1}}$.
Then since the rest of the network parameters of both and $f_{\Psi_{1}}$ and
$f_{\Psi_{2}}$ are identical the result follows. ∎

Each time a collation neuron passes its collected computations back into the
main computational channels of the network, the biases of the neurons in the
main computational channel that are directly connected to the collation neuron
need to be modified as a function of the special network weights and the
constant $C_{\ell}$ in accordance with Lemma 11.

Now, given these observations, the relation between the parameters
$\tilde{\Psi}=\\{(\tilde{M}^{(\ell)},\tilde{\bm{b}}^{(\ell)})\\}_{\ell=0}^{L}$
of the special network and the parameters
$\Psi=\\{(M^{(\ell)},\bm{b}^{(\ell)})\\}_{\ell=0}^{L}$ of the corresponding
standard network depend on whether or not the special network is type 1 or
type 2. If the special network is type 1, then the relation between the
network parameters is given by,

$\displaystyle{M}^{(\ell)}=\tilde{M}^{(\ell)},\qquad\ell=0,\dotsc,L,$
$\displaystyle b_{j}^{(0)}=\tilde{b}_{j}^{(0)},\qquad j=1,\dotsc W-1,$
$\displaystyle
b_{j}^{(\ell)}=\begin{cases}\tilde{b}_{j}^{(\ell)},&j=1,\dotsc,W-1\\\
\tilde{b}_{j}^{(\ell)}+C_{\ell},&j=W\end{cases}\qquad\ell=1,\dotsc,L-1,$
$\displaystyle b^{L}=\tilde{b}^{L}-\sum_{\ell=1}^{L-1}C_{\ell},$

and if the network is type 2, then the finding the relation between parameters
depends on Lemma 11 and is given by,

$\displaystyle{M}^{(\ell)}=\tilde{M}^{(\ell)},\qquad\ell=0,\dotsc,L,$
$\displaystyle b_{j}^{(0)}=\tilde{b}_{j}^{(0)},\qquad j=1,\dotsc W-1,$
$\displaystyle
b_{j}^{(\ell)}=\begin{cases}\tilde{b}_{j}^{(\ell)}&j=1,\dotsc,d\\\
\tilde{b}_{j}^{(\ell)}-C_{\ell}\tilde{M}^{(\ell)}_{jW},&j=d+1,\dotsc,W-1,\\\
\tilde{b}_{j}^{(\ell)}+C_{\ell},&j=W\end{cases}\qquad\ell=1,\dotsc,L-1$
$\displaystyle b^{L}=\tilde{b}^{L}-\sum_{\ell=1}^{L-1}C_{\ell}.$

Additionally, in the case when there exists $\bm{\theta}\in[D_{1},D_{2}]^{d}$
that contains negative valued components, then converting from a special to
standard network requires expanding the width of the source channel from $d$
to $2d$ neurons. The additional $d$ neurons are referred to by negative
indices $-(d-1),\dotsc,0$, and the network parameters (weights and biases)
associated with these added neurons are described below.

$\displaystyle M^{(0)}_{jk}=-1,\qquad j=-(d-1),\dotsc,0,\qquad k=1,\dotsc,d$
$\displaystyle M^{(\ell)}_{jk}=\begin{cases}-1,&j=d,\dotsc,W-1,\qquad
k=-(d-1),\dotsc,0\\\ 1,&j=-(d-1),\dotsc,0,\qquad k=-(d-1),\dotsc,0\\\
0,&j=-(d-1),\dotsc,0,\qquad k=1,\dotsc,d\\\ 0,&j=1,\dotsc,d,\qquad\qquad
k=-(d-1),\dotsc,0\end{cases}\qquad\ell=1,\dotsc,L-1$ $\displaystyle
b^{(\ell)}_{j}=0,\qquad j=-(d-1),\dotsc,0,\qquad\ell=0,\dotsc,L-1$

We note here that regardless of the type of special network, the source
channel modification is the same.

##  Appendix B Auxiliary Proofs

Proof of Lemma 2. Let $\bm{g}_{j}$ denote the output of the final hidden layer
of network $f_{\Psi_{j}}$, let $b^{(L)}_{j}$ be the output bias associated
with network $f_{\Psi_{j}}$, and let $M^{(L)}_{j}$ be the output weights
associated with network $f_{\Psi_{j}}$ for any $j=1,\dotsc,J$. Then the output
of network $f_{\Psi_{j}}$ is given by $\bm{g}_{j}M^{(L)}_{j}+b^{(L)}_{j}$. The
network realizing the desired linear combination can be built as pictured in
Figure 11.

Figure 11: Network forming linear combination
$\sum_{j=1}^{J}a_{j}f_{\Psi_{j}}$

Each output weight matrix $M^{(L)}_{j}$ is multiplied by the corresponding
constant $a_{j}$, and all constituent networks $f_{\Psi_{j}}$ are made to
share a single output neuron with bias $\sum_{j=1}^{J}a_{j}b^{(L)}_{j}$. Then
a direct calculation shows that the full network computes
$\sum_{j=1}^{J}a_{j}(M^{(L)}_{j}g_{j}+b^{(L)}_{j})=\sum_{j=1}^{J}a_{j}f_{\Psi_{j}}$,
and by construction the resulting network has width $W=\sum_{j}W_{j}$ and
depth $L$.

Proof of Lemma 5.This proof proceeds constructively. The type 1 special
network pictured in Figure 12

Figure 12: Type 1 special network producing
$a_{0}\,\theta+\sum_{j=1}^{m}a_{j}\,h^{\circ j}(\theta)$

computes the desired linear combination of compositions of $h$. The
rectangular blocks $h$ are a condensed representation of the neural networks
$h\in\mathcal{N}^{D_{1},D_{2},d}_{W,L}$. Notice that the output of each
network $h$ feeds into the next network $h$ indicating composition. By Lemma 1
this type of composition can be done with no added width and additive depth,
meaning the full network has depth $mL$. The bottom neurons form a collation
channel that collects and sums the contributions of the network after each new
copy of $h$. Since each network $h$ accepts as input the output of the
previous copy, this collation channel is collecting a sum of weighted
compositions of successively longer length. The first pictured neuron in the
collation channel contains $a_{0}\theta$, the second contains
$a_{0}\theta+a_{1}h(\theta)$, and it continues in this manner. In general, the
$(j+1)st$ pictured bottom neuron contains
$a_{0}\theta+\sum_{k=1}^{j}a_{k}h^{\circ k}(\theta)$. Given the constructive
nature of the proof the width of the resulting network can be calculated
directly as $W+2$.

######  Remark B.1.

In Figure 12, although just one source and one collation neuron is pictured
for each network $h$, this is just done to simplify the figure. Indeed, there
are source and collation neurons present for each and every hidden layer of
each copy of $h$.

Proof of Lemma 6. The proof is fully constructive with the help of type 2
special networks. Indeed the type 2 special network displayed in Figure 13
realizes $p_{J}$ in the case that $d=1$.

Figure 13: Type 2 special ReLU network realizing $p_{J}$ with $d=1$

The extension to $d>1$ is straightforward and can be accomplished by
increasing the width of the source channel to $d$. Similar to previous network
diagrams we only picture one source and collation neuron per constituent
network, but this is just done to simplify the figure. There are in fact
source and collation neurons present for each of the hidden layers of each of
the constituent networks. For this particular network structure, the collation
channel only accepts outputs from the final hidden layer of each of the
constituent networks $h_{j}$ and $h_{j}^{\prime}$. This is in no conflict with
our definition of collation channel as incoming and outgoing weights between
collation neurons and neurons in the main computational channels can always be
set to zero. Given the constructive nature of the proof, the network
complexity can be calculated directly. Indeed the width of the type 2 network
is the width $W$ of the constituent networks $h_{j}$ and $h_{j}^{\prime}$ plus
a width $d$ source channel and width $1$ collation channel yielding an overall
width of $W+d+1$. Furthermore, the depth is additive with respect to the
constituent networks yielding an overall depth of
$\sum_{j=1}^{J-1}(L_{j}+L_{j}^{\prime})$.

Proof: density of $S_{c}$ in $S$. Here we show that $S_{c}$ is dense in $S$
with respect to the $L^{p}$ norm for $1\leq p<\infty$. Recall the form of the
sets $S$ and $S_{c}$,

$\displaystyle S$
$\displaystyle=\\{f:\Theta=[0,1]^{d}\mapsto\mathbb{R}:||\hat{f}||_{L^{1}(\mathbb{R}^{d})}<\infty\\}$
$\displaystyle S_{c}$ $\displaystyle=\\{f\in S:\hat{f}\text{ has compact
support}\\}.$

We claim that $S_{c}$ is dense in $S$ with respect to $||\cdot||_{L^{p}}$ for
any $1\leq p<\infty$. Let $\varepsilon>0$ and $f\in S$. Then
$||f||_{L^{\infty}(\Theta)}\leq||\hat{f}||_{L^{1}(\mathbb{R}^{d})}<\infty$,
and since $\Theta$ is compact this implies $f\in L^{p}(\Theta)$ for all $1\leq
p<\infty$. Define

$\bar{f}(\bm{\theta})=\begin{cases}f(\bm{\theta})&\bm{\theta}\in\Theta\\\
0&\bm{\theta}\in\mathbb{R}^{d}\setminus\Theta.\end{cases}$

Then $\bar{f}\in L^{p}(\mathbb{R}^{d})$ for all $1\leq p\leq\infty$. Now since
the Fourier transform is an automorphism of Schwarz space there exists a
Schwarz function $\varphi:\mathbb{R}^{d}\mapsto\mathbb{R}$ satisfying the
following properties:

  * •

$\int_{\mathbb{R}^{d}}\varphi\>d\bm{\theta}=1$

  * •

$||\varphi||_{L^{p}(\mathbb{R}^{d})}<\infty$ for all $1\leq p<\infty$

  * •

$\hat{\varphi}$ has compact support.

Further define the family of functions $\\{\varphi_{\lambda}\\}_{\lambda>0}$
by the dilation $\varphi_{\lambda}=\lambda^{d}\varphi(\lambda\bm{\theta})$.
Such an operation makes $\\{\varphi_{\lambda}\\}_{\lambda>0}$ an approximation
to the identity [8] satisfying

  * •

$\int_{\mathbb{R}^{d}}\varphi_{\lambda}\>d\bm{\theta}=1$

  * •

$||\varphi_{\lambda}||_{L^{p}(\mathbb{R}^{d})}<\infty$ for all $1\leq
p<\infty$

  * •

For any $\delta>0$,
$\lim_{\lambda\to\infty}\int_{\mathbb{R}^{d}\setminus\overline{B_{\delta}(\bm{0})}}|\varphi_{\lambda}|\>d\bm{\theta}=0$.

Additionally, notice that
$\hat{\varphi}_{\lambda}=\hat{\varphi}(\bm{\omega}/\lambda)$ and so
$\hat{\varphi}_{\lambda}$ has compact support for all $\lambda>0$. Now define
$g_{\lambda}=\bar{f}*\varphi_{\lambda}$, and
$g^{\Theta}_{\lambda}=g_{\lambda}|_{\Theta}$. Since $\bar{f}$ and
$\varphi_{\lambda}$ are both in $L^{1}(\mathbb{R}^{d})$ and $\bar{f}$ is
additionally in $L^{\infty}(\mathbb{R}^{d})$, Young’s inequality tells us that
$g_{\lambda}\in L^{1}(\mathbb{R}^{d})\cap L^{\infty}(\mathbb{R}^{d})$. It then
follows that $||g^{\Theta}_{\lambda}||_{L^{\infty}(\Theta)}<\infty$ as well.
Furthermore, we have $\hat{g}_{\lambda}=\hat{\bar{f}}\hat{\varphi}_{\lambda}$,
and since $\hat{\varphi}_{\lambda}$ has compact support so does
$\hat{g}_{\lambda}$ and $\hat{g}_{\lambda}^{\Theta}$. Continuing, this compact
support also implies

$||\hat{g}^{\Theta}_{\lambda}||_{L^{1}(\mathbb{R}^{d})}\leq||\hat{g}_{\lambda}||_{L^{1}(\mathbb{R}^{d})}\leq||g_{\lambda}||_{L^{1}(\mathbb{R}^{d})}\cdot\text{supp}(\hat{\varphi}_{\lambda})<\infty.$

Overall then $g^{\theta}_{\lambda}\in S_{c}$ for all $\lambda$. Finally, we
find

$\lim_{\lambda\to\infty}||g^{\Theta}_{\lambda}-f||_{L^{p}(\Theta)}\leq\lim_{\lambda\to\infty}||g_{\lambda}-\bar{f}||_{L^{p}(\mathbb{R}^{d})}\leq\varepsilon.$

where the right inequality which indicates convergence in norm is a well known
result that is true for any $L^{p}$ function in convolution with an
approximation of the identity, for example see [8, 22, 7].