Development of Stochastic Approximation Monte Carlo Methods

在过去的五十年中，马尔可夫链蒙特卡罗（MCMC）方法已经发展成为一个通用的和强大的工具，科学计算。然而，正如许多研究人员所知，传统的MCMC方法在具有崎岖能量景观的系统的模拟中容易陷入局部能量最小值，从而使模拟效率低下。为了克服这个困难，研究者和他的合作者最近提出了一种非马尔可夫链蒙特卡罗算法，即所谓的随机近似蒙特卡罗（SAMC）算法。大量的数值结果表明，SAMC可以优于它的MCMC竞争对手的许多困难的计算问题，如分子结构预测，系统发育树重建，和复杂的模型选择问题。本项目继续在理论和方法上发展SAMC。首先，SAMC是广义的，允许一些统计平滑技术被用于迭代，以提高其效率。对广义算法的收敛性和渐近性建立了严格的理论。其次，SAMC是广义的，通过改变其当前的离散设置为连续的。所得到的算法是特别适合于解决边际密度估计问题。第三，SAMC进一步改进，利用进化计算中发展的一些技术。初步结果表明，SAMC的性能得到了显著提高，为解决分子结构预测、遗传分析、遗传网络推理、机器学习、VLSI设计等硬科学问题提供了先进的计算方法。对这些问题的成功计算反过来又加深了人们对这些问题的理解。该项目在统计理论和科学计算领域都有广泛的影响。研究成果通过PI与其他学科研究人员的直接合作、会议报告、书籍和在学术期刊上发表的论文传播给这些社区。该项目还通过研究生的直接参与和将成果纳入本科生和研究生课程，对教育产生了重大影响。

During the past five decades, Markov chain Monte Carlo (MCMC) methods have been developed as a versatile and powerful tool for scientific computing. However, as known by many researchers, conventional MCMC methods are prone to get trapped in local energy minima in simulations from a system with a rugged energy landscape, rendering the simulations inefficient. To overcome this difficulty, the investigaor and his collaborators recently proposed a non-Markov chain Monte Carlo algorithm, the so-called stochastic approximation Monte Carlo (SAMC) algorithm. Extensive numerical results show that SAMC can outperform its MCMC competitors for many hard computational problems, such as molecular structure prediction, phylogenetic tree reconstruction, and complex model selection problems. This project continues to develop SAMC in both theory and methodology. First, SAMC is generalized by allowing some statistical smoothing techniques to be used in iterations to improve its efficiency. A rigorous theory is established concerning the convergence and asymptotic behavior of the generalized algorithm. Second, SAMC is generalized by changing its current discrete setting to continuous one. The resulting algorithm is particularly suitable for solving marginal density estimation problems. Third, SAMC is further improved by making use of some techniques developed in evolutionary computing. Preliminary results show that the performance of SAMC can be significantly improved by the new developments.This project provides some advanced computational methods, which can play an important role in solving some hard scientific problems, such as molecular structure prediction, phylogeny analysis, genetic network inference, machine learning, and VLSI design. Successful computation to these problems in turn enhances people's understanding to them. This project has broader impacts in both communities of statistical theory and scientific computing. The research results are disseminated to these communities via PI's direct collaboration with researchers in other disciplines, conference presentations, books, and papers published in academic journals. This project has also significant impacts on education through direct involvement of graduate students and incorporation of results into undergraduate and graduate courses.