5.7 Backpropagation

This section is more technical than the rest of the course and is presented here for completeness. There will be no quiz questions associated with it; it is just the explanation of how the method works.

In the previous chapter, we already discussed that \(f_\beta(x)=\beta^\top\phi(x)\) was linear in \(\beta\), in which case \(\nabla J\) was a matrix times a residual. Here, \(f_\beta\) is a composition,

\[ x \;\to\; z^{[1]}=W^{[1]}x+b^{[1]} \;\to\; a^{[1]}=\sigma(z^{[1]}) \;\to\; \cdots \;\to\; \hat y, \]

and \(J=\frac12(\hat y-y)^2\). The chain rule still applies, but you take it from the loss back to the inputs.

On one observation the last residual is \(\hat y-y\). That number is multiplied by the local slope of \(\sigma\) and by the previous layer’s weights, layer by layer. Each layer produces two things:

  • the gradient of \(J\) with respect to its \(W,b\) (what you use to take a step) and

  • the gradient with respect to its input (what the previous layer needs). That sweep is backpropagation.

You store the forward values \(z^{[k]},a^{[k]}\) because the local slopes depend on them.

 

The only complexity fact that matters: if scoring one observation needs \(N\) operations, getting every partial of \(J\) takes \(O(N)\) operations as well, not one derivative per parameter. That is why treating \(\phi_c\) as part of \(\beta\) is practical.

 

5.7.1 The Theorem Behind

A neural net is already a finite recipe of additions, multiplications, and maps such as ReLU: you evaluate it from the inputs toward \(\hat y\), with no loops. It is also a directed acyclic graph since each node is a number, each arrow is one of those operations. Backpropagation is the statement that the same graph yields every partial of \(J\) at essentially the cost of one extra forward pass, not at \(d\) times the cost.

A differentiable circuit of size \(N\) is a directed acyclic graph of \(+\), \(-\), \(\times\), \(/\), and elementary maps (\(\mathrm{ReLU}\), \(\exp\), \(\log\),), each of which can be computed with its local derivative in constant time. The claim that makes this model class practical is that the gradient of such a circuit is essentially as cheap as the circuit.

 

Theorem (reverse-mode autodiff / cheap gradient)

Let \(f:\mathbb{R}^\ell\to\mathbb{R}\) be computed by a differentiable circuit of size \(N\), in which every elementary gate and the product of that gate’s local derivative with a scalar can be evaluated in \(O(1)\) time. Then \(\nabla f\) can be computed by a circuit of size \(O(N)\) in time \(O(N)\).

When every gate is just \(+\), \(\times\), or multiplication by a constant, the same claim has a precise form: Baur and Strassen (1983) showed that if \(f\) can be computed with \(S\) such operations, then \(f\) and \(\nabla f\) can be computed with at most \(5S\) operations. Morgenstern (1985) gave a short proof by induction backward through the circuit. Griewank (1989) extended the idea beyond polynomials, to a general list of elementary functions. What follows is that argument written on a computation graph, i.e. a multilayer perceptron.

Proof

Label nodes \(v_1,\ldots,v_N\) in topological order. Each \(v_t\) is an input coordinate or \(\varphi_t\) applied to \(O(1)\) earlier nodes (bounded fan-in). Write \(\mathrm{ch}(t)\) for the children of \(t\). The output is the scalar \(v_N=f(x)\).

The forward pass evaluates \(t=1,\ldots,N\) and stores every \(v_t\). Time and extra memory are \(O(N)\).

Define the adjoint \(\bar v_t:=\partial f/\partial v_t\), and set \(\bar v_N=1\). The chain rule reads

\[ \bar v_t =\sum_{s\in\mathrm{ch}(t)}\bar v_s\cdot\frac{\partial\varphi_s}{\partial v_t}(v_{\mathrm{pa}(s)}). \]

Each local factor depends only on stored parents of \(s\) and, by hypothesis, can be multiplied by \(\bar v_s\) in constant time. Sweeping \(t=N-1,\ldots,1\) therefore fills every adjoint after its children’s adjoints are known.

Each edge contributes one local derivative and one multiply-add, hence \(O(N)\). The input adjoints are the coordinates of \(\nabla f(x)\).

Correctness is induction down the reverse order. The base \(\bar v_N=1\) is tautological. If every child of \(t\) holds a correct adjoint, the displayed sum is the chain rule. Nodes off the path to the output stay at their initialized value \(0\). Attaching an adjoint node and \(O(1)\) extra gates to each original node produces a circuit of size \(O(N)\).

Why backpropagation?

Forward-mode autodiff pushes one directional derivative from the inputs to the output in \(O(N)\) time. The full gradient then costs \(O(\ell N)\). Reverse mode costs \(O(N)\) because the output is a scalar. For maps \(\mathbb{R}^\ell\to\mathbb{R}^m\) the costs swap. Fitting a network is \(\ell\gg m=1\): many parameters, one loss. Differentiating coordinate by coordinate is forward mode \(d\) times. Reverse mode recycles one forward tape across all coordinates.

If \(f\) is cheap, so is any scalar function of \(\nabla f\), including a one-step unrolled update \(\ell(\beta-\eta\nabla\ell(\beta))\). If \(g(x)=\langle\nabla f(x),v\rangle\), then \(\nabla g(x)=\nabla^2 f(x)\,v\) costs \(O(N+\ell)\): Hessian–vector products without forming the Hessian.

Modules, not Jacobians

If a scalar \(J\) depends on a tensor \(z\), \(\partial J/\partial z\) has the same shape as \(z\). Differentiate scalars with respect to tensors. Do not materialize the Jacobian of a vector-valued map unless there is no other option.

For \(u=g(z)\) and \(J=f(u)\),

\[ \frac{\partial J}{\partial z}=(Dg)^\top\frac{\partial J}{\partial u}. \]

The linear map \(v\mapsto(Dg)^\top v\) is the backward function \(B[g,z]\) of the module \(g\) at the stored input \(z\). A network is a composition \(J=M_k\circ\cdots\circ M_1\). Forward: store each \(u^{[i]}=M_i(u^{[i-1]})\). Backward: start from \(\partial J/\partial u^{[k]}=1\) and apply \(B[M_i,\,\cdot\,]\) to move the adjoint onto the previous activation and onto the parameters inside \(M_i\).

For \(u=Wz+b\) with incoming adjoint \(v=\partial J/\partial u\),

\[ B[\mathrm{MM},z](v)=W^\top v, \qquad B[\mathrm{MM},W](v)=vz^\top, \qquad B[\mathrm{MM},b](v)=v. \]

The middle identity is the one people check once. Entrywise, \(\partial u_k/\partial W_{ij}\) equals \(z_j\) if \(k=i\) and equals \(0\) otherwise, so \((\partial J/\partial W)_{ij}=v_i z_j\), which is the outer product \(vz^\top\). Shapes: \(v\) is \(n\times 1\), \(z^\top\) is \(1\times m\), \(vz^\top\) is \(n\times m\).

For an elementwise \(\sigma\), \(B[\sigma,z](v)=\sigma'(z)\odot v\) in linear time. For squared error, \(\partial J/\partial z=z-y\) at the top of the backward pass (up to the conventional \(1/2\)).

The MLP in two Directions

Forward, storing every \(z^{[k]}\) and \(a^{[k]}\):

\[ z^{[1]}=W^{[1]}x+b^{[1]},\quad a^{[1]}=\sigma(z^{[1]}),\quad \ldots,\quad z^{[r]}=W^{[r]}a^{[r-1]}+b^{[r]},\quad J=\tfrac12\bigl(z^{[r]}-y\bigr)^2 \]

if the head is linear. Backward, starting from \(\partial J/\partial z^{[r]}=z^{[r]}-y\) and writing \(a^{[0]}=x\),

\[ \begin{aligned} \frac{\partial J}{\partial W^{[k+1]}} &=\frac{\partial J}{\partial z^{[k+1]}}\,(a^{[k]})^\top,\\ \frac{\partial J}{\partial b^{[k+1]}} &=\frac{\partial J}{\partial z^{[k+1]}},\\ \frac{\partial J}{\partial a^{[k]}} &=(W^{[k+1]})^\top\frac{\partial J}{\partial z^{[k+1]}},\\ \frac{\partial J}{\partial z^{[k]}} &=\sigma'(z^{[k]})\odot\frac{\partial J}{\partial a^{[k]}}. \end{aligned} \]

From memory, one layer: \(z=Wa+b\), \(a_{\mathrm{out}}=\sigma(z)\); then \(\delta\leftarrow(W^{+})^\top\delta\odot\sigma'(z)\), \(\nabla W\leftarrow\delta a^\top\), \(\nabla b\leftarrow\delta\).

On a mini-batch, stack examples as columns of \(X\in\mathbb{R}^{d\times B}\). Then \(Z=WX+b\) with \(b\) broadcast, and \(\partial J/\partial W=VX^\top\) if \(V\) holds the incoming adjoints as columns. Papers use that column convention. NumPy and PyTorch put batch first, so \(X\in\mathbb{R}^{B\times d}\) and \(Z=XW+b\). Transpose every matrix and flip every product; do not mix conventions.