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

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

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.