Search papers, labs, and topics across Lattice.
This paper analyzes reverse-mode automatic differentiation (AD) specifically for discrete probabilistic programs, employing Combinatory Homomorphic Automatic Differentiation (CHAD) to treat AD as a structure-preserving transformation. The authors focus on the finite atomic distribution monad, demonstrating that differentiating probabilistic programs necessitates the flow of cotangents through both deterministic and probabilistic structures. Their results include a defined reverse-mode code transformation and a correctness proof using categorical logical-relations, paving the way for future advancements in differentiating more complex probabilistic languages and algebraic effects.
Differentiating probabilistic programs reveals that cotangents must navigate both deterministic and probabilistic structures, challenging traditional views on automatic differentiation.
We analyse reverse-mode automatic differentiation (AD) for discrete probabilistic programs. Our construction is formulated in the framework of Combinatory Homomorphic Automatic Differentiation (CHAD), treating AD as a structure-preserving transformation of programs, guided by a denotational semantics. The main case study is the finite atomic distribution monad, whose computations have finite support and differentiable weights. The key point is that differentiating probabilistic programs requires cotangents to flow backwards not only through deterministic computations, but also through the probabilistic structure itself. We define the corresponding reverse-mode code transformation and prove its correctness, for handled real-output programs, by a categorical logical-relations argument. Although the paper focuses on finite discrete probability, the construction gives a reusable pattern for differentiating discrete-output algebraic effects, including finite multiset non-determinism (e.g., from fork-join parallelism), exceptions, and writer-style accumulation (e.g., for in-place accumulation of high-dimensional vectors). More broadly, we view this work as a foundational step towards extending CHAD to richer probabilistic languages and to other algebraic effects with handlers.
