Adaptive Reduced Multilevel Splitting

This paper considers the classical problem of sampling with Monte Carlo methods a target probability distribution obtained by conditioning on a rare event defined by the level set of a real-valued score function that is very expensive to compute. We also consider a context where, with each new evaluation of the true score function, a method that iteratively builds a sequence of reduced scores is available; these reduced scores being moreover certified with pointwise error bounds. This work proposes a fully adaptive algorithm that iteratively: i) builds a sequence of proposal distributions obtained by conditioning on the reduced score above an adaptively well-chosen level, and ii) draws from the latter both for importance sampling of the true target rare events, as well as for proposing relevant (expensive) updates to the reduced score. An essential contribution consists in the adaptive choice of the level in i) and ii). The latter is calculated solely from the reduced score and its error bound, and is interpreted as the first non-achievable level as quantified by a given cost (in a pessimistic scenario) of importance sampling of the associated true target distribution. From a practical point of view, sampling the proposal sequence is performed by extending the framework of the popular Adaptive Multilevel Splitting (AMS) algorithm to the use of score function reduction. Numerical experiments evaluate the proposed importance sampling algorithm in terms of computational complexity versus squared error. In particular, we investigate the performance of the algorithm when simulating rare events related to the solution of a parametric PDE approximated by a reduced basis.