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.