Universal Approximation Theorem

The universal approximation theorem states that for any continuous function, there exists a shallow network that can approximate this function to any specified precision.

Let’s say we have a shallow neural network of the form:

$$y={\varphi }_0+{\varphi }_1{h}_1+\cdots +{\varphi }_n{h}_n$$

where $d$-th hidden unit $h_d$ is:

$$h_d=a[{\theta }_{d_0}+{\theta }_{d_1}x]$$

where $a$ is an activation function such as ReLU. We can then write the neural network as:

$$y={\varphi }_0+\sum _{d=1}^D{\varphi }_d{h}_d$$

The number of hidden units in a shallow network is a measure of the network capacity.

With ReLU activation functions, the output of a network with $D$ hidden units has at most D “joints” and so is a piecewise linear function with at most $D+1$ linear regions：

As we add more hidden units, the model can approximate more complex functions. With enough capacity (more hidden units), a shallow network can describe any continuous 1D function defined on a compact subset of the real line to arbitrary precision.

To see this, consider that every time we add a hidden unit, we add another linear region to the function. More regions means that each represents smaller sections of the function, which in turn means a better approximation.

Why would we ever need a neural network with more than one hidden layer? The theorem guarantees existence, but no claims about the scaling of $N$ (the number of hidden neurons) as a function of $ϵ$, the desired approximation error. $N$ might grow exponentially as $ϵ$ get smaller.

Width Version

The width version of this theorem states that there exists a network with one hidden layer containing a finite number of hidden units that can approximate any specified continuous function on a compact subset of ${\mathbb{R}}^n$ to arbitrary accuracy.

Depth Version

There exist a network with ReLU activation functions and at least $D_i+4$ hidden units in each layer that can approximate any $D_i$-dimensional Lebesgue integrable function to arbitrary accuracy given enough layers. This was shown in [1709.02540] The Expressive Power of Neural Networks: A View from the Width.

This is known as the depth version of the universal approximation theorem.

Formalization

Universal Approximation Theorem

Let $\sigma$ be any continuous sigmoidal function. The finite sums of the form

$$G(x)=\sum _{j=1}^N{\alpha }_j\sigma ({\omega }_{j}x+{\theta }_j)$$

• ($w_j,{\alpha }_j$ are weights and ${\theta }_j$ are biases)

are dense in $C(I_n)$ (continuous functions in domain $I_n$).

In other words, given any $f\in C(I_n)$ and $ϵ>0$, there is a sum $G(s)$, of the above form, for which

$$\left|G(x)-f(x)\right|<ϵ\text{for all }x\in I_n$$

In this example, $I_n=[0,1{]}^n$. It just needs to be a compact domain.

Sigmoidal function

A function $\sigma$ is “sigmoidal” if

$$\sigma (x)=\{\begin{array}{ll}1& \text{as }x\to \infty \\ 0& \text{as }x\to -\infty \end{array}$$

Informal Proof

Suppose we let ${\omega }_j\to \infty$ for $j=1,\dots ,N$, then

$$\sigma ({\omega }_{j}x)⟶\{\begin{array}{ll}0& \text{for }x\le 0\\ 1& \text{for }x>0\end{array}$$

By shifting the $x$-axis by $b_j$, we get

$$\sigma ({\omega }_j(x-b_j))⟶\{\begin{array}{ll}0& \text{for }x\le b_j,\\ 1& \text{for }x>b_j\end{array}$$

Within this limit, we obtain the Heaviside step function:

$$H(x)=\underset{{\omega }_j\to \infty }{\lim }\sigma ({\omega }_{j}x)$$

Let us define

$$H(x;b)=\underset{\omega \to \infty }{\lim }\sigma (\omega (x-b))$$

We can use two such functions to create a horizontal piece:

$$P(x;b,\delta )=H(x;b)-H(x;b+\delta )$$

where $P$ is made from sigmoidal functions:

The piece function $P(x;b,\delta )$ is defined as

Since $f(x)$ is continuous,

$$\underset{x\to a}{\lim }f(x)=f(a),\forall a\in I_n$$

Therefore, $\exists$ an interval, $(a_j,a_j+\Delta x)$, such that

$$\left|f(x)-f(a_j)\right|<ϵ,\forall x\in (a_j,a_j+\Delta x)$$

As a result, the function

$$G(x)=\sum _{j=1}^{N^{\prime }}f(a_j)P(x;b_j,{\delta }_j)$$

satisfies the constraint

$$\left|G(x)-f(x)\right|<ϵ\text{ for all }x\in I_n$$

Here, $N^{\prime }$ is the number of subintervals. $G(x)$ can also be written in terms of threshold functions (which can be approximated by sigmoids) as:

$$G(x)=\sum _{j=1}^{N^{\prime }}f(a_j)(H(x;b_j)-H(x;b_j+{\delta }_j))$$

Thus, the total number of hidden neurons required to construct $G(x)$ is $N=2N^{\prime }$.

Instead of using sigmoid, we can do ReLU, etc. The proof would be different but in theory the result should be the same.