Write a Blog >>
Thu 23 Jan 2020 16:18 - 16:40 at Ile de France III (IDF III) - Probabilistic Programming Chair(s): Ohad Kammar

This paper addresses a fundamental problem in random variate generation: given access to a random source that emits a stream of independent fair bits, what is the most accurate and entropy-efficient algorithm for sampling from a discrete probability distribution (p₁, …, pₙ), where the output distribution (p̂₁, …, p̂ₙ) of the sampling algorithm can be specified with a given level of bit precision? We present a theoretical framework for formulating this problem and provide new techniques for finding sampling algorithms that are optimal both statistically (in the sense of sampling accuracy) and information-theoretically (in the sense of entropy consumption). We leverage these results to build a system that, for a broad family of measures of statistical accuracy, delivers a sampling algorithm whose expected entropy usage is minimal among those that induce the same distribution (i.e., is “entropy-optimal”) and whose output distribution (p̂₁, …, p̂ₙ) is a closest approximation to the target distribution (p₁, …, pₙ) among all entropy-optimal sampling algorithms that operate within the specified precision budget. This optimal approximate sampler is also a closer approximation than any (possibly entropy-suboptimal) sampler that consumes a bounded amount of entropy with the specified precision, a class which includes floating-point implementations of inversion sampling and related methods found in many standard software libraries. We evaluate the accuracy, entropy consumption, precision requirements, and wall-clock runtime of our optimal approximate sampling algorithms on a broad set of probability distributions, demonstrating the ways that they are superior to existing approximate samplers and establishing that they often consume significantly fewer resources than are needed by exact samplers.

Slide Deck (popl20main-p126-slides.pdf)3.97MiB

Thu 23 Jan

POPL-2020-Research-Papers
15:35 - 16:40: Research Papers - Probabilistic Programming at Ile de France III (IDF III)
Chair(s): Ohad KammarUniversity of Edinburgh
POPL-2020-Research-Papers15:35 - 15:56
Talk
David DaraisUniversity of Vermont, Ian SweetUniversity of Maryland, Chang LiuCitadel Securities, Michael HicksUniversity of Maryland
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers15:56 - 16:18
Talk
Alexander VandenbrouckeKU Leuven, Belgium, Tom SchrijversKU Leuven
Link to publication DOI Media Attached File Attached
POPL-2020-Research-Papers16:18 - 16:40
Talk
Feras SaadMassachusetts Institute of Technology, Cameron FreerMassachusetts Institute of Technology, Martin RinardMIT, Vikash MansinghkaMIT
Link to publication DOI Media Attached File Attached