Adjoint Algorithmic Differentiation (AAD)

XVA valuation (CVA and the like) uses the Monte Carlo method to find many sensitivities. Quants, risk managers, and developers of valuation systems run into the problem that the computation time balloons as the number of sensitivities grows.

Why more sensitivities take longer

Bumping (finite differences) moves one input by a small amount, reruns the valuation, and divides the change in price by the size of the move. Each sensitivity (the Greeks, such as delta and vega) adds one more rerun, so the work grows in proportion to the number of sensitivities¹. A one-sided bump that moves input $\theta$ by $\Delta\theta$ is given by the formula below². The definition of a sensitivity is covered in The Greeks.

$$\frac{\partial V}{\partial \theta} \approx \frac{V(\theta + \Delta\theta) - V(\theta)}{\Delta\theta}$$

Consider a hypothetical example in which a portfolio takes 1 minute to value once and you need 1,000 sensitivities, such as points on the interest rate curve and points on the volatility surface. A one-sided bump needs the original valuation plus 1,000 bumped valuations, 1,001 in all, which takes 1,001 minutes (about 16.7 hours). In theory, the reverse mode of automatic differentiation can find all 1,000 in less than 5 times the original valuation (less than 5 minutes). This holds only when the output is a single price, and memory and other costs come on top.

Besides the count, bumping has a problem with choosing the step size. The right size depends on the value of the input, and balancing accuracy against stability is not simple³. A step that is too large increases the approximation error, and for a discontinuous payoff a step that is too small makes the estimate noisy². In the Monte Carlo method, the same random numbers are used before and after the bump to hold down the noise². A central difference is more accurate, but it needs two reruns per sensitivity².

For correlations the count grows even faster. With many random factors, the number of pairs grows with the square of the number of factors, so finding the correlation sensitivity of every pair by bumping is often too heavy to be practical¹.

The difference approximation in bumping is not the same as the finite difference method, which solves a partial differential equation on a grid.

Forward mode and reverse (adjoint) mode

Automatic differentiation finds the derivatives of a computation written as a program by using the chain rule. However complex the program, it is a composition of elementary operations such as addition, multiplication, and $\sin$, and the partial derivatives of those operations are known, so the derivative of the whole can be assembled⁴.

Suppose the computation runs from the input $Z$ through $A$ and $B$ to the output $Y$. $Y$ is a single number, such as a price, and $Z$ is the set of inputs whose sensitivities you want. When there are several inputs, $\partial A / \partial Z$ and the like are matrices (Jacobian matrices). The forward (tangent linear) mode works in the same direction as the computation and finds, step by step, how much a movement $\dot Z$ of the inputs carries through to the output⁵.

$$\dot{Y} = \frac{\partial Y}{\partial B}\,\frac{\partial B}{\partial A}\,\frac{\partial A}{\partial Z}\,\dot{Z}$$

$\dot Z$ can hold the direction of only one input, so $N$ sensitivities need $N$ forward runs⁵.

The reverse (adjoint) mode computes backward, from the output to the inputs. It sets the adjoint of the output, $\bar{Y}$, to 1 and finds the adjoint of each variable, such as $\bar{A}$, by using transposed matrices as follows⁶.

$$\bar{Z} = \left(\frac{\partial A}{\partial Z}\right)^{T}\left(\frac{\partial B}{\partial A}\right)^{T}\left(\frac{\partial Y}{\partial B}\right)^{T}\bar{Y}$$

Each component of $\bar{Z}$ is the sensitivity of the output $Y$ to the corresponding input. A single backward pass starting from $\bar{Y} = 1$ finds all $N$ of them⁶.

The reverse mode suits cases where there are few outputs whose sensitivities you want and many inputs. The forward mode suits the opposite case, with few inputs and many outputs⁴. When the output is a single portfolio value and the inputs are hundreds of market data points and model parameters, the reverse mode is the better fit. The technique of applying the reverse mode to a whole calculation program is AAD (adjoint algorithmic differentiation)⁷.

Sensitivities of three inputs by the reverse mode

Consider a hypothetical example in which an output $y$ is found from the inputs $x_1 = 2$, $x_2 = 3$, and $x_3 = 1$ in three steps.

$$v_1 = x_1 x_2, \qquad v_2 = v_1 + x_3, \qquad y = v_2^{2}$$

In the forward calculation (the original valuation), the intermediate values and the output are as follows.

The backward calculation starts from $\bar{y} = 1$ and goes in reverse order. The partial derivative at each step is fixed by the intermediate values found in the forward pass ($v_2 = 7$, $x_1 = 2$, $x_2 = 3$).

One backward pass gives $\partial y/\partial x_1 = 42$, $\partial y/\partial x_2 = 28$, and $\partial y/\partial x_3 = 14$ at the same time. Differentiating the formula directly, $y = (x_1 x_2 + x_3)^2$ gives $\partial y/\partial x_1 = 2 \times 7 \times 3 = 42$ and so on, the same values. The forward mode would need 3 runs for 3 inputs. With only 3 inputs, bumping also needs just 4 valuations, counting the original. The gap in the number of runs widens with many inputs, such as the 1,000 sensitivities in the bumping example.

Compared with a one-sided bump of step size 0.001, the results are as follows. The bump values are larger than the true values because of the approximation error from the step size.

Computational cost, memory, and accuracy

There is a theoretical result that the computational cost of the reverse mode is less than 5 times that of the original computation, and it does not depend on the number of inputs. The cost of the forward mode grows in proportion to the number of inputs⁴. In the correlation sensitivity example too, the cost stays within 4 times that of finding the price once, regardless of the number of factors or pairs⁸.

However, one reverse run returns the sensitivities of a single output. When you want sensitivities of many outputs, the forward mode can find them with less additional work⁹.

On memory, the backward calculation uses the intermediate values found in the forward pass (such as $v_2$ in the example above). In a Monte Carlo method that works path by path, only the values of the current path need to be stored, so memory is described as not a heavy burden¹⁰. In a large pricing library, memory management and techniques such as checkpointing are said to help¹¹.

On accuracy, automatic differentiation returns the derivative of the computation as written in the program exactly, to machine precision, whereas bumping contains approximation error⁴. The bump difference of 0.009 in the example above is the error that remains even with a step size of 0.001. Whether the computation itself matches the true sensitivity is a separate question. For example, a discontinuous payoff cannot be used as it is with the method that differentiates the payoff path by path (the pathwise method).

Deep diveThe adjoint along a stochastic differential equation path and the cost

Suppose a Monte Carlo path is built by the following recursion. $\hat{S}_n$ is the state at time $n$, $S_0$ is the initial value, and $F_n$ is the update for one step¹².

$$\hat{S}_{n+1} = F_n(\hat{S}_n)$$

Let $D_n = \partial F_n / \partial \hat{S}_n$ be the partial derivative of one step's update, and let $f$ be the payoff at maturity. The sensitivity to the initial value is then the following product.

$$\frac{\partial f(\hat{S}_N)}{\partial S_0} = \frac{\partial f}{\partial \hat{S}_N}\, D_{N-1} D_{N-2} \cdots D_0$$

Multiplying from the $D_0$ side (forward) means a series of matrix-matrix products, which costs about $m^3$ per step for a state of dimension $m$. Multiplying from the $\partial f / \partial \hat{S}_N$ side (backward) lets you find the adjoint $V_n = (\partial f / \partial \hat{S}_n)^T$ in turn by $V_n = D_n^{T} V_{n+1}$, which takes about $m^2$ per step¹². Counting the extra work for each input parameter, the backward cost is about $m^2 + m \times$ (number of parameters) and the forward cost is about $m^2 \times$ (number of parameters), so the gap widens as the parameters increase¹³.

Where it is used

For Greeks, a 2006 study used the reverse mode for the delta and vega of swaptions in the LIBOR market model, and Homescu describes it as a pioneering paper. For a portfolio of 15 swaptions, forward-mode automatic differentiation was about 10 times as efficient as bumping. With 80 time periods, the reverse mode was 5 times as efficient as the forward mode for delta alone and 25 times as efficient for delta and vega¹⁴. In the same passage Homescu also writes that the reverse mode cut the cost by "several orders of magnitude" compared with the forward mode, which reads as inconsistent with the figures of 5 and 25 times. The summary does not settle which is accurate. The study combines the reverse mode with the pathwise method, which differentiates the payoff with respect to the inputs path by path and averages the results.

Correlation sensitivities are another use. AAD has been applied to the valuation of baskets built with the Gaussian copula. In numerical tests on basket default options, the correlation sensitivities of all pairs were found within 4 times the price, regardless of the number of factors⁸. With 20 reference entities it was about 100 times as fast as bumping, and with 40 about 500 times¹⁵.

For the sensitivities of CVA, there is an example from a 2011 paper. For a portfolio of 5 commodity swaps over 5 years, there were more than 600 CVA sensitivities. With one CVA valuation taking 10 seconds, the reverse mode of automatic differentiation found all the sensitivities in under 40 seconds (less than 4 times one valuation), while bumping (finite differences) took about 1 hour 40 minutes¹⁶.

The gradient of the objective function in calibration (the sum of squared differences between model prices and market prices) contains the sensitivity of each price to the parameters, and the adjoint procedure can find it¹⁷. In an example from a 2009 paper, for the calibration of a lognormal variance model by Monte Carlo, a computation that took more than 3 hours when the gradient was found by finite differences took under 10 minutes with the adjoint¹⁸. The procedure is covered in Model Calibration.

Difficulties in adoption and where the assumptions break down

The pathwise method differentiates the payoff with respect to the inputs path by path and averages the results. It requires the payoff and the coefficients of the equation that builds the paths to be continuous and piecewise differentiable, so a discontinuous payoff cannot be handled as it is²¹. There are remedies such as approximating a digital option, smoothing the payoff with conditional expectation, and combining with the likelihood ratio method (which differentiates the probability density rather than the payoff with respect to the inputs)²². A product whose payment changes depending on whether a level is crossed, such as a barrier option, runs into this problem.

Implementations take one of two approaches: derive the derivative formula from the continuous equation and then discretize, or differentiate the discretized computation. The latter is often preferred. It is built systematically, and automatic differentiation tools can shorten development time²³. Tools include those that generate code computing the sensitivities from the original code, and those that replace the operations with a type that pairs a value with its sensitivity²⁴. To check an implementation, you can compare with the gradient from bumping, and you can also confirm that the forward-mode and reverse-mode gradients agree to machine precision¹⁹. In a large pricing library, memory management is also said to help.

What AAD speeds up is the sensitivity calculation inside a model. Uncertainty about the choice of option pricing model can create model risk in the valuation of a portfolio²⁵.

Notes

1. Capriotti and Giles, "Fast Correlation Greeks by Adjoint Algorithmic Differentiation" (arXiv, 2010), first two paragraphs of the introduction. The cost of bumping grows in proportion to the number of sensitivities, and for all pairs of correlations with the square of the number of factors. ↩ ↩²

2. Giles, "Advanced Monte Carlo Methods: Computing Greeks" (Oxford University, lecture slides), pages 5–6 ("Finite difference sensitivities"). The difference formulas and cost, the error and noise from the step size, and the use of the same random numbers. ↩ ↩² ↩³ ↩⁴

3. Homescu, "Adjoints and automatic (algorithmic) differentiation in computational finance" (arXiv, 2011), page 4. The finite difference step size depends on the value of the input, and choosing a step that balances accuracy and stability is difficult. ↩

4. Homescu (arXiv, 2011), page 3 (section 1). The chain rule, the reverse-mode cost of less than 5 times (presented as a result from Griewank and Walther), which mode suits which case, and machine precision versus truncation error. ↩ ↩² ↩³ ↩⁴

5. Homescu (arXiv, 2011), pages 4–6 (section 2). The formula for the forward (tangent linear) mode and the need for one computation per input direction. The notation is Homescu's, with the three steps Z, A, B, Y. ↩ ↩²

6. Homescu (arXiv, 2011), pages 4–6 (2.1, 2.2). The formula for the reverse (adjoint) mode. Transposed matrices give the adjoints in reverse order, and from $\bar{Y} = 1$ one pass finds all the sensitivities. ↩ ↩²

7. Capriotti and Giles (arXiv, 2010), fifth paragraph of the introduction. The adjoint implementation is an example of AAD, a programming technique that can be used to compute the sensitivities of numerical algorithms in general. ↩

8. Capriotti and Giles (arXiv, 2010), abstract. In Monte Carlo valuation of baskets and in tests on portfolio default options, the correlation sensitivities of all pairs are found within 4 times the cost of finding the price. ↩ ↩²

9. Giles (Oxford University, lecture slides), page 27 ("Adjoint approach"). The adjoint method gives the sensitivities of only one output, while the forward method gives the sensitivities of several outputs with little additional work. ↩

10. Giles (Oxford University, lecture slides), page 25 ("Adjoint approach"). Only the data for the current path needs to be stored, so the memory requirement is not large. ↩

11. Homescu (arXiv, 2011), page 19 (section 9). Because of the complexity of pricing libraries, automatic differentiation tools, memory management, and techniques such as checkpointing help. ↩

12. Giles (Oxford University, lecture slides), pages 23–24 ("Adjoint approach"). The recursion, $D_n$, $V_n = D_n^T V_{n+1}$, and the cost per step, $O(m^3)$ forward and $O(m^2)$ backward. $F_n$ and $f$ are Giles's symbols. ↩ ↩²

13. Giles (Oxford University, lecture slides), pages 26–27 ("Adjoint approach"). $B_n$ differs by parameter while $V_n$ is shared, so the backward cost is about $m^2 + m \times$ (number of parameters). ↩

14. Homescu (arXiv, 2011), page 16 (section 8.1). A summary of the 2006 paper by Giles and Glasserman, with the figures of about 10, 5, and 25 times and, in the same paragraph, "several orders of magnitude". ↩

15. Homescu (arXiv, 2011), page 17 (section 8.1). For basket default options, about 100 times as fast as bumping for 20 names and about 500 times for 40 names. ↩

16. Homescu (arXiv, 2011), page 17 (section 8.1). A summary of the 2011 paper by Capriotti, Lee, and Peacock: under 40 seconds for the reverse mode and about 1 hour 40 minutes for finite differences. ↩

17. Homescu (arXiv, 2011), page 16 (section 7). The gradient of $F = \sum (\text{ModelPrice}[j] - \text{MarketPrice}[j])^2$ contains the price sensitivities, and the adjoint procedure finds it. ↩

18. Homescu (arXiv, 2011), page 19 (section 8.2). A summary of the 2009 paper by Kaebe, Maruhn, and Sachs, comparing more than 3 hours with under 10 minutes. It builds the adjoint from the continuous equation (ContAdj). ↩

19. Homescu (arXiv, 2011), page 6 (section 2.3). The automatic differentiation gradient is compared with the finite difference gradient, and the forward and reverse gradients are expected to be identical to machine precision. ↩ ↩²

20. Homescu (arXiv, 2011), pages 19–20 (section 9.1). A summary of a 2010 presentation by Baxter: each routine has a computation function and an adjoint function, and the adjoint functions are called in reverse order. ↩

21. Giles (Oxford University, lecture slides), page 11 ("Pathwise sensitivities"). The conditions are a continuous, piecewise differentiable payoff and coefficients, and a discontinuous payoff cannot be handled. ↩

22. Giles (Oxford University, lecture slides), pages 20–21 ("Discontinuous payoffs"). A piecewise linear approximation for digitals, conditional expectation, and Vibrato Monte Carlo. Barriers are an example of conditional expectation. ↩

23. Homescu (arXiv, 2011), page 3 (section 1). The names of the continuous and discrete adjoints, and why the discrete adjoint is preferred: it is systematic and shortens development. ↩

24. Giles (Oxford University, lecture slides), page 19 ("Automatic Differentiation"). The approach that generates new code from the source code, and the approach that redefines the operations with a type pairing a value and a sensitivity (operator overloading). ↩

25. Cont, "Model uncertainty and its impact on the pricing of derivative instruments" (Newton Institute preprint), abstract. Uncertainty about the choice of option pricing model can lead to "model risk" in the valuation of a portfolio of options. ↩