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

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

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.