Reverse mode run-time about autodiff HOT 13 OPEN

This is indeed a lot. I have not been able improve the reverse mode algorithm - focus has been given mainly to forward mode, which uses template meta-programming techniques to optimize the arithmetic/mathematical operations on variables of type dual at compile time. The variables of dual type are allocated at stack memory, whereas the variables of type var are pointer wrappers to dynamically allocated memory. Mathematical operations on dual variables should then be much faster, but their purpose is different -- computing derivatives of a function with respect to individual variables (one at a time) or with respect to a direction vector (with the case of individual variables being a specific case of a direction vector along the unit vector corresponding to the input variable of interest).

The reverse mode algorithm needs to construct an expression tree at runtime (as opposed to at compile time as it happens for the forward mode). Basically, you replace operations on type double by type var which is a wrapper to a pointer to dynamic memory allocated data. The bottom line is that the reverse algorithm in autodiff is, currently, not optimized as the forward algorithm, and it would be great if one or more people could collaborate in this area.

May I ask you to formulate a simple, running example, not necessary identical to your case, but that demonstrates this performance issue? I would then run it here and profile it; see where is the bottleneck.

from autodiff.

As my cost function links many intermediate variables each depending on the design variables, and because inheritance is used in reverse.hpp, I believe this is what slows down so massively my gradient calculation. I tried to build a simple example, but it seemed to work just fine in that case. It might just happen when someone links many intermediate variables that depend on the design variables. I can still send you an example where this happens but it is using my original cost function, which is very messy..

I might not use this library for my current application, but many thanks for your help!

from autodiff.

If your code is self-contained and does not depend on complicated third-party codes, then I could have a look and see how things can be improved for your specific case.

from autodiff.

Apologies for my delay - a lot of things have popped up to do.
Yes, my code is self-contained, only making use of eigen library.
Please feel free to ask any questions about my cost function - I'm also sorry I did not find the time to clean up my code..

example-reverse-mode-run-time.txt

from autodiff.

Haven't been able to run your code yet, but the cost function seems indeed complicated. A suggestion: your objective function could be a class method, and the multiple VectorXvar objects it currently instantiates transformed into data members of the class, to avoid their repeated allocation at every function call.

What happens is that when f is evaluated with double variables, this is blazing fast compared to var because an expression tree is dynamically (at runtime) created when var is used, so that this tree can be traversed later to compute all the derivatives. I see some toc commands there, and I'm curious to know where is the function taking most of the time (the bottleneck).

Have you tried using dual instead?

from autodiff.

@allanleal I think, that i can try to optimize code in reverse mode.

from autodiff.

That would be great @supersega !

from autodiff.

@supersega , if you open a new issue, we can discuss there what needs to be done.

from autodiff.

@allanleal sure!

from autodiff.

#40

from autodiff.

Have you tried using dual instead?

Yes, I did try dual when I first implemented it but it was similarly slow. I assumed at that time that it was because I was calculating the derivative of a scalar w.r.t. many input variables

from autodiff.

@davidleitao95 Please read this explanation I wrote in another issue:
#19 (comment)

Your function evaluation seems very expensive, and if you have many variables, using forward automatic differentiation will require a function call per variable to compute gradient (if a scalar function) or Jacobian (if a vector function).

Reverse mode algorithm can in principle in a single function call compute all derivatives of a scalar function (with respect to all variables). But this requires the construction of an expression tree at runtime, which can be expensive and memory consuming.

My idea is to use forward diff to compute gradients without N function evaluations, but this is something that I can only implement and experiment in a couple of months. Forward diff uses template meta programming techniques to optimize the derivative calculations and avoid temporaries. More details in that link above.

from autodiff.

Thanks for alerting me to this! A couple of months might actually be when I come back to this as I have currently to finish other stuff and finite differences do the job for the time being. I can then try that new approach to calculate the derivatives.

from autodiff.