ACCELERATION ON ADAPTIVE IMPORTANCE SAMPLING WITH SAMPLE AVERAGE APPROXIMATION

作者：Kawai Reiichiro^*

来源：SIAM Journal on Scientific Computing, 2017, 39(4): A1586-A1615.

DOI：10.1137/15M1047192

• central limit theorem
• exponential family
• importance sampling
• small sample sizes
• sample average approximation
• variance reduction

We construct and analyze acceleration techniques for adaptive Monte Carlo simulations for general multivariate probability laws when the sample average approximation is employed for optimal parameter search. Our goal is to accelerate the adaptive Monte Carlo estimation by leading the parameter search line based on the sample average approximation to reach a nearly optimal realm at its small sample size stage. First, we introduce an auxiliary parameter into the parameter search line and update it wisely to aim for small-sample convergence. All three lines of the algorithm (the Monte Carlo averaging, the importance sampling parameter search, and the auxiliary parameter updating) run concurrently in a fully automated manner with a common set of random vectors without ad hoc tuning of the simulation system. We next propose and examine various criteria for the auxiliary parameter updating, all under which the asymptotic normality of the estimator of the desired mean and of the importance sampling parameter hold true. To illustrate the applicability and effectiveness of the proposed methods, we provide numerical results throughout the paper with particular attention toward the very early stages of the algorithm. In particular, direct use of the importance sampling parameter as the auxiliary parameter has the great potential to accelerate the parameter search line, and thus the Monte Carlo averaging as a consequence, by orders of magnitude without further restriction of the parameter domain or additional computing effort.

• 出版日期2017