Recursive Estimation of a Failure Probability for a Lipschitz Function

Bernard, Lucie; Cohen, Albert; Guyader, Arnaud; Malrieu, Florent

The SMAI Journal of computational mathematics, Tome 8 (2022), pp. 75-97.

Let $g:\Omega ={[0,1]}^d\to ℝ$ denote a Lipschitz function that can be evaluated at each point, but at the price of a heavy computational time. Let $X$ stand for a random variable with values in $\Omega$ such that one is able to simulate, at least approximately, according to the restriction of the law of $X$ to any subset of $\Omega$. For example, thanks to Markov chain Monte Carlo techniques, this is always possible when $X$ admits a density that is known up to a normalizing constant. In this context, given a deterministic threshold $T$ such that the failure probability $p:=\mathbb{P}\left(g\right(X)>T)$ may be very low, our goal is to estimate the latter with a minimal number of calls to $g$. In this aim, building on Cohen et al. [9], we propose a recursive and (in a certain sens) optimal algorithm that selects on the fly areas of interest and estimates their respective probabilities.

Classification : 60J20, 65C05, 65C05, 68Q25, 68W20
Mots clés : Sequential design, Probability of failure, Sequential Monte Carlo, Tree based algorithms, High dimension

[1] Au, S. K.; Beck, J. L. Estimation of small failure probabilities in high dimensions by subset simulation, Probabilistic Engineering Mechanics, Volume 16 (2001) no. 4, pp. 263-277 | DOI

[2] Au, S. K.; Beck, J. L. Subset Simulation and its Application to Seismic Risk Based on Dynamic Analysis, Journal of Engineering Mechanics, Volume 129 (2003) no. 8, pp. 901-917 | DOI

[3] Bect, J.; Ginsbourger, D.; Li, L.; Picheny, V.; Vazquez, E. Sequential design of computer experiments for the estimation of a probability of failure, Stat. Comput., Volume 22 (2012) no. 3, pp. 773-793 | DOI | MR

[4] Bect, J.; Li, L.; Vazquez, E. Bayesian Subset Simulation, SIAM/ASA J. Uncertain. Quantif., Volume 5 (2017) no. 1, pp. 762-786 | DOI | MR | Zbl

[5] Bucklew, J. A. Introduction to rare event simulation, Springer Series in Statistics, Springer, 2004, xii+260 pages | DOI | MR

[6] Cérou, F.; Del Moral, P.; Furon, T.; Guyader, A. Sequential Monte Carlo for rare event estimation, Stat. Comput., Volume 22 (2012) no. 3, pp. 795-808 | DOI | MR | Zbl

[7] Cérou, F.; Guyader, A. Fluctuation analysis of adaptive multilevel splitting, Ann. Appl. Probab., Volume 26 (2016) no. 6, pp. 3319-3380 | DOI | MR | Zbl

[8] Cérou, F.; Guyader, A.; Rousset, M. Adaptive multilevel splitting: Historical perspective and recent results, Chaos: An Interdisciplinary Journal of Nonlinear Science, Volume 29 (2019) no. 4, p. 043108 | DOI | MR | Zbl

[9] Cohen, A.; Devore, R.; Petrova, G.; Wojtaszczyk, P. Finding the minimum of a function, Methods Appl. Anal., Volume 20 (2013) no. 4, pp. 365-381 | DOI | MR

[10] Ditlevsen, O.; Madsen, H. O. Structural reliability methods, 178, Wiley New York, 1996

[11] Evans, L. C.; Gariepy, R. F. Measure theory and fine properties of functions, Studies in Advanced Mathematics, CRC Press, 1992, viii+268 pages | MR | Zbl

[12] Guyader, A.; Hengartner, N.; Matzner-Løber, E. Simulation and Estimation of Extreme Quantiles and Extreme Probabilities, Appl. Math. Optim., Volume 64 (2011), pp. 171-196 | DOI | MR | Zbl

[13] Harbitz, A. An efficient sampling method for probability of failure calculation, Structural Safety, Volume 3 (1986) no. 2, pp. 109-115 | DOI

[14] Kahn, H.; Harris, T. E. Estimation of particle transmission by random sampling, National Bureau of Standards Appl. Math. Series, Volume 12 (1951), pp. 27-30

[15] Neveu, J. Arbres et processus de Galton-Watson, Ann. Inst. Henri Poincaré, Volume 22 (1986) no. 2, pp. 199-207 | Numdam | MR | Zbl

[16] Rasmussen, C. E.; Williams, C. K. I. Gaussian processes for machine learning, Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2006, xviii+248 pages | MR

[17] Schöbi, R.; Sudret, B.; Wiart, J. Polynomial-chaos-based Kriging, Int. J. Uncertain. Quantif., Volume 5 (2015) no. 2, pp. 171-193 | DOI | MR

[18] Tierney, L. Markov chains for exploring posterior distributions, Ann. Stat., Volume 22 (1994) no. 4, pp. 1701-1762 (With discussion and a rejoinder by the author) | DOI | MR | Zbl