0
$\begingroup$

Does anyone have any resources I could follow that explains how to compute the Nth derivative using both forward and backward autodiff

I understand how to compute the first derivatives

Any assistance would be appreciated thanks

Edit: Could I compute the derivative normally then pass those values through the autodiff equation again to get the second derivative?

$\endgroup$
1
  • 1
    $\begingroup$ No expert on AD, but if you know how to compute the first derivative ... compute the first derivative of the first derivative? $\endgroup$
    – davidhigh
    Dec 17, 2022 at 8:30

1 Answer 1

1
$\begingroup$

If $F:\Bbb R^n\to\Bbb R^m$ is represented by a computational graph, and its derivative in direction $v$ denoted as $F'(x)[v]$, then the forward mode of AD evaluates exactly that. In the backward mode the gradient of a linear combination $\alpha(F(x))$ is computed, one could denote this as $\alpha(F'(x)[:])$. So to compute the Jacobian one has the choice of $n$ forward passes of $F'(x)[e_k]$ or $m$ backward passes of $\theta^k(F'(x)[:])$. Each pass, without counting organizational overhead, has about twice the evaluation cost as the evaluation of $F$ itself.

The second derivative is a third order tensor, or a box configuration of size $m\times n\times n$ (with some symmetry in the last two coordinates). Again one has the choice of $n^2$ (or $n^2/2$) forward evaluations of $F''(x)[e_i,e_j]$ or $mn$ backward evaluations of $\theta^j(F''(x)[e_i,:])$. This makes a huge difference if $m$ is small and $n$ large.

What you suggest are methods to implement the forwards mode variant. This is relatively easy to implement with code-rewriting tools or by methods of graph manipulation that trace the first-derivative forward push into an enhanced computational graph, from which then again the derivative can be taken. This would resolve operations on dual numbers similar to how one can resolve one complex multiplication into 4 (or 3) real multiplications.

There also exist approaches to push forward the coefficient structure for the full second-degree Taylor polynomials, starting with the coordinates $[x_i,e_i,0_{n\times n}]$. This can also be done for higher derivatives, but the level of duplicate computations due to the symmetry of the mixed derivatives rises fast.

For the method of combining forward and a backward passes see the established literature.

Another approach to target some or all higher-order derivatives is to push forward truncated Taylor polynomials for lines or paths in a select collection of directions. This then results in a linear system for a collection of derivatives, usually with an unavoidably large condition number.

$\endgroup$
3
  • $\begingroup$ I see makes sense thank you. Do you have any links I can follow to try implement these? trying to understand Autograd thoroughly and I think would be best to try implement autograd myself $\endgroup$ Dec 19, 2022 at 6:56
  • $\begingroup$ Do you want to reconstruct the structures for computation or the automatic generation of these structures? $\endgroup$ Dec 19, 2022 at 7:23
  • $\begingroup$ Both would be ok. Ill have a look at both then decide which is more useful for me thank you $\endgroup$ Dec 19, 2022 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.