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.