Soundness for Automatic Differentiation via String Diagrams

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.

Date
Friday, September 10, 2021 15:00 Europe/Paris
Event
GReTA seminar
Mario Alvarez-Picallo
Mario Alvarez-Picallo
Senior Research Scientist

Mario Alvarez currently works as a research scientist at Huawei’s Programming Languages lab in Edinburgh. His work focuses on developing and generalising efficient automatic differentiation algorithms as graph-to-graph transformations. He obtained a PhD in Computer Science from the University of Oxford under the supervision of prof. Luke Ong, studying generalised notions of derivatives.