分布式梅特罗波利斯算法:收敛条件与最优并行加速  

Distributed Metropolis algorithm:convergence condition and optimal parallel speed-up

作　　者：凤维明 尹一通 Weiming FENG;Yitong YIN(State Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China)

机构地区：[1]南京大学计算机软件新技术国家重点实验室,南京210023

出　　处：《中国科学：信息科学》2022年第2期287-313,共27页Scientia Sinica(Informationis)

基　　金：国家重点研发计划重点专项(批准号:2018YFB1003202)资助。

摘　　要：梅特罗波利斯算法(Metropolis algorithm)是一种基本的马尔可夫链蒙特卡罗(Markov chain Monte Carlo,MCMC)采样技术,可用于从概率图模型所表示的高维概率分布(即吉布斯(Gibbs)分布)中进行随机采样.传统的梅特罗波利斯算法是一个串行算法.关于其快速收敛性的一个经典结论是:当满足梅特罗波利斯算法的Dobrushin-Shlosman条件时,该算法在O(n log n)步内快速收敛,其中n是随机变量的个数.本文研究了梅特罗波利斯算法的分布式版本——局部梅特罗波利斯算法.对该算法的正确性与收敛速度进行了分析,证明了该算法总是收敛于正确的吉布斯分布;并且对于一类自然的不包含三角形(triangle-free)概率图模型,如果满足相同的Dobrushin-Shlosman条件,则局部梅特罗波利斯算法在O(log n)轮内快速收敛.相比于传统的串行算法,实现了?(n)倍的渐进最优并行加速比.具体应用包括图染色、硬核模型和伊辛(Ising)模型的分布式采样算法.The Metropolis algorithm is a fundamental Markov chain Monte Carlo(MCMC)sampling technique,which can be used for drawing random samples from high-dimensional probability distributions(i.e.,Gibbs distributions)represented by probabilistic graphical models.The traditional Metropolis algorithm is a sequential algorithm.A classic result regarding the fast convergence of the Metropolis algorithm is:when the Dobrushin-Shlosman condition for the Metropolis algorithm is satisfied,the algorithm converges rapidly within O(n log n)step,where n is the number of variables.This paper studies a distributed variant of the Metropolis algorithm,called the local-Metropolis algorithm.We provide an analysis of the correctness and convergence of this new algorithm,and show:the algorithm always converges to the correct Gibbs distribution;moreover,for a natural class of triangle-free probabilistic graphical models,as long as the same Dobrushin-Shlosman condition is satisfied,the local-Metropolis algorithm converges within O(log n)rounds of distributed computing.Compared to the traditional sequential Metropolis algorithm,this achieves an asymptotically optimal?(n)factor of speed-ups.Concrete applications include the distributed sampling algorithms for graph coloring,hardcore model,and Ising model.

关 键 词：分布式采样 马尔可夫链蒙特卡洛 混合时间 自旋系统 耦合 

分 类 号：O211.62[理学—概率论与数理统计] O157.5[理学—数学]