6
$\begingroup$

I asked this question earlier on StackOverflow, but it's obviously better suited for SciComp:

While there seem to be lots of references online which compare automatic differentiation methods and frameworks against each other, I can't seem to find anything on how I should expect automatic differentiation to compare to hand-written derivative evaluation.

My particular situation: I'm doing a gradient-descent of a scalar cost function, with a few thousand variables and significant (>99%) sparsity. I have a C++ function to compute this cost. I've also manually derived and implemented functions to compute the gradient and Hessian. (The cost function and its derivatives are not tuned in any way, they're just a straightforward implementation.) A typical descent to a minimum takes about ten seconds.

I want to more easily use different cost functions, and using AD seems like a good way to proceed. I used CppAD to automatically evaluate the gradient and Hessian; these values are exactly the same as those from my manual derivative functions. But using AD, a typical gradient descent takes about five minutes.

I was surprised at how much slower AD was, but then realized that I don't really know how fast it should be. I'm not looking so much for "How do I speed up my computations?", as "What should I expect?"

How much slower should automatic differentiation be, compared to hand-written derivatives? How about for first- and second-order derivatives?

$\endgroup$
  • $\begingroup$ Did you use forward mode or reverse mode of AD ? Forward mode will be expensive when there are many independent variables. $\endgroup$ – cfdlab Nov 27 '19 at 11:16
  • $\begingroup$ Like I said, I'm using CppAD to do the calculation; it uses its own estimates to choose between forward and reverse mode. The gradient derivation is fine, it works pretty fast (so I'm guessing it uses reverse mode). The Hessian, on the other hand, seems to take a tremendous amount of time (though not an intractable amount, obviously). $\endgroup$ – gilgamec Nov 28 '19 at 8:53
  • 3
    $\begingroup$ The Hessian is computed using a combination of one reverse and forward mode, thus is as slow as a forward mode derivative. Have you also tried to avoid to compute the Hessian, or to do it repeatedly, by using BFGS updates of an approximate Hessian? $\endgroup$ – Lutz Lehmann Nov 29 '19 at 13:02
  • $\begingroup$ I hadn't seen BFGS before, thanks! Something like that seems more useful for my particular problem. $\endgroup$ – gilgamec Dec 1 '19 at 10:20
5
$\begingroup$

So you said that you have a few thousand variables. AD will usually be slower than hand coded derivatives, and if you're using forward AD, then you essentially need to evaluate the cost function once for each design variable,s and you have thousands of them. Typically in these cases, people use the reverse mode of AD, which scales independent of the number of design variables, and instead scales with the number of objective or cost functions. The reverse mode of AD corresponds to solving the adjoint problem. The benefit of AD is the comparative ease of implementation, as your hand coded-derivatives should be faster to run than AD in most cases.If you want the second derivatives, then the scaling forward AD will scale with the number of design variables squared, which is really just intractable.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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