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.