Timezone: »

 
Oral
A* Sampling
Chris Maddison · Danny Tarlow · Tom Minka

Wed Dec 10 01:20 PM -- 01:40 PM (PST) @ Level 2, room 210
in Oral Session 8 »

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 Toronto)
Danny Tarlow (Google Research, Brain team)
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