Timezone: »

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

Wed Dec 10 04:00 PM -- 08:59 PM (PST) @ 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