Timezone: »

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

Wed Dec 10 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
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.

[ PDF] 

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 Oral: A* Sampling »
    Wed. Dec 10th 09:20 -- 09:40 PM Room Level 2, room 210

More from the Same Authors