Universal approximation theorem

One of the first versions of the arbitrary width case was proven by George Cybenko in 1989 for sigmoid activation functions.[8] Kurt Hornik, Maxwell Stinchcombe, and Halbert White showed in 1989 that multilayer feed-forward networks with as few as one hidden layer are universal approximators.[1] Hornik also showed in 1991[9] that it is not the specific choice of the activation function but rather the multilayer feed-forward architecture itself that gives neural networks the potential of being universal approximators. Moshe Leshno et al in 1993[10] and later Allan Pinkus in 1999[11] showed that the universal approximation property is equivalent to having a nonpolynomial activation function.

The arbitrary depth case was also studied by a number of authors, such as Zhou Lu et al in 2017,[12] Boris Hanin and Mark Sellke in 2018,[13] and Patrick Kidger and Terry Lyons in 2020.[14] The result minimal width per layer was refined in 2020[15][16] for residual networks.

Several extensions of the theorem exist, such as to discontinuous activation functions,[10] noncompact domains,[14] certifiable networks,[17] random neural networks,[18] and alternative network architectures and topologies.[14][19]

The classical form of the universal approximation theorem for arbitrary width and bounded depth is as follows.[8][9][20][21] It extends[11] the classical results of George Cybenko and Kurt Hornik.

Universal approximation theorem: Let ${\displaystyle C(X,Y)}$ denote the set of continuous functions from ${\displaystyle X}$ to ${\displaystyle Y}$. Let ${\displaystyle \sigma \in C(\mathbb {R} ,\mathbb {R} )}$. Note that ${\displaystyle (\sigma \circ x)_{i}=\sigma (x_{i})}$, so ${\displaystyle \sigma \circ x}$ denotes ${\displaystyle \sigma }$ applied to each component of ${\displaystyle x}$.

Then ${\displaystyle \sigma }$ is not polynomial if and only if for every ${\displaystyle n\in \mathbb {N} }$, ${\displaystyle m\in \mathbb {N} }$, compact ${\displaystyle K\subseteq \mathbb {R} ^{n}}$, ${\displaystyle f\in C(K,\mathbb {R} ^{m}),\varepsilon >0}$ there exist ${\displaystyle k\in \mathbb {N} }$, ${\displaystyle A\in \mathbb {R} ^{k\times n}}$, ${\displaystyle b\in \mathbb {R} ^{k}}$, ${\displaystyle C\in \mathbb {R} ^{m\times k}}$ such that

$${\displaystyle \sup _{x\in K}\|f(x)-g(x)\|<\varepsilon }$$

where

$${\displaystyle g(x)=C\cdot (\sigma \circ (A\cdot x+b))}$$

Such an ${\displaystyle f}$ can also be approximated by a network of greater depth by using the same construction for the first layer and approximating the identity function with later layers.

The 'dual' versions of the theorem consider networks of bounded width and arbitrary depth. A variant of the universal approximation theorem was proved for the arbitrary depth case by Zhou Lu et al. in 2017.[12] They showed that networks of width n+4 with ReLU activation functions can approximate any Lebesgue integrable function on n-dimensional input space with respect to ${\displaystyle L^{1}}$ distance if network depth is allowed to grow. It was also shown that if the width was less than or equal to n, this general expressive power to approximate any Lebesgue integrable function was lost. In the same paper[12] it was shown that ReLU networks with width n+1 were sufficient to approximate any continuous function of n-dimensional input variables.[22] The following refinement, specifies the optimal minimum width for which such an approximation is possible and is due to.[23]

Universal approximation theorem (L1 distance, ReLU activation, arbitrary depth, minimal width). For any Bochner–Lebesgue p-integrable function ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}}$ and any ${\displaystyle \epsilon >0}$, there exists a fully-connected ReLU network ${\displaystyle F}$ of width exactly ${\displaystyle d_{m}=\max\{{n+1},m\}}$, satisfying

${\displaystyle \int _{\mathbb {R} ^{n}}\left\|f(x)-F_{}(x)\right\|^{p}\mathrm {d} x<\epsilon }$.

Moreover, there exists a function ${\displaystyle f\in L^{p}(\mathbb {R} ^{n},\mathbb {R} ^{m})}$ and some ${\displaystyle \epsilon >0}$, for which there is no fully-connected ReLU network of width less than ${\displaystyle d_{m}=\max\{{n+1},m\}}$ satisfying the above approximation bound.

Together, the central result of [14] yields the following universal approximation theorem for networks with bounded width.

Universal approximation theorem (non-affine activation, arbitrary depth, constrained width). Let ${\displaystyle {\mathcal {X}}}$ be a compact subset of ${\displaystyle \mathbb {R} ^{d}}$. Let ${\displaystyle \sigma$ :\mathbb {R} \to \mathbb {R} } be any non-affine continuous function which is continuously differentiable at at least one point, with nonzero derivative at that point. Let ${\displaystyle {\mathcal {N}}_{d,D:d+D+2}^{\sigma }}$ denote the space of feed-forward neural networks with ${\displaystyle d}$ input neurons, ${\displaystyle D}$ output neurons, and an arbitrary number of hidden layers each with ${\displaystyle d+D+2}$ neurons, such that every hidden neuron has activation function ${\displaystyle \sigma }$ and every output neuron has the identity as its activation function, with input layer ${\displaystyle \phi }$, and output layer ${\displaystyle \rho }$. Then given any ${\displaystyle \varepsilon >0}$ and any ${\displaystyle f\in C({\mathcal {X}},\mathbb {R} ^{D})}$, there exists ${\displaystyle {\hat {f}}\in {\mathcal {N}}_{d,D:d+D+2}^{\sigma }}$ such that

${\displaystyle \sup _{x\in {\mathcal {X}}}\,\left\|{\hat {f}}(x)-f(x)\right\|<\varepsilon .}$

In other words, ${\displaystyle {\mathcal {N}}}$ is dense in ${\displaystyle C({\mathcal {X}};\mathbb {R} ^{D})}$ with respect to the topology of uniform convergence.

Certain necessary conditions for the bounded width, arbitrary depth case have been established, but there is still a gap between the known sufficient and necessary conditions.[12][13][24]

Achieving useful universal function approximation on graphs (or rather on graph isomorphism classes) has been a longstanding problem. The popular graph convolutional neural networks (GCNs or GNNs) can be made as discriminative as the Weisfeiler–Leman graph isomorphism test.[25] In 2020,[26] a universal approximation theorem result was established by Brüel-Gabrielsson, showing that graph representation with certain injective properties is sufficient for universal function approximation on bounded graphs and restricted universal function approximation on unbounded graphs, with an accompanying ${\displaystyle O(}$#edges${\displaystyle \times }$#nodes${\displaystyle )}$-runtime method that performed at state of the art on a collection of benchmarks.

• Kolmogorov–Arnold representation theorem
• Representer theorem
• No free lunch theorem
• Stone–Weierstrass theorem
• Fourier series