Model: \(p = \sigma(z)\) where \(z = \mathbf{w}^T\mathbf{x} + b\)

Sigmoid: \(\sigma(z) = \frac{1}{1 + e^{-z}}\)

Loss (binary cross-entropy):

Derivative of sigmoid:

Loss gradient w.r.t. \(z\):

Weight gradient:

Bias gradient:

Setup:

• Input: \(\mathbf{x} = [2, 1]^T\)
• Weights: \(\mathbf{w} = [0.5, -0.3]^T\)
• Bias: \(b = 0\)
• Label: \(y = 1\)

Forward pass:

Loss:

Gradient computation:

Numerical check (finite difference with \(\epsilon = 10^{-5}\)):

For \(w_1\):

Matches analytical gradient

Two-layer network:

Forward pass equations:

Layer 1:

Layer 2:

Loss:

Question: How to update \(W^{(1)}\)?

Answer: \(W^{(1)} \leftarrow W^{(1)} - \eta \frac{\partial \mathcal{L}}{\partial W^{(1)}}\)

Loss depends on \(W^{(1)}\) through path:

Need systematic method for arbitrary depth

Per layer \(l = 1, \ldots, L\):

• \(\mathbf{s}^{(l)} = W^{(l)}\mathbf{a}^{(l-1)} + \mathbf{b}^{(l)}\) — pre-activation
• \(\mathbf{a}^{(l)} = \sigma(\mathbf{s}^{(l)})\) — activation (post-nonlinearity)
• \(W^{(l)} \in \mathbb{R}^{n_l \times n_{l-1}}\) — weight matrix
• \(\mathbf{b}^{(l)} \in \mathbb{R}^{n_l}\) — bias vector
• \(\sigma\) — activation function (sigmoid, ReLU, etc.)

Boundary and indexing:

• \(\mathbf{a}^{(0)} = \mathbf{x}\) — input (layer 0)
• \(\mathbf{a}^{(L)} = \hat{\mathbf{y}}\) — output (layer \(L\))
• \(\mathcal{L}(\hat{\mathbf{y}}, \mathbf{y})\) — loss (scalar)
• \(l\) indexes layers, \(L\) is the total count

Gradient shorthand:

• \(\boldsymbol{\delta}^{(l)} \equiv \frac{\partial \mathcal{L}}{\partial \mathbf{s}^{(l)}}\) — “delta” at layer \(l\)

Symbolic differentiation:

Expand \(\mathcal{L}\) as function of inputs, differentiate

Example with 3 layers:

Applying chain rule symbolically:

Problem: Expression size grows exponentially

• Layer \(L\): \(O(2^L)\) terms due to chain rule expansion
• For \(L=50\): \(2^{50} \approx 10^{15}\) terms
• Infeasible to store or compute

Numerical differentiation:

For each parameter \(w_{ij}\):

Requires 2 forward passes per parameter

Example network:

• Layer 1: 784 → 256 (200,704 parameters)
• Layer 2: 256 → 128 (32,768 parameters)
• Layer 3: 128 → 10 (1,280 parameters)

Total parameters: \(n = 234{,}752\)

Gradient computation cost:

• Numerical: \(2n = 469{,}504\) forward passes
• Backpropagation: 3 forward passes

Speedup: \(156{,}501\times\)

Modern networks:

• ResNet-50: 25M parameters
• GPT-3: 175B parameters
• Numerical differentiation completely infeasible

Must reuse intermediate computations

Both approaches fail:

• Symbolic: Exponential expression growth
• Numerical: Linear cost in parameters
• Need: Constant cost independent of parameter count

Example: \(y = \sigma(wx + b)\) with \(w=2, b=1, x=0.5\)

Forward:

Derivative:

Example: Composition \(g(\mathbf{y}(\mathbf{x}))\) where

• \(\mathbf{y} = W\mathbf{x}\) (linear transform)
• \(g(\mathbf{y}) = \mathbf{y}^T\mathbf{y}\) (squared norm)

Forward:

Gradient w.r.t. \(\mathbf{y}\):

Gradient w.r.t. \(\mathbf{x}\) (via chain rule):

Each layer implements two operations:

forward(input):

1. Compute output from input
2. Cache input and intermediate values
3. Return output

backward(grad_output):

1. Receive gradient w.r.t. output
2. Compute gradient w.r.t. input
3. Compute gradient w.r.t. parameters
4. Return gradient w.r.t. input

Example: Linear layer

class Linear:
    def forward(self, a_prev):
        self.a_prev = a_prev  # cache
        self.z = W @ a_prev + b
        return self.z

    def backward(self, grad_z):
        grad_W = grad_z @ a_prev.T
        grad_b = grad_z
        grad_a_prev = W.T @ grad_z
        return grad_a_prev

Example: Sigmoid layer

class Sigmoid:
    def forward(self, z):
        self.a = 1 / (1 + np.exp(-z))
        return self.a

    def backward(self, grad_a):
        grad_z = grad_a * self.a * (1 - self.a)
        return grad_z

Each module only needs its own inputs/outputs

No module needs global network structure

Forward: \(\mathbf{x} \xrightarrow{W^{(1)}} \mathbf{h} \xrightarrow{W^{(2)}} \hat{\mathbf{y}} \to \mathcal{L}\)

Store intermediate activations

Backward: \(\frac{\partial \mathcal{L}}{\partial W^{(1)}} \xleftarrow{} \frac{\partial \mathcal{L}}{\partial W^{(2)}} \xleftarrow{} \frac{\partial \mathcal{L}}{\partial \hat{\mathbf{y}}}\)

Update (\(\forall l = 1, \ldots, L\)):

Dimensions: \(W^{(l)} \in \mathbb{R}^{n_l \times n_{l-1}}\), \(\mathbf{a}^{(l)}, \mathbf{s}^{(l)}, \mathbf{b}^{(l)} \in \mathbb{R}^{n_l}\)

Chain rule applied systematically from output to input

Architecture: Two-layer scalar network

One scalar value per layer

Parameters:

• \(w_1 = 0.5\), \(b_1 = 0\)
• \(w_2 = -1\), \(b_2 = 0.5\)

Data:

• Input: \(x = 2\)
• Target: \(y = 1\)

Goal: Compute all gradients

Forward values computed left to right

Layer 1:

Layer 2:

Loss (binary cross-entropy, \(y=1\)):

Sigmoid evaluation at specific pre-activation values

Gradient w.r.t. \(\hat{y}\):

Through sigmoid (\(\sigma'(z) = \sigma(z)(1-\sigma(z))\)):

Chain rule:

Weight gradient:

Define: \(\delta^{(l)} \equiv \frac{\partial \mathcal{L}}{\partial s^{(l)}}\) (gradient w.r.t. pre-activation)

Why useful: Appears repeatedly in gradient computation

For our network:

Output layer:

Hidden layer:

Weight gradients simplify:

Gradient flows back through weight:

Through sigmoid:

Weight gradient:

All gradients:

• \(\frac{\partial \mathcal{L}}{\partial w_2} = -0.408\), \(\frac{\partial \mathcal{L}}{\partial b_2} = \delta^{(2)} = -0.558\)
• \(\frac{\partial \mathcal{L}}{\partial w_1} = 0.220\), \(\frac{\partial \mathcal{L}}{\partial b_1} = \delta^{(1)} = 0.110\)

Gradients propagate backward, multiplying at each stage

Problem 1: Initialize gradient w.r.t. pre-activation

How to compute \(\frac{\partial \mathcal{L}}{\partial s^{(L)}}\) at output layer?

Problem 2: Propagate gradient backward one layer

Given \(\frac{\partial \mathcal{L}}{\partial s^{(l+1)}}\), compute \(\frac{\partial \mathcal{L}}{\partial s^{(l)}}\)

Problem 3: Compute parameter gradients

Given \(\frac{\partial \mathcal{L}}{\partial s^{(l)}}\), compute \(\frac{\partial \mathcal{L}}{\partial w_l}\) and \(\frac{\partial \mathcal{L}}{\partial b_l}\)

Using \(\delta^{(l)} \equiv \frac{\partial \mathcal{L}}{\partial s^{(l)}}\):

Problem 1: Compute \(\delta^{(L)}\)

Problem 2: Compute \(\delta^{(l)}\) from \(\delta^{(l+1)}\)

Problem 3: Compute gradients from \(\delta^{(l)}\)

Architecture: Two hidden units

Parameters: \(w_1 = 0.5, w_2 = -0.3, w_3 = 1, w_4 = 1\), all biases zero

Data: \(x = 1\), target \(t = 0.5\)

Forward:

\(h_1 = \sigma(0.5) = 0.622\)

\(h_2 = \sigma(-0.3) = 0.426\)

\(y = 0.622 + 0.426 = 1.048\)

Loss: \(\mathcal{L} = \frac{1}{2}(1.048 - 0.5)^2 = 0.150\)

Backward: \(\frac{\partial \mathcal{L}}{\partial y} = 1.048 - 0.5 = 0.548\)

Multiple gradient paths converge at \(x\)

Multivariate chain rule:

Two paths from \(\mathcal{L}\) to \(x\):

Path 1 contribution:

Path 2 contribution:

Total gradient:

Analytical gradient matches numerical

Loss and activation functions:

Loss (binary cross-entropy):

Sigmoid activation:

Derivatives:

Loss derivative:

Sigmoid derivative:

Backpropagation formulas:

Define: \(\delta^{(l)} = \frac{\partial \mathcal{L}}{\partial s^{(l)}}\)

Output layer:

Hidden layers:

Parameter updates:

Each gradient: upstream \(\times\) local derivative

Dimensions:

• Input: \(\mathbf{x} \in \mathbb{R}^3\)
• Hidden: \(\mathbf{h} \in \mathbb{R}^4\)
• Output: \(\mathbf{y} \in \mathbb{R}^2\) (2-class example)

Parameters:

Layer 1:

• \(W^{(1)} \in \mathbb{R}^{4 \times 3}\): 12 weights
• \(\mathbf{b}^{(1)} \in \mathbb{R}^4\): 4 biases

Layer 2:

• \(W^{(2)} \in \mathbb{R}^{2 \times 4}\): 8 weights
• \(\mathbf{b}^{(2)} \in \mathbb{R}^2\): 2 biases

Total: 26 parameters

Forward pass:

Fully connected: every unit in one layer connects to every unit in next layer

Compact notation:

Expanded (element-wise) (3 → 4 example):

Which weights affect given output?

Element \(z_i^{(1)}\) depends on:

All inputs: \(x_1, x_2, x_3\)

One row of \(W^{(1)}\): \(w_{i1}^{(1)}, w_{i2}^{(1)}, w_{i3}^{(1)}\)

One bias: \(b_i^{(1)}\)

Gradient \(\frac{\partial \mathcal{L}}{\partial w_{ij}^{(1)}}\) affects only \(z_i^{(1)}\)

Rest of backprop: how changes in \(z_i^{(1)}\) affect loss \(\mathcal{L}\)

Layer 1:

Pre-activation:

Dimensions:

Activation (element-wise):

Layer 2:

Pre-activation:

Dimensions:

Softmax (probability distribution):

where \([\text{softmax}(\mathbf{s})]_i = \frac{e^{s_i}}{\sum_j e^{s_j}}\)

Note: Each output depends on all inputs, i.e., not element-wise activation

Example computation:

Reminder: Matrix multiplication requires dimension compatibility

Problem 2 (scalar): Propagate \(\delta\) backward one layer

Three scalar multiplications

Problem 2 (vector): Propagate \(\boldsymbol{\delta}\) backward

Components:

• \(\boldsymbol{\delta}^{(l+1)} \in \mathbb{R}^{n_{l+1}}\) (vector)
• \(W^{(l+1)} \in \mathbb{R}^{n_{l+1} \times n_l}\) (matrix)
• \(\sigma'(\mathbf{s}^{(l)}) \in \mathbb{R}^{n_l}\) (vector)

How do these combine?

Problem 3 (scalar): Weight gradient

Problem 3 (vector): Weight gradient matrix

Dimensions: \(\mathbb{R}^{n_l \times n_{l-1}}\) required

Scalar → Vector translation:

Multiplication (\(\cdot\)) → Matrix multiply or element-wise (\(\odot\))?

Example (3 → 4 → 2 network):

Output layer: \(\boldsymbol{\delta}^{(2)} \in \mathbb{R}^2\) computed

Hidden layer: \(\boldsymbol{\delta}^{(1)} \in \mathbb{R}^4\) = ?

Inputs available:

• \(\boldsymbol{\delta}^{(2)} = [d_1^{(2)}, d_2^{(2)}]^T\) (2 × 1)
• \(W^{(2)} \in \mathbb{R}^{2 \times 4}\)
• \(\sigma'(\mathbf{s}^{(1)}) \in \mathbb{R}^4\) (4 × 1)

Need output: 4 × 1 vector

Matrix dimensions suggest: \((W^{(2)})^T \boldsymbol{\delta}^{(2)}\) gives 4 × 1

But how does \(\sigma'\) combine? Element-wise or matrix?

Need systematic framework for vector derivatives

Jacobian matrix: All partial derivatives

For \(\mathbf{y} = f(\mathbf{x})\) where \(\mathbf{y} \in \mathbb{R}^m\), \(\mathbf{x} \in \mathbb{R}^n\):

Linear layer:

Element-wise activation:

Diagonal because \(\frac{\partial a_i}{\partial s_j} = 0\) for \(i \neq j\)

Jacobian structure reflects dependencies

Scalar chain rule:

For \(\mathcal{L}(f(g(x)))\):

Vector chain rule:

For \(\mathcal{L}(\mathbf{a}(\mathbf{s}(\mathbf{x})))\) where \(\mathcal{L}: \mathbb{R}^n \to \mathbb{R}\):

Transpose appears from chain rule!

For our network:

where \(\boldsymbol{\delta}^{(l)} = \frac{\partial \mathcal{L}}{\partial \mathbf{s}^{(l)}}\)

Dimension verification:

Forward (layer \(l\)):

Backward:

Example: Layer 2 → Layer 1

\(W^{(2)} \in \mathbb{R}^{2 \times 4}\), \(\boldsymbol{\delta}^{(2)} \in \mathbb{R}^{2}\)

Transpose ensures dimension compatibility

Denominator layout (this course)

• Rows = outputs → \(J \in \mathbb{R}^{m \times n}\)

• Chain rule: \(\nabla_\mathbf{x} \mathcal{L} = \left(\frac{\partial \mathbf{y}}{\partial \mathbf{x}}\right)^T \nabla_\mathbf{y} \mathcal{L}\)
• Dimensions: \([n \times 1] = [n \times m][m \times 1]\)
• Transpose needed

Numerator layout (alternative)

• Rows = inputs → \(J \in \mathbb{R}^{n \times m}\)

• Chain rule: \(\nabla_\mathbf{x}^T \mathcal{L} = \nabla_\mathbf{y}^T \mathcal{L} \cdot \frac{\partial \mathbf{y}}{\partial \mathbf{x}^T}\)
• No transpose — but gradient is a row vector

Hadamard product (element-wise multiply): \(\odot\)

Example:

Connection to diagonal matrix:

where \(\text{diag}(\mathbf{a})\) puts vector on diagonal:

Used in backprop to apply element-wise activation derivatives

Define: \(\boldsymbol{\delta}^{(l)} = \frac{\partial \mathcal{L}}{\partial \mathbf{s}^{(l)}} \in \mathbb{R}^{n_l}\)

Vector of error signals at layer \(l\)

Output layer (softmax + cross-entropy):

For \(\mathbf{y}\) one-hot and \(\mathcal{L} = -\log(a_k^{(L)})\) where \(y_k = 1\):

Hidden layers:

where \(\odot\) is Hadamard (element-wise) product

Convenient since element-wise activation has diagonal Jacobian (zero off-diagonal)

Dimension check:

Matrix-vector multiply, then element-wise multiply

Example: 2-layer network

Output delta (\(n_2 = 2\)):

(from \(\mathbf{a}^{(2)} - \mathbf{y}\) with \(\mathbf{y} = [0, 1]^T\))

Hidden delta (\(n_1 = 4\)):

Scalar to matrix derivation:

Layer computation: \(s_i^{(l)} = \sum_{j=1}^{n_{l-1}} w_{ij}^{(l)} a_j^{(l-1)} + b_i^{(l)}\)

Chain rule:

Matrix form (all elements):

Recognize outer product:

Dimensions: \([n_l \times 1][1 \times n_{l-1}] = [n_l \times n_{l-1}]\) ✓

Bias gradient:

Setup:

x = np.array([1.0, 0.5, -0.5])
y = np.array([0, 1])  # one-hot

W1 = np.array([[0.1, 0.2, -0.1],
               [0.3, -0.2, 0.1],
               [-0.1, 0.1, 0.2],
               [0.2, 0.3, -0.3]])
b1 = np.array([0.1, -0.1, 0.0, 0.2])

W2 = np.array([[0.5, -0.3, 0.2, 0.1],
               [-0.2, 0.4, -0.1, 0.3]])
b2 = np.array([0.0, 0.1])

Forward:

Loss: \(\mathcal{L} = -\log(0.491) = 0.711\)

Backward:

Gradients:

Single sample: \(\mathbf{x} \in \mathbb{R}^d\)

Batch of \(m\) samples: \(X \in \mathbb{R}^{m \times d}\)

Samples as rows:

Forward pass (layer \(l\)):

where \(A^{(l-1)} \in \mathbb{R}^{m \times n_{l-1}}\)

Bias broadcast: add \(\mathbf{b}^{(l)}\) to each row

Activation: Element-wise on matrix

Dimension check:

Backward pass:

Delta for batch: \(\Delta^{(l)} \in \mathbb{R}^{m \times n_l}\)

Each row is delta for one sample

Weight gradient (average over batch):

Bias gradient:

Sum deltas across batch, average

For each sample \(i = 1, \ldots, m\) in batch:

Forward pass:

Backward pass:

Accumulate gradients:

Single SGD update after processing batch:

Matrix form (all samples stacked):

where \(\Delta^{(l)} \in \mathbb{R}^{m \times n_l}\) stacks all \(\boldsymbol{\delta}_i^{(l)}\) as rows

Same result, different notation

Batch of 3 samples:

Forward (Layer 1, \(W^{(1)} \in \mathbb{R}^{4 \times 3}\)):

Backward:

Output delta (3 samples × 2 classes):

Weight gradient:

Average gradient across 3 samples

Why batch:

• GPU matrix multiply: \(O(mn_ln_{l-1})\) for batch
• 3 separate forwards: \(3 \times O(n_ln_{l-1})\)
• Same asymptotic cost, but batching uses optimized BLAS
• Memory access patterns favor contiguous batch data

Input: Network \(\{W^{(l)}, \mathbf{b}^{(l)}\}_{l=1}^L\), data \((\mathbf{x}, \mathbf{y})\)

Output: Gradients \(\{\nabla W^{(l)}, \nabla \mathbf{b}^{(l)}\}_{l=1}^L\)

Forward pass:

a⁽⁰⁾ ← x
for l = 1 to L:
  s⁽ˡ⁾ ← W⁽ˡ⁾ a⁽ˡ⁻¹⁾ + b⁽ˡ⁾
  a⁽ˡ⁾ ← σ⁽ˡ⁾(s⁽ˡ⁾)
  store: a⁽ˡ⁻¹⁾, s⁽ˡ⁾, a⁽ˡ⁾

Backward pass:

δ⁽ᴸ⁾ ← ∇_a⁽ᴸ⁾ 𝓛(a⁽ᴸ⁾, y)
for l = L down to 1:
  δ⁽ˡ⁾ ← (W⁽ˡ⁺¹⁾)ᵀ δ⁽ˡ⁺¹⁾ ⊙ σ'(s⁽ˡ⁾)

Gradient computation:

for l = 1 to L:
  ∇W⁽ˡ⁾ ← δ⁽ˡ⁾ (a⁽ˡ⁻¹⁾)ᵀ
  ∇b⁽ˡ⁾ ← δ⁽ˡ⁾

Single forward pass + single backward pass computes all gradients

Historical context:

Rumelhart, Hinton, Williams (1986) paper: “Learning representations by back-propagating errors”

Algorithm existed earlier (Werbos 1974, others) but 1986 paper demonstrated effectiveness for neural networks

Name origin:

Gradients propagate backward through network:

1. Compute loss at output
2. Gradient flows from loss back to earlier layers
3. Each layer receives gradient from layer ahead
4. Apply chain rule locally
5. Pass gradient to layer behind

Direction: Output \(\to\) Input (opposite of data flow)

Data flow:

Forward: \(\mathbf{x} \to \mathbf{a}^{(1)} \to \mathbf{a}^{(2)} \to \cdots \to \mathbf{a}^{(L)} \to \mathcal{L}\)

Backward: \(\nabla_{\mathbf{x}} \mathcal{L} \leftarrow \boldsymbol{\delta}^{(1)} \leftarrow \boldsymbol{\delta}^{(2)} \leftarrow \cdots \leftarrow \boldsymbol{\delta}^{(L)} \leftarrow 1\)

Gradients propagate in reverse order (output \(\to\) input)

Common misconception: “Backpropagation of errors”

Correct: Backpropagation of gradients

Delta values \(\boldsymbol{\delta}^{(l)}\) are not errors—they are partial derivatives \(\frac{\partial \mathcal{L}}{\partial \mathbf{s}^{(l)}}\)

Forward pass (single sample):

Layer \(l\): Matrix multiply \(W^{(l)}\mathbf{a}^{(l-1)}\)

Cost: \(O(n_l \cdot n_{l-1})\) multiplications

Activation: \(O(n_l)\) (element-wise)

Total forward: \(\sum_{l=1}^L O(n_l \cdot n_{l-1})\)

Backward pass:

Delta propagation: \((W^{(l+1)})^T \boldsymbol{\delta}^{(l+1)}\)

Cost: \(O(n_l \cdot n_{l+1})\) (same as forward)

Weight gradient: \(\boldsymbol{\delta}^{(l)} (\mathbf{a}^{(l-1)})^T\)

Cost: \(O(n_l \cdot n_{l-1})\) (outer product)

Total backward: \(2 \times \sum_{l=1}^L O(n_l \cdot n_{l-1})\)

Result: Backward cost = 2× Forward cost

(Delta propagation + Weight gradients)

Total training step: Forward + Backward = 3× forward pass

Example: 3-layer network

\(784 \to 256 \to 128 \to 10\)

Forward operations:

• Layer 1: \(784 \times 256 = 200{,}704\)
• Layer 2: \(256 \times 128 = 32{,}768\)
• Layer 3: \(128 \times 10 = 1{,}280\)
• Total: \(234{,}752\) multiplications

Backward operations:

• Delta 3→2: \(128 \times 10 = 1{,}280\)
• Delta 2→1: \(256 \times 128 = 32{,}768\)
• Delta 1→0: \(784 \times 256 = 200{,}704\)
• Gradients: Same counts as forward
• Total: \(2 \times 234{,}752 = 469{,}504\)

Total: \(3 \times\) forward pass operations

Compare to numerical differentiation: \(2 \times 234{,}752 = 469{,}504\) forward passes

Speedup: \(\frac{469{,}504}{3} \approx 156{,}500\times\)

Parameters: \(\sum_{l=1}^L n_l \cdot n_{l-1}\)

Must store \(W^{(l)}\) and \(\mathbf{b}^{(l)}\) for all layers

Gradients: Same size as parameters

Store \(\nabla W^{(l)}\) and \(\nabla \mathbf{b}^{(l)}\)

Activations: \(\sum_{l=1}^L n_l \cdot m\)

Store \(\mathbf{a}^{(l)}\) and \(\mathbf{s}^{(l)}\) for batch size \(m\)

Needed for backward pass

Memory scaling:

Parameters: Fixed (independent of batch size)

Activations: Linear in batch size

Activations dominate for large batches

Example: ResNet-50, batch 32, ImageNet (224×224 input)

Parameters:

• \(W^{(l)}\), \(\mathbf{b}^{(l)}\): 25M parameters
• Storage: \(25 \times 10^6 \times 4\) bytes = 100 MB

Gradients:

• \(\nabla W^{(l)}\), \(\nabla \mathbf{b}^{(l)}\): 25M values
• Storage: 100 MB

Activations (batch 32):

Activation memory varies by layer (spatial dimensions decrease, channels increase):

• Early layers: \(56 \times 56 \times 256 \times 32 \times 4\) bytes ≈ 65 MB
• Middle layers: \(28 \times 28 \times 512 \times 32 \times 4\) bytes ≈ 33 MB
• Deep layers: \(14 \times 14 \times 1024 \times 32 \times 4\) bytes ≈ 26 MB

Forward activations: ~200 MB, Backward gradients: ~200 MB

Total memory (batch 32): 100 + 100 + 400 = 600 MB

Scaling with batch size:

• Batch 64: Activations ≈ 800 MB, total ≈ 1000 MB
• Batch 128: Activations ≈ 1600 MB, total ≈ 1800 MB
• Batch 256: Activations ≈ 3200 MB, total ≈ 3400 MB

For large batches, activations dominate memory usage

Algorithm unchanged—only \(\sigma'(\mathbf{s}^{(l)})\) differs per layer

Sigmoid: \(\sigma(s) = \frac{1}{1+e^{-s}}\)

Can compute from stored activation: \(a(1-a)\)

Tanh: \(\sigma(s) = \tanh(s)\)

Also from activation: \(1 - a^2\)

ReLU: \(\sigma(s) = \max(0, s)\)

Indicator function (discontinuous at 0)

Leaky ReLU: \(\sigma(s) = \max(\alpha s, s)\) with \(\alpha = 0.01\)

ReLU advantages:

• Sparse gradients (50% zeros)
• No vanishing gradient for active units (\(s > 0\))
• Cheap to compute

Element-wise activations (sigmoid, tanh, ReLU):

Each output depends only on corresponding input

Jacobian is diagonal:

Delta update uses Hadamard product:

Softmax (non-element-wise):

Each output depends on all inputs

Jacobian is full matrix:

Delta initialization requires matrix-vector product:

Special case (softmax + cross-entropy):

Jacobian multiplication simplifies to subtraction

Standard

Regularized

Objective:

Gradient:

Objective:

Gradient:

L2 regularization (weight decay):

Frobenius norm: \(\|W\|_F^2 = \sum_{i,j} w_{ij}^2\)

Gradient:

Modified update:

Equivalent to weight decay: \(W^{(l)} \leftarrow (1 - 2\eta\lambda)W^{(l)} - \eta \boldsymbol{\delta}^{(l)}(\mathbf{a}^{(l-1)})^T\)

L1 regularization:

L1 norm: \(\|W\|_1 = \sum_{i,j} |w_{ij}|\)

Subgradient:

Modified update:

Promotes sparsity: weights shrink toward zero

Bias terms typically not regularized

Architecture: MNIST digit classifier

Input: 28×28 grayscale images = 784 pixels

Output: 10 class probabilities

Parameters per layer:

• \(W^{(1)}\): \(256 \times 784 = 200{,}704\)
• \(W^{(2)}\): \(128 \times 256 = 32{,}768\)
• \(W^{(3)}\): \(64 \times 128 = 8{,}192\)
• \(W^{(4)}\): \(32 \times 64 = 2{,}048\)
• \(W^{(5)}\): \(10 \times 32 = 320\)

Biases: \(256 + 128 + 64 + 32 + 10 = 490\)

Total: \(244{,}032\) weights + \(490\) biases = \(244{,}522\) parameters

Backprop computes all 244,522 gradients in 2 passes (1 forward + 1 backward)

Delta magnitude at layer \(l\):

Rough approximation ignoring vector structure

Sigmoid network:

Maximum derivative: \(\max_s \sigma'(s) = 0.25\) at \(s=0\)

Typical values: \(\sigma'(s) \approx 0.2\) in practice

After 10 layers: \((0.2)^{10} \approx 10^{-7}\)

Gradients vanish exponentially with depth

Early layers receive near-zero gradients, fail to train

ReLU network:

Derivative: \(\text{ReLU}'(s) \in \{0, 1\}\)

Active units (\(s > 0\)): gradient = 1 (no shrinking)

Dead units (\(s \leq 0\)): gradient = 0 (propagation stops)

Better gradient flow if units stay active

Sigmoid/tanh: Exponential decay

ReLU: Better but still degrades

Nodes: Operations (MatMul, Add, Sigmoid, etc.)

Edges: Tensors flowing between operations

Example: 2-layer network decomposed

Forward: \(\mathbf{x} \to W^{(1)}\mathbf{x} \to + \mathbf{b}^{(1)} \to \sigma \to W^{(2)} \to + \mathbf{b}^{(2)} \to \sigma \to \mathcal{L}\)

Each arrow represents data dependency

Directed: Information flows one direction (forward)

Acyclic: No loops (feedforward network)

Topological order: Can order nodes so all inputs come before outputs

Forward pass: Traverse in topological order

Backward pass: Traverse in reverse topological order

Benefits:

• Modular: Each operation self-contained
• Composable: Build complex functions from primitives
• Automatic: Can differentiate any graph mechanically

Each node: Implements forward and backward

class Operation:
    def forward(self, inputs):
        # Compute output from inputs
        # Cache inputs for backward
        self.cache = inputs
        return self.compute(inputs)

    def backward(self, grad_output):
        # Compute gradient w.r.t. inputs
        # Use cached values
        return self.local_gradient(
            grad_output, self.cache)

No global knowledge required

Node only needs:

• How to compute output from inputs (forward)
• How to compute input gradients from output gradient (backward)

Chain rule automatic:

Graph framework connects local gradients

Node A → Node B: \(\frac{\partial \mathcal{L}}{\partial \text{input}_A} = \frac{\partial \text{output}_B}{\partial \text{input}_A}^T \frac{\partial \mathcal{L}}{\partial \text{output}_B}\)

Framework handles composition

Forward: \(\mathbf{y} = A\mathbf{x}\)

Input: Matrix \(A \in \mathbb{R}^{m \times n}\), vector \(\mathbf{x} \in \mathbb{R}^n\)

Output: \(\mathbf{y} \in \mathbb{R}^m\)

Backward: Given \(\frac{\partial \mathcal{L}}{\partial \mathbf{y}}\), compute gradients w.r.t. inputs

Gradient w.r.t. \(\mathbf{x}\):

Dimension: \([n \times 1] = [n \times m][m \times 1]\)

Gradient w.r.t. \(A\):

Dimension: \([m \times n] = [m \times 1][1 \times n]\)

Implementation:

class MatMul:
    def forward(self, A, x):
        self.A, self.x = A, x
        return A @ x

    def backward(self, grad_y):
        grad_x = self.A.T @ grad_y
        grad_A = np.outer(grad_y, self.x)
        return grad_A, grad_x

Numerical example:

Forward:

Backward (assume \(\frac{\partial \mathcal{L}}{\partial \mathbf{y}} = \begin{bmatrix} 0.8 \\ -0.5 \end{bmatrix}\)):

Forward: \(z = x + y\)

Inputs: Scalars, vectors, or matrices (same shape)

Output: Same shape as inputs

Backward: Given \(\frac{\partial \mathcal{L}}{\partial z}\)

Addition distributes gradient to both inputs:

Gradient copies to each input (no modification)

Broadcast addition: \(\mathbf{z} = \mathbf{x} + b\) where \(b\) scalar

Forward: Add \(b\) to each element of \(\mathbf{x}\)

Backward:

Gradient w.r.t. scalar sums gradients from all elements

Gradient distribution rule:

• Fork (1→many): Copy gradient
• Join (many→1): Sum gradients

Forward: \(\mathbf{a} = \sigma(\mathbf{s})\)

Apply function element-wise: \(a_i = \sigma(s_i)\)

Backward: Given \(\frac{\partial \mathcal{L}}{\partial \mathbf{a}}\)

Hadamard product (element-wise multiply)

Each \(\frac{\partial \mathcal{L}}{\partial s_i} = \frac{\partial \mathcal{L}}{\partial a_i} \cdot \sigma'(s_i)\)

Different activations:

Sigmoid: \(\sigma'(s) = \sigma(s)(1-\sigma(s))\) (can compute from \(a\))

ReLU: \(\sigma'(s) = \mathbb{1}_{s > 0}\) (needs \(s\), not just \(a\))

Implementation:

class Sigmoid:
    def forward(self, s):
        self.a = 1 / (1 + np.exp(-s))
        return self.a

    def backward(self, grad_a):
        # Use cached activation
        grad_s = grad_a * self.a * (1 - self.a)
        return grad_s

Fork (one input, multiple outputs):

Single value used by multiple operations

Example: \(x \to f(x)\) and \(x \to g(x)\)

Backward: Gradients from all paths sum

Each path contributes independently

Join (multiple inputs, one output):

Multiple values combine into single operation

Example: \(z = f(x, y)\)

Backward: Each input gets its gradient

Separate gradients for each input

Skip connections, attention mechanisms: Multiple paths converge

Static graph: Structure fixed before execution

Build graph once, execute many times

TensorFlow 1.x, compiled frameworks

Optimization possible (graph fusion, memory planning)

Cannot change based on data

Dynamic graph: Structure built during forward pass

Graph structure can depend on data

PyTorch, TensorFlow 2.x (eager mode)

Example: Variable-length sequences

RNN processing sentence: Graph depth = sequence length

Different inputs \(\to\) different graphs

Backward pass: Follow actual graph from forward

Only differentiate paths that were executed

Benefits:

• Control flow (if/while in forward)
• Data-dependent architecture
• Easier debugging (standard Python)

Cost: Less optimization opportunity

PyTorch example:

import torch

# Forward pass (builds graph)
x = torch.tensor([1.0, 2.0],
                 requires_grad=True)
W = torch.tensor([[0.5, 0.3],
                  [0.2, -0.4]],
                 requires_grad=True)
y = W @ x
loss = y.sum()

# Backward pass (automatic)
loss.backward()

# Gradients computed
print(x.grad)  # ∂L/∂x
print(W.grad)  # ∂L/∂W

Framework tracks all operations on tensors

Builds computation graph automatically

Backward computes all gradients

User never writes backward: Framework does it

Only need to define forward computation

How it works:

Each operation on tensor:

1. Computes forward result
2. Registers itself in computation graph
3. Stores backward function

# Conceptual implementation
class Tensor:
    def __init__(self, data, grad_fn=None):
        self.data = data
        self.grad = None
        self.grad_fn = grad_fn  # Backward

    def backward(self):
        self.grad = 1.0  # Start
        # Traverse graph backward
        for op in reversed(graph):
            op.backward()

Modern frameworks:

• PyTorch: Dynamic graph, eager execution
• JAX: Functional, JIT compilation
• TensorFlow 2.x: Eager by default

All use reverse-mode autodiff (backpropagation)

Reverse mode: 1 backward pass computes gradients w.r.t. all \(n\) parameters (cost \(\approx 3\times\) forward)

Forward mode: 1 pass computes gradient w.r.t. 1 parameter (\(n\) passes for all parameters)

Loss functions have many inputs, one output → reverse mode wins

import numpy as np

class TwoLayerNet:
    def __init__(self, input_dim, hidden_dim,
                 output_dim):
        # Xavier initialization
        self.W1 = np.random.randn(
            hidden_dim, input_dim
        ) * np.sqrt(2 / input_dim)
        self.b1 = np.zeros(hidden_dim)

        self.W2 = np.random.randn(
            output_dim, hidden_dim
        ) * np.sqrt(2 / hidden_dim)
        self.b2 = np.zeros(output_dim)

        # Store forward pass values
        self.cache = {}

Example: 784 → 256 → 10 network

net = TwoLayerNet(
    input_dim=784,    # MNIST images
    hidden_dim=256,   # Hidden units
    output_dim=10     # Digit classes
)

# Parameters
# W1: 256 × 784 = 200,704
# b1: 256
# W2: 10 × 256 = 2,560
# b2: 10
# Total: 203,530 parameters

def forward(self, X):
    # X: (batch_size, input_dim)
    self.cache['A0'] = X

    # Layer 1
    self.cache['S1'] = X @ self.W1.T + self.b1
    self.cache['A1'] = sigmoid(self.cache['S1'])

    # Layer 2
    self.cache['S2'] = self.cache['A1'] @ \
                       self.W2.T + self.b2
    self.cache['A2'] = softmax(self.cache['S2'])

    return self.cache['A2']

def sigmoid(s):
    return 1 / (1 + np.exp(-s))

def softmax(s):
    # Subtract max for numerical stability
    s_shift = s - np.max(s, axis=1,
                         keepdims=True)
    exp_s = np.exp(s_shift)
    return exp_s / np.sum(exp_s, axis=1,
                          keepdims=True)

def backward(self, y_true):
    m = y_true.shape[0]

    # Output layer (softmax + cross-entropy)
    delta2 = (self.cache['A2'] - y_true) / m
    self.dW2 = delta2.T @ self.cache['A1']
    self.db2 = np.sum(delta2, axis=0)

    # Hidden layer
    A1 = self.cache['A1']
    delta1 = (delta2 @ self.W2) * \
             A1 * (1 - A1)
    self.dW1 = delta1.T @ self.cache['A0']
    self.db1 = np.sum(delta1, axis=0)

def update_parameters(self, learning_rate=0.1):
    self.W2 -= learning_rate * self.dW2
    self.b2 -= learning_rate * self.db2
    self.W1 -= learning_rate * self.dW1
    self.b1 -= learning_rate * self.db1

Complete: 30 lines for forward + backward + update

All 203,530 gradients computed in one backward pass

# Generate synthetic data
np.random.seed(42)
n_samples = 1000
n_features = 20
n_classes = 5

# Random features
X = np.random.randn(n_samples, n_features)

# Random labels (one-hot)
labels = np.random.randint(0, n_classes,
                           n_samples)
y = np.zeros((n_samples, n_classes))
y[np.arange(n_samples), labels] = 1

# Initialize network
net = TwoLayerNet(
    input_dim=n_features,
    hidden_dim=50,
    output_dim=n_classes
)

# Train
losses = []
for epoch in range(500):
    # Forward
    predictions = net.forward(X)
    loss = -np.mean(np.sum(
        y * np.log(predictions + 1e-10),
        axis=1
    ))
    losses.append(loss)

    # Backward
    net.backward(y)

    # Update
    net.update_parameters(learning_rate=0.1)

Loss: \(1.609 \to 1.456\) (random labels, cannot fit perfectly)

Finite difference approximation:

Centered difference: \(O(\epsilon^2)\) error

Choice of \(\epsilon\): \(10^{-5}\) to \(10^{-7}\)

Too large: truncation error from Taylor expansion

Too small: numerical cancellation (roundoff error)

Implementation:

def gradient_check(net, X, y, eps=1e-5):
    # Analytical gradient
    net.forward(X)
    net.backward(y)
    analytic = net.dW1.copy()

    # Numerical gradient
    def loss_fn(W):
        net.W1 = W.reshape(net.W1.shape)
        pred = net.forward(X)
        return -np.mean(np.sum(
            y * np.log(pred + 1e-10), axis=1
        ))

    W_flat = net.W1.flatten()
    numeric = numerical_gradient(
        loss_fn, W_flat, eps
    ).reshape(net.W1.shape)

    # Relative error
    diff = np.linalg.norm(analytic - numeric)
    scale = np.linalg.norm(analytic) + \
            np.linalg.norm(numeric)
    return diff / scale

Relative error metric:

Scale-invariant comparison

Thresholds:

• \(< 10^{-7}\): Implementation correct
• \(10^{-7}\) to \(10^{-5}\): Acceptable (check carefully)
• \(> 10^{-5}\): Bug in implementation

Sweet spot at \(\epsilon \approx 10^{-5}\) to \(10^{-7}\): U-shaped curve from competing error sources

Buggy implementation: Missing sigmoid derivative

def backward_buggy(self, y_true):
    m = y_true.shape[0]

    delta2 = (self.cache['A2'] - y_true) / m
    self.dW2 = delta2.T @ self.cache['A1']
    self.db2 = np.sum(delta2, axis=0)

    # BUG: Missing activation derivative
    delta1 = (delta2 @ self.W2)  # Wrong!
    # Should be:
    # delta1 = (delta2 @ self.W2) * A1 * (1-A1)

    self.dW1 = delta1.T @ self.cache['A0']
    self.db1 = np.sum(delta1, axis=0)

Gradient check result:

error = gradient_check(buggy_net, X, y)
print(f"Relative error: {error:.2e}")
# Output: Relative error: 7.34e-01

Error \(\sim 0.7\): Implementation wrong

Correct implementation: Error < \(10^{-7}\)

Correct: points on diagonal. Buggy: systematic deviation — missing \(\sigma'\) distorts every gradient element

784→256→128→10, float32 (4 bytes per value)

Parameters (fixed, independent of batch):

\(W^{(1)}\): \(256 \times 784 = 200{,}704\) values → 803 KB

\(W^{(2)}\): \(128 \times 256 = 32{,}768\) values → 131 KB

\(W^{(3)}\): \(10 \times 128 = 1{,}280\) values → 5 KB

Biases: \(394\) values → 1.6 KB

Total parameters: \(235{,}146 \times 4 = 940\) KB

Gradients: Must store \(\nabla W^{(l)}\) same shape as \(W^{(l)}\) → another 940 KB

Activations (per sample, needed for backward):

\(\mathbf{s}^{(l)}\) and \(\mathbf{a}^{(l)}\) at each layer: \(2 \times (256 + 128 + 10) = 788\) values

Batch \(m = 32\): \(788 \times 32 \times 4 = 101\) KB

Total (batch 32): \(940 + 940 + 101 \approx 2\) MB

For this small network, parameters dominate. For large networks the picture inverts: GPT-2 (1.5B params) uses 12 GB for parameters+gradients but ~50 GB for activations at batch 32

Experiment: Train 10-layer sigmoid network

Monitor \(\|\nabla W^{(l)}\|\) at each layer during training

Network: 100→100→…→100→10 (10 layers, 100 units each)

Data: MNIST (784→100 via projection)

Training: 1000 iterations, batch size 64, learning rate 0.01

Observation:

Early layers (1-3): Gradient norm \(\sim 10^{-6}\)

Late layers (8-10): Gradient norm \(\sim 10^{-2}\)

Ratio: \(10^4\) difference across network

Early layers barely update

Cause:

Sigmoid: \(\max |\sigma'(s)| = 0.25\)

Product of 9 terms: \((0.25)^9 \approx 4 \times 10^{-6}\)

Gradients vanish exponentially with depth for sigmoid

Experiment: Same 10-layer network with different activations

Compare gradient flow:

• Sigmoid: \(\sigma'(s) = \sigma(s)(1-\sigma(s))\), max = 0.25
• Tanh: \(\tanh'(s) = 1 - \tanh^2(s)\), max = 1.0
• ReLU: \(\text{ReLU}'(s) = \mathbb{1}_{s>0}\), value = 1 when active

Measurement: \(\|\nabla W^{(1)}\|\) after 100 training steps

Results:

• Sigmoid: \(3.2 \times 10^{-7}\) (vanished)
• Tanh: \(1.4 \times 10^{-4}\) (small but usable)
• ReLU: \(2.1 \times 10^{-2}\) (healthy)

Training loss (after 1000 steps):

• Sigmoid: 2.15 (barely improved from 2.30)
• Tanh: 1.82 (modest improvement)
• ReLU: 0.45 (converged)

ReLU preserves gradients through depth, making deep networks trainable

ReLU: Best gradient preservation through depth

Experiment: Train 784→256→128→10 network on MNIST

Hardware: NVIDIA V100 GPU (16 GB)

Batch sizes: 32, 64, 128, 256

Measurements (milliseconds per training step):

Backward consistently \(\approx\) 2× forward time

Throughput peaks at batch 256 (GPU saturation)

Memory (batch 256):

Parameters: 0.9 MB

Gradients: 0.9 MB

Activations: 0.4 MB

Total: 2.2 MB (tiny for modern GPU)

Backward time ≈ 2× forward (matches expected)

LMS adaptive filter (linear):

Gradient: \(\frac{\partial \hat{y}_t}{\partial \mathbf{w}} = \mathbf{x}_t\) (trivial for linear model)

MLP with online backpropagation:

Gradient: \(\frac{\partial f}{\partial \Theta}\) requires backpropagation (nontrivial for deep, nonlinear model)

Same conceptual algorithm:

1. Predict with current parameters
2. Measure error/loss
3. Compute gradient of prediction w.r.t. parameters
4. Update parameters opposite to gradient

What changes: Step 3 complexity

LMS: Gradient is input \(\mathbf{x}_t\) (immediate)

MLP: Gradient computed via chain rule through layers (backpropagation)

Backpropagation = systematic gradient computation for nonlinear, multilayer adaptive filtering

Enables same stochastic gradient descent framework, but for deep architectures

See EE 583 (adaptive algorithms) and stochastic optimization

Standard batch training: Stationary \(P(Y|X)\)

Accumulate gradients over dataset:

Converges to minimize \(\mathbb{E}[\mathcal{L}]\) over fixed distribution

Assumption: Data distribution doesn’t change

Online adaptation: Time-varying \(P_t(Y|X)\)

Update after each sample (no accumulation):

Tracks changing distribution if learning rate chosen properly

Learning rate controls tracking speed vs stability tradeoff

Example deployment scenario:

Train on historical data (batch mode)

Deploy in changing environment (online adaptation)

Strategy: Freeze early layers, adapt final layer only

Why this works:

Early layers: General feature extraction (stable across environments)

Final layer: Task-specific mapping (may drift with distribution shift)

Fewer parameters to adapt → faster convergence, less overfitting to noise

Backpropagation enables: Computing \(\nabla_{\Theta_{\text{final}}} \mathcal{L}_t\) efficiently even when final layer is deep in network