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

合作研究：AF：小型：全局约束下的采样和优化

• 批准号: 2309707
• 负责人: Ewan Davies
• 金额: $ 29.99万
• 依托单位: Colorado State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2309707&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Sampling

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.

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