We enhance Liquid Haskell with mechanisms to reason about relational properties of probabilistic computations. Our mechanisms, which are inspired from probabilistic couplings, are applicable to a rich set of probabilistic properties, including expected sensitivity, which ensures that the distance between outputs of two probabilistic computations can be controlled from the distance between their inputs. We implement our mechanisms in the type system of Liquid Haskell, and we use them to formally verify two classic algorithms from the machine learning literature: Temporal Difference (TD) reinforcement learning, and stochastic gradient descent (SGD). We formalize a fragment of our system for discrete distributions, and we prove soundness with respect to a set-theoretical semantics.
Tue 13 SepDisplayed time zone: Belgrade, Bratislava, Budapest, Ljubljana, Prague change
13:40 - 15:20 | Program Verification & SynthesisICFP Papers and Events at Linhart Chair(s): Arthur Azevedo de Amorim Boston University | ||
13:40 20mTalk | Verified Symbolic Execution with Kripke Specification Monads (and no Meta-Programming) ICFP Papers and Events Steven Keuchel Vrije Universiteit Brussel, Sander Huyghebaert Vrije Universiteit Brussel, Georgy Lukyanov Newcastle University, UK, Dominique Devriese KU Leuven DOI | ||
14:00 20mTalk | Safe Couplings: Coupled Refinement Types ICFP Papers and Events Lisa Vasilenko IMDEA Software Institute, Niki Vazou IMDEA Software Institute, Gilles Barthe MPI-SP, Germany / IMDEA Software Institute, Spain DOI | ||
14:20 20mTalk | Aeneas: Rust Verification by Functional Translation ICFP Papers and Events DOI | ||
14:40 20mTalk | Searching Entangled Program Spaces ICFP Papers and Events James Koppel Massachusetts Institute of Technology, USA, Zheng Guo University of California, San Diego, Edsko de Vries Well-Typed LLP, Armando Solar-Lezama Massachusetts Institute of Technology, Nadia Polikarpova University of California at San Diego DOI | ||
15:00 20mTalk | Iterating on multiple collections in synchronyJFP Presentation ICFP Papers and Events Stefano Perna , Val Tannen University of Pennsylvania, USA, Limsoon Wong National University of Singapore |