Large Deviation Methods for the Analysis and Design of Accelerated Monte Carlo Schemes

加速蒙特卡罗方案分析与设计的大偏差方法

• 批准号: 1317199
• 负责人: Paul Dupuis
• 金额: $ 55万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1317199&HistoricalAwards=false
• 关键词: Large; Deviation; Methods; Analysis; Design

The main focus of the research program is the use of large deviation ideas for the design and analysis of accelerated Monte Carlo methods. In addition, the underlying large deviation theory will be developed where needed. The PIs will emphasize two classes of problems, which are (i) accelerating the convergence of an empirical measure to a target stationary distribution and (ii) the estimation of the probability of a single rare event. In prior work the PIs have initiated use of the large deviation rate for the empirical measure of a Markov process as a tool for algorithm analysis. By considering suitable limits of the already effective parallel tempering algorithm, they developed a new algorithm called infinite swapping, as well as computationally tractable variants called partial infinite swapping. The research program involves further theoretical development of the algorithm and the associated large deviation tools, as well as applications to challenging problems from materials science. With regard to the estimation of the probability of a rare event, the PIs will continue to develop an approach based on large deviations and subsolutions to an associated Hamilton-Jacobi-Bellman equation for the design and analysis of importance sampling and certain types of branching algorithms. The primary applications focus of the research program is the study of nanoscale materials. Because their basic physical and chemical properties can differ significantly from those of their bulk counterparts, such materials are of substantial practical and theoretical interest. Understanding how these basic properties are determined by the atomic-level details involved, an essential element in realizing the ultimate design potential of these systems, involves overcoming a number of rare event challenges. Monte Carlo algorithms are one of the most flexible and useful numerical tools in the applied sciences and engineering. They are used to solve a broad range of problems, such as determining thermodynamic properties in models from chemistry and material science, evaluating equilibrium properties in large scale networks, and in problems of classification and estimation in Bayesian statistics. However, with many Monte Carlo algorithms, rare events play a dominant role in determining the quality and hence usefulness of the resulting numerical approximation. An important example is the approximation of integrals via Markov chain Monte Carlo. These applications are very challenging when the distribution has pockets of significant probability and transitions between these pockets are rare. Another example is estimation of the probability of a single rare event, such as unexpectedly large payouts in insurance claims or the transition between metastable wells in a model from chemical physics. The PIs will develop and apply methods from large deviation theory, which is the branch of probability that analyzes and characterizes rare events, to the problem of efficient algorithm design. They will apply these algorithms to problems of materials science.

该研究计划的主要重点是使用大偏差思想来设计和分析加速蒙特卡罗方法。 此外，将在需要时发展基本的大偏差理论。 PI将强调两类问题，即（i）加速经验测量向目标平稳分布的收敛，以及（ii）估计单个罕见事件的概率。 在以前的工作中，PI已经开始使用马尔可夫过程的经验测量的大偏差率作为算法分析的工具。 通过考虑已经有效的并行回火算法的适当限制，他们开发了一种称为无限交换的新算法，以及称为部分无限交换的计算易处理的变体。 该研究计划涉及算法和相关大偏差工具的进一步理论开发，以及材料科学挑战性问题的应用。 关于罕见事件概率的估计，PI将继续开发一种基于相关Hamilton-Jacobi-Bellman方程的大偏差和子解的方法，用于设计和分析重要性抽样和某些类型的分支算法。 该研究计划的主要应用重点是纳米材料的研究。 由于它们的基本物理和化学性质与它们的本体对应物显著不同，因此这些材料具有实质性的实际和理论兴趣。 了解这些基本属性是如何由所涉及的原子级细节决定的，这是实现这些系统最终设计潜力的基本要素，涉及克服一些罕见事件的挑战。蒙特卡罗算法是应用科学和工程中最灵活和最有用的数值工具之一。 它们用于解决广泛的问题，例如确定化学和材料科学模型中的热力学性质，评估大规模网络中的平衡性质，以及贝叶斯统计中的分类和估计问题。 然而，在许多蒙特卡罗算法中，罕见事件在确定所得到的数值近似的质量和有用性方面起着主导作用。 一个重要的例子是通过马尔可夫链蒙特卡罗积分的近似。 当分布具有显著概率的口袋并且这些口袋之间的过渡很少时，这些应用非常具有挑战性。 另一个例子是估计单个罕见事件的概率，例如保险索赔中意外的巨额支出或化学物理模型中亚稳态威尔斯之间的转变。 PI将开发和应用大偏差理论的方法，这是概率的分支，分析和表征罕见事件，有效的算法设计的问题。 他们将把这些算法应用于材料科学的问题。