Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning
We present Zar: a formally verified compiler pipeline from discrete probabilistic programs with unbounded loops in the conditional probabilistic guarded command language (cpGCL) to proved-correct executable samplers in the random bit model. We exploit the key idea that all discrete probability distributions can be reduced to unbiased coin-flipping schemes. The compiler pipeline first translates cpGCL programs into choice-fix trees, an intermediate representation suitable for reduction of biased probabilistic choices. Choice-fix trees are then translated to coinductive interaction trees for execution within the random bit model. The correctness of the composed translations establishes the sampling equidistribution theorem: compiled samplers are correct wrt. the conditional weakest pre-expectation semantics of cpGCL source programs. Zar is implemented and fully verified in the Coq proof assistant. We extract verified samplers to OCaml and Python and empirically validate them on a number of illustrative examples.
Tue 20 JunDisplayed time zone: Eastern Time (US & Canada) change
13:40 - 15:40 | PLDI: Probabilistic AnalysesPLDI Research Papers at Royal Chair(s): Gagandeep Singh University of Illinois at Urbana-Champaign | ||
13:40 20mTalk | Lilac: A Modal Separation Logic for Conditional Probability PLDI Research Papers John Li Northeastern University, Amal Ahmed Northeastern University, USA, Steven Holtzen Northeastern University DOI Pre-print | ||
14:00 20mTalk | Formally Verified Samplers from Probabilistic Programs with Loops and Conditioning PLDI Research Papers Alexander Bagnall Ohio University, Gordon Stewart Bedrock Systems, Anindya Banerjee IMDEA Software Institute DOI | ||
14:20 20mTalk | Verified Density Compilation for a Probabilistic Programming Language PLDI Research Papers DOI | ||
14:40 20mTalk | Probabilistic Programming with Stochastic Probabilities PLDI Research Papers Alexander K. Lew Massachusetts Institute of Technology, Matin Ghavami Massachusetts Institute of Technology, Martin Rinard MIT, Vikash K. Mansinghka Massachusetts Institute of Technology DOI | ||
15:00 20mTalk | Automated Expected Value Analysis of Recursive Programs PLDI Research Papers DOI | ||
15:20 20mTalk | Synthesizing Quantum-Circuit Optimizers PLDI Research Papers Amanda Xu University of Wisconsin-Madison, Abtin Molavi University of Wisconsin-Madison, Lauren Pick University of Wisconsin-Madison and University of California, Berkeley, Swamit Tannu University of Wisconsin-Madison, Aws Albarghouthi University of Wisconsin-Madison DOI Pre-print |