Certifiable Deep Importance Sampling for Rare-Event Simulation of Black Box Systems

References

• Ackerman E (2016) Fatal Tesla self-driving car crash reminds us that robots aren’t perfect. IEEE Spectrum (July 1), https://spectrum.ieee.org/fatal-tesla-autopilot-crash-reminds-us-that-robots-arent-perfect.Google Scholar
• Arief M, Glynn P, Zhao D (2018) An accelerated approach to safely and efficiently test pre-production autonomous vehicles on public streets. Zhang W-B, Bayen AM, Sánchez Medina JJ, Barth MJ, eds. Proc. 21st Internat. Conf. Intelligent Transportation Systems (IEEE, Piscataway, NJ), 2006–2011.Google Scholar
• Arief M, Huang Z, Kumar GKS, Bai Y, He S, Ding W, Lam H, et al. (2021) Deep probabilistic accelerated evaluation: A robust certifiable rare-event simulation methodology for black box safety-critical systems. Banerjee A, Fukumizu K, eds. Proc. Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 595–603.Google Scholar
• Asmussen S, Albrecher H (2010) Ruin Probabilities, vol. 14 (World Scientific, Hackensack, NJ).Crossref, Google Scholar
• Asmussen S, Kroese DP (2006) Improved algorithms for rare event simulation with heavy tails. Adv. Appl. Probability 38(2):545–558.Crossref, Google Scholar
• Au SK, Beck JL (2001) Estimation of small failure probabilities in high dimensions by subset simulation. Probabilistic Engrg. Mechanics 16(4):263–277.Crossref, Google Scholar
• Blanchet J, Glynn P (2008) Efficient rare-event simulation for the maximum of heavy-tailed random walks. Ann. Appl. Probability 18(4):1351–1378.Crossref, Google Scholar
• Blanchet J, Lam H (2012) State-dependent importance sampling for rare-event simulation: An overview and recent advances. Surveys 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 JH, Liu J (2008) State-dependent importance sampling for regularly varying random walks. Adv. Appl. Probability 40(4):1104–1128.Crossref, Google Scholar
• Blanchet J, Glynn P, Leder K (2012a) On Lyapunov inequalities and subsolutions for efficient importance sampling. ACM Trans. Modeling Comput. Simulation 22(3):13:1–13:27.Crossref, Google Scholar
• Blanchet J, Lam H, Zwart B (2012b) Efficient rare-event simulation for perpetuities. Stochastic Processes Appl. 122(10):3361–3392.Crossref, Google Scholar
• Bonami P, Kilinç M, Linderoth J (2012) Algorithms and software for convex mixed integer nonlinear programs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming, IMA Volumes in Mathematicsand Its Applications, vol. 154 (Springer, New York), 1–39.Crossref, Google Scholar
• Botev ZI, L’Ecuyer P, Tuffin B (2013) Markov chain importance sampling with applications to rare event probability estimation. Statist. Comput. 23(2):271–285.Crossref, Google Scholar
• Botev ZI, Ridder A, Rojas-Nandayapa L (2016) Semiparametric cross entropy for rare-event simulation. J. Appl. Probability 53(3):633–649.Crossref, Google Scholar
• Bucklew J (2013) Introduction to Rare Event Simulation (Springer Science & Business Media, New York).Google Scholar
• Bucklew JA (2004) Rare Event Simulation for Level Crossing and Queueing Models (Springer, New York).Crossref, Google Scholar
• Budhiraja A, Dupuis P (2019) Analysis and Approximation of Rare Events: Representations and Weak Convergence Methods (Springer, New York).Crossref, Google Scholar
• Cérou F, Guyader A (2007) Adaptive multilevel splitting for rare event analysis. Stochastic Anal. Appl. 25(2):417–443.Crossref, Google Scholar
• Cérou F, Guyader A (2016) Fluctuation analysis of adaptive multilevel splitting. Ann. Appl. Probability 26(6):3319–3380.Crossref, Google Scholar
• Cérou F, Guyader A, Rousset M (2019) Adaptive multilevel splitting: Historical perspective and recent results. Chaos: Interdisciplinary J. Nonlinear Sci. 29(4):043108.Crossref, 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
• Clarke EM, Henzinger TA, Veith H, Bloem R (2018) Handbook of Model Checking, vol. 10 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• Claybrook J, Kildare S (2018) Autonomous vehicles: No driver… no regulation? Science (1979) 361(6397):36–37.Google Scholar
• Collamore JF (2002) Importance sampling techniques for the multidimensional ruin problem for general Markov additive sequences of random vectors. Ann. Appl. Probability 12(1):382–421.Crossref, Google Scholar
• Corso A, Moss RJ, Koren M, Lee R, Kochenderfer MJ (2021) A survey of algorithms for black-box safety validation of cyber-physical systems. J. Artificial Intelligence Res. 72:377–428.Google Scholar
• De Boer PT, Kroese DP, Mannor S, Rubinstein RY (2005) A tutorial on the cross-entropy method. Ann. Oper. Res. 134(1):19–67.Crossref, Google Scholar
• Dean T, Dupuis P (2009) Splitting for rare event simulation: A large deviation approach to design and analysis. Stochastic Processes Appl. 119(2):562–587.Crossref, Google Scholar
• Dembo A, Zeitouni O (2010) Large Deviations Techniques and Applications (Springer-Verlag, Heidelberg).Crossref, Google Scholar
• Deo A, Murthy K (2023) Achieving efficiency in black box simulation of distribution tails with self-structuring importance samplers. Oper. Res. 73(1):325–343.Google Scholar
• Dieker A, Mandjes M (2005) On asymptotically efficient simulation of large deviation probabilities. Adv. Appl. Probability 37(2):539–552.Crossref, Google Scholar
• Dieker AB, Mandjes M (2006) Fast simulation of overflow probabilities in a queue with Gaussian input. ACM Trans. Modeling Comput. Simulations 16(2):119–151.Crossref, Google Scholar
• Dupuis P, Ellis RS (2011) A Weak Convergence Approach to the Theory of Large Deviations, vol. 902 (John Wiley & Sons, New York).Google Scholar
• Dupuis P, Leder K, Wang H (2009) Importance sampling for weighted-serve-the-longest-queue. Math. Oper. Res. 34(3):642–660.Link, Google Scholar
• Ellis RS (1984) Large deviations for a general class of random vectors. Ann. Probability 12(1):1–12.Crossref, Google Scholar
• Feng Y, Yu C, Xu S, Liu HX, Peng H (2018) An augmented reality environment for connected and automated vehicle testing and evaluation. Proc. IEEE Intelligent Vehicles Sympos. (IEEE, Piscataway, NJ), 1549–1554.Google Scholar
• Gärtner J (1977) On large deviations from the invariant measure. Theory Probability Appl. 22(1):24–39.Crossref, Google Scholar
• Glasserman P (2004) Monte Carlo Methods in Financial Engineering (Springer, New York).Crossref, Google Scholar
• Glasserman P, Wang Y (1997) Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probability 7(3):731–746.Crossref, Google Scholar
• Glasserman P, Heidelberger P, Shahabuddin P, Zajic T (1999) Multilevel splitting for estimating rare event probabilities. Oper. Res. 47(4):585–600.Link, Google Scholar
• Glynn PW, Iglehart DL (1989) Importance sampling for stochastic simulations. Management Sci. 35(11):1367–1392.Link, Google Scholar
• Grace AW, Kroese DP, Sandmann W (2014) Automated state-dependent importance sampling for Markov jump processes via sampling from the zero-variance distribution. J. Appl. Probability 51(3):741–755.Crossref, Google Scholar
• Guyader A, Hengartner N, Matzner-Løber E (2011) Simulation and estimation of extreme quantiles and extreme probabilities. Appl. Math. Optim. 64(2):171–196.Crossref, Google Scholar
• Heidelberger P (1995) Fast simulation of rare events in queueing and reliability models. ACM Trans. Modeling Comput. Simulations 5(1):43–85.Crossref, Google Scholar
• Huang Z, Lam H, Zhao D (2018) Designing importance samplers to simulate machine learning predictors via optimization. Rabe M, Juan AA, Mustafee N, Skoogh A, Jain S, Johansson B, eds. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 1730–1741.Google Scholar
• Huang Z, Lam H, LeBlanc DJ, Zhao D (2018) 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. Modeling Comput. Simulations 22(2):8:1–8:21.Google Scholar
• Juneja S, Shahabuddin P (2006) Rare-event simulation techniques: An introduction and recent advances. Henderson SG, Nelson BL, eds. Handbooks in Operations Research and Management Science, vol. 13 (Elsevier/North-Holland, Amsterdam), 291–350.Crossref, Google Scholar
• Kalra N, Paddock SM (2016) Driving to safety: How many miles of driving would it take to demonstrate autonomous vehicle reliability? Transportation Res. Part A: Policy Practice 94:182–193.Crossref, Google Scholar
• Koopman P, Wagner M (2017) Autonomous vehicle safety: An interdisciplinary challenge. IEEE Intelligent Transportation Systems Magazine 9(1):90–96.Crossref, Google Scholar
• Koren M, Alsaif S, Lee R, Kochenderfer MJ (2018) Adaptive stress testing for autonomous vehicles. Proc. IEEE Intelligent Vehicles Sympos. (IEEE, Piscataway, NJ), 1898–1904.Google Scholar
• Kroese DP, Nicola VF (1999) Efficient estimation of overflow probabilities in queues with breakdowns. Performance Evaluation 36–37(1–4):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. Modeling Comput. Simulations 20(1):1–41.Crossref, Google Scholar
• Legriel J, Le Guernic C, Cotton S, Maler O (2010) Approximating the pareto front of multi-criteria optimization problems. Esparza J, Majumdar R, eds. Tools and Algorithms for the Construction and Analysis of Systems (Springer, Berlin), 69–83.Crossref, Google Scholar
• Müller T, Mcwilliams B, Rousselle F, Gross M, Novák J (2019) Neural importance sampling. ACM Trans. Graph 38(5):45:1–145:19.Crossref, Google Scholar
• Murthy KRA, Juneja S, Blanchet J (2014) State-independent importance sampling for random walks with regularly varying increments. Stochastic Systems 4(2):321–374.Link, Google Scholar
• NHTSA (2007) The new car assessment program suggested approaches for future program enhancements. Report No. DOT HS 810 698 (National Highway Traffic Safety Administration, U.S. Department of Transportation, Washington, DC).Google Scholar
• Nicola VF, Shahabuddin P, Nakayama MK (2001) Techniques for fast simulation of models of highly dependable systems. IEEE Trans. Reliability 50(3):246–264.Crossref, Google Scholar
• NTSB (2016) Preliminary report, highway HWY16FH018. Accessed July 14, 2026, http://www.ntsb.gov/investigations/AccidentReports/Pages/HWY16FH018-preliminary.aspx.Google Scholar
• Nyquist P (2017) Moderate deviation principles for importance sampling estimators of risk measures. J. Appl. Probability 54(2):490–506.Crossref, 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. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems (Curran Associates, RedHook, NY), 9827–9838.Google Scholar
• Orzechowski PF, Li K, Lauer M (2019) Towards responsibility-sensitive safety of automated vehicles with reachable set analysis. Proc. IEEE Internat. Conf. Connected Vehicles Expo (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Rubino G, Tuffin B (2009) Markovian models for dependability analysis. Rubino G, Tuffin B, eds. Rare Event Simulation Using Monte Carlo Methods (John Wiley, Hoboken, NJ), 125–144.Crossref, Google Scholar
• Rubinstein RY (2005) A stochastic minimum cross-entropy method for combinatorial optimization and rare-event estimation. Methodology Comput. Appl. Probability 7(1):5–50.Crossref, Google Scholar
• Rubinstein RY, Kroese DP (2013) The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning (Springer Science & Business Media, New York).Google Scholar
• Sadowsky JS (1991) Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue. IEEE Trans. Automated 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
• Siegmund D (1976) Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4(4):673–684.Crossref, Google Scholar
• Tjeng V, Xiao K, Tedrake R (2019) Evaluating robustness of neural networks with mixed integer programming. 7th Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Treiber M, Hennecke A, Helbing D (2000) Congested traffic states in empirical observations and microscopic simulations. Phys. Rev. E 62(2):1805–1824.Crossref, Google Scholar
• Tuffin B, Ridder A (2012) Probabilistic bounded relative error for rare event simulation learning techniques. Laroque C, Himmelspach J, Pasupathy R, Rose O, Uhrmacher AM, eds. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 442–453.Google Scholar
• Uesato J, Kumar A, Szepesvari C, Erez T, Ruderman A, Anderson K, Heess N, et al. (2019) Rigorous agent evaluation: An adversarial approach to uncover catastrophic failures. 7th Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Villén-Altamirano J (2010) Importance functions for restart simulation of general Jackson networks. Eur. J. Oper. Res. 203(1):156–165.Crossref, Google Scholar
• Villén-Altamirano M, Villén-Altamirano J (1994) Restart: A straightforward method for fast simulation of rare events. Tew JD, Manivannan S, Sadowski DA, Seila AF, eds. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 282–289.Google Scholar
• Wang X, Jiang R, Li L, Lin Y, Zheng X, Wang F (2018) Capturing car-following behaviors by deep learning. IEEE Trans. Intelligent Transportation Systems 19(3):910–920.Crossref, Google Scholar
• Webb S, Rainforth T, Teh YW, Kumar MP (2019) A statistical approach to assessing neural network robustness. 7th Internat. Conf. Learn. Representations (OpenReview.net).Google Scholar
• Wegener J, Bühler O (2004) Evaluation of different fitness functions for the evolutionary testing of an autonomous parking system. Deb K, Poli R, Banzhaf W, Beyer H-G, Burke E, Darwen P, Dasgupta D, et al., eds. Proc. Genetic Evolutionary Comput. Conf. (Springer-Verlag, Heidelberg), 1400–1412.Google Scholar
• Wu X, Gomes-Selman J, Shi Q, Xue Y, García-Villacorta R, Anderson E, Sethi S, et al. (2018) Efficiently approximating the pareto frontier: Hydropower dam placement in the Amazon basin. McIlraith SA, Weinberger KQ, eds. Proc. Thirty-Second AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 849–858.Google Scholar
• Zhao D, Peng H (2018) From the lab to the street: Solving the challenge of accelerating automated vehicle testing. Hitachi Rev. 67(1):014–015.Google Scholar
• Zhao D, Huang X, Peng H, Lam H, LeBlanc DJ (2017) 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