Poster
A* Sampling
Chris Maddison · Daniel Tarlow · Tom Minka

Wed Dec 10th 07:00 -- 11:59 PM @ Level 2, room 210D #None
in Poster Session »

The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem. In this work, we show how sampling from a continuous distribution can be converted into an optimization problem over continuous space. Central to the method is a stochastic process recently described in mathematical statistics that we call the Gumbel process. We present a new construction of the Gumbel process and A* sampling, a practical generic sampling algorithm that searches for the maximum of a Gumbel process using A* search. We analyze the correctness and convergence time of A* sampling and demonstrate empirically that it makes more efficient use of bound and likelihood evaluations than the most closely related adaptive rejection sampling-based algorithms.

Author Information

Chris Maddison (University of Oxford / DeepMind)
Daniel Tarlow (Google Brain)
Tom Minka (MSR)

More from the Same Authors