Exercises — Universal approximation theorem

The two hypotheses are: continuous target, on a compact (closed + bounded) domain.

• (a) YES — $\sin$ is continuous, $[0,2\pi ]$ is closed and bounded. ✔ both.
• (b) NO — domain $(0,1]$ is open at $0$ (not closed ⇒ not compact) and $f$ blows up. ✘ compactness.
• (c) NO — floor has jumps ⇒ not continuous. ✘ continuity.
• (d) YES — a Gaussian is continuous, $[-5,5]$ is compact. ✔ both.

Universal $⟺$ activation is non-polynomial.

• (a) $z^2$ is a polynomial ⇒ NOT universal.
• (b) $\tanh$ is non-polynomial ⇒ universal.
• (c) ReLU is non-polynomial (a kink is not a polynomial) ⇒ universal.
• (d) constant $7$ is a (degree-0) polynomial and is not "non-constant" ⇒ NOT universal.

Each sigmoid bump = subtract two sharp steps = 2 neurons. So $N=2M$.

• (a) $M=1\Rightarrow N=2$.
• (b) $M=5\Rightarrow N=10$.
• (c) $M=100\Rightarrow N=200$.

Midpoints: $0.125,0.375,0.625,0.875$. Heights $h_k=f(\text{mid})={\text{mid}}^2$:

• $h_1=0.125^2=0.015625$
• $h_2=0.375^2=0.140625$
• $h_3=0.625^2=0.390625$
• $h_4=0.875^2=0.765625$

Neurons: $M=4$ bumps $\Rightarrow N=2M=8$ hidden neurons.

At $x=b$: $\sigma (w\cdot 0)=\sigma (0)=\frac{1}{1+e^0}=\frac{1}{2}=0.5$. Geometrically: every sigmoid, no matter how sharp, passes through height $0.5$ exactly at its center $b$. The step is antisymmetric about that point — this is why $b$ is called the "location" of the step.

Let $g(x)=\text{ReLU}(x)-\text{ReLU}(x-\delta )$ with $\delta =2$.

• $x=-1$: $\max (0,-1)-\max (0,-3)=0-0=0$.
• $x=0$: $\max (0,0)-\max (0,-2)=0-0=0$.
• $x=\frac{\delta }{2}=1$: $\max (0,1)-\max (0,-1)=1-0=1$.
• $x=\delta =2$: $\max (0,2)-\max (0,0)=2-0=2$.
• $x=2\delta =4$: $\max (0,4)-\max (0,2)=4-2=2$.

The value rises from $0$ to $2$ over $[0,\delta ]$ and then stays at $2=\delta$ forever — it never returns to $0$. That is a plateau, not a bump.

Figure s02 (below) shows exactly this: the red curve climbs the ramp over $[0,2]$ then flatlines at the dotted line $y=\delta =2$ and never comes back down. Contrast it mentally with the red localized bump of figure s01 — that is the visual difference between "plateau" and "bump" the whole ReLU discussion turns on.

Uniform continuity (Uniform continuity) says: for any target error $\epsilon$ there is a single width $\delta$ such that whenever two inputs are within $\delta$, their $f$-values are within $\epsilon$ — and this same $\delta$ works everywhere on the domain.

• Make each staircase interval narrower than that $\delta$. Then on each interval $f$ varies by less than $\epsilon$, so the constant plateau (set to $f$ at the midpoint) is within $\epsilon$ of $f$ across that whole interval.
• Compactness is what upgrades ordinary continuity to uniform continuity: on a closed, bounded set a continuous function is automatically uniformly continuous. Without compactness (e.g. $1/x$ on $(0,1]$) no single $\delta$ works everywhere — you'd need infinitely narrow intervals near the trouble spot, i.e. infinitely many neurons.

Idea: a flat top needs four corners, so we place four ReLU kinks — one where the left ramp starts, one where it must stop rising, one where the right ramp starts falling, one where it must stop falling. Between the middle two kinks the slopes cancel to $0$, giving a genuine flat plateau (unlike the triangle you'd get from only three kinks).

Use a steep slope $s=\frac{h}{\delta }$ so each side climbs/falls by exactly $h$ over its width-$\delta$ ramp: $B(x)=s\text{ReLU}(x-a)-s\text{ReLU}(x-(a+\delta ))-s\text{ReLU}(x-(b-\delta ))+s\text{ReLU}(x-b).$

• Term 1 starts a $+s$ ramp at $x=a$.
• Term 2 cancels that ramp at $x=a+\delta$ → the value holds flat at height $s\delta =h$.
• Term 3 starts a $-s$ ramp at $x=b-\delta$ → begins descending.
• Term 4 cancels the descent at $x=b$ → the value holds flat at $0$ forever.

Peak height on the plateau $=s\delta =\frac{h}{\delta }\cdot \delta =h$. ✔ (no phantom half-height — the two inner kinks are what flatten the top instead of forming a triangle apex.)

Numerical check. Take $a=0,b=4,\delta =1,h=1$, so $s=1$: $B(x)=\text{ReLU}(x)-\text{ReLU}(x-1)-\text{ReLU}(x-3)+\text{ReLU}(x-4).$

• $x=-1$: $0-0-0+0=0$. ✔ off left.
• $x=1$ (start of top): $1-0-0+0=1$. ✔ at height $h$.
• $x=2$ (middle of top): $2-1-0+0=1$. ✔ flat at $h$.
• $x=3$ (end of top): $3-2-0+0=1$. ✔ still $h$.
• $x=4$: $4-3-1+0=0$. ✔ back to zero.
• $x=6$: $6-5-3+2=0$. ✔ off right forever.

This is a genuine flat-top rectangular bump using 4 ReLU units — vs 2 sigmoid units. That extra pair of units is the "constant-factor overhead" the parent note mentioned.

• Sigmoids: $2$ per bump $\Rightarrow 2\times 4=8$ neurons.
• ReLU flat-top bumps: $4$ per bump $\Rightarrow 4\times 4=16$ neurons.

Ratio $16/8=2$ — a constant factor overhead, not an exponential one. Universality is unaffected; only efficiency shifts. (In practice ReLU nets share kinks between neighbouring bumps and rarely pay the full $2\times$; see Depth vs Width tradeoff.)

Three distinct flaws:

1. Existence ≠ learnability. UAT says there exist weights achieving small error; it does not say gradient descent + Backpropagation found them, nor that the found ones are the approximating ones.
2. Fitting ≠ generalizing. UAT is about approximating a target on its domain given ideal weights. Fitting 500 sampled points says nothing about points between them — that is Overfitting and generalization, a separate bias–variance issue.
3. "Zero training error" is a red flag, not a guarantee — it often signals overfitting (memorizing noise), which typically hurts new-point accuracy.

UAT promises: for a continuous target on a compact domain, a wide-enough shallow net can be within $\epsilon$ everywhere. UAT does not promise: trainability, small width, or generalization to unseen data.

UAT is an existence statement: "$\exists N$ such that error $<\epsilon$." It is silent on how large $N$ must be.

• For some functions the required $N$ grows exponentially with input dimension or with the fineness $1/\epsilon$ — the staircase needs a bump per feature-combination.
• Because $N$ can explode and the loss landscape can be hard, a shallow solution may be both huge and untrainable.
• Depth re-expresses the same function by composing simple maps: features built in early layers are reused, so the total neuron count can drop from exponential to polynomial. Same capability (UAT already granted it), far better efficiency — the theme of Depth vs Width tradeoff.

So UAT ends the "can it be done?" question (yes) and hands off to depth theory for the "how cheaply?" question.

Compactness gives ::: uniform continuity, so one interval width works everywhere. Sigmoid bump neuron cost per bump ::: 2 (subtract two steps). ReLU flat-top bump neuron cost per bump ::: 4 (up-ramp, cancel, down-ramp, cancel). UAT is an existence result about ::: fitting a continuous target on a compact domain, not learnability or generalization. Why we still go deep ::: same capability, exponentially fewer neurons and easier training.