Universal Approximation Theorem

Let $\sigma$ be any continuous sigmoidal function (i.e., $\sigma(t) \to 1$ as $t \to +\infty$ and $\sigma(t) \to 0$ as $t \to -\infty$). For any continuous function $g: K \to \mathbb{R}$ on a compact set $K \subset \mathbb{R}^d$ and any $\epsilon > 0$, there exists $N \in \mathbb{N}$ and parameters $\{\alpha_j, w_j, b_j\}_{j=1}^N$ such that:

$\sup_{x \in K} \left| g(x) - \sum_{j=1}^{N} \alpha_j \, \sigma(w_j^T x + b_j) \right| < \epsilon$

Each hidden neuron $\sigma(w_j^T x + b_j)$ implements a soft step function in the direction $w_j$. By combining many step functions at different orientations, positions, and scales, you can approximate any continuous function to arbitrary precision. This is similar to how Fourier series approximate functions using sums of sines and cosines, but with learned basis functions.

The UAT justifies using neural networks as a flexible function class. Before this result, it was unclear whether neural networks could represent the functions arising in real-world tasks. The theorem says they can, at least in principle, even with a single hidden layer.

The theorem does not bound $N$ (the required width). For some functions, $N$ may need to be exponentially large in the input dimension $d$. The theorem does not address optimization (can gradient descent find the right weights?) or generalization (will the approximation work on unseen inputs?). A network with $N$ parameters fit to $n < N$ data points can perfectly interpolate training data while computing arbitrary nonsense elsewhere.

There exist families of functions that can be represented exactly by a ReLU network of depth $k$ and width $O(d)$, but require width $\Omega(2^{k-1})$ if restricted to depth 2 (a single hidden layer). Deeper networks can be exponentially more parameter-efficient than shallow ones.

Depth enables composition. A function that is naturally expressed as $f_k \circ f_{k-1} \circ \cdots \circ f_1$ can be represented with $O(kd)$ parameters using $k$ layers, each implementing one $f_i$. A single hidden layer must "flatten" this composition, requiring exponentially many neurons to represent all the intermediate computations simultaneously.

This explains why deep networks outperform shallow wide networks in practice. Real-world functions (image classification, language modeling) are compositional in nature: edges compose into textures, textures into parts, parts into objects. Deep networks exploit this compositional structure; shallow networks cannot.

Depth separation results are worst-case. For some function classes (e.g., smooth functions with bounded derivatives), shallow networks approximate almost as efficiently as deep ones. The practical advantage of depth depends on whether the target function has compositional structure.