Universal Approximation Theorem

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Problem Statement
6. Cybenko's Theorem (1989)
7. Constructive Proof Sketch
8. Depth vs. Width
9. Activation Function Requirements
10. Approximation Rates and Limitations
11. From Existence to Learnability
12. Worked Examples
13. Connection to the Broader Curriculum
14. Common Pitfalls and Misconceptions
15. Research Perspective
16. Summary of Takeaways
17. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. State the Universal Approximation Theorem (UAT) for single-hidden-layer feedforward networks.
2. Explain the role of the activation function and why nonlinearity is essential.
3. Distinguish between approximation existence (UAT) and learnability (optimization, generalization).
4. Compare depth vs. width tradeoffs in network expressivity.
5. Describe constructive proof strategies (Ridge functions, Fourier sums).
6. State the limitations of UAT: no bounds on network size, no guarantee of efficient approximation.

Prerequisites

• Backpropagation — feedforward network architecture
• Matrix Operations & Linear Transformations — linear maps, composition

Notation

• $\sigma$ — Nonlinear activation function
• $\mathcal{C}(K)$ — Continuous functions on compact set $K$
• **$\** — \cdot\ — _\infty$ — Supremum (uniform) norm
• $L$ — Number of hidden units
• $\epsilon > 0$ — Approximation tolerance

Core Intuition

Why do neural networks work at all? The Universal Approximation Theorem provides a foundational answer: a feedforward network with a single hidden layer containing sufficiently many neurons can approximate any continuous function on a compact domain to arbitrary accuracy.

This is an existence result — it says the capacity is there. It does not say:

• How many neurons are needed
• How to find the right weights (Backpropagation)
• That the network will generalize to unseen data

Nevertheless, UAT justifies the hypothesis class. Without it, there would be no theoretical guarantee that a neural network could represent the target function, regardless of training.

Series context. Part II of Chapter 6 (Deep Learning Foundations) in Volume II.

Problem Statement

Definition 1 (Feedforward Network). A single-hidden-layer network with activation $\sigma: \mathbb{R} \to \mathbb{R}$ is:

where $\mathbf{w}_j \in \mathbb{R}^d$, $v_j, b_j, c \in \mathbb{R}$, and $N$ is the number of hidden units.

Definition 2 (Uniform Approximation). A sequence of functions $\{f_N\}$ approximates $g$ uniformly on compact $K \subset \mathbb{R}^d$ if:

Definition 3 (Universal Approximation). An activation function $\sigma$ has the universal approximation property if for every continuous $g: K \to \mathbb{R}$ and every $\varepsilon > 0$, there exists $N$ and parameters such that $\sup_{\mathbf{x} \in K} |f_N(\mathbf{x}) - g(\mathbf{x})| < \varepsilon$.

Cybenko's Theorem (1989)

Theorem 1 (Cybenko, 1989). Let $\sigma: \mathbb{R} \to \mathbb{R}$ be a continuous, bounded, non-constant function. Let $K \subset \mathbb{R}^d$ be compact. Then for every continuous $g: K \to \mathbb{R}$ and every $\varepsilon > 0$, there exist $N \in \mathbb{N}$, weights $\{v_j, \mathbf{w}_j, b_j\}_{j=1}^N$, and bias $c$ such that

Theorem 2 (Hornik, Stinchcombe, White, 1989). The same conclusion holds if $\sigma$ is merely nonpolynomial (not a polynomial on any interval), without requiring boundedness. This covers ReLU: $\sigma(z) = \max(0, z)$.

Corollary 1. ReLU networks with one hidden layer are universal approximators on compact domains.

Key observation. Only one hidden layer is needed for universality — but the number of hidden units $N$ may need to be very large. Depth provides efficiency, not capability (in the limit).

Constructive Proof Sketch

We outline the proof strategy for Theorem 1; full details appear in Cybenko (1989) and Hornik et al. (1989).

Step 1: Ridge Functions. Each hidden unit computes a ridge function $\sigma(\mathbf{w}^T \mathbf{x} + b)$ — a function constant along directions orthogonal to $\mathbf{w}$. The network sums ridge functions with different directions and biases.

Step 2: Density of Ridge Function Sums. The set $\mathcal{M} = \left\{\sum_{j=1}^N v_j \sigma(\mathbf{w}_j^T \mathbf{x} + b_j)\right\}$ forms a linear subspace of $C(K)$ (continuous functions on $K$).

Step 3: Hahn-Banach / Riesz Representation. Suppose $\mathcal{M}$ is not dense. By the Hahn-Banach theorem, there exists a nonzero continuous linear functional $L$ on $C(K)$ that vanishes on $\mathcal{M}$.

Step 4: Fourier Transform Argument. The Riesz representation gives $L(g) = \int_K g(\mathbf{x})\, d\mu(\mathbf{x})$ for a signed measure $\mu$. Setting $g(\mathbf{x}) = \sigma(\mathbf{w}^T \mathbf{x} + b)$ and using the fact that $L$ vanishes on all ridge functions leads to a contradiction unless $\mu = 0$, via properties of the Fourier transform of $\sigma$.

Step 5: Conclusion. $\mathcal{M}$ is dense in $C(K)$, so any continuous function can be approximated arbitrarily well. $\blacksquare$

Alternative Constructive Approach (Siggelkow, 2002). Approximate $g$ by a sum of step functions; approximate each step function by a difference of two sigmoids. This gives explicit (though inefficient) constructions.

Depth vs. Width

Theorem 3 (Depth Efficiency, informal). There exist functions that can be represented by a deep network of polynomial size but require an exponential number of neurons in a shallow network.

Example 1 (Parity Function). The parity function on $d$ bits requires a single hidden layer of size $2^d$ but can be computed by a network of depth $O(\log d)$ with $O(d)$ total neurons.

Proposition 1 (Depth Hierarchy). For ReLU networks, there exist depth-$L$ networks that cannot be represented by any depth-$(L-1)$ network without exponential width increase (Telgarsky, 2016; Eldan & Shamir, 2016).

Interpretation. UAT guarantees that some shallow network suffices, but it may require exponentially many neurons. Deep networks can represent certain functions much more efficiently. This is the primary theoretical motivation for depth.

Activation Function Requirements

Proposition 2 (Linear Activation Fails). If $\sigma(z) = z$ (identity), then $f_N(\mathbf{x})$ is a linear function of $\mathbf{x}$ regardless of $N$. Non-constant linear functions cannot approximate nonlinear $g$.

Proposition 3 (Polynomial Activation Fails). If $\sigma$ is a polynomial of degree $p$, then $f_N$ is a polynomial of bounded degree (independent of $N$ on each coordinate). Cannot approximate non-polynomial functions.

Proposition 4 (ReLU Suffices). $\sigma(z) = \max(0, z)$ is nonpolynomial and satisfies Theorem 2. ReLU networks are universal approximators.

Proposition 5 (Sigmoid Suffices). $\sigma(z) = 1/(1+e^{-z})$ is bounded, continuous, non-constant — satisfies Theorem 1.

The activation must introduce nonlinearity that cannot be reduced to a fixed-degree polynomial.

Approximation Rates and Limitations

Definition 4 (Approximation Rate). The approximation rate asks: how many neurons $N(\varepsilon)$ are needed to achieve error $\varepsilon$?

Theorem 4 (Barron, 1993). If $g$ has bounded Barron norm (integrability condition on its Fourier transform), then $N = O(1/\varepsilon^2)$ neurons suffice.

Theorem 5 (Curse of Dimensionality). For general continuous functions on $[0,1]^d$, the worst-case approximation rate with smooth activations is $N = O(\varepsilon^{-d})$. The number of neurons grows exponentially in dimension.

Limitations of UAT:

1. No size bounds. UAT says approximation exists but not how large $N$ must be.
2. No optimization guarantee. Finding the right weights is a separate (hard) problem.
3. No generalization guarantee. Approximating training data does not imply test performance.
4. Compact domain only. Approximation on all of $\mathbb{R}^d$ requires additional growth conditions.

From Existence to Learnability

Definition 5 (Three Levels of Theory).

• Approximation — Can the network represent $g$? — UAT: yes
• Optimization — Can we find the weights? — Non-convex; no global guarantee (but works in practice)
• Generalization — Does it work on new data? — Requires capacity control, more data

Proposition 6 (NTK Regime). In the infinite-width limit, gradient descent on a neural network is equivalent to kernel regression with the Neural Tangent Kernel (Jacot et al., 2018). This connects approximation, optimization, and generalization in a specific regime.

UAT addresses only the first row. Modern deep learning theory aims to close the gap.

Worked Examples

Example 2: Approximating $g(x) = x^2$ on $[0, 1]$

Using ReLU: $x^2 = 2\sum_{i=0}^{n} \text{ReLU}(x - i/n) \cdot (1/n) - \text{ReLU}(2x - 1) + \text{const}$ (approximate integral representation). As $n \to \infty$, error $\to 0$.

Example 3: Step Function via Sigmoid

$\mathbb{1}[x > 0] \approx \sigma(\alpha x)$ as $\alpha \to \infty$. A sum of shifted sigmoids approximates piecewise constant functions, which approximate continuous functions (Weierstrass approximation).

Example 4: XOR Requires Hidden Layer

XOR is not linearly separable — a linear model (no hidden layer) cannot represent it. A network with one hidden unit of two ReLUs suffices: $f(x_1, x_2) = \text{ReLU}(x_1 + x_2 - 1) - \text{ReLU}(x_1) - \text{ReLU}(x_2) + 1$.

Connection to the Broader Curriculum

• Backpropagation — how we find the approximating weights
• Self-Attention — Transformers also satisfy universal approximation (Yun et al., 2020)
• Universal Approximation for Transformers — depth-$N$ Transformer can approximate sequence-to-sequence maps
• Bias–Variance Tradeoff — generalization beyond approximation

Common Pitfalls and Misconceptions

Pitfall 1: "UAT proves deep learning works." UAT proves representational capacity, not that gradient descent finds good weights or that the network generalizes.

Pitfall 2: "One hidden layer is enough, so depth is unnecessary." UAT allows exponentially many neurons in one layer. Depth provides efficiency.

Pitfall 3: "Any activation works." Polynomial activations fail. The activation must be nonpolynomial.

Pitfall 4: "UAT applies to all network architectures." UAT is proven for feedforward networks. CNNs, RNNs, and Transformers have separate (but analogous) results.

Pitfall 5: Confusing approximation on compact sets with global approximation. Functions on all of $\mathbb{R}^d$ may require networks that grow with the domain.

Research Perspective

Cybenko (1989) and Hornik, Stinchcombe, and White (1989) established UAT independently, building on earlier work by Kolmogorov (1957) and Arnold (1957) on superposition theorems.

Modern directions:

• Depth separation (Telgarsky, 2016): formal exponential gaps between deep and shallow networks
• Transformer universality (Yun et al., 2020): Transformers are universal approximators for sequence functions
• Neural Tangent Kernel (Jacot et al., 2018): infinite-width limit connects to kernel methods
• Approximation with constraints (sparsity, quantization): how Quantization affects expressivity

UAT remains the starting point for any theoretical discussion of neural network expressivity.

Summary of Takeaways

• UAT — One hidden layer + nonpolynomial $\sigma$ suffices for uniform approximation on compact sets
• ReLU — Nonpolynomial → universal
• Depth — Exponential efficiency gains over width for some functions
• Limitations — No size bounds, no optimization/generalization guarantees
• Three levels — Approximation ≠ optimization ≠ generalization

Next article: Batch Normalization →

Exercises

Exercise 1. Prove that a network with linear activation can only represent linear functions, regardless of depth or width.

Exercise 2. Show that XOR requires at least one hidden unit (not linearly separable in input space).

Exercise 3. Construct a ReLU network with 3 hidden units that exactly represents $\max(0, x_1, x_2)$ on $[0,1]^2$.

Exercise 4. Explain why the parity function on $d$ bits requires $2^d$ hidden units in one layer but $O(d)$ neurons with $O(\log d)$ depth.

Exercise 5 (Conceptual). UAT guarantees approximation exists. Why does this not imply that gradient descent will find it?

Exercise 6. State the difference between Cybenko's theorem (bounded $\sigma$) and Hornik's extension (nonpolynomial $\sigma$). Which covers ReLU?

Exercise 7. Research question: formulate what a "Universal Approximation Theorem for Transformers" would state.

Exercise 8. Give an example of a continuous function on $[0,1]$ where a 2-neuron sigmoid network provides a good approximation, and explain the construction.