Overconservativeness of Variance-Based Efficiency Criteria and Probabilistic Efficiency in Rare-Event Simulation

References

• Arief M, Huang Z, Koushik Senthil Kumar G, Bai Y, He S, Ding W, Lam H, Zhao D (2021) Deep probabilistic accelerated evaluation: A robust certifiable rare-event simulation methodology for black-box safety-critical systems. Proc. 24th Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), vol. 130, 595–603.Google Scholar
• Asmussen S (1985) Conjugate processes and the simulation of ruin problems. Stochastic Processes Their Appl. 20(2):213–229.Crossref, Google Scholar
• Asmussen S, Albrecher H (2010) Ruin Probabilities. Advanced Series on Statistical Science & Applied Probability, vol. 14 (World Scientific, Singapore).Google Scholar
• Asmussen S, Glynn PW (2007) Stochastic Simulation: Algorithms and Analysis, vol. 57 (Springer Science & Business Media, New York).Crossref, Google Scholar
• Bai Y, Huang Z, Lam H, Zhao D (2022) Rare-event simulation for neural network and random forest predictors. ACM Trans. Model. Comput. Simulation 32(3):1–33.Crossref, Google Scholar
• Blanchet J, Glynn P (2008) Efficient rare-event simulation for the maximum of heavy-tailed random walks. Ann. Appl. Probab. 18(4):1351–1378.Crossref, Google Scholar
• Blanchet J, Glynn P (2009) Efficient rare event simulation of continuous time markovian perpetuities. Proc. 2009 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 444–451.Google Scholar
• Blanchet J, Lam H (2012) State-dependent importance sampling for rare-event simulation: An overview and recent advances. Survey Oper. Res. Management Sci. 17(1):38–59.Crossref, Google Scholar
• Blanchet J, Lam H (2014) Rare-event simulation for many-server queues. Math. Oper. Res. 39(4):1142–1178.Link, Google Scholar
• Blanchet J, Mandjes M (2007) Editorial: Rare-event simulation for queues. Queueing Systems 57(2–3):57–59.Crossref, Google Scholar
• Blanchet J, Glynn P, Lam H (2009) Rare event simulation for a slotted time M/G/s model. Queueing Systems 63(1):33–57.Crossref, Google Scholar
• Blanchet J, Lam H, Zwart B (2012) Efficient rare-event simulation for perpetuities. Stochastic Processes Their Appl. 122(10):3361–3392.Crossref, Google Scholar
• Bucklew JA (2004) Introduction to Rare Event Simulation. Springer Series in Statistics (Springer Science & Business Media, New York). Crossref, Google Scholar
• Carrasco JA (1992) Failure distance-based simulation of repairable fault-tolerant systems. Balbo G, Srazzi G, eds. Computer Performance Evaluation: Modelling Techniques and Tools (Elsevier, Amsterdam), 351–365.Google Scholar
• Chen B, Blanchet J, Rhee CH, Zwart B (2019) Efficient rare-event simulation for multiple jump events in regularly varying random walks and compound poisson processes. Math. Oper. Res. 44(3):919–942.Link, Google Scholar
• Chen JC, Lu D, Sadowsky JS, Yao K (1993) On importance sampling in digital communications. I. Fundamentals. IEEE J. Sel. Areas Comm. 11(3):289–299.Crossref, Google Scholar
• Dembo A, Zeitouni O (2009) Large Deviations Techniques and Applications, vol. 38 (Springer Science & Business Media, New York).Google Scholar
• Ding W, Chen B, Li B, Eun KJ, Zhao D (2021) Multimodal safety-critical scenarios generation for decision-making algorithms evaluation. IEEE Robotics Automation Lett. 6(2):1551–1558.Crossref, Google Scholar
• Dupuis P, Wang H (2009) Importance sampling for Jackson networks. Queueing Systems 62(1):113–157.Crossref, Google Scholar
• Dupuis P, Sezer AD, Wang H (2007) Dynamic importance sampling for queueing networks. Ann. Appl. Probab. 17(4):1306–1346.Crossref, Google Scholar
• Glasserman P (2003) Monte Carlo Methods in Financial Engineering of Stochastic Modelling and Applied Probability, vol. 53 (Springer, New York).Crossref, Google Scholar
• Glasserman P, Li J (2005) Importance sampling for portfolio credit risk. Management Sci. 51(11):1643–1656.Link, Google Scholar
• Glasserman P, Wang Y (1997) Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7(3):731–746.Crossref, Google Scholar
• Glasserman P, Kang W, Shahabuddin P (2008) Fast simulation of multifactor portfolio credit risk. Oper. Res. 56(5):1200–1217.Link, Google Scholar
• Goyal A, Shahabuddin P, Heidelberger P, Nicola VF, Glynn PW (1992) A unified framework for simulating Markovian models of highly dependable systems. IEEE Trans. Comput. 41(1):36–51.Crossref, Google Scholar
• Heidelberger P (1995) Fast simulation of rare events in queueing and reliability models. ACM Trans. Model. Comput. Simulation 5:43–85.Crossref, Google Scholar
• Huang Z, Lam H, Zhao D (2018a) Designing importance samplers to simulate machine learning predictors via optimization. 2018 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 1730–1741.Google Scholar
• Huang Z, Lam H, LeBlanc DJ, Zhao D (2018b) Accelerated evaluation of automated vehicles using piecewise mixture models. IEEE Trans. Intelligent Transportation Systems 19(9):2845–2855.Crossref, Google Scholar
• Hult H, Svensson J (2012) On importance sampling with mixtures for random walks with heavy tails. ACM Trans. Model. Comput. Simulation 22(2):1–21.Crossref, Google Scholar
• Juneja S, Shahabuddin P (2006) Rare-event simulation techniques: An introduction and recent advances. Henderson SG, Nelson BL, eds. Simulation. Handbooks in Operations Research and Management Science, vol. 13 (Elsevier, Amsterdam), 291–350.Crossref, Google Scholar
• Kratsios M (2019) The National Artificial Intelligence Research and Development Strategic Plan: 2019 Update (National Science and Technology Council, Washington, DC).Google Scholar
• Kroese DP, Nicola VF (1999) Efficient estimation of overflow probabilities in queues with breakdowns. Performance Evaluation 36–37:471–484.Crossref, Google Scholar
• L’Ecuyer P, Blanchet JH, Tuffin B, Glynn PW (2010) Asymptotic robustness of estimators in rare-event simulation. ACM Trans. Model. Comput. Simulation 20(1):1–41.Crossref, Google Scholar
• Lewis EE, Böhm F (1984) Monte Carlo simulation of Markov unreliability models. Nuclear Engrg. Design 77(1):49–62.Crossref, Google Scholar
• Maurer A, Pontil M (2009) Empirical Bernstein bounds and sample variance penalization. Proc. 22nd Conf. Learning Theory (COLT 2009) (PMLR, New York).Google Scholar
• O’Kelly M, Sinha A, Namkoong H, Tedrake R, Duchi JC (2018) Scalable end-to-end autonomous vehicle testing via rare-event simulation. NIPS’18: Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (ACM, New York).Google Scholar
• Ridder A (2009) Importance sampling algorithms for first passage time probabilities in the infinite server queue. Eur. J. Oper. Res. 199(1):176–186.Crossref, Google Scholar
• Rubino G, Tuffin B (2009) Rare Event Simulation Using Monte Carlo Methods (John Wiley & Sons, Ltd., Hoboken, NJ).Crossref, Google Scholar
• Sadowsky JS (1991) Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue. IEEE Trans. Automatic Control 36(12):1383–1394.Crossref, Google Scholar
• Sadowsky JS, Bucklew JA (1990) On large deviations theory and asymptotically efficient monte carlo estimation. IEEE Trans. Inform. Theory 36(3):579–588.Crossref, Google Scholar
• Shahabuddin P (1994) Importance sampling for the simulation of highly reliable Markovian systems. Management Sci. 40(3):333–352.Link, Google Scholar
• Siegmund D (1976) Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4(4):673–684.Crossref, Google Scholar
• Smith PJ, Shafi M, Gao H (1997) Quick simulation: A review of importance sampling techniques in communications systems. IEEE J. Selected Areas Comm. 15(4):597–613.Crossref, Google Scholar
• Szechtman R, Glynn PW (2002) Rare-event simulation for infinite server queues. Proc. Winter Simulation Conference, vol. 1 (IEEE, Piscataway, NJ), 416–423.Google Scholar
• Tuffin B (2004) On numerical problems in simulations of highly reliable Markovian systems. Proc. 1st Internat. Conf. Quant. Evaluation Systems (QEST 2004) (IEEE, Piscataway, NJ), 156–164.Google Scholar
• Tuffin B, Ridder A (2012) Probabilistic bounded relative error for rare event simulation learning techniques. Proc. 2012 Winter Simulation Conf. (WSC) (IEEE, Piscataway, NJ), 1–12.Google Scholar
• Webb S, Rainforth T, Teh YW, Kumar MP (2018) A statistical approach to assessing neural network robustness. Preprint, submitted November 17, https://arxiv.org/abs/1811.07209.Google Scholar
• Zhang XW, Glynn PW, Giesecke K, Blanchet J (2009) Rare event simulation for a generalized hawkes process. Proc. 2009 Winter Simulation Conference (WSC) (IEEE, Piscataway, NJ), 1291–1298.Google Scholar
• Zhao D, Huang X, Peng H, Lam H, LeBlanc DJ (2018) Accelerated evaluation of automated vehicles in car-following maneuvers. IEEE Trans. Intelligent Transportation Systems 19(3):733–744.Crossref, Google Scholar
• Zhao D, Lam H, Peng H, Bao S, LeBlanc DJ, Nobukawa K, Pan CS (2016) Accelerated evaluation of automated vehicles safety in lane-change scenarios based on importance sampling techniques. IEEE Trans. Intelligent Transportation Systems 18(3):595–607.Crossref, Google Scholar