Timezone: »

A* Sampling
Chris Maddison · Daniel Tarlow · Tom Minka

Wed Dec 10 01:20 PM -- 01:40 PM (PST) @ Level 2, room 210

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)

Related Events (a corresponding poster, oral, or spotlight)

  • 2014 Poster: A* Sampling »
    Thu Dec 11th 12:00 -- 04:59 AM Room Level 2, room 210D

More from the Same Authors