Universal approximation theorem

One of the first versions of the arbitrary width case was proven by George Cybenko in 1989 for sigmoid activation functions.[11] 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[12] 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[13] and later Allan Pinkus in 1999[14] showed that the universal approximation property is equivalent to having a nonpolynomial activation function. In 2022, Shen Zuowei, Haizhao Yang, and Shijun Zhang[15] obtained precise quantitative information on the depth and width required to approximate a target function by deep and wide ReLU neural networks.

The arbitrary depth case was also studied by a number of authors such as Gustaf Gripenberg in 2003,[16] Dmitry Yarotsky,[17] Zhou Lu et al in 2017,[18] Boris Hanin and Mark Sellke in 2018[19] who focused on neural networks with ReLU activation function. In 2020, Patrick Kidger and Terry Lyons[20] extended those results to neural networks with general activation functions such, e.g. tanh, GeLU, or Swish, and in 2022, their result was made quantitative by Leonie Papon and Anastasis Kratsios[21] who derived explicit depth estimates depending on the regularity of the target function and of the activation function.

The question of minimal possible width for universality was first studied in 2021, Park et al obtained the minimum width required for the universal approximation of L^p functions using feed-forward neural networks with ReLU as activation functions.[10] Similar results that can be directly applied to residual neural networks were also obtained in the same year by Paulo Tabuada and Bahman Gharesifard using control-theoretic arguments.[22][23] In 2023, Cai[24] obtained the optimal minimum width bound for the universal approximation.

The bounded depth and bounded width case was first studied by Maiorov and Pinkus in 1999.[25] They showed that there exists an analytic sigmoidal activation function such that two hidden layer neural networks with bounded number of units in hidden layers are universal approximators. Using algorithmic and computer programming techniques, Guliyev and Ismailov constructed a smooth sigmoidal activation function providing universal approximation property for two hidden layer feedforward neural networks with less units in hidden layers.[26] It was constructively proved in 2018 paper[27] that single hidden layer networks with bounded width are still universal approximators for univariate functions, but this property is no longer true for multivariable functions.

Several extensions of the theorem exist, such as to discontinuous activation functions,[13] noncompact domains,[20] certifiable networks,[28] random neural networks,[29] and alternative network architectures and topologies.[20][30]

A spate of papers in the 1980s—1990s, from George Cybenko and Kurt Hornik etc, established several universal approximation theorems for arbitrary width and bounded depth.[31][11][32][12] See[33][34][14] for reviews. The following is the most often quoted:

Universal approximation theorem — Let ${\displaystyle C(X,\mathbb {R} ^{m})}$ denote the set of continuous functions from a subset ${\displaystyle X}$ of a Euclidean ${\displaystyle \mathbb {R} ^{n}}$ space to a Euclidean space ${\displaystyle \mathbb {R} ^{m}}$. 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 problem with polynomials may be removed by allowing the outputs of the hidden layers to be multiplied together (the "pi-sigma networks"), yielding the generalization:[32]

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.[18] 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[18] it was shown that ReLU networks with width n + 1 were sufficient to approximate any continuous function of n-dimensional input variables.[35] The following refinement, specifies the optimal minimum width for which such an approximation is possible and is due to.[36]

Universal approximation theorem (L1 distance, ReLU activation, arbitrary depth, minimal width). For any Bochner–Lebesgue p-integrable function ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ^{m}}$ and any ${\displaystyle \varepsilon >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}}\|f(x)-F(x)\|^{p}\,\mathrm {d} x<\varepsilon .}$

Moreover, there exists a function ${\displaystyle f\in L^{p}(\mathbb {R} ^{n},\mathbb {R} ^{m})}$ and some ${\displaystyle \varepsilon >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.

Remark: If the activation is replaced by leaky-ReLU, and the input is restricted in a compact domain, then the exact minimum width is[24] ${\displaystyle d_{m}=\max\{n,m,2\}}$.

Quantitative refinement: In the case where, when ${\displaystyle {\mathcal {X}}=[0,1]^{d}}$ and ${\displaystyle D=1}$ and where ${\displaystyle \sigma }$ is the ReLU activation function, the exact depth and width for a ReLU network to achieve ${\displaystyle \varepsilon }$ error is also known.[37] If, moreover, the target function ${\displaystyle f}$ is smooth, then the required number of layer and their width can be exponentially smaller.[38] Even if ${\displaystyle f}$ is not smooth, the curse of dimensionality can be broken if ${\displaystyle f}$ admits additional "compositional structure".[39][40]

Together, the central result of[20] yields the following universal approximation theorem for networks with bounded width (see also[16] for the first result of this kind).

Universal approximation theorem (Uniform 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.

Quantitative refinement: The number of layers and the width of each layer required to approximate ${\displaystyle f}$ to ${\displaystyle \varepsilon }$ precision known;[21] moreover, the result hold true when ${\displaystyle {\mathcal {X}}}$ and ${\displaystyle \mathbb {R} ^{D}}$ are replaced with any non-positively curved Riemannian manifold.

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.[18][19][41]

The first result on approximation capabilities of neural networks with bounded number of layers, each containing a limited number of artificial neurons was obtained by Maiorov and Pinkus.[25] Their remarkable result revealed that such networks can be universal approximators and for achieving this property two hidden layers are enough.

Universal approximation theorem:[25] There exists an activation function ${\displaystyle \sigma }$ which is analytic, strictly increasing and sigmoidal and has the following property: For any ${\displaystyle f\in C[0,1]^{d}}$ and ${\displaystyle \varepsilon >0}$ there exist constants ${\displaystyle d_{i},c_{ij},\theta _{ij},\gamma _{i}}$, and vectors ${\displaystyle \mathbf {w} ^{ij}\in \mathbb {R} ^{d}}$ for which

$${\displaystyle \left\vert f(\mathbf {x} )-\sum _{i=1}^{6d+3}d_{i}\sigma \left(\sum _{j=1}^{3d}c_{ij}\sigma (\mathbf {w} ^{ij}\cdot \mathbf {x-} \theta _{ij})-\gamma _{i}\right)\right\vert <\varepsilon }$$

for all ${\displaystyle \mathbf {x} =(x_{1},...,x_{d})\in [0,1]^{d}}$.

This is an existence result. It says that activation functions providing universal approximation property for bounded depth bounded width networks exist. Using certain algorithmic and computer programming techniques, Guliyev and Ismailov efficiently constructed such activation functions depending on a numerical parameter. The developed algorithm allows one to compute the activation functions at any point of the real axis instantly. For the algorithm and the corresponding computer code see.[26] The theoretical result can be formulated as follows.

Universal approximation theorem:[26][27] Let ${\displaystyle [a,b]}$ be a finite segment of the real line, ${\displaystyle s=b-a}$ and ${\displaystyle \lambda }$ be any positive number. Then one can algorithmically construct a computable sigmoidal activation function ${\displaystyle \sigma \colon \mathbb {R} \to \mathbb {R} }$, which is infinitely differentiable, strictly increasing on ${\displaystyle (-\infty ,s)}$, ${\displaystyle \lambda }$ -strictly increasing on ${\displaystyle [s,+\infty )}$, and satisfies the following properties:

1) For any ${\displaystyle f\in C[a,b]}$ and ${\displaystyle \varepsilon >0}$ there exist numbers ${\displaystyle c_{1},c_{2},\theta _{1}}$ and ${\displaystyle \theta _{2}}$ such that for all ${\displaystyle x\in [a,b]}$

$${\displaystyle |f(x)-c_{1}\sigma (x-\theta _{1})-c_{2}\sigma (x-\theta _{2})|<\varepsilon }$$

2) For any continuous function ${\displaystyle F}$ on the ${\displaystyle d}$-dimensional box ${\displaystyle [a,b]^{d}}$ and ${\displaystyle \varepsilon >0}$, there exist constants ${\displaystyle e_{p}}$, ${\displaystyle c_{pq}}$, ${\displaystyle \theta _{pq}}$ and ${\displaystyle \zeta _{p}}$ such that the inequality

$${\displaystyle \left|F(\mathbf {x} )-\sum _{p=1}^{2d+2}e_{p}\sigma \left(\sum _{q=1}^{d}c_{pq}\sigma (\mathbf {w} ^{q}\cdot \mathbf {x} -\theta _{pq})-\zeta _{p}\right)\right|<\varepsilon }$$

holds for all ${\displaystyle \mathbf {x} =(x_{1},\ldots ,x_{d})\in [a,b]^{d}}$. Here the weights ${\displaystyle \mathbf {w} ^{q}}$, ${\displaystyle q=1,\ldots ,d}$, are fixed as follows:

$${\displaystyle \mathbf {w} ^{1}=(1,0,\ldots ,0),\quad \mathbf {w} ^{2}=(0,1,\ldots ,0),\quad \ldots ,\quad \mathbf {w} ^{d}=(0,0,\ldots ,1).}$$

In addition, all the coefficients ${\displaystyle e_{p}}$, except one, are equal.

Here “${\displaystyle \sigma \colon \mathbb {R} \to \mathbb {R} }$ is ${\displaystyle \lambda }$-strictly increasing on some set ${\displaystyle X}$” means that there exists a strictly increasing function ${\displaystyle u\colon X\to \mathbb {R} }$ such that ${\displaystyle |\sigma (x)-u(x)|\leq \lambda }$ for all ${\displaystyle x\in X}$. Clearly, a ${\displaystyle \lambda }$-increasing function behaves like a usual increasing function as ${\displaystyle \lambda }$ gets small. In the "depth-width" terminology, the above theorem says that for certain activation functions depth-${\displaystyle 2}$ width-${\displaystyle 2}$ networks are universal approximators for univariate functions and depth-${\displaystyle 3}$ width-${\displaystyle (2d+2)}$ networks are universal approximators for ${\displaystyle d}$-variable functions (${\displaystyle d>1}$).

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.[42] In 2020,[43] 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