Universal Approximation

The multilayer perceptron solved XOR by inserting one nonlinear hidden layer. The natural next question is how much a single hidden layer can represent. The answer: a net with one hidden layer is already a universal approximator. The limitation is that can represent says nothing about can represent cheaply, and the gap between the two is exponential.

The theorem

Let $f : K \to R$ be continuous on a compact set $K \subset R^{d}$ . A single-hidden-layer network with $N$ units computes

F_{N} (x) = j = 1 \sum N v_{j} g (w_{j}^{⊤} x + b_{j}),

an affine readout of $N$ nonlinear features, each a neuron with weights $w_{j} \in R^{d}$ , bias $b_{j} \in R$ , and output coefficient $v_{j}$ . The classical result (Cybenko 1989 for the sigmoid; Hornik, Stinchcombe & White 1989; Hornik 1991 for the general activation; Leshno et al. 1993 for the sharp condition) says this family is dense in the continuous functions on $K$ .¹

Leshno, Lin, Pinkus & Schocken (1993) sharpened this to an iff: a single-hidden-layer network with a continuous activation $g$ is dense in $C (K)$ if and only if $g$ is non-polynomial, so non-polynomiality is the exact boundary, not merely one sufficient condition.

The theorem has two hypotheses, and dropping either breaks the result.

Hypothesis	Why it is needed	What breaks without it
$g$ non-polynomial	a degree- $k$ polynomial activation keeps $F_{N}$ a degree- $k$ polynomial in $x$ — a finite-dimensional space, never dense	the net can only ever output polynomials
$K$ compact, $f$ continuous	uniform approximation needs $f$ uniformly continuous; on unbounded domains the tails escape	error blows up off the compact set

The non-polynomial hypothesis is quick to see in one line. If $g$ is a polynomial of degree $k$ , then each feature $g (w_{j}^{⊤} x + b_{j})$ is a polynomial of degree $\leq k$ in the coordinates of $x$ , and a finite sum of degree- $\leq k$ polynomials is again a polynomial of degree $\leq k$ . So $F_{N}$ lives in the space of polynomials of degree at most $k$ in $d$ variables, a fixed $(k d + k)$ -dimensional subspace of $C (K)$ , no matter how large $N$ grows. A fixed finite-dimensional subspace cannot be dense in the infinite-dimensional $C (K)$ : pick any $f$ outside its closure (say degree $k + 1$ ) and no width helps. The moment $g$ has a non-vanishing derivative of every order at some point (as $σ$ , $tanh$ , and piecewise $ρ$ effectively do), the features are no longer confined to a finite-dimensional subspace and their span is dense in $C (K)$ .

Note what the theorem does not promise: nothing about how large $N$ must be, nothing about whether gradient descent can find the parameters, and nothing about behavior off $K$ . It is a statement of pure expressivity.²

A constructive proof: bumps from sigmoids

Cybenko's original argument is a functional-analysis duality (a measure that annihilates every $g (w^{⊤} x + b)$ must be zero). But the constructive proof is more instructive and generalizes to ReLU: build a localized bump from two opposed sigmoids, then tile the domain with bumps.

Work in one dimension and write the logistic sigmoid $σ (z) = 1/ (1 + e^{- z})$ . A single steep sigmoid approximates a step: as the gain $s \to \infty$ ,

σ (s (x - a)) ⟶ 1 [x > a],

a unit step rising at $x = a$ . Subtract a second step that rises later, at $x = a + Δ$ , and the difference is a bump, a feature that is on inside $[a, a + Δ]$ and off everywhere else:

ϕ_{a, Δ} (x) = σ (s (x - a)) - σ (s (x - a - Δ)) s \to \infty 1 [a \leq x \leq a + Δ] .

Two opposed sigmoids make a bump. The left step

σ (s (x - a))

(blue) minus the right step

σ (s (x - a - Δ))

(red) leaves a localized bump

ϕ_{a, Δ}

(green), supported on

[a, a + Δ]

Scaling the bump by a height $c$ and placing it over a thin interval gives a single rectangular tile of any height. Now partition $[0, 1]$ into $N$ slabs of width $Δ = 1/ N$ at grid points $x_{k} = k Δ$ , and choose each tile's height to match the target there, $c_{k} = f (x_{k})$ . The sum of tiles is a step function shadowing $f$ :

F_{N} (x) = k = 1 \sum N f (x_{k}) ϕ_{x_{k - 1}, Δ} (x) \approx k = 1 \sum N f (x_{k}) 1 [x_{k - 1} \leq x \leq x_{k}] .

This is precisely a Riemann sum rendered as a network. Each tile uses two hidden units, so $F_{N}$ has $2 N$ units; uniform continuity of $f$ controls the error.³

For example, take a bump centred on $[0.4, 0.6]$ with gain $s = 50$ : the network computes $σ (50 (x - 0.4)) - σ (50 (x - 0.6))$ . At the left edge $x = 0.4$ the first sigmoid sits at $σ (0) = 0.5$ while the second is $σ (- 10) \approx 4.5 \times 1 0^{- 5}$ , so the bump reads $\approx 0.5$ ; at the centre $x = 0.5$ both arguments are $\pm 5$ , giving $σ (5) - σ (- 5) = 0.9933 - 0.0067 = 0.987$ ; outside $[0.35, 0.65]$ both sigmoids are saturated the same way and cancel to under $1 0^{- 3}$ . The transition band where the bump is neither $0$ nor its plateau has width $\approx 4/ s = 0.08$ , and it shrinks as $1/ s$ . That transition band is the only source of the per-bump error, which is why the proof sends $s \to \infty$ after fixing the grid: first choose the grid fine enough for the staircase to track $f$ , then choose $s$ large enough for each bump to track its indicator.

A bump-sum approximation of a smooth target

f

(blue) by scaled bumps

F_{N}

(green); halving the slab width halves the worst-case error.

The ReLU version: ramps, not bumps

The modern activation is the ReLU $ρ (z) = max (0, z)$ , which is piecewise linear, so the natural building block is a ramp rather than a step. A single ReLU is a hinge that turns on at $x = b$ ; differences of shifted ReLUs build a basis of hinges, and any combination of $N$ hinges is a continuous piecewise-linear function with at most $N$ breakpoints:

F_{N} (x) = v_{0} + j = 1 \sum N v_{j} ρ (x - b_{j}), F_{N} is piecewise linear with breakpoints {b_{j}} .

The coefficient $v_{j}$ measures the change in slope at the breakpoint $b_{j}$ . To see this: to the left of $b_{j}$ the term $v_{j} ρ (x - b_{j})$ is flat at $0$ ; to the right it contributes slope $v_{j}$ . So the slope of $F_{N}$ jumps by exactly $v_{j}$ as $x$ crosses $b_{j}$ , and the slope on the piece after the $m$ -th breakpoint is the running sum $\sum_{j \leq m} v_{j}$ . To interpolate a target $f$ sampled on a uniform grid $b_{j} = j h$ , match slopes: the desired slope on piece $m$ is the forward difference $(f (b_{m + 1}) - f (b_{m})) / h$ , so the required jump is the second difference

v_{j} = \frac{f ( b _{j + 1} ) - 2 f ( b _{j} ) + f ( b _{j - 1} )}{h},

a discrete curvature. Where $f$ is convex the jumps are positive, where concave negative, and where $f$ is already linear they vanish: units are needed only where the target bends. The network becomes a linear spline through the sampled points, using one hidden unit per interior grid point.

A ReLU network is a linear spline: shifted ramps (black) sum to a piecewise-linear approximation

F_{N}

(green) of the target

f

(blue), one unit per breakpoint.

The accounting is exact: one hidden unit adds one breakpoint, hence at most one extra linear piece. A shallow ReLU net's expressivity is linear in its width. The depth-separation results below rest on this fact.

Existence is not efficiency

The theorem is an existence statement: some width $N$ works. It is silent on how large $N$ must be, and for many natural functions $N$ is exponentially large unless the network is deep. This is the content of depth-separation theorems.⁴

Recall the shallow bound: a one-layer ReLU net of width $w$ produces at most $w + 1$ linear pieces. Now compose. Let $T : [0, 1] \to [0, 1]$ be the sawtooth / tent map, $T (x) = 1 - ∣ 2 x - 1 ∣$ , a single fold built from two ReLUs. Written out, $T (x) = 2 ρ (x) - 4 ρ (x - \frac{1}{2}) + 2 ρ (x - 1)$ on $[0, 1]$ : two units of positive slope and a middle unit that reverses it, giving the rising-then-falling tent.

The folding mechanism is the point. $T$ maps $[0, 1]$ onto $[0, 1]$ but sends both halves $[0, \frac{1}{2}]$ and $[\frac{1}{2}, 1]$ across the full range $[0, 1]$ , folding the interval in half like paper. So if a function $ψ$ has $p$ linear pieces on $[0, 1]$ , the composition $ψ \circ T$ replays all $p$ pieces on each half, giving $2 p$ pieces. A network that applies $T$ a second time folds the already-folded line, doubling the number of linear segments; $n$ layers of folding produce $2^{n}$ teeth from a linear seed.

T^{(n)} (x) = n T \circ T \circ \dots \circ T (x) has 2^{n} linear pieces, using only 2 n ReLUs.

Folding doubles linear pieces: composing the tent map

n

times yields

2^{n}

teeth from only

2 n

ReLUs, which a shallow net cannot match cheaply.

A depth- $n$ folding net produces $2^{n}$ linear pieces with $2 n$ units; a single-layer net, capped at $w + 1$ pieces, needs width $w \approx 2^{n}$ to match — an exponential separation, and not an isolated example.

The mechanism is region-counting, and the arithmetic is worth stating precisely. In $d$ input dimensions, a single hidden layer of width $w$ places $w$ hyperplanes (one activation boundary per unit); the number of regions $w$ hyperplanes carve $R^{d}$ into is $\sum_{i = 0}^{d} (i w)$ , which for fixed $d$ is polynomial in $w$ (additive-flavoured growth, roughly $w^{d} / d!$ ). Stacking layers composes the partition instead of unioning it: each new layer of width $w$ re-cuts every region the earlier layers produced, so the counts multiply. The sharpest known bound for an $L$ -layer, width- $w$ ReLU net is on the order of

# regions = O ((\frac{w}{d})^{(L - 1) d} w^{d}) = w^{O (L \cdot d)},

exponential in depth $L$ but only polynomial in width $w$ . The asymmetry — depth in the exponent, width in the base — decides the comparison: reaching $2^{n}$ regions costs $L = O (n)$ layers or $w = Ω (2^{n})$ units, and the former is exponentially cheaper.

Region counting in a

d = 2

input. Left: a single hidden layer of width

w = 4

draws

4

activation-boundary lines, partitioning the plane into

11

linear regions (polynomial in

w

). Right: a second layer re-cuts every region, so the partition composes and the count multiplies with depth.

Width explosion. For the depth-

n

sawtooth a shallow net pays

Ω (2^{n})

units (red) while a deep net pays only

O (n)

(green).

Shallow versus deep

The two regimes represent the same function class (both are universal) but at very different cost in units.

Property	Shallow (1 hidden layer)	Deep ( $L$ layers)
Universal approximator	yes (Cybenko/Hornik)	yes
Linear regions (ReLU)	$O (w)$ — additive in width	$O (w^{L})$ — multiplicative in depth
Units for $2^{n}$ -piece sawtooth	$Ω (2^{n})$	$O (n)$
Parameter / sample efficiency	poor — width must explode	strong — reuse of features
Optimization	one convex-ish layer, easy to fit	non-convex, but trains in practice
Inductive bias	none beyond smoothness	compositional structure

The deep column wins on representation and statistics; the shallow column wins on optimization simplicity. Real-world functions are overwhelmingly compositional (an object is parts of edges of pixels), and that compositional structure is what depth encodes cheaply while width can only imitate at exponential cost.⁵

Region count versus depth at fixed width

w

, on a

log_{2}

vertical axis. Adding depth (green) multiplies regions — a straight line in

log

scale, so exponential growth. Spending the same budget on width (blue) only adds regions — a flat, near-constant curve. Depth compounds; width accumulates.

Necessary, but not sufficient

Universal approximation is a statement about the existence of good parameters, and it is silent on the two questions that actually decide whether a network works in practice.

Question	What universality says	Where it is settled
Can the function be represented?	yes — that is the theorem	this lesson
Will gradient descent find the parameters?	nothing	optimization landscape
Will it generalize from finite data?	nothing	generalization theory

The error budget. The target

f

sits outside the network class

F

; universality shrinks

F

up against

f

so the approximation gap (blue) to the best network

F^{⋆}

vanishes. The estimation gap (red) from

F^{⋆}

to the trained

\hat{F}

is what data and optimization must close, and universality is silent on it.

A net that can represent the target may still be impossible to train (the loss surface is non-convex) or may memorize the training set without generalizing (too much capacity, too little data). The expressivity question closed here hands off to the optimization question (can we reach the good parameters?) and the generalization question (do they say anything about unseen data?).

Sharper approximation bounds

Goodfellow states universality and depth separation; the surrounding literature sharpens both the width bound and the rate, and reframes what the theorem does not buy.

How the width scales matters as much as that it is finite. The bare theorem lets $N \to \infty$ as $ε \to 0$ with no rate, but Barron (1993) proved a rate for functions whose Fourier transform has a bounded first moment: a one-hidden-layer sigmoid net achieves $L^{2}$ error $O (1/ N)$ with $N$ units, independent of the input dimension $d$ . This is why neural nets can avoid the curse of dimensionality on structured targets — a grid-based approximator would need $N = Ω (ε^{- d})$ units, exponential in $d$ , while a Barron-class function needs only $O (ε^{- 2})$ . Depth separation (Telgarsky 2016; Eldan & Shamir 2016 exhibited a function deep nets fit with polynomial width that any shallow net needs exponential width to match) is the complementary result: not just how many units, but how the count depends on depth.

Universality also holds with bounded width and unbounded depth. The classical statement fixes depth at one and grows width. Lu et al. (2017) and Hanin & Sellke (2017) proved the dual: a ReLU network of bounded width (roughly $d + 1$ to $d + 4$ for inputs in $R^{d}$ ) is a universal approximator if allowed to grow deep. So both knobs reach every continuous function; the region-counting argument of the last section explains why the deep-narrow route is usually the efficient one.

Existence is not the limiting question in modern practice. The modern view, sharpened by the double-descent and overparameterization literature (Belkin et al., 2019; the neural-tangent-kernel analysis of Jacot et al., 2018), is that real networks operate far past the point where they can fit the data — they can fit random labels outright (Zhang et al., 2017). What decides success is not the approximation floor this lesson establishes but the implicit bias of gradient descent toward particular solutions among the infinitely many that interpolate. Universality tells you the target is reachable; it says nothing about which of the many perfect fits the optimizer will actually land on, which is the subject the generalization lessons take up.⁶

Takeaways

Universal approximation (Cybenko 1989 / Hornik 1991): one hidden layer with any continuous non-polynomial activation approximates any continuous $f$ on a compact set to arbitrary uniform accuracy. Non-polynomial and compact are the two load-bearing hypotheses.
The constructive proof builds a localized bump from two opposed sigmoids, $ϕ_{a, Δ} = σ (s (x - a)) - σ (s (x - a - Δ))$ , then sums scaled bumps into a Riemann-style staircase shadowing $f$ . The ReLU version sums shifted ramps into a linear spline, one unit per breakpoint.
Existence is not efficiency. A shallow ReLU net has $O (w)$ linear regions (additive in width); a deep net has $O (w^{L})$ (multiplicative in depth).
Depth separation (Telgarsky 2016; parity): the sawtooth $T^{(n)}$ needs $O (n)$ units deep but $Ω (2^{n})$ units shallow — an exponential gap.
Universality is necessary but not sufficient: it crushes approximation error to $0$ but says nothing about trainability or generalization.

Goodfellow, Deep Learning, §6.4.1 — Universal Approximation Properties and Depth: a single hidden layer with a non-polynomial activation is dense in $C (K)$ , with no bound on the width required. ↩
Goodfellow, Deep Learning, §6.4 — Architecture Design: the theorem promises only existence — not the width, not that gradient descent finds the weights, not behavior off the compact set. ↩
Chollet, Deep Learning with Python, Ch. 4–5 — model capacity: enough units can represent (and overfit) any target, so capacity must be balanced against data, not maximized. ↩
Goodfellow, Deep Learning, §6.4.1 — depth-separation: functions a deep ReLU net represents with $O (n)$ units force a shallow net to width $exp (n)$ ; depth multiplies linear regions, width only adds them. ↩
Goodfellow, Deep Learning, §6.4.1 / §15.4 — the compositional prior: real-world targets factor as parts-of-parts, the structure depth encodes cheaply and a shallow net must pay exponentially to imitate. ↩
Primary sources: Barron, Universal Approximation Bounds for Superpositions of a Sigmoidal Function (1993) for the dimension-independent $O (1/ N)$ rate; Eldan & Shamir, The Power of Depth for Feedforward Neural Networks (2016) and Telgarsky, Benefits of Depth in Neural Networks (2016) for depth separation; Lu et al., The Expressive Power of Neural Networks: A View from the Width (2017) and Hanin & Sellke (2017) for bounded-width universality; Zhang et al., Understanding Deep Learning Requires Rethinking Generalization (2017), Jacot et al., Neural Tangent Kernel (2018), and Belkin et al., Reconciling Modern Machine Learning and the Bias-Variance Trade-off (2019) for why interpolation, not existence, is the live question. ↩