Gang Zhao

January 2011
Structured DataBase Monte Carlo (SDMC): An Approach to Efficient Parametric Estimation
Committee Members: Advisor: Pirooz Vakili, SE/ME; Ioannis Paschalidis, SE/ECE; Jerome Detemple, Economics & Finance; Kostas Kardaras, Mathematics & Statistics

Abstract: Monte Carlo (MC) simulation is a very general and flexible method for estimation of quantities of interest in stochastic models used in diverse areas of science and engineering. While the convergence rate of the method, by contrast to deterministic algorithms, does not grow with problem dimension and depends only on the number of random samples, its computational cost can be substantial due to the slow rate of convergence of the MC estimator. As a result, a large class of efficient Monte Carlo algorithms includes methods to reduce the variance of the MC estimator. They are referred to as Variance Reduction Techniques (VRTs). Most of these techniques cannot be generically applied and depend on special features of the specific estimation problems that need to be discovered by users one problem type at a time.

Inthisthesisitisassumedthattheestimationproblemdependsonamodelordecisionparameter. Inthis parametric setting a new class of efficient MC algorithms, called Structured Database Monte Carlo (SDMC), is introduced that can be generically used in a wide class of parametric estimation problems. The approach relies on computational learning at a nominal parameter value in order to gain efficiency when estimating at neighboring parameters and is based on the variance reduction technique of stratification.

To analyze the convergence properties of the algorithm a novel connection between variance reduction techniques and the framework of Information Based Complexity (IBC) is established. It is shown that under some assumptions the SDMC algorithm achieves the optimal worst case convergence rate. Additional optimal properties of the algorithm are established. Computational experiments are provided to illustrate the significant computational efficiencies that can be gained. Settings under which the direct application of the approach is not appropriate or effective are discussed and variants of the algorithm that can be used in these setting are presented. Extensions of the approach to problems where the perturbation is in model dynamics rather than model parameters are provided.