Functorial String Diagrams for Reverse-Mode Automatic Differentiation
This work addresses the need for principled and efficient automatic differentiation in functional programming and machine learning, though it appears incremental as it builds on existing string diagram and AD frameworks.
The paper tackles the problem of formulating and proving soundness for a reverse-mode automatic differentiation algorithm for simply typed lambda calculus by enhancing string diagrams with hierarchical features to capture closed monoidal structure, resulting in a sound and complete representation using hierarchical hypergraphs called hypernets for efficient implementation.
We enhance the calculus of string diagrams for monoidal categories with hierarchical features in order to capture closed monoidal (and cartesian closed) structure. Using this new syntax we formulate an automatic differentiation algorithm for (applied) simply typed lambda calculus in the style of [Pearlmutter and Siskind 2008] and we prove for the first time its soundness. To give an efficient yet principled implementation of the AD algorithm we define a sound and complete representation of hierarchical string diagrams as a class of hierarchical hypergraphs we call hypernets.