Universal approximation theorem

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 }$$

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

Universal approximation theorem for pi-sigma networks — With any nonconstant activation function, a one-hidden-layer pi-sigma network is a universal approximator.

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 .}$$

${\displaystyle f\in L^{p}(\mathbb {R} ^{n},\mathbb {R} ^{m})}$

${\displaystyle \varepsilon >0}$

${\displaystyle d_{m}=\max\{n+1,m\}}$

Remark: If the activation is replaced by leaky-ReLU, and the input is restricted in a compact domain, then the exact minimum width is^[19] ${\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.^[42] If, moreover, the target function ${\displaystyle f}$ is smooth, then the required number of layer and their width can be exponentially smaller.^[43] Even if ${\displaystyle f}$ is not smooth, the curse of dimensionality can be broken if ${\displaystyle f}$ admits additional "compositional structure".^[44][45]

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;^[20] moreover, the result hold true when ${\displaystyle {\mathcal {X}}}$ and ${\displaystyle \mathbb {R} ^{D}}$ are replaced with any non-positively curved Riemannian manifold.

Universal approximation theorem:^[12] — 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 }$$

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

Universal approximation theorem:^[13][14] — 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.