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将继续开发一种基于大偏差和相关汉密尔顿-雅可比-贝尔曼方程的子解的方法，用于设计和分析重要抽样和某些类型的分支算法。该研究项目的主要应用重点是纳米材料的研究。由于它们的基本物理和化学性质可能与它们的块状对应物有很大的不同，因此这些材料具有重要的实践和理论意义。了解这些基本特性是如何由所涉及的原子级细节决定的，这是实现这些系统最终设计潜力的基本要素，涉及克服许多罕见事件挑战。蒙特卡罗算法是应用科学和工程中最灵活和最有用的数值工具之一。它们被用于解决广泛的问题，例如确定化学和材料科学模型中的热力学性质，评估大规模网络中的平衡性质，以及贝叶斯统计中的分类和估计问题。然而，对于许多蒙特卡罗算法，罕见事件在决定结果数值近似的质量和有用性方面起着主导作用。一个重要的例子是通过马尔可夫链蒙特卡罗逼近积分。当分布具有显著概率的口袋并且这些口袋之间的转换很少时，这些应用非常具有挑战性。另一个例子是估计单个罕见事件的概率，例如保险索赔中意外的巨额赔付或化学物理模型中亚稳态井之间的转换。pi将开发和应用从大偏差理论（分析和表征罕见事件的概率分支）到高效算法设计问题的方法。他们将把这些算法应用于材料科学问题。