论文标题
离散空间中本地平衡建议的最佳缩放
Optimal Scaling for Locally Balanced Proposals in Discrete Spaces
论文作者
论文摘要
在连续空间中，对大都市杂货（M-H）算法的最佳缩放率进行了很好的研究，但是在离散空间中缺乏类似的理解。最近，事实证明，一个本地平衡的建议（LBP）是渐近的最佳选择，但最佳缩放问题仍然是开放的。在本文中，我们首次确定了离散空间中M-H的效率也可以以渐近的接受率独立于目标分布为特征。此外，我们从理论和经验上验证了LBP和随机步行大都市（RWM）的最佳接受率分别为$ 0.574 $和0.234美元。这些结果还有助于确定LBP在$ o上渐近（n^\ frac {2} {3}）$比RWM在模型尺寸$ n $方面效率更高。了解最佳接受率的知识使人们可以在离散空间中自动调整提案分布的邻域大小，直接类似于连续空间中的尺寸控制。我们从经验上证明，这种自适应M-H采样可以在离散空间中的各种目标分布（包括训练基于深度能量的模型）中的各种目标分布中进行稳健改进采样。
Optimal scaling has been well studied for Metropolis-Hastings (M-H) algorithms in continuous spaces, but a similar understanding has been lacking in discrete spaces. Recently, a family of locally balanced proposals (LBP) for discrete spaces has been proved to be asymptotically optimal, but the question of optimal scaling has remained open. In this paper, we establish, for the first time, that the efficiency of M-H in discrete spaces can also be characterized by an asymptotic acceptance rate that is independent of the target distribution. Moreover, we verify, both theoretically and empirically, that the optimal acceptance rates for LBP and random walk Metropolis (RWM) are $0.574$ and $0.234$ respectively. These results also help establish that LBP is asymptotically $O(N^\frac{2}{3})$ more efficient than RWM with respect to model dimension $N$. Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces. We demonstrate empirically that such adaptive M-H sampling can robustly improve sampling in a variety of target distributions in discrete spaces, including training deep energy based models.
