Development of Stochastic Approximation Monte Carlo Methods

在过去的五十年中，马尔可夫链蒙特卡罗（MCMC）方法已经发展成为一种通用的、强大的科学计算工具。然而，正如许多研究人员所知，传统的MCMC方法在模拟具有崎岖能量景观的系统时容易陷入局部能量极小，从而导致模拟效率低下。为了克服这个困难，研究者和他的合作者最近提出了一种非马尔可夫链蒙特卡罗算法，即所谓的随机逼近蒙特卡罗（SAMC）算法。大量的数值结果表明，SAMC在分子结构预测、系统发育树重建和复杂模型选择等许多难计算问题上都优于MCMC。该项目继续在理论和方法上发展SAMC。首先，通过允许在迭代中使用一些统计平滑技术来推广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.