Scalable Algorithm Design for Unbiased Estimation via Couplings of Markov Chain Monte Carlo Methods

点击翻译按钮获取中文摘要

Markov chain Monte Carlo methods have revolutionized statistics and data science in the past several decades. These methods are routinely used for simulation and numerical integration in nearly all scientific areas. In practice, however, parallel implementation is a long-standing bottleneck for Markov chain Monte Carlo methods. Existing Monte Carlo estimators generally suffer from bias, which precludes their direct use of modern parallel computing devices. This project aims to design a new framework to construct unbiased estimators based on Markov chain Monte Carlo outputs. Results of the project will advance the development of unbiased estimators and efficient algorithms that can scale up for massive datasets. The new method will empower practitioners in scientific fields such as chemistry, biology, and computer science that face high-dimensional simulation problems. This project will provide training opportunities to undergraduate and graduate students. The technical goals of this project include two interconnected aspects. The first focus is on unbiased estimators for general simulation-based inference problems by combining the idea of the existing unbiased Markov chain Monte Carlo and Multilevel Monte Carlo methods. The second aspect focuses on designing fast algorithms for unbiased estimation. The efficiency of the developed method relies on the underlying Markov chain Monte Carlo algorithm and the design of a coupling strategy between the two Markov chains. This project will theoretically investigate the convergence speed of different existing algorithms and develop practical, implementable algorithms. The new method will be applied to solve problems arising from diverse areas such as operation research, optimization, and machine learning.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.