Universal Approximation

Definition

$\mathcal{F}=\mathrm{span}\{x\mapsto \sigma (w^{\top }x+b)\}$ is dense in $C(K)$ for every compact $K\subset {\mathbb{R}}^d$ if $\sigma$ is continuous and not a polynomial (Pinkus 1999).

Formula

$$\forall f^{\ast }\in C(K),\epsilon >0\exists m,\theta :\underset{x\in K}{\sup }|f^{\ast }(x)-f_{\theta }(x)|<\epsilon$$

It says nothing about the number of units needed, the Lipschitz constant of the approximation, whether GD can find it from data (Theorem 7: it may need $2^{\Omega (d)}$ gradient steps) or about generalization. Depth can be exponentially more efficient than width (Telgarsky 2016).

Appears in

• Lecture 8, Theorem 6 (universal approximation) and proof, trainability

Related concepts

• Neural Tangent Kernel