universal approximation theorem

The universal approximation theorem is the reassuring mathematical statement that neural networks are, in principle, expressive enough to represent essentially any function you might want. More precisely, a network with even a single hidden layer, if made wide enough and given a suitable nonlinear activation, can approximate any continuous function on a bounded region to any desired accuracy. It is the theoretical license for using neural networks at all: whatever the true mapping from images to labels is, some network can represent it arbitrarily well.

The classical results (Cybenko 1989 for sigmoidal activations; Hornik 1991 generalizing the activation) say that for any continuous function f on a compact (closed and bounded) set, and any tolerance epsilon greater than 0, there exists a single-hidden-layer network g with finitely many neurons and a non-polynomial activation such that the magnitude of g(x) minus f(x) is less than epsilon for all x in that set. A complementary deep, bounded-width version shows networks of fixed width but growing depth are also universal. The key hypotheses are continuity of the target, a bounded domain, and a non-polynomial activation (a polynomial activation fails, because it can only produce polynomials).

The theorem is an existence result, and its caveats are as important as the statement. First, it guarantees a network exists, not that gradient descent will find it. Second, wide enough can mean astronomically, even exponentially, many neurons; the theorem says nothing about doing it efficiently. Third, it promises approximation on the training domain, not generalization to new inputs. Fourth, it assumes you can set the weights to the right values, but learning them from finite data is a separate, harder problem. So universality explains why networks can work, not why a particular trained network does.

If one wide layer suffices in principle, why build deep, convolutional, attention-based vision models? Because efficiency and generalization, not mere representability, are what matter in practice. Many functions that need exponentially many neurons in a shallow network need only polynomially many in a deep one (depth-separation results), and architectural priors (convolution's locality and translation equivariance, attention's content-based routing) make the right functions easy to learn from limited data. The universal approximation theorem says the destination is reachable; modern architecture design is about getting there with feasible size and data.