Lune

LICS2023Top-tier venue

ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs

Mathieu Huot, Alexander K. Lew, Vikash K. Mansinghka, Sam Staton

Abstract

We introduce a new setting, the category of ωPAP spaces, for reasoning denotationally about expressive differentiable and probabilistic programming languages. Our semantics is general enough to assign meanings to most practical probabilistic and differentiable programs, including those that use general recursion, higher-order functions, discontinuous primitives, and discrete and continuous sampling. But crucially, it is also specific enough to exclude many pathological denotations, enabling us to establish new results about differentiable and probabilistic programs. In the differentiable setting, we prove general correctness theorems for automatic differentiation and its use within gradient descent. In the probabilistic setting, we establish the almost-everywhere differentiability of probabilistic programs’ trace density functions, and the existence of convenient base measures for density computation in Monte Carlo inference. In some cases these results were previously known, but required detailed proofs of an operational flavor; by contrast, all our proofs work directly with programs’ denotations.

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.

7 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

  • A mathematical model for automatic differentiation in machine learning cites On Correctness of Automatic Differentiation for Non-Differentiable Functions
  • On Correctness of Automatic Differentiation for Non-Differentiable Functions cites A mathematical model for automatic differentiation in machine learning
  • What does automatic differentiation compute for neural networks? cites A mathematical model for automatic differentiation in machine learning
  • What does automatic differentiation compute for neural networks? cites On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters
  • What does automatic differentiation compute for neural networks? cites Automatic differentiation in PCF
  • What does automatic differentiation compute for neural networks? cites On Correctness of Automatic Differentiation for Non-Differentiable Functions
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites A mathematical model for automatic differentiation in machine learning
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites Automatic differentiation in PCF
  • On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters cites On Correctness of Automatic Differentiation for Non-Differentiable Functions
  • Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation cites Automatic differentiation in PCF
  • Semantics of Integrating and Differentiating Singularities cites Automatic differentiation in PCF
  • Semantics of Integrating and Differentiating Singularities cites On Correctness of Automatic Differentiation for Non-Differentiable Functions
  • Automatic differentiation in PCF cites On Correctness of Automatic Differentiation for Non-Differentiable Functions
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers7

  1. On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable ParametersWonyeol Lee, Sejun Park, Alex AikenICML 2023 · 6 citations
  2. Bayesian Separation Logic: A Logical Foundation and Axiomatic Semantics for Probabilistic ProgrammingShing Hin Ho, Nicolas Wu, Azalea RaadPOPL 2026 · 2 citations
  3. A Cartesian Closed Category for Random VariablesPietro Di Gianantonio, Abbas EdalatLICS 2024 · 1 citation
  4. What does automatic differentiation compute for neural networks?Sejun Park, Sanghyuk Chun, Wonyeol LeeICLR 2024
  5. Semantics of Integrating and Differentiating SingularitiesJesse Michel, Wonyeol Lee, Hongseok YangPLDI 2025

Builds on11

  1. A mathematical model for automatic differentiation in machine learningJérôme Bolte, Edouard PauwelsNeurIPS 2020 · 84 citations
  2. On Correctness of Automatic Differentiation for Non-Differentiable FunctionsWonyeol Lee, Hangyeol Yu, Xavier Rival, Hongseok YangNeurIPS 2020 · 50 citations
  3. Automatic differentiation in PCFDamiano Mazza, Michele PaganiPOPL 2021 · 47 citations
  4. Trace types and denotational semantics for sound programmable inference in probabilistic languagesAlexander K. Lew, Marco F. Cusumano-Towner, Benjamin Sherman, Michael Carbin et al.POPL 2020 · 30 citations
  5. Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiationFaustyna Krawiec, Simon Peyton Jones, Neel Krishnaswami, Tom Ellis et al.POPL 2022 · 27 citations

Related papers

  1. Deterministic stream-sampling for probabilistic programming: semantics and verificationFredrik Dahlqvist, Alexandra Silva, William SmithLICS 2023 · 4 citations
  2. ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic ProgramsAlexander K. Lew, Mathieu Huot, Sam Staton, Vikash K. MansinghkaPOPL 2023 · 16 citations
  3. 𝜆ₛ: computable semantics for differentiable programming with higher-order functions and datatypesBenjamin Sherman, Jesse Michel, Michael CarbinPOPL 2021 · 11 citations
  4. A simple differentiable programming languageMartín Abadi, Gordon D. PlotkinPOPL 2020 · 49 citations
  5. Guaranteed bounds for posterior inference in universal probabilistic programmingRaven Beutner, C.-H. Luke Ong, Fabian ZaiserPLDI 2022 · 18 citations
Dusk over the sea between two cliffs drawn in fine vertical lines