Backpropagation

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Computation Graphs
6. The Multivariate Chain Rule
7. Forward Pass: Activations and Caching
8. Backward Pass: Error Signals
9. Layer-Wise Gradient Formulas
10. The General Backpropagation Algorithm
11. Vector-Jacobian Products
12. Gradients for Common Operations
13. Computational Complexity
14. Worked Examples
15. Connection to the Broader Curriculum
16. Common Pitfalls and Misconceptions
17. Research Perspective
18. Summary of Takeaways
19. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. Represent a neural network as a directed acyclic computation graph and identify intermediate variables.
2. State and apply the multivariate chain rule for composed functions $\mathbb{R}^n \to \mathbb{R}$.
3. Derive the forward pass equations that cache activations for the backward pass.
4. Derive the backward pass (error propagation) equations for a multi-layer network.
5. Write the general formulas $\delta^l = (W^{l+1})^T \delta^{l+1} \odot \sigma'(z^l)$ and $\partial \mathcal{L}/\partial W^l = \delta^l (a^{l-1})^T$.
6. Explain backpropagation as repeated vector-Jacobian products.
7. Analyze the $O(\text{\# parameters})$ computational cost of gradient computation via backpropagation.

Prerequisites

This chapter assumes familiarity with:

• Gradient Descent — gradients, chain rule in single-variable calculus
• Matrix Operations & Linear Transformations — matrix multiplication, transposes
• Logistic Regression — sigmoid, cross-entropy gradient

Notation

• $f^{(l)}$ — Activation at layer $l$
• $\mathbf{W}^{(l)}, \mathbf{b}^{(l)}$ — Weight matrix and bias at layer $l$
• $\delta^{(l)} = \partial \mathcal{L}/\partial f^{(l)}$ — Error signal (adjoint variable)
• $\mathcal{L}$ — Scalar loss
• $\odot$ — Element-wise (Hadamard) product

Core Intuition

Training a neural network requires computing $\partial \mathcal{L}/\partial \theta$ for every parameter $\theta$ — potentially billions of them. Backpropagation is an efficient algorithm for this, discovered independently by Werbos (1974), Parker (1985), and popularized by Rumelhart, Hinton, and Williams (1986).

The core idea is elementary: a neural network is a composition of functions. The gradient of a composition is computed by the chain rule, applied systematically from the loss backward to the inputs. Backpropagation is not a new mathematical principle — it is the chain rule organized to reuse intermediate computations.

The efficiency comes from dynamic programming: each intermediate gradient is computed once and reused for all parameters downstream. Without this sharing, gradient computation would be exponentially expensive in network depth.

Series context. This opens Chapter 6 (Deep Learning Foundations) in Volume II. It connects Gradient Descent to all subsequent deep learning training — Batch Normalization, Self-Attention, and beyond.

Computation Graphs

Definition 1 (Computation Graph). A computation graph is a directed acyclic graph (DAG) where:

• Leaf nodes are inputs (data $\mathbf{x}$, parameters $\mathbf{W}, \mathbf{b}$)
• Interior nodes are intermediate values computed from their parents
• Root node is the scalar loss $\mathcal{L}$

Each edge represents a functional dependency: if node $v$ depends on node $u$, then $\partial v / \partial u$ is well-defined.

Definition 2 (Neural Network as Composition). An $L$-layer network defines a composition:

where $f_l(\mathbf{a}^{l-1}) = \sigma(W^l \mathbf{a}^{l-1} + \mathbf{b}^l)$ and $\ell$ is the loss function.

Proposition 1. Any differentiable computation — matrix multiplications, activations, normalization, attention — can be represented as a computation graph. Backpropagation applies to the entire graph.

The Multivariate Chain Rule

Theorem 1 (Multivariate Chain Rule). Let $f: \mathbb{R}^m \to \mathbb{R}^n$ and $g: \mathbb{R}^n \to \mathbb{R}$ be differentiable. Then $h = g \circ f: \mathbb{R}^m \to \mathbb{R}$ is differentiable and

where $\partial f / \partial \mathbf{x} \in \mathbb{R}^{n \times m}$ is the Jacobian of $f$.

Proof. For each component, $\partial h / \partial x_j = \sum_{i=1}^{n} (\partial g / \partial y_i)(\partial y_i / \partial x_j)$. Stacking: $\nabla_{\mathbf{x}} h = \mathbf{J}_f^T \nabla_{\mathbf{y}} g$. $\blacksquare$

Definition 3 (Error Signal / Adjoint). Define the error signal at node $\mathbf{v}$:

Backpropagation computes $\bar{\mathbf{v}}$ for every node by propagating from the loss backward.

Forward Pass: Activations and Caching

Definition 4 (Layer Notation). For layer $l = 1, \ldots, L$:

with $\mathbf{a}^0 = \mathbf{x}$ (input) and $\hat{\mathbf{y}} = \mathbf{a}^L$ (output).

Algorithm (Forward Pass). For $l = 1, \ldots, L$:

1. Compute pre-activation: $\mathbf{z}^l = W^l \mathbf{a}^{l-1} + \mathbf{b}^l$

2. Compute activation: $\mathbf{a}^l = \sigma(\mathbf{z}^l)$

3. Cache $\mathbf{z}^l$ and $\mathbf{a}^{l-1}$ for the backward pass

4. Compute loss: $\mathcal{L} = \ell(\mathbf{a}^L, \mathbf{y})$

All cached values are needed for gradient computation — memory cost is $O(L \cdot \text{width})$.

Backward Pass: Error Signals

We derive gradients for a two-layer network, then generalize.

Setup. Layer 2 (output): $\mathbf{z}^2 = W^2 \mathbf{a}^1 + \mathbf{b}^2$, $\hat{\mathbf{y}} = \sigma(\mathbf{z}^2)$. Layer 1 (hidden): $\mathbf{z}^1 = W^1 \mathbf{x} + \mathbf{b}^1$, $\mathbf{a}^1 = \sigma(\mathbf{z}^1)$.

Definition 5 (Output Error). Define $\delta^l = \partial \mathcal{L} / \partial \mathbf{z}^l$ (error at pre-activation of layer $l$).

Step 1: Output layer error. For cross-entropy with sigmoid output and binary labels:

Proof. $\mathcal{L} = -y \log \sigma(z) - (1-y)\log(1-\sigma(z))$. Using $\sigma'(z) = \sigma(z)(1-\sigma(z))$:

Multiplying by $\sigma'(z) = \sigma(z)(1-\sigma(z))$ gives $\sigma(z) - y = \hat{y} - y$. $\blacksquare$

Step 2: Parameter gradients at layer 2.

Proof. Since $\mathbf{z}^2 = W^2 \mathbf{a}^1 + \mathbf{b}^2$, we have $\partial z_i^2 / \partial W_{ij}^2 = a_j^1$ and $\partial \mathcal{L}/\partial W_{ij}^2 = \delta_i^2 a_j^1$. Matrix form: $\partial \mathcal{L}/\partial W^2 = \delta^2 (\mathbf{a}^1)^T$. $\blacksquare$

Step 3: Propagate error to layer 1.

where $\odot$ denotes element-wise (Hadamard) product.

Proof. By the chain rule: $\partial \mathcal{L}/\partial z_j^1 = \sum_i (\partial \mathcal{L}/\partial z_i^2)(\partial z_i^2 / \partial a_j^1)(\partial a_j^1 / \partial z_j^1) = \sum_i \delta_i^2 W_{ij}^2 \cdot \sigma'(z_j^1)$. Vector form: $\delta^1 = (W^2)^T \delta^2 \odot \sigma'(\mathbf{z}^1)$. $\blacksquare$

Step 4: Parameter gradients at layer 1.

Layer-Wise Gradient Formulas

Theorem 2 (General Backpropagation Equations). For an $L$-layer network with loss $\mathcal{L}$, the error signals satisfy:

and the parameter gradients are:

Proof. By induction on $l$. The base case $l = L$ follows from the chain rule through the loss. For the inductive step, assume $\delta^{l+1} = \partial \mathcal{L}/\partial \mathbf{z}^{l+1}$. Since $\mathbf{z}^{l+1} = W^{l+1}\sigma(\mathbf{z}^l) + \mathbf{b}^{l+1}$:

This gives (11). For (12): $\partial \mathcal{L}/\partial W^l = \delta^l (\mathbf{a}^{l-1})^T$ follows from $\partial z_i^l / \partial W_{ij}^l = a_j^{l-1}$. $\blacksquare$

Important equation. Equations (11)–(12) are the workhorse of deep learning. Modern automatic differentiation systems implement these recurrences as reverse-mode adjoint passes over the computation graph.

The General Backpropagation Algorithm

Algorithm (Backpropagation).

Input: Network with parameters $\{W^l, \mathbf{b}^l\}_{l=1}^L$, input $\mathbf{x}$, target $\mathbf{y}$.

1. Forward pass: Compute and cache $\mathbf{z}^l, \mathbf{a}^l$ for all $l$.
2. Output error: $\delta^L = \nabla_{\hat{\mathbf{y}}} \ell \odot \sigma'(\mathbf{z}^L)$.
3. Backward pass: For $l = L-1, \ldots, 1$:
   • $\delta^l = (W^{l+1})^T \delta^{l+1} \odot \sigma'(\mathbf{z}^l)$
4. Gradients: For $l = 1, \ldots, L$:
   • $\nabla_{W^l} \mathcal{L} = \delta^l (\mathbf{a}^{l-1})^T$
   • $\nabla_{\mathbf{b}^l} \mathcal{L} = \delta^l$
5. Update: $\theta \leftarrow \theta - \alpha \nabla_\theta \mathcal{L}$ (gradient descent step)

Vector-Jacobian Products

Definition 6 (VJP). The vector-Jacobian product of $f: \mathbb{R}^m \to \mathbb{R}^n$ at $\mathbf{x}$ with cotangent vector $\mathbf{v} \in \mathbb{R}^n$ is:

where $\mathbf{J}_f = \partial f / \partial \mathbf{x}$.

Proposition 2. Backpropagation computes VJPs in reverse topological order. Each node receives a cotangent $\bar{\mathbf{v}}$ and passes $\mathbf{J}_f^T \bar{\mathbf{v}}$ to its parents.

This abstraction generalizes backpropagation beyond feedforward networks to arbitrary DAGs (residual connections, attention, branching).

Theorem 3 (Automatic Differentiation). Reverse-mode automatic differentiation (backpropagation) computes the full gradient $\nabla_{\boldsymbol{\theta}} \mathcal{L} \in \mathbb{R}^p$ for $p$ parameters in $O(\text{cost of forward pass})$ operations, regardless of $p$.

Forward-mode AD computes one directional derivative in $O(\text{forward pass})$ but requires $p$ passes for the full gradient — impractical for neural networks where $p \gg 1$.

Gradients for Common Operations

Proposition 3 (Linear Layer). For $\mathbf{z} = W\mathbf{a} + \mathbf{b}$ with upstream gradient $\bar{\mathbf{z}} = \partial \mathcal{L}/\partial \mathbf{z}$:

Proposition 4 (Element-wise Activation). For $\mathbf{a} = \sigma(\mathbf{z})$:

Proposition 5 (Softmax + Cross-Entropy). For $K$-class softmax output with cross-entropy loss:

where $\hat{\mathbf{p}} = \text{softmax}(\mathbf{z})$ and $\mathbf{y}$ is the one-hot target — the same clean form as (5).

Proposition 6 (ReLU). For $a = \max(0, z)$: $\partial \mathcal{L}/\partial z = \partial \mathcal{L}/\partial a \cdot \mathbb{1}[z > 0]$.

Computational Complexity

Theorem 4 (Backprop Cost). For a network with $W$ weights and forward pass cost $C_{\text{fwd}}$, backpropagation computes all gradients in $O(C_{\text{fwd}})$ — typically $O(W)$.

Proof sketch. Each edge in the computation graph is traversed once in the forward pass and once in the backward pass. The total work is at most twice the forward cost. $\blacksquare$

Comparison. Numerical gradient via finite differences requires $p + 1$ forward passes for $p$ parameters — $O(p \cdot C_{\text{fwd}})$, infeasible for $p \sim 10^9$.

Worked Examples

Example 1: Scalar Two-Layer Network

Let $x \in \mathbb{R}$, $W^1, W^2, b^1, b^2 \in \mathbb{R}$, $\sigma = \text{ReLU}$. Forward: $z^1 = W^1 x + b^1$, $a^1 = \max(0, z^1)$, $z^2 = W^2 a^1 + b^2$, $\hat{y} = z^2$ (linear output), $\mathcal{L} = \frac{1}{2}(\hat{y} - y)^2$.

Backward: $\delta^2 = \hat{y} - y$, $\partial \mathcal{L}/\partial W^2 = \delta^2 a^1$, $\delta^1 = W^2 \delta^2 \cdot \mathbb{1}[z^1 > 0]$, $\partial \mathcal{L}/\partial W^1 = \delta^1 x$.

Example 2: Batch Processing

For a mini-batch $\mathbf{X} \in \mathbb{R}^{B \times d}$, gradients accumulate over batch dimension: $\partial \mathcal{L}/\partial W^l = \frac{1}{B}\sum_{b=1}^{B} \delta_b^l (\mathbf{a}_b^{l-1})^T$.

Example 3: Depth and Vanishing Gradients

For $\sigma = \text{sigmoid}$, $|\sigma'(z)| \leq 1/4$. Through $L$ layers: $\|\delta^1\| \leq (1/4)^L \|\delta^L\| \to 0$ as $L \to \infty$. This motivates ReLU, residual connections, and careful initialization.

Connection to the Broader Curriculum

Backpropagation is the computational engine for:

• Batch Normalization — additional nodes in the computation graph
• Self-Attention — gradients through softmax attention weights
• Variational Autoencoders — reparameterization trick enables backprop through stochastic nodes
• LoRA — backprop through low-rank adapter matrices
• Flash Attention — IO-aware implementation of the same mathematical gradients

Gradient Descent provides the optimizer; backpropagation provides the gradients.

Common Pitfalls and Misconceptions

Pitfall 1: Thinking backpropagation is separate from the chain rule. It is the chain rule, organized efficiently. There is no additional mathematical content.

Pitfall 2: Forgetting to cache forward pass values. The backward pass requires $\mathbf{a}^{l-1}$ and $\mathbf{z}^l$ from the forward pass. Recomputing them doubles cost.

Pitfall 3: Confusing $\partial \mathcal{L}/\partial \mathbf{a}^l$ with $\delta^l = \partial \mathcal{L}/\partial \mathbf{z}^l$. The error signal $\delta^l$ is at the pre-activation. The activation gradient requires multiplying by $\sigma'(\mathbf{z}^l)$.

Pitfall 4: Numerical gradient checking on large networks. Finite-difference checking is $O(p)$ — use only on tiny subnetworks for debugging.

Pitfall 5: Ignoring vanishing/exploding gradients. Deep networks require architectural mitigations (residual connections, normalization, gated activations) beyond naive backpropagation.

Research Perspective

The modern history of backpropagation begins with Werbos's 1974 PhD thesis, was independently rediscovered by Parker (1985), and was popularized by Rumelhart, Hinton, and Williams (1986), who demonstrated learning of internal representations.

Automatic differentiation was formalized by Wengert (1964) and developed into modern AD theory (Griewank & Walther, 2008). Reverse-mode AD computes the full gradient of a scalar loss in time proportional to a single forward pass — the computational foundation of deep learning optimization.

Open research directions include:

• Gradient-free optimization for non-differentiable objectives (evolution strategies, REINFORCE)
• Second-order methods using Hessian information (K-FAC, natural gradient)
• Memory-efficient backprop (gradient checkpointing, reversible networks)
• Understanding gradient dynamics in overparameterized networks (neural tangent kernel regime)

Backpropagation remains the dominant training algorithm four decades after its popularization — a testament to the chain rule's enduring power.

Summary of Takeaways

• Error signal — $\delta^l = \partial \mathcal{L}/\partial \mathbf{z}^l$ — Upstream gradient at layer $l$
• Backprop recurrence — $\delta^l = (W^{l+1})^T \delta^{l+1} \odot \sigma'(\mathbf{z}^l)$ — Propagate errors backward
• Weight gradient — $\partial \mathcal{L}/\partial W^l = \delta^l (\mathbf{a}^{l-1})^T$ — Outer product of error and input
• Output layer (CE+sigmoid) — $\delta^L = \hat{\mathbf{y}} - \mathbf{y}$ — Clean gradient form
• VJP — $\mathbf{v}^T \mathbf{J}_f$ — General backprop abstraction
• Complexity — $O(C_{\text{fwd}})$ — Same order as one forward pass

Next article: Universal Approximation Theorem → — why depth and width give neural networks their expressive power.

Exercises

Exercise 1 (Chain rule). Derive (8) explicitly for a scalar two-layer network without matrix notation.

Exercise 2 (Softmax gradient). Prove (17) by differentiating categorical cross-entropy through softmax.

Exercise 3 (Generalization). Extend Theorem 2 to a network with skip connections: $\mathbf{a}^l = \sigma(\mathbf{z}^l) + \mathbf{a}^{l-1}$. How does the error propagate?

Exercise 4 (VJP). Express the full backpropagation algorithm for a DAG (not just a chain) using VJP notation.

Exercise 5 (Complexity). Count the number of multiply-add operations for forward and backward passes of a single fully connected layer mapping $\mathbb{R}^n \to \mathbb{R}^m$.

Exercise 6 (Vanishing gradients). For $\sigma = \tanh$, bound $|\sigma'(z)|$ and derive the worst-case gradient decay through $L$ layers.

Exercise 7 (Batch). Show that batch gradient $\frac{1}{B}\sum_b \nabla \mathcal{L}_b$ equals the gradient of the average loss $\mathcal{L} = \frac{1}{B}\sum_b \mathcal{L}_b$.

Exercise 8 (Conceptual). Why is reverse-mode AD preferred over forward-mode for neural network training? Give a quantitative argument using typical values of $p$ (parameters) and output dimension.