Source-linked AI summary
A Multilevel Interacting Particle System Method for the estimation of Failure Probabilities
Rubén Aylwin, José Pinto
TL;DR
Failure-probability estimation requires computing whether a quantity of interest crosses a critical value. The paper combines multilevel decomposition with Interacting Particle Systems and sequential sampling, reporting faster convergence than classical Monte Carlo and MLMC while producing samples concentrated near the critical interface.
Problem
The paper addresses computation of the probability that a quantity of interest lies above or below a prescribed critical value.
Method
The method combines multilevel Monte Carlo, Interacting Particle Systems, Feynman-Kac measures, and sequential sampling focused near the critical value.
Results
The algorithm achieves more efficient convergence rates than classical Monte Carlo and multilevel Monte Carlo, comparable rates to the current best alternative, and concentrates samples near the limit-state surface.
Takeaways & Limitations
The generated samples may support later reduced-order-model applications and sensitivity computation for failure probabilities.
Takeaways & Limitations
The convergence analysis assumes the coarsest numerical approximation is sufficiently precise to enter the linear decay regime.
Abstract
from arXiv · showhide
We propose a novel method that combines a multilevel decomposition with the framework of Interacting Particle Systems to compute the probability that given quantities of interest take values above or below a certain pre-specified value. Through the application of a sequential sampling scheme, the algorithm is able to achieve convergence rates faster than those achieved by the classical Multilevel Monte Carlo algorithm, and competes with the current state of the art techniques, while also being dimension independent. Furthermore, the sample points generated by the algorithm form a sequence which concentrates near the critical value of the quantity of interest. Our results are rigorously established and later verified through numerical experiments.
1 Introduction
The paper targets failure-probability estimation in uncertainty quantification, where a system failure is represented by a QoI crossing a critical value. It proposes an interacting-particle multilevel approach that concentrates expensive sampling near this threshold.
- Failure probabilities measure the chance that a system fails or behaves undesirably, often expressed through a QoI crossing a critical value.
- The proposed method combines multilevel Monte Carlo with Interacting Particle Systems to estimate threshold-exceedance probabilities.
- Sequential sampling restricts multilevel contributions to parameter points where the QoI lies close to the critical value.
- The paper develops the method, proves asymptotic convergence properties, and evaluates it through numerical experiments.
2 General Context
The problem setting models a bounded solution map and continuous QoI over a probability space, then approximates the QoI through increasingly accurate numerical solution levels. The analysis explicitly tracks computational cost and approximation rates.
- The goal is to compute the probability that a parametrized solution u(y) belongs to an open subset of the solution space.
- The QoI is formed by composing a continuous functional g with the solution map u, while the failure indicator is defined from the resulting scalar quantity G.
- Level-dependent finite-dimensional spaces provide increasingly accurate numerical approximations to the solution map and its QoI.
- Each level has a computational cost Wℓ, with approximation quality and work governed by exponents q, r, and α.
- The QoI approximation rate may require additional assumptions, and an additional approximation of g is needed when g(uℓ(y)) cannot be computed exactly.
3 Monte Carlo Sampling
The paper reviews Monte Carlo and multilevel Monte Carlo estimators for approximated failure indicators, deriving sample-allocation and work bounds under approximation assumptions. MLMC can reduce high-level sampling when interlevel differences decay sufficiently quickly.
- Monte Carlo Sampling: Monte Carlo approximates expectations using independent identically distributed samples from the parameter distribution.
- Monte Carlo Sampling: The analysis requires an L2 error bound for the numerical failure indicator and imposes an approximation-probability decay assumption.
- Monte Carlo Sampling: The coarsest approximation must be sufficiently precise to lie in the linear decay regime used by the convergence analysis.
- Multilevel Monte Carlo Method: MLMC exploits rapidly decaying interlevel differences by using fewer samples on higher-cost levels.
- Multilevel Monte Carlo Method: For MLMC, the work bound depends on the relation between q and r, with regimes α^-2qL, L^2α^-2qL, and α^-(q+r)L.
4 Multilevel Interacting Particle System
The section develops a multilevel failure-probability approximation using conditional sampling, Feynman–Kac measures, and interacting particle systems. The resulting MLIPS method samples progressively near the QoI’s critical limit surface and has rigorously established convergence and work bounds.
- Conditional multilevel approximation: The multilevel decomposition restricts sampling to sets Aℓ where contributions may be informative, while disregarding regions where they are null.The sets are constructed so that multilevel contributions need not be sampled across the entire parameter space.
- Conditional multilevel approximation: Sampling from the conditional measures µℓ produces points approximating the limit surface {y ∈ P : G(y) = 0}.Under continuity of G, every sequence selected from the sets Aℓ has a convergent subsequence whose limit satisfies G(y) = 0.
- Interacting particle systems: Feynman–Kac prediction measures represent the conditional sampling scheme through potentials Gℓ and Markov transitions, with Gℓ chosen as 1Aℓ.The transitions are constructed to preserve both µ and µℓ and to satisfy the required accessibility condition.
- MLIPS approximation: Different numbers of samples may be used at each level, with fewer samples generated at finer levels from the preceding particle population.The approximation therefore depends on the full sequence of per-level sample counts, not only the final level.
- MLIPS approximation: The MLIPS approximation uses interacting particle systems to approximate the multilevel failure-probability estimator through conditional expectations and probabilities.Its practical computation is specified by an algorithm that generates samples across levels.
- Convergence and work: Theorem 20 establishes a choice of per-level sample numbers giving an L-independent error bound and bounds the total work of the MLIPS approximation.The supplied theorem statement does not include the explicit rates or work expression.
5 Experimental results
The experiments evaluate convergence across synthetic and applied settings, varying rates, cutoffs, error constants, and numerical discretizations. The MLIPS method generally follows its theoretical behavior, improves on MLMC in selected regimes, and generates samples near the failure interface.
- Synthetic example: For q = 2 and r = 3, MC and MLMC achieve their expected convergence rates, while MLIPS approaches its theoretical bound of 1/2.Each point represents the average squared error of 100 realizations.
- Synthetic example: 10 times smaller failure probabilities produce an upward shift in relative error for all three methods.The comparison uses experiments with different cutoff values and corresponding probabilities of interest.
- Synthetic example: For q = 2 and r = 4, all methods retain their expected theoretical convergence rates, with MLIPS showing a small additional rate deterioration.The deterioration is attributed in the cited passage to the L^4 term in the Theorem 20 estimate.
- Synthetic example: Smaller cutoff values produce higher relative errors across the convergence experiments.This trend is reported again for the q = 2 and r = 4 case.
- Synthetic example: For q = 2 and r = 5, the MLMC and MLIPS convergence-rate deterioration is stronger than in the preceding experiments.Figure 3 reports the same overall trends as the earlier synthetic cases.
- Applied example: In the parametric PDE example, both the proposed and adaptive algorithms achieve the predicted convergence rate of 0.5 with respect to total computational effort.The experiment uses eight random parameters and an L-shaped domain with mesh refinement across levels.
6 Conclusions
The paper proposes MLIPS for failure-probability computation and shows that its sequential sampling concentrates samples near the critical interface as resolution increases.
- MLIPS computes failure probabilities for PDE-based quantities of interest using a multilevel method.
- Samples accumulate around the interface G(y) = ϑ with increasing precision across levels.
- Sequential sampling evaluates multilevel contributions only where they are meaningful, improving efficiency relative to classical Monte Carlo and multilevel Monte Carlo methods.
- The method achieves convergence rates comparable to the current best alternative while generating samples near the relevant limit-state surface.
A Number of Samples per Level for the MLIPS Approximation
The MLIPS approximation allocates level-dependent sample counts and analyzes computational error and work separately across three regimes determined by q relative to 1/(2r).
- The analysis chooses different numbers of samples per level to control the MLIPS approximation's error and computational work.
- The proof distinguishes the cases q > 1/(2r), q = 1/(2r), and q < 1/(2r).
- Case q > 1/(2r): For q > 1/(2r), the final sums governing error and work are bounded independently of L.
- Case q < 1/(2r): For q < 1/(2r), the appendix separately derives bounds for the error and computational work.