Universal Approximation Theorem

Learning Objectives

By the end of this section, you will:

1. Understand why a single hidden layer with enough neurons can approximate any continuous function
2. See the constructive proof: how sigmoid neurons create step functions, how pairs of steps form bumps, and how scaled bumps sum to approximate any target
3. Build a function approximator from scratch in NumPy using the bump construction
4. Train a universal approximator in PyTorch and verify that gradient descent discovers the right weights
5. Know the limitations of the theorem: what it guarantees and what it does not

The Big Question

In the previous two sections we designed MLP architectures and trained them to classify two-moons data. But a deeper question remains: why can neural networks learn anything at all? What is it about a stack of linear transformations and nonlinear activations that gives them such extraordinary representational power?

Consider this: a network with one hidden layer of $N$ sigmoid neurons computes a function of the form $G(x) = \sum_{i=1}^{N} \alpha_i \, \sigma(w_i^T x + b_i)$. Each term is just a weighted, shifted sigmoid. There is nothing inherently complex about any single term. Yet when you add enough of them together, the sum can approximate any continuous function to any desired precision.

This is not magic — it is mathematics. And the proof is surprisingly intuitive once you see the right picture. Let us build it from the ground up.

From Neurons to Step Functions

A single sigmoid neuron computes $\sigma(wx + b) = \frac{1}{1 + e^{-(wx+b)}}$. This S-shaped curve maps any real number to the interval $(0, 1)$. The key observation is what happens when the weight $w$ becomes very large.

When $w$ is large and positive, the sigmoid becomes almost a step function: it is near 0 for $x < -b/w$ and near 1 for $x > -b/w$. The transition happens at the point $x = -b/w$, and the width of the transition region is approximately $4/w$. As $w \to \infty$, the transition becomes infinitely sharp — a perfect step.

Think of it this way: a neuron with a very large weight acts like a binary switch. It is “off” on one side of a threshold and “on” on the other. The bias $b$ controls where the switch flips, and the weight $w$ controls how sharply it flips.

From Steps to Bumps

If one neuron creates a step up at position $a$, and another creates a step up at position $b$, then their difference creates a bump:

$\text{bump}(x) = \sigma(w(x - a)) - \sigma(w(x - b))$ where $a < b$

This bump is approximately 1 between $a$ and $b$, and approximately 0 outside. It is created by exactly two neurons in the hidden layer. The network has learned a localized feature: “activate when $x$ is between $a$ and $b$.”

The subtraction logic is elegant:

• $x < a$: both sigmoids are near 0, so the bump is $0 - 0 = 0$
• $a < x < b$: the first sigmoid is near 1 but the second is still near 0, so the bump is $1 - 0 = 1$
• $x > b$: both sigmoids are near 1, so the bump is $1 - 1 = 0$

From Bumps to Any Function

Here is the key insight that makes neural networks universally powerful. Suppose we want to approximate a continuous function $f(x)$ on the interval $[0, 1]$:

1. Divide the domain $[0, 1]$ into $N$ equal intervals, each of width $1/N$
2. Place a bump at each interval using 2 sigmoid neurons
3. Scale each bump by the function value at the interval center: $h_i = f(\text{center}_i)$
4. Sum all scaled bumps: $G(x) = \sum_{i=1}^{N} f(c_i) \cdot \text{bump}_i(x)$

As $N \to \infty$, the bumps become narrower and more numerous. The approximation $G(x)$ converges to $f(x)$ at every point. This is a neural network version of Riemann integration — the same idea behind numerical calculus, implemented by neurons instead of rectangles.

The Construction in Plain English: Take any curve. Chop it into narrow slices. For each slice, build a bump function (2 neurons) at the right height. Stack them up. As the slices get thinner, the stack of bumps converges to the original curve. That is the universal approximation theorem.

This construction requires $2N$ hidden neurons for $N$ bumps. The approximation error decreases as $O(1/N^2)$ for smooth functions — doubling the neurons reduces the error by roughly 4×.

Interactive: Approximation Explorer

Use the explorer below to see the bump construction in action. Select a target function, then drag the Bumps slider to watch the approximation improve as you add more bump functions. Toggle Show bumps to see each individual bump's contribution. Try the Animate button to watch the convergence unfold automatically.

The Formal Theorem

The intuition above is not just a hand-wavy argument — it is the core of a rigorous mathematical theorem. Here is the precise statement:

Universal Approximation Theorem (Cybenko, 1989): Let $\sigma$ be any continuous sigmoidal function. For any continuous function $f$ on the unit hypercube $[0,1]^d$ and any $\varepsilon > 0$, there exist an integer $N$, real constants $\alpha_i, b_i$, and vectors $w_i \in \mathbb{R}^d$ such that the function $G(x) = \sum_{i=1}^{N} \alpha_i \, \sigma(w_i^T x + b_i)$ satisfies $|G(x) - f(x)| < \varepsilon$ for all $x \in [0,1]^d$.

Hornik, Stinchcombe, and White (1989) independently proved a stronger result: the theorem holds for any non-constant, bounded, monotonically increasing continuous activation function — not just sigmoids. Later results extended it even further:

The requirements are minimal:

1. The activation must be non-polynomial (sigmoid, ReLU, tanh, GELU all qualify; a purely linear activation does not)
2. The target function must be continuous on a compact (closed and bounded) domain
3. The hidden layer must be wide enough — but the theorem does not specify how wide

NumPy: Constructive Approximation

Let us implement the constructive proof from scratch. We will build sigmoid bump functions, position them across $[0, 1]$, scale each one to match $\sin(2\pi x)$ at its center, and measure how the approximation improves as we increase $N$.

  Bump 0: [0.00, 0.25], h=+0.7071
  Bump 1: [0.25, 0.50], h=+0.7071
  Bump 2: [0.50, 0.75], h=-0.7071
  Bump 3: [0.75, 1.00], h=-0.7071

  N= 1 bumps ( 2 neurons): MSE = 0.500000
  N= 2 bumps ( 4 neurons): MSE = 0.232133
  N= 4 bumps ( 8 neurons): MSE = 0.050217
  N= 8 bumps (16 neurons): MSE = 0.011809
  N=16 bumps (32 neurons): MSE = 0.002871
  N=32 bumps (64 neurons): MSE = 0.000709

1import numpy as np
2
3def sigmoid(x):
4    return 1 / (1 + np.exp(-np.clip(x, -500, 500)))
5
6def bump(x, left, right, steepness=50):
7    """Two sigmoid neurons create one bump function."""
8    return sigmoid(steepness * (x - left)) - sigmoid(steepness * (x - right))
9
10# Target function: sin(2*pi*x) on [0, 1]
11x = np.linspace(0, 1, 200)
12target = np.sin(2 * np.pi * x)
13
14# ── Approximate with N=4 bumps ──
15N = 4
16width = 1.0 / N
17approx = np.zeros(200)
18
19for i in range(N):
20    left_i = i * width
21    right_i = (i + 1) * width
22    center_i = (left_i + right_i) / 2
23    height_i = np.sin(2 * np.pi * center_i)
24    approx += height_i * bump(x, left_i, right_i)
25    print(f"  Bump {i}: [{left_i:.2f}, {right_i:.2f}], h={height_i:+.4f}")
26
27mse = np.mean((target - approx) ** 2)
28print(f"\n4 bumps (8 neurons): MSE = {mse:.6f}")
29
30# ── Scale up: more bumps = better approximation ──
31print("\n── Convergence ──")
32for N in [1, 2, 4, 8, 16, 32]:
33    w = 1.0 / N
34    a = sum(
35        np.sin(2 * np.pi * (i * w + w / 2)) * bump(x, i * w, (i+1) * w)
36        for i in range(N)
37    )
38    print(f"  N={N:2d} bumps ({2*N:2d} neurons): MSE = {np.mean((target - a)**2):.6f}")

The convergence table tells the story of the theorem: as $N$ increases, the MSE drops toward zero at a rate of $O(1/N^2)$. With 32 bumps (64 neurons), the error is less than 0.001. With enough bumps, we can make it arbitrarily small.

PyTorch: Learning Any Function

The constructive proof shows that a good approximation exists. But can gradient descent actually find it? Let us train a standard MLP to approximate $\sin(2\pi x)$ from data, with no knowledge of the target function's formula. The network must discover the right internal features entirely through optimization.

Approximator(
  (net): Sequential(
    (0): Linear(in=1, out=32)
    (1): ReLU()
    (2): Linear(in=32, out=1)
  )
)

  Step    0: loss = 0.481233
  Step  500: loss = 0.008214
  Step 1000: loss = 0.000813
  Step 1500: loss = 0.000198
  Step 2000: loss = 0.000072

1import torch
2import torch.nn as nn
3
4# ── Simple MLP: 1 input → hidden layer → 1 output ──
5class Approximator(nn.Module):
6    def __init__(self, width=32):
7        super().__init__()
8        self.net = nn.Sequential(
9            nn.Linear(1, width),
10            nn.ReLU(),
11            nn.Linear(width, 1),
12        )
13
14    def forward(self, x):
15        return self.net(x)
16
17# ── Training data: 200 samples of sin(2*pi*x) ──
18x_train = torch.linspace(0, 1, 200).unsqueeze(1)
19y_train = torch.sin(2 * torch.pi * x_train)
20
21model = Approximator(width=32)
22optimizer = torch.optim.Adam(model.parameters(), lr=0.01)
23loss_fn = nn.MSELoss()
24
25print(f"Parameters: {sum(p.numel() for p in model.parameters())}")
26
27# ── Train for 2000 steps ──
28for step in range(2001):
29    pred = model(x_train)
30    loss = loss_fn(pred, y_train)
31    optimizer.zero_grad()
32    loss.backward()
33    optimizer.step()
34    if step % 500 == 0:
35        print(f"  Step {step:4d}: loss = {loss.item():.6f}")
36
37# ── Evaluate on unseen points ──
38x_test = torch.linspace(0, 1, 500).unsqueeze(1)
39y_test = torch.sin(2 * torch.pi * x_test)
40with torch.no_grad():
41    pred_test = model(x_test)
42    test_mse = loss_fn(pred_test, y_test).item()
43print(f"\nTest MSE (500 points): {test_mse:.6f}")

The network converges from MSE $\approx 0.48$ (random) to $\approx 0.00007$ in 2000 steps. With just 97 parameters, it achieves an approximation quality that our constructive proof needed 64 neurons (193 parameters) to match. This is because gradient descent is free to place its internal features wherever they are most useful — it does not need the rigid uniform grid of our constructive proof.

Key Insight: The constructive proof (NumPy) shows the approximation exists. The trained network (PyTorch) shows that gradient descent can find it — and often finds a more efficient one than the constructive proof provides.

Width, Depth, and the Modern View

The classical UAT is a width theorem: it says one hidden layer is enough, provided it is wide enough. But “wide enough” can mean exponentially many neurons. Modern results reveal a richer picture.

Depth Separation Results

Telgarsky (2016) proved a landmark depth separation result: there exist functions that a deep network of $O(k^3)$ neurons and $O(k)$ layers can represent, but any network with $O(k)$ layers or fewer needs $\Omega(2^k)$ neurons. In other words: depth can be exponentially more efficient than width.

Why Modern Networks are Deep

Transformers, ResNets, and other modern architectures are deep for a reason. Consider the function $f(x) = \sin(2^k \pi x)$: it oscillates $2^k$ times over $[0, 1]$. A shallow network needs $\Omega(2^k)$ neurons to capture all oscillations. A deep ReLU network can represent it with $O(k)$ layers of constant width, because each layer “doubles the frequency” of the previous layer's output.

The practical lesson: width guarantees existence, but depth provides efficiency. This is why we stack 96 layers in GPT-3 rather than using one hidden layer with billions of neurons.

What the Theorem Does NOT Tell You

The UAT is an existence theorem, not a recipe. Understanding its limitations is as important as understanding the result itself.

The gap between “a solution exists” and “gradient descent finds it” is where all the hard problems in deep learning live. The theory of optimization (will SGD converge?), generalization (will it work on unseen data?), and scaling (how much compute do we need?) are all separate from the approximation question that the UAT answers.

Connection to Modern Systems

The Universal Approximation Theorem is not just a historical curiosity — it directly explains why key architectural choices in modern systems work.

Feed-Forward Networks in Transformers

Every transformer block contains a feed-forward network (FFN): $\text{FFN}(x) = W_2 \cdot \text{ReLU}(W_1 x + b_1) + b_2$. This is a 2-layer MLP with one hidden layer — exactly the architecture the UAT covers. By the theorem, each FFN layer can approximate any function of its input.

Research by Geva et al. (2021) and Dai et al. (2022) shows that FFN layers store factual knowledge as key-value pairs in their weight matrices. Each hidden neuron acts like one of our “bumps” — it activates for a specific pattern in the input and contributes a specific value to the output. This is the constructive proof playing out at scale inside every transformer.

Scaling Laws and the Approximation Connection

Kaplan et al. (2020) discovered that language model loss decreases as a power law with model size: $L \propto N^{-\alpha}$ where $N$ is the parameter count. The UAT predicts exactly this behavior: more neurons means finer bumps, which means better approximation. The specific exponent $\alpha$ reflects how efficiently the network allocates its parameters — learned representations are more efficient than the uniform grid of the constructive proof.

Multi-Head Attention and Width

Multi-head attention splits the $d_{\text{model}}$ dimensional space into $h$ heads, each operating on $d_k = d_{\text{model}}/h$ dimensions. From the UAT perspective, each head is a separate approximator that can capture different aspects of the input relationships. More heads means more independent “bump sets” that collectively provide a richer approximation of the attention function.

Flash Attention and KV-Cache: Making Approximation Practical

The UAT tells us that a network can represent any function given enough parameters. But representing a function in billions of parameters means nothing if inference is too slow or uses too much memory. This is where efficiency innovations become critical:

• Flash Attention (Dao et al., 2022) does not change what the attention mechanism computes — it changes how. By tiling the computation to fit in GPU SRAM, it reduces memory from $O(n^2)$ to $O(n)$ while producing identical results. The UAT guarantees representational power; Flash Attention makes that power computationally tractable.
• KV-Cache stores previously computed key and value vectors during autoregressive generation, avoiding redundant recomputation. A transformer FFN with 100 billion parameters can approximate extremely complex functions (by UAT), but serving this at interactive speed requires caching to avoid recomputing the same internal “bumps” for every token.

The pattern is consistent: the UAT provides the theoretical foundation (“it can represent the function”), while engineering innovations (Flash Attention, KV-cache, model parallelism) make the theoretical capacity usable in practice.

Summary

The Universal Approximation Theorem is the theoretical bedrock of neural networks. Here are the essential takeaways:

1. Neurons create building blocks: A single sigmoid neuron produces a step function. Two neurons produce a localized bump. These are the atomic units of approximation.
2. Bumps approximate anything: By placing bumps at regular intervals and scaling them to match the target function, we construct an approximation that converges as $O(1/N^2)$. This is a neural network version of Riemann integration.
3. The formal theorem: Any continuous function on a compact domain can be approximated to arbitrary precision by a single hidden layer with a non-polynomial activation (Cybenko 1989, Hornik et al. 1989, Leshno et al. 1993).
4. Gradient descent finds efficient solutions: Our PyTorch experiment showed that trained networks often find more parameter-efficient approximations than the constructive proof provides.
5. Depth is more efficient than width: While one wide layer suffices in theory, deep networks can represent the same functions with exponentially fewer parameters (Telgarsky, 2016).
6. The theorem has limits: It does not guarantee that training will converge, that the network will generalize, or how many neurons are needed. These are separate, harder problems.

With the UAT as our foundation, we now know that the MLP architecture from Sections 1 and 2 is not just a convenient tool — it is a provably powerful function approximator. The challenge in practice is never “can the network represent this function?” but rather “can we find the right weights efficiently?”