Universal Approximation Theorems
What one hidden layer can and cannot do efficiently.
One hidden layer is enough: sums approximate any continuous function on a compact set, for almost any activation . That is the universal approximation theorem, true and often over-read. This lesson proves it three ways (a construction for ReLUs, Cybenko's duality argument, and the derivative trick behind "any non-polynomial activation"), derives Barron's dimension-free rate with Maurey's sampling argument, and marks what the theorems leave out: how many units, and whether training finds them.
What you’ll learn
- State the theorems of Cybenko, Hornik and Leshno–Lin–Pinkus–Schocken, and prove that polynomial activations are not universal.
- Give the constructive one-dimensional ReLU proof with its error bounds, and sketch Cybenko's proof via Hahn–Banach and the Riesz representation theorem.
- Prove Maurey's lemma, use it to explain Barron's rate, and contrast it with the barrier for fixed bases.
- Distinguish expressivity from trainability, and state minimal-width results for deep narrow networks.
What “universal” means
| Theorem | Activation | Conclusion |
|---|---|---|
| Cybenko (1989) | continuous sigmoidal: at , at | dense in |
| Hornik, Stinchcombe & White (1989) | any squashing function (nondecreasing, limits 0 and 1) | uniform approximation on compacta; Borel functions in measure |
| Hornik (1991) | bounded and nonconstant | dense in for finite ; in if also continuous |
| Leshno, Lin, Pinkus & Schocken (1993) | locally bounded, piecewise continuous | universal if and only if is not a polynomial; covers ReLU |
Let be continuous on , take knots , and let be the slope of the chord of on . Define
Each unit switches on at its knot and changes the slope by , so is the piecewise-linear interpolant of , built from hidden units:
On an interval of length , the chord stays within of an -Lipschitz , and the classical interpolation bound handles smooth :
Uniform continuity makes the error go to 0 for every continuous . In dimensions, piecewise-linear interpolation at spacing needs on the order of pieces: the curse of dimensionality appears as soon as accuracy has a price.
Two proofs of density
Suppose the closure of in is a proper subspace. Hahn–Banach gives a nonzero bounded linear functional vanishing on it, and the Riesz representation theorem writes it as integration against a nonzero finite signed regular Borel measure :
Scale: as , tends to 1 on the open half-space , to 0 on the opposite one and to on the hyperplane. Bounded convergence, then , shows that gives zero mass to every half-space and hyperplane:
Fix . The functional vanishes on indicators of intervals, hence on simple functions and, by bounded convergence, on all bounded measurable , including and . So the Fourier transform of vanishes everywhere, forcing : a contradiction.
The proof is non-constructive: it shows that no measure can be orthogonal to all sigmoidal ridges, without exhibiting an approximant. Leshno et al.'s "any non-polynomial activation" rests on a different, almost algebraic idea. For smooth , a divided difference in the weight, , is itself a network, and its limit lies in the closure:
With one hidden layer of unlimited width, which activation is not universal?
Show the answer
C.
Every network with a cubic activation is a polynomial of degree at most 3, a closed finite-dimensional space. ReLU, tanh and sine are not polynomials, so Leshno et al.'s theorem applies to all three.
Rates: Barron’s theorem
It suffices to treat a finite convex combination close to . Draw i.i.d. with , so ; the cross terms of independent mean-zero vectors vanish:
Some outcome is at least as good as the average: the probabilistic method. Nothing in the argument depends on the dimension of the underlying space.
Barron writes : an average, under the density , of ridge functions bounded by on . Each ridge is a limit of convex combinations of sigmoid steps of norm at most in , and Maurey gives
Suppose . How many sigmoid units does Barron's theorem guarantee are enough for an error of ?
Show the answer
10000
, in any dimension. The catch is hidden in : the class of functions with small becomes more restrictive as grows (functions with about square-integrable derivatives qualify).
The rate is dimension-free because the network chooses its own basis functions, the directions , to suit . Barron also proved that for any fixed basis functions, the worst-case squared error over the same class is at least of order : no linear method escapes the curse. For generic smooth classes the curse returns even for networks: on the unit ball of a Sobolev space with derivatives on , any method whose parameters depend continuously on has worst-case error of order at least (DeVore, Howard & Micchelli, 1989), so accuracy costs about parameters, a rate shallow networks attain (Mhaskar, 1996) but cannot beat on the whole class.
Width, existence and trainability
Universality with bounded width needs depth instead. ReLU networks of width are universal in (Lu et al., 2017). For continuous functions on with scalar output the minimal width is (Hanin & Sellke, 2017), and in the minimal width of ReLU networks is exactly for inputs and outputs (Park, Yun, Lee & Shin, 2021). Below these widths approximation fails in general; the one-hidden-layer cousin of the obstruction, that a bounded decision region in needs at least monotone units, is proved in From Neurons to Networks.
Key takeaways
- One hidden layer is universal for every locally bounded, piecewise continuous non-polynomial activation (Leshno et al.), including ReLU; polynomial activations fail because they span a closed finite-dimensional space.
- In one dimension, ReLUs interpolate any with error for -Lipschitz ; Cybenko's proof is non-constructive (Hahn–Banach, Riesz, Fourier uniqueness).
- Barron: functions with finite are approximated with squared error in any dimension, by Maurey's probabilistic lemma.
- Fixed bases cannot beat squared error of order on Barron's class, and generic Sobolev classes cost about parameters: universality is not efficiency.
- Width suffices with enough depth; approximation theorems are existence results, and training may not find the weights they promise.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
What does the universal approximation theorem guarantee for a one-hidden-layer network with a sigmoidal activation?
- Gradient descent finds weights within of any continuous target
- For any continuous on a compact set and any , some finite network is uniformly within of
- The number of hidden units needed grows only polynomially with the input dimension
- A network fitted to finitely many samples of generalizes to all of the compact set
Show the answer
B. For any continuous on a compact set and any , some finite network is uniformly within of
It is a density statement about the set of functions networks can represent. It says nothing about how many units are needed, how to find the weights, or how well a fit to data generalizes.
Why can no one-hidden-layer network with the activation approximate uniformly on , however wide it is?
- is unbounded
- is not monotone
- Every such network is a polynomial of degree at most 2, and that space is closed and does not contain
- It can, given enough units
Show the answer
C. Every such network is a polynomial of degree at most 2, and that space is closed and does not contain
is a quadratic. Quadratics form a three-dimensional, hence closed, subspace of , and has positive distance from it.
Under Barron's bound , how many more hidden units guarantee half the error?
- Twice as many
- times as many
- times as many
- Four times as many
Show the answer
D. Four times as many
The error itself scales like , so halving it needs units, independently of .
Barron's theorem gives error in any dimension, yet he also proved that basis functions cannot beat error of order on the same class. Why is there no contradiction?
- The lower bound is for fixed basis functions chosen before seeing ; a network adapts its directions to
- The two results use different norms
- The lower bound only applies in one dimension
- Barron's theorem only holds for
Show the answer
A. The lower bound is for fixed basis functions chosen before seeing ; a network adapts its directions to
Linear methods fix the basis and fit only the coefficients. Networks choose their ridge directions per target, a nonlinear approximation, which is exactly what Maurey's sampling argument exploits.
Further reading
- G. Cybenko, "Approximation by superpositions of a sigmoidal function," Mathematics of Control, Signals and Systems 2, 303–314 (1989).
- K. Hornik, "Approximation capabilities of multilayer feedforward networks," Neural Networks 4, 251–257 (1991).
- M. Leshno, V. Ya. Lin, A. Pinkus & S. Schocken, "Multilayer feedforward networks with a nonpolynomial activation function can approximate any function," Neural Networks 6, 861–867 (1993).
- A. R. Barron, "Universal approximation bounds for superpositions of a sigmoidal function," IEEE Transactions on Information Theory 39, 930–945 (1993).
- A. Pinkus, "Approximation theory of the MLP model in neural networks," Acta Numerica 8, 143–195 (1999).