Optimization of Markov Chain Monte Carlo Schemes with Spectral Gap Estimation

Texas A&M University, College Station TX

Investigators

Abstract

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.