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

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

• 批准号: 2309708
• 负责人: William Perkins
• 金额: $ 29.97万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2309708&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.

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

项目成果

Leibniz International Proceedings in Informatics (LIPIcs):Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

莱布尼茨国际信息学论文集 (LIPIcs)：近似、随机化和组合优化。

• DOI: 10.4230/lipics.approx/random.2023.26
• 发表时间: 2023
• 期刊: APPROX RANDOM
• 作者: Chawla, Shuchi;Gergatsouli, Evangelia;McMahan, Jeremy;Tzamos, Christos
• 通讯作者: Tzamos, Christos

On the hardness of finding balanced independent sets in random bipartite graphs

论随机二分图中寻找平衡独立集的难度

• 发表时间: 2024
• 期刊: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Perkins, Will;Wang, Yuzhou
• 通讯作者: Wang, Yuzhou