tspooner / aegir

Strongly-typed, compile-time autodifferentiation in Rust.
MIT License
9 stars 0 forks source link

Caching: add sub-expression caching support #7

Open tspooner opened 1 year ago

tspooner commented 1 year ago

Summary

At present, any given mathematical expression in aegir is formed as a (potentially very large) tree vis-a-vis symbolic differentiation. This leads to many challenges, but doesn't have to be a blocker if implemented correctly despite what many people claim [1]. The problem is, we are currently missing one crucial feature to avoid redundant computation.

Caching is fundamentally important for efficient computation in symbolic approaches to autodiff. The idea is to avoid computing the output every single operator if we can assert that the result has already been computed. This facilitates the transformation of expression trees into expression forests which are known to be equivalent to the DAGs used in more traditional implementations [1].

[1] Laue, Sören. "On the equivalence of forward mode automatic differentiation and symbolic differentiation." arXiv preprint arXiv:1904.02990 (2019).

To-Do List

tspooner commented 1 year ago

Progress is being made here: see commits 9ad7fcc through 380678c. Major roadblock will be in how to propagate Cached through Differentiable::adjoint. Similar challenge to #5 in which rewrites to the tree are not permitted when each operator is a unique type rather than an algebraic data type.