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

arXiv: https://arxiv.org/abs/2111.02204 · HTML: https://mlsanity.com/paper/2111.02204/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 90 references that are in the map.
- First posted on arXiv 3 Nov 2021.

## Builds on (most cited first, 12 of 12)

- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Neural Importance Sampling](https://mlsanity.com/paper/1808.03856/) (2018)
- [Scalable End-to-End Autonomous Vehicle Testing via Rare-event Simulation](https://mlsanity.com/paper/1811.00145/) (2018)
- [Adaptive Stress Testing for Autonomous Vehicles](https://mlsanity.com/paper/1902.01909/) (2019)
- [A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical Systems](https://mlsanity.com/paper/2005.02979/) (2020)
- [A Statistical Approach to Assessing Neural Network Robustness](https://mlsanity.com/paper/1811.07209/) (2018)
- [Accelerated Evaluation of Automated Vehicles Safety in Lane Change Scenarios Based on Importance Sampling Techniques](https://mlsanity.com/paper/1605.04965/) (2016)
- [Accelerated Evaluation of Automated Vehicles Using Piecewise Mixture Models](https://mlsanity.com/paper/1701.08915/) (2017)
- [Achieving Efficiency in Black Box Simulation of Distribution Tails with Self-structuring Importance Samplers](https://mlsanity.com/paper/2102.07060/) (2021)
- [An Accelerated Approach to Safely and Efficiently Test Pre-Production Autonomous Vehicles on Public Streets](https://mlsanity.com/paper/1805.02114/) (2018)
- [Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks](https://mlsanity.com/paper/1911.05059/) (2019)
- [From the Lab to the Street: Solving the Challenge of Accelerating Automated Vehicle Testing](https://mlsanity.com/paper/1707.04792/) (2017)

## Built on by (most cited first, 3 of 3)

- [A Flow-Based Generative Model for Rare-Event Simulation](https://mlsanity.com/paper/2305.07863/) (2023)
- [Test Against High-Dimensional Uncertainties: Accelerated Evaluation of Autonomous Vehicles with Deep Importance Sampling](https://mlsanity.com/paper/2204.02351/) (2022)
- [Adaptive Splitting of Reusable Temporal Monitors for Rare Traffic Violations](https://mlsanity.com/paper/2405.15771/) (2024)

## Abstract (arXiv)

Rare-event simulation techniques, such as importance sampling (IS), constitute powerful tools to speed up challenging estimation of rare catastrophic events. These techniques often leverage the knowledge and analysis on underlying system structures to endow desirable efficiency guarantees. However, black-box problems, especially those arising from recent safety-critical applications of AI-driven physical systems, can fundamentally undermine their efficiency guarantees and lead to dangerous under-estimation without diagnostically detected. We propose a framework called Deep Probabilistic Accelerated Evaluation (Deep-PrAE) to design statistically guaranteed IS, by converting black-box samplers that are versatile but could lack guarantees, into one with what we call a relaxed efficiency certificate that allows accurate estimation of bounds on the rare-event probability. We present the theory of Deep-PrAE that combines the dominating point concept with rare-event set learning via deep neural network classifiers, and demonstrate its effectiveness in numerical examples including the safety-testing of intelligent driving algorithms.