Recursive Estimation of a Failure Probability for a Lipschitz Function

Lucie Bernard; Albert Cohen; Arnaud Guyader; Florent Malrieu

doi:10.5802/smai-jcm.80

Lucie Bernard ¹; Albert Cohen ²; Arnaud Guyader ³; Florent Malrieu ¹

¹ IDP, Université de Tours, France
² LJLL, Sorbonne Université, France
³ LPSM, Sorbonne Université, France

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

Abstract

Let $g : Ω = {[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 $Ω$ such that one is able to simulate, at least approximately, according to the restriction of the law of $X$ to any subset of $Ω$ . 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 : = ℙ (g (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.

Published online: 2022-04-08

DOI: 10.5802/smai-jcm.80

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

Author's affiliations:

Lucie Bernard ¹; Albert Cohen ²; Arnaud Guyader ³; Florent Malrieu ¹

¹ IDP, Université de Tours, France
² LJLL, Sorbonne Université, France
³ LPSM, Sorbonne Université, France

License:

CC-BY-NC-ND 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{SMAI-JCM_2022__8__75_0,
     author = {Lucie Bernard and Albert Cohen and Arnaud Guyader and Florent Malrieu},
     title = {Recursive {Estimation} of a {Failure} {Probability} for a {Lipschitz} {Function}},
     journal = {The SMAI Journal of computational mathematics},
     pages = {75--97},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {8},
     year = {2022},
     doi = {10.5802/smai-jcm.80},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.80/}
}

TY  - JOUR
AU  - Lucie Bernard
AU  - Albert Cohen
AU  - Arnaud Guyader
AU  - Florent Malrieu
TI  - Recursive Estimation of a Failure Probability for a Lipschitz Function
JO  - The SMAI Journal of computational mathematics
PY  - 2022
SP  - 75
EP  - 97
VL  - 8
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.80/
DO  - 10.5802/smai-jcm.80
LA  - en
ID  - SMAI-JCM_2022__8__75_0
ER  -

%0 Journal Article
%A Lucie Bernard
%A Albert Cohen
%A Arnaud Guyader
%A Florent Malrieu
%T Recursive Estimation of a Failure Probability for a Lipschitz Function
%J The SMAI Journal of computational mathematics
%D 2022
%P 75-97
%V 8
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.80/
%R 10.5802/smai-jcm.80
%G en
%F SMAI-JCM_2022__8__75_0

Lucie Bernard; Albert Cohen; Arnaud Guyader; Florent Malrieu. Recursive Estimation of a Failure Probability for a Lipschitz Function. The SMAI Journal of computational mathematics, Volume 8 (2022), pp. 75-97. doi : 10.5802/smai-jcm.80. https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.80/

References
Cited by

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

[2] S. K. Au; J. L. Beck 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] J. Bect; D. Ginsbourger; L. Li; V. Picheny; E. Vazquez 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] J. Bect; L. Li; E. Vazquez Bayesian Subset Simulation, SIAM/ASA J. Uncertain. Quantif., Volume 5 (2017) no. 1, pp. 762-786 | DOI | MR | Zbl

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

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

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

[8] F. Cérou; A. Guyader; M. Rousset 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] A. Cohen; R. Devore; G. Petrova; P. Wojtaszczyk Finding the minimum of a function, Methods Appl. Anal., Volume 20 (2013) no. 4, pp. 365-381 | DOI | MR

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

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

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

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

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

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

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

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

[18] L. Tierney 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

Cited by Sources: