Collaborative Research: AF: Small: Sampling and Optimization under Global Constraints

从复杂的高维概率分布中采样和优化高维函数是两项核心计算任务，在机器学习、统计、物理和许多其他领域都有应用，包括工业和科学领域。概率图形模型为研究这两项任务提供了一个广泛且非常有用的框架。这一框架起源于统计物理学，物理直觉指导了算法的发展和对计算复杂性的理解。在实际和科学应用中，一种常见的设置是对图形模型施加全局约束；例如，固定系统中相互作用的粒子的数量，固定磁体的数学模型中的磁化强度，或固定元素分区的大小。对算法在这种情况下的性能的严格理解在很大程度上仍然缺乏。这个项目的目标是开发算法和复杂性方面的新技术，以了解全局约束如何影响这些采样和优化问题的可处理性。在统计物理学见解的指导下，这项研究项目将开发新的算法，并研究算法方法的局限性。该项目还包括对研究生的跨学科研究和高中推广计划的培训。该项目的主要研究目标是在以下几个算法环境中建立一个健壮的抽样和优化理论：近似计数和抽样的计算阈值；马尔可夫链混合时间；以及随机图上的优化问题的结构。初步工作表明，对马尔可夫随机场施加全局约束可以改变相关抽样和优化问题的行为和复杂性。该项目关注的具体问题包括：确定有界度图上固定磁化强度下反铁磁性伊辛模型的计算阈值；证明保守动力学(如川崎动力学)的最优混合时间界限；以及理解稀疏随机图上优化问题的极限值。这一方法是由统计物理学的直觉指导的，该领域提供了一种自然语言和一套技术来分析图形模型和大量由于施加全球约束而导致的不同现象的例子。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Sampling from complex, high dimensional probability distributions and optimizing high dimensional functions are two central computational tasks, with applications in machine learning, statistics, physics, and many other fields, both industrial and scientific. A widespread and very useful framework for studying both of these tasks is provided by probabilistic graphical models. This framework originates in statistical physics, and physical intuition has guided both the development of algorithms and the understanding of computational complexity. A common setting in both practical and scientific applications is the imposition of global constraints on a graphical model; examples including fixing the number of interacting particles in a system, fixing magnetization in a mathematical model of a magnet, or fixing the sizes of a partition of elements. A rigorous understanding of the performance of algorithms in this setting is still largely absent. The goal of this project is to develop new techniques in algorithms and complexity to understand how global constraints influence the tractability of these sampling and optimization problems. Guided by insights from statistical physics, this research project will develop new algorithms and study the limits of algorithmic approaches. The project also involves the training of graduate students in interdisciplinary research and a high-school outreach program.The main research goal of the project is to build a robust theory of sampling and optimization in the presence of global constraints in several algorithmic contexts: computational thresholds for approximate counting and sampling; Markov chain mixing times; and the structure of optimization problems on random graphs. Preliminary work shows that imposing a global constraint on a Markov random field can transform the behavior and complexity of the associated sampling and optimization problems. Specific problems the project focuses on include the determination of computational thresholds for the antiferromagnetic Ising model at fixed magnetization on bounded degree graphs; proving optimal mixing time bounds for conservative dynamics like the Kawasaki dynamics; and understanding the limiting values of optimization problems on sparse random graphs. The approach is guided by intuition from statistical physics, a field that provides a natural language and suite of techniques for analyzing graphical models and a wealth of examples of different phenomena that result from imposing global constraints.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.