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