Mixing Regimes for Adaptive Markov Chain Monte Carlo

计算复杂积分是贝叶斯统计和其他科学的核心计算问题。马尔可夫链蒙特卡罗（MCMC）是一种通用的计算工具，它生成一系列保证收敛于期望积分的估计。MCMC的一大优点是它不需要太多的努力：即使是需要计算困难积分的新手用户也可以快速生成许多保证工作的MCMC算法。不幸的是，通常情况下，大多数这些算法效率太低，无法发挥作用。因此，在实践中，用户必须花时间寻找“好的”MCMC算法。自适应MCMC （AMCMC）试图通过迭代地改进底层MCMC算法来自动化这个过程，因为它改进了对积分的估计，最终学习到一个好的算法和一个好的积分估计。如果成功，AMCMC扩展了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.