Universal approximation theorem

Summary

The universal approximation theorem (Cybenko, 1989; Hornik, 1991) applies to continuous functions on a compact subset of $R^{n}$ . A feed-forward network with one sufficiently wide hidden layer and a suitable non-polynomial activation can approximate any such function to arbitrary accuracy.

UAT is often quoted as “neural networks can learn anything.” That is a misleading summary; the theorem is an existence result, not a guarantee that:

training will find the approximating network,
the network has reasonable size,
it generalizes from finite samples,
it is practical for the input dimension you care about.

Knowing what UAT does and doesn’t promise is a senior-level expectation; the wrong reading shows up regularly in interviews.

What the theorem says (precisely)

For any continuous function $f : K \to R$ on a compact $K \subset R^{n}$ and any $ε > 0$ , there exists a network

g (x) = i = 1 \sum N c_{i} σ (w_{i}^{⊤} x + b_{i})

with finite width $N$ such that $sup_{x \in K} ∣ g (x) - f (x) ∣ < ε$ , where $σ$ is a continuous sigmoidal activation in Cybenko’s formulation. Later results broaden the sufficient activation conditions.

Learning objective: read universal approximation as a uniform error guarantee for some finite network on a compact domain, then separate that existence claim from width, optimization, generalization, and extrapolation.

The quantifiers are the lesson

What does “there exists an approximating network” actually guarantee?

Read it this way: choose the compact domain and tolerance first. The theorem says that some finite network can keep its largest vertical error below that tolerance everywhere in the domain. It does not tell you how wide the network is, how to find its weights, whether it generalizes from samples, or what happens outside the domain. The target, approximation, and coordinates are an original construction checked against Cybenko (1989).

Modern extensions:

ReLU networks are also universal approximators (Pinkus, 1999; Lu et al., 2017).
Deep networks with bounded width can be universal (Lu et al., 2017): width $\geq n + 4$ suffices for some classes.

What the theorem does not say

Width may be exponential. UAT does not bound $N$ . For some functions, the required width is exponential in input dimension.
Training is not guaranteed. UAT is non-constructive. It proves existence, not how SGD finds it.
Generalization is not addressed. A perfect fit on training data is not the same as predicting on test data.
Deep beats wide for some functions. UAT applies to wide-shallow nets; depth gives exponential efficiency for many natural functions (Telgarsky, 2016).

Why deep nets are practically necessary

If shallow nets are universal, why use deep ones? Two reasons:

Compositional efficiency: many functions of practical interest (image features, language structure) are naturally compositional. Deep nets express them with polynomially fewer units than shallow nets (Mhaskar & Poggio, 2016; Eldan & Shamir, 2016).
Optimization landscape: SGD finds good solutions in deep over-parameterized networks more reliably than in narrow shallow ones. Empirically and per modern theory (NTK, lottery ticket, etc.).

So UAT justifies “neural networks can fit anything in principle.” Practical deep learning relies on additional, separately-justified properties.

Barron’s theorem (1993): for functions with bounded “Barron norm,” the approximation error of a width- $N$ shallow net is $O (1/ N)$ . Independent of input dimension. Constructive guarantee for a restricted function class.
Kolmogorov–Arnold theorem (1957): continuous functions on $[0, 1]^{n}$ can be exactly represented as a sum of compositions of single-variable continuous functions. Inspired KAN architectures (2024).
Width-bounded ReLU UAT: width $n + 4$ is sufficient for universality (Lu et al., 2017).

What to say in interviews

If asked “do neural networks really learn anything?”:

State UAT precisely (one hidden layer, non-polynomial activation, compact domain).
Note that it is non-constructive and bounds nothing about width or trainability.
Argue that practical deep learning relies on (a) compositional efficiency of depth, (b) the optimization landscape of over-parameterized networks, and (c) inductive biases of architectures (CNNs for translation invariance, transformers for sequences).

That sequence demonstrates senior-level understanding rather than sloganeering.

Common pitfalls

Citing UAT as a guarantee that any NN learns its task. UAT says some network exists; SGD may not find it.
Using UAT to justify wide-shallow nets. Empirically, depth helps; UAT alone doesn’t predict that.
Ignoring the compactness assumption. UAT is for compact domains; behavior outside the training support is unconstrained.