Technical Summary: An (ϵ, δ)-accurate level set estimation with a stopping criterion

Problem Statement

Level Set Estimation (LSE) aims to identify regions within a candidate set where an unknown, costly-to-evaluate function $f(x)$ exceeds (or falls below) a specified threshold $\theta$. While active learning strategies have been proposed to minimize the number of function evaluations required, a significant gap remains in the theoretical formulation of stopping criteria.

Existing methods often rely on sequential optimization to find $\epsilon$-accurate solutions (allowing a margin around the threshold) but lack rigorous stopping rules. Common approaches include:

• Budget-based stopping: Halting after a fixed number of experiments, which may lead to wasted resources or insufficient accuracy.
• F-score sampling (FS): Stopping when a sampled percentile of F-scores exceeds a target. However, this requires knowing the maximum achievable F-score a priori, which is often unclear. Furthermore, the actual F-score at the stopping point may not meet the desired target, and the method relies on computationally expensive sampling.
• Fully Classified (FC) criteria: Stopping only when all points are classified. This often fails to terminate in the presence of noise, as points near the threshold remain "undetermined" indefinitely.

The paper addresses the need for an acquisition strategy that incorporates a theoretically grounded stopping criterion to ensure the algorithm halts when further exploration is unlikely to yield improvements, thereby reducing unnecessary evaluations while providing probabilistic guarantees on accuracy.

Methodology

1. Gaussian Process Framework

The method models the unknown function using Gaussian Process Regression (GPR). Given a dataset $S_N$, the posterior distribution of the function value at a new point $x^*$ is Gaussian, $N(\mu_N(x^*), \sigma_N^2(x^*))$.

2. Proposed Acquisition Function

Traditional acquisition functions based on misclassification probability ($p_{min}(x)$) select points where the posterior variance is high or the mean is close to the threshold. The authors argue that this can lead to redundant exploration of points where the true function value is inherently close to the threshold (the "margin region"), offering diminishing returns.

To address this, the paper introduces a margin $\epsilon > 0$. A point $x$ is considered "difficult to classify" not just if $f(x) \approx \theta$, but if $f(x) \in (\theta - \epsilon/2, \theta + \epsilon/2]$. The goal is to achieve $\epsilon$-accuracy, where the estimated sets $\tilde{H}_\theta$ (upper), $\tilde{L}_\theta$ (lower), and $\tilde{U}_\theta$ (undetermined/margin) satisfy specific inclusion properties with respect to the true sets.

The proposed acquisition function, $r_{min}(x)$, is defined as:
$$r_{min}(x) = \min \{ \Pr(x \in H_\theta), \Pr(x \in L_\theta), \Pr(x \notin U_\theta) \}$$
where:

• $\Pr(x \in H_\theta)$ and $\Pr(x \in L_\theta)$ are the probabilities of belonging to the upper and lower level sets.
• $\Pr(x \notin U_\theta)$ is the probability that the function value lies outside the margin region $U_\theta = \{x \mid |f(x) - \theta| \le \epsilon/2\}$.

The algorithm selects the next point $x_{new} = \arg \max_{x \in X} r_{min}(x)$. This function prioritizes points that are either difficult to classify (low probability of being in $H_\theta$ or $L_\theta$) OR points where the uncertainty about being in the margin region is high. Crucially, if a point is thoroughly explored and the posterior variance decreases, the probability that it falls within the margin ($\Pr(x \in U_\theta)$) increases, causing $\Pr(x \notin U_\theta)$ to decrease. This naturally reduces the acquisition value for points that are already "solved" within the $\epsilon$ tolerance, preventing infinite loops.

3. Stopping Criterion

The algorithm stops when the following inequality is satisfied for a confidence parameter $\delta \in (0, 1)$:
$$1 - \sum_{x \in X} r_{min}(x) \ge \delta$$
This condition ensures that the sum of the "uncertainty" (acquisition values) across all candidate points is sufficiently low.

4. Theoretical Guarantees

The paper proves Theorem 3.1: If the classification rule assigns points to $\tilde{H}_\theta$, $\tilde{L}_\theta$, or $\tilde{U}_\theta$ based on maximizing the respective probabilities, then upon satisfying the stopping criterion, the triplet $(\tilde{H}_\theta, \tilde{L}_\theta, \tilde{U}_\theta)$ is $\epsilon$-accurate with a probability of at least $\delta$.

Furthermore, Proposition 3.2 establishes that this theoretical guarantee extends to performance metrics. Specifically, the F-score, accuracy, recall, precision, and specificity are guaranteed to be above certain lower bounds with probability $1 - \sum r_{min}(x)$. Unlike previous methods (e.g., Qing et al., 2022b) that estimate F-score bounds via sampling, this method provides analytical lower bounds.

5. Parameter Selection

• $\delta$ (Confidence): Set close to 1 (e.g., 0.99). The stopping time is shown to be insensitive to small variations in $\delta$ near 1.
• $\epsilon$ (Margin): Instead of setting $\epsilon$ directly (which depends on function range and noise), the paper proposes an adaptive method based on a parameter $L$ (representing a minimum number of effective observations). $\epsilon$ is derived from the posterior variance $\sigma_N(x)$ and $L$, making it robust to noise variance and function scale.

Key Contributions

1. Novel Acquisition Function: An acquisition function based on the distribution of classification difficulty that explicitly accounts for the margin region, preventing redundant exploration of points where the true value is close to the threshold.
2. Theoretical Stopping Criterion: A stopping rule that guarantees $(\epsilon, \delta)$-accuracy. The algorithm halts when the probability of the solution being $\epsilon$-accurate exceeds $1-\delta$.
3. Performance Metric Guarantees: Theoretical proofs providing lower bounds for F-score, accuracy, recall, precision, and specificity, which are analytically computable without sampling.
4. Computational Efficiency: The stopping criterion relies on the cumulative distribution function (CDF) of the standard normal distribution, resulting in linear computational complexity with respect to the number of candidate points. This contrasts with F-score sampling methods that require quadratic complexity due to Monte Carlo sampling.

Experimental Results

The method was evaluated on synthetic test functions (Rosenbrock, Branin, Cross in tray) and a real-world application involving the estimation of "red zones" (impurity regions) in silicon ingots for solar cells.

• Performance: The proposed method achieved F-scores comparable to existing state-of-the-art acquisition functions (Straddle, MILE, RMILE, MELK, Uncertainty Sampling).
• Stopping Efficiency:
  • Fully Classified (FC): Failed to stop in noisy environments for most methods, as points near the threshold remained undetermined.
  • F-score Sampling (FS): Often stopped prematurely before F-scores converged, or required fine-tuning of the target F-score which is difficult to determine in practice. In some cases, the actual F-score at the stopping point was below the desired threshold.
  • Proposed Method: Successfully stopped the algorithm once sufficient estimation accuracy was achieved, regardless of the final converged F-score value. It demonstrated robustness across different noise levels and function shapes without requiring problem-specific tuning of the stopping threshold.
• Real-world Application: In the silicon ingot experiment, the proposed method effectively terminated the LSE process early while maintaining high F-scores, whereas the FC criterion continued until the full budget was exhausted.

Significance and Claims

The paper claims to address a critical gap in Level Set Estimation: the lack of effective, theoretically grounded stopping criteria. By integrating the stopping condition directly into the acquisition strategy via the concept of $\epsilon$-accuracy, the method ensures that the algorithm terminates when further exploration is unlikely to improve the classification within the specified tolerance.

The authors emphasize that their approach provides probabilistic guarantees on both the accuracy of the level set estimation and the lower bounds of standard performance metrics. This contrasts with existing heuristic or sampling-based stopping rules that lack such theoretical backing. The method is presented as a practical solution for adaptive experimental design where cost and time are constrained, allowing researchers to stop experiments with confidence that the results meet a predefined accuracy standard. The paper modestly notes that while the method is conservative (which can be beneficial for safety-critical applications), balancing these theoretical guarantees with more aggressive stopping remains an open area for future work.