Mixing Regimes for Adaptive Markov Chain Monte Carlo

点击翻译按钮获取中文摘要

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.***