Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations
summary
Presents a semantics-preserving optimization path from naive dual-numbers reverse AD to an implementation with the expected time complexity and a practical Haskell98 subset implementation. Key steps: add monotonic IDs and monadic staging to enforce the reverse-of-forward evaluation order, apply linear factoring to merge duplicate backpropagator calls, use the difference-list/kleisli trick for sparse vector accumulation, replace maps with mutable arrays and de-functionalize to produce a tape; prototype exists and benchmarks show roughly comparable performance (within a constant factor) to an existing Haskell AD library.
AI-written summary · about
chapters (12)
- 0:00Efficient reverse AD intro
- 1:27Naive algorithm optimizations
- 3:12Dual numbers for reverse AD
- 7:50Call graph explosion
- 8:33Linear factoring via distributive law
- 10:40Evaluation order for linear factoring
- 13:09Staging function calls with IDs
- 15:16Sparse vectors and difference lists
- 17:00Replacing tree maps with arrays
- 18:23Classic tape algorithm derivation
- 19:05Efficiency and results
- 19:34Q&A
related talks
27mProvably Correct, Asymptotically Efficient, Higher-Order Reverse-Mode Automatic
19mEfficient CHAD
29mReverse Automatic Differentiation for Accelerate (Extended Abstract)
01h 21mNon-local compiler transformations in the presence of dynamic dispatch
06mLightning Talk: A Compiler Optimization and the 2-Adic Numbers
29mStaging Automatic Differentiation with Fusion
23mContextual source code AD transformations for sum types
26mAdding AD to Scheme by Differentiating the Interpreter