8 Universal approximation
Context
Backprop (#7) taught the field how to train networks — but what can they in principle express? Are there functions out of their reach? Cybenko (1989) and Hornik (1991) give a rigorous answer.
The idea and the mechanism
A network with one hidden layer computes a weighted sum of nonlinear "bumps":
The theorem: for any continuous f on a compact set and any ε > 0 there exist an N and parameters such that sup|f − g| < ε. With bumps like these you can tile any smooth shape. Hornik strengthened it: universality comes from the architecture itself, not from the sigmoid — any non-polynomial activation will do, which is why ReLU is universal too.
functional analysis What the theorem gives you — and what it does NOT
Cybenko's proof is non-constructive: it shows that the set of sums σ(w·x+b) is dense in the space of continuous functions (via the Hahn–Banach theorem and properties of measures). Two important "no"s follow:
- No number of neurons. The theorem guarantees that an N exists, but puts no bound on it — reaching the accuracy you want may take exponentially many neurons.
- No guarantee of training. The network exists, but whether gradient descent from a random initialization will find it is a separate question, on which the theorem says nothing.
Why depth. There are functions (with many "folds", say) that a network of depth L represents with a number of neurons polynomial in L, while a single hidden layer needs an exponential number. Width is formally sufficient, but depth is radically cheaper. That is why deep learning is "deep" and not "wide".
NumPy Approximating a function with a sum of ReLU bumps
import numpy as np
# one hidden layer: g(x) = Σ αᵢ · ReLU(wᵢ·x + bᵢ)
def g(x, W1, b1, W2):
h = np.maximum(0, np.outer(x, W1) + b1) # N hidden ReLU neurons
return h @ W2 # weighted sum of the bumps
# with large enough N and the right parameters, g(x) ≈ any continuous fWhy it matters
This is the theoretical licence to use neural networks at all: there is no class of functions that is out of reach for them. But it is precisely its limitations (non-constructiveness, the advantage of depth) that explain why in practice what matters is not general existence theorems but concrete architectures, initialization and optimizers.
Connections
Backprop gives you how to train; the theorem says what is achievable in principle. Together they close the question "is this worth doing at all": yes — networks are both expressive and trainable.
There, universality is for Boolean functions (a network of threshold neurons computes any of them). Here it is for continuous ones. Two faces of one fact about the expressive power of neural networks.
"Depth is cheaper than width" is the theoretical argument; ResNet is the engineering answer: how to make very deep networks actually trainable, so that the advantage can be had in practice.
Questions worth asking
If one layer is "enough", why have depth at all?
"Enough" is about existence, not efficiency. For some functions a shallow network needs exponentially more neurons than a deep one. On top of that, depth gives a hierarchy of reusable features (edges → parts → objects) that a wide layer does not build. An existence theorem and practicality are different things.
If a network can approximate anything, doesn't that mean it will always overfit?
Expressive power and overfitting are different axes. Yes, a network is able to memorize noise, but in practice SGD + regularization + architectural biases pull it towards simple solutions (implicit bias). The puzzle of deep learning is exactly that overparameterised networks generalize even though they "could" overfit.
The theorem is about continuous functions — what if the target function is discontinuous?
Strictly speaking the theorem says nothing about it, but in practice this rarely gets in the way: a discontinuity is approximated by a steep (but continuous) transition, arbitrarily closely in the sense of, say, the L² norm. What causes trouble is not discontinuities as such but high frequency and roughness, which demand a great many neurons.
What to read in the original
The originals are measure-theoretic mathematics. For the canon it is enough to understand the statement and two caveats: non-constructiveness, and the advantage of depth over width.