A* Sampling
This provides a novel method for efficient sampling in continuous spaces, which is incremental but offers practical improvements for probabilistic modeling and inference tasks.
The paper tackles the problem of drawing samples from continuous distributions by converting it into an optimization problem using a Gumbel process, resulting in A* sampling, which is shown empirically to be more efficient than related adaptive rejection sampling algorithms in terms of bound and likelihood evaluations.
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.