CAREER: Sampling, learning and testing spin systems

职业：采样、学习和测试旋转系统

• 批准号: 2143762
• 负责人: Antonio Blanca Pimentel
• 金额: $ 50万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2027-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2143762&HistoricalAwards=false
• 关键词: CAREER; Sampling; learning; testing; spin

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.

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

项目成果

Fast and perfect sampling of subgraphs and polymer systems

• DOI: 10.1145/3632294
• 发表时间: 2022-02
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Antonio Blanca;Sarah Cannon;Will Perkins

Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics

通过随机簇动力学在无界度随机图上进行 Potts 采样

• 发表时间: 2022
• 期刊: and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022
• 作者: Antonio Blanca;Reza Gheissari
• 通讯作者: Reza Gheissari