Notes on the runtime of A* sampling
share
The challenge of simulating random variables is a central problem in Statistics and Machine Learning. Given a tractable proposal distribution P, from which we can draw exact samples, and a target distribution Q which is absolutely continuous with respect to P, the A* sampling algorithm allows simulating exact samples from Q, provided we can evaluate the Radon-Nikodym derivative of Q with respect to P. Maddison et al. originally showed that for a target distribution Q and proposal distribution P, the runtime of A* sampling is upper bounded by 𝒪(exp(D_∞[Q||P])) where D_∞[Q||P] is the Renyi divergence from Q to P. This runtime can be prohibitively large for many cases of practical interest. Here, we show that with additional restrictive assumptions on Q and P, we can achieve much faster runtimes. Specifically, we show that if Q and P are distributions on ℝ and their Radon-Nikodym derivative is unimodal, the runtime of A* sampling is 𝒪(D_∞[Q||P]), which is exponentially faster than A* sampling without assumptions.
READ FULL TEXT