Automatic differentiation and backpropagation

Let $p,q\ge 1$, let $\mathrm{\Theta }\subseteq {\mathbb{R}}^p$ and $H\subseteq {\mathbb{R}}^q$ be open, let $T\ge 0$ be an integer, and fix $\theta \in \mathrm{\Theta }$. A map is continuously differentiable here when it is totally differentiable at every point of its open domain and its derivative matrix varies continuously there. A finite shared-parameter recurrence consists of an initial-state map $h_0:\mathrm{\Theta }\to H$, transition maps ${\mathrm{\Phi }}_t:\mathrm{\Theta }\times H\to H$ for $t=1,\dots ,T$, and a scalar loss $\mathrm{\ell }:\mathrm{\Theta }\times H\to \mathbb{R}$, all continuously differentiable on open domains containing the evaluated inputs. Put $h_0=h_0(\theta )$, $h_t={\mathrm{\Phi }}_t(\theta ,h_{t-1})$, and $J(\theta )=\mathrm{\ell }(\theta ,h_T)$. A fixed collection of external inputs, such as the observations at successive time steps, may be built into the maps ${\mathrm{\Phi }}_t$. The same parameter vector $\theta$ is supplied to every transition.

For each map, its registered local derivative is the total derivative with respect to the indicated variable while the other displayed variables are held fixed. Transposes are Euclidean adjoints for the stated coordinate inner products. Evaluate and store $h_0,h_1,\dots ,h_T$. If a map is undefined, return DOMAIN_ERROR. For piecewise-$C^1$ maps, use only the derivative on a unique strict active branch; if any evaluated input lies on a branch boundary or has ambiguous branch selection, return NONDIFFERENTIABLE and no gradient.

Initialize ${\lambda }_T=(D_h\mathrm{\ell }(\theta ,h_T){)}^T$ and $g=(D_{\theta }\mathrm{\ell }(\theta ,h_T){)}^T$. For $t=T,T-1,\dots ,1$, set $A_t=D_{\theta }{\mathrm{\Phi }}_t(\theta ,h_{t-1})$, $B_t=D_h{\mathrm{\Phi }}_t(\theta ,h_{t-1})$, then update

$g\leftarrow g+A_t^T{\lambda }_t,{\lambda }_{t-1}=B_t^T{\lambda }_t\mathrm{.}$

After the reverse sweep, set $g\leftarrow g+(D{h}_0(\theta ){)}^T{\lambda }_0$ and return $(J(\theta ),g)$. For $T=0$, the reverse loop is empty and the same initialization and final update apply. All derivative calculations in this procedure are real-arithmetic operations on the specified maps; no floating-point accuracy guarantee is asserted.

The diagram shows the finite unrolling: arrows point from an input value to the operation that uses it. The single $\theta$ node feeds each transition and the loss, so the reverse updates add all of those contributions into the same accumulator $g$; the $h_t$ cotangents flow from right to left. The diagram illustrates the algorithm, and no correctness proof relies on it.

diagram failed to render:
\begin{tikzpicture}[>=stealth, node distance=1.55cm]
  \node[draw,circle] (theta) {$\theta$};
  \node[draw,rectangle,right of=theta,xshift=0.4cm] (h0) {$h_0(\theta)$};
  \node[draw,rectangle,right of=h0,xshift=0.65cm] (phi1) {$\Phi_1$};
  \node[draw,rectangle,right of=phi1,xshift=0.65cm] (h1) {$h_1$};
  \node[draw,rectangle,right of=h1,xshift=0.65cm] (phi2) {$\Phi_2$};
  \node[right of=phi2,xshift=0.35cm] (dots) {$\cdots$};
  \node[draw,rectangle,right of=dots,xshift=0.35cm] (phit) {$\Phi_T$};
  \node[draw,rectangle,right of=phit,xshift=0.65cm] (ht) {$h_T$};
  \node[draw,rectangle,right of=ht,xshift=0.65cm] (loss) {$\ell(\theta,h_T)$};
  \draw[->] (theta) -- (h0);
  \draw[->] (h0) -- (phi1);
  \draw[->] (theta) to[bend left=30] (phi1);
  \draw[->] (phi1) -- (h1);
  \draw[->] (h1) -- (phi2);
  \draw[->] (theta) to[bend left=42] (phi2);
  \draw[->] (phi2) -- (dots);
  \draw[->] (dots) -- (phit);
  \draw[->] (theta) to[bend left=55] (phit);
  \draw[->] (phit) -- (ht);
  \draw[->] (ht) -- (loss);
  \draw[->] (theta) to[bend left=68] (loss);
\end{tikzpicture}

Finite real-arithmetic graph and strict-branch conventions

Generic scalar-output reverse-mode sweep

Continuously differentiable Euclidean maps

Total derivative as a linear first-order approximation

This is a mathematical real-arithmetic procedure. A floating-point implementation may round its primal values and local derivatives; the definition supplies no numerical error estimate.

Let $p,q\ge 1$, let $\mathrm{\Theta }\subseteq {\mathbb{R}}^p$ and $H\subseteq {\mathbb{R}}^q$ be open, and let $T$ be a nonnegative integer. Suppose $h_0:\mathrm{\Theta }\to H$, ${\mathrm{\Phi }}_t:\mathrm{\Theta }\times H\to H$ for $1\le t\le T$, and $\mathrm{\ell }:\mathrm{\Theta }\times H\to \mathbb{R}$ are continuously differentiable on open domains containing the trajectory at $\theta \in \mathrm{\Theta }$. A continuously differentiable map is totally differentiable at each point and has a derivative matrix continuous on its domain. Define $h_0=h_0(\theta )$, $h_t={\mathrm{\Phi }}_t(\theta ,h_{t-1})$, and $J(\theta )=\mathrm{\ell }(\theta ,h_T)$. Write $A_t=D_{\theta }{\mathrm{\Phi }}_t(\theta ,h_{t-1})$ and $B_t=D_h{\mathrm{\Phi }}_t(\theta ,h_{t-1})$, with each partial derivative holding the other argument fixed. Set ${\lambda }_T=(D_h\mathrm{\ell }(\theta ,h_T){)}^T$ and, in descending order, ${\lambda }_{t-1}=B_t^T{\lambda }_t$. Then the backpropagation algorithm returns $J(\theta )$ and

${\mathrm{\nabla }}_{\theta }J(\theta )=(D_{\theta }\mathrm{\ell }(\theta ,h_T){)}^T+{\sum }_{t=1}^T{A}_t^T{\lambda }_t+(D{h}_0(\theta ){)}^T{\lambda }_0,$

where the sum is empty when $T=0$. The statement also applies when every primitive is evaluated on one fixed strict $C^1$ branch; it makes no assertion at a branch boundary.