CAREER: Sampling, learning and testing spin systems

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

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.