An alternative approach https://www.microsoft.com/en-us/research/video/the-simple-es... where you define the right functional structures that allow a very compact and efficient way of expressing automatic differentiation and then let the existing compiler do the heavy lifting.
I've read the corresponding paper, and while I think it's a fun read, I'm not sure it does particularly much to clear up the underlying confusion here. Reverse mode AD on straight line primitives is describabable in about three lines of exposition. The tricky part is how do you handle control flow (equivalently recursion). The description thereof then depends on what your underlying IR data structure is, but describing this generally isn't horrible either. The real problem in the literature is that there is lots of confusion over what is the AD algorithm and what are the workarounds applied to make it work in the particular system described.
For example, all the ML frameworks generally combine a high level tracer with a straight line AD transform, which then sometimes gets presented as a fundamental aspect of AD (which it isn't, you're just using the tracer to get an IR you can handle). As a result, this field has a lot of confused terminology, but all the results have been known since the 70s.
The name of the game for all the latest generation tools is to cleanly separate out the semantic AD transform from the rest of the system and then just use an unmodified compiler thereafter. We do it by transforming Julia IR, the Swift folks do it on SIL, and the Scala folks have an implementation using shift/reset and LMS. If you do this, a bunch of traditional AD techniques become just special cases of general purpose compiler transforms (DCE, CSE, etc). See this talk I gave recently for some more details: https://juliacomputing.com/blog/2019/02/19/growing-a-compile...
As an aside, a pet peeve of mine is people calling these algorithms "tape free". High storage requirements, due to the need to remember (or alternatively, recompute) intermediate values are a fundamental property of reverse mode AD and you can't get rid of it. The best you can do is hide it (e.g. in compiler managed stack or closure environments), with all the same fundamental challenges. This is probably a terminology clash, with people wanting to use "tape" as a term for a much more narrow kind of data structure generated from a tracing AD system, but the requirement to have some data structure like it, no matter how hidden is fundamental to the algorithm.
Currently, I'm currently using TF 1.x for most of my AD needs, but encountering the limits so I'm always looking for neater solutions.
Conceptually, I enjoy the functional approach where the standard compiler does the work. But I'm still using some graph based approach, where the order of operations are recorded on a "tape", then replayed it in reverse order.
The main reason is to be able to manage the memory and computation placement. To distribute huge computations among machines, while limiting memory transfers between machines/devices to a minimum.
Also some kind of automatic gradient accumulation to reduce the memory need would be nice. Currently using the graph based approach, partitioning a big tensor into smaller ones and doing a map-reduce to accumulate the gradient works surprising well (except for the initial very long graph creation time).
Every time I do one of those manual optimizations I start dreaming : "that should be done by the compiler". You tell the compiler your cluster definition and devices, you write a few for loops as if the code was done on a single cpu. And the compiler do the loop splitting, reordering, parallelization across device in an optimal way given your available memory constraints.
> As an aside, a pet peeve of mine is people calling these algorithms "tape free".
The common autograd-style tape combines a recording of both the operations of a program and its intermediate values, making the term ambiguous; so when people say "tape-free" they mean avoiding recorded operations.
In the Julia world we've tried to disambiguate with "trace" and "tape" for operations and values, but that's not standard terminology, unfortunately.
Yes, I understand that, but i still think it's misleading. Even in Julia, we're still recording operations, just
a) at a much coarser granularity (if there's no control flow in the middle we can record it as one operation)
b) in the type of the tape data structure rather than explicitly
For example, one could imagine applying common subexpression compression to a tracer tape, and would get essentially the same thing.
Other places to stores this information are the stack of a closure chain, but it's still fundamentally the same information.
In a more traditional SCT AD like Tapenade, there isn't really anything that corresponds to recording of program operations at runtime. Zygote arguably does something semantically equivalent to recording a trace (at the interprocedural level), but of course the idea is that once you've optimised that away we approximate Tapenade – so the line is a bit blurred.
Don't get me wrong, I agree with your core point: "tape-free" conflates multiple things, and none of them really capture the AD design space in a useful way. Hopefully as the field settles down we'll figure out more useful axes for comparing these tools.
