Stanford CS229 Machine Learning Spring 2026 Lecture 8: Neural Networks 2 (Backpropagation)

Backpropagation and the Computational Graph

Backpropagation is the fundamental algorithm used to compute the gradient of a loss function with respect to a model's parameters. In deep learning, this process is often referred to as auto-differentiation. The core technical takeaway is that for any differentiable circuit (a network composed of a sequence of arithmetic operations and elementary functions), the gradient can be computed in the same asymptotic time complexity as the forward pass.

The Complexity Theorem

If a differentiable circuit of size $n$ (where $n$ is the number of operations) computes a real-valued scalar function $f$, the gradient of $f$ with respect to its inputs can also be computed in $O(n)$ time.

In the context of neural networks:

  • Forward Pass: Evaluating the loss function for a given input.
  • Backward Pass: Computing the gradient of that loss with respect to the parameters.

Because the number of operations required to evaluate a neural network is typically proportional to the number of parameters, both the forward and backward passes operate in $O( ext{number of parameters})$ time.

Advanced Applications of Efficient Gradients

Efficient gradient computation enables several advanced machine learning techniques:

  • Second-Order Methods: While computing the full Hessian matrix (an $n imes n$ matrix) is computationally prohibitive, the Hessian-vector product can be computed efficiently in $O(n)$ time. This is achieved by computing the gradient of a function that is itself a gradient product.
  • Meta-Learning: Backpropagation can be applied to the algorithm itself. For example, one can optimize a learning rate or initialization by backpropagating through the steps of the gradient descent algorithm to minimize a final loss.

The Mechanics of the Chain Rule

Backpropagation is an iterative application of the chain rule. To understand this, consider a function where an input $z$ passes through a function $g$ to produce an intermediate variable $u$, which then passes through a function $f$ to produce a scalar output $j$.

The Backward Function

To compute the gradient of the final output $j$ with respect to the input $z$, the chain rule provides a formula: the gradient with respect to $z$ is a linear combination of the gradient with respect to the intermediate variable $u$.

Mathematically, this is expressed as a matrix multiplication: $$ rac{ ext{d}j}{ ext{d}z} = ( ext{Jacobian of } g)^T imes rac{ ext{d}j}{ ext{d}u}$$

This mechanism is "Markovian" in nature: to compute the gradient at a specific layer, you only need the gradient from the subsequent layer ($ rac{ ext{d}j}{ ext{d}u}$) and the local information of the current function $g$ and its input $z$. You do not need to know the internal details of the function $f$ that produced the subsequent gradient.

Backpropagation in Neural Network Layers

In a multi-layer network, the process involves two interleaved phases: computing gradients with respect to activations (intermediate variables) and computing gradients with respect to parameters.

1. Gradients with Respect to Activations

To find the gradient for the first layer, the algorithm must first propagate the gradient backward from the final output through all subsequent layers. This creates a sequential dependency: $ rac{ ext{d}j}{ ext{d}u_k} ightarrow rac{ ext{d}j}{ ext{d}u_{k-1}} ightarrow rac{ ext{d}j}{ ext{d}u_1}$.

2. Gradients with Respect to Parameters

Once the gradient with respect to an activation $u_i$ is known, the gradient with respect to the parameters $ heta_i$ associated with that layer can be computed independently. This allows for potential parallelization of parameter gradient updates once the activation gradients have been propagated.

Concrete Examples of Backward Functions

Matrix Multiplication (Linear Layers)

For a linear transformation $u = Wz + b$:

  • Gradient with respect to input $z$: The backward function is simply the transpose of the weight matrix multiplied by the incoming gradient: $ rac{ ext{d}j}{ ext{d}z} = W^T rac{ ext{d}j}{ ext{d}u}$.
  • Gradient with respect to weights $W$: The gradient for a specific weight $w_{ij}$ is the product of the gradient of the output it connects to and the value of the input it originates from. In matrix form, this is an outer product: $ rac{ ext{d}j}{ ext{d}W} = rac{ ext{d}j}{ ext{d}u} z^T$. This results in a rank-one matrix for a single training example.

Activation Functions (Element-wise Layers)

For an element-wise activation function $u = ext{sigma}(z)$:

  • The Jacobian is a diagonal matrix because each output $u_i$ depends only on its corresponding input $z_i$.
  • The backward pass is computed as the element-wise (Hadamard) product of the incoming gradient and the derivative of the activation function: $ rac{ ext{d}j}{ ext{d}z} = ext{sigma}'(z) ext{⊙} rac{ ext{d}j}{ ext{d}u}$.

This efficiency ensures that the backward pass for activation functions remains $O(m)$ for an $m$-dimensional vector, matching the complexity of the forward pass.

Sources