CAREER: Sampling, learning and testing spin systems

自旋系统在科学和工程中无处不在。它们为研究小相互作用粒子的复杂系统提供了一个强大的数学模型，并因此用于解决核心科学挑战。它们起源于统计物理学，在过去的几十年里，它们在计算生物学、机器学习和理论计算机科学中获得了突出的地位。本项目着重于自旋系统研究中出现的基本计算问题。具体而言，它旨在推进对这些问题的理论认识；众所周知，这可以提高使用自旋系统的应用程序的性能和可靠性。该项目侧重于采样、学习和测试问题，这是自旋系统中最常遇到的计算任务。项目的第一个研究方向是研究自旋系统的马尔可夫链蒙特卡罗（MCMC）采样算法。这些算法通常依赖于启发式和经验方法来证明收敛性，导致有偏见的样本和不可靠的实验结果。因此，该项目侧重于严格分析MCMC算法的收敛速度。为此，将开发或增强几种分析马尔可夫链的技术，以解决马尔可夫链分析可用工具的众所周知的局限性。项目的第二个方向涉及身份测试和结构学习这两个密切相关的推理问题。这个项目对抽样、学习和测试的统一研究是新颖的。它将建立必要的联系，融合机器学习、统计物理和理论计算机科学的思想。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Spin systems are ubiquitous in science and engineering. They provide a robust mathematical model for studying complex systems of small interacting particles and are thus used to tackle central scientific challenges. They originated in statistical physics, and, in the last few decades, they have gained prominence in computational biology, machine learning, and theoretical computer science. This project focuses on the fundamental computational problems that emerge from the study of spin systems. Specifically, it aims to advance the theoretical understanding of such problems; this is well-known to improve the performance and reliability of applications that utilize spin systems.The project focuses on the problems of sampling, learning, and testing, which are among the most frequently encountered computational tasks in the context of spin systems. The first research direction of the project concerns the study of Markov chain Monte Carlo (MCMC) sampling algorithms for spin systems. These algorithms often rely on heuristics and empirical approaches to certify convergence, resulting in biased samplers and unreliable experimental outcomes. As such, the project focuses on the rigorous analysis of the convergence rates of MCMC algorithms. For this, several techniques for analyzing Markov chains will be developed or enhanced, addressing the well-known limitations of the available tools for Markov-chain analysis. The second direction of the project concerns the two closely related inference problems of identity testing and structure learning. This project's unified study of sampling, learning, and testing is novel. It will create essential connections and blend ideas from machine learning, statistical physics, and theoretical computer science.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.