A ⇤ Sampling
The problem of drawing samples from a discrete distribution can be converted into a discrete optimization problem [1,2,3,4]. 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.
This paper introduces a new approach to sampling from continuous probability distributions. The method extends prior work on using a combination of Gumbel perturbations and optimization to the continuous case. This is technically challenging, and they devise several interesting ideas to deal with continuous spaces, e.g. to produce an exponentially large or even infinite number of random variables (one per point of the continuous/discrete space) with the right distribution in an implicit way. Finally, they highlight an interesting connection with adaptive rejection sampling. Some experimental results are provided and show the promise of the approach. The paper is well written (I have a few suggestions below) and generally easy to read (Figure 1 is nice and very helpful to understand the algorithm). This is very novel work where the authors explore an interesting combination of ideas from computer science and traditional AI (like A* search) with advanced statistics. The paper deals with a very important problem which is very relevant to NIPS.The experimental evaluation is a bit limited (and only on synethetic data) but I think it might be good enough as an initial step. One issue is that the algorithm doesn't seem to be able to handle high-dimensional spaces well, but that is of course very hard. One concern I have is that the performance metric used in the experimental section is "likelihood evaluations per sample". What about runtime? Are there overheads in using A* sampling?Other comments:It would be good to specify clearly what is the input and what is the output of the algorithms reported as pseudocode (Algorithm 1 and 2).Line 177. I would expand the first paragraph of section 4. The decomposition in tractable and intractable parts is key. The results in the previous sections obviously don't make any sense if we can already sample and integrate. I would try to say more about what the decomposition means, maybe mentioning some of the examples used later.  Explanation in section 6.2 is a bit confusing (especially the last paragraph is rather obscure)In 6.3, why is it compared to rejection sampler and not with OS*? Is it so slow that can only do 3 points and 5 runs?How does one deal with ties? If the argmax contains more than one element, do we have to sample uniformly from the set or is it sufficient to output one? I am guessing in principle it only happens with probability zero so it might not be an issue, but since you are generating an exponentially large number of random variable using finite precision arithmetic can it still happen?It's unclear what the probability is conditioned on in Eq (3)Line 85-86: at that point it's unclear what it means that max and argmax are independentline 4 of pseudocode: are there technical assumptions for the max to be defined (as opposed to a supremum)