Collaborative Research: AF: Small: Phase Transitions in Sampling Related Problems

合作研究：AF：小：采样相关问题中的相变

• 批准号: 2007022
• 负责人: Eric Vigoda
• 金额: $ 24.99万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2022-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007022&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Phase

Graphical models are a widely used tool to succinctly represent high-dimensional data and to understand the fundamental building blocks and interactions of physical and biological systems. These models have appeared in a variety of scientific fields. In physics they are used to understand the thermodynamic properties of ferromagnetic materials and are integral in the study of phase transitions in physical systems. In biology these models are a fundamental tool for inferring evolutionary history using genetic data in phylogenetic models. Graphical models are ubiquitous in machine learning for computational tasks such as Bayesian inference. This project addresses fundamental computational tasks that are crucial for studying, constructing, and utilizing graphical models. The project will involve undergraduate students in research involving graphical models in social science settings.There are two core tasks for studying graphical models: learning and sampling. The learning problem is focused on inferring the inner structure of the underlying graphical model from the macroscopic behavior of the system. In contrast, the goal of the associated sampling problem is to efficiently simulate the thermodynamic behavior of a learned or inferred graphical model. This project will develop new algorithms, and more generally understand the computational complexity of sampling and learning as well as several related problems. A common theme in this project is connecting the computational complexity of these sampling- and inference-related problems with statistical-physics phase transitions.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的法定任务，并被认为是值得通过基金会的智力优点和更广泛的影响来通过评估来支持的。

项目成果

Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion

• DOI: 10.1145/3406325.3451035
• 发表时间: 2020-11
• 期刊: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Zongchen Chen;Kuikui Liu;Eric Vigoda

Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction

• DOI: 10.1109/focs46700.2020.00124
• 发表时间: 2020-01-01
• 期刊: 2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020)
• 作者: Chen, Zongchen;Liu, Kuikui;Vigoda, Eric
• 通讯作者: Vigoda, Eric

Rapid Mixing for Colorings via Spectral Independence

• DOI: 10.1137/1.9781611976465.94
• 发表时间: 2020-07
• 作者: Zongchen Chen;Andreas Galanis;Daniel Stefankovic;Eric Vigoda

Entropy decay in the Swendsen–Wang dynamics on ℤ^d

∄^d 上的 Swendsen-Wang 动力学中的熵衰减

• DOI: 10.1145/3406325.3451095
• 发表时间: 2021
• 期刊: Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC
• 作者: Blanca, Antonio;Caputo, Pietro;Parisi, Daniel;Sinclair, Alistair;Vigoda, Eric
• 通讯作者: Vigoda, Eric

The complexity of approximating averages on bounded-degree graphs

有界度图上近似平均值的复杂性

• DOI: 10.1109/focs46700.2020.00127
• 发表时间: 2020
• 期刊: Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS
• 作者: Galanis, Andreas;Stefankovic, Daniel;Vigoda, Eric
• 通讯作者: Vigoda, Eric