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

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

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.