New Bounds and Truncation Boundaries for Importance Sampling
By: Yijuan Liang, Guangxin Jiang, Michael C. Fu
Potential Business Impact:
Makes computer simulations more accurate and faster.
Importance sampling (IS) is a technique that enables statistical estimation of output performance at multiple input distributions from a single nominal input distribution. IS is commonly used in Monte Carlo simulation for variance reduction and in machine learning applications for reusing historical data, but its effectiveness can be challenging to quantify. In this work, we establish a new result showing the tightness of polynomial concentration bounds for classical IS likelihood ratio (LR) estimators in certain settings. Then, to address a practical statistical challenge that IS faces regarding potentially high variance, we propose new truncation boundaries when using a truncated LR estimator, for which we establish upper concentration bounds that imply an exponential convergence rate. Simulation experiments illustrate the contrasting convergence rates of the various LR estimators and the effectiveness of the newly proposed truncation-boundary LR estimators for examples from finance and machine learning.
Similar Papers
Stochastic Optimization with Optimal Importance Sampling
Optimization and Control
Improves computer guessing for better results.
Logarithmic Accuracy in Importance Sampling via Large Deviations
Statistics Theory
Improves computer guesses for rare events.
When Machine Learning Meets Importance Sampling: A More Efficient Rare Event Estimation Approach
Machine Learning (CS)
Makes computer networks run better by predicting problems.