45.08.10 · mathematical-statistics / 08-learning-methods

Neural Networks: The Multilayer Perceptron and Backpropagation

shipped3 tiersLean: none

Anchor (Master): Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) Ch. 11 (the full statistical treatment, regularization, the bias-variance behaviour); Goodfellow, Bengio & Courville 2016 Deep Learning (MIT Press) Ch. 6 and Ch. 8 (back-propagation and optimization for training); Cybenko 1989 Approximation by superpositions of a sigmoidal function (Math. Control Signals Systems 2) and Hornik 1991 Approximation capabilities of multilayer feedforward networks (Neural Networks 4) for universal approximation

Intuition Beginner

Logistic regression draws a single straight boundary through your data. That is fine when the labels really do separate along a line, but most real patterns bend. A neural network is the simplest honest way to let the boundary bend as much as the data demand: instead of feeding the raw measurements straight into a logistic model, you first pass them through a layer of simple bending units, and only then run the logistic step on what those units report.

Each bending unit does two things. It forms a weighted blend of the measurements — a slope in some direction through the data — and then it squashes that blend through an S-shaped curve, so the unit switches gently from "off" to "on" as you cross its own little boundary. A layer of many such units, each watching a different direction, turns the raw inputs into a richer set of features: "is this point on the high side of unit 3?", "how strongly does unit 7 fire?" The final layer then does ordinary logistic-style classification on those learned features rather than on the raw inputs.

The trick that makes this practical is training: there is a fast, exact way to figure out how to nudge every weight in every layer at once so the network's mistakes shrink. That method is called backpropagation, and it is the engine behind almost everything labelled "deep learning."

Visual Beginner

A network is layers of units, wired left to right. Inputs enter on the left; each later unit blends the values from the layer before it, squashes the blend, and passes it on. The last layer reports the prediction.

Layer	What each unit does	What comes out
Input	nothing; just holds a measurement	the raw numbers $x_{1}, x_{2}, \dots$
Hidden	blend the inputs, then squash through an S-curve	"learned features" — bent versions of the data
Output	run a logistic / linear step on the hidden features	the prediction (a probability or a number)

The picture to keep: the hidden layer invents useful features by bending the inputs, and the output layer is just the linear-or-logistic model you already know, sitting on top of those invented features. Forward arrows make a prediction; the dashed backward arrows carry the error back to teach every weight.

Worked example Beginner

Take the smallest pattern that defeats a straight line: the "exclusive-or." Two inputs, each $0$ or $1$ . The label is $1$ when the inputs differ and $0$ when they match. So $(0, 1)$ and $(1, 0)$ are label $1$ ; $(0, 0)$ and $(1, 1)$ are label $0$ . No single straight line can separate these four points — that is the whole point of the example.

Now add two hidden units. Let unit A fire when "at least one input is on," and unit B fire when "both inputs are on." For each of the four cases:

$(0, 0)$ : A is off, B is off.
$(0, 1)$ : A is on, B is off.
$(1, 0)$ : A is on, B is off.
$(1, 1)$ : A is on, B is on.

The label we want is $1$ exactly when "A is on but B is off." That is a simple rule on the two hidden features: fire the output when A minus B is positive. The output unit can do this with a plain weighted sum — A counts $+ 1$ , B counts $- 2$ , and we keep the result when it lands above zero.

What this tells us: the raw inputs were not linearly separable, but the hidden features A and B are. The hidden layer rebuilt the problem into one the simple output layer can finish. That is the entire idea of a neural network in miniature — learn features that make the last, easy step possible.

Check your understanding Beginner

Formal definition Intermediate+

Fix an input space $R^{p}$ and an output dimension $K$ . An $L$ -layer multilayer perceptron (MLP) is the parameterised map $f_{θ} : R^{p} \to R^{K}$ built by composing affine maps with a fixed coordinatewise nonlinearity $σ : R \to R$ . Write $a^{(0)} = x$ for the input. For layers $l = 1, \dots, L$ ,

z^{(l)} = W^{(l)} a^{(l - 1)} + b^{(l)}, a^{(l)} = σ (z^{(l)}) (l < L), a^{(L)} = g (z^{(L)}),

where $W^{(l)} \in R^{d_{l} \times d_{l - 1}}$ are the weights, $b^{(l)} \in R^{d_{l}}$ the biases, $z^{(l)}$ the pre-activations, $a^{(l)}$ the activations (the derived features of the hidden layers), and $g$ the output transform. The collected parameter vector is $θ = (W^{(1)}, b^{(1)}, \dots, W^{(L)}, b^{(L)})$ . Common hidden nonlinearities are the logistic $σ (t) = 1/ (1 + e^{- t})$ , the hyperbolic tangent $tanh (t)$ , and the rectified linear unit $ReLU (t) = max (t, 0)$ . The output transform $g$ is the identity for real-valued regression and the softmax $g (z)_{k} = e^{z_{k}} / \sum_{ℓ} e^{z_{ℓ}}$ for $K$ -class classification.

The defining structural fact is that the last layer is an ordinary linear (regression) or multinomial-logistic (classification) model fitted not to $x$ but to the learned features $a^{(L - 1)}$ . Setting $Z = a^{(L - 1)}$ , the output is $a^{(L)} = g (W^{(L)} Z + b^{(L)})$ , which is exactly the logistic / softmax form of 45.08.03 with $Z$ in place of the raw design. An MLP is therefore adaptive basis-function regression: it learns the basis $x \mapsto Z (x)$ rather than fixing it in advance, and runs a generalized linear model on top.

Training objective. Given i.i.d. data $(x_{i}, y_{i})_{i = 1}^{n}$ and a per-example loss $ℓ$ , the empirical risk is

R (θ) = \frac{1}{n} i = 1 \sum n ℓ (y_{i}, f_{θ} (x_{i})) .

For regression $ℓ$ is squared error $\frac{1}{2} ∥ y - f_{θ} (x) ∥^{2}$ ; for classification $ℓ$ is the cross-entropy $- \sum_{k} y_{k} lo g f_{θ} (x)_{k}$ , the negative log-likelihood of the softmax model, generalizing the logistic deviance of 45.08.03. Training minimises $R (θ)$ (optionally with a penalty) by gradient methods; the gradient $\nabla_{θ} R$ is computed by backpropagation.

Counterexamples to common slips

A network with no nonlinearity is not deep. If $σ$ is the identity, the composition $W^{(L)} \dots W^{(1)} x + (const)$ collapses to a single affine map: no number of linear layers exceeds the expressive power of one. The nonlinearity is what makes depth buy anything.
Backpropagation is not the optimizer. Backpropagation computes the gradient $\nabla_{θ} R$ ; it does not decide the step. The update — gradient descent, stochastic gradient descent 44.06.05, or a quasi-Newton method — is a separate component that consumes the gradient.
Universal approximation is not a learning guarantee. The approximation theorem says a network exists that fits any continuous target; it says nothing about whether gradient descent on finite noisy data will find it, nor how many units the fit needs.
More parameters than data need not overfit catastrophically. Classical intuition predicts disaster when the parameter count exceeds $n$ , but heavily overparameterized networks trained to interpolation often generalize well — the double-descent phenomenon of 45.06.02, which the classical bias-variance curve does not capture.

Key theorem with proof Intermediate+

The signature computational result is that the gradient of the empirical risk with respect to every weight in every layer is obtained by one forward pass and one backward pass through the network, at a cost a fixed multiple of one forward evaluation, independent of the number of parameters. This is backpropagation: the chain rule organised as a reverse-mode sweep over the layered computational graph, the special case of the reverse-mode automatic differentiation of 44.03.08 applied to a scalar loss. The result follows Hastie, Tibshirani & Friedman ^{[Hastie 2009]} §11.4 and Goodfellow, Bengio & Courville ^{[Goodfellow 2016]} §6.5.

Theorem (the backpropagation recursion). Consider a single example $(x, y)$ with loss $J (θ) = ℓ (y, a^{(L)})$ , activations $a^{(l)} = σ (z^{(l)})$ for $l < L$ , output $a^{(L)} = g (z^{(L)})$ , and $z^{(l)} = W^{(l)} a^{(l - 1)} + b^{(l)}$ . Define the layer error (adjoint) $δ^{(l)} = \partial J / \partial z^{(l)} \in R^{d_{l}}$ . Then

δ^{(L)} = \nabla_{a^{(L)}} ℓ ⊙ g^{'} (z^{(L)}), δ^{(l)} = ((W^{(l + 1)})^{⊤} δ^{(l + 1)}) ⊙ σ^{'} (z^{(l)}) (l < L),

where $⊙$ is the coordinatewise (Hadamard) product, and the parameter gradients are

\frac{\partial J}{\partial W ^{(l)}} = δ^{(l)} (a^{(l - 1)})^{⊤}, \frac{\partial J}{\partial b ^{(l)}} = δ^{(l)} .

Proof. Write $J$ as a function of the pre-activations through the composition $z^{(l)} \mapsto a^{(l)} \mapsto z^{(l + 1)} \mapsto \dots \mapsto J$ . The chain rule gives, for the output layer, $δ_{j}^{(L)} = \partial J / \partial z_{j}^{(L)} = \sum_{k} (\partial ℓ / \partial a_{k}^{(L)}) (\partial a_{k}^{(L)} / \partial z_{j}^{(L)})$ . When $g$ acts coordinatewise, $\partial a_{k}^{(L)} / \partial z_{j}^{(L)} = g^{'} (z_{j}^{(L)}) [k = j]$ , so $δ^{(L)} = \nabla_{a^{(L)}} ℓ ⊙ g^{'} (z^{(L)})$ . (For the softmax with cross-entropy the same chain rule collapses to the clean form $δ^{(L)} = a^{(L)} - y$ , derived in the Full proof set.)

For a hidden layer $l < L$ , the pre-activation $z^{(l)}$ influences $J$ only through the next pre-activation $z^{(l + 1)} = W^{(l + 1)} σ (z^{(l)}) + b^{(l + 1)}$ . Hence

δ_{j}^{(l)} = \frac{\partial J}{\partial z _{j}^{(l)}} = i \sum \frac{\partial J}{\partial z _{i}^{(l + 1)}} \frac{\partial z _{i}^{(l + 1)}}{\partial z _{j}^{(l)}} = i \sum δ_{i}^{(l + 1)} W_{ij}^{(l + 1)} σ^{'} (z_{j}^{(l)}),

since $\partial z_{i}^{(l + 1)} / \partial z_{j}^{(l)} = W_{ij}^{(l + 1)} σ^{'} (z_{j}^{(l)})$ . Collecting the index $j$ into a vector, the sum $\sum_{i} δ_{i}^{(l + 1)} W_{ij}^{(l + 1)}$ is the $j$ -th entry of $(W^{(l + 1)})^{⊤} δ^{(l + 1)}$ , and the factor $σ^{'} (z_{j}^{(l)})$ multiplies coordinatewise, giving $δ^{(l)} = ((W^{(l + 1)})^{⊤} δ^{(l + 1)}) ⊙ σ^{'} (z^{(l)})$ .

Finally, $z_{j}^{(l)} = \sum_{m} W_{j m}^{(l)} a_{m}^{(l - 1)} + b_{j}^{(l)}$ depends on $W_{j m}^{(l)}$ only through that single term, so $\partial J / \partial W_{j m}^{(l)} = δ_{j}^{(l)} a_{m}^{(l - 1)}$ , i.e. the outer product $δ^{(l)} (a^{(l - 1)})^{⊤}$ , and $\partial J / \partial b_{j}^{(l)} = δ_{j}^{(l)}$ . $□$

Bridge. The proof's engine is that each pre-activation feeds the loss through exactly one downstream layer, so the multivariate chain rule factors into the layerwise recursion $δ^{(l)} = ((W^{(l + 1)})^{⊤} δ^{(l + 1)}) ⊙ σ^{'} (z^{(l)})$ : the adjoint flows backward exactly as the activations flowed forward, the transpose $(W^{(l + 1)})^{⊤}$ playing the role the forward weight $W^{(l + 1)}$ played going in. This is exactly the reverse-mode adjoint pass of 44.03.08 specialised to the layered graph, which is the foundational reason the whole gradient costs one forward plus one backward sweep rather than a separate evaluation per parameter — the cheap-gradient principle wearing neural-network clothing. Each per-layer parameter gradient is the rank-one outer product $δ^{(l)} (a^{(l - 1)})^{⊤}$ , so the forward activations stored on the way in are precisely the data the backward pass consumes, which generalises the storage-versus-recomputation tradeoff of that unit. The recursion builds toward the optimization layer: backpropagation supplies the gradient that stochastic gradient descent 44.06.05 consumes, and putting these together, the central insight is that an MLP is trained by alternating a forward prediction sweep with a backward error sweep, each adjusting weights in proportion to how much they contributed to the mistake. It appears again at the output layer, where the recursion bottoms out in the softmax-cross-entropy residual $a^{(L)} - y$ , the same error term that drove the logistic fit of 45.08.03.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Show that weight decay — adding $\frac{λ}{2} ∥ θ ∥^{2}$ to the risk — changes each gradient by $λ θ$ , and explain why this is the ridge penalty of regression applied to the network weights.

Hint

Differentiate the penalty $\frac{λ}{2} \sum_{l} ∥ W^{(l)} ∥_{F}^{2}$ with respect to a single weight.

Answer

The penalised objective is $R_{λ} (θ) = R (θ) + \frac{λ}{2} ∥ θ ∥^{2}$ . For any weight entry $w$ , $\partial (\frac{λ}{2} w^{2}) / \partial w = λ w$ , so $\nabla R_{λ} = \nabla R + λ θ$ and each gradient-descent step becomes $θ \leftarrow θ - η (\nabla R + λ θ) = (1 - η λ) θ - η \nabla R$ : the weights are shrunk toward zero by the factor $(1 - η λ)$ at every step, hence the name "decay." This is exactly the $ℓ_{2}$ / ridge penalty of regularized regression 45.06.03 transplanted onto the network weights; it trades a controlled bias for reduced variance.

Exercise 6 (hard, symbolic).

A deep network with logistic activations can suffer vanishing gradients. Using the recursion $δ^{(l)} = ((W^{(l + 1)})^{⊤} δ^{(l + 1)}) ⊙ σ^{'} (z^{(l)})$ and $∣ σ^{'} ∣ \leq 1/4$ , bound $∥ δ^{(l)} ∥$ in terms of $∥ δ^{(L)} ∥$ and the spectral norms $∥ W^{(k)} ∥_{2}$ , and explain why ReLU mitigates the problem.

Hint

The logistic derivative attains its maximum $1/4$ at the origin; chain the bound across $L - l$ layers.

Answer

Taking norms, $∥ δ^{(l)} ∥ \leq ∥ W^{(l + 1)} ∥_{2} ∥ σ^{'} (z^{(l)}) ∥_{\infty} ∥ δ^{(l + 1)} ∥ \leq \frac{1}{4} ∥ W^{(l + 1)} ∥_{2} ∥ δ^{(l + 1)} ∥$ , since $max_{t} σ^{'} (t) = σ (0) (1 - σ (0)) = 1/4$ . Iterating from layer $L$ down to $l$ , $∥ δ^{(l)} ∥ \leq (1/4)^{L - l} (\prod_{k = l + 1}^{L} ∥ W^{(k)} ∥_{2}) ∥ δ^{(L)} ∥$ . If the weight norms are near or below $1$ , the factor $(1/4)^{L - l}$ drives the early-layer gradients to zero exponentially in depth, so the first layers learn slowly. ReLU has derivative $1$ on its active region (and $0$ otherwise), so it does not contribute a contractive $1/4$ factor at each layer; the gradient can pass through active units undamped, which is the principal reason ReLU enabled training of much deeper networks.

Exercise 7 (hard, short-answer).

State the universal approximation theorem precisely for single-hidden-layer networks, and explain why it does not by itself justify deep learning's success. Name two things it leaves unexplained.

Hint

The theorem is an existence statement about density in $C (K)$ ; think about width, optimization, and generalization.

Answer

The theorem (Cybenko 1989; Hornik 1991): for a continuous nonconstant bounded activation $σ$ and a compact $K \subset R^{p}$ , the set of finite sums $\sum_{j = 1}^{N} c_{j} σ (a_{j}^{⊤} x + b_{j})$ is dense in $C (K)$ under the uniform norm — any continuous target can be approximated to arbitrary accuracy by a sufficiently wide single-hidden-layer net. It leaves unexplained: (i) the width needed — approximating a generic function may require exponentially many units, so existence does not imply efficiency, and depth can be exponentially more parameter-efficient than width; (ii) trainability — the theorem says a good network exists but not that gradient descent on the non-convex risk from a random start will find it; and (iii) generalization — it concerns approximating a known function, not estimating one from finite noisy samples, so it is silent about overfitting and the bias-variance / double-descent behaviour. Full credit for the density statement plus any two of width, optimization, and generalization.

Lean formalization Intermediate+

Mathlib does not host the neural-network layer, so no module is wired in (lean_status: none). The intended statements — the MLP as a parameterised map, the universal-approximation density theorem, and the correctness of the backprop recursion against fderiv — would read roughly as follows.

-- Intended shape; not part of the current Babel Bible Lean build.
-- Requires: a layered map, the activation σ with its derivative, and the
-- adjoint recursion verified against Mathlib's `fderiv`.
variable {p K : ℕ} (σ : ℝ → ℝ)

-- a single affine-plus-activation layer
def layer (W : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (a : Fin n → ℝ) :
    Fin m → ℝ := fun i => σ ((W i) ⬝ᵥ a + b i)

-- universal approximation (Cybenko/Hornik): finite single-hidden-layer sums
-- are dense in C(K, ℝ) for a discriminatory σ
theorem universal_approximation
    (hσ : Discriminatory σ) (K : Set (Fin p → ℝ)) (hK : IsCompact K) :
    DenseRange (fun (net : SingleHiddenLayer σ) => net.toContinuousMap K) := by
  sorry

-- backprop correctness: the layerwise adjoint recursion equals the gradient
theorem backprop_eq_fderiv (net : MLP σ) (x y : _) :
    backpropGrad net x y = fderiv ℝ (fun θ => loss (net.eval θ x) y) net.θ := by
  sorry

the Mathlib gap analysis records what is missing: a formal MLP model, the Discriminatory predicate and the Hahn-Banach / annihilating-measure proof of universal approximation, the empirical-risk objective, and the verified equivalence of the reverse-mode adjoint pass with fderiv.

Advanced results Master

The MLP is a flexible function estimator whose output layer is a generalized linear model on learned features; the results below place its expressive power, its training, and its statistical behaviour on a precise footing.

Theorem 1 (universal approximation). Let $σ : R \to R$ be continuous, bounded, and nonconstant, and let $K \subset R^{p}$ be compact. Then for every $h \in C (K)$ and every $ε > 0$ there exist $N \in N$ , weights $a_{j} \in R^{p}$ , biases $b_{j} \in R$ , and coefficients $c_{j} \in R$ with

h - j = 1 \sum N c_{j} σ (a_{j}^{⊤} \cdot + b_{j})_{\infty, K} < ε .

Cybenko ^{[Cybenko 1989]} proved this for continuous sigmoidal $σ$ by a Hahn-Banach argument: were the closed span $S$ of the functions $x \mapsto σ (a^{⊤} x + b)$ a proper subspace of $C (K)$ , the Riesz representation theorem would supply a nonzero signed measure $μ$ annihilating $S$ , i.e. $\int σ (a^{⊤} x + b) d μ = 0$ for all $a, b$ ; a discriminatory $σ$ (one no nonzero measure can annihilate) forbids this, forcing $S = C (K)$ . Hornik ^{[Hornik 1991]} removed the sigmoidal restriction to any bounded nonconstant $σ$ and extended the density to Sobolev norms (simultaneous approximation of derivatives). The theorem is an existence statement: it bounds neither the width $N$ nor the attainability of the approximant by training.

Theorem 2 (backpropagation as reverse-mode AD; the cheap-gradient bound). For an MLP of total computational cost $TIME (f_{θ})$ to evaluate, one forward pass storing the activations followed by one backward adjoint pass computes the full gradient $\nabla_{θ} R (θ)$ — every partial derivative with respect to every weight and bias — in time at most a fixed constant times $TIME (f_{θ})$ , independent of the parameter count $∣ θ ∣$ . This is the cheap-gradient principle of reverse-mode automatic differentiation 44.03.08 specialised to the layered graph: the adjoint $δ^{(l)}$ is propagated by the transpose recursion of the Key theorem, each elementary operation contributing to the backward sweep a constant multiple of the work it did forward. The memory cost is the storage of the forward activations, $O (\sum_{l} d_{l})$ per example, recoverable by checkpointing at the price of recomputation — the same time-memory tradeoff that governs reversal of any deep computation.

Theorem 3 (nonconvexity and the role of overparameterization). The empirical risk $R (θ)$ of a network with at least one hidden layer and a nonlinear $σ$ is generally non-convex in $θ$ , with many critical points: permuting hidden units and (for odd $σ$ ) flipping signs leave $f_{θ}$ unchanged, so every minimum sits in a large orbit of equivalent minima, and saddle points proliferate in high dimension. Gradient descent nonetheless trains such networks reliably in practice, and the modern explanation is overparameterization: when $∣ θ ∣ ≫ n$ , the loss landscape near initialization is benign — in the wide-network (neural-tangent-kernel) limit the dynamics linearise and gradient descent converges to a global interpolator — and the many parameters provide many descent directions, so first-order methods escape saddles and reach near-zero training loss. Overparameterization trades a worse-conditioned but more navigable landscape for the convexity it forgoes.

Theorem 4 (regularization and the double-descent picture). Three regularizers control the variance of the overparameterized fit. Weight decay adds $\frac{λ}{2} ∥ θ ∥^{2}$ , the ridge penalty of 45.06.03 applied to the weights, equivalent to a Gaussian prior and shrinking each weight by $(1 - η λ)$ per step. Early stopping halts gradient descent before convergence; for a linear model with squared loss it is provably a soft spectral shrinkage closely related to ridge, so stopping early caps the effective degrees of freedom. Dropout randomly zeroes a fraction of activations each step, training an implicit ensemble and approximating model averaging. Statistically, the classical bias-variance trade-off 45.06.02 predicts a U-shaped test error in model complexity; deep networks instead exhibit double descent: test error first rises to a peak at the interpolation threshold $∣ θ ∣ \approx n$ , then descends again as $∣ θ ∣$ grows past it, so the most overparameterized models can generalize best — a regime the classical curve does not describe.

Synthesis. The foundational reason an MLP coheres as a statistical object is the layered decomposition into an adaptive feature map followed by a generalized linear output: the hidden layers learn a basis $x \mapsto Z (x)$ and the last layer runs the logistic / softmax model of 45.08.03 on it, so a neural network is adaptive basis-function regression, and this is exactly the projection-pursuit idea pushed to many composed layers. The training algorithm is dual to this structure: backpropagation propagates the output residual $a^{(L)} - y$ backward through the transposed weights, which is the reverse-mode adjoint pass of 44.03.08 and the central insight that the whole gradient costs one forward plus one backward sweep regardless of how many parameters there are — the cheap-gradient principle is what makes training billion-parameter models feasible at all.

Putting these together, the gradient that backprop computes is consumed by stochastic gradient descent 44.06.05 on a non-convex landscape, and the practical success of this pairing is explained not by convexity but by overparameterization, which is dual to the regularization that controls it: weight decay generalises ridge 45.06.03, early stopping is its spectral shadow, and dropout is implicit averaging. The bridge from classical theory to deep learning is the bias-variance picture of 45.06.02: the U-shaped curve is the foundational reason classical models trade complexity against variance, and double descent is exactly where that picture breaks and is replaced by the interpolation regime, the precise sense in which what classical statistics explains about neural networks — the output GLM, the ridge penalty, the basis expansion — is bounded by what it does not yet explain about why interpolating overparameterized fits generalize.

Full proof set Master

Proposition 1 (a linear network collapses). If $σ$ is the identity, then $f_{θ} (x) = W^{(L)} \dots W^{(1)} x + c$ for a single matrix and vector, so the composition has no more expressive power than one affine map.

Proof. With $σ = id$ , $a^{(l)} = z^{(l)} = W^{(l)} a^{(l - 1)} + b^{(l)}$ . Unrolling, $a^{(L)} = W^{(L)} (W^{(L - 1)} (\dots) + b^{(L - 1)}) + b^{(L)}$ . Matrix multiplication is associative, so the product $W^{(L)} \dots W^{(1)} =: W$ is a single matrix, and the accumulated biases form a single vector $c = \sum_{l} W^{(L)} \dots W^{(l + 1)} b^{(l)}$ . Hence $f_{θ} (x) = W x + c$ , an affine map. $□$

Proposition 2 (the backpropagation recursion). With $δ^{(l)} = \partial J / \partial z^{(l)}$ , the recursion $δ^{(l)} = ((W^{(l + 1)})^{⊤} δ^{(l + 1)}) ⊙ σ^{'} (z^{(l)})$ holds for $l < L$ , and $\partial J / \partial W^{(l)} = δ^{(l)} (a^{(l - 1)})^{⊤}$ , $\partial J / \partial b^{(l)} = δ^{(l)}$ .

Proof. This is the Key theorem. The pre-activation $z^{(l)}$ enters $J$ only through $z^{(l + 1)} = W^{(l + 1)} σ (z^{(l)}) + b^{(l + 1)}$ , so $\partial z_{i}^{(l + 1)} / \partial z_{j}^{(l)} = W_{ij}^{(l + 1)} σ^{'} (z_{j}^{(l)})$ and the chain rule gives $δ_{j}^{(l)} = \sum_{i} δ_{i}^{(l + 1)} W_{ij}^{(l + 1)} σ^{'} (z_{j}^{(l)})$ , the stated Hadamard-transpose form. Since $z_{j}^{(l)}$ depends on $W_{j m}^{(l)}$ only through $W_{j m}^{(l)} a_{m}^{(l - 1)}$ and on $b_{j}^{(l)}$ linearly, the parameter gradients are the outer product $δ^{(l)} (a^{(l - 1)})^{⊤}$ and $δ^{(l)}$ respectively. $□$

Proposition 3 (softmax-cross-entropy output residual). For the softmax $a_{k} = e^{z_{k}} / \sum_{ℓ} e^{z_{ℓ}}$ and cross-entropy $ℓ = - \sum_{k} y_{k} lo g a_{k}$ with one-hot $y$ , the output adjoint is $δ^{(L)} = a - y$ .

Proof. The softmax Jacobian is $\partial a_{k} / \partial z_{j} = a_{k} ([k = j] - a_{j})$ : differentiating $a_{k} = e^{z_{k}} / S$ with $S = \sum_{ℓ} e^{z_{ℓ}}$ gives, for $j = k$ , $a_{k} - a_{k}^{2} = a_{k} (1 - a_{k})$ , and for $j \neq = k$ , $- e^{z_{k}} e^{z_{j}} / S^{2} = - a_{k} a_{j}$ . Then $\partial ℓ / \partial z_{j} = - \sum_{k} (y_{k} / a_{k}) a_{k} ([k = j] - a_{j}) = - y_{j} + a_{j} \sum_{k} y_{k} = a_{j} - y_{j}$ , using $\sum_{k} y_{k} = 1$ . In vector form $δ^{(L)} = a - y$ . $□$

Proposition 4 (cheap-gradient bound for the MLP). One forward pass and one backward pass compute $\nabla_{θ} J$ in time at most $ω TIME (f_{θ})$ for an absolute constant $ω$ , independent of $∣ θ ∣$ .

Proof. The forward pass evaluates each layer's matrix-vector product $W^{(l)} a^{(l - 1)}$ and the coordinatewise $σ$ , costing $TIME (f_{θ}) = \sum_{l} (d_{l} d_{l - 1} + d_{l})$ multiply-adds up to constants. The backward pass, by Proposition 2, computes $δ^{(l)} = ((W^{(l + 1)})^{⊤} δ^{(l + 1)}) ⊙ σ^{'} (z^{(l)})$ — a transposed matrix-vector product of the same size $d_{l + 1} \times d_{l}$ as the forward product — and the parameter gradient $δ^{(l)} (a^{(l - 1)})^{⊤}$ , another $d_{l} d_{l - 1}$ operations. Each layer's backward work is thus a fixed multiple (transpose-multiply plus outer product, roughly $2 \times$ to $3 \times$ ) of its forward work, and $σ^{'} (z^{(l)})$ reuses the stored $a^{(l)}$ . Summing over layers, total work $\leq ω TIME (f_{θ})$ with $ω$ an absolute constant; nowhere does the bound reference $∣ θ ∣$ except through $TIME (f_{θ})$ itself, which is the cheap-gradient principle of 44.03.08. $□$

Proposition 5 (universal approximation, density route). For continuous nonconstant bounded $σ$ and compact $K \subset R^{p}$ , the span of ${x \mapsto σ (a^{⊤} x + b) : a \in R^{p}, b \in R}$ is dense in $C (K)$ under the uniform norm.

Proof (Cybenko's Hahn-Banach argument, sketch). Let $S \subset C (K)$ be the closed linear span of the functions $σ_{a, b} (x) = σ (a^{⊤} x + b)$ . Suppose $S \neq = C (K)$ . By the Hahn-Banach theorem there is a nonzero continuous linear functional $Λ$ on $C (K)$ vanishing on $S$ . By the Riesz representation theorem $Λ (h) = \int_{K} h d μ$ for a nonzero finite signed regular Borel measure $μ$ , so $\int_{K} σ (a^{⊤} x + b) d μ (x) = 0$ for every $a, b$ . A sigmoidal (or, after Hornik, any bounded nonconstant) $σ$ is discriminatory: the only signed measure $μ$ with $\int σ (a^{⊤} x + b) d μ = 0$ for all $a, b$ is $μ = 0$ . This contradicts $μ \neq = 0$ , so $S = C (K)$ . (The discriminatory property is established by taking pointwise limits of $σ (λ (a^{⊤} x + b) + c)$ as $λ \to \infty$ to recover indicator-of-halfspace functions, then invoking uniqueness of the Fourier-Stieltjes transform.) $□$

Connections Master

Logistic and softmax regression 45.08.03 is the output layer of every classification MLP: the final transform $g (W^{(L)} Z + b^{(L)})$ is exactly the multinomial-logistic model of that unit fitted to the learned features $Z = a^{(L - 1)}$ rather than to the raw design, and the output adjoint $δ^{(L)} = a^{(L)} - y$ that drives backprop is the softmax generalisation of the logistic residual $y - p$ , so a neural network is the discriminative GLM of that unit sitting on top of an adaptive basis.
Automatic differentiation 44.03.08 is the backbone of training: backpropagation is precisely reverse-mode AD applied to the scalar empirical risk, and the layerwise adjoint recursion $δ^{(l)} = ((W^{(l + 1)})^{⊤} δ^{(l + 1)}) ⊙ σ^{'} (z^{(l)})$ is the adjoint pass over the layered computational graph of that unit. The cheap-gradient bound — full gradient in a constant multiple of one forward evaluation, independent of parameter count — is inherited directly, and the forward-activation storage versus checkpointing tradeoff is the same memory-versus-recomputation balance.
Stochastic gradient and mirror descent 44.06.05 is the optimizer that consumes the gradients backprop produces: training minimises the non-convex risk by mini-batch SGD, inheriting that unit's noisy-gradient convergence theory, learning-rate schedules, and momentum / adaptive variants, and the implicit regularization of early stopping is an artefact of the SGD trajectory rather than of the objective.
Ridge regression and shrinkage 45.06.03 is the statistical content of weight decay: the penalty $\frac{λ}{2} ∥ θ ∥^{2}$ added to the network risk is the $ℓ_{2}$ / ridge penalty of that unit applied to the weights, equivalent to a Gaussian prior and producing the per-step shrinkage factor $(1 - η λ)$ , so the bias-variance bargain of regularized regression carries over verbatim to network training.
The bias-variance decomposition 45.06.02 frames what classical theory does and does not explain about networks: the U-shaped complexity-error curve of that unit is the classical account of overfitting, and the double-descent behaviour of overparameterized networks is exactly where that curve is superseded by the interpolation regime, making this unit the place the bias-variance picture meets its modern boundary.

Historical & philosophical context Master

The perceptron of Rosenblatt (1958) trained a single linear threshold unit; Minsky and Papert's Perceptrons (1969) showed such a unit cannot represent the exclusive-or, a limitation removed only by adding a hidden layer. The algorithm for training the hidden weights — backpropagation — was discovered repeatedly: as reverse-mode accumulation of derivatives over a computational graph it appears in Seppo Linnainmaa's 1970 thesis, and Paul Werbos proposed it for networks in his 1974 dissertation. It entered mainstream use through Rumelhart, Hinton, and Williams' 1986 paper Learning representations by back-propagating errors ^{[Rumelhart 1986]}, which demonstrated that gradient descent on the squared error, with the gradient computed by the layerwise chain rule, could train multilayer networks to learn internal representations.

The expressive power of a single hidden layer was settled by George Cybenko's 1989 proof ^{[Cybenko 1989]} that finite superpositions of a continuous sigmoidal function are dense in the continuous functions on a compact set, established by a Hahn-Banach and Riesz-representation argument rather than by construction. Kurt Hornik's 1991 paper ^{[Hornik 1991]}, following joint work with Stinchcombe and White, removed the sigmoidal hypothesis to any bounded nonconstant activation and extended density to Sobolev norms, showing the approximation power is a property of the multilayer architecture, not of the particular nonlinearity. The contemporary statistical-learning treatment is consolidated in Hastie, Tibshirani, and Friedman ^{[Hastie 2009]} Ch. 11 and in Goodfellow, Bengio, and Courville ^{[Goodfellow 2016]}, the latter framing backpropagation explicitly as reverse-mode automatic differentiation and documenting the optimization and regularization practice of deep networks.

Bibliography Master

@book{hastie2009elements,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009},
  note      = {Chapter 11, neural networks}
}

@book{goodfellow2016deep,
  author    = {Goodfellow, Ian and Bengio, Yoshua and Courville, Aaron},
  title     = {Deep Learning},
  publisher = {MIT Press},
  year      = {2016}
}

@article{cybenko1989approximation,
  author  = {Cybenko, George},
  title   = {Approximation by superpositions of a sigmoidal function},
  journal = {Mathematics of Control, Signals and Systems},
  volume  = {2},
  number  = {4},
  pages   = {303--314},
  year    = {1989}
}

@article{hornik1991approximation,
  author  = {Hornik, Kurt},
  title   = {Approximation capabilities of multilayer feedforward networks},
  journal = {Neural Networks},
  volume  = {4},
  number  = {2},
  pages   = {251--257},
  year    = {1991}
}

@article{rumelhart1986learning,
  author  = {Rumelhart, David E. and Hinton, Geoffrey E. and Williams, Ronald J.},
  title   = {Learning representations by back-propagating errors},
  journal = {Nature},
  volume  = {323},
  number  = {6088},
  pages   = {533--536},
  year    = {1986}
}

@phdthesis{werbos1974beyond,
  author = {Werbos, Paul J.},
  title  = {Beyond Regression: New Tools for Prediction and Analysis in the Behavioral Sciences},
  school = {Harvard University},
  year   = {1974}
}

@book{minsky1969perceptrons,
  author    = {Minsky, Marvin and Papert, Seymour},
  title     = {Perceptrons: An Introduction to Computational Geometry},
  publisher = {MIT Press},
  year      = {1969}
}

Prerequisites

45.08.03
44.03.08

Tier anchors

beginner: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) §11.1-11.3 (projection pursuit and neural networks, the single-hidden-layer net as a sum of sigmoid basis functions); 3Blue1Brown — 'Neural networks' chapters 1-4 (the network as nested affine-plus-nonlinearity layers, gradient descent, and the backpropagation calculus)
intermediate: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) §11.3-11.5 (the feed-forward model, fitting by back-propagation as the chain rule over the layers, the squared-error and cross-entropy objectives, weight decay and early stopping); Goodfellow, Bengio & Courville 2016 Deep Learning (MIT Press) Ch. 6 (deep feedforward networks, hidden units, the back-propagation algorithm as reverse-mode differentiation on the computational graph)
master: Hastie, Tibshirani & Friedman 2009 The Elements of Statistical Learning 2e (Springer) Ch. 11 (the full statistical treatment, regularization, the bias-variance behaviour); Goodfellow, Bengio & Courville 2016 Deep Learning (MIT Press) Ch. 6 and Ch. 8 (back-propagation and optimization for training); Cybenko 1989 Approximation by superpositions of a sigmoidal function (Math. Control Signals Systems 2) and Hornik 1991 Approximation capabilities of multilayer feedforward networks (Neural Networks 4) for universal approximation

References

Hastie, T., Tibshirani, R. & Friedman, J. — The Elements of Statistical Learning (2nd ed.) · Springer, 2009. Ch. 11 (neural networks): §11.1-11.2 (projection-pursuit regression g(sum a_m^T x) as the statistical ancestor, the single-hidden-layer net as an adaptive basis expansion), §11.3 (the feed-forward model: derived features Z_m = sigma(alpha_{0m} + alpha_m^T X) from the hidden layer, the output T_k = beta_{0k} + beta_k^T Z and the output transform g_k, with g the identity for regression and the softmax for K-class classification — the output layer is exactly a linear/multinomial-logistic model on the learned features Z), §11.4 (fitting neural networks: the sum-of-squared-errors and cross-entropy objectives R(theta), gradient descent by back-propagation derived as the chain rule giving the delta_{ki} and s_{mi} error terms with the forward/backward two-pass structure, the learning rate, batch versus online updates), §11.5 (issues in training: the non-convex objective with many local minima, the need for multiple random starts, weight decay sum theta^2 as the ridge analogue, scaling of inputs, the number of hidden units and layers, early stopping as implicit regularization), §11.6 (the running ZIP-code digit example). The discussion frames the network as flexible nonlinear function estimation and connects weight decay to ridge and the bias-variance trade-off.
Goodfellow, I., Bengio, Y. & Courville, A. — Deep Learning · MIT Press, 2016. Ch. 6 (deep feedforward networks): the MLP as a composition f(x) = f^{(L)} circ ... circ f^{(1)}(x) of affine-plus-activation layers approximating some target f^*, the role of hidden units in learning a representation, activation functions (the sigmoid 1/(1+e^{-z}), tanh, and the rectified linear unit max(0,z) with its non-saturating gradient), output units (linear-Gaussian, sigmoid-Bernoulli, softmax-multinoulli) tied to the maximum-likelihood / cross-entropy loss, §6.5 the back-propagation algorithm presented as reverse-mode automatic differentiation on the computational graph (forward pass computing activations, backward pass propagating gradients via the chain rule with the Jacobian-times-vector recursion), and the distinction between back-propagation (the gradient computation) and the learning algorithm (stochastic gradient descent that consumes it). Ch. 7 (regularization: L2/weight decay as a Gaussian prior / ridge penalty, early stopping, dropout as approximate model averaging) and Ch. 8 (optimization for training, the non-convex landscape, mini-batch SGD).
Cybenko, G. — Approximation by superpositions of a sigmoidal function · Mathematics of Control, Signals and Systems 2(4), 1989, pp. 303-314. Proves the universal approximation theorem for single-hidden-layer feedforward networks with a continuous sigmoidal activation: finite sums sum_{j} c_j sigma(a_j^T x + b_j) are dense in C([0,1]^n) under the uniform norm, for any continuous discriminatory (in particular any continuous sigmoidal) sigma. The proof is non-constructive, by the Hahn-Banach and Riesz representation theorems: if the closure of the span were a proper subspace there would be a nonzero signed measure annihilating every sigma(a^T x + b), contradicting the discriminatory property. Hornik, Stinchcombe & White (1989) and Hornik (1991) extend the result to arbitrary bounded nonconstant activations and to approximation of derivatives in Sobolev norms, decoupling the approximation power from the specific sigmoid shape.

Estimated time

beginner: 25m
intermediate: 55m
master: 90m