ML Mathematics: Approximation Theory¶
Job: state the universal approximation theorem (Cybenko / Hornik) and its precise qualitative character; develop the approximation rates of neural networks — Barron's dimension-free \(O(1/\sqrt{m})\) rate for variation-norm-bounded functions and the Barron space \(\mathcal{B}^s\); and the depth-separation theorems (Eldan–Shamir, Telgarsky, Yarotsky, Poggio–Mhaskar–Rosasco–Magguli) showing deep nets can be exponentially more efficient than shallow nets for structured function classes.
Core¶
Universal approximation¶
Let \(K\subset\mathbb{R}^d\) be compact, \(\sigma:\mathbb{R}\to\mathbb{R}\) a fixed activation. The shallow network class with \(m\) hidden units is
Theorem (Cybenko 1989, sigmoidal \(\sigma\); Hornik 1991, general). If \(\sigma\) is continuous, non-polynomial, and discriminatory (Cybenko: sigmoidal, i.e. \(\sigma(t)\to 1\) as \(t\to+\infty\) and \(\to 0\) as \(t\to-\infty\); Hornik: any non-polynomial continuous \(\sigma\)), then \(\bigcup_m\mathcal{NN}_m^{\mathrm{shallow}}\) is dense in \(C(K)\) in the uniform norm. Equivalently, for every \(f\in C(K)\) and \(\varepsilon>0\) there exist \(m\in\mathbb{N}\), weights \(\{(w_i,b_i,c_i)\}_{i=1}^m\) with \(\sum_i c_i\sigma(w_i\cdot x+b_i)\) within \(\varepsilon\) of \(f\) uniformly.
The proof is a Hahn–Banach / Riesz-representation argument: if the closure were proper, a signed measure \(\mu\) annihilating all \(\sigma(w\cdot x+b)\) exists, and the non-polynomial / discriminatory hypothesis forces the Fourier transform of \(\mu\) to vanish, hence \(\mu=0\) — contradiction. The theorem is purely qualitative: it gives no bound on \(m\) as a function of \(\varepsilon\) and \(f\), and no role for depth. The depth/rate content is the post-Cybenko theory.
Barron's theorem and the Barron space¶
Barron (1993) introduced a variation-norm condition that yields a dimension-free approximation rate. Define the Barron norm of \(f\) on \(K=[-1,1]^d\) (or a convex body) by the Fourier representation
the infimum over Fourier representations of \(f\) of the first-moment of the spectral measure. Equivalently (Barron's original form), \(f\) admits a representation \(f(x)=\int \sigma(w\cdot x+b)\,d\mu(w,b)\) for a signed measure \(\mu\) with \(\int|w|\,d|\mu|<\infty\) (after absorbing the bias into the measure). The Barron space \(\mathcal{B}=\{f:\|f\|_{\mathcal{B}}<\infty\}\) is a Banach space (a variation-norm space containing \(C^1\) functions with bounded \(\int\|\nabla f\|\) and the \(C^s\) functions for \(s\ge\lceil d/2\rceil\) via Sobolev embedding of the Fourier first moment).
Theorem (Barron 1993). For \(f\in\mathcal{B}\) with \(\|f\|_{\mathcal{B}}\le C\), and any \(m\ge 1\), there exists a shallow net \(\hat f_m=\sum_{i=1}^m c_i\sigma(w_i\cdot x+b_i)\) with $$ |\hat f_m - f|_{L^2(K)}\;\le\;\frac{2C}{\sqrt{m}}. $$ The rate \(O(1/\sqrt{m})\) is independent of dimension \(d\), and the weights \((w_i,b_i,c_i)\) are obtained by sampling from the Barron-representing measure. The rate is optimal up to constants for Monte-Carlo approximation of the integral.
The proof: \(f(x)=\int\sigma(w\cdot x+b)\,d\mu(w,b)\) with total variation \(\le C\); approximate the integral by \(m\) i.i.d. samples from \(|\mu|/C\) and the empirical average. The dimension-free character comes from the Monte-Carlo \(1/\sqrt{m}\) rate of integrating a fixed-amplitude function in any dimension — the curse of dimensionality is beaten because the Barron norm controls the variation, not the ambient dimension.
| Function class | Shallow NN approximation rate (width \(m\)) | Dimension dependence |
|---|---|---|
| \(C(K)\), general \(f\) | no rate (Cybenko qualitative; can be arbitrarily slow) | curse (no rate) |
| \(C^s([0,1]^d)\), \(s\) smooth | \(O(m^{-s/d})\) (curse of dim.) | \(d\) in exponent |
| \(W^{s,p}([0,1]^d)\) | \(O(m^{-s/d})\) (curse) | \(d\) in exponent |
| Barron \(\mathcal{B}\) (\(\|f\|_{\mathcal{B}}<\infty\)) | \(O(m^{-1/2})\) | none (dimension-free) |
| Barron\(^s\) (tensor Barron) | \(O(m^{-s/(2s+d)})\) for tensor \(C^s\) | improved |
| Compositional / tree-structured | \(O(m^{-s/\sum k_i})\) (curse in sum of local dims) | beaten if compositional |
| Holomorphic on a Bernstein ellipse | \(O(\rho^{-m})\) exponential | \(d\) only via the ellipse |
Depth separation: deep vs shallow¶
Theorem (Eldan–Shamir 2016). There exists a function \(f:\mathbb{R}^d\to\mathbb{R}\) (a radial "bump" / smoothed indicator of a ball) computable by a depth-\(3\) ReLU network of polynomial size that cannot be approximated to error \(\varepsilon\) by any depth-\(2\) (shallow) net of width less than \(\exp(c\sqrt{d}\,\varepsilon^{-2})\).
Theorem (Telgarsky 2016, sawtooth). Let \(g_k\) be the sawtooth function on \([0,1]\) obtained by iterating the tent map \(k\) times (i.e. \(g_k=T^k\), \(T(x)=2\min(x,1-x)\), \(g_k\) has \(2^k\) oscillations). Then \(g_k\) is computed exactly by a depth-\(k\) ReLU net of width \(O(1)\) (each layer folds), but any depth-\(2\) net approximating \(g_k\) to \(L^\infty\) error \(\varepsilon=O(2^{-k})\) requires width \(\Omega(2^k)\). Depth-\(k\) size \(O(k)\) vs depth-\(2\) size \(\Omega(2^k)\) — exponential separation.
Theorem (Yarotsky 2017). For \(f\in W^{s,\infty}([0,1]^d)\), there exists a deep ReLU net of depth \(O(s)\) and width / total params \(O(\varepsilon^{-d/s}\log(1/\varepsilon))\) approximating \(f\) to \(L^\infty\) error \(\varepsilon\) — recovering the classical \(C^s\) approximation rate \(\varepsilon^{-d/s}\) (curse of dimensionality) with deep nets. For compositional / tree-structured \(f=\phi\circ\cdots\circ\phi\) with \(k_i\)-dim inputs at each node (Poggio–Mhaskar–Rosasco–Magguli), the rate improves to \(O(\varepsilon^{-s/\sum k_i})\) — the curse is replaced by the sum of local dimensions, a dimension-free rate when the composition has bounded local arity.
The depth-separation theorems together establish that depth is not a notational convenience: there are concrete functions (sawtooth, radial bump, compositional) for which a depth-\(L\) net of polynomial size requires depth-\(2\) nets of exponential size to match. The structural hypothesis (Barron norm, composition, smoothness) is what makes the dimension-free or improved rates possible; without it the curse of dimensionality persists (see Information-Theoretic Limits).
See it¶
Barron norm of \(f(x)=\|x\|^2\) on \([0,1]^d\), and the dimension-free approximation. Compute \(\|f\|_{\mathcal{B}}\) for \(f(x)=\|x\|^2=\sum_j x_j^2\). The Fourier representation: \(x_j^2\) has Fourier transform (in distribution sense) \(\widehat{x_j^2}(\omega)=-\delta''(\omega_j)\prod_{k\ne j}\delta(\omega_k)\cdot 2\pi\), and summing gives a spectral measure supported on the axes with \(\|\omega\|\)-first-moment bounded by the integral of the second-derivative mass. Concretely, \(f(x)=\|x\|^2\) admits the Barron representation \(f(x)=\int_0^1 (x\cdot u - t)_+\,d\mu(u,t)\) via the identity \(\|x\|^2=\int_{S^{d-1}}(x\cdot u)_+\,d\nu(u)-c\) with \(\nu\) the uniform measure on \(S^{d-1}\) scaled appropriately (the distributional identity \(\|x\|^2=c_d\int_{S^{d-1}}(x\cdot u)_+\,du\) for a constant \(c_d=O(1)\)). The Barron norm is \(\|f\|_{\mathcal{B}}=c_d\int_{S^{d-1}}|u|\,du=O(1)\) — bounded independently of \(d\). Hence by Barron's theorem, \(\|x\|^2\) is approximated by a shallow ReLU net of width \(m\) to \(L^2\) error \(O(1/\sqrt{m})\) in any dimension — the dimension-free rate is realized. This is the prototypical "Barron beats the curse" computation: a quadratic function (which has Barron norm \(O(1)\)) is approximated at the Monte-Carlo rate regardless of \(d\), whereas a general \(C^2\) function on \([0,1]^d\) would require \(m=O(\varepsilon^{-d/2})\) width (curse) without the Barron structural assumption.
Telgarsky sawtooth depth separation. Let \(T(x)=2\min(x,1-x)\) be the tent map on \([0,1]\). \(T\) is computed by a width-\(1\) ReLU layer (two ReLUs: \(T(x)=2\sigma(x)-4\sigma(x-1/2)+2\sigma(x-1)\)). The \(k\)-th iterate \(g_k=T^{\circ k}\) is computed by a depth-\(k\) net of width \(O(1)\) (each layer composes \(T\), with \(O(1)\) ReLUs per layer), total size \(O(k)\). But \(g_k\) has \(2^k\) linear pieces, so approximating it to error \(\varepsilon\le 2^{-k}/10\) in \(L^\infty\) requires a depth-\(2\) net to place a "break" near each peak — at least \(\Omega(2^k)\) ReLUs (a depth-\(2\) net with \(m\) units produces a piecewise-linear function with at most \(m+1\) pieces). Hence depth-\(k\) size \(O(k)\) vs depth-\(2\) size \(\Omega(2^k)\) — exponential separation by depth. This is the canonical "deep is exponentially more efficient than shallow" example.
Check¶
Why does the Cybenko/Hornik universal approximation theorem give no approximation rate, and identify the precise obstruction that prevents extracting one from the proof.
The proof is by contradiction via Hahn–Banach: assume \(\overline{\bigcup_m\mathcal{NN}_m}\) is a proper closed subspace of \(C(K)\), then there is a non-zero signed measure \(\mu\) annihilating it; the non-polynomial / discriminatory hypothesis forces the Fourier transform \(\hat\mu\) to vanish on a dense set, hence \(\mu=0\), contradiction. The argument proves density (existence of some net within \(\varepsilon\)) but produces no constructive \(m(\varepsilon,f)\) — the proof gives no control on the number of neurons, because the contradiction is qualitative (the measure vanishes, hence the function is in the closure, but no rate of the approximation in terms of \(m\) is extracted). Extracting a rate requires a quantitative hypothesis on \(f\) (Barron norm, smoothness, compositional structure) — the Cybenko theorem alone, with \(f\in C(K)\) only, can be arbitrarily slow (a standard fact: density without rate, as in the Weierstrass theorem without the Jackson/Bernstein rates). The obstruction is that the annihilating-measure argument is non-quantitative: it shows \(\mu=0\) but not how small a finite combination is needed.
Verify the Barron norm computation for \(f(x)=\|x\|^2\) is dimension-independent, and explain why this does not contradict the curse of dimensionality for general \(C^2\) functions.
The identity \(\|x\|^2=c_d\int_{S^{d-1}}(x\cdot u)_+\,du\) (with \(c_d=O(1)\)) gives a Barron representation with total variation \(c_d\int_{S^{d-1}}1\,du=c_d\,|S^{d-1}|=O(1)\) independent of \(d\) up to the \(c_d\) normalization (one checks \(c_d\) is \(O(1)\) from the surface measure / stereographic identity). Hence \(\|f\|_{\mathcal{B}}=O(1)\) and Barron's \(O(1/\sqrt{m})\) rate applies dimension-free. This does not contradict the curse for general \(C^2\) because \(\|x\|^2\) is a special \(C^2\) function with bounded Barron norm — a generic \(C^2\) function \(g\) on \([0,1]^d\) has Barron norm \(\|g\|_{\mathcal{B}}=O(d)\) or worse (the first Fourier moment of a generic \(C^2\) function grows with \(d\) via Sobolev embedding), and the dimension-free rate for \(\|x\|^2\) reflects that its Fourier mass concentrates on a sphere of radius \(O(1)\) — a structural property most \(C^2\) functions lack. The Barron class is a strict, dimension-controlled subspace of \(C^2\), not all of \(C^2\).
Pitfalls¶
- Universal approximation is qualitative: Cybenko/Hornik give no rate and no role for depth; treating it as the "explanation" of NN expressivity is the standard popular error.
- Barron's \(O(1/\sqrt{m})\) needs the Barron-norm hypothesis: the rate applies to \(\|f\|_{\mathcal{B}}<\infty\) only; a generic \(C^s\) function is not Barron (the Barron class is a variation-norm subspace, strict in \(C^s\) for \(s\) fixed and \(d\) large). Using Barron's rate without verifying the hypothesis overstates the result.
- Depth separation requires specific functions: the Eldan–Shamir / Telgarsky / Yarotsky separations are for specific constructed functions (bump, sawtooth, compositional); they do not say "deep is always exponentially better than shallow" — for Barron / smooth functions the depth advantage may be polynomial or absent.
- Yarotsky's \(C^s\) rate recovers the curse: deep ReLU gives \(\varepsilon^{-d/s}\) for \(C^s\), the same rate as classical splines / wavelets; the improvement is only for compositional / structured \(f\), where the exponent \(\sum k_i\) replaces \(d\).
- Compositional structure is a hypothesis, not a theorem: the Poggio et al. dimension-free rate for tree-structured functions requires the tree to be known / matched to the architecture; a generic function does not decompose.
Refs¶
- Cybenko, Approximation by superpositions of a sigmoidal function (Math. Control Signals 1989)
- Hornik, Approximation capabilities of multilayer feedforward networks (Neural Networks 1991)
- Barron, Universal approximation bounds for superpositions of a sigmoidal function (IEEE TIT 1993)
- Eldan–Shamir, The power of depth for feedforward neural networks (COLT 2016); Telgarsky, Benefits of depth in neural networks (COLT 2016)
- Yarotsky, Error bounds for approximating deep neural networks (2017); Poggio–Mhaskar–Rosasco–Magguli, Theory of deep learning III (2017)
Next¶
NTK & Optimization · Generalization · Information-Theoretic Limits · ML Mathematics index · Numerical analysis · Functional analysis · Fourier analysis · Optimization