An Adaptive Sampling Algorithm for Level-set Approximation

We propose a new numerical scheme for approximating level-sets of Lipschitz multivariate functions which is robust to stochastic noise. The algorithm's main feature is an adaptive grid-based stochastic approximation strategy which automatically refines the approximation over regions close to the level set. This strategy combines a local function approximation method with a noise reduction scheme and produces ε-accurate approximations with an expected cost complexity reduction of ε−(p+1/αp ) compared to a non-adaptive scheme, where α is the convergence rate of the function approximation method and we assume that the noise can be controlled in L^p. We provide numerical experiments in support of our theoretical findings. These include 2- and 3-dimensional functions with a complex level set structure, as well as a failure region estimation problem described by a hyperelasticity partial differential equation with random field coefficients.