Abstract
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 $\mathcal{X}$. Furthermore, high probability bounds on a measure of discrepancy between the estimated level set and the true level set for 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.
Introduction
Level set estimation (LSE) is the task of identifying all points $x$ in a search space where an unknown function $f(x)$ exceeds a specific threshold $\tau$. This problem is fundamental to numerous real-world applications, such as environmental monitoring (e.g., mapping radiation hotspots) and medical imaging. In these scenarios, the function $f$ is typically a "black box," meaning it can only be explored through noisy and often expensive evaluations.
While Gaussian Processes (GPs) provide a robust Bayesian framework for modeling such functions, existing GP-based LSE algorithms face two significant hurdles. First, they often suffer from a "computational wall," where the cost of optimizing over a dense grid or discrete set scales exponentially with the number of dimensions ($D$). Second, the theoretical guarantees for these algorithms frequently rely on "maximum information gain" ($\gamma_n$), a metric that often overestimates uncertainty for common kernel types, leading to pessimistic convergence predictions.
Methodology: Hierarchical Partitioning
To address these challenges, this research introduces a multiscale algorithm that treats the search space as a tree of partitions rather than a flat grid. This hierarchical approach allows the algorithm to focus its computational budget on regions near the level set boundary while ignoring areas clearly above or below the threshold.
Key Algorithmic Features
- Adaptive Refinement: The algorithm maintains an "active set" of cells. For each cell, it calculates upper and lower bounds on the function value. If the uncertainty from observation noise is smaller than the estimated variation within the cell, the algorithm "refines" the cell by splitting it into smaller pieces. Otherwise, it continues to sample points within the current cell.
- Multiscale Selection: Candidate points are selected based on their deviation from the threshold $\tau$. This strategy balances exploration (sampling high-variance areas) and exploitation (sampling near the boundary).
- Low-Complexity Implementation: A modified version of the algorithm ensures that the computational cost grows only linearly with the dimension $D$. This is achieved by replacing global grid searches with a tree-based search, effectively bypassing the curse of dimensionality for the selection step.
Theoretical Insights
A core contribution of this work is the recognition that the structured, hierarchical nature of the sampling process allows for a more precise analysis of information gain. Traditional bounds assume evaluation points could be distributed arbitrarily; by accounting for the algorithm's specific structure, the authors derived a tighter characterization of information gain ($I \approx O(n^a)$) specifically for Matern kernels.
This "zooming" behavior—where the algorithm increases resolution only where necessary—allows it to achieve high precision at the boundary without wasting resources on the function's interior or exterior.
Key Results and Performance
The proposed multiscale approach yields significant improvements in both theoretical guarantees and practical efficiency:
- Tighter Error Bounds: For Matern kernels with smoothness $\nu > 1$, the high-probability bounds on the discrepancy between the estimated and true level sets are strictly better than the previous state-of-the-art.
- Computational Efficiency: The low-complexity variant of the algorithm operates in $O(n^4 + Dn)$ time. This represents a massive improvement over standard algorithms, which often require $O(n^{2D+3})$—a cost that becomes prohibitive even for moderate values of $D$.
- Information Gain: The new bound for information gain is shown to be tighter than the standard $\gamma_n$ bounds used in the literature since 2012, providing a more realistic prediction of how quickly the algorithm learns.
Limitations and Future Work
While the algorithm offers a significant leap forward, some limitations remain. The "full" version of the algorithm can still reach $O(n^{\alpha\tilde{D}+3})$ complexity in the worst case, where $\tilde{D}$ is the near-boundary dimension. Additionally, the current framework requires prior knowledge of GP parameters, such as the kernel and noise variance.
Future research directions include extending these multiscale techniques to non-Bayesian settings (e.g., functions following Hӧlder continuity) and developing "parameter-free" versions of the algorithm that can automatically adapt to unknown smoothness parameters without user intervention.
Summary updated