Automatic differentiation

Definition

Let $U \subseteq \R^n$ be open and let $f \colon U \to \R^m$ be given by an evaluation trace. Its first variables $v_{1-n}, \ldots, v_0$ are the inputs $x_1, \ldots, x_n$. The others are given for $k = 1, \ldots, \ell$ by $$v_k = \varphi_k\big( (v_j)_{j \in P_k} \big),$$ where $P_k \subseteq \set{1 - n, \ldots, k - 1}$ and each $\varphi_k$ is a differentiable elementary function, such as $+$, $\times$, $\sin$ or $\exp$. The outputs $y_1, \ldots, y_m$ are some of the $v_k$.

1. Forward mode takes a direction $\dot x \in \R^n$, sets $\dot v_{i - n} = \dot x_i$, and computes along with each $v_k$ the value $\dot v_k = \sum_{j \in P_k} \frac{\partial \varphi_k}{\partial v_j} \dot v_j$.
2. Reverse mode first evaluates the trace and takes $\bar y \in \R^m$. It sets the adjoint $\bar v$ of each output to its entry of $\bar y$ and all other adjoints to $0$. Then for $k = \ell, \ell - 1, \ldots, 1$ it adds $\bar v_k \frac{\partial \varphi_k}{\partial v_j}$ to $\bar v_j$ for each $j \in P_k$.

Automatic differentiation is the computation of derivatives of $f$ by these propagation rules. Forward mode returns $\dot y = J_f(x) \dot x$, where $J_f(x)$ is the Jacobian matrix. Reverse mode returns $\bar x = J_f(x)^{T} \bar y$, where $\bar x_i = \bar v_{i-n}$.