Mixing Regimes for Adaptive Markov Chain Monte Carlo

计算复杂积分是贝叶斯统计和科学中的一个核心计算问题。马尔可夫链蒙特卡罗(MCMC)是一种通用的计算工具，它通过生成一系列保证收敛到期望积分的估计来完成这一计算。MCMC的一大优点是它不需要太多的工作：即使是需要计算困难积分的新手用户也可以快速生成许多保证工作的MCMC算法。不幸的是，通常情况下，这些算法中的大多数都效率太低而没有用处。因此，在实践中，用户必须花费时间寻找“好的”MCMC算法。自适应MCMC(AMCMC)试图通过迭代改进底层MCMC算法来自动化这一过程，因为它改进了对积分的估计，最终学习到一个好的算法和一个好的积分估计。当AMCMC成功时，它扩大了MCMC方法的应用范围，而不需要太多的用户工作。AMCMC理论的研究到目前为止一直集中在时间渐近的问题上，即AMCMC最终保证何时学习到一个好的MCMC算法。我的研究目标是了解这种学习什么时候发生得足够快，足以发挥作用。更确切地说，我考虑的是描述学习发生得足够快的问题类别的“复杂性-渐近”问题，以加快积分的“良好”估计的计算。后一个问题集中在找到一个足够好的积分估计所需的时间，这是大多数用户关心的，而不是估计收敛的渐近速度，这可能对大多数用户来说实际上是看不见的。这项研究将使用户更好地了解AMCMC在哪些情况下可以帮助他们，而且这种理解的增加很可能会导致新的AMCMC算法的开发。我的建议更准确地区分了时间渐近和复杂性渐近的观点，并给出了AMCMC算法的复杂性渐近理论的轮廓。这包括新的定义，重要的早期计算和定理，以及最重要的证明某些现象的存在的方法，这些现象对于MCMC算法来说不会发生，也不能被“时间渐近”理论看到。从数学上讲，我的项目与MCMC的“混合时间”理论类似，后者是概率研究的核心领域。执行我的计划将涉及寻找经典MCMC结果的新版本或更健壮的版本，这也将增加社区对MCMC理论的理解。*

Calculating complicated integrals is a central computational problem in Bayesian statistics and the sciences. Markov chain Monte Carlo (MCMC) is a general-purpose tool for doing this computation by generating a sequence of estimates that are guaranteed to converge to the desired integral. One of MCMC's great virtues is that it doesn't require too much effort: even novice users who need to calculate difficult integrals can quickly generate many MCMC algorithms that are guaranteed to work. Unfortunately, it is often the case that most of these algorithms are too inefficient to be useful. Thus, in practice users must spend time finding `good' MCMC algorithms. Adaptive MCMC (AMCMC) attempts to automate this process by iteratively refining the underlying MCMC algorithm as it improves its estimate of the integral, eventually learning both a good algorithm and a good estimate of the integral. When successful, AMCMC expands the range of problems for which MCMC methods can be applied without too much user effort.******Research on AMCMC theory to date has focused on the `time-asymptotic' question of when AMCMC is guaranteed to learn a good MCMC algorithm eventually. The goal of my research is to understand when this learning happens quickly enough to be useful. More precisely, I consider the `complexity-asymptotic' question of describing classes of problems for which learning occurs quickly enough to speed up the computation of a `good' estimate of the integral. This latter question focuses on the time required to find a good-enough estimate of the integral, which is what most users care about, rather than the asymptotic rate at which estimates converge, which may be effectively invisible to most users. This research will give users a better understanding of the situations under which AMCMC can help them, and it is likely that the increased understanding will lead to the development of new AMCMC algorithms. My proposal makes more precise the distinction between the time- and complexity-asymptotic viewpoints and gives the outlines of a complexity-asymptotic theory of AMCMC algorithms. This includes new definitions, important early calculations and theorems, and most significantly approaches to proving the existence of certain phenomena that do not occur for MCMC algorithms and cannot be seen by the `time-asymptotic' theory. Mathematically, my project parallels the MCMC theory of `mixing times,' a central area of research in probability. Carrying out my program will involve finding new or more robust versions of classical MCMC results, and this will increase the community's understanding of MCMC theory as well.***