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.