Optimization of Markov Chain Monte Carlo Schemes with Spectral Gap Estimation

现代数据的巨大规模和日益增加的复杂性使得在计算上无法找到数据科学中使用的许多数学模型的精确解。采样方法已经成为解决这一问题的有效替代方法，并广泛应用于各种科学领域，包括生物学，物理学，金融学，地球科学和人工智能。通过生成大量的随机解并模拟不同的场景，采样可以以计算高效的方式揭示隐藏的模式和关系，这些模式和关系可能从数据本身看不出来。然而，对于不同的数据集和科学问题，给定的采样算法的有效性可能会有很大差异。该项目的一个主要目标是开发在算法执行过程中评估采样难度的通用方法，这些方法可以进一步用于自适应地调整现有采样算法的行为，以实现最佳性能。例如，考虑使用由数百万个基因组成的现代基因组数据集选择与某些复杂疾病相关的基因的问题。该研究团队旨在开发采样算法，可以快速识别哪些基因极有可能或不太可能与疾病相关，然后分配大部分计算资源来分析少量可能相互作用并显示关联的中间证据的基因。该项目将对学生进行理论和跨学科研究方面的培训，并使调查人员能够开发和改进与抽样方法有关的课程。 马尔可夫链收敛理论为使用马尔可夫链蒙特卡罗（MCMC）抽样提供了理论保证和实践指导，MCMC抽样是贝叶斯计算的主要驱动力，过去十年来，高维统计模型的MCMC方法的复杂性分析得到了快速发展。然而，估计MCMC收敛速度从一个单一的轨迹得到的关注少得多。现有的几种方法计算量很大，使得从业者难以优化MCMC方案的效率。该项目旨在通过开发新的理论和方法来测量，估计和优化各种MCMC方案的收敛速度，包括经典的Metropolis-Hastings算法和最近提出的重要性回火计划，以填补这些空白。 将开发新的采样算法，旨在克服统计学和其他科学领域中出现的具有挑战性的多模态目标分布。此外，随机控制方法将被探索，以获得进一步的理论见解，以优化设计的回火MCMC schemes.This奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

The enormous scale and increasing complexity of modern data make it computationally prohibitive to find exact solutions to many mathematical models used in data sciences. Sampling methods have emerged as an efficient alternative approach to this issue and are widely used in various scientific fields, including biology, physics, finance, geoscience, and artificial intelligence. By generating a large number of random solutions and simulating different scenarios, sampling can reveal hidden patterns and relationships that may not be apparent from the data itself in a computationally efficient manner. However, for different data sets and scientific problems, the efficacy of a given sampling algorithm can vary significantly. One major goal of this project is to develop general methods for assessing sampling difficulty during the algorithm execution, which can be further used to adaptively tune the behavior of existing sampling algorithms to achieve optimal performance. For example, consider the problem of selecting genes associated with some complex disease using a modern genomic data set consisting of millions of genes. The research team aims to develop sampling algorithms that can quickly identify which genes are highly likely or unlikely to be associated with the disease and then allocate most computational resources to analyzing a small number of genes that may interact with each other and show intermediate evidence of association. This project will train students on both theoretical and interdisciplinary research and enable the investigator to develop and revamp courses related to sampling methodology. The Markov chain convergence theory provides both theoretical guarantees and practical guidance on the use of Markov chain Monte Carlo (MCMC) sampling, the main driving force behind Bayesian computation, and the past decade has witnessed a rapid development in the complexity analysis of MCMC methods for high-dimensional statistical models. However, estimation of the MCMC convergence rate from a single trajectory has received much less attention. The few existing methods are computationally expensive, making it difficult for practitioners to optimize the efficiency of MCMC schemes. This project aims to fill these gaps by developing novel theory and methodology for measuring, estimating and optimizing the convergence rates of various MCMC schemes, including classical Metropolis-Hastings algorithms and recently proposed importance tempering schemes. New sampling algorithms will be developed aiming to overcome challenging multimodal target distributions that arise in statistics and other scientific fields. Additionally, a stochastic control approach will be explored to gain further theoretical insights into the optimal design of tempered MCMC schemes.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.