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 的法定使命，并通过使用基金会的智力价值和更广泛的影响进行评估，被认为值得支持审查标准。

项目成果

期刊论文数量（11）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees

通过张量化实现任意树上随机独立集的最佳混合

DOI：
发表时间：
2023-09
期刊：
RANDOM
影响因子：
0
作者：
Efthymiou, Charilaos;Hayes, Thomas P.;Štefankovič, Daniel;Vigoda, Eric
通讯作者：
Vigoda, Eric

Metastability of the Potts Ferromagnet on Random Regular Graphs

随机正则图上波兹铁磁体的亚稳态

DOI：
发表时间：
2022-07
期刊：
Leibniz international proceedings in informatics
影响因子：
0
作者：
Coja;Galanis, Andreas;Goldberg, Leslie Ann;Ravelomanana, Jean Bernoulli;Štefankovič, Daniel;Vigoda, Eric
通讯作者：
Vigoda, Eric

Improved Distributed Algorithms for Random Colorings

改进的随机着色分布式算法