Lune

POPL2021Top-tier venue

Automatic differentiation in PCF

Damiano Mazza, Michele Pagani

Abstract

We study the correctness of automatic differentiation (AD) in the context of a higher-order, Turing-complete language (PCF with real numbers), both in forward and reverse mode. Our main result is that, under mild hypotheses on the primitive functions included in the language, AD is almost everywhere correct, that is, it computes the derivative or gradient of the program under consideration except for a set of Lebesgue measure zero. Stated otherwise, there are inputs on which AD is incorrect, but the probability of randomly choosing one such input is zero. Our result is in fact more precise, in that the set of failure points admits a more explicit description: for example, in case the primitive functions are just constants, addition and multiplication, the set of points where AD fails is contained in a countable union of zero sets of non-identically-zero polynomials.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

13 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • You Only Linearize Once: Tangents Transpose to Gradients cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • You Only Linearize Once: Tangents Transpose to Gradients cites Backpropagation in the simply typed lambda-calculus with linear negation
  • You Only Linearize Once: Tangents Transpose to Gradients cites A simple differentiable programming language
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites Backpropagation in the simply typed lambda-calculus with linear negation
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites A simple differentiable programming language
  • On Correctness of Automatic Differentiation for Non-Differentiable Functions cites A simple differentiable programming language
  • Systematically differentiating parametric discontinuities cites On Correctness of Automatic Differentiation for Non-Differentiable Functions
  • Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations cites Backpropagation in the simply typed lambda-calculus with linear negation
  • Efficient Dual-Numbers Reverse AD via Well-Known Program Transformations cites A simple differentiable programming language
  • ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs cites Backpropagation in the simply typed lambda-calculus with linear negation
  • ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs cites A simple differentiable programming language
  • ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs cites On Correctness of Automatic Differentiation for Non-Differentiable Functions
  • ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs cites Systematically differentiating parametric discontinuities
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers13

  1. Systematically differentiating parametric discontinuitiesSai Praveen Bangaru, Jesse Michel, Kevin Mu, Gilbert Bernstein et al.SIGGRAPH 2021 · 30 citations
  2. Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiationFaustyna Krawiec, Simon Peyton Jones, Neel Krishnaswami, Tom Ellis et al.POPL 2022 · 27 citations
  3. ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic ProgramsAlexander K. Lew, Mathieu Huot, Sam Staton, Vikash K. MansinghkaPOPL 2023 · 16 citations
  4. You Only Linearize Once: Tangents Transpose to GradientsAlexey Radul, Adam Paszke, Roy Frostig, Matthew J. Johnson et al.POPL 2023 · 13 citations
  5. Efficient Dual-Numbers Reverse AD via Well-Known Program TransformationsTom Smeding, Matthijs VákárPOPL 2023 · 10 citations

Builds on3

  1. On Correctness of Automatic Differentiation for Non-Differentiable FunctionsWonyeol Lee, Hangyeol Yu, Xavier Rival, Hongseok YangNeurIPS 2020 · 50 citations
  2. A simple differentiable programming languageMartín Abadi, Gordon D. PlotkinPOPL 2020 · 49 citations
  3. Backpropagation in the simply typed lambda-calculus with linear negationAloïs Brunel, Damiano Mazza, Michele PaganiPOPL 2020 · 24 citations

Related papers

  1. On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable ParametersWonyeol Lee, Sejun Park, Alex AikenICML 2023 · 6 citations
  2. ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable ProgramsMathieu Huot, Alexander K. Lew, Vikash K. Mansinghka, Sam StatonLICS 2023 · 5 citations
  3. What does automatic differentiation compute for neural networks?Sejun Park, Sanghyuk Chun, Wonyeol LeeICLR 2024
  4. A mathematical model for automatic differentiation in machine learningJérôme Bolte, Edouard PauwelsNeurIPS 2020 · 84 citations
  5. Efficient CHADTom Smeding, Matthijs VákárPOPL 2024 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines