Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

Universal Approximation Theorems

What one hidden layer can and cannot do efficiently.

One hidden layer is enough: sums ∑jcjφ(wj⋅x+bj)\sum_jc_j\varphi(\mathbf w_j\cdot\mathbf x+b_j) approximate any continuous function on a compact set, for almost any activation φ\varphi. That is the universal approximation theorem, true and often over-read. This lesson proves it three ways (a construction for ReLUs, Cybenko's duality argument, and the derivative trick behind "any non-polynomial activation"), derives Barron's dimension-free rate with Maurey's sampling argument, and marks what the theorems leave out: how many units, and whether training finds them.

What you’ll learn

  • State the theorems of Cybenko, Hornik and Leshno–Lin–Pinkus–Schocken, and prove that polynomial activations are not universal.
  • Give the constructive one-dimensional ReLU proof with its error bounds, and sketch Cybenko's proof via Hahn–Banach and the Riesz representation theorem.
  • Prove Maurey's lemma, use it to explain Barron's O(1/n)\order{1/n} rate, and contrast it with the n−1/dn^{-1/d} barrier for fixed bases.
  • Distinguish expressivity from trainability, and state minimal-width results for deep narrow networks.

What “universal” means

TheoremActivationConclusion
Cybenko (1989)continuous sigmoidal: φ→0\varphi\to0 at −∞-\infty, →1\to1 at +∞+\inftydense in C([0,1]d)C([0,1]^d)
Hornik, Stinchcombe & White (1989)any squashing function (nondecreasing, limits 0 and 1)uniform approximation on compacta; Borel functions in measure
Hornik (1991)bounded and nonconstantdense in Lp(μ)L^p(\mu) for finite μ\mu; in C(K)C(K) if also continuous
Leshno, Lin, Pinkus & Schocken (1993)locally bounded, piecewise continuousuniversal if and only if φ\varphi is not a polynomial; covers ReLU
Pinkus (1999) surveys the whole family. The universal approximation property is about a single hidden layer; depth is not needed for it.
DerivationA constructive proof for ReLU in one dimension
  1. g(x)=f(0)+s1 ReLU(x−t0)+∑i=1n−1(si+1−si) ReLU(x−ti)g(x)=f(0)+s_1\,\mathrm{ReLU}(x-t_0)+\sum_{i=1}^{n-1}(s_{i+1}-s_i)\,\mathrm{ReLU}(x-t_i)

    Let ff be continuous on [0,1][0,1], take knots ti=i/nt_i=i/n, and let sis_i be the slope of the chord of ff on [ti−1,ti][t_{i-1},t_i]. Define

  2. g(ti)=f(ti)(i=0,…,n),g linear on each [ti−1,ti]g(t_i)=f(t_i)\quad(i=0,\dots,n),\qquad g\ \text{linear on each }[t_{i-1},t_i]

    Each unit switches on at its knot and changes the slope by si+1−sis_{i+1}-s_i, so gg is the piecewise-linear interpolant of ff, built from nn hidden units:

  3. ∥f−g∥∞≤L2n  (f L-Lipschitz),∥f−g∥∞≤∥f′′∥∞8n2  (f∈C2)\norm{f-g}_\infty\le\frac{L}{2n}\ \ (f\ L\text{-Lipschitz}),\qquad\norm{f-g}_\infty\le\frac{\norm{f''}_\infty}{8n^2}\ \ (f\in C^2)

    On an interval of length h=1/nh=1/n, the chord stays within 2L(ti−x)(x−ti−1)/h≤Lh/22L(t_i-x)(x-t_{i-1})/h\le Lh/2 of an LL-Lipschitz ff, and the classical interpolation bound handles smooth ff:

  4. error ε ⇒ n∼ε−1 (d=1),∼ε−d grid cells in d dimensions\text{error }\varepsilon\ \Rightarrow\ n\sim\varepsilon^{-1}\ (d=1),\qquad\sim\varepsilon^{-d}\ \text{grid cells in }d\text{ dimensions}

    Uniform continuity makes the error go to 0 for every continuous ff. In dd dimensions, piecewise-linear interpolation at spacing hh needs on the order of h−dh^{-d} pieces: the curse of dimensionality appears as soon as accuracy has a price.

Two proofs of density

DerivationCybenko’s proof by duality (sketch)
  1. ∫Kσ(w⋅x+b) dμ(x)=0for all w∈Rd, b∈R\int_K\sigma(\mathbf w\cdot\mathbf x+b)\,d\mu(\mathbf x)=0\qquad\text{for all }\mathbf w\in\R^d,\ b\in\R

    Suppose the closure of Σd(σ)\Sigma_d(\sigma) in C(K)C(K) is a proper subspace. Hahn–Banach gives a nonzero bounded linear functional vanishing on it, and the Riesz representation theorem writes it as integration against a nonzero finite signed regular Borel measure μ\mu:

  2. μ({x:w⋅x+b>0})=0for all w,b\mu\big(\{\mathbf x:\mathbf w\cdot\mathbf x+b>0\}\big)=0\qquad\text{for all }\mathbf w,b

    Scale: as λ→∞\lambda\to\infty, σ(λ(w⋅x+b)+ϕ)\sigma\big(\lambda(\mathbf w\cdot\mathbf x+b)+\phi\big) tends to 1 on the open half-space {w⋅x+b>0}\{\mathbf w\cdot\mathbf x+b>0\}, to 0 on the opposite one and to σ(ϕ)\sigma(\phi) on the hyperplane. Bounded convergence, then ϕ→±∞\phi\to\pm\infty, shows that μ\mu gives zero mass to every half-space and hyperplane:

  3. μ^(w)=∫Kei w⋅x dμ(x)=0  for all w⟹μ=0\hat\mu(\mathbf w)=\int_Ke^{i\,\mathbf w\cdot\mathbf x}\,d\mu(\mathbf x)=0\ \ \text{for all }\mathbf w\quad\Longrightarrow\quad\mu=0

    Fix w\mathbf w. The functional h↦∫h(w⋅x) dμh\mapsto\int h(\mathbf w\cdot\mathbf x)\,d\mu vanishes on indicators of intervals, hence on simple functions and, by bounded convergence, on all bounded measurable hh, including cos⁡\cos and sin⁡\sin. So the Fourier transform of μ\mu vanishes everywhere, forcing μ=0\mu=0: a contradiction.

The proof is non-constructive: it shows that no measure can be orthogonal to all sigmoidal ridges, without exhibiting an approximant. Leshno et al.'s "any non-polynomial activation" rests on a different, almost algebraic idea. For smooth σ\sigma, a divided difference in the weight, [σ((w+δ)x+b)−σ(wx+b)]/δ[\sigma((w+\delta)x+b)-\sigma(wx+b)]/\delta, is itself a network, and its limit lies in the closure:

∂k∂wk σ(wx+b)∣w=0=xk σ(k)(b)\frac{\partial^k}{\partial w^k}\,\sigma(wx+b)\Big|_{w=0}=x^k\,\sigma^{(k)}(b)
If σ\sigma is smooth and not a polynomial, then for each kk some bb has σ(k)(b)≠0\sigma^{(k)}(b)\neq0 (otherwise σ(k)≡0\sigma^{(k)}\equiv0 and σ\sigma would be a polynomial). So every monomial xkx^k lies in the closure, and Weierstrass gives density on intervals. In dd dimensions, every homogeneous polynomial is a combination of powers (w⋅x)k(\mathbf w\cdot\mathbf x)^k of linear forms, so ridge functions reach all polynomials, hence all of C(K)C(K). Non-smooth activations are smoothed by convolution, which preserves "not a polynomial".
Check your understanding

With one hidden layer of unlimited width, which activation is not universal?

  1. ReLU(z)\mathrm{ReLU}(z)
  2. tanh⁡z\tanh z
  3. z3−zz^3-z
  4. sin⁡z\sin z
Show the answer

C. z3−zz^3-z

Every network with a cubic activation is a polynomial of degree at most 3, a closed finite-dimensional space. ReLU, tanh and sine are not polynomials, so Leshno et al.'s theorem applies to all three.

Rates: Barron’s theorem

DerivationProof of Maurey’s lemma, and how Barron uses it
  1. E∥f∗−1n∑j=1ngj∥2=1n E∥g1−f∗∥2=E∥g1∥2−∥f∗∥2n≤b2−∥f∗∥2n\E\Big\lVert f^*-\frac1n\sum_{j=1}^ng_j\Big\rVert^2=\frac1n\,\E\norm{g_1-f^*}^2=\frac{\E\norm{g_1}^2-\norm{f^*}^2}{n}\le\frac{b^2-\norm{f^*}^2}{n}

    It suffices to treat a finite convex combination f∗=∑iλihif^*=\sum_i\lambda_ih_i close to ff. Draw g1,…,gng_1,\dots,g_n i.i.d. with Pr⁡(gj=hi)=λi\Pr(g_j=h_i)=\lambda_i, so Egj=f∗\E g_j=f^*; the cross terms of independent mean-zero vectors vanish:

  2. ∃ g1,…,gn∈G:∥f∗−1n∑jgj∥2≤b2n\exists\ g_1,\dots,g_n\in G:\qquad\Big\lVert f^*-\frac1n\sum_jg_j\Big\rVert^2\le\frac{b^2}{n}

    Some outcome is at least as good as the average: the probabilistic method. Nothing in the argument depends on the dimension of the underlying space.

  3. ∥f−fn∥L2(μ)2≤(2rCf)2n⟺n≥(2rCfε)2 units for error ε\norm{f-f_n}^2_{L^2(\mu)}\le\frac{(2rC_f)^2}{n}\qquad\Longleftrightarrow\qquad n\ge\Big(\frac{2rC_f}{\varepsilon}\Big)^2\ \text{units for error }\varepsilon

    Barron writes f(x)−f(0)=∫(cos⁡(ω⋅x+θ(ω))−cos⁡θ(ω))∣f^(ω)∣ dωf(\mathbf x)-f(0)=\int\big(\cos(\boldsymbol\omega\cdot\mathbf x+\theta(\boldsymbol\omega))-\cos\theta(\boldsymbol\omega)\big)\abs{\hat f(\boldsymbol\omega)}\,d\boldsymbol\omega: an average, under the density ∥ω∥∣f^∣/Cf\norm{\boldsymbol\omega}\abs{\hat f}/C_f, of ridge functions bounded by CfrC_fr on BrB_r. Each ridge is a limit of convex combinations of sigmoid steps of norm at most b=2rCfb=2rC_f in L2(μ)L^2(\mu), and Maurey gives

Predict before you look

Suppose 2rCf=12rC_f=1. How many sigmoid units does Barron's theorem guarantee are enough for an L2(μ)L^2(\mu) error of 0.010.01?

Show the answer

10000

n≥(1/0.01)2=10,000n\ge(1/0.01)^2=10{,}000, in any dimension. The catch is hidden in CfC_f: the class of functions with small CfC_f becomes more restrictive as dd grows (functions with about d/2+2d/2+2 square-integrable derivatives qualify).

The rate is dimension-free because the network chooses its own basis functions, the directions ak\mathbf a_k, to suit ff. Barron also proved that for any nn fixed basis functions, the worst-case squared error over the same class is at least of order (1/n)2/d(1/n)^{2/d}: no linear method escapes the curse. For generic smooth classes the curse returns even for networks: on the unit ball of a Sobolev space with ss derivatives on [0,1]d[0,1]^d, any method whose nn parameters depend continuously on ff has worst-case error of order at least n−s/dn^{-s/d} (DeVore, Howard & Micchelli, 1989), so accuracy ε\varepsilon costs about ε−d/s\varepsilon^{-d/s} parameters, a rate shallow networks attain (Mhaskar, 1996) but cannot beat on the whole class.

Width, existence and trainability

Universality with bounded width needs depth instead. ReLU networks of width d+4d+4 are universal in L1(Rd)L^1(\R^d) (Lu et al., 2017). For continuous functions on [0,1]d[0,1]^d with scalar output the minimal width is d+1d+1 (Hanin & Sellke, 2017), and in LpL^p the minimal width of ReLU networks is exactly max⁡(dx+1,dy)\max(d_x+1,d_y) for dxd_x inputs and dyd_y outputs (Park, Yun, Lee & Shin, 2021). Below these widths approximation fails in general; the one-hidden-layer cousin of the obstruction, that a bounded decision region in Rd\R^d needs at least d+1d+1 monotone units, is proved in From Neurons to Networks.

Key takeaways

  • One hidden layer is universal for every locally bounded, piecewise continuous non-polynomial activation (Leshno et al.), including ReLU; polynomial activations fail because they span a closed finite-dimensional space.
  • In one dimension, nn ReLUs interpolate any ff with error L/(2n)L/(2n) for LL-Lipschitz ff; Cybenko's proof is non-constructive (Hahn–Banach, Riesz, Fourier uniqueness).
  • Barron: functions with finite Cf=∫∥ω∥∣f^∣C_f=\int\norm{\boldsymbol\omega}\abs{\hat f} are approximated with squared error (2rCf)2/n(2rC_f)^2/n in any dimension, by Maurey's probabilistic lemma.
  • Fixed bases cannot beat squared error of order n−2/dn^{-2/d} on Barron's class, and generic Sobolev classes cost about ε−d/s\varepsilon^{-d/s} parameters: universality is not efficiency.
  • Width max⁡(dx+1,dy)\max(d_x+1,d_y) suffices with enough depth; approximation theorems are existence results, and training may not find the weights they promise.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What does the universal approximation theorem guarantee for a one-hidden-layer network with a sigmoidal activation?

  1. Gradient descent finds weights within ε\varepsilon of any continuous target
  2. For any continuous ff on a compact set and any ε>0\varepsilon>0, some finite network is uniformly within ε\varepsilon of ff
  3. The number of hidden units needed grows only polynomially with the input dimension
  4. A network fitted to finitely many samples of ff generalizes to all of the compact set
Show the answer

B. For any continuous ff on a compact set and any ε>0\varepsilon>0, some finite network is uniformly within ε\varepsilon of ff

It is a density statement about the set of functions networks can represent. It says nothing about how many units are needed, how to find the weights, or how well a fit to data generalizes.

Question 2

Why can no one-hidden-layer network with the activation φ(z)=z2\varphi(z)=z^2 approximate f(x)=x3f(x)=x^3 uniformly on [0,1][0,1], however wide it is?

  1. z2z^2 is unbounded
  2. z2z^2 is not monotone
  3. Every such network is a polynomial of degree at most 2, and that space is closed and does not contain x3x^3
  4. It can, given enough units
Show the answer

C. Every such network is a polynomial of degree at most 2, and that space is closed and does not contain x3x^3

∑jcj(wjx+bj)2\sum_jc_j(w_jx+b_j)^2 is a quadratic. Quadratics form a three-dimensional, hence closed, subspace of C([0,1])C([0,1]), and x3x^3 has positive distance from it.

Question 3

Under Barron's bound ∥f−fn∥L2(μ)2≤(2rCf)2/n\norm{f-f_n}^2_{L^2(\mu)}\le(2rC_f)^2/n, how many more hidden units guarantee half the L2L^2 error?

  1. Twice as many
  2. 2\sqrt2 times as many
  3. 2d2^d times as many
  4. Four times as many
Show the answer

D. Four times as many

The error itself scales like 1/n1/\sqrt n, so halving it needs 4n4n units, independently of dd.

Question 4

Barron's theorem gives error O(n−1/2)\order{n^{-1/2}} in any dimension, yet he also proved that nn basis functions cannot beat error of order n−1/dn^{-1/d} on the same class. Why is there no contradiction?

  1. The lower bound is for nn fixed basis functions chosen before seeing ff; a network adapts its directions ak\mathbf a_k to ff
  2. The two results use different norms
  3. The lower bound only applies in one dimension
  4. Barron's theorem only holds for d≤3d\le3
Show the answer

A. The lower bound is for nn fixed basis functions chosen before seeing ff; a network adapts its directions ak\mathbf a_k to ff

Linear methods fix the basis and fit only the coefficients. Networks choose their ridge directions per target, a nonlinear approximation, which is exactly what Maurey's sampling argument exploits.

Further reading

  • G. Cybenko, "Approximation by superpositions of a sigmoidal function," Mathematics of Control, Signals and Systems 2, 303–314 (1989).
  • K. Hornik, "Approximation capabilities of multilayer feedforward networks," Neural Networks 4, 251–257 (1991).
  • M. Leshno, V. Ya. Lin, A. Pinkus & S. Schocken, "Multilayer feedforward networks with a nonpolynomial activation function can approximate any function," Neural Networks 6, 861–867 (1993).
  • A. R. Barron, "Universal approximation bounds for superpositions of a sigmoidal function," IEEE Transactions on Information Theory 39, 930–945 (1993).
  • A. Pinkus, "Approximation theory of the MLP model in neural networks," Acta Numerica 8, 143–195 (1999).