Adaptive Monte Carlo Integration

• Author / Creator

  Neufeld, James, P

• Monte Carlo methods are a simple, effective, and widely deployed way of approximating integrals that prove too challenging for deterministic approaches. This thesis presents a number of contributions to the field of adaptive Monte Carlo methods. That is, approaches that automatically adjust the behaviour of the sampling algorithm to better suit the targeted integrand. The first of such contributions is the introduction of a new method, antithetic Markov chain sampling, which improves sampling efficiency through the use of simulated Markov chains. These chains effectively guide the sampling toward more influential regions of the integrand (modes). We demonstrate that this approach leads to unbiased estimators and offers significant improvements over standard approaches on challenging multi-modal integrands. We next consider the complementary task of efficiently allocating computation between a set of unbiased samplers through observations of their past performance. Here, we show that this problem is equivalent to the well known stochastic multi-armed bandit problem and, as a result, existing algorithms and theoretical guarantees transfer immediately which gives rise to new results for the adaptive Monte Carlo setting. We then extend this framework to cover an important practical condition, where each individual sampler (bandit arm) may take a random amount of computation time to produce a sample. Here, we again show that existing bandit algorithms can be applied through the use of a simple sampling trick, and prove new results which bounding the regret for any such algorithm from above. Lastly, we consider the task of combining a set of unbiased Monte Carlo estimators, with unique variances and samples sizes, into a single estimator. We show that upper-confidence approaches similar to those used in the multi-armed bandit literature lead to estimators that improve on existing solutions both theoretically and in practice. Interestingly, each of these contributions may be applied in parallel and in complement to one another to produce any number of highly adaptable, robust, and practical Monte Carlo integration algorithms.

• Subjects / Keywords

  • Machine Learning
  • Monte Carlo
  • Multi-armed Bandits
  • Online Learning

• Graduation date

  Spring 2016

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3PC2TH65

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.