Mathieu Huot ; Sam Staton ; Matthijs Vákár - Higher Order Automatic Differentiation of Higher Order Functions

lmcs:7106 - Logical Methods in Computer Science, March 22, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:41)2022
Higher Order Automatic Differentiation of Higher Order FunctionsArticle

Authors: Mathieu Huot ; Sam Staton ; Matthijs Vákár

    We present semantic correctness proofs of automatic differentiation (AD). We consider a forward-mode AD method on a higher order language with algebraic data types, and we characterise it as the unique structure preserving macro given a choice of derivatives for basic operations. We describe a rich semantics for differentiable programming, based on diffeological spaces. We show that it interprets our language, and we phrase what it means for the AD method to be correct with respect to this semantics. We show that our characterisation of AD gives rise to an elegant semantic proof of its correctness based on a gluing construction on diffeological spaces. We explain how this is, in essence, a logical relations argument. Throughout, we show how the analysis extends to AD methods for computing higher order derivatives using a Taylor approximation.


    Volume: Volume 18, Issue 1
    Published on: March 22, 2022
    Accepted on: February 1, 2022
    Submitted on: January 19, 2021
    Keywords: Computer Science - Programming Languages,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Semantically correct automatic differentiation; Funder: European Commission; Code: 895827
    • Better Languages for Statistics: foundations for non-parametric probabilistic programming; Funder: European Commission; Code: 864202
    • Compositional Higher-Order Model Checking: Logics, Models and Algorithms; Funder: UK Research and Innovation; Code: EP/M023974/1

    2 Documents citing this article

    Consultation statistics

    This page has been seen 1451 times.
    This article's PDF has been downloaded 757 times.