2022/05/30 by Markou, Stratis
#Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2205.15250
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 O(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 O(D∞[Q||P]), which is exponentially faster than A* sampling without assumptions.