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

马尔可夫链蒙特卡罗方法在过去的几十年里彻底改变了统计学和数据科学。这些方法通常用于几乎所有科学领域的模拟和数值积分。然而，在实践中，并行实现是一个长期存在的瓶颈马尔可夫链蒙特卡罗方法。现有的蒙特卡罗估计一般遭受偏见，这妨碍了他们直接使用现代并行计算设备。本计画旨在设计一个新的架构，以建构基于马尔可夫链蒙地卡罗输出的无偏估计量。该项目的结果将推动无偏估计器和高效算法的开发，这些算法可以扩展到大规模数据集。这种新方法将使化学、生物学和计算机科学等科学领域的从业者能够面对高维模拟问题。该项目将为本科生和研究生提供培训机会。该项目的技术目标包括两个相互关联的方面。第一个重点是无偏估计一般模拟为基础的推理问题相结合的想法，现有的无偏马尔可夫链蒙特卡罗和多级蒙特卡罗方法。第二个方面着重于设计无偏估计的快速算法。所开发的方法的效率依赖于底层的马尔可夫链蒙特卡罗算法和两个马尔可夫链之间的耦合策略的设计。这个项目将从理论上研究不同现有算法的收敛速度，并开发实用的，可实现的算法。该奖项体现了NSF的法定使命，通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.