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.