AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms

AF：小：MCMC 算法最优边界的新技术

• 批准号: 2147094
• 负责人: Eric Vigoda
• 金额: $ 48.74万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-05-01 至 2025-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2147094&HistoricalAwards=false
• 关键词: AF; Small; New; Techniques; Optimal

Markov Chain Monte Carlo (MCMC) algorithms are a widely used tool in a variety of scientific fields for sampling problems. Understanding the convergence rate of Markov chains to their equilibrium distribution is crucial for the efficiency and accuracy of scientific studies utilizing MCMC algorithms. This project focuses on the design and analysis of fast algorithms for randomly sampling from distributions defined on exponentially large combinatorial sets. This is a fundamental task that arises in a variety of scientific fields; some common examples include: Bayesian inference which is a key tool in machine learning, computer vision, and evolutionary biology; the study of the equilibrium state of idealized physical systems in statistical physics; and the design of algorithms for counting and sampling problems in theoretical computer science. The education plan of this project includes an interdisciplinary summer school at the University of California Santa Barbara to train graduate students on recent developments in the research area.This project will introduce new techniques for proving optimal convergence rates of Markov chains. The focus is an exciting new technique known as spectral independence, which measures the pairwise influences in graphical models or spin systems, and implies optimal mixing time bounds for a variety of Markov chains. This project will enhance the technique by strengthening the implications of spectral independence and extend its applicability by presenting new tools for establishing spectral independence. These improved techniques will yield new connections between various algorithmic approaches for approximate sampling and counting problems. In addition, this project will formalize connections between the computational complexity of approximate counting problems on general graphs with statistical physics phase transitions on trees.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.

马尔可夫链蒙特卡洛（MCMC）算法是在各种科学领域中广泛使用的工具，用于采样问题。 了解马尔可夫链对其平衡分布的收敛速率对于利用MCMC算法的科学研究的效率和准确性至关重要。 该项目的重点是从定义的大型组合集中定义的分布中随机采样的快速算法的设计和分析。 这是在各种科学领域中产生的基本任务。一些常见的例子包括：贝叶斯推断，这是机器学习，计算机视觉和进化生物学的关键工具；统计物理学理想化物理系统的平衡状态的研究；以及用于计算和采样问题计算机科学中计数和采样问题的算法的设计。 该项目的教育计划包括加利福尼亚大学圣塔芭芭拉分校的一所跨学科暑期学校，以培训研究生的研究领域的最新发展。该项目将引入新技术，以证明马尔可夫连锁店的最佳收敛速度。焦点是一种令人兴奋的新技术，称为光谱独立性，它可以测量图形模型或自旋系统中的成对影响，并意味着各种马尔可夫链的最佳混合时间边界。 该项目将通过增强光谱独立性的含义并通过提供新的工具来建立光谱独立性来增强技术。 这些改进的技术将在各种算法方法之间产生新的联系，以近似采样和计数问题。 此外，该项目将正式地在树木上具有统计物理学相变的一般图表上近似计数问题的计算复杂性之间形式上的联系。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的审查标准通过评估来获得支持的。

项目成果

Approximating Observables Is as Hard as Counting

近似可观测值与计数一样困难

• 发表时间: 2022
• 期刊: ICALP 2022
• 作者: Galanis, Andreas;Štefankovič, Daniel;Vigoda, Eric
• 通讯作者: Vigoda, Eric

Spectral Independence via Stability and Applications to Holant-Type Problems

• DOI: 10.1109/focs52979.2021.00023
• 发表时间: 2021-06
• 期刊: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Zongchen Chen;Kuikui Liu;Eric Vigoda

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling

• 发表时间: 2022-07
• 作者: Antonio Blanca;Zongchen Chen;Daniel Stefankovic;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

Counting and Sampling Labeled Chordal Graphs in Polynomial Time

• DOI: 10.48550/arxiv.2308.09703
• 发表时间: 2023-08
• 期刊: ArXiv
• 作者: Úrsula Hébert-Johnson;D. Lokshtanov;Eric Vigoda