MLPs and universal approximation

Before this lesson: matrices as maps (linear algebra, lesson 01) and rank (linear algebra, lesson 02); logistic and softmax regression (ml-fundamentals track); functions, sets and the notation $f: \mathbb{R}^n \to \mathbb{R}^m$ (foundations track). This is the first lesson of the track. Time: about 65 minutes, plus the notebook.

Why this matters #

Every architecture in this track is built from multilayer perceptrons (MLPs). The feed-forward block of a transformer is a two-layer MLP and holds about 2/3 of the weights of a standard block. Physics-informed neural networks (PINNs) and neural fields are MLPs that take coordinates as input, and the branch and trunk networks of DeepONet are usually MLPs. When someone asks "why can a network fit this?", the usual answer is the universal approximation theorem. You should know exactly how weak this answer is: it promises existence, nothing more. Depth separation is the first precise reason to prefer deep networks over wide ones.

1. Predict first #

2. The picture #

One unit is a hinge #

The rectified linear unit is $\operatorname{relu}(u) = \max(0, u)$. One unit with one input $x$ computes $\operatorname{relu}(wx + b)$. The inside, $wx + b$, is zero at $x = -b/w$. On one side of this point the unit outputs 0; on the other side it outputs the straight line $wx + b$. We call this graph a hinge and the point $-b/w$ its joint.

Example: $\operatorname{relu}(2x - 1)$ has its joint at $x = 1/2$. For $x < 1/2$ it is 0; for $x > 1/2$ it is $2x - 1$, a line with slope 2. If $w < 0$, the sides swap: $\operatorname{relu}(-2x + 4)$ is $0$ for $x > 2$ and $-2x + 4$ for $x < 2$.

A hidden layer adds hinges #

A network with one hidden layer of $H$ units and one output computes

Each term is a hinge scaled by its output weight $c_i$. A sum of hinges is continuous and piecewise linear. Each unit adds at most one joint, so $N$ has at most $H$ joints and at most $H + 1$ linear pieces. Between two joints nothing bends, so $N$ is a straight line there.

How to "connect the dots". Take four points: $(0, 0)$, $(1, 2)$, $(2, 1)$, $(3, 1)$. The straight lines between them have slopes $s_1 = 2$, $s_2 = -1$, $s_3 = 0$. Build $N$ from left to right:

1. Start at $x = 0$ with a unit $\operatorname{relu}(x - 0)$ and output weight $c_0 = 2$. Now the slope is $2$, which is right on $[0, 1]$.
2. At $x = 1$ the slope must change from $2$ to $-1$. Add $\operatorname{relu}(x - 1)$ with output weight $c_1 = -1 - 2 = -3$.
3. At $x = 2$ the slope must change from $-1$ to $0$. Add $\operatorname{relu}(x - 2)$ with output weight $c_2 = 0 - (-1) = 1$.

So $N(x) = 2\operatorname{relu}(x) - 3\operatorname{relu}(x - 1) + \operatorname{relu}(x - 2)$. Check: $N(1) = 2$, $N(2) = 4 - 3 = 1$, $N(3) = 6 - 6 + 1 = 1$. Each output weight is a change of slope. That is the whole idea of the construction in section 3. More points give more units and a closer fit to a smooth curve.

Depth folds, width only adds #

A second hidden layer applies hinges to the output of the first layer, not to $x$. Suppose the first layer outputs a function that goes up and then down on $[0, 1]$. It folds the interval: two different inputs give the same value. Every hinge in the next layer then acts on both halves at the same time. So the pieces multiply from layer to layer, while inside one layer they only add.

The cleanest example is the tent map $t(x) = 2\operatorname{relu}(x) - 4\operatorname{relu}(x - \tfrac12)$. On $[0, \tfrac12]$ it is $2x$ (up from 0 to 1); on $[\tfrac12, 1]$ it is $2x - 4x + 2 = 2 - 2x$ (down from 1 to 0). It uses 2 units. Apply it twice: $t(t(x))$ goes up and down twice, so it has 4 pieces. Each new layer of 2 units doubles the number of pieces.

Without an activation nothing folds #

If we remove the activation, every layer is an affine map $x \mapsto xW + b$, and an affine map of an affine map is affine. Straight lines stay straight, parallel lines stay parallel, and the midpoint of a segment goes to the midpoint of its image. No number of layers changes this.

3. Definitions and main results #

The multilayer perceptron #

We use the row-vector convention of PyTorch. A mini-batch of $B$ inputs is a matrix $X \in \mathbb{R}^{B \times n_0}$, one example per row. For $l = 1, \dots, L$:

with weights $W_l \in \mathbb{R}^{n_{l-1} \times n_l}$, biases $b_l \in \mathbb{R}^{1 \times n_l}$, the column of ones $\mathbf{1} \in \mathbb{R}^{B}$ (it adds $b_l$ to every row), and an activation $\sigma$ applied entry by entry. The last layer has no activation: $Z_L$ is the output (the logits for classification, followed by a softmax in the loss; lesson 02).

• $L$ is the depth: the number of affine layers. (Do not mix it with the loss $\mathcal{L}$.)
• $n_l$ is the width of layer $l$. Layers $1, \dots, L - 1$ are the hidden layers.
• $Z_l$ is the pre-activation and $A_l$ the activation of layer $l$. Shapes: $Z_l, A_l \in \mathbb{R}^{B \times n_l}$.

Parameter count. Layer $l$ has $n_{l-1} n_l$ weights and $n_l$ biases, so

Example: $2 \to 3 \to 1$ has $(2 + 1) \cdot 3 + (3 + 1) \cdot 1 = 9 + 4 = 13$ parameters.

Example: the transformer feed-forward block. With model width $D$ and hidden width $4D$, the block is $D \to 4D \to D$. Its parameter count is $(D + 1) \cdot 4D + (4D + 1) \cdot D = 8D^2 + 5D$. The attention projections $W_Q, W_K, W_V, W_O$ have $4D^2 + 4D$, and two LayerNorms have $4D$. So the feed-forward part is about $8D^2 / 12D^2 = 2/3$ of a block (lesson 11). For $D = 1024$ it has $8{,}393{,}728$ parameters.

Collapse without nonlinearity #

Proposition. If $\sigma$ is the identity, the network is one affine map $x \mapsto xW + b$ with $W = W_1 W_2 \cdots W_L$, and $\operatorname{rank}(W) \le \min_l n_l$.

Proof.

1. Two layers: $(xW_1 + b_1)W_2 + b_2 = x(W_1W_2) + (b_1W_2 + b_2)$. This is affine, with weight $W_1W_2$ and bias $b_1W_2 + b_2$.
2. Induction on $L$: if the first $L - 1$ layers are one affine map, adding layer $L$ is step 1 again.
3. Rank: $\operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B)$ (linear algebra, lesson 01), and $\operatorname{rank}(W_l) \le \min(n_{l-1}, n_l)$. So the product has rank at most the smallest width. $\blacksquare$

So a deep linear classifier is just softmax regression, possibly with a rank bottleneck. (Its training problem is still non-convex in $(W_1, \dots, W_L)$, which is why deep linear networks are a useful model for studying optimization.)

The universal approximation theorem #

A set $K \subset \mathbb{R}^d$ is compact if it is closed and bounded, for example a cube $[0, 1]^d$. The sup norm of an error is its largest absolute value over $K$: $\sup_{x \in K} |f(x) - g(x)|$. A small sup norm means the approximation is good everywhere on $K$, not only on average.

Theorem (universal approximation; Leshno, Lin, Pinkus and Schocken, 1993). Let $\sigma: \mathbb{R} \to \mathbb{R}$ be continuous and not a polynomial. For every compact set $K \subset \mathbb{R}^d$, every continuous $f: K \to \mathbb{R}$ and every $\varepsilon > 0$ there are $H$ and $a_i, b_i \in \mathbb{R}$, $w_i \in \mathbb{R}^d$ with

In words: one hidden layer is enough to approximate any continuous function on a compact set, to any accuracy, if the activation is not a polynomial. ReLU, tanh, the logistic sigmoid and GELU all qualify. Cybenko (1989) proved the first version for sigmoid-like $\sigma$, and Hornik (1991) for continuous, bounded, non-constant $\sigma$.

Why polynomials fail. If $\sigma$ is a polynomial of degree $k$, then each $\sigma(w_i^\top x + b_i)$ is a polynomial in $x$ of degree at most $k$, and so is every sum of them, for any $H$. These polynomials form a finite-dimensional subspace of the continuous functions. A finite-dimensional subspace is closed, so it cannot come arbitrarily close to functions outside it, such as $x_1^{k+1}$ on a cube.

The 1-D ReLU case by construction #

For ReLU in one dimension we can prove the theorem with our own hands. The idea is the "connect the dots" construction of section 2.

Theorem (exact interpolation). Take knots $x_0 < x_1 < \dots < x_K$ with values $y_0, \dots, y_K$, and let $g$ be the piecewise-linear interpolant (straight lines between the points). Let $s_k = (y_k - y_{k-1})/(x_k - x_{k-1})$ be the slope on $[x_{k-1}, x_k]$, for $k = 1, \dots, K$. Then

equals $g$ on $[x_0, x_K]$. It is a one-hidden-layer network with $K$ units: input weights 1, biases $-x_0, \dots, -x_{K-1}$, output weights $s_1$ and $s_{k+1} - s_k$, and output bias $y_0$.

Proof.

1. $N$ is continuous and piecewise linear, with joints only at $x_0, \dots, x_{K-1}$.
2. At $x = x_0$ every ReLU is zero, so $N(x_0) = y_0 = g(x_0)$.
3. Take $x$ in an interval $(x_j, x_{j+1})$. The units with joints $x_0, \dots, x_j$ are active (each has slope 1), and the others are zero. So the slope of $N$ there is $s_1 + (s_2 - s_1) + \dots + (s_{j+1} - s_j) = s_{j+1}$. The sum telescopes: every middle term cancels.
4. $N$ and $g$ start at the same value and have the same slope on every interval, so they are equal on $[x_0, x_K]$. $\blacksquare$

Theorem (approximation of any continuous $f$ on $[a, b]$). For every continuous $f$ and every $\varepsilon > 0$ there is a one-hidden-layer ReLU network $g$ with $\sup_{[a, b]} |f - g| < \varepsilon$.

Proof.

1. A continuous function on a closed, bounded interval is uniformly continuous: there is $\delta > 0$ such that $|x - x'| < \delta$ implies $|f(x) - f(x')| < \varepsilon$.
2. Choose knots $a = x_0 < \dots < x_K = b$ with spacing less than $\delta$. Set $y_k = f(x_k)$ and let $g$ be the interpolant. By the previous theorem, $g$ is a ReLU network.
3. For $x \in [x_k, x_{k+1}]$, $g(x) = \lambda f(x_k) + (1 - \lambda) f(x_{k+1})$ for some $\lambda \in [0, 1]$. Then $|f(x) - g(x)| \le \lambda |f(x) - f(x_k)| + (1 - \lambda)|f(x) - f(x_{k+1})| < \varepsilon$, because $x$ is within $\delta$ of both knots. $\blacksquare$

Rate. For a twice-differentiable $f$ and knot spacing $h$, the interpolation error is at most $h^2 \max|f''| / 8$. Halve $h$ (twice the units) and the error falls by a factor 4. In $d$ dimensions, a grid of spacing $h$ has about $h^{-d}$ cells, so a grid-based construction needs a number of units that grows exponentially with $d$: the curse of dimensionality.

What the theorem does not give #

• Width. $H$ can be huge, exponential in $d$ in the worst case.
• Learnability. The weights exist; nothing says gradient descent finds them. For example, networks trained by gradient descent fit low frequencies first (spectral bias, Rahaman et al. 2019), so fine details can take very long to learn.
• Generalization. The theorem approximates a known $f$. It says nothing about learning $f$ from finite, noisy samples (lesson 17).
• Outside $K$. No control at all. Far from its joints, a ReLU network is affine.

Depth separation #

Shallow, 1-D. $H$ ReLU units in one hidden layer give at most $H + 1$ pieces (section 2).

Theorem (pieces of a deep ReLU network, 1-D input). A network $\mathbb{R} \to \mathbb{R}$ with $K$ hidden layers of width $D$ has at most $(D + 1)^K$ linear pieces.

Proof.

1. After the first hidden layer, every unit output is piecewise linear in $x$, with at most $D + 1$ pieces in total (all joints together).
2. Suppose that after layer $l$ all unit outputs are linear on each of $p$ pieces. A unit of layer $l + 1$ computes $\operatorname{relu}$ of an affine combination of these outputs. On each piece, the combination is a linear function of $x$, so the ReLU adds at most one joint inside that piece.
3. The $D$ units of layer $l + 1$ add at most $D$ joints inside each piece, which splits it into at most $D + 1$ pieces. So after layer $l + 1$ there are at most $p(D + 1)$ pieces.
4. Start with $p = 1$ (no layer yet) and repeat $K$ times: at most $(D + 1)^K$. The output layer is affine and adds no joint. $\blacksquare$

The tent map reaches exponential growth. $t$ maps $[0, 1]$ onto $[0, 1]$ twice (once going up, once going down). So every composition doubles the pieces: the $k$-fold composition $t^{(k)}$ is a sawtooth with $2^k$ pieces. Its values are $0, 1, 0, 1, \dots$ at $x = j/2^k$. It uses $k$ hidden layers of 2 units ($2k$ units). A network with one hidden layer needs $2^k - 1$ joints, so at least $2^k - 1$ units, to represent it.

Answers to section 1. (1) Only affine maps $x \mapsto xW + b$, with $\operatorname{rank}(W)$ at most the smallest width. The ten layers add nothing that one layer cannot do. (2) Network B. The tent-map construction gives $2^{10} = 1024$ pieces with 20 units, while A has at most $1000 + 1 = 1001$ pieces.

4. Worked example #

Approximate $f(x) = x^2$ on $[0, 2]$ with a ReLU network.

Knots $0, 1, 2$ (spacing $h = 1$). The values are $y = (0, 1, 4)$. The slopes are $s_1 = (1 - 0)/1 = 1$ and $s_2 = (4 - 1)/1 = 3$. The output weights are $c_0 = s_1 = 1$ and $c_1 = s_2 - s_1 = 2$, so

This is a network with two hidden units: input weights $(1, 1)$, biases $(0, -1)$, output weights $(1, 2)$, output bias 0.

• Values. $N(0) = 0$. $N(1) = 1 + 2 \cdot 0 = 1$. $N(2) = 2 + 2 \cdot 1 = 4$. ✓
• Slopes. On $(0, 1)$ only $\operatorname{relu}(x)$ is active: slope 1. On $(1, 2)$ both are active: slope $1 + 2 = 3$. ✓
• Error. At $x = 0.5$: $N = 0.5$, $f = 0.25$, error $0.25$. The bound is $h^2 \max|f''|/8 = 1 \cdot 2/8 = 0.25$. It is reached at the midpoints $0.5$ and $1.5$.

Knots $0, 0.5, 1, 1.5, 2$ (spacing $h = 0.5$). The values are $0, 0.25, 1, 2.25, 4$. The slopes are $0.5, 1.5, 2.5, 3.5$. The output weights are $c_0 = 0.5$ and the slope changes $1.5 - 0.5 = 1$, $2.5 - 1.5 = 1$, $3.5 - 2.5 = 1$:

The largest error is $0.0625 = 0.25/4$: twice the units give a quarter of the error (the $h^2$ rate). This network has $H = 4$ units and $3H + 1 = 13$ parameters (an input weight, a bias and an output weight per unit, plus the output bias).

5. In code #

PyTorch and NumPy check the counts, the collapse, the worked example and the tent map.

import numpy as np
import torch
from torch import nn

torch.manual_seed(0)

# 1. Parameter count of a transformer-style FFN, D = 1024, hidden width 4D.
ffn = nn.Sequential(nn.Linear(1024, 4096), nn.GELU(), nn.Linear(4096, 1024))
print(sum(p.numel() for p in ffn.parameters()))        # 8393728 = 8 D^2 + 5 D

# 2. Without the nonlinearity, two layers are one affine map.
f1, f2 = nn.Linear(5, 7), nn.Linear(7, 3)
x = torch.randn(4, 5)
W = f2.weight @ f1.weight                  # PyTorch layout: (out, in)
b = f2.weight @ f1.bias + f2.bias
print(torch.allclose(f2(f1(x)), x @ W.T + b, atol=1e-6))   # True

# 3. The worked example: N(x) = relu(x) + 2 relu(x - 1) against x^2 on [0, 2].
xs = np.linspace(0, 2, 2001)
N = np.maximum(xs, 0) + 2 * np.maximum(xs - 1, 0)
print(np.abs(N - xs**2).max())             # 0.25 (at x = 0.5 and x = 1.5)

# 4. Depth: k compositions of the tent map t(x) = 2 relu(x) - 4 relu(x - 1/2).
t = lambda u: 2 * np.maximum(u, 0) - 4 * np.maximum(u - 0.5, 0)
grid = np.linspace(0, 1, 2**12 + 1)        # dyadic grid: contains every joint
for k in (1, 3, 10):
    y = grid.copy()
    for _ in range(k):
        y = t(y)
    slopes = np.diff(y) / np.diff(grid)
    pieces = 1 + np.count_nonzero(np.abs(np.diff(slopes)) > 1e-9)
    print(k, 2 * k, pieces)                # 1 2 2 / 3 6 8 / 10 20 1024

The FFN count is $1024 \cdot 4096 + 4096 + 4096 \cdot 1024 + 1024 = 8{,}393{,}728$. The last loop prints 2, 8 and 1024 pieces for 2, 6 and 20 units.

6. Where it shows up #

• Transformers. Each block has the feed-forward MLP $D \to 4D \to D$ with $8D^2$ weights, against $4D^2$ for the attention projections (lesson 11). Mixture-of-experts layers replace this one MLP by many (lesson 15).
• Classifiers and regressors. An MLP on top of features is the standard "head" of a vision or language model; a linear probe is the special case with no hidden layer (lesson 14).
• ML for science. PINNs and neural fields are coordinate MLPs. The theorem says a solution can be represented; it does not say it can be learned. Spectral bias is why Fourier features (Tancik et al. 2020) or sine activations (SIREN, Sitzmann et al. 2020) are used for fields with fine scales.
• Operator learning. Chen and Chen (1995) proved a universal approximation theorem for nonlinear operators. It is the theory behind DeepONet (Lu et al. 2021).
• Architecture design. Depth against width is a design choice with a theory behind it: for a fixed parameter budget, deeper ReLU networks can produce far more linear regions (Prince, Fig. 4.7).

7. Common mistakes #

• Forgetting the biases in the parameter count. Each layer has $(n_{l-1} + 1) n_l$ parameters, not $n_{l-1} n_l$.
• Putting an activation on the output layer. The last layer outputs logits or real values; a ReLU there would make negative outputs impossible.
• "Universal approximation means a network can learn anything." It is an existence result: no width bound, no training guarantee, no statement about data.
• Dropping the conditions. A ReLU network cannot approximate $x^2$ or $\sin x$ uniformly on all of $\mathbb{R}$: it is affine outside a bounded interval. The domain must be compact, and the target continuous.
• Stacking linear layers "for capacity". Without $\sigma$ they collapse to one affine map, with rank at most the narrowest width.
• Counting regions as capacity. The many regions of a deep network depend strongly on each other.

8. Check yourself #

1. How many parameters does an MLP $3 \to 4 \to 4 \to 2$ with biases have?
   Answer

   $(3+1)\cdot 4 + (4+1)\cdot 4 + (4+1)\cdot 2 = 16 + 20 + 10 = 46$.
2. Why does a polynomial activation fail the theorem?
   Answer

   With $\sigma$ of degree $k$, every one-hidden-layer network is a polynomial of degree at most $k$, for any width. These polynomials form a finite-dimensional, closed subspace of the continuous functions on $K$, which is not dense: it misses, for example, $x^{k+1}$ on an interval.
3. In the worked example, how many hidden units does the uniform grid need for a largest error of at most $10^{-4}$ on $[0, 2]$?
   Answer

   $h^2 \cdot 2/8 \le 10^{-4}$ gives $h^2 \le 4 \cdot 10^{-4}$, so $h \le 0.02$. Then $K = 2/0.02 = 100$ cells and 100 hidden units.
4. Describe $t \circ t$ for the tent map on $[0, 1]$.
   Answer

   A sawtooth with 4 pieces: values $0, 1, 0, 1, 0$ at $x = 0, \tfrac14, \tfrac12, \tfrac34, 1$, slopes $\pm 4$.
5. Can a ReLU network approximate $\sin x$ uniformly on all of $\mathbb{R}$?
   Answer

   No. Beyond its last joint the network is affine. If the slope there is nonzero, the error grows without bound. If it is zero, the network is a constant $c$ there, and $\sup|\sin x - c| \ge 1$.
6. A linear autoencoder $784 \to 64 \to 784$ has no activations. Which maps can it represent?
   Answer

   Only affine maps $x \mapsto xW + b$ with $\operatorname{rank}(W) \le 64$. Trained with squared error on centered data, its best solution projects onto the top-64 principal subspace, as PCA does ([linear algebra, lesson 09](/linear-algebra/09-pca-randomized-svd/)).

9. Interview angle #

• "Why do we need nonlinearities?" — Without them, any depth collapses to one affine map, with rank at most the narrowest width.
• "State the universal approximation theorem. Why use deep networks then?" — One hidden layer with a non-polynomial activation approximates any continuous function on a compact set. It is existence only, with no width bound. Depth can be exponentially more efficient (the sawtooth), and in practice deep networks train and generalize better.
• "How many linear regions does a ReLU network have?" — In 1-D: at most $H + 1$ for one layer of $H$ units, at most $(D + 1)^K$ for $K$ layers of width $D$; the tent map reaches $2^k$ with $2k$ units.
• "Count the parameters of this MLP." — $\sum_l (n_{l-1} + 1)\, n_l$. Do not forget the biases.
• "Can a ReLU network extrapolate $x^2$?" — No: far from its joints it is affine, so it grows linearly, not quadratically.

10. Practice #

The notebook for this lesson runs in Colab. It uses NumPy (PyTorch only for one optional check). Each exercise has a check cell and a folded solution:

1. mlp_forward: the forward pass of an MLP in the row convention, with the shapes of every layer.
2. count_params: the parameter count, checked against the formula (and against nn.Sequential when PyTorch is installed).
3. relu_interpolant: the weights of the one-hidden-layer network through given knots, checked to be exact on the knots.
4. The error of the interpolant of $\sin$ against the number of units: measure the slope on a log-log plot and compare it with the $h^2$ rate.
5. sawtooth: build $t^{(k)}$ as a deep network with $2k$ units and count its pieces.

11. Watch and read #

• Michael Nielsen, Neural Networks and Deep Learning, chapter 4: A visual proof that neural nets can compute any function (free online book): the same construction with step-like units.
• Simon Prince, Understanding Deep Learning (free PDF): chapter 3 (shallow networks, universal approximation) and chapter 4, §4.5 (shallow against deep, linear regions). The notebooks for chapter 3 draw the regions of small networks.
• Matus Telgarsky, Benefits of depth in neural networks (2016): §1.1 and §3 (the triangle maps and the oscillation count).
• The theorem of section 3: Leshno, Lin, Pinkus and Schocken, "Multilayer feedforward networks with a nonpolynomial activation function can approximate any function", Neural Networks 6 (1993). The journal version is not free; chapter 3 of Prince's book above gives the statement and the references.