8
$\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?

Improve this question
$\endgroup$
4
  • $\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, 2019 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, 2019 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, 2019 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, 2019 at 10:20

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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