paper

ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs — Alexander K. Lew, Mathieu Huot, Sam Staton & Vikash K. Mansinghka (2022). arXiv:2212.06386 (v1, PDF); POPL 2023, Proc. ACM Program. Lang. 7, doi:10.1145/3571198.

Extends forward-mode automatic differentiation to probabilistic programs: a source-to-source transformation turns a program whose expected value is a loss into one whose expected value is the loss’s derivative, with gradient estimators (enumeration, REINFORCE, reparametrisation) chosen per primitive, proved correct with logical relations; the prototype is a few dozen lines of Haskell.

Sources: the paper, arXiv:2212.06386v1, checked against the arXiv listing. Index: Papers.

Key definitions and results

  • Figure 2: naive AD of a probabilistic program gives the wrong derivative
  • Definitions 2.1–2.4, Lemma 2.1, Theorem 2.2: correctness of forward-mode AD by logical relations
  • Definitions 3.1–3.3, 3.5, Theorem 3.2: unbiased estimators, unbiased derivatives, correctness on the combinator language
  • Definition 4.1, Lemma 4.1, Theorem 4.3, Corollary 4.4: correct dual-number expectation estimators; the discrete language
  • Theorem 5.3, Theorem 6.1, Corollary 7.1: continuous and full languages
  • Appendix D: the logical-relations argument, categorically

Concept notes

Automatic Differentiation of Expected Values, Continuation Monad, Logical Relations