Grant: Discovery Grants Program - Individual
University of Ottawa
$16,000.00
Mixing Regimes for Adaptive Markov Chain Monte Carlo
EF 2015-16
Résumé
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<span style=""line-height: 1.5em;"">. 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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2015-05460
Name nom
Smith, Aaron
Department département
Mathematics and Statistics - Mathématiques et statistiques
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
16000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
3008
Research subject group en
Statistics and probability
Research subject group fr
Statistique et probabilité
Research subject en
Applied probability
Research subject fr
Probabilité appliquée
Partie
1
Nb partie
5
Application title
Mixing Regimes for Adaptive Markov Chain Monte Carlo
Keyword
NSERC
Application summary
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.<br />
<br />
Research on AMCMC theory to date has focused on the `time-asymptotic' question of when AMCMC is guaranteed to learn a good MCMC algorithm <em>eventually</em>. The goal of my research is to understand when this learning happens <em>quickly enough to be useful</em><span style=""line-height: 1.5em;"">. 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.</span><em><br />
</em>