Epsilon-Neighborhood Decision-Boundary Governed Estimation (EDGE) of 2D Black Box Classifier Functions

1. Problem Statement

The paper addresses the challenge of accurately estimating the decision boundary ($\partial S$) of a black-box binary classifier $f(\cdot): X \to \{0, 1\}$ in a 2D domain.

• Context: In safety-critical engineering (e.g., power grid stability, design optimization), it is vital to distinguish between "desirable" states ($f(x)=1$) and "undesirable" states ($f(x)=0$).
• Constraints:
  • The system is a "black box," meaning no analytical expression of $f(x)$ is available.
  • Evaluations of $f(x)$ are computationally expensive (e.g., high-fidelity simulations).
  • Existing methods (like adaptive sampling or active learning) often lack guarantees on how close the estimated boundary is to the true boundary.
  • Existing methods often explore regions far from the boundary, leading to poor sample efficiency.
• Objective: Develop an algorithm that estimates the boundary within a user-specified $\epsilon$-neighborhood (a band of width $\epsilon$ around the true boundary) with minimal function queries and without requiring hyperparameter tuning.

2. Methodology: The EDGE Algorithm

The proposed $\epsilon$-Neighborhood Decision-Boundary Governed Estimation (EDGE) algorithm is a function-agnostic, sample-efficient method based on the Intermediate Value Theorem (IVT). It operates in two main phases:

A. Initialization via Bisection

1. Requirement: The algorithm requires at least one interior point ($x_{in} \in S_1$) and one exterior point ($x_{out} \in S_0$).
2. Bisection: If the distance between $x_{in}$ and $x_{out}$ is greater than $\epsilon$, a bisection procedure is applied along the segment connecting them.
3. Convergence: The algorithm iteratively queries the midpoint. If $f(mid)=1$, it becomes the new interior point; otherwise, it becomes the new exterior point. This continues until the distance between the last interior and exterior points is $\le \epsilon$.
4. Result: This yields the initial pair of points ($\tilde{S}^1_0, \tilde{S}^0_0$) that bracket the boundary within the $\epsilon$-neighborhood.

B. Boundary Walking ($\epsilon$-Stepping)

Once initialized, EDGE "walks" along the boundary to trace its full extent:

1. Geometric Intersection: For the current pair of points ($p_{in} \in \tilde{S}^1, p_{out} \in \tilde{S}^0$), the algorithm constructs two circles of radius $\epsilon$ centered at these points.
2. Candidate Selection: The intersection points of these two circles are calculated. One intersection point is selected as the next test point ($x_{test}$) based on a cross-product criterion to maintain a consistent traversal direction.
3. Query and Update:
   • If $f(x_{test}) = 1$, it is added to the interior set ($\tilde{S}^1$).
   • If $f(x_{test}) = 0$, it is added to the exterior set ($\tilde{S}^0$).
4. Domain Boundaries: If the test point falls outside the domain $X$, the algorithm switches to a "Domain Boundary Walk" (Algorithm 3), stepping along the domain edge $\partial X$ until it re-enters the feasible region or detects the boundary again.
5. Termination: The process repeats until the walk returns to the vicinity of the starting points, ensuring the entire boundary within the domain is spanned.

Key Features:

• 100% Sample Efficiency (Post-Initialization): Every point queried during the walking phase is guaranteed to be within the $\epsilon$-neighborhood of the true boundary.
• No Hyperparameters: Unlike Active Learning methods, EDGE requires no tuning of kernel widths or learning rates.
• Deterministic: It does not rely on random initialization, avoiding stochastic variance in results.

3. Key Contributions

1. Theoretical Guarantee: EDGE provides a rigorous mathematical guarantee that the estimated boundary lies strictly within a user-defined $\epsilon$-neighborhood of the true boundary, a feature missing in most existing adaptive sampling techniques.
2. Sample Efficiency: By leveraging the IVT and geometric stepping, EDGE minimizes the number of expensive function evaluations, avoiding the "blind" exploration of regions far from the boundary.
3. Function Agnosticism: The algorithm works on any continuous black-box function without requiring gradient information or specific model assumptions.
4. Benchmarking Framework: The authors introduce a "Naïve Grid Sampling" method as a baseline to prove that $\epsilon$-guarantees are possible, and compare EDGE against Active Learning at the Boundaries (ALB) using Support Vector Machines (SVM).

4. Experimental Results

The algorithm was evaluated on three benchmarks:

1. Case Study: An IEEE 5-bus power grid stability problem with uncertain renewable power injection (linear constraints).
2. Nonlinear Functions: Rosenbrock, Goldenstein-Price, and Beale test functions (highly nonlinear).

Performance Metrics:

• Average Surface Distance (ASD): A metric quantifying the approximation error between the estimated and true boundaries.
• Sample Count: The number of function queries required.
• Computation Time: Wall-clock time.

Findings:

• vs. Naïve Grid Search: EDGE achieved similar ASD accuracy but with orders of magnitude fewer samples. While grid search complexity scales as $O(1/\epsilon^2)$, EDGE scales linearly with the boundary length $L$ and $1/\epsilon$ ($O(L/\epsilon)$).
• vs. Active Learning (ALB/SVM):
  • Accuracy: EDGE consistently achieved lower ASD values than ALB. ALB struggled to capture complex nonlinear regions even after many iterations.
  • Efficiency: EDGE was significantly faster. ALB suffered from the $O(m^3)$ complexity of SVM kernel matrix computations and high stochasticity (variance in results due to random initialization).
  • Reliability: EDGE produced deterministic results, whereas ALB results varied significantly across 30 repetitions.

Table 1 Summary (Beale Function, $\epsilon=0.05$):

• EDGE: ASD = 0.055, Samples = 1,903, Time = 0.13s.
• ALB: ASD = 0.374 (avg), Samples = 1,903 (budget limited), Time = 764.52s (avg).
• Grid: ASD = 0.054, Samples = 67,721, Time = 7.88s.

5. Significance and Future Work

• Significance: EDGE solves a critical gap in safety-critical system design by providing a guaranteed error bound ($\epsilon$) while drastically reducing computational costs. This is particularly valuable for physical experiments or high-fidelity simulations where every query is expensive.
• Future Directions:
  • Extending the framework from binary classification to multiclass problems.
  • Adapting the algorithm for high-dimensional spaces (currently limited to 2D due to the circle-intersection logic).
  • Applying EDGE to systems with noise, using $\epsilon$ to define a soft transition zone.
  • Using EDGE-generated boundary points as support vectors to train more robust SVMs with reduced stochasticity.

In conclusion, the paper presents EDGE as a superior alternative to current state-of-the-art boundary estimation methods, offering a unique combination of theoretical guarantees, deterministic performance, and extreme sample efficiency.