Backpropagation

A neural network computes a composite function: input $x$ passes through layers $f_1, f_2, \dots, f_L$, each parameterized by weights $\theta_\ell$, producing a scalar loss $\mathcal{L}$ after comparison with a target via a loss function. Training requires $\partial \mathcal{L}/\partial \theta_\ell$ for every layer $\ell$, so that gradient descent can update each weight. The computational graph is the directed acyclic graph (DAG) of all intermediate values: each node is a tensor, each edge a differentiable operation, and the loss is the unique sink.

Forward-mode differentiation propagates derivatives of intermediate variables with respect to one input forward through the graph — efficient when there are few inputs and many outputs. Reverse-mode differentiation, which is what backpropagation is, propagates derivatives of the loss with respect to many intermediate variables backward from the single output. Because a neural network has one scalar output (the loss) and potentially millions of parameters (playing the role of "inputs" whose sensitivities we want), reverse mode is the correct choice: it computes gradients with respect to all parameters in a single backward traversal, regardless of how many there are. The key mathematical object is the adjoint, written $\bar{v} = \partial \mathcal{L}/\partial v$ for any node $v$ in the graph. Backpropagation computes adjoints for every node in one pass, from the loss backward to the inputs, using the multivariate chain rule: if $v$ feeds into nodes $u_1, \dots, u_k$, then

This single recurrence, applied node by node in reverse topological order, is the entirety of the algorithm. Everything else — layer-specific derivative formulas, matrix shapes, caching strategies — is implementation detail around this recurrence.

Training a feedforward network proceeds in two passes over the same computational graph.

Forward pass. Compute and cache every intermediate activation, since the backward pass will need them to compute local derivatives. For a layer with pre-activation $z^{(\ell)} = W^{(\ell)} a^{(\ell-1)} + b^{(\ell)}$ and activation $a^{(\ell)} = \sigma(z^{(\ell)})$, cache both $z^{(\ell)}$ and $a^{(\ell)}$.

Backward pass. Starting from $\bar{\mathcal{L}} = \partial \mathcal{L}/\partial \mathcal{L} = 1$, walk the graph in reverse topological order. At each node, use the local derivative (a Jacobian or its transpose-vector product) to convert the adjoint of the node's outputs into the adjoint of its inputs. For a dense layer this yields the classical equations:

where $\odot$ is elementwise multiplication and $\delta^{(\ell)}$ is the traditional "error signal" at layer $\ell$. Note $\bar a^{(\ell-1)}$ is exactly what the previous layer needs as its output-adjoint — this is the chaining that makes the pass a single linear sweep. ```

# Forward + backward pass for an L-layer MLP.

# Weights W[1..L], biases b[1..L]; activation function sigma with derivative sigma_prime.

# x: input vector, y: target, loss L(a_L, y) with known dL/da_L. function FORWARD(x, W, b): a[0] = x for l = 1 to L: z[l] = W[l] @ a[l-1] + b[l] # cache z[l] a[l] = sigma(z[l]) # cache a[l] return a[L], {z, a} # a[L] used to compute the loss function BACKWARD(y, a_L, cache, W):

# 1. Seed: gradient of loss wrt the network's final output grad_a[L] = dLoss_dOutput(a_L, y) # e.g. (a_L - y) for MSE for l = L downto 1:

# 2. Push through the activation function (local Jacobian is diagonal) delta[l] = grad_a[l] * sigma_prime(cache.z[l]) # elementwise

# 3. Parameter gradients (accumulate — outer product) grad_W[l] = delta[l] @ transpose(cache.a[l-1]) grad_b[l] = delta[l]

# 4. Propagate to the previous layer's activation (matrix-vector) if l > 1: grad_a[l-1] = transpose(W[l]) @ delta[l] return grad_W, grad_b function TRAIN_STEP(x, y, W, b, learning_rate): a_L, cache = FORWARD(x, W, b) grad_W, grad_b = BACKWARD(y, a_L, cache, W) for l = 1 to L: W[l] = W[l] - learning_rate grad_W[l] b[l] = b[l] - learning_rate grad_b[l] return LOSS(a_L, y) ``` Two invariants are worth naming explicitly. First, the caching invariant: any value used to compute a local derivative during the backward pass must have been stored during the forward pass (this is why memory, not just compute, scales with depth — see below). Second, the adjoint-accumulation invariant: if a node's output feeds into multiple downstream nodes (e.g., a weight shared across time steps, or a skip connection), its adjoint is the sum of the contributions from each consumer, exactly as the chain-rule sum above dictates. Forgetting to accumulate — instead of overwrite — at fan-out nodes is one of the most common implementation bugs.

Time complexity. Let $C_f$ be the cost of the forward pass. Each forward operation — a matrix multiply, an elementwise nonlinearity — has a corresponding backward operation whose cost is the same asymptotic order as its forward counterpart: the backward of $z = Wa$ is two matrix-vector (or matrix-matrix, for batches) products of identical shape, $\bar W = \delta a^\top$ and $\bar a = W^\top \delta$, each costing $O(\text{same FLOPs as the forward multiply})$. Summing over all operations in the graph, the total backward cost is $O(C_f)$, with a constant factor typically cited as 2–3 (one multiply forward, roughly two equivalent multiplies backward, per layer). This is the crucial efficiency claim: gradient computation costs a constant multiple of a single forward pass, independent of the number of parameters — a stark contrast to numerical finite-differencing, which costs $O(P \cdot C_f)$ for $P$ parameters, since it needs one perturbed forward pass per parameter.

Space complexity. The forward pass must cache every intermediate activation needed by the backward pass, so memory scales as $O(\text{depth} \times \text{width})$ — i.e., proportional to the total number of intermediate activations, not just the number of parameters. This is the well-known memory bottleneck of deep networks and the motivation for gradient checkpointing (recomputing selected activations during the backward pass instead of storing all of them, trading time for memory).

Correctness argument. The algorithm is a direct, mechanical unfolding of the multivariate chain rule, and its correctness is provable by induction over the reverse topological order of the DAG. Claim: after processing node $v$ in the backward traversal, the computed value equals the true adjoint $\bar v = \partial \mathcal{L}/\partial v$. Base case: the loss node $\mathcal{L}$ is initialized with $\bar{\mathcal{L}} = 1 = \partial \mathcal{L}/\partial \mathcal{L}$, trivially correct. Inductive step: suppose every node downstream of $v$ (in forward-graph terms, every consumer of $v$) has already had its adjoint correctly computed, because the traversal visits nodes in reverse topological order — a node is only processed after all its consumers have been. Let $u_1, \dots, u_k$ be the direct consumers of $v$ in the graph, so each $u_i = g_i(v, \dots)$ for some differentiable $g_i$. By the multivariate chain rule, since $\mathcal{L}$ depends on $v$ only through the $u_i$'s,

Each $\bar u_i$ is available by the inductive hypothesis, and $\partial u_i/\partial v$ is a local derivative computable from cached forward values without reference to the rest of the graph. The algorithm computes exactly this sum, so $v$'s adjoint is correct. Since the DAG is finite and reverse-topological order always exists (the graph is acyclic by construction — no operation can depend on its own output), induction terminates with every adjoint, including all parameter adjoints, correctly computed. $\blacksquare$

Honest tradeoffs. Backpropagation gives exact gradients (up to floating-point error) at optimal asymptotic cost, but it is not free of pathology: repeated multiplication of Jacobians across many layers can make gradients shrink or grow geometrically with depth (foreshadowing The Vanishing and Exploding Gradient Problem), and the memory cost of caching every activation can dominate GPU memory budgets for very deep or very wide networks, forcing engineering tradeoffs like checkpointing or mixed precision.

Consider a tiny two-layer network with scalar-friendly shapes: input $x \in \mathbb{R}^2$, one hidden unit with sigmoid activation, one linear output unit, and squared-error loss against target $y$.

Take concrete numbers: $x = (1.0, 2.0)$, $w^{(1)} = (0.5, -0.3)$, $b^{(1)} = 0.1$, $w^{(2)} = 2.0$, $b^{(2)} = 0.0$, target $y = 1.0$.

Forward pass:

Backward pass, seeding $\bar{\mathcal{L}} = 1$:

A gradient-descent step with learning rate $\eta = 0.1$ updates, e.g., $w^{(2)} \leftarrow 2.0 - 0.1\times(-0.02375) = 2.002375$, nudging the output closer to $y=1.0$ — consistent with the fact that $\bar z^{(2)} < 0$ (output too high) correctly produces gradient updates that increase $w^{(2)}$ and the hidden-layer weights that feed into it. Notice how every downstream adjoint ($\bar z^{(2)}, \bar a^{(1)}, \bar z^{(1)}$) was computed exactly once and reused to derive both the parameter gradients at that layer and the adjoint passed to the previous layer — the essence of the algorithm's efficiency: no quantity is recomputed.

Backpropagation as applied to neural networks was popularized by the 1986 paper of Rumelhart, Hinton, and Williams, though the mathematical technique — reverse-mode accumulation of derivatives through a chain of computations — was independently discovered multiple times in control theory and automatic differentiation research going back to the 1960s and 70s (notably by Seppo Linnainmaa's 1970 thesis on reverse-mode AD, and earlier control-theoretic work by Henry J. Kelley and Arthur Bryson).

Every deep learning framework's automatic differentiation engine — PyTorch's `autograd`, TensorFlow's `tf.GradientTape`, JAX's `grad`/`vjp` — is a general-purpose implementation of reverse-mode backpropagation over an arbitrary computational graph, not just fixed feedforward layers. Training convolutional networks for vision, transformers for language, graph neural networks, diffusion models, and reinforcement learning policies all reduce, at the innermost loop, to one backward pass computed by this algorithm. Hardware accelerators (GPUs, TPUs) are designed around the matrix-multiply-heavy structure of both forward and backward passes, and systems like gradient checkpointing, mixed-precision training, and distributed data-parallel training all exist specifically to manage the compute/memory tradeoffs backpropagation introduces. Understanding backpropagation is the prerequisite for understanding Automatic Differentiation engines in full generality and for diagnosing training pathologies like The Vanishing and Exploding Gradient Problem.

Ask the tutor: How would the backward-pass equations change if two layers share the same weight matrix?