论文标题
关于抽样的运行时间的注释
Notes on the runtime of A* sampling
论文作者
论文摘要
模拟随机变量的挑战是统计和机器学习中的核心问题。鉴于可处理的提案分配$ p $，我们可以从中绘制精确的样本，而目标分配$ q $绝对相对于$ p $，a*采样算法允许从$ q $中模拟精确的样品，前提是我们可以评估radon-nikodym衍生产品相对于$ p $ $ p $。 Maddison等。最初表明，对于目标分配$ q $和提案分布$ p $，A*采样的运行时间由$ \ Mathcal {o}（\ exp（\ exp（d _ {\ infty} [q || p]））$ $ d _ {\ infty} [q iffty} [q | | | | | | | | | | | | |是$ qunyi dive $ q $。对于许多实际兴趣的情况，此运行时可能会非常大。在这里，我们表明，有了$ Q $和$ P $的其他限制性假设，我们可以实现更快的运行时间。具体来说，我们表明，如果$ \ sathbb {r} $上的分布$ q $和$ p $，并且它们的radon-nikodym导数是单模式的，则*样本的运行时间为$ \ natercal {o}（d _ {\ infty} [\ infty} [q | | | | | | | | | || P] $，而不是Bathing Bath Appententy exponeential fastion。
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 $\mathcal{O}(\exp(D_{\infty}[Q||P]))$ where $D_{\infty}[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 $\mathbb{R}$ and their Radon-Nikodym derivative is unimodal, the runtime of A* sampling is $\mathcal{O}(D_{\infty}[Q||P])$, which is exponentially faster than A* sampling without assumptions.
