Adaptive Importance Sampling for Efficient Stochastic Root Finding and Quantile Estimation

Shengyi He (), Guangxin Jiang (), Henry Lam () and Michael C. Fu ()
Additional contact information
Shengyi He: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Guangxin Jiang: School of Management, Harbin Institute of Technology, Harbin 150001, China
Henry Lam: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Michael C. Fu: Institute for Systems Research, University of Maryland, College Park, Maryland 20740; Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742

Operations Research, 2024, vol. 72, issue 6, 2612-2630

Abstract: In solving simulation-based stochastic root-finding or optimization problems that involve rare events, such as in extreme quantile estimation, running crude Monte Carlo can be prohibitively inefficient. To address this issue, importance sampling can be employed to drive down the sampling error to a desirable level. However, selecting a good importance sampler requires knowledge of the solution to the problem at hand, which is the goal to begin with and thus forms a circular challenge. We investigate the use of adaptive importance sampling to untie this circularity. Our procedure sequentially updates the importance sampler to reach the optimal sampler and the optimal solution simultaneously, and can be embedded in both sample-average-approximation-type algorithms and stochastic-approximation-type algorithms. Our theoretical analysis establishes strong consistency and asymptotic normality of the resulting estimators. We also demonstrate, via a minimax perspective, the key role of using adaptivity in controlling asymptotic errors. Finally, we illustrate the effectiveness of our approach via numerical experiments.

Keywords: Simulation; Monte Carlo simulation; importance sampling; adaptive algorithms; quantile estimation; stochastic root finding; stochastic optimization; central limit theorem (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.2484 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:6:p:2612-2630

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().