The Simple Essence of Automatic Differentiation (Invited Talk)
Automatic differentiation (AD) is often presented in two forms: forward mode and reverse mode. Forward mode is quite simple to implement and package via operator overloading but is inefficient for many problems of practical interest such as deep learning and other uses of gradient-based optimization. Reverse mode (including its specialization, back-propagation) is much more efficient for these problems, but is also typically given much more complicated explanations and implementations, involving mutation, graph construction, and “tapes”. This talk develops a very simple specification and Haskell implementation for mode-independent AD based on the vocabulary of categories (generalized functions). Although the categorical vocabulary would be difficult to write in directly, one can instead write regular Haskell programs to be converted to this vocabulary automatically (via a compiler plugin) and then interpreted as differentiable functions. The result is direct, exact, and efficient differentiation of Haskell programs with no notational overhead. The specification and implementation are then generalized considerably by parameterizing over an underlying category. This generalization is then easily specialized to forward and reverse modes, with the latter resulting from a simple dual construction for categories. Another instance of generalized AD is automatic incremental evaluation of functional programs, again with no notational impact to the programmer.
Conal Elliott has been working (and playing) in functional programming for more than 35 years. He especially enjoys applying semantic elegance and rigor to library design and optimized implementation. He invented the paradigm now known as “functional reactive programming” in the early 1990s, and then pioneered compilation techniques for high-performance, high-level embedded domain-specific languages, with applications including 2D and 3D computer graphics. The latter work included the first compilation of Haskell programs to GPU code, while maintaining precise and simple semantics and powerful composability, as well a high degree of optimization. Conal earned a BA in math with honors from the College of Creative Studies at UC Santa Barbara in 1982 and a PhD in Computer Science from Carnegie Mellon University in 1990. He is currently working as distinguished scientist at Target. Previously, we worked at Tabula Inc on chip specification and compiling Haskell to hardware for massively parallel execution. Before Tabula, his positions included Architect at Sun Microsystems and Researcher in the Microsoft Research graphics group. He has also coached couples and led conscious relationship workshops together with his partner Holly Croydon, with whom he now lives on 20 acres in the woods in the California Gold Country.