# Qualitative neural network approximation over $\mathbb{R}$ and $\mathbb{C}$:
Elementary proofs for analytic and polynomial activation

Josiah Park  Josiah Park
Department of Mathematics
Texas A&M University
155 Ireland Street
College Station, TX 77840<EMAIL_ADDRESS>and  Stephan Wojtowytsch  Stephan
Wojtowytsch
Department of Mathematics
Texas A&M University
155 Ireland Street
College Station, TX 77840<EMAIL_ADDRESS>
###### Abstract.

In this article, we prove approximation theorems in classes of deep and
shallow neural networks with analytic activation functions by elementary
arguments. We prove for both real and complex networks with non-polynomial
activation that the closure of the class of neural networks coincides with the
closure of the space of polynomials. The closure can further be characterized
by the Stone-Weierstrass theorem (in the real case) and Mergelyan’s theorem
(in the complex case). In the real case, we further prove approximation
results for networks with higher-dimensional harmonic activation and
orthogonally projected linear maps.

We further show that fully connected and residual networks of large depth with
polynomial activation functions can approximate any polynomial under certain
width requirements. All proofs are entirely elementary.

###### Key words and phrases:

Uniform approximation theorem, approximation of holomorphic functions,
approximation of harmonic functions, holomorphic neural network, complex
analytic activation function, real analytic activation function, polynomial
activation function, shallow neural network, deep residual network, DenseNet

###### 2020 Mathematics Subject Classification:

68T07, 41A30, 41A10, 32A05

##  1\. Introduction

Neural networks are becoming increasingly popular tools in fields outside of
the classical domain of data science. Chief among these applications are
experiments in scientific computing, which often involve the solution of
potentially high-dimensional partial differential equations. In many important
problems – e.g. computations involving quantum systems with many particles –
the output of the neural network may be complex valued. For such problems, the
approximation power of complex neural networks with activation functions
$\sigma:\mathbb{C}\to\mathbb{C}$ has recently come under investigation[GDW+21,
TBZ+17, TBC+16, VSL17], and sufficient conditions were established for
$\sigma$ under which (shallow, deep) neural networks can approximate any
continuous function on a compact subset of $\mathbb{C}^{d}$ [Voi20].

It is a well-known fact that the field of complex numbers and the algebra of
complex-differentiable functions behave in surprising ways when compared to
the analogous objects of real analysis. For instance, if
$D\subseteq\mathbb{C}$ is a bounded open set, the space of functions
$f:\overline{D}\to\mathbb{C}$ which are complex differentiable in $D$ and
continuous on $\overline{D}$ form a proper closed subspace of the space of
continuous functions on $\overline{D}$. In particular there exists a
continuous function $f:\overline{D}\to\mathbb{C}$ such that
$\|f-p\|_{C^{0}(\overline{D})}\geq 1$ for all polynomials $p$. This contrasts
drastically with the situation in real analysis, where polynomials are dense
in the space of continuous functions on a compact set as established by the
Stone-Weierstrass theorem.

A similar observation can be made in classes of neural networks. For a
function $\sigma:\mathbb{C}\to\mathbb{C}$ and a set of parameters

$\Theta:=\big{\\{}(a_{k},w_{k},b_{k})\in\mathbb{C}\times\mathbb{C}^{d}\times\mathbb{C}:k=1,\dots,n\\},$

we define

$f_{\Theta}(z)=\sum_{k=1}^{n}a_{k}\,\sigma\big{(}\langle
w_{k},z\rangle+b_{k}\big{)}$

where $z=(z_{1},\dots,z_{d})\in\mathbb{C}^{d}$ is a complex vector and
$\langle w,z\rangle=\sum_{i=1}^{d}\overline{w}_{i}\cdot z_{i}$. We denote the
set of all such functions with a fixed number $n$ of ‘neurons’ by
${\mathcal{M}}_{\sigma,n}$ and
${\mathcal{M}}_{\sigma}=\bigcup_{n=1}^{\infty}{\mathcal{M}}_{\sigma,n}$. The
following observations are immediate:

  1. (1)

If $\sigma$ is a polynomial in of degree $m$ in one complex variable, then
$f_{\Theta}$ is a polynomial of degree $m$ in $d$ complex variables.

  2. (2)

If $\sigma$ can be represented by a convergent power series on $\mathbb{C}$,
then $f_{\Theta}$ can be represented by a convergent power-series in $d$
complex variables.

In particular, if $D\subseteq\mathbb{C}$ is open, there exists a continuous
function $f:\overline{D}\to\mathbb{C}$ which cannot be approximated by
functions of the form (1). Depending on the application, this ‘rigidity’ may
be an asset or an obstacle. Encoding a priori information about the solution
of a problem (often referred to as ‘domain knowledge’) in the neural network
architecture has proved invaluable in many tasks, for example by designing
convolutional neural networks to approximately respect translation invariance
[ON15], using periodic activation functions in signal processing [ADd+96,
SMB+20, XN21b, XN21a], designing specialized neural networks for data in
hyperbolic spaces [CYRL19, GBH18, LNK19, PVM+21] or directly enforcing
physical symmetries in computational chemistry [Zha18, CZWE20]. By analogy, if
we can show that the solution to a problem in scientific computing is given by
a holomorphic function or operator, it serves us well to encode this into the
design of our neural network.

The question remains: When trying to approximate a holomorphic function
$f:D\subseteq\mathbb{C}^{d}\to\mathbb{C}$, which activation functions can be
used? We present an approximation theorem which treats complex and real
shallow neural networks in a unified fashion.

######  Theorem 1.1.

Let ${\mathbb{K}}\in\\{\mathbb{R},\mathbb{C}\\}$ and let

$\sigma:{\mathbb{K}}\to{\mathbb{K}},\qquad\sigma(z)=\sum_{k=0}^{\infty}\alpha_{k}z^{k}$

be an analytic function defined by a power series with infinite radius of
convergence. Consider the class of shallow neural networks of arbitrary finite
width $n$ with activation $\sigma$

${\mathcal{M}}_{\sigma}=\bigcup_{n=1}^{\infty}{\mathcal{M}}_{\sigma,n},\qquad{\mathcal{M}}_{\sigma,n}=\left\\{\sum_{k=1}^{n}a_{k}\,\sigma\big{(}\langle
w_{k},z\rangle+b_{k}\big{)}:(a_{k},w_{k},b_{k})\in{\mathbb{K}}\times{\mathbb{K}}^{d}\times{\mathbb{K}}\right\\}.$

Let $D\subseteq{\mathbb{K}}^{d}$ be an open bounded subset and denote by
$C^{0}(\overline{D})$ the space of continuous functions from $\overline{D}$ to
${\mathbb{K}}$.

  1. (1)

If $\sigma$ is a polynomial of degree $m$ in $z$, then
${\mathcal{M}}_{\sigma}$ is the space ${\mathcal{P}}_{m}$ of polynomials of
degree $m$ in $z$.

  2. (2)

If $\sigma$ is a not a polynomial, then the closures of
${\mathcal{M}}_{\sigma}$ and
${\mathcal{P}}:=\bigcup_{m=0}^{\infty}{\mathcal{P}}_{m}$ in
$C^{0}(\overline{D})$ coincide.

If ${\mathbb{K}}=\mathbb{R}$, we can now recover the classical universal
approximation theorem for networks with analytic activation by appealing the
Stone-Weierstrass theorem [K0̈4, Section 15.7]:

######  Theorem (Stone-Weierstrass Theorem).

Let $K\subset\mathbb{R}^{d}$ be compact and $\mathcal{P}$ the vector space of
polynomials. Then $\mathcal{P}$ is dense in $C^{0}(K)$.

While the result is restrictive due to the strong assumptions on $\sigma$, our
proof is entirely elementary and does not require advanced techniques beyond
an introductory class in (real, complex) analysis.

If ${\mathbb{K}}=\mathbb{C}$, we emphasize that $\sigma$ is analytic in $z$,
not $(z,\bar{z})$ or $(x,y)$, and that the elements of ${\mathcal{P}}_{m}$ are
equally polynomials in the complex variable $z$. The closure of
${\mathcal{P}}$ depends on the topology of the set $D$. If
$D=\\{z\in\mathbb{C}:r<|z|<R\\}$ is an annular domain and $k\in\mathbb{N}$,
then the function $f(z)=z^{-k}$ is holomorphic on $U$, but cannot be
approximated by polynomials. This follows from Cauchy’s integral formula
[FB93, Theorem II.3.2] as

$\int_{\gamma}z^{k-1}f(z)\cdot\,\mathrm{d}z=2\pi
i,\qquad\int_{\gamma}z^{k-1}\,p(z)\cdot\,\mathrm{d}z=0$

for all polynomials $p$ and all curves $\gamma$ in $D$ which loop around the
origin. If there were polynomials which could approximate $f$ uniformly, also
the integrals would have to converge.

On the positive side, in 1951 Mergelyan [Mer51] showed the following [Rud87,
Theorem 20.5]:

######  Theorem (Mergelyan’s Theorem).

Let $K\subseteq\mathbb{C}$ be compact such that $\mathbb{C}\setminus K$ is
connected, and $f:K\to\mathbb{C}$ a continuous function which is holomorphic
in the interior $K^{\circ}$ of $K$. Then for every $\varepsilon>0$, there
exists a complex polynomial $P$ such that $\sup_{z\in
K}|f(z)-p(z)|<\varepsilon$.

The class of ‘good’ domains in particular includes all simply connected
bounded open sets with Lipschitz boundary. The situation in many complex
variables is more complicated and not entirely understood. While multi-variate
Mergelyan-type theorems [FGMN21, Gub15, Cho98] and related results like the
Oka-Weil Theorem [Oka61, Wei35] have been obtained, there are obstructions to
proving the statement in full generality. Notably, Diederich and Fornaess
[DF76] constructed an example of a pseudoconvex domain
$D\subseteq\mathbb{C}^{2}$ with smooth boundary and a continuous function
$f:\overline{D}\to\mathbb{C}$ such that $f$ is holomorphic in $D$, but cannot
be approximated uniformly by polynomials in $\overline{D}$. Thus even for
functions of multiple complex variables which can be shown to be holomorphic
on a ‘good’ domain, there may be deep obstructions to approximation by both
polynomials and holomorphic neural networks. A recent survey of holomorphic
approximation can be found e.g. in [FsFW20].

While holomorphic functions can be thought of simultaneously as a
generalization of differentiable functions and infinitely differentiable
functions, the perhaps closest analogue in real analysis is the class of
harmonic functions. In two dimensions, a correspondence between harmonic and
holomorphic functions on $\mathbb{C}=\mathbb{R}^{2}$ can be constructed by
taking the real part of a function, which is one-to-one up to an affine shift
in the imaginary part. Like holomorphic functions, harmonic functions in any
dimension form a closed proper subspace of $C^{0}(\overline{D})$ for open
bounded $D\subseteq\mathbb{R}^{d}$. For a deeper understanding of complex-
analytic rigidity, we study real neural networks with harmonic activation
functions.

Since harmonic functions in one real dimension are just affine linear, the
interesting case concerns activation functions $\sigma$ of two or more real
variables. Furthermore, we restrict the linear representation of data to be
angle-preserving projections. Namely, if $\sigma:\mathbb{R}^{k}\to\mathbb{R}$
is harmonic, we consider a class of functions on $\mathbb{R}^{d}$ for $d\geq
k$ given by
${\mathcal{M}}_{\sigma}=\bigcup_{n=1}^{\infty}{\mathcal{M}}_{\sigma,n}$ where

${\mathcal{M}}_{\sigma,n}=\left\\{\sum_{i=1}^{n}a_{i}\sigma\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}:\rho_{i}\in\mathbb{R},\>b_{i}\in\mathbb{R}^{k},\>P_{i}\in\mathbb{R}^{k\times
d}\text{ s.t. }P_{i}P_{i}^{T}=I_{k\times k}\right\\}.$

Geometrically, the linear maps $P_{i}$ are orthogonal projections from
$\mathbb{R}^{d}$ to $\mathbb{R}^{k}$ for all $i$. It is easy to see that
$f\in{\mathcal{M}}_{\sigma}$ is harmonic, and thus that
${\mathcal{M}}_{\sigma}$ is at most dense in the space of harmonic functions.
We show the following.

######  Theorem 1.2.

Let $\sigma:\mathbb{R}^{k}\to\mathbb{R}$ be a harmonic function, $d\geq k$ and
$D\subseteq\mathbb{R}^{d}$ open and bounded.

  1. (1)

If $\sigma$ is a harmonic polynomial of degree $m$, then
${\mathcal{M}}_{\sigma}$ is the class of harmonic polynomials of degree $m$

$\mathcal{HP}_{m}(\mathbb{R}^{d})=\\{p\in{\mathcal{P}}_{m}(\mathbb{R}^{d}):\Delta\,p=0\\}.$

  2. (2)

If $\sigma$ is not a polynomial, then the closures of ${\mathcal{M}}_{\sigma}$
and $\mathcal{HP}=\bigcup_{m=0}^{\infty}\mathcal{HP}_{m}$ in
$C^{0}(\overline{D})$ coincide.

So far, we only considered shallow neural networks with two layers (i.e. one
hidden layer). While this case is historically well-studied, modern neural
networks are ‘deep’, i.e. they have many layers. To keep things simple, we
focus on functions $f:{\mathbb{K}}^{d}\to{\mathbb{K}}$ which are represented
by residual neural networks (ResNets), but comparable results can be obtained
for classical fully connected feedforward networks and DenseNets (see Appendix
C). Residual neural networks form a function class which is comparable to feed
forward networks in terms of approximation power, but with a parametrization
that facilitates gradient-based optimization to find appropriate network
parameters. The incremental nature of the change to the internal state in
every layer alleviates the vanishing and exploding gradients phenomenon, which
is the main motivation of the ResNets in [HZRS16]. For this reason, truly
‘deep’ networks typically have a form of residual structure. Continuum limits
for infinitely deep neural networks have been studied in [E17, LCTW17] and
later in [CRBD18] as ‘neural ODEs’.

A ResNet can be understood as follows.

  * •

Let $d_{0}\in\mathbb{N}$. For a given input $z\in\overline{D}$ and parameters
$A^{0}\in{\mathbb{K}}^{d_{0}\times d}$, $b^{0}\in{\mathbb{K}}^{d_{0}}$,
designate $z^{0}=A^{0}z+b^{0}\in{\mathbb{K}}^{d_{0}}$.

  * •

For $\ell\in\\{1,\dots,L-1\\}$ and parameters
$A^{\ell}\in{\mathbb{K}}^{d_{0}\times
D_{\ell}},W^{\ell}\in{\mathbb{K}}^{D_{\ell}\times
d_{0}},b^{\ell}\in{\mathbb{K}}^{D_{\ell}}$ for some $D_{\ell}\in\mathbb{N}$,
set

$z^{\ell}=z^{\ell-1}+A^{\ell}\,\sigma(W^{\ell}z^{\ell-1}+b^{\ell})$

where $\sigma$ is applied coordinatewise.

  * •

For parameters $A^{L}\in{\mathbb{K}}^{d_{0}}$, set $z^{L}=A^{L}z^{L-1}$.

As previously, we collect the weights in a single vector

$\Theta=\big{(}A^{0},b^{0},A^{1},b^{1},W^{1},\dots,A^{L-1},b^{L-1},W^{L-1},A^{L}\big{)}$

and denote $f_{\Theta}(z)=z^{L}$, where we suppressed the dependence of
$z^{L}$ on the input $x$ and weights $\Theta$ for the sake of compact
notation. It should be noted that sometimes in ResNets, the architecture is
specified further by taking $D_{\ell}\equiv d_{0}$ and $A^{\ell}$ as the unit
matrix.

Deeper neural networks have multiple parameters that govern their complexity:
The depth $L$ and the vector of widths $d^{0},D^{1},\dots,D^{L-1}$. The width
of the input layer $d$ and the output layer $d_{L}=1$ are given by the problem
statement. The notation therefore becomes somewhat less compact compared to
shallow networks. We denote the classes of ResNets with a fixed architecture
by $\mathcal{R}_{L,\sigma}(d_{0},D_{1},\dots,D_{L-1})$. We can now present our
third main result.

######  Theorem 1.3.

Let ${\mathbb{K}}\in\\{\mathbb{R},\mathbb{C}\\}$ and let

$\sigma:{\mathbb{K}}\to{\mathbb{K}},\qquad\sigma(z)=\sum_{n=0}^{\infty}\alpha_{n}z^{n}$

be an analytic function defined by a power series with infinite radius of
convergence. Let $U\subseteq{\mathbb{K}}^{d}$ be an open bounded subset.

  1. (1)

Let $L\geq 2$ be fixed, $d_{0}\geq d+1$ and $n:=D_{1}+\dots+D_{L-1}$. Then
${\mathcal{M}}_{\sigma,n}\subseteq\mathcal{R}_{L,\sigma}(d_{0},D_{1},\dots,D_{L-1})$.
In particular, if $\sigma$ is not a polynomial, then the closures of

$\mathcal{N}_{1}:=\bigcup_{D_{1}=1}^{\infty}\mathcal{R}_{L,\sigma}(d+1,D_{1},0,\dots,0),\qquad\mathcal{N}_{2}:=\bigcup_{L=1}^{\infty}\mathcal{R}_{L,\sigma}(d+1,m,m,\dots,m)$

and the closure of the space of polynomials $\mathcal{P}$ in
$C^{0}(\overline{D})$ coincide for all $m\geq 1$.

  2. (2)

If $\sigma$ is not a linear function, then the closure of

$\widetilde{\mathcal{N}_{2}}:=\bigcup_{L=1}^{\infty}\mathcal{R}_{L,\sigma}(d+2,m,\dots,m)$

and the closure of the space of polynomials $\mathcal{P}$ in
$C^{0}(\overline{D})$ coincide for all $m\geq 4$.

Roughly speaking, we only need to have the width of one layer go to infinity,
while all others remain bounded, or the depth go to infinity if $d_{0}\geq
d+1$. This is not surprising: In the first case, we approximate the target
function with the first hidden layer and the remaining layers are the identity
map, while in the second case, we ‘turn the shallow neural network on its
side’. This idea is classical and will be explained in greater detail below
for the reader’s convenience. The restriction that $d_{0}\geq d+1$ is equally
classical if the input dimension is $d\geq 2$, as there are obstructions to
universal approximation for thinner networks [Joh18].

The most interesting of the results given in Theorem 1.3 is the fact that
polynomial activation functions are admissible if the neural network is
slightly wider than before and we vary the depth rather than the width. This
is not entirely surprising since elements of
$\mathcal{R}_{L,\sigma}(d_{0},D_{1},\dots,D_{L-1})$ are polynomials of degree
at most $m^{L}$ if $\sigma$ is a polynomial of degree $m$. As $L\to\infty$,
the upper bound becomes less and less restrictive. Nevertheless, it is not
immediately obvious that we can in fact approximate all polynomials. We
believe the result to be folklore, but are not aware of a rigorous proof in
the literature.

The approximation properties of neural networks have been studied in great
detail by many authors over the course of at least three decades in [Cyb89,
Hor91, LLPS93, Bar93, Mak98, Pin99, MP99, ABMM18, ES16, Yar17, EW18, KB18,
EW20, MP16, KB18, PV18, SX19, YZ19, CJLZ19, SH19, PN21a, PN21b, SX20b, SX20a,
DHP21, DDD+21, DDF+22, GKNV22] to name only a few. The main goal of this
article is to provide a self-contained and elementary introduction to
qualitative versions of universal and qualified approximation theorems, not to
improve upon the state of the art in specific classes of functions. As such,
the proofs in the remainder of the article are elementary and require little
or no knowledge beyond undergraduate real and complex analysis. Nevertheless,
we maintain that several results, including the unified treatment of real and
complex networks, as well as the treatment of polynomial activation functions,
are at most folklore to the best of our knowledge. The main novel contribution
of these notes, the proof of Theorem 1.2 in Section 3, is the only place where
deeper results are used.

##  2\. Proof of Theorem 1.1: Shallow networks

In the real case, a version of this proof goes back to [Mha96].

###### Proof.

Step 1. Assume that $\sigma(z)=\sum_{j=0}^{\infty}\alpha_{j}z^{j}$. In this
step, we show that for any $m\in\mathbb{N}_{0}$, the function
$z\mapsto\alpha_{m}z^{m}$ can be approximated by a shallow neural network
$f_{m}\in{\mathcal{M}}_{\sigma,m+1}$ of the form (1) in one dimension. This
holds trivially in the case $m=0$, since $\sigma(0)=\alpha_{0}z^{0}$ and
$z\mapsto\sigma(0)=1\cdot\sigma(\langle
0,z\rangle+0)\in{\mathcal{M}}_{\sigma,1}$. For $m\geq 1$, note that

$\frac{d^{m}}{dh^{m}}\bigg{|}_{h=0}\sigma(hz)=\frac{d^{m}}{dh^{m}}\bigg{|}_{h=0}\sum_{j=0}^{\infty}a_{j}(hz)^{j}=m!\,\alpha_{m}z^{m}$

since power series and their derivatives converge locally uniformly, so
summation and differentiation commute [K0̈4, Sections 6.4 and 15.2]. The
$m$-th derivative of $\sigma$ is the limit of iterated difference quotients

$\frac{d^{m}}{dh^{m}}\sigma(hz)=\lim_{\gamma\to
0}\frac{\sum_{l=0}^{m}(-1)^{l}\binom{m}{l}\sigma\big{(}(h+l\gamma)z\big{)}}{\gamma^{m}}\
\text{ thus }\ \lim_{\gamma\to
0}\frac{\sum_{l=0}^{m}(-1)^{l}\binom{m}{l}\,\sigma\big{(}l\gamma
z\big{)}}{\gamma^{m}}=m!\,\alpha_{m}z^{m},$

where the limit holds uniformly in the set $|z|\leq R$ for any $R>0$.111 This
is a corollary to either the Mean Value Theorem or the Fundamental Theorem of
Calculus in real analysis, which easily applies to the complex case.
Strangely, it seems to be omitted in many textbooks on real analysis. A
reference in a somewhat more general setting can be found in [Lan93, Corollary
4.4]. Since

$z\mapsto\frac{1}{\gamma^{m}}\sum_{l=0}^{m}(-1)^{l}\binom{m}{l}\,\sigma\big{(}(h+l\gamma)z\big{)}\in{\mathcal{M}}_{\sigma,m+1}$

by definition, the result is proved.

Step 2. In this step, we show that if $a_{M}\neq 0$, then $z\mapsto z^{m}$ can
be approximated uniformly by elements of ${\mathcal{M}}_{\sigma}$ for any
$m\leq M$. The result is trivial for $m=M$, since we can divide by $a_{M}$.
For $m<M$, the result follows as previously by noting that

$\displaystyle z^{m}$
$\displaystyle=\frac{m!}{M!}\,\frac{d^{M-m}}{dz^{M-m}}z^{M}=\frac{m!}{M!}\,\lim_{\beta\to
0}\frac{\sum_{n=0}^{M-m}(-1)^{n}\binom{M-m}{n}(z+n\beta)^{M}}{\beta^{M-m}}$
$\displaystyle=\frac{m!}{a_{M}\cdot M!}\,\lim_{\beta\to 0}\lim_{\gamma\to
0}\frac{\sum_{n=0}^{M-m}\sum_{l=0}^{M}(-1)^{n+l}\binom{M}{l}\binom{M-m}{n}\,\sigma(l\gamma
z+n\beta)}{\beta^{M-m}\,\gamma^{M}},$

and noting that the approximating functions are elements of
${\mathcal{M}}_{\sigma,2M-m+2}$.

Step 3. From now on, we will consider the general case $d\geq 1$. Assume that
$\sigma$ is a polynomial of degree $m$. Then clearly
${\mathcal{M}}_{\sigma}\subseteq{\mathcal{P}}_{m}$ since

$\sum_{k=1}^{n}a_{k}\,\sigma(\langle
w_{k},z\rangle+b_{k})=\sum_{k=1}^{n}a_{k}\sum_{j=0}^{m}\alpha_{j}\big{(}\langle
w_{k},z\rangle+b_{k}\big{)}^{j}$

is a polynomial of degree $m$ in $d$ variables. On the other hand, we claim
that any polynomial $p$ of degree $m$ can be approximated uniformly by
elements of ${\mathcal{M}}_{\sigma}$. It suffices to consider the case that

$p(z)=z_{1}^{m_{1}}\dots z_{d}^{m_{d}}$

is a monomial of degree $\overline{m}:=m_{1}+\dots+m_{d}\leq m$. Then
$p\in\overline{{\mathcal{M}}_{\sigma}}$ by the same rationale as before since

$p(z)=\frac{1}{\overline{m}!}\,\frac{\partial^{\overline{m}}}{\partial_{h_{1}}^{m_{1}}\dots\partial_{h_{d}}^{m_{d}}}\big{(}h_{1}z_{1}+\dots+h_{d}z_{d}\big{)}^{\overline{m}}.$

By considering one-dimensional slices and Step 2, the function

$\big{(}h_{1}z_{1}+\dots+h_{d}z_{d}\big{)}^{\overline{m}}$

lies in $\overline{{\mathcal{M}}_{\sigma}}$ for any choice of
$h_{1},\dots,h_{d}$ and $\overline{m}$. As previously, also its difference
quotients in $h$ can be approximated by elements of ${\mathcal{M}}_{\sigma}$.
Since monomials can be approximated and ${\mathcal{M}}_{\sigma}$ is a linear
class, we find that
${\mathcal{P}}_{m}\subseteq\overline{{\mathcal{M}}_{\sigma}}$.

Step 4. If $d\geq 1$ and $\sigma$ is not a polynomial, then for every
$m\in\mathbb{N}_{0}$, there exists $M\geq m$ such that $a_{M}\neq 0$. As in
step 3, we can show that every polynomial of degree at most $m$ can be
approximated uniformly by elements $f_{m}\in{\mathcal{M}}_{\sigma}$. Taking
the union over $m\in\mathbb{N}$, we find that any polynomial can be
approximated uniformly by $f\in{\mathcal{M}}_{\sigma}$. By a standard diagonal
sequence argument, we conclude that
$\overline{\bigcup_{m=0}^{\infty}{\mathcal{P}}_{m}}\subseteq\overline{{\mathcal{M}}_{\sigma}}$.

On the other hand, let $f\in\subseteq\overline{{\mathcal{M}}_{\sigma}}$. Then,
for every $\varepsilon>0$, there exist $n\in\mathbb{N}$ and
$f_{n}\in{\mathcal{M}}_{\sigma,n}$ such that
$\|f_{n}-f\|_{C^{0}(\overline{D})}<\varepsilon/2$. Since

$f_{n}(z)=\sum_{k=1}^{n}a_{k}\,\sigma(\langle
w_{i},z\rangle+b_{i})=\lim_{m\to\infty}\sum_{j=1}^{m}\sum_{i=1}^{n}\alpha_{k}a_{i}\,\big{(}\langle
w_{i},z\rangle+b_{i}\big{)}^{m}$

uniformly in the set $|z|\leq R$ for any given $R>0$, we can truncate the
series for $f_{n}$ at an index $m$ such that

$\|f_{n,m}-f\|_{C^{0}(\overline{D})}\leq\|f_{n}-f\|_{C^{0}(\overline{D})}+\|f_{n}-f_{n,m}\|_{C^{0}(\overline{D})}<\varepsilon.$

As this can be done for any $\varepsilon>0$, we have
$f\in\overline{\bigcup_{m=0}^{\infty}{\mathcal{P}}_{m}}$. ∎

Since power series converge to their limit in $C^{k}$ for any
$k\in\mathbb{N}$,222 Since their derivatives, which are also power series,
converge uniformly. we find that
$\overline{{\mathcal{M}}_{\sigma}}\subseteq\overline{{\mathcal{P}}}$ also if
the closure is taken with respect to the $C^{k}$-topology. Conversely, since
the $m$-th difference quotient of a $C^{m+k}$-function also converges in
$C^{k}$, and since $\sigma\in C^{\infty}$, we can use the proof of Theorem 1.1
also to see that $\overline{P}\subseteq\overline{{\mathcal{M}}_{\sigma}}$ in
the $C^{k}$-topology.

######  Corollary 2.1.

Let ${\mathbb{K}}\in\\{\mathbb{R},\mathbb{C}\\}$ and let

$\sigma:{\mathbb{K}}\to{\mathbb{K}},\qquad\sigma(z)=\sum_{n=0}^{\infty}\alpha_{n}z^{n}$

be an analytic function defined by a power series with infinite radius of
convergence. Consider the class ${\mathcal{M}}_{\sigma}$ of shallow neural
networks of arbitrary finite width $n$ and activation $\sigma$ as before. Let
$D\subseteq{\mathbb{K}}^{d}$ be an open bounded subset, $k\geq 1$, and denote
by $C^{k}(\overline{D})$ the space of $k$ times differentiable functions from
$D$ to ${\mathbb{K}}$ such that the derivatives of all orders extend
continuously to the closure $\overline{D}$.

  1. (1)

If $\sigma$ is a polynomial of degree $m$, then ${\mathcal{M}}_{\sigma}$ is
the space ${\mathcal{P}}_{m}$ of polynomials of degree $m$.

  2. (2)

If $\sigma$ is a not a polynomial, then the closures of
${\mathcal{M}}_{\sigma}$ and
${\mathcal{P}}:=\bigcup_{m=0}^{\infty}{\mathcal{P}}_{m}$ in
$C^{k}(\overline{D})$ coincide.

In Corollary 2.1, we replaced the $C^{0}$-topology by the stronger
$C^{k}$-topology. Similarly, we could pass from a stronger topology like
$C^{0}$ or $C^{k}$ to a weaker one, like $L^{p}$ or $W^{k,p}$ and conclude
that the closures of ${\mathcal{P}}$ and ${\mathcal{M}}_{\sigma}$ coincide.

There exists a finite number of neurons $n$ that a shallow neural network of
the form (1) requires to approximate the function $z\mapsto z^{m}$ to
arbitrary accuracy. Reaching higher precision requires increasing the
magnitude of weights, but not the number of neurons. In particular, $n$
depends only on $m$ and on which coefficients of $\sigma$ in a power series
expansion are non-zero. It seems advantageous to choose activation functions
in which all coefficients are non-zero (such as $\exp$), or at least such that
there are no long gaps in the set of non-zero coefficients (such as
$\sin,\cos,\sinh,\cosh$). If all coefficients are non-zero, then the proof of
Theorem 1.1 also illustrates that the bias term $b_{i}$ in $\langle
w_{i},z\rangle+b_{i}$ is not needed to prove approximation results. This
explains the density of Fourier series in the space of continuous functions,
which are formally neural networks with a single hidden layer and the
activation function $\sigma(z)=\exp(2\pi iz)$. In a Fourier series, all biases
are set to zero.

The conditions on $\sigma$ in Theorem 1.1 can be weakened somewhat. To
approximate $z^{m}$ by elements of ${\mathcal{M}}_{\sigma}$, we ‘zoomed in’
suitably at the origin to utilize the power series expansion. In particular,
if $f$ can be represented by a convergent non-polyomial power series in a
neighbourhood of the origin on the real line, then every polynomial can be
approximated arbitrarily well by elements of ${\mathcal{M}}_{\sigma}$. This
applies in particular to real analytic activation functions like
$\tanh(x)=\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}$ or the sigmoid function
$\sigma(x)=\frac{1}{1+e^{-x}}$, whose power series representation does not
converge globally. Since polynomials are dense in the space of continuous
functions due to the Stone-Weierstrass Theorem [K0̈4, Section 15.7], it
follows that
$\overline{{\mathcal{M}}_{\sigma}}=\overline{{\mathcal{P}}}=C^{0}(\overline{D})$,
if the closure is taken in the uniform topology.

In the complex plane, the assumption that the radius of convergence of
$\sigma$ is $\infty$ is used to prove that elements of
${\mathcal{M}}_{\sigma}$ can be approximated by polynomials. It is implied by
the assumption that $\sigma$ is holomorphic on the entire plane $\mathbb{C}$,
since the radius of convergence can be characterized as the distance to the
closest singularity (which, in this case, is infinity) [Rud87, Theorem 16.2].
If ${\mathbb{K}}=\mathbb{C}$ and $\sigma$ is a rational function, then the
closure of ${\mathcal{M}}_{\sigma}$ may be strictly larger than that of the
space of polynomials (e.g. if $U$ is annular domain and the weights of the
network are chosen such that a pole of $\sigma$ is inside the hole in $U$). In
this situation ‘neural networks’ $f:\mathbb{C}\to\mathbb{C}$ with activation
$\sigma(z)=z^{-1}$ can approximate any meromorphic functions
$f:\mathbb{C}\to\overline{\mathbb{C}}$ in $C^{0}(K)$, if $f$ does not have a
singularity in $K$. The key observation is that any type of pole $z\mapsto
z^{-m}$ can be generated by a superposition of derivatives of $\sigma$.
Difference quotients approximate these derivatives uniformly away from the
singularity.

Of course, if $\sigma$ is a rational function (and not a polynomial), then
there exists $z^{*}\in\mathbb{C}$ such that $\lim_{z\to z^{*}}|f(z)|=\infty$.
When approximating a target function which is bounded on $\overline{D}$, the
weights should be chosen such that these poles lie outside of $\overline{D}$.
However, especially in the initial phase of training, the infinite gradients
of $f$ may lead to greater numerical instability, and there is no guarantee
that the domain $U$ is captured accurately by finite amounts of data. The
greater expressivity therefore comes with a not so hidden cost.

In the context of machine learning, obstructions to polynomial approximation
(in the complex case) would not be immediately visible: If
$\\{z_{1},\dots,z_{N}\\}\subset\mathbb{C}$ and
$\\{y_{1},\dots,y_{N}\\}\subset\mathbb{C}$ are finite data sets, then there
always exists a unique polynomial $P_{N}$ of degree $N$ such that
$P_{N}(z_{i})=y_{i}$ (assuming that all $z_{i}$ are different). In Lagrange
representation, we can write

$P_{N}(z)=\sum_{i=1}^{N}y_{i}\,\prod_{j\neq i}\frac{z-z_{j}}{z_{i}-z_{j}}.$

An exact interpolant can also be found in ${\mathcal{M}}_{\sigma,n}$ for
sufficiently large $n$, which may scale linearly with $N$ (depending on which
power series coefficients of $\sigma$ vanish). Even for functions which are
holomorphic on the data domain $D$, it is therefore imperative to understand
whether $f$ can be approximated by polynomials, as this cannot be determined
from a finite data set. At most we may notice that $P_{N}$ does not
approximate the function we expected at previously unseen data points (the
test set).

As another consequence of Cauchy’s integral formula, we recall the following
Liouville theorem.

######  Theorem (Liouville’s theorem).

If

$\limsup_{r\to\infty}\frac{\max\\{|\sigma(z)|:z\in
B_{r}(0)\\}}{r^{\alpha}}<\infty$

for some $\alpha>0$, then $\sigma$ is a polynomial of degree at most
$\lfloor\alpha\rfloor$ since the $\lfloor\alpha\rfloor+1$-th derivative of
$\sigma$ vanishes.

This version of Liouville’s Theorem can be proved by appealing to Cauchy’s
integral formula in a fashion virtually identical to the classical case
$\alpha=0$, which states that every bounded holomorphic function is constant.
Surprisingly, it is skipped in many standard texts on complex analysis. For a
reference, see e.g. [How03, Exercise 7.11].

Consequently, any holomorphic activation function which generates universal
approximators (in the class of holomorphic functions) fails to be Lipschitz
continuous. This lack of quantitative global continuity has undesirable
consequences from the perspective of statistical learning and gradient-based
optimization.

In analogy to [Voi20], rather than the closure in the $C^{0}(K)$-topology for
a fixed compact set $K$, we can consider the closure of
${\mathcal{M}}_{\sigma}$ in the topology of locally uniform convergence (or
compact-open topology) on ${\mathbb{K}}^{d}$, i.e. the set of functions
$f:{\mathbb{K}}^{d}\to{\mathbb{K}}$ such that there exists a sequence
$f_{n}\in{\mathcal{M}}_{\sigma}$ such that $f_{n}\to f$ uniformly on every
compact set $K\subset{\mathbb{K}}^{d}$. The relationship between the closures
is more subtle in our case and discussed in Appendix B.

##  3\. Proof of Theorem 1.2: Harmonic shallow networks

###  3.1. A primer on harmonic polynomials

Before we come to the main proof, we review some properties of harmonic
functions and harmonic polynomials.

######  Definition 3.1.

  1. (1)

A function $f:\mathbb{R}^{d}\to\mathbb{R}$ is called harmonic if $\Delta
f=(\partial_{1}^{2}+\dots\partial_{d}^{2})f=0$.

  2. (2)

A function $f:\mathbb{R}^{d}\to\mathbb{R}$ is called homogeneous of degree $j$
if $f(\lambda x)=\lambda^{j}f(x)$ for all $\lambda\in\mathbb{R}$ and
$x\in\mathbb{R}^{d}$.

It is an easy exercise to see that if $p:\mathbb{R}^{d}\to\mathbb{R}$ is
harmonic, then so is $x\mapsto p(Ox)$ for any orthogonal matrix $O$, see also
(3.1). For polynomials, being homogeneous means that there are no lower order
terms, and the degree of the polynomial and degree of homogeneity coincide.
Every (harmonic) polynomial can be decomposed uniquely as
$p=\sum_{j=0}^{\mathrm{deg}\,p}p_{j}$, where $p_{j}$ is a homogeneous
(harmonic) polynomial of degree $j$. The fact that the $j$-homogeneous part
$p_{j}$ of a harmonic polynomial $p$ is harmonic follows from the fact that
$\Delta p_{j}$ is $j-2$-homogeneous, and that the terms of different
homogeneity must vanish separately. We denote

$\mathcal{HP}^{d}_{j}=\\{p:\mathbb{R}^{d}\to\mathbb{R}:p\text{ harmonic
homogeneous polynomial of degree $j$}\\}.$

Before we come to the proof of Theorem 1.2, we require the following auxiliary
result about harmonic homogeneous polynomials and coordinate rotations.

######  Lemma 3.2.

Let $p\in\mathcal{HP}^{d}_{j}$ for some $d,n$ and denote

$V_{p}=\mathrm{span}\\{p(Ox):O\in O(d)\\}\subseteq\mathcal{HP}^{d}_{j}.$

If $p\not\equiv 0$, then $V_{p}=\mathcal{HP}^{d}_{j}$.

In particular, Lemma 3.2 illustrates that there is no substantial difference
between harmonic polynomials in many variables and few variables, since e.g.
$x_{1}^{2}-x_{2}^{2}$ and its rotations can be used to generate any
homogeneous harmonic polynomial of degree $2$ on a high-dimensional space.

We prove Lemma 3.2 in Appendix A.

###  3.2. Approximation by harmonic neural networks

If $\sigma:\mathbb{R}^{k}\to\mathbb{R}$ is harmonic, then any
$f\in{\mathcal{M}}_{\sigma}$ is harmonic for any $d\geq k$ since the Laplace
operator $\Delta$ is linear and

$\displaystyle\Delta a_{i}\sigma\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}$
$\displaystyle=a_{i}\sum_{j=1}^{d}\partial_{x_{j}}\partial_{x_{j}}\sigma\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}$
$\displaystyle=a_{i}\rho_{i}\sum_{j=1}^{d}\partial_{x_{j}}\left(\sum_{l=1}^{k}P_{i;lj}(\partial_{y_{l}}\sigma)\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}\right)$
$\displaystyle=a_{i}\rho_{i}^{2}\sum_{j=1}^{d}\sum_{l,m=1}^{k}P_{i;lj}P_{i;mj}(\partial_{y_{l}}\partial_{y_{m}}\sigma)\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}$
$\displaystyle=a_{i}\rho_{i}^{2}\sum_{l,m=1}^{k}\left(\sum_{j=1}^{d}P_{i;lj}P_{i;mj}\right)(\partial_{y_{l}}\partial_{y_{m}}\sigma)\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}$
$\displaystyle=a_{i}\rho_{i}^{2}\sum_{l,m=1}^{k}(P_{i}P_{i}^{T})_{lm}(\partial_{y_{l}}\partial_{y_{m}}\sigma)\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}$
$\displaystyle=a_{i}\rho_{i}^{2}\sum_{l,m=1}^{k}\delta_{lm}(\partial_{y_{l}}\partial_{y_{m}}\sigma)\big{(}\rho_{i}\,P_{i}x+b_{i}\big{)}$
$\displaystyle=a_{i}\rho_{i}^{2}(\Delta\sigma)\big{(}\rho_{i}P_{i}x+b_{i})=0.$
(3.1)

This implies that element of ${\mathcal{M}}_{\sigma}$ cannot approximate any
function which is not harmonic due to [GT01, Theorem 2.8] in close analogy to
the observations for holomorphic functions.

###### Proof of Theorem 1.2.

Step 1. Let $q\in\mathcal{HP}_{m}^{d}$ and
$\sigma:\mathbb{R}^{k}\to\mathbb{R}$ harmonic such that $\sigma$ is not a
polynomial of degree at most $m-1$. In this step, we show that
$q\in\overline{{\mathcal{M}}_{\sigma}}$.

Note that for any $t\in\mathbb{R}$, the function
$x\in\mathbb{R}^{k}\mapsto\sigma(tx)$ is harmonic by the same argument as
(3.1). Since sums of harmonic functions are harmonic, this means that

$x\mapsto\frac{\sigma(tx)-\sigma(0)}{t}$

is harmonic for every $t\neq 0$, and since the uniform limit of harmonic
functions is harmonic, also $x\mapsto\frac{d}{dt}\big{|}_{t=0}\sigma(tx)$ is
harmonic. The same is true for iterated difference quotients, and therefore
higher order derivatives. Since $\sigma$ is harmonic, it is analytic and can
be written as

$\sigma(x)=\sum_{j=0}^{\infty}p_{j}(x)$

in a neighbourhood of the origin [Eva10, Section 2.2, Theorem 10], where
$p_{j}$ is a homogeneous polynomial of degree $j$. As for holomorphic
functions, we find that

$\frac{d}{dt}\bigg{|}_{t=0}\sigma(tx)=\sum_{j=0}^{\infty}\frac{d}{dt}\bigg{|}_{t=0}p_{j}(tx)=\sum_{j=0}^{\infty}\frac{d}{dt}\bigg{|}_{t=0}t^{j}\,p_{j}(x)=j!\,p_{j}(x).$

In particular, we see that $p_{j}$ is harmonic for all $j\in\mathbb{N}$. Since
$\sigma$ is not a polynomial of degree at most $m-1$, there exists some $j\geq
m$ such that $p_{j}\not\equiv 0$. By the preceding analysis and the definition
of ${\mathcal{M}}_{\sigma}$, we find that

$x\mapsto p_{j}(Px)\in\overline{\mathcal{M}}_{\sigma}$

for any $P\in O(d,k)$. Thus, fixing $P:\mathbb{R}^{d}\to\mathbb{R}^{k}$ as
$x\mapsto(x_{1},\dots,x_{k})$ and setting $\tilde{p}_{j}(x)=p_{j}(Px)$, we
find that $x\mapsto\tilde{p}_{j}(Ox)\in\overline{\mathcal{M}}_{\sigma}$ for
all $O\in O(d)$.

If $f$ and $g$ can be approximated to arbitrary accuracy by elements of
${\mathcal{M}}_{\sigma}$, the same is true for $f+g$ and $\lambda f$ with
$\lambda\in\mathbb{R}$, so $\overline{{\mathcal{M}}_{\sigma}}$ is a linear
space. In the terminology of Lemma 3.2, this means that
$V_{\tilde{p}_{j}}\subseteq\overline{{\mathcal{M}}_{\sigma}}$ and thus
$\mathcal{HP}^{d}_{j}\subseteq\overline{{\mathcal{M}}_{\sigma}}$. If $j=m$,
then $q\in\overline{{\mathcal{M}}_{\sigma}}$ and the proof is concluded.

If $j>m\geq 0$, we observe that there exists $1\leq\ell\leq k$ such that
$\partial_{x^{\ell}}p(x)$ is not the zero polynomial, since a non-trivial
polynomial has a non-trivial gradient. By [K9̈3, Section 2.2], we have
$\Delta\partial_{x^{\ell}}p=\partial_{x^{\ell}}\Delta p=0$. In particular
$\partial_{x^{\ell}}p(x)$ is a homogeneous harmonic polynomial of degree $j-1$
and

$\partial_{x^{\ell}}p(x)=\lim_{h\to
0}\frac{p(x+he_{\ell})-p(x)}{h}\in\overline{{\mathcal{M}}_{\sigma}}$

by almost the same construction as before. The main difference is that earlier
we took the derivative in the scaling factor $\rho$, where now we take the
derivative in the bias $b$. After $j-m$ steps, we find
$\tilde{p}\in\mathcal{HP}^{d}_{m}\cap\overline{{\mathcal{M}}_{\sigma}}$, and
the proof can be concluded as before.

Step 2. We have seen that, if $\sigma$ is not a harmonic polynomial of degree
at most $m-1$, then every harmonic homogeneous polynomial of degree at most
$m$ can be approximated by elements of ${\mathcal{M}}_{\sigma}$ in the uniform
topology on $\overline{D}$. By linearity, this is also true for every harmonic
polynomial of degree at most $m$. We now distinguish two cases:

  1. (1)

$\sigma$ is a polynomial of degree $m$. Then ${\mathcal{M}}_{\sigma}$ is
contained in the space of harmonic polynomials of degree at most $m$, so
${\mathcal{M}}_{\sigma}=\overline{{\mathcal{M}}_{\sigma}}=\oplus_{j=0}^{m}\mathcal{HP}_{j}^{d}$
is the space of harmonic polynomials of degree at most $m$.

  2. (2)

$\sigma$ is not a polynomial. Then
$\oplus_{j=0}^{\infty}\mathcal{HP}_{j}^{d}\subseteq\overline{{\mathcal{M}}_{\sigma}}$,
where the $\oplus$ denotes the direct sum in which at most finitely many terms
are non-zero. By density
$\overline{\oplus_{j=0}^{\infty}\mathcal{HP}_{j}^{d}}\subseteq\overline{{\mathcal{M}}_{\sigma}}$.

Step 3. We now show that
$\overline{{\mathcal{M}}_{\sigma}}\subseteq\overline{\mathcal{HP}}$. Since
$\sigma$ is a harmonic function on the entire space $\mathbb{R}^{k}$, it can
be represented by a globally convergent power series in many variables

$\sigma(x)=\sum_{j=0}^{\infty}p_{j}(x)$

due to [Eva10, Section 2.2.e], where $p_{j}$ is a harmonic homogeneous
polynomial of degree $j$, much like in Step 1. In particular, for any $P\in
O(d,k)$ and $\rho,b\in\mathbb{R}$, we see that $x\mapsto\sigma(\rho Px+b)$ is
an analytic function. Since power series converge locally uniformly, we can
truncate the series at a finite index depending on $\rho,b$ and $\overline{D}$
to obtain a harmonic polynomial in $d$ variables which uniformly approximates
$\sigma(\rho Px+b)$. By linearity, any element in ${\mathcal{M}}_{\sigma}$ can
be approximated uniformly by harmonic polynomials. By density and selection of
a diagonal sequence, this extends to any element in the closure
$\overline{{\mathcal{M}}_{\sigma}}$. ∎

######  Remark 3.3.

The restrictive class of linear maps is crucial in this result, since the
harmonicity is only preserved due to the orthogonality constraint. If
$\widetilde{M}_{\sigma,n}$ is the class of all maps

$f(x)=\sum_{i=1}^{n}a_{i}\,\sigma\big{(}W_{i}x+b_{i}\big{)}$

for general linear maps $W_{i}:\mathbb{R}^{n}\to\mathbb{R}^{k}$ and
$\widetilde{\mathcal{M}}_{\sigma}=\bigcup_{n=1}^{\infty}\widetilde{\mathcal{M}}_{\sigma,n}$,
then

  1. (1)

If $\sigma$ is a polyomial of degree at most $m$, then
${\mathcal{M}}_{\sigma}={\mathcal{P}}_{m}$ is the space of polynomials of
degree $m$.

  2. (2)

If $\sigma$ is not a polynomial, then ${\mathcal{M}}_{\sigma}$ is dense in the
space of continuous functions.

This holds even for harmonic activation functions. An easy way to see this is
to fix a direction $v\in\mathbb{R}^{k}$ such that $t\mapsto\sigma(tv)$ is not
a polynomial (not a polynomial of low degree) and consider the uniform
approximation theorem in one variable, e.g. Theorem 1.1 for maps $W_{i}$ which
project to the line $tv$. To see that such a direction exists, observe the
following:

$\sigma(x)=\sum_{j=0}^{\infty}p_{j}(x)$

where $p_{j}$ is a homogeneous harmonic polynomial of degree $j$. For all $j$,
the following dichotomy holds: Either $p_{j}\equiv 0$, or the set

$N_{j}=\\{v\in\mathbb{R}^{d}:p_{j}(v)=0\\}$

has Lebesgue measure $0$.333 If $n=1$, this is the fundamental theorem of
calculus. In the general case, this can be proved by Fubini’s theorem and
induction on $n$. See e.g. [Iva10] for an alternative elegant proof. In
particular, the set

$Y=\bigcap_{N_{j}\not\equiv\mathbb{R}^{d}}\big{(}\mathbb{R}^{d}\setminus
N_{j}\big{)}$

has full measure. For any $v\in Y$, $\sigma_{v}(t)=\sigma(tv)$ is an analytic
function which is a polynomial of the same degree as $\sigma$ if $\sigma$ is a
polynomial, and not a polynomial if $\sigma$ is not a polynomial.

Analogously, the restriction to complex linear maps plays a major role in the
context of [Voi20].

######  Remark 3.4.

As in the complex case, the question whether all harmonic functions in $D$
which extend continuously to $\overline{D}$ can be approximated by harmonic
polynomials depends on the topology of $D$. For a general compact set
$K\subseteq\mathbb{R}^{d}$, the following are equivalent [Gar95, Theorem 1.3]:

  1. (1)

Every continuous function on $K$ which is harmonic in the interior $K^{\circ}$
of $K$ can be approximated uniformly by harmonic polynomials.

  2. (2)

$\mathbb{R}^{d}\setminus K$ and $\mathbb{R}^{d}\setminus K^{\circ}$ are thin
at the same points of $K$.

For a review of thin sets, see e.g. [Gar95, Section 0] or [Hel14, Section
5.6]. In particular, if $D$ is a bounded open set with $C^{2}$-boundary and
$d\geq 3$, every harmonic function on $D$ which extends continuously to
$\overline{D}$ can be approximated uniformly by harmonic polynomials.

##  4\. Proof of Theorem 1.3: Deep residual networks

In this section, we establish the approximation properties of deep residual
neural networks. The proof of the first claim in Theorem 1.3 is a classical
technique of ‘turning a neural network on its side’.

###### Proof.

First claim. Let

$f_{\Theta}\in{\mathcal{M}}_{\sigma,n},\qquad
f_{\Theta}(x)=\sum_{i=1}^{n}a_{i}\,\sigma(\langle
w_{i},x\rangle+b_{i})=\sum_{i=1}^{n}a_{i}\,\sigma\left(\sum_{j=1}^{d}\overline{w}_{i,j}x_{j}+b_{i}\right)$

be a shallow neural network. We represent $f_{\Theta}$ by a residual neural
network as

$\displaystyle z\mapsto$ $\displaystyle\xrightarrow{linear}\begin{pmatrix}x\\\
0\end{pmatrix}\xrightarrow{residual}\begin{pmatrix}x+\sigma(0)\\\
0+\sum_{i=1}^{D_{1}}a_{i}\,\sigma(\langle
w_{i},x\rangle+b_{i})\end{pmatrix}=\begin{pmatrix}x\\\
\sum_{i=1}^{D_{1}}a_{i}\,\sigma(\langle w_{i},x\rangle+b_{i})\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\begin{pmatrix}x\\\
\sum_{i=1}^{D_{1}+D_{2}}a_{i}\,\sigma(\langle
w_{i},x\rangle+b_{i})\end{pmatrix}\xrightarrow{residual}\>\dots\>\xrightarrow{residual}\begin{pmatrix}x\\\
\sum_{i=1}^{n}a_{i}\,\sigma(\langle w_{i},x\rangle+b_{i})\end{pmatrix}$
$\displaystyle\xrightarrow{linear}\sum_{i=1}^{D_{1}}a_{i}\,\sigma(\langle
w_{i},x\rangle+b_{i})$

with weights

$A^{0}=\begin{pmatrix}1&0&\dots&0\\\ 0&1&&\\\ \vdots&&\ddots&\vdots\\\
0&\dots&\dots&1\\\ 0&\dots&\dots&0\end{pmatrix},\quad
b^{0}=\begin{pmatrix}0\\\ \vdots\\\ 0\end{pmatrix},\quad
A^{L}=\begin{pmatrix}0&\dots&0&1\end{pmatrix}$

and, for $1\leq\ell\leq L-1$,

$A^{\ell}=\begin{pmatrix}0&\dots&0\\\ \vdots&\ddots&\vdots\\\ 0&\dots&0\\\
a_{N_{\ell}+1}&\dots&a_{N_{\ell}+D_{\ell}}\end{pmatrix}\in{\mathbb{K}}^{(d+1)\times
D_{\ell}},\qquad
W^{\ell}=\begin{pmatrix}\overline{w}_{N_{\ell}+1,1}&\dots&\overline{w}_{N_{\ell}+1,d}\\\
\vdots&\ddots&\vdots\\\
\overline{w}_{N_{\ell}+D_{\ell},1}&\dots&\overline{w}_{N_{\ell}+D_{\ell},d}\\\
0&\dots&0\end{pmatrix}\in{\mathbb{K}}^{D_{\ell}\times(d+1)}$

where $N_{\ell}=\sum_{i=1}^{\ell-1}D_{i}$. The biases are chosen accordingly
as $b^{\ell}=(b_{N_{\ell}+1},\dots,b_{N_{\ell}+D_{\ell}})$. Of course if
${\mathbb{K}}=\mathbb{R}$, the complex conjugation has no effect.

In particular
$\overline{{\mathcal{P}}}=\overline{{\mathcal{M}}_{\sigma}}\subseteq\overline{\mathcal{N}_{1}}$
since ${\mathcal{M}}_{\sigma}\subseteq\mathcal{N}_{1}$, and similarly for
$\mathcal{N}_{2}$. On the other hand,
$f\in\mathcal{R}(d_{0},D_{1},\dots,D_{L-1})$ is a composition of analytic
(vector-valued) functions with globally convergent power series. Consequently,
also $f$ can be represented by a globally convergent power series [K0̈4,
Section 14.2], and by truncating
$\mathcal{R}_{L,\sigma}(d_{0},D_{1},\dots,D_{L-1})\subseteq\overline{\mathcal{P}}$
for any choice of architecture $d_{0},D_{1},\dots,D_{L-1}$. Therefore in
particular
$\overline{\mathcal{N}_{1}},\,\overline{\mathcal{N}_{2}}\subseteq\overline{{\mathcal{P}}}$.

Second claim. If $\sigma$ is not a polynomial, the second claim follows from
the first. In the case of polynomial activation, the approximation properties
of deep networks are strictly greater than those of networks of fixed depths.
We provide a direct proof for the second claim which does not use the first.

First, consider the case that that $\sigma(z)=z^{2}$. Again, we construct the
ResNet such that the vector $z=(z_{1},\dots,z_{d})$ is available at all
layers. We recall that

$z_{i}z_{j}=\frac{\sigma(z_{i}+z_{j})-\sigma(z_{i}-z_{j})}{4}\quad\text{and}\quad
z_{i}=\frac{\sigma(z_{i}+1)-\sigma(z_{i}-1)}{4}.$

Let $P(z)=\sum_{j_{1}+\dots+j_{d}\leq m\\\
,j_{i}\in\mathbb{N}_{0}}a_{j_{1}\dots j_{d}}z_{1}^{j_{1}}\dots z_{d}^{j_{d}}$.
If $d_{0}\geq d+2$ and $D_{\ell}\geq 2$, we construct the residual
representation

$\displaystyle z$
$\displaystyle\xrightarrow{linear}\begin{pmatrix}a_{0,\dots,0}+\sum_{j=1}^{d}a_{0,\dots,1,\dots,0}z_{j}\\\
0\\\
z\end{pmatrix}\xrightarrow{residual}\begin{pmatrix}a_{0,\dots,0}+\sum_{j=1}^{d}a_{0,\dots,1,\dots,0}z_{j}+a_{1,1,0,\dots,0}z_{1}^{2}\\\
0\\\ z\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\begin{pmatrix}a_{0,\dots,0}+\sum_{j=1}^{d}a_{0,\dots,1,\dots,0}z_{j}+a_{2,0,\dots,0}z_{1}^{2}+a_{1,1,0,\dots,0}z_{1}z_{2}\\\
0\\\ z\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\>\dots\>\xrightarrow{residual}\begin{pmatrix}a_{0,\dots,0}+\sum_{j=1}^{d}a_{0,\dots,1,\dots,0}z_{j}+\sum_{i,j=1}^{d}a_{0,\dots,1,\dots,1,\dots,0}z_{i}z_{j}\\\
0\\\ z\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\begin{pmatrix}a_{0,\dots,0}+\sum_{j=1}^{d}a_{0,\dots,1,\dots,0}z_{j}+\sum_{i,j=1}^{d}a_{0,\dots,1,\dots,1,\dots,0}z_{i}z_{j}\\\
z_{1}^{2}\\\ z\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\begin{pmatrix}a_{0,\dots,0}+\sum_{j=1}^{d}a_{0,\dots,1,\dots,0}z_{j}+\sum_{i,j=1}^{d}a_{0,\dots,1,\dots,1,\dots,0}z_{i}z_{j}\\\
z_{1}^{3}\\\ z\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\begin{pmatrix}a_{0,\dots,0}+\sum_{j=1}^{d}a_{0,\dots,1,\dots,0}z_{j}+\sum_{i,j=1}^{d}a_{0,\dots,1,\dots,1,\dots,0}z_{i}z_{j}+a_{3,0,\dots,0}z_{1}^{3}\\\
0\\\ z\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\>\dots\>\begin{pmatrix}P(z)\\\ 0\\\
z\end{pmatrix}\xrightarrow{linear}P(z).$

The additional zero component is needed to ‘build up’ higher powers of $z$ by
using $\sigma$ and

$z_{1}^{j_{1}+1}\dots z_{d}^{j_{d}}=z_{1}^{j_{1}}\dots z_{d}^{j_{d}}\cdot
z_{1}$

together with (4), before adding them to the polynomial which is assembled
over many layers in the first component. We note that the requirement
$D_{\ell}\geq 2$ was needed in order to execute multiplication – if
multiplication were stretched over multiple layers, an additional ‘storage’
space would be required. Wider networks with wider residual blocks could fit
multiple terms of the polynomial at the same time.

Now consider the case that $\sigma$ is a general analytic function which is
not affine-linear. In this case, there exists $z^{*}\in{\mathbb{K}}$ such that
$\sigma^{\prime\prime}(z)\neq 0$. As in the proof of Theorem 1.1, we can
approximate $z\mapsto z^{2}$ to arbitrary accuracy by

$z^{2}=\lim_{h\to
0}\frac{\sigma(z^{*}+hz)-2\sigma(z^{*})+\sigma(z^{*}-hz)}{h^{2}\,\sigma^{\prime\prime}(z^{*})},$

so we note that we can approximate squares to arbitrary accuracy using three
evaluations of $\sigma$ and products to arbitrary accuracy using six
evaluations of $\sigma$. However, as we only require squares or the
differences of squares for which middle function value $\sigma(z^{*})$ cancels
out, only $m=4$ neurons are needed rather than $m=6$.

We thus see that
${\mathcal{P}}\subseteq\overline{\bigcup_{L=1}^{\infty}\mathcal{R}_{L,\sigma}(d+2,4,\dots,4)}$.
The opposite inclusion holds since every element of the space on the right is
analytic. ∎

While every shallow neural network can be expressed as a deep residual
network, the number of parameters required to represent the network increases
roughly twofold, since we list $D_{\ell}\cdot d$ zeros explicitly in the
weight matrices $A^{\ell},W^{\ell}$ in every step which are implicit in the
shallow neural network. While a shallow neural network is described by
$(d+2)n$ parameters, the same function represented as a deep residual network
has

$(d+1)+\sum_{\ell=1}^{L-1}\big{(}2D_{\ell}(d+1)+D_{\ell}\big{)}+d(d+1)+(d+1)=2(n+1)(d+1)+n$

parameters. On the other hand, deep residual networks have a much larger
expressive power for this number of parameters, since a single input can pass
through multiple non-linear activations $\sigma$.

A similar argument can be made for traditional fully-connected feed forward
networks and DenseNets. More details can be found in Appendix C. In the real
case, the final proof remains valid under the weaker assumption that $\sigma$
is not affine linear and $\sigma\in C^{2}$.

##  5\. Conclusion and Further Directions

We showed that neural networks with (real or complex) analytic activation
function can approximate any function which can be approximated by
polynomials, and vice versa. While we focused on the $C^{0}$-topology in our
presentation, the result holds in any $C^{k}$\- or $L^{p}$\- topology. The
proofs are simple and only require the approximation of derivatives by
difference quotients. In the real case, we reprove the universal approximation
theorem by elementary means, reducing it to the Stone-Weierstrass theorem. In
the complex case, the situation is more complicated, and results may depend on
the topology of the domain of approximation.

If a function is known to be holomorphic in $d\geq 2$ complex variables, or
the domain of approximation does not satisfy the hypotheses of Mergelyan’s
theorem for $d=1$, then also approximation by neural networks is generally
impossible. Similar results are obtained for shallow real ‘harmonic’ neural
networks, which utilize orthogonal projections of the data onto a lower-
dimensional (but not one-dimensional) linear space.

Finally, we showed that polynomial activation functions are admissible from
the perspective of approximation theory for residual networks if the network
has a certain minimal width and the depth may be taken arbitrarily large.

The results as presented above are unsatisfying in several ways.

  1. (1)

The results presented here are purely qualitative. No rates of approximation
are established under stronger assumptions on the target function in terms of
e.g. the number of parameters. Some quantitative rates can be found in [Suz18,
Yar17] for target functions which lie either in Sobolev or Hölder spaces, and
for approximation in different topologies. However, we emphasize that any
function class which has desirable properties from the perspective of
statistical learning theory faces the curse of dimensionality when
approximating some function in a too general function class, even in a weak
topology [EW21].

  2. (2)

The proofs above involved the approximation of derivatives by difference
quotients. Consequently, the coefficients are large and the representation of
the neural network depends critically on cancellation between possibly very
large terms. For gradient-based optimizers, such subtle coefficients are hard
to find.

  3. (3)

The proofs cannot be easily modified to include the possibly most popular
activation function in practice, the rectified linear united (ReLU) activation
$\sigma(x)=\max\\{x,0\\}$. Analogous results in the case of ReLU activation
are presented in Appendix D.

From a negative perspective, our results can be interpreted as a statement
that neural networks can approximate exactly the same functions as
polynomials. In the real case, this is not surprising since polynomials are
dense in the space of continuous functions. Nevertheless, approximation by
polynomials of high degree performs poorly even in one-dimensional
interpolation problems, as interpolation with poorly chosen data points leads
to high amplitude oscillations at the domain boundary known as the Runge
phenomenon [Tre13, Chapter 13]. Universal approximation theorems are therefore
unable to explain the superiority of neural networks over other parametrized
function classes.

Approximation results for neural networks with bounded weights in a suitable
sense can be obtained in suitable model classes adapted to neural networks
[Bar93, Bac17, EMW19, EW22, PN21a], in which it can also be demonstrated that
neural networks significantly outperform any linear method in spaces of high
dimension [Bar93, Theorem 6].

##  6\. Acknowledgements

The authors would like to thank Ron DeVore, Guergana Petrova and Peter Binev
for inspiring conversations. JP would also like to acknowledge helpful
conversations with Dmitriy Bilyk, Alexey Glazyrin, and Oleksandr Vlasiuk at
the SIAM TX-LA Conference.

##  Appendix A Proof of Lemma 3.2

Let $\mathcal{HP}^{d}_{n}$ be the space of harmonic homogeneous polynomials of
degree $n$ in $d$ variables. Harmonic homogeneous polynomials are in one-to-
one correspondence with their restriction on the sphere as described below.
When we restrict harmonic polynomials to the sphere we obtain what are called
spherical harmonics, which are eigenfunctions of the Laplace-Beltrami operator
on the (surface of the) sphere. Similarly there is a unique way to extend a
spherical harmonic to a harmonic polynomial on Euclidean space
$\mathbb{R}^{d}$. This and much of what is below are standard facts from
harmonic analysis on spheres [DX13].

To prove our lemma we need a result on zonal spherical harmonics, spherical
harmonics which are invariant under rotation with respect to a fixed axis.
These functions are unique (up to a multiplicative constant) and can be
represented on the sphere as $Z^{y}_{n}(x)=C_{n}^{\lambda}(\langle
x,y\rangle)$ where $\lambda=(d-2)/2$ and $C_{n}^{\lambda}(t)$ is the degree
$n$ Gegenbauer polynomial (defined below). A well-known observation about
these functions from interpolation on the sphere states that zonal spherical
harmonics form a basis for the spherical harmonics, and thus by the
observation above, the restriction of $\mathcal{HP}^{d}_{n}$ to the sphere
(Theorem A.1).

There are a few additional objects we need to define before proving Lemma 3.2.
Gegenbauer polynomials are a class of orthogonal polynomials which play a
special role in harmonic analysis on spheres. These functions, denoted
$C_{n}^{\lambda}(t)$ define a reproducing kernel in the space
$L^{2}(\mathbb{S}^{d-1})$.

Before we introduce that relation (known as the addition formula) we note that
spherical harmonics, as eigenfunctions of the Laplace-Beltrami operator, form
a basis for $L^{2}(\mathbb{S}^{d-1})$ and we may index a basis of
eigenfunctions in terms of the $n$-th eigenvalue of this operator (its
eigenvalues are non-negative and increasing). For each eigenvalue the space of
spherical harmonics corresponding to this $n$-th eigenvalue is a linear space
$V_{n}$ of dimension $\dim V_{n}$ which has a basis $\\{Y_{n,1},...,Y_{n,\dim
V_{n}}\\}$. The addition formula tells us that

$C_{n}^{\lambda}(\langle x,y\rangle)=\frac{1}{\dim V_{n}}\sum_{k=1}^{\dim
V_{n}}Y_{n,k}(x)\overline{Y_{n,k}(y)}.$

The addition formula shows immediately that the Gegenbauer polynomials are
what we call positive definite functions on $\mathbb{S}^{d-1}$ meaning

$\sum_{1\leq i,j\leq k}c_{i}\overline{c_{j}}C_{n}^{\lambda}(\langle
x_{i},x_{j}\rangle)\geq 0$

holds for all coefficients $c_{1},...,c_{k}\in\mathbb{C}$ and all
$x_{1},...,x_{k}\in\mathbb{S}^{d-1}$. This is equivalent to stating that for
any collection of points the matrix obtained by evaluating a Gegenbauer
polynomial on the inner product matrix corresponding to our system of points
is positive definite. From this the following inequality holds

$\det\left[C_{n}^{\lambda}(\langle x_{i},x_{j}\rangle)\right]_{i,j=1}^{N}\geq
0.$

When this inequality is strict our collection of points is called a
fundamental system of points on the sphere. The content of the following
result (which we use in our proof of Lemma 3.2) tells us that the zonal
spherical harmonics form a basis for the restriction of $\mathcal{HP}^{d}_{n}$
to the sphere when we evaluate them on a fundamental system.

######  Theorem A.1.

[DX13, Thm. 1.3.3] If $\\{x_{1},...,x_{N}\\}$ is a fundamental system of
points on the sphere, then $\\{C_{n}^{\lambda}(\langle\cdot,x_{i}\rangle)\ :\
i=1,2,...,N\\},\lambda=(d-2)/2$ is a basis for $\mathcal{HP}^{d}_{n}$.

As a final remark recall that the special orthogonal group $SO(d)$, which may
be identified with the set of orthogonal matrices of determinant one, is a
locally-compact abelian group. As such, up to multiplicative constant there is
unique nontrivial countably additive probability measure on the Borel subsets
of $SO(d)$ by Haar’s theorem [Loo53]. This measure is invariant on subsets
under action of the group (it is left-translation invariant) and we call this
measure the Haar measure of $SO(d)$.

###### Proof of Lemma 3.2.

Suppose non-zero $p\in\mathcal{HP}^{d}_{n}$ is given. Because of the one-to-
one correspondence between harmonic polynomials and their restriction to the
sphere mentioned above, we will interchangeably refer to $p$ as a function on
the sphere $\mathbb{S}^{d-1}$ and one defined on all of $\mathbb{R}^{d}$.

As a function defined on $\mathbb{S}^{d-1}$ we may average $p$ with respect to
all rotations which fix the axis $y$, with respect to the Haar measure on the
special orthogonal group, obtaining the function

$\displaystyle f(x)=\int_{SO(d)}p(O_{y}x)\,\mathrm{d}m(y).$

Note that this function is a spherical harmonic, which also extends to a
homogeneous polynomial of degree $n$ on $\mathbb{R}^{d}$, and which
additionally is invariant under rotations about the axis $y$. Further this
function will take the same value as $p(x)$ at the poles fixed by rotation
about axis $y$. Thus so long as $p$ is non-zero at these values we see
immediately that $f$ is non-zero also.

Let $V=\mathcal{HP}^{d}_{n}|_{\mathbb{S}^{d-1}}$ be the linear space of
polynomials $\mathcal{HP}^{d}_{n}$ restricted to the sphere. The space $V$ is
a finite dimensional space. We know that for $f$ non-zero,
$f(x)=cZ_{n}^{y}(x)$ for some constant $c\neq 0$ by uniqueness of zonal
spherical harmonics of degree $n$, and so $\text{dist}(W,Z_{n}^{y}(x))=0$.
However this holds for every zonal spherical harmonic (this was shown for
arbitrary $y$). Theorem A.1 then shows that if we took $y$ to be each $x_{i}$
in a fundamental system which avoids the condition $p(x_{i})=0$, we then
arrive at a basis for $V$ by averaging $p$ over rotations multiple times
(since the fundamental system condition is satisfied almost everywhere while
the set of zeroes of $p$ have measure $0$ we can choose such $x_{i}$
satsifying both these conditions). Each of the basis functions in
$V=\mathcal{HP}^{d}_{n}|_{\mathbb{S}^{d-1}}$ satisfy
$\text{dist}(W,Z_{n}^{x_{i}}(x))=0$ and so $W=V$. ∎

##  Appendix B Locally uniform approximation and approximation on compact sets

There are (at least) two natural ways to study the closure of the function
class ${\mathcal{M}}_{\sigma}$:

  1. (1)

Fix a compact set $K$ and take the closure
$\overline{{\mathcal{M}}_{\sigma}}^{K}$ of ${\mathcal{M}}_{\sigma}$ in
$C^{0}(K)$.

  2. (2)

Consider the more global closure of ${\mathcal{M}}_{\sigma}$ in the compact-
open topology or topology of compact convergence [Mun00, §46]:

$\overline{{\mathcal{M}}_{\sigma}}^{cc}=\big{\\{}f\in
C^{0}({\mathbb{K}}^{d}):\exists\
(f_{n})_{n\in\mathbb{N}}\in{\mathcal{M}}_{\sigma}\text{ s.t. }f_{n}\to f\text{
in }C^{0}(K)\text{ for all compact }K\subseteq{\mathbb{K}}^{d}\big{\\}}.$

In this appendix, we compare the different closures. By the nature of the
subject, this appendix is more technical than the main text and requires some
familiarity with topology, Baire categories, and elliptic partial differential
equations. Its content is not needed for the main results of this article, but
illustrates and justifies the conceptual difference to the approach taken in
[Voi20].

The two notions of closure are related as follows:

######  Lemma B.1.

A function $f\in C^{0}({\mathbb{K}}^{d})$ satisfies
$f\in\overline{{\mathcal{M}}_{\sigma}}^{cc}$ if and only if
$f|_{K}\in\overline{{\mathcal{M}}_{\sigma}}^{K}$ for all compact sets $K$.

###### Proof.

The implication $f\in\overline{{\mathcal{M}}_{\sigma}}^{cc}\Rightarrow
f|_{K}\in\overline{{\mathcal{M}}_{\sigma}}^{K}$ is trivial. For the opposite
implication, note that by definition for all $n\in\mathbb{N}$ there exists
$f_{n}\in{\mathcal{M}}_{\sigma}$ such that

$\|f_{n}-f\|_{C^{0}(\overline{B_{n}(0)})}<\frac{1}{n}.$

Since every compact set $K$ is contained in $B_{n}(0)$ for sufficiently large
$n$, we find that $f_{n}\to f$ locally uniformly, i.e.
$f\in\overline{{\mathcal{M}}_{\sigma}}^{cc}$. ∎

In particular, if $f\in\overline{{\mathcal{M}}_{\sigma}}^{cc}$ and
$K\subseteq{\mathbb{K}}^{d}$ is a compact set, then
$f|_{K}\in\overline{{\mathcal{M}}_{\sigma}}^{K}\subseteq C^{0}(K)$. The
opposite question is more subtle: if
$f\in\overline{{\mathcal{M}}_{\sigma}}^{K}$ for a fixed compact set
$K\subseteq{\mathbb{K}}^{d}$, is there
$F\in\overline{{\mathcal{M}}_{\sigma}}^{cc}({\mathbb{K}}^{d})$ such that
$f=F|_{K}$?

First consider neural networks with analytic activation function
$\sigma:{\mathbb{K}}\to{\mathbb{K}}$.

  1. (1)

${\mathbb{K}}=\mathbb{R}$. In this case,
$\overline{{\mathcal{M}}_{\sigma}}^{K}=\overline{{\mathcal{P}}}^{K}=C^{0}(K)$
by the Stone-Weierstrass Theorem [K0̈4, Section 15.7]. Thus
$\overline{{\mathcal{M}}_{\sigma}}^{cc}$ is the set of functions
$f:{\mathbb{K}}^{d}\to{\mathbb{K}}$ such that $f$ is continuous everywhere,
the Fréchet space $C^{0}({\mathbb{K}}^{d})$.

We can answer the question in the affirmative in the real case due to the
Tietze-Urysohn Theorem [Rud87, Theorem 20.4]:

######  Theorem (Tietze-Urysohn Extension Theorem).

Let $K\subseteq{\mathbb{K}}^{d}$ be compact and $f\in C^{0}(K)$. Then there
exists $F\in C_{c}({\mathbb{K}}^{d})$ such that $F|_{K}=f$.

  2. (2)

${\mathbb{K}}=\mathbb{C}$. In this case, we claim that
$\overline{{\mathcal{M}}_{\sigma}}^{cc}$ is the space of holomorphic functions
on $\mathbb{C}^{d}$. To see this, note that a holomorphic function on
$\mathbb{C}^{d}$ can be expanded into a globally convergent power series. By
truncating the series, we see that $f$ can be approximated by polynomials in
the uniform topology on every open set.

On the other hand, assume that $f\in\overline{{\mathcal{M}}_{\sigma}}^{cc}$,
i.e. $f\in\overline{{\mathcal{M}}_{\sigma}}^{K}$ for all compact subsets of
$\mathbb{C}^{d}$. Then for every $R>0$, $f$ can be approximated by holomorphic
functions arbitrarily well in $C^{0}(\overline{B_{R}(0)})$, so $f$ is
holomorphic in the interior $B_{R}(0)$. Consequently $f$ is holomorphic on the
entire space $\mathbb{C}^{d}$.

It is well known that even in one complex dimension, there are holomorphic
functions which cannot be extended to the entire complex plane. As an example
consider $f:\mathbb{C}\setminus\\{0\\}\to\mathbb{C}$, $f(z)=z^{-1}$. On the
other hand, $f$ can be approximated uniformly on any compact set $K$ for which
$\mathbb{C}\setminus K$ is connected by Mergelyan’s theorem.

Thus in the complex case, the answer to our question is negative.

A statement in the same spirit holds also if
$\sigma:\mathbb{R}^{k}\to\mathbb{R}$ is harmonic. While the closure of
${\mathcal{M}}_{\sigma}$ in the topology of locally uniform convergence
coincides with the space of harmonic functions on $\mathbb{R}^{d}$, the
closure of ${\mathcal{M}}_{\sigma}$ in the topology of uniform convergence on
a fixed set $\overline{D}$ contains functions which are harmonic in $D$, but
merely continuous on $\overline{D}$. In particular, there exists no harmonic
extension of $f$ to $\mathbb{R}^{d}$, and we may miss possible limiting
functions if we only consider the topology of locally uniform convergence.

To see that this is true, let $D$ be a bounded $C^{2}$-domain in
$\mathbb{R}^{d}$. By the Perron method [GT01, Section 2.8], the Dirichlet
problem

$\left\\{\begin{array}[]{rll}-\Delta u&=0&\text{in }D\\\ u&=f&\text{on
}\partial D\end{array}\right.$

has a solution for every $f\in C^{0}(D)$ which is continuous on
$\overline{D}$. By Remark 3.4, $u$ can be approximated by harmonic
polynomials. On the other hand, if $f$ is merely continuous, then $u$ cannot
be extended to a harmonic function on $\mathbb{R}^{d}$, so $u$ is not the
restriction of a function $U\in\overline{{\mathcal{M}}_{\sigma}}^{cc}$ to
$\overline{D}$, where the closure is taken with respect to the compact-open
topology.

In fact, we can define a continuous linear map

$A:\overline{{\mathcal{M}}_{\sigma}}^{cc}\to\overline{{\mathcal{M}}_{\sigma}}^{D},\qquad
u\mapsto u|_{\overline{D}}$

and compose further with the trace map $B:C^{0}(\overline{D})\to
C^{0}(\partial D)$. Then $B\circ
A(\overline{{\mathcal{M}}_{\sigma}}^{cc})\subseteq C^{2}(\partial D)$ while
$B(\overline{{\mathcal{M}}_{\sigma}}^{D})=C^{0}(\partial D)$. It follows from
the well known Banach-Mazurkiewicz Theorem [Ash17, Theorem 9] that $C^{2}$ is
of first Baire category in $C^{0}$, i.e. it is the union of countably many
closed sets which all have empty interior. In this sense, we miss ‘most’
functions which can be approximated in $\overline{D}$ by studying only the
global limiting objects in the topology of locally uniform convergence. A
measure-theoretic extension can be found e.g. in [Hun94].

##  Appendix C Classical multi-layer perceptra and DenseNets

###  C.1. Fully connected neural networks

For the sake of completeness, we prove an approximation theorem for classical
fully connected neural networks with multiple layers. While the depth of
residual networks can reach dozens or hundreds and in extreme cases thousands
of layers, the number of layers in a deep neural network is typically more
manageable. Nevertheless, both statements in Theorem 1.3 have analogues for
deep fully connected networks.

A fully connected deep neural network is defined as follows:

  * •

For a given input $z\in\overline{D}\subseteq{\mathbb{K}}^{d}$, designate
$\hat{z}^{0}=z$ and $d_{0}=d$.

  * •

For $\ell\in\\{1,\dots,L\\}$, let $d_{\ell}\in\mathbb{N}$ and set

$z^{\ell}:=A^{\ell}\hat{z}^{\ell-1}+b^{\ell}\quad\text{and}\quad\hat{z}^{\ell}=\sigma(z^{\ell}),$

where $A^{\ell}\in{\mathbb{K}}^{d_{\ell}\times d_{\ell-1}}$ is a linear map
which takes $\hat{z}^{\ell-1}\in{\mathbb{K}}^{d_{\ell-1}}$ to
$z^{\ell}\in{\mathbb{K}}^{d_{\ell}}$, and
$b^{\ell}\in{\mathbb{K}}^{d_{\ell}}$. The function $\sigma$ is applied to the
vector $z^{\ell}$ coordinate-wise.

We designate the parameters (or “weights”) of the deep neural network by

$\Theta=\big{(}A^{1},b^{1},\dots,A^{L},b^{L}\big{)}\in{\mathbb{K}}^{d_{1}\times
d}\times{\mathbb{K}}^{d_{1}}\times\dots\times{\mathbb{K}}^{1\times
d_{\ell-1}}\times{\mathbb{K}}$

and set $f_{\Theta}(z)=z^{L}\in{\mathbb{K}}^{d_{L}}={\mathbb{K}}$. A fully
connected neural network is described by the choice of activation function
$\sigma$, depth $L$ and width of the layers $d_{0},\dots,d_{L}$ (where
$d_{0}=d$ and $d_{L}=1$ in our case). We designate the class of fully
connected neural networks with such architecture by
$\mathcal{FNN}_{\sigma,L}(d_{0},\dots,d_{L})$.

The following is the analogue of Theorem 1.3 for deep fully connected neural
networks.

######  Theorem C.1.

Let $d_{\ell}=d+1+m_{\ell}$ for $m_{\ell}\in\mathbb{N}$ and $1\leq\ell\leq
L-1$. Set $n:=\sum_{\ell=1}^{L-1}m_{\ell}$. Assume that $\sigma$ is not a
constant function. Then for every compact set $K\subset{\mathbb{K}}^{d}$ we
have

${\mathcal{M}}_{\sigma,n}\subseteq\overline{\mathcal{FNN}_{\sigma,L}(d,d_{1},\dots,d_{L-1},d_{L})}$

for the closure in $C^{0}(K)$.

###### Proof.

Since $\sigma$ is not a constant function, there exists $z^{*}$ in
${\mathbb{K}}$ such that $\sigma^{\prime}(z^{*})\neq 0$. We write
$\sigma(z^{*}+\varepsilon z)=c_{0}+c_{1}\varepsilon z+O\big{(}(\varepsilon
z)^{2}\big{)}$ for small $\varepsilon$ and $c_{0}=\sigma(z^{*})$ and
$c_{1}=\sigma^{\prime}(z^{*})$. Since $z\in K$, there exists $R>0$ such that
$|z|\leq R$, so the error term is uniformly small in $z$. We initially ignore
the quadratic error term and note that any affine function of $z$ can be
written as an affine function of $c_{0}+c_{1}\varepsilon z$. By an abuse of
notation we denote by $c_{0},z^{*}$ also the vectors with identical entries in
${\mathbb{K}}^{d}$. With the notations

$N_{\ell}=\sum_{i=1}^{\ell-1}m_{\ell},\qquad
W_{\ell}=\begin{pmatrix}\overline{w}_{N_{\ell}+1,1}&\dots&\overline{w}_{N_{\ell}+1,d}\\\
\vdots&\ddots&\vdots\\\
\overline{w}_{N_{\ell}+m_{\ell},1}&\dots&\overline{w}_{N_{\ell}+m_{\ell},d}\end{pmatrix}\in\mathbb{R}^{m_{\ell}\times
d},\quad a_{\ell}=(a_{N_{\ell}+1},\dots,a_{N_{\ell}+m_{\ell}})$

we represent

$\displaystyle z$ $\displaystyle\xrightarrow{linear}\begin{pmatrix}0\\\
W_{1}z+b_{1}\\\ z^{*}+\varepsilon
z\end{pmatrix}\xrightarrow[\approx]{\sigma}\begin{pmatrix}\sigma(0)\\\
\sigma(W_{1}z+b_{1})\\\ c_{0}+c_{1}\varepsilon
z\end{pmatrix}\xrightarrow[\approx]{linear}\begin{pmatrix}z^{*}+\varepsilon\,a_{1}^{T}\sigma(W_{1}z+b_{1})\\\
W_{2}z+b_{2}\\\ z^{*}+\varepsilon z\end{pmatrix}$
$\displaystyle\xrightarrow[\approx]{\sigma}\dots\xrightarrow[\approx]{\sigma}\begin{pmatrix}c_{0}+c_{1}\varepsilon\sum_{i=1}^{n-m_{L-1}}a_{i}\sigma(\langle
w_{i},z\rangle+b_{i})\\\ \sigma(W_{L-1}z+b_{L-1})\\\ z^{*}+\varepsilon
z\end{pmatrix}\xrightarrow[\approx]{linear}\sum_{i=1}^{n}a_{i}\sigma(\langle
w_{i},z\rangle+b_{i}).$

The approximation error can be made arbitrarily small without increasing the
number of parameters, by taking $\varepsilon$ sufficiently small. When writing
an affine function of $z$ as an affine function of $c_{0}+c_{1}\varepsilon z$,
this can lead to potentially poorly conditioned linear maps, which may cause
numerical instability in practice. Taking the limit $\varepsilon\to 0$, we see
that any shallow neural network can be approximated arbitrarily well by a
deeper neural network with sufficient width and length. ∎

######  Remark C.2.

The number of weights of a deep neural network with architecture
$d_{1},\dots,d_{L}$ is

$N=\sum_{\ell=1}^{L}\big{(}d_{\ell-1}\cdot d_{\ell}+d_{\ell}\big{)}.$

Assume that $L:=n/d$ is an integer. Then we can construct two networks to
approximate $f\in{\mathcal{M}}_{\sigma,n}$:

  1. (1)

A network of depth $n$ and width $d+2$. The number of weights is $N\sim
nd^{2}$.

  2. (2)

A network of depth $L$ and width $2d+1$. The number of weights is $N\sim
L(2d)^{2}\sim 4n/d$.

Thus the number of weights increases by a factor $d$ if we approximate $f$ by
a thin deep network and by a factor $4$ if we use a network which is both wide
and deep instead.

Thus in a sense, we can argue that anything which can be achieved by a shallow
neural network can also be achieved by a deep neural network with a comparable
number of parameters, if the width of the deep network is not too small. Since
deep neural networks with analytic activation are analytic, we find the
following.

######  Corollary C.3.

Consider the classes of neural networks

$\mathcal{NN}_{1}=\bigcup_{L=1}^{\infty}\mathcal{FNN}_{\sigma,L}(d,d+1+m,\dots,d+1+m,1)$

for any fixed $m\in\mathbb{N}$ and

$\mathcal{NN}_{2}=\bigcup_{m=1}^{\infty}\mathcal{FNN}_{\sigma,L}(d,d+1+m,\dots,d+1+m,1)$

for fixed $L$. Then for any compact set $K\subseteq{\mathbb{K}}^{d}$ we have
$\overline{\mathcal{NN}_{1}}=\overline{\mathcal{NN}_{2}}=\overline{{\mathcal{P}}}$
in $C^{0}(K)$.

###  C.2. DenseNets

A DenseNet [IMK+14] is a modified neural network structure in which the
internal state of the $\ell$-th layer is computed linearly from the state of
the network at all previous layers $0,\dots,\ell-1$, rather than just the
previous state. Namely, consider the following structure.

  * •

For a given input $z\in\overline{D}\subseteq{\mathbb{K}}^{d}$, designate
$\hat{z}^{0}=z$ and $d_{0}=d$.

  * •

For $\ell\in\\{1,\dots,L\\}$, let $d_{\ell}\in\mathbb{N}$ the width of the
$\ell$-th state,

$n_{\ell}=\sum_{i=0}^{\ell-1}d_{i},\qquad
A^{\ell}\in{\mathbb{K}}^{d_{\ell}\times n_{\ell}},\quad
b^{\ell}\in{\mathbb{K}}^{d_{\ell}}$

and

$z^{\ell}=A^{\ell}\begin{pmatrix}\hat{z}^{0}\\\ \vdots\\\
\hat{z}^{\ell-1}\end{pmatrix}+b^{\ell},\qquad\hat{z}^{\ell}=\sigma(\hat{z}^{\ell}).$
$z^{\ell}:=A^{\ell}\hat{z}^{\ell-1}+b^{\ell}\quad\text{and}\quad\hat{z}^{\ell}=\sigma(z^{\ell}),$

The function $\sigma$ is applied to the vector $z^{\ell}$ coordinate-wise.

  * •

The output of the network is $f(z)=z^{L}$, where we suppressed the dependence
on the input $z$ and the weights $(A^{0},b^{0},\dots,A^{L},b^{L})$ in the
notation.

We denote the class of DenseNets with activation $\sigma$ and widths
$(d_{0},d_{1},\dots,d_{L-1},d_{L})$ by
$\mathcal{D}_{\sigma,L}(d_{0},d_{1},\dots,d_{L-1},d_{L})$. As usual, $d_{0}=d$
and $d_{L}=1$ are fixed by the problem statement. Since a DenseNet can access
all previous states (including the input) at all layers, every neural network
with a single hidden layer and activation function $\sigma$ can be represented
exactly by a sufficiently large DenseNet. No restriction to compact sets or
closure operation is required, and there is no need to invert potentially ill-
conditioned matrices. The same result holds for deep neural networks, since
the previous layer can be accessed.

######  Theorem C.4.

Set $n=\sum_{\ell=1}^{L-1}d_{\ell}=n_{L}-d$. Then we have

${\mathcal{M}}_{\sigma,n}\>\cup\>\mathcal{FNN}_{\sigma,L}(d,d_{1},\dots,d_{L-1},1)\quad\subseteq\quad\mathcal{D}_{\sigma,L}(d,d_{1},\dots,d_{L-1},1).$

In particular, if $\sigma$ is analytic and not polynomial/affine, an analogue
of Corollary C.3 holds for DenseNets. Note, however, that the number of
parameters for DenseNets with comparable widths is significantly larger, since
the weights $A^{\ell}\nabla{\mathbb{K}}^{d_{\ell}\times n_{\ell}}$ used in the
construction of Theorem C.4 have block structures which list many zeros
explicitly, as only the first/previous layer is accessed.

##  Appendix D A few words on ReLU activation

Our presentation on neural networks does not apply to one of the most popular
activations in practice: $\sigma:\mathbb{R}\to\mathbb{R}$ given by
$\sigma(x)=\mathrm{ReLU}(x)=\max\\{x,0\\}$. For the sake of completeness, we
sketch how similar results can be obtained in this situation by different
means. Almost all activation functions fall into one of these categories: real
analytic, or ReLU-like (e.g. $x\mapsto\max\\{x,\varepsilon x\\}$ for
$\varepsilon\in[0,1)$).

######  Example D.1 (Shallow neural networks).

The direct approximation for shallow ReLU networks can also be proved in
elementary fashion since a $C^{2}$-function $f:\mathbb{R}\to\mathbb{R}$ can be
represented as

$f(x)=f(a)\,\mathrm{ReLU}(1)+f^{\prime}(a)\,\mathrm{ReLU}(x-a)+\int_{a}^{\infty}f^{\prime\prime}(t)\,\mathrm{ReLU}(x-t)\,\,\mathrm{d}t$

for $x>a$, and the integral can be discretized by a Riemann sum uniformly for
$x\in[a,b]$. In particular, the function $x\mapsto x^{m}$ can be approximated
by a shallow ReLU network on any bounded interval. The third step of the proof
of Theorem 1.1 still applies, and we we can approximate $x_{1}^{m_{1}}\dots
x_{d}^{m_{d}}$ for any $m_{1},\dots,m_{d}\in\mathbb{N}$ by approximating
suitable derivatives of $(h_{1}x_{1}+\dots+h_{d}x^{d})^{m_{1}+\dots+m_{d}}$.

We have thus proved the direct approximation theorem for ReLU networks in an
entirely elementary fashion.

Equation (D.1) can be established using the fundamental theorem of calculus
and integrating by parts or using Fubini’s theorem to exchange the order of
integration. A faster, but conceptually more involved, proof utilizes the fact
that the second derivative of the ReLU function is the measure localized at
zero which measures the magnitude of the jump in the first derivative (i.e. a
Dirac $\delta$).

######  Example D.2 (Deep residual networks).

As with fully connected networks, it is possible to deduce the universal
approximation theorem for deep residual networks from that for shallow
networks. We go a different route here, which uses the deep structure in a
more interesting way. The argument is due to Boris Hanin [Han19].

Recall that any function $g:\mathbb{R}^{d}\to\mathbb{R}$ with a uniformly
bounded Hessian can be written as the difference of non-negative strongly
convex functions:

$g(x)=\left(g(x)+\frac{\lambda}{2}\,\|x\|^{2}+c\right)-\frac{\lambda}{2}\|x\|^{2}-c=f_{1}(x)-f_{2}(x).$

The convexity property holds since the Hessians of $f_{1},f_{2}$ satisfy

$D^{2}f_{1}=\lambda I_{d\times d}+D^{2}g\geq I_{d\times d},\qquad
D^{2}f_{2}=\lambda\,I_{d\times d}\geq I_{d\times d}$

if $\lambda>0$ is large enough. Since strongly convex functions are bounded
from below, we can choose $c>0$ large enough to make $f_{1},f_{2}$ non-
negative.

In particular, since $C^{\infty}_{c}(\mathbb{R}^{d})\cap C^{0}(K)$ is dense in
$C^{0}(K)$ for any compact $K\subseteq\mathbb{R}^{d}$,444 To prove this, we
use the Tietze-Urysohn extension [Rud87, Theorem 20.4] and convolution as in
Theorem [Bre11, Theorem 4.23]. we find that the class of dc functions
(functions which are the difference of two convex functions) is dense in
$C^{0}(K)$. It therefore suffices to show that every dc function can be
approximated arbitrarily well by deep residual ReLU networks.

Recall furthermore that a convex function $f:\mathbb{R}^{d}\to\mathbb{R}$ can
be written as the supremum of affine linear functions:

$f(x)=\sup\\{\langle w,x\rangle+b:(w,b)\in A_{f}\\}$

for some set $A_{f}\subseteq\mathbb{R}^{d}\times\mathbb{R}$, using e.g. the
convex conjugate and the Fenchel-Moreau Theorem [Bre11, Theorem 1.11]. On any
compact set $K\subseteq\mathbb{R}^{d}$, $f$ can be approximated uniformly by
the maximum of finitely many linear functions

$f_{L}(x)=\max\\{\langle w_{i},x\rangle+b_{i}:1\leq i\leq L\\}.$

We show that it is possible to represent $f_{L}$ exactly by a deep residual
network of depth $L+1$ and width $d+1$, and to represent
$f_{L}^{(1)}-f_{L^{\prime}}^{(2)}$ for two different functions of the form
(D.2) by a deep residual network of depth $\max\\{L,L^{\prime}\\}$ and width
$d+2$.

First, consider the case in which $f_{L}$ is convex and non-negative. Write

$g_{k}(x)=\max\\{0,\langle w_{1},x\rangle+b_{1},\dots,\langle
w_{k},x\rangle+b_{k}\\}$

and recall that $\max\\{\alpha,\beta\\}=\alpha+\sigma(\beta-\alpha)$ for all
$\alpha,\beta\in\mathbb{R}$, as well as

$\max\\{\alpha_{1},\dots,\alpha_{L}\\}=\max\big{\\{}\max\\{\alpha_{1},\dots,\alpha_{k-1}\\},\alpha_{k}\\}.$

On this basis, we construct a residual network as

$\displaystyle x\xrightarrow{linear}\begin{pmatrix}0\\\ x\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\begin{pmatrix}0+\sigma(\langle
w_{1},x\rangle+b_{1})\\\
x+\sigma(0)\end{pmatrix}=\begin{pmatrix}\max\\{0,\langle
w_{1},x\rangle+b_{1}\\}\\\ x\end{pmatrix}=\begin{pmatrix}g_{1}(x)\\\
x\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\begin{pmatrix}g_{1}(x)+\sigma\big{(}\langle
w_{2},x\rangle+b_{2}-g_{1}(x)\big{)}\\\
x\end{pmatrix}=\begin{pmatrix}g_{2}(x)\\\ x\end{pmatrix}$
$\displaystyle\xrightarrow{residual}\dots\xrightarrow{residual}\begin{pmatrix}g_{L}(x)\\\
x\end{pmatrix}\xrightarrow{linear}g_{L}(x).$

If $f=f_{L}^{(1)}-f_{L}^{(2)}$ and the width of the network is increased to
$d+2$, then two convex functions can be generated simultaneously, and the
final linear layer can be used to express their difference.

Thus the class of deep residual networks of width at least $d+2$ is dense in
the class of dc functions with respect to the $L^{\infty}_{loc}$-topology, and
thus in $C^{0}(K)$ for any compact set $K\subseteq\mathbb{R}^{d}$.

Note that this is true for a particularly simple class of residual networks
compared to the general form (• ‣ 1), namely $D_{\ell}=1$ and
$A^{\ell}=(1,0,\dots,0)$ for all $1\leq\ell\leq L$ in the convex case and

$D_{\ell}=2,\qquad A^{\ell}=\begin{pmatrix}1&0&0&\dots&0\\\
0&1&0&\dots&0\end{pmatrix}^{T}$

in the general case.

######  Remark D.3.

We note that increasing the width $d_{0}$ of the residual network (in unison
with the residual blocks) drastically decreases the required depth. While with
one additional layer we are only able to take the maximum of one additional
linear function per layer, due to the identity

$\max\\{y_{1},\dots,y_{2k}\\}=\max\big{\\{}\max\\{y_{1},y_{2}\\},\dots,\max\\{y_{2k-1},y_{2k}\\}\big{\\}},$

with a residual network of width $d_{0}+k$, it is possible to take the maximum
of $k$ linear functions in $\lceil\log_{2}(k)\rceil$ layers.

######  Example D.4 (Fully connected deep neural networks).

We can argue that any shallow neural network with ReLU activation can be
represented exactly by a deeper network with sufficient width rather than just
approximated at the cost of a marginally larger width. The arguments are a
simpler version of those in Appendix C and do not involve the inversion of
possibly ill-conditioned linear maps with a small parameter $\varepsilon>0$.
Moreover, they apply on the entire quadrant
$Q_{+}=\\{x\in\mathbb{R}^{d}:x_{i}>0\>\forall\ 1\leq i\leq d\\}$.

Claim: Let $K\subseteq{\mathbb{K}}^{d}$ compact and
$f\in{\mathcal{M}}_{\sigma,n}$ for $\sigma=\mathrm{ReLU}$. Then
$f\in\mathcal{FNN}_{\sigma,L}(d,d_{1},\dots,d_{L-1},1)$ if

  1. (1)

$d_{\ell}\geq d+2$ for all $1\leq\ell\leq L-1$ and

  2. (2)

$\sum_{\ell=1}^{L}(d_{\ell}-d-2)=n$.

Proof of claim: Let $K\subseteq{\mathbb{K}}^{d}$ be a compact set and
$f(x)=\sum_{i=1}^{n}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})$ an element of
${\mathcal{M}}_{\sigma,n}$. Due to the compactness of $K$, there exist a
scaling and translation $x\mapsto\alpha x+\beta$ such that $(\alpha
x+\beta)_{i}\geq 0$ for all $i=1,\dots,d$. We note that any affine linear
function of $x$ can also be expressed as an affine linear function of
$\hat{x}=\alpha x+\beta$.

We introduce the notations

$m_{i}=d_{i}-(d+2),\quad N_{\ell}=\sum_{i=1}^{\ell-1}m_{i},\qquad
W_{\ell}=\begin{pmatrix}w_{N_{\ell}+1,1}&\dots&w_{N_{\ell}+1,d}\\\
\vdots&\ddots&\vdots\\\
w_{N_{\ell}+m_{\ell},1}&\dots&w_{N_{\ell}+m_{\ell},d}\end{pmatrix}\in\mathbb{R}^{m_{\ell}\times
d}$

and

$I^{+}_{\ell}=\big{\\{}i\in\\{1,\dots,N_{\ell}\\}:a_{i}\geq 0\big{\\}},\qquad
I^{-}_{\ell}=\\{0,\dots,N_{\ell}\\}\setminus I^{+}_{\ell}.$

Using that $\sigma(z)\geq 0$ for all $z\in\mathbb{R}$ and $\sigma(z)=z$ for
all $z\geq 0$, we may represent $f$ by a deeper network as

$\displaystyle x$ $\displaystyle\xrightarrow{linear}\begin{pmatrix}0\\\ 0\\\
W_{1}+b_{1}\\\ \alpha
x+\beta\end{pmatrix}\xrightarrow{\sigma}\begin{pmatrix}\sigma(0)\\\
\sigma(0)\\\ \sigma(W_{1}x+b_{1})\\\ \sigma(\alpha
x+\beta)\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ \sigma(W_{1}x+b_{1})\\\ \alpha
x+\beta\end{pmatrix}\xrightarrow{linear}\begin{pmatrix}\sum_{i\in
I^{+}_{1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})\\\ -\sum_{i\in
I^{-}_{1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})\\\ W_{2}x+b_{2}\\\ \alpha
x+\beta\end{pmatrix}$
$\displaystyle\xrightarrow{\sigma}\begin{pmatrix}\sigma\left(\sum_{i\in
I^{+}_{1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})\right)\\\
\sigma\left(-\sum_{i\in I^{-}_{1}}a_{i}\sigma(\langle
w_{i},x\rangle+b_{i})\right)\\\ \sigma\big{(}W_{2}x+b_{2}\big{)}\\\
\sigma(\alpha x+\beta)\end{pmatrix}=\begin{pmatrix}\sum_{i\in
I^{+}_{1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})\\\ -\sum_{i\in
I^{-}_{1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})\\\ \sigma(W_{2}x+b_{2})\\\
\alpha x+\beta\end{pmatrix}\xrightarrow{linear}\>\dots\>\xrightarrow{\sigma}$
$\displaystyle\xrightarrow{\sigma}\begin{pmatrix}\sum_{i\in
I^{+}_{L-1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})\\\ -\sum_{i\in
I^{-}_{L-1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})\\\
\sigma(W_{2}x+b_{2})\\\ \alpha
x+\beta\end{pmatrix}\xrightarrow{linear}\sum_{i\in
I^{+}_{L-1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})+\sum_{i\in
I^{-}_{L-1}}a_{i}\sigma(\langle w_{i},x\rangle+b_{i})$
$\displaystyle=\sum_{i=1}^{n}a_{i}\,\sigma(\langle
w_{i},x\rangle+b_{i})=f(x).$

We note that also the convex analytic method of proof generalizes to multi-
layer perceptra. Let $\phi_{1},\dots,\phi_{L}:\mathbb{R}^{d}\to\mathbb{R}$ be
linear maps. We construct

$\displaystyle x$ $\displaystyle\xrightarrow{linear}\begin{pmatrix}0\\\
\phi_{1}(x)-\phi_{2}(x)\\\ \alpha
x+\beta\end{pmatrix}\xrightarrow{\sigma}\begin{pmatrix}0\\\
\max\\{\phi_{1}(x)-\phi_{2}(x),0\\}\\\ \alpha x+\beta\end{pmatrix}$
$\displaystyle\xrightarrow{linear}\begin{pmatrix}\phi_{2}(x)+\max\\{\phi_{1}(x)-\phi_{2}(x),0\\}\\\
\phi_{3}(x)\\\ \alpha
x+\beta\end{pmatrix}=\begin{pmatrix}\max\\{\phi_{1}(x),\phi_{2}(x)\\}\\\
\phi_{3}(x)\\\ \alpha x+\beta\end{pmatrix}$
$\displaystyle\xrightarrow{linear}\begin{pmatrix}\max\\{\phi_{1}(x),\phi_{2}(x)\\}\\\
\phi_{3}(x)-\max\\{\phi_{1}(x),\phi_{2}(x)\\}\\\ \alpha
x+\beta\end{pmatrix}\xrightarrow{\sigma}\begin{pmatrix}\max\\{\phi_{1}(x),\phi_{2}(x)\\}\\\
\sigma\big{(}\phi_{3}(x)-\max\\{\phi_{1}(x),\phi_{2}(x)\\}\big{)}\\\ \alpha
x+\beta\end{pmatrix}$
$\displaystyle\xrightarrow{linear}\begin{pmatrix}\max\\{\phi_{1}(x),\phi_{2}(x),\phi_{3}(x)\\}\\\
\phi_{4}(x)\\\ \alpha
x+\beta\end{pmatrix}\xrightarrow{\sigma}\>\dots\>\xrightarrow{\sigma}\begin{pmatrix}\max\\{\phi_{1}(x),\dots,\phi_{L-1}\\}\\\
\sigma\big{(}\phi_{L}(x)-\max\\{\phi_{1}(x),\dots\phi_{L-1}(x)\\}\big{)}\\\
\alpha x+\beta\end{pmatrix}$
$\displaystyle\xrightarrow{linear}\max\big{\\{}\phi_{1}(x),\dots,\phi_{L}(x)\big{\\}}.$

As the composition of linear maps is linear, this network can be represented
by a standard neural network architecture. Increasing the width of the network
may drastically reduce the required depth as in Remark D.3.

## References

  * [ABMM18] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee.  Understanding deep neural networks with rectified linear units.  ICLR Conference paper, 2018, arXiv:1611.01491.
  * [ADd+96] M. Alderighi, S. D’Angelo, F. d’Ovidio, E. Gummati, and G. R. Sechi.  An advanced neuron model for optimizing the siren network architecture.  In Proceedings of 1996 IEEE Second International Conference on Algorithms and Architectures for Parallel Processing, ICA/sup 3/PP’96, pages 194–200. IEEE, 1996.
  * [Ash17] P. Ashraf.  Pathological functions and the baire category theorem.  Technical report, Uppsala Universitet, 2017.
  * [Bac17] F. Bach.  Breaking the curse of dimensionality with convex neural networks.  The Journal of Machine Learning Research, 18(1):629–681, 2017, arXiv:1412.8690.
  * [Bar93] A. R. Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  IEEE Trans. Inform. Theory, 39(3):930–945, 1993.
  * [Bre11] H. Brezis.  Functional analysis, Sobolev spaces and partial differential equations.  Universitext. Springer, New York, 2011.
  * [Cho98] S. Cho.  On the mergelyan approximation property on pseudoconvex domains in $\mathbb{C}^{n}$.  Proceedings of the American Mathematical Society, 126(8):2285–2289, 1998.
  * [CJLZ19] M. Chen, H. Jiang, W. Liao, and T. Zhao.  Efficient approximation of deep relu networks for functions on low dimensional manifolds.  Advances in neural information processing systems, 32, 2019.
  * [CRBD18] R. T. Chen, Y. Rubanova, J. Bettencourt, and D. K. Duvenaud.  Neural ordinary differential equations.  Advances in neural information processing systems, 31, 2018.
  * [Cyb89] G. Cybenko.  Approximation by superpositions of a sigmoidal function.  Mathematics of control, signals and systems, 2(4):303–314, 1989\.
  * [CYRL19] I. Chami, Z. Ying, C. Ré, and J. Leskovec.  Hyperbolic graph convolutional neural networks.  Advances in neural information processing systems, 32, 2019, arXiv:1910.12933.
  * [CZWE20] Y. Chen, L. Zhang, H. Wang, and W. E.  DeePKS: A comprehensive data-driven approach toward chemically accurate density functional theory.  Journal of Chemical Theory and Computation, 17(1):170–181, dec 2020, arXiv:2008.00167.
  * [DDD+21] I. Daubechies, R. DeVore, N. Dym, S. Faigenbaum-Golovin, S. Z. Kovalsky, K.-C. Lin, J. Park, G. Petrova, and B. Sober.  Neural network approximation of refinable functions.  arXiv preprint, 2021, arXiv:2107.13191.
  * [DDF+22] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova.  Nonlinear approximation and (deep) relu networks.  Constructive Approximation, 55(1):127–172, 2022, arXiv:1905.02199.
  * [DF76] K. Diederich and J. E. Fornaess.  A strange bounded smooth domain of holomorphy.  Bull. Amer. Math. Soc., 82(1):74–76, 1976.
  * [DHP21] R. DeVore, B. Hanin, and G. Petrova.  Neural network approximation.  Acta Numerica, 30:327–444, 2021, arXiv:2012.14501.
  * [DX13] F. Dai and Y. Xu.  Approximation theory and harmonic analysis on spheres and balls.  Springer Monographs in Mathematics. Springer, New York, 2013.
  * [E17] W. E.  A proposal on machine learning via dynamical systems.  Communications in Mathematics and Statistics, 5(1):1–11, 2017.
  * [EMW19] W. E, C. Ma, and L. Wu.  A priori estimates of the population risk for two-layer neural networks.  Comm. Math. Sci., 17(5):1407 – 1425, 2019, arXiv:1810.06397.
  * [ES16] R. Eldan and O. Shamir.  The power of depth for feedforward neural networks.  In Conference on learning theory, pages 907–940, 2016, arXiv:1512.03965.
  * [Eva10] L. C. Evans.  Partial differential equations, volume 19 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, second edition, 2010.
  * [EW18] W. E and Q. Wang.  Exponential convergence of the deep neural network approximation for analytic functions.  Sci. China Math., 61(10):1733–1740, 2018, arXiv:1807.00297.
  * [EW20] W. E and S. Wojtowytsch.  On the Banach spaces associated with multi-layer ReLU networks of infinite width.  CSIAM Trans. Appl. Math., 1(3):387–440, 2020, arXiv:2007.15623.
  * [EW21] W. E and S. Wojtowytsch.  Kolmogorov width decay and poor approximators in machine learning: shallow neural networks, random feature models and neural tangent kernels.  Res. Math. Sci., 8(1):Paper No. 5, 28, 2021, arXiv:2005.10807.
  * [EW22] W. E. and S. Wojtowytsch.  Representation formulas and pointwise properties for Barron functions.  Calc. Var. Partial Differential Equations, 61(2):Paper No. 46, 37, 2022, arXiv:2006.05982.
  * [FB93] E. Freitag and R. Busam.  Funktionentheorie.  Springer-Lehrbuch. [Springer Textbook]. Springer-Verlag, Berlin, 1993\.
  * [FGMN21] J. Falcó, P. M. Gauthier, M. Manolaki, and V. Nestoridis.  A function algebra providing new Mergelyan type theorems in several complex variables.  Adv. Math., 381:Paper No. 107649, 31, 2021, arXiv:1901.01339.
  * [FsFW20] J. E. Fornæ ss, F. Forstnerič, and E. F. Wold.  Holomorphic approximation: the legacy of Weierstrass, Runge, Oka-Weil, and Mergelyan.  In Advancements in complex analysis—from theory to practice, pages 133–192. Springer, Cham, [2020] ©2020, arXiv:1802.03924.
  * [Gar95] S. J. Gardiner.  Harmonic approximation, volume 221 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 1995.
  * [GBH18] O. Ganea, G. Bécigneul, and T. Hofmann.  Hyperbolic neural networks.  Advances in neural information processing systems, 31, 2018, arXiv:1805.09112.
  * [GDW+21] Z. Gao, W. Dang, X. Wang, X. Hong, L. Hou, K. Ma, and M. Perc.  Complex networks and deep learning for eeg signal analysis.  Cognitive Neurodynamics, 15(3):369–388, 2021.
  * [GKNV22] R. Gribonval, G. Kutyniok, M. Nielsen, and F. Voigtlaender.  Approximation spaces of deep neural networks.  Constructive Approximation, 55(1):259–367, 2022, arXiv:1905.01208.
  * [GT01] D. Gilbarg and N. S. Trudinger.  Elliptic partial differential equations of second order.  Classics in Mathematics. Springer-Verlag, Berlin, 2001.  Reprint of the 1998 edition.
  * [Gub15] S. Gubkin.  $L^{2}$-Mergelyan theorems in several complex variables.  ProQuest LLC, Ann Arbor, MI, 2015.  Thesis (Ph.D.)–The Ohio State University.
  * [Han19] B. Hanin.  Universal function approximation by deep neural nets with bounded width and relu activations.  Mathematics, 7(10):992, 2019, arXiv:1708.02691.
  * [Hel14] L. L. Helms.  Potential theory.  Universitext. Springer, London, second edition, 2014.
  * [Hor91] K. Hornik.  Approximation capabilities of multilayer feedforward networks.  Neural networks, 4(2):251–257, 1991.
  * [How03] J. M. Howie.  Complex analysis.  Springer Undergraduate Mathematics Series. Springer-Verlag London, Ltd., London, 2003.
  * [Hun94] B. R. Hunt.  The prevalence of continuous nowhere differentiable functions.  Proc. Amer. Math. Soc., 122(3):711–717, 1994.
  * [HZRS16] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016, arXiv:1512.03385.
  * [IMK+14] F. Iandola, M. Moskewicz, S. Karayev, R. Girshick, T. Darrell, and K. Keutzer.  Densenet: Implementing efficient convnet descriptor pyramids.  arXiv preprint, 2014, arXiv:1404.1869.
  * [Iva10] S. Ivanov.  Zariski closed sets in $\mathbb{C}^{n}$ are of measure 0, https://mathoverflow.net/questions/25513/zariski-closed-sets-in-cn-are-of-measure-0, 2010\.
  * [Joh18] J. Johnson.  Deep, skinny neural networks are not universal approximators.  arXiv preprint, 2018, arXiv:1810.00393.
  * [K9̈3] K. Königsberger.  Analysis. 2.  Springer-Lehrbuch. [Springer Textbook]. Springer-Verlag, Berlin, 1993\.  Grundwissen Mathematik. [Basic Knowledge in Mathematics].
  * [K0̈4] K. Königsberger.  Analysis. 1.  Springer-Lehrbuch. [Springer Textbook]. Springer-Verlag, Berlin, sixth edition, 2004.
  * [KB18] J. M. Klusowski and A. R. Barron.  Approximation by combinations of relu and squared relu ridge functions with $\ell^{1}$ and $\ell^{0}$ controls.  IEEE Transactions on Information Theory, 64(12):7649–7656, 2018, arXiv:1607.07819.
  * [Lan93] S. Lang.  Real and functional analysis, volume 142 of Graduate Texts in Mathematics.  Springer-Verlag, New York, third edition, 1993.
  * [LCTW17] Q. Li, L. Chen, C. Tai, and E. Weinan.  Maximum principle based algorithms for deep learning.  The Journal of Machine Learning Research, 18(1):5998–6026, 2017\.
  * [LLPS93] M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken.  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  Neural networks, 6(6):861–867, 1993.
  * [LNK19] Q. Liu, M. Nickel, and D. Kiela.  Hyperbolic graph neural networks.  Advances in Neural Information Processing Systems, 32, 2019, arXiv:1910.12892.
  * [Loo53] L. H. Loomis.  An introduction to abstract harmonic analysis.  D. Van Nostrand Co., Inc., Toronto-New York-London, 1953.
  * [Mak98] Y. Makovoz.  Uniform approximation by neural networks.  Journal of Approximation Theory, 95(2):215–228, 1998.
  * [Mer51] S. N. Mergelyan.  On the representation of functions by series of polynomials on closed sets.  Doklady Akad. Nauk SSSR (N.S.), 78:405–408, 1951.
  * [Mha96] H. N. Mhaskar.  Neural networks for optimal approximation of smooth and analytic functions.  Neural computation, 8(1):164–177, 1996.
  * [MP99] V. Maiorov and A. Pinkus.  Lower bounds for approximation by MLP neural networks.  Neurocomputing, 25(1-3):81–91, 1999.
  * [MP16] H. N. Mhaskar and T. Poggio.  Deep vs. shallow networks: an approximation theory perspective.  Anal. Appl. (Singap.), 14(6):829–848, 2016.
  * [Mun00] J. R. Munkres.  Topology.  Prentice Hall, Inc., Upper Saddle River, NJ, 2000.  Second edition of [ MR0464128].
  * [Oka61] K. Oka.  Sur les fonctions analytiques de plusieurs variables.  Iwanami Shoten, Tokyo, 1961.
  * [ON15] K. O’Shea and R. Nash.  An introduction to convolutional neural networks.  arXiv preprint, 2015, arXiv:1511.08458.
  * [Pin99] A. Pinkus.  Approximation theory of the mlp model in neural networks.  Acta numerica, 8(1):143–195, 1999.
  * [PN21a] R. Parhi and R. D. Nowak.  Banach space representer theorems for neural networks and ridge splines.  J. Mach. Learn. Res., 22(43):1–40, 2021, arXiv:2006.05626.
  * [PN21b] R. Parhi and R. D. Nowak.  What kinds of functions do deep neural networks learn? insights from variational spline theory.  arXiv preprint, 2021, arXiv:2105.03361.
  * [PV18] P. Petersen and F. Voigtlaender.  Optimal approximation of piecewise smooth functions using deep relu neural networks.  Neural Networks, 108:296–330, 2018, arXiv:1709.05289.
  * [PVM+21] W. Peng, T. Varanka, A. Mostafa, H. Shi, and G. Zhao.  Hyperbolic deep neural networks: A survey.  arXiv preprint, 2021, arXiv:2101.04562.
  * [Rud87] W. Rudin.  Real and complex analysis.  McGraw-Hill Book Co., New York, third edition, 1987.
  * [SH19] J. Schmidt-Hieber.  Deep relu network approximation of functions on a manifold.  arXiv preprint, 2019, arXiv:1908.00695.
  * [SMB+20] V. Sitzmann, J. Martel, A. Bergman, D. Lindell, and G. Wetzstein.  Implicit neural representations with periodic activation functions.  Advances in Neural Information Processing Systems, 33:7462–7473, 2020, arXiv:2006.09661.
  * [Suz18] T. Suzuki.  Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality, 2018, arXiv:1810.08033.
  * [SX19] J. W. Siegel and J. Xu.  On the approximation properties of neural networks.  arXiv preprint, 2019, arXiv:1904.02311.
  * [SX20a] J. W. Siegel and J. Xu.  Approximation rates for neural networks with general activation functions.  Neural Networks, 128:313–321, 2020, arXiv:1904.02311.
  * [SX20b] J. W. Siegel and J. Xu.  High-order approximation rates for neural networks with reluk activation functions.  arXiv preprint, 2020, arXiv:2012.07205.
  * [TBC+16] M. Tygert, J. Bruna, S. Chintala, Y. LeCun, S. Piantino, and A. Szlam.  A mathematical motivation for complex-valued convolutional networks.  Neural computation, 28(5):815–825, 2016, arXiv:1503.03438.
  * [TBZ+17] C. Trabelsi, O. Bilaniuk, Y. Zhang, D. Serdyuk, S. Subramanian, J. Santos, S. Mehri, N. Rostamzadeh, Y. Bengio, and C. Pal.  Deep complex networks.  arXiv preprint, 2017, arXiv:1705.09792.
  * [Tre13] L. N. Trefethen.  Approximation theory and approximation practice.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013.
  * [Voi20] F. Voigtlaender.  The universal approximation theorem for complex-valued neural networks.  arXiv preprint, 2020, arXiv:2012.03351.
  * [VSL17] P. Virtue, X. Y. Stella, and M. Lustig.  Better than real: Complex-valued neural nets for mri fingerprinting.  In 2017 IEEE international conference on image processing (ICIP), pages 3953–3957. IEEE, 2017, arXiv:1707.00070.
  * [Wei35] A. Weil.  L’intégrale de Cauchy et les fonctions de plusieurs variables.  Math. Ann., 111(1):178–182, 1935.
  * [XN21a] Z. Xuan and K. Narayanan.  Deep joint source-channel coding for transmission of correlated sources over awgn channels.  In ICC 2021-IEEE International Conference on Communications, pages 1–6. IEEE, 2021.
  * [XN21b] Z. Xuan and K. Narayanan.  Low-delay analog distributed joint source-channel coding using sirens.  In 2021 29th European Signal Processing Conference (EUSIPCO), pages 1601–1605. IEEE, 2021.
  * [Yar17] D. Yarotsky.  Error bounds for approximations with deep ReLU networks.  Neural Networks, 94:103–114, 2017, arXiv:1610.01145.
  * [YZ19] D. Yarotsky and A. Zhevnerchuk.  The phase diagram of approximation rates for deep neural networks.  arXiv preprint, 2019, arXiv:1906.09477.
  * [Zha18] L. Zhang.  Deep potential molecular dynamics: A scalable model with the accuracy of quantum mechanics.  Physical Review Letters, 120(14), 2018, arXiv:1707.09571.