Maximally Adaptive Nonparametric Importance Sampling

Maximally Adaptive Nonparametric Importance Sampling

Boks, A.

Meester, L.E. (mentor)

Electrical Engineering, Mathematics and Computer Science

Applied mathematics

Probability

2012-03-22

Nowadays, Monte Carlo integration is a popular tool for estimating high-dimensional, complex integrals. Its scope of application can be widened if ways can be found to produce estimates with smaller variance at the same computational cost. Variance reduction techniques aim to accomplish this. In particular, using importance sampling with the so-called zero-variance distribution would result in a simulation procedure with variance zero. Unfortunately the zero-variance distribution cannot be constructed in practice, as it requires knowledge of the value to be estimated. In this thesis we look at how iterative approximation of the zero-variance distribution can be exploited to yield more efficient Monte Carlo simulations, a technique called adaptive importance sampling. We will explore the characteristics of existing methods for adaptive importance sampling, and prove some generic limit theorems for such methods. Based on the methods by Ping Zhang, which use kernel density estimation to approximate the zero-variance distribution, we then propose Maximally Adaptive Nonparametric Importance Sampling. This variation aims to make better use of the information available by updating its approximation to the zero-variance distribution after every generated sample. We will show that the method (when using n samples) yields an estimator with an asymptotic variance of O(ln(n)n^{-7/6}), faster than methods (eventually) based on i.i.d. replicates. We illustrate the empirical convergence of the method with a simulation experiment, and briefly discuss the issues and considerations related to application of the method in practice.

Monte Carlo
Importance Sampling
variance reduction
Adaptive Importance Sampling
nonparametric
kernel density estimator
zero-variance

http://resolver.tudelft.nl/uuid:ca591240-ffcf-4624-81bb-ec020b853255

Student theses

master thesis

(c) 2012 Boks, A.