GReTA seminar #17: "Soundness for Automatic Differentiation via String Diagrams"
Channel: GReTA Seminar
Date: 2021-09-10

Speaker:

Mario Alvarez-Picallo (Department of Computer Science, University of Oxford, UK)

Abstract:

Reverse-mode automatic differentiation, especially in the presence of complex language features, is notoriously hard to implement correctly, and most implementations focus on differentiating straight-line imperative first-order code. Generalisations exist, however, that can tackle more advanced features; for example, the algorithm described by Pearlmutter and Siskind in their 2008 paper can differentiate higher-order functions written in a pure functional language. We show that AD algorithms can benefit enormously from being translated into the language of string diagrams in two steps: first, we describe a Pearlmutter-Siskind style AD algorithm as a set of rules for transforming hierarchical graphs; rules which can -and indeed have been- be implemented correctly and efficiently for a non-trivial language. Then, we present a proof of soundness for it by reducing the above rewrite rules to a suitable graphical version of the axioms of Cartesian reverse differential categories, expressed as string diagrams.


About the GReTA seminars:

The GReTA – Graph TRansformation Theory and Applications virtual seminar series aims to serve as a platform for the international graph rewriting community, to promote recent developments and trends in the field, and to permit a regular networking and interaction between members of this community. Seminars are held twice a month in the form of Zoom sessions (some of which will be live-streamed to YouTube). Please refer to http://www.irif.fr/~greta for further details (including information on how to register for participating in the Zoom meetings).