Multiscale Gaussian Process Level Set Estimation
This work addresses the challenge of efficient level set estimation in high-dimensional spaces for applications like optimization and uncertainty quantification, representing an incremental improvement over prior Bayesian methods.
The paper tackles the problem of estimating the level set of a black-box function from noisy and expensive evaluations by proposing a new algorithm using a Gaussian Process prior with a hierarchical partition strategy. It results in significantly lower computational cost for higher-dimensional spaces and provides better high-probability bounds on the discrepancy between estimated and true level sets compared to existing methods.
In this paper, the problem of estimating the level set of a black-box function from noisy and expensive evaluation queries is considered. A new algorithm for this problem in the Bayesian framework with a Gaussian Process (GP) prior is proposed. The proposed algorithm employs a hierarchical sequence of partitions to explore different regions of the search space at varying levels of detail depending upon their proximity to the level set boundary. It is shown that this approach results in the algorithm having a low complexity implementation whose computational cost is significantly smaller than the existing algorithms for higher dimensional search space $\X$. Furthermore, high probability bounds on a measure of discrepancy between the estimated level set and the true level set for the the proposed algorithm are obtained, which are shown to be strictly better than the existing guarantees for a large class of GPs. In the process, a tighter characterization of the information gain of the proposed algorithm is obtained which takes into account the structured nature of the evaluation points. This approach improves upon the existing technique of bounding the information gain with maximum information gain.