Approximation Theory and Backpropagation

Universal approximation with its exact hypotheses, why it says nothing about learnability, and backpropagation as reverse-mode differentiation on a computational graph.

Deep LearningAdvanced⏱ 3 hours10 min readuniversal approximationmlpbackpropagationautodiffcomputational graph

5 problems →

AssumesMultivariable and Matrix Calculus · Logistic Regression

From the perceptron to a hidden layer

PropositionA single threshold unit cannot represent XOR

There is no $(w,b)\in\R^2\times\R$ with $\sign(\ip w{x}+b)$ equal to $x_1\oplus x_2$ on $\{0,1\}^2$ .

This is the observation that halted the first wave of neural network research, and the fix — compose two layers — is what the next theorem generalises.

Universal approximation

TheoremUniversal approximation theorem

Let $\rho:\R\to\R$ be continuous and not a polynomial. Then for every compact $K\subseteq\R^d$ , every continuous $f:K\to\R$ and every $\eps>0$ , there exist $m\in\N$ , $w_j\in\R^d$ , $b_j\in\R$ and $c_j\in\R$ with

\sup_{x\in K}\left|f(x) - \sum_{j=1}^m c_j\,\rho\big(\ip{w_j}{x}+b_j\big)\right| < \eps .

Quoted from Leshno et al., which gives the sharp hypothesis; Cybenko and Hornik proved earlier versions for sigmoidal and for bounded non-constant activations. The proof is a functional-analysis argument (the set of such sums is a subalgebra-like family whose closure is shown to be all of $C(K)$ , via Stone–Weierstrass or via a Hahn–Banach separation and a Fourier/Radon-transform computation).

PropositionWhat universal approximation does not give

The theorem is a statement about the closure of a set of functions. It provides:

no bound on $m$ — the width may need to grow exponentially in $d$ or in $1/\eps$ ;
no algorithm for finding the parameters;
no statement about generalisation from finite data;
no distinction between activations, architectures or depths.

TheoremDepth separation

There is a function $g:\R^d\to\R$ , expressible exactly by a network with three layers and $O(\mathrm{poly}(d))$ units, such that any two-layer network approximating $g$ to constant accuracy in $L^2$ over a natural measure requires $e^{\Omega(d)}$ units.

Quoted from Eldan and Shamir; Telgarsky gives a complementary one-dimensional construction separating depth $k$ from depth $O(k^{1/3})$ using a sawtooth function whose oscillation count grows exponentially with depth. These are the strongest rigorous statements available about the value of depth, and it is worth being clear about their scope: they show depth can buy exponential efficiency on specially constructed functions. They do not show that the functions arising in practice have this character.

Backpropagation

Represent the network as a computational graph: nodes are intermediate values, edges are elementary operations. For a feedforward net,

a^{(0)} = x, \qquad z^{(\ell)} = W^{(\ell)}a^{(\ell-1)}+b^{(\ell)}, \qquad a^{(\ell)} = \rho\big(z^{(\ell)}\big), \qquad \ell = 1,\dots,L,

with scalar loss $\mathcal{J} = \ell\big(a^{(L)},y\big)$ .

TheoremBackpropagation computes the exact gradient

Define the adjoints $\delta^{(\ell)} = \partial\mathcal{J}/\partial z^{(\ell)}$ . Then

\delta^{(L)} = \nabla_{a^{(L)}}\ell \odot \rho'\big(z^{(L)}\big), \qquad \delta^{(\ell)} = \Big(\big(W^{(\ell+1)}\big)^\top\delta^{(\ell+1)}\Big)\odot\rho'\big(z^{(\ell)}\big),

and

\frac{\partial\mathcal{J}}{\partial W^{(\ell)}} = \delta^{(\ell)}\big(a^{(\ell-1)}\big)^\top, \qquad \frac{\partial\mathcal{J}}{\partial b^{(\ell)}} = \delta^{(\ell)} .

These are exact derivatives (no finite differences), computed in time $O(\text{forward pass})$ and memory $O(\sum_\ell\dim a^{(\ell)})$ .

Key idea

Backpropagation is not an algorithm specific to neural networks and it is not an approximation. It is reverse-mode automatic differentiation applied to a particular graph, and the reason it is cheap is the one on the matrix calculus page: many inputs, one output, so accumulate the Jacobian product from the left. The "many parameters, one loss" shape of deep learning is what makes it affordable, and the memory cost of storing activations is the price.

PropositionGradient magnitude through a deep chain

With $J^{(\ell)} = \diag(\rho'(z^{(\ell)}))\big(W^{(\ell)}\big)^\top$ , the input-layer adjoint is

\delta^{(1)} = J^{(1)}J^{(2)}\cdots J^{(L-1)}\,\delta^{(L)},

\norm{\delta^{(1)}}_2 \le \left(\prod_{\ell=1}^{L-1}\norm{J^{(\ell)}}\right)\norm{\delta^{(L)}}_2,

and generically $\norm{\delta^{(1)}}_2 \approx c^{L}$ for $c$ the typical singular value. The gradient is therefore exponential in depth, vanishing for $c<1$ and exploding for $c>1$ .

Why this proposition explains four architectural choices

Everything in modern deep learning that looks like a trick is an attempt to keep $\prod_\ell\norm{J^{(\ell)}}$ near $1$ :

Careful initialisation (He, Glorot) sets $\Var(W_{ij}) = 2/n_{\text{in}}$ so that $\E\norm{J^{(\ell)}}\approx1$ at the start of training.
Residual connections replace $J^{(\ell)}$ with $I + \tilde J^{(\ell)}$ , whose product stays near $I$ when the $\tilde J$ are small — this is the mathematical content of ResNet.
Normalisation layers rescale $z^{(\ell)}$ so that $\rho'$ operates in its non-saturated range, keeping $\diag(\rho'(z))$ away from zero.
Gating in LSTMs and GRUs creates paths where the effective Jacobian is exactly $I$ , which is the subject of the recurrence page.

None of these is a heuristic in need of an explanation; each targets this specific product.

Problems

XOR is not linearly separableProof · Foundation · 15 min Derive the backpropagation recursionProof · Intermediate · 30 min Width needed to represent a piecewise linear functionProof · Advanced · 1 hour Gradient magnitude through a deep chainProof · Intermediate · 30 min Implement backpropagation from scratchCoding · Intermediate · 3 hours

References

PaperGeorge Cybenko (1989). Approximation by superpositions of a sigmoidal function
PaperKurt Hornik (1991). Approximation capabilities of multilayer feedforward networks
PaperMoshe Leshno, Vladimir Ya. Lin, Allan Pinkus and Shimon Schocken (1993). Multilayer feedforward networks with a nonpolynomial activation function can approximate any function
PaperMatus Telgarsky (2016). Benefits of depth in neural networks
PaperRonen Eldan and Ohad Shamir (2016). The Power of Depth for Feedforward Neural Networks
PaperDavid E. Rumelhart, Geoffrey E. Hinton and Ronald J. Williams (1986). Learning representations by back-propagating errors
BookIan Goodfellow, Yoshua Bengio and Aaron Courville (2016). Deep Learning

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionA single linear threshold unit cannot represent XORproof includedThe classic separability obstruction, and the exact reason a hidden layer is needed.
TheoremUniversal approximation theoremOne hidden layer with a non-polynomial activation approximates any continuous function on a compact set uniformly.
PropositionWhat universal approximation does not giveproof includedIt is a density statement with no bound on width, no learning algorithm and no sample complexity.
TheoremDepth separationThere are functions expressible by a small three-layer network that require exponential width at two layers.
TheoremBackpropagation computes the exact gradientproof includedReverse accumulation on a computational graph returns the exact derivative, not an approximation, in time proportional to the forward pass.
PropositionGradient magnitude through a deep chainproof includedThe gradient is a product of layer Jacobians, so its norm is governed by a product of singular values and is generically exponential in depth.

Problems (5)

All problems