CRII: AF: Markov Chain Monte Carlo Algorithms for Spin Systems

CRII：AF：旋转系统的马尔可夫链蒙特卡罗算法

• 批准号: 1850443
• 负责人: Antonio Blanca Pimentel
• 金额: $ 17.5万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1850443&HistoricalAwards=false
• 关键词: CRII; AF; Markov; Chain; Monte

Generating samples from probability distributions is a fundamental computational task in science, engineering, and technology. Efficient and unbiased sampling algorithms have a significant impact in a variety of fields, notably including statistics, biology, physics, and computer science. The Markov chain Monte Carlo (MCMC) method provides a powerful class of sampling algorithms used by an active community of researchers in diverse applications, typically relying on heuristics for their design and analysis. This project focuses on the theoretical study of MCMC algorithms, aiming to increase their reliability and to reduce computational costs in practice. Two application areas will be most relevant: statistical physics and machine learning. Most of the work will be carried out in close collaboration with graduate students; the training provided will be conducive to their development as researchers. The PI will consider the problem of sampling from Gibbs (or Boltzmann) distributions in the context of spin systems, a general framework for modeling interacting systems of simple elements. In this context, the PI intends to rigorously analyze the efficiency of popular MCMC algorithms. Two specific foci will be the Alternating Scan dynamics for bipartite systems and the Swendsen-Wang algorithm for the classical Ising/Potts model from statistical physics. The former is actively used to train Restricted Boltzmann Machines and build sophisticated deep learning architectures, while the latter is a standard method for sampling from the Ising/Potts distribution. The PI will also study the interplay between the efficiency of MCMC algorithms and the phase transitions of the underlying probabilistic model. Additional computational implications of these phase transitions will be explored in the context of structure learning, a closely related supervised learning problem. As such, the connections between theoretical computer science, statistical physics, and machine learning will play a central role in this project.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

从概率分布生成样本是科学、工程和技术中的一项基本计算任务。高效且公正的采样算法在各个领域都具有重大影响，特别是统计、生物学、物理学和计算机科学。马尔可夫链蒙特卡罗 (MCMC) 方法提供了一类强大的采样算法，供活跃的研究人员社区在不同的应用中使用，通常依靠启发式方法进行设计和分析。 该项目侧重于 MCMC 算法的理论研究，旨在提高其可靠性并降低实践中的计算成本。两个最相关的应用领域：统计物理学和机器学习。大部分工作将与研究生密切合作进行；所提供的培训将有利于他们作为研究人员的发展。 PI 将考虑自旋系统中吉布斯（或玻尔兹曼）分布的采样问题，自旋系统是对简单元素交互系统进行建模的通用框架。在此背景下，PI打算严格分析流行的MCMC算法的效率。两个具体的焦点是二分系统的交替扫描动力学和统计物理学中经典 Ising/Potts 模型的 Swendsen-Wang 算法。前者被积极用于训练受限玻尔兹曼机并构建复杂的深度学习架构，而后者是从 Ising/Potts 分布中采样的标准方法。 PI 还将研究 MCMC 算法的效率与底层概率模型的相变之间的相互作用。 这些相变的其他计算含义将在结构学习（一个密切相关的监督学习问题）的背景下进行探索。因此，理论计算机科学、统计物理学和机器学习之间的联系将在该项目中发挥核心作用。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

受限玻尔兹曼机和 Potts 模型的身份测试硬度

• 发表时间: 2021
• 期刊: Journal of machine learning research
• 影响因子: 6
• 作者: Blanca, A;Chen, Z;Štefankovič, D;Vigoda, E.
• 通讯作者: Vigoda, E.

Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness

树唯一性中随机正则图的随机簇动力学

• 发表时间: 2021
• 期刊: Communications in mathematical physics
• 影响因子: 2.4
• 作者: Blanca, A;Gheissari, R.
• 通讯作者: Gheissari, R.

Entropy decay in the Swendsen–Wang dynamics on Zd

Zd 上的 Swendsen-Wang 动力学中的熵衰减

• DOI: 10.1214/21-aap1702
• 发表时间: 2022
• 期刊: The Annals of Applied Probability
• 作者: Blanca, Antonio;Caputo, Pietro;Parisi, Daniel;Sinclair, Alistair;Vigoda, Eric
• 通讯作者: Vigoda, Eric