---
title: Universal Approximation
module: Neural Networks
moduleNumber: 2
lessonNumber: 3
order: 203
summary: >
  One hidden layer with a non-polynomial activation can approximate any
  continuous function on a compact set to arbitrary accuracy: the universal
  approximation theorem. We prove it constructively (two sigmoids make a bump;
  sums of bumps make any curve), then show the limitation: existence is not
  efficiency. Depth-separation results exhibit functions a deep net represents
  with $O(n)$ units that a shallow net needs $\exp(n)$ units to match.
topics: [Neural Networks]
sources:
  - book: Goodfellow
    ref: "§6.4.1 — Universal Approximation Properties and Depth"
  - book: Goodfellow
    ref: "§6.4 — Architecture Design"
---

The [multilayer perceptron](/deep-learning/neural-networks/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 \mathbb{R}$ be continuous on a compact set $K \subset
\mathbb{R}^d$. A single-hidden-layer network with $N$ units computes

$$
F_N(x) = \sum_{j=1}^{N} v_j\, g\parens{w_j^\top x + b_j},
$$

an affine readout of $N$ nonlinear features, each a neuron with weights $w_j \in
\mathbb{R}^d$, bias $b_j \in \mathbb{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$.[^gf-uat]

> **Theorem (Universal Approximation).** Let $g : \mathbb{R} \to \mathbb{R}$ be
> continuous and **non-polynomial**. Then for every continuous $f : K \to
> \mathbb{R}$ on a compact $K \subset \mathbb{R}^d$ and every $\varepsilon > 0$,
> there exist a width $N$ and parameters $\{(v_j, w_j, b_j)\}_{j=1}^N$ such that
> the single-hidden-layer network $F_N$ satisfies
> $\;\sup_{x \in K}\, \abs{F_N(x) - f(x)} < \varepsilon.$

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^\top x + b_j)$ is a polynomial of degree
$\le k$ in the coordinates of $x$, and a finite sum of degree-$\le k$ polynomials
is again a polynomial of degree $\le k$. So $F_N$ lives in the space of
polynomials of degree at most $k$ in $d$ variables, a fixed
$\binom{d+k}{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 $\sigma$, $\tanh$, and piecewise $\rho$ effectively do),
the features are no longer confined to a finite-dimensional subspace and their
span is dense in $C(K)$.

> **Definition (Universal approximator).** A parametric family $\{F_\theta\}$ is a
> universal approximator on $K$ if its closure under the uniform norm
> $\norm{h}_\infty = \sup_{x\in K}\abs{h(x)}$ contains every
> continuous $f : K \to \mathbb{R}$, i.e. the family is _dense_ in
> $C(K)$. Width $N$ may grow without bound as $\varepsilon \to 0$.

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.[^gf-arch]

## A constructive proof: bumps from sigmoids

Cybenko's original argument is a functional-analysis duality (a measure
that annihilates every $g(w^\top 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 $\sigma(z) =
1/(1+e^{-z})$. A single _steep_ sigmoid approximates a step: as the gain $s \to
\infty$,

$$
\sigma\parens{s(x - a)} \;\longrightarrow\;
\mathbf{1}[x > a],
$$

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

$$
\phi_{a,\Delta}(x) \;=\; \sigma\parens{s(x - a)} - \sigma\parens{s(x - a - \Delta)}
\;\xrightarrow[\,s\to\infty\,]{}\;
\mathbf{1}\brackets{a \le x \le a + \Delta}.
$$

$$
% caption: Two opposed sigmoids make a bump. The left step $\sigma(s(x-a))$ (blue)
% minus the right step $\sigma(s(x-a-\Delta))$ (red) leaves a localized bump
% $\phi_{a,\Delta}$ (green), supported on $[a,a+\Delta]$.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (-3.0,0) -- (3.3,0) node[right, font=\footnotesize] {input};
  \draw[->, thick] (0,-0.3) -- (0,3.0) node[above, font=\footnotesize] {output};
  \draw[black, dashed] (-2.9,2.0) -- (2.9,2.0) node[black, right, font=\footnotesize] {1};
  % left step: rises at x=-1
  \draw[acc, very thick] plot[domain=-2.6:2.6, samples=100] (\x, {2/(1+exp(-2.5*(\x+1)))});
  \node[acc, font=\footnotesize, anchor=east] at (-1.6,2.45) {\texttt{left step}};
  % right step: rises at x=+1
  \draw[red, very thick] plot[domain=-2.6:2.6, samples=100] (\x, {2/(1+exp(-2.5*(\x-1)))});
  \node[red, font=\footnotesize, anchor=west] at (1.75,2.45) {\texttt{right step}};
  % bump = difference
  \draw[green, very thick] plot[domain=-2.6:2.6, samples=130]
    (\x, {2/(1+exp(-2.5*(\x+1))) - 2/(1+exp(-2.5*(\x-1)))});
  \node[green, font=\footnotesize, anchor=south west] at (0.2,2.15) {\texttt{bump}};
\end{tikzpicture}
$$

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 $\Delta = 1/N$ at grid points $x_k = k\Delta$, 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) \;=\; \sum_{k=1}^{N} f(x_k)\,\phi_{x_{k-1},\,\Delta}(x)
\;\approx\; \sum_{k=1}^{N} f(x_k)\,\mathbf{1}\brackets{x_{k-1} \le x \le x_k}.
$$

This is precisely a **Riemann sum** rendered as a network. Each tile uses two
hidden units, so $F_N$ has $2N$ units; uniform continuity of $f$ controls the
error.[^chollet-capacity]

For example, take a bump centred on
$[0.4, 0.6]$ with gain $s = 50$: the network computes $\sigma(50(x-0.4)) -
\sigma(50(x-0.6))$. At the left edge $x = 0.4$ the first sigmoid sits at
$\sigma(0) = 0.5$ while the second is $\sigma(-10) \approx 4.5\times 10^{-5}$, so
the bump reads $\approx 0.5$; at the centre $x = 0.5$ both arguments are
$\pm 5$, giving $\sigma(5) - \sigma(-5) = 0.9933 - 0.0067 = 0.987$; outside
$[0.35, 0.65]$ both sigmoids are saturated the same way and cancel to under
$10^{-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.

> **Proof (sketch, one-dimensional).** Fix $\varepsilon > 0$. Since $f$ is
> continuous on the compact $[0,1]$ it is uniformly continuous, so choose
> $\delta$ with $\abs{f(x) - f(x')} < \varepsilon/2$ whenever
> $\abs{x - x'} < \delta$, and take $N$ with $\Delta = 1/N < \delta$. On each slab the
> step value $f(x_k)$ differs from $f(x)$ by less than $\varepsilon/2$. Pick the
> gain $s$ large enough that each two-sigmoid bump is within $\varepsilon/2$ of
> its ideal indicator off a negligible transition zone. Then
> $\sup_x \abs{F_N(x) - f(x)} < \varepsilon/2 + \varepsilon/2 = \varepsilon$. The multivariate
> case tiles $K$ with $d$-dimensional bumps built as products of one-dimensional
> ones (a ridge per coordinate), or invokes Stone–Weierstrass on the algebra
> generated by the features. $\qed$

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (-0.3,0) -- (6.4,0) node[right, font=\footnotesize] {input};
  \draw[->, thick] (0,-0.3) -- (0,3.0) node[above, font=\footnotesize] {output};
  % staircase approximation (bump sum) drawn first, behind the curve
  \draw[green, very thick]
    (0,0.6) -- (0.75,0.6) -- (0.75,1.25) -- (1.5,1.25) -- (1.5,1.95) --
    (2.25,1.95) -- (2.25,2.45) -- (3.0,2.45) -- (3.0,2.6) -- (3.75,2.6) --
    (3.75,2.35) -- (4.5,2.35) -- (4.5,1.7) -- (5.25,1.7) -- (5.25,1.0) -- (6.0,1.0);
  \node[green, font=\footnotesize, anchor=south west] at (4.7,2.5) {\texttt{bump sum}};
  % smooth target curve on top
  \draw[acc, very thick] plot[domain=0:6, samples=120]
    (\x, {1.4 + 1.15*sin(\x*42) });
  \node[acc, font=\footnotesize, anchor=south] at (2.6,2.75) {target};
\end{tikzpicture}
$$

## The ReLU version: ramps, not bumps

The modern activation is the [ReLU](/deep-learning/neural-networks/activation-functions)
$\rho(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 + \sum_{j=1}^{N} v_j\,\rho(x - b_j),
\qquad
F_N \text{ 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 \rho(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 \le 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 $\bigl(f(b_{m+1}) - f(b_m)\bigr)/h$, so the required
jump is the **second difference**

$$
v_j \;=\; \frac{f(b_{j+1}) - 2f(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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (-0.3,0) -- (6.4,0) node[right, font=\footnotesize] {input};
  \draw[->, thick] (0,-0.3) -- (0,3.0) node[above, font=\footnotesize] {output};
  % the constituent ramps, faint, below
  \draw[black, thick] (1.2,0) -- (2.4,0) -- (3.0,0.55);
  \draw[black, thick] (2.4,0) -- (3.6,0) -- (4.2,0.5);
  \draw[black, thick] (3.6,0) -- (4.8,0) -- (5.4,0.45);
  \node[black, font=\footnotesize, anchor=north west] at (3.0,0.0) {\texttt{shifted ramps}};
  % smooth target
  \draw[acc, very thick] plot[domain=0:6, samples=120]
    (\x, {1.5 + 0.95*sin(\x*40) });
  \node[acc, font=\footnotesize, anchor=south] at (1.4,2.55) {target};
  % piecewise-linear interpolant (vertices sampled near the curve)
  \draw[green, very thick]
    (0,1.5) -- (0.75,2.07) -- (1.5,2.36) -- (2.25,2.13) -- (3.0,1.5) --
    (3.75,0.86) -- (4.5,0.63) -- (5.25,0.93) -- (6.0,1.5);
  \node[green, font=\footnotesize, anchor=south] at (4.9,1.75) {\texttt{linear spline}};
\end{tikzpicture}
$$

> **Lemma (ReLU piecewise-linear density).** A one-hidden-layer ReLU network with
> $N$ units computes a continuous piecewise-linear function with at most $N+1$
> linear pieces, and conversely every continuous piecewise-linear $f$ on a
> compact interval with $m$ pieces is computed _exactly_ by such a network with
> $m-1$ units. Since piecewise-linear functions are dense in $C(K)$, ReLU
> networks are universal approximators.

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.[^gf-depthsep]

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 - \abs{2x - 1}$, a single fold built from two ReLUs. Written
out, $T(x) = 2\rho(x) - 4\rho(x - \tfrac12) + 2\rho(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,\tfrac12]$ and $[\tfrac12,1]$ across the full range $[0,1]$, folding
the interval in half like paper. So if a function $\psi$ has $p$ linear pieces on
$[0,1]$, the composition $\psi \circ T$ replays all $p$ pieces on each half,
giving $2p$ 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) \;=\; \underbrace{T \circ T \circ \cdots \circ T}_{n}\,(x)
\quad\text{has } 2^{\,n} \text{ linear pieces, using only } 2n \text{ ReLUs.}
$$

$$
% caption: Folding doubles linear pieces: composing the tent map $n$ times yields
% $2^n$ teeth from only $2n$ ReLUs, which a shallow net cannot match cheaply.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % ---- one fold (left) ----
  \begin{scope}
    \draw[->, thick] (-0.2,0) -- (2.4,0) node[right, font=\footnotesize] {x};
    \draw[->, thick] (0,-0.2) -- (0,2.3);
    \draw[acc, very thick] (0,0) -- (1.0,2.0) -- (2.0,0);
    \node[font=\footnotesize, anchor=north] at (1.0,-0.25) {1 fold (2 ReLUs)};
    \node[acc, font=\footnotesize] at (1.0,2.2) {2 pieces};
  \end{scope}
  % ---- two folds (middle) ----
  \begin{scope}[xshift=4.0cm]
    \draw[->, thick] (-0.2,0) -- (2.4,0) node[right, font=\footnotesize] {x};
    \draw[->, thick] (0,-0.2) -- (0,2.3);
    \draw[acc, very thick] (0,0) -- (0.5,2.0) -- (1.0,0) -- (1.5,2.0) -- (2.0,0);
    \node[font=\footnotesize, anchor=north] at (1.0,-0.25) {2 folds (4 ReLUs)};
    \node[acc, font=\footnotesize] at (1.0,2.2) {4 pieces};
  \end{scope}
  % ---- three folds (right) ----
  \begin{scope}[xshift=8.0cm]
    \draw[->, thick] (-0.2,0) -- (2.4,0) node[right, font=\footnotesize] {x};
    \draw[->, thick] (0,-0.2) -- (0,2.3);
    \draw[green, very thick]
      (0,0) -- (0.25,2.0) -- (0.5,0) -- (0.75,2.0) -- (1.0,0) --
      (1.25,2.0) -- (1.5,0) -- (1.75,2.0) -- (2.0,0);
    \node[font=\footnotesize, anchor=north] at (1.0,-0.25) {3 folds (6 ReLUs)};
    \node[green, font=\footnotesize] at (1.0,2.2) {8 pieces};
  \end{scope}
\end{tikzpicture}
$$

A depth-$n$ folding net produces $2^n$ linear pieces with $2n$ 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.

> **Theorem (Depth separation — sawtooth).** There is a family of functions
> $f_n : [0,1] \to \mathbb{R}$ computable by a ReLU network of depth $O(n)$ and
> width $O(1)$ (total $O(n)$ units) such that **any** depth-$2$ ReLU network
> approximating $f_n$ to constant accuracy must have width $\Omega(2^{n})$
> (Telgarsky 2016). The same exponential gap holds for the **parity** function
> $\bigoplus_{i=1}^{n} x_i$ on the Boolean cube: linear depth suffices, but a
> single hidden layer needs $\exp(n)$ units (Håstad-style circuit lower bounds).

> **Proof (counting sketch).** The number of linear regions a ReLU network can
> carve into its input is at most $w+1$ for one hidden layer of width $w$, but
> _multiplies_ across layers: $L$ layers of width $w$ realize on the order of
> $w^{\,L}$ regions, exponential in depth, only polynomial in width. The
> sawtooth $f_n = T^{(n)}$ oscillates across $2^n$ regions, so any approximant
> must itself resolve $\Omega(2^n)$ regions. A depth-$2$ net achieves this region
> count only with width $\Omega(2^n)$, whereas folding reaches it with $O(n)$
> units. Depth buys region count multiplicatively; width buys it only
> additively. $\qed$

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
$\mathbb{R}^d$ into is $\sum_{i=0}^{d}\binom{w}{i}$, 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

$$
\#\text{regions} \;=\; O\!\left( \left(\tfrac{w}{d}\right)^{(L-1)d} \, w^{d} \right)
\;=\; 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 = \Omega(2^n)$ units, and the former is
exponentially cheaper.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % ---- one layer: 4 hyperplanes ----
  \begin{scope}
    \draw[black] (0,0) rectangle (3,3);
    \draw[acc, thick] (0.5,0) -- (2.7,3);
    \draw[acc, thick] (0,2.3) -- (3,1.4);
    \draw[acc, thick] (2.6,0) -- (0.3,3);
    \draw[acc, thick] (0,0.6) -- (3,1.9);
    \node[font=\footnotesize, anchor=north] at (1.5,-0.2) {\texttt{1 layer, w = 4}};
    \node[acc, font=\footnotesize, anchor=south] at (1.5,3.15) {\texttt{11 regions}};
  \end{scope}
  % ---- two layers: composed cuts ----
  \begin{scope}[xshift=5.2cm]
    \draw[black] (0,0) rectangle (3,3);
    \draw[acc, thick] (0.5,0) -- (2.7,3);
    \draw[acc, thick] (0,2.3) -- (3,1.4);
    \draw[acc, thick] (2.6,0) -- (0.3,3);
    \draw[acc, thick] (0,0.6) -- (3,1.9);
    % second layer re-cuts: fold the lines within regions (short green cuts)
    \draw[green, thick] (1.5,0) -- (1.5,3);
    \draw[green, thick] (0,1.5) -- (3,1.5);
    \draw[green, thick] (0.4,0) -- (3,2.2);
    \draw[green, thick] (0,2.4) -- (2.6,0);
    \node[font=\footnotesize, anchor=north] at (1.5,-0.2) {\texttt{2 layers}};
    \node[green, font=\footnotesize, anchor=south] at (1.5,3.15) {\texttt{many more regions}};
  \end{scope}
  \draw[->, black, thick] (3.4,1.5) -- (4.8,1.5)
    node[midway, above, font=\footnotesize] {\texttt{compose}};
\end{tikzpicture}
$$

$$
% caption: Width explosion. For the depth-$n$ sawtooth a shallow net pays
% $\Omega(2^n)$ units (red) while a deep net pays only $O(n)$ (green).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % ---- shallow-wide: one fat bar ----
  \node[font=\small, anchor=south] at (1.0,3.4) {\texttt{shallow \& wide}};
  \draw[red, very thick, fill=red!15] (0.3,0) rectangle (1.7,3.2);
  \node[red, font=\footnotesize, anchor=north] at (1.0,-0.1) {\texttt{1 layer}};
  \node[red, font=\small] at (1.0,1.6) {$2^{n}$};
  \node[font=\footnotesize, anchor=north] at (1.0,-0.55) {\texttt{units}};
  % ---- deep-narrow: many thin bars ----
  \node[font=\small, anchor=south] at (7.0,3.4) {\texttt{deep \& narrow}};
  \foreach \i in {0,...,7} {
    \draw[green, very thick, fill=green!15]
      ({4.0 + \i*0.75},0) rectangle ({4.0 + \i*0.75 + 0.45},0.7);
  }
  \node[green, font=\footnotesize, anchor=north] at (7.0,-0.1) {$n$ \texttt{layers}};
  \node[green, font=\small] at (7.0,1.4) {$2n$ \texttt{units total}};
  % comparison arrow
  \draw[->, black, thick] (2.1,1.6) -- (3.7,1.6)
    node[midway, above, font=\footnotesize, text=black] {\texttt{same function}};
\end{tikzpicture}
$$

## 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 | $\Omega(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.[^gf-compositional]

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (0,0) -- (6.4,0) node[right, font=\footnotesize] {depth L};
  \draw[->, thick] (0,0) -- (0,4.2)
    node[above, font=\footnotesize, anchor=south east] {log regions};
  % gridline ticks on y
  \foreach \y/\lab in {1/2,2/4,3/8} {
    \draw[black] (0,\y) -- (6,\y);
    \node[black, font=\footnotesize, anchor=east] at (-0.1,\y) {\lab};
  }
  % deep: exponential (straight line in log) -- slope from w^L
  \draw[green, very thick] (0.4,0.4) -- (1.4,1.4) -- (2.4,2.4) -- (3.4,3.4) -- (4.4,4.0);
  \node[green, font=\footnotesize, anchor=west] at (4.55,3.6) {\texttt{depth: w to the L}};
  % shallow: additive -- nearly flat, sublinear in log
  \draw[acc, very thick] plot[domain=0.4:6, samples=60] (\x, {0.55 + 0.9*ln(\x)/ln(6)});
  \node[acc, font=\footnotesize, anchor=north west] at (3.0,1.05) {\texttt{width: w times L}};
\end{tikzpicture}
$$

> **Remark (Why depth, restated).** Universality answers _can a net represent
> $f$?_ — and the answer is always yes. Depth answers _how many units does it
> cost?_ — and there the answer separates shallow from deep by an exponential
> factor whenever $f$ has compositional or oscillatory structure. The first
> theorem licenses neural networks at all; the second explains why we stack them.

## 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](/deep-learning/optimization/the-optimization-landscape) |
| Will it _generalize_ from finite data? | nothing | [generalization theory](/deep-learning/theory/generalization-theory) |

> **Definition (Approximation vs. estimation error).** Total error decomposes as
> $\text{approximation error}$ (how well the _best_ network in the class fits
> the target, which universality drives to $0$) plus $\text{estimation error}$
> (how far the _learned_ network lands from that best one, given finite data
> and a finite-time optimizer). Universality crushes the first term and says
> nothing about the second.

$$
% caption: The error budget. The target $f$ sits outside the network class
% $\mathcal{F}$; universality shrinks $\mathcal{F}$ up against $f$ so the
% approximation gap (blue) to the best network $F^\star$ vanishes. The estimation
% gap (red) from $F^\star$ to the trained $\hat F$ is what data and optimization
% must close, and universality is silent on it.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % the class as a blob
  \draw[green, very thick, fill=green!10] (0,0) ellipse (2.6 and 1.7);
  \node[green, font=\footnotesize, anchor=west] at (-2.35,-1.2) {\texttt{network class F}};
  % target outside
  \fill[black] (4.0,1.3) circle (2.2pt);
  \node[black, font=\footnotesize, anchor=west] at (4.15,1.3) {\texttt{target f}};
  % best-in-class point on the boundary near target
  \fill[acc] (2.35,0.9) circle (2.2pt);
  \node[acc, font=\footnotesize, anchor=east] at (1.95,1.15) {\texttt{best F*}};
  % trained point inside, off the best
  \fill[red] (0.9,-0.5) circle (2.2pt);
  \node[red, font=\footnotesize, anchor=north] at (0.9,-0.65) {\texttt{trained F-hat}};
  % approximation gap: best to target
  \draw[acc, thick, dashed] (2.35,0.9) -- (4.0,1.3)
    node[midway, above, font=\footnotesize, acc] {\texttt{approx}};
  % estimation gap: trained to best
  \draw[red, thick, dashed] (0.9,-0.5) -- (2.35,0.9)
    node[midway, below right, font=\footnotesize, red] {\texttt{estim}};
\end{tikzpicture}
$$

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](/deep-learning/optimization/gradient-descent-and-sgd)
question (_can we reach the good parameters?_) and the
[generalization](/deep-learning/theory/generalization-theory) 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 $\varepsilon \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/\sqrt{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 = \Omega(\varepsilon^{-d})$ units, exponential in $d$,
while a Barron-class function needs only $O(\varepsilon^{-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 $\mathbb{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](/deep-learning/theory/generalization-theory) lessons take up.[^beyond-uat]

## 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,
  $\phi_{a,\Delta} = \sigma(s(x-a)) - \sigma(s(x-a-\Delta))$, 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 $\Omega(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](/deep-learning/theory/generalization-theory).

[^gf-uat]: **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.
[^gf-arch]: **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.
[^gf-depthsep]: **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.
[^gf-compositional]: **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.
[^chollet-capacity]: **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.
[^beyond-uat]: Primary sources: Barron, "Universal Approximation Bounds for Superpositions of a Sigmoidal Function" (1993) for the dimension-independent $O(1/\sqrt 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.