A common problem encountered in many real-world applications is level set estimation where the goal is to determine the region in the function domain where the function is above or below a given threshold. When the function is black-box and expensive to evaluate, the level sets need to be found in a minimum set of function evaluations. Existing methods often assume a discrete search space with a finite set of data points for function evaluations and estimating the level sets. When applied to a continuous search space, these methods often need to first discretize the space which leads to poor results while needing high computational time. While some methods cater for the continuous setting, they still lack a proper guarantee for theoretical convergence. To address this problem, we propose a novel algorithm that does not need any discretization and can directly work in continuous search spaces. Our method suggests points by constructing an acquisition function that is defined as a measure of confidence of the function being higher or lower than the given threshold. A theoretical analysis for the convergence of the algorithm to an accurate solution is provided. On multiple synthetic and real-world datasets, our algorithm successfully outperforms state-of-the-art methods.

Black-box optimization has emerged as an effective technique in many real-world applications to find the global optimum of expensive, noisy black-box functions. Some notable applications include hyper-parameter optimization in machine learning algorithms Snoek et al. [2012], Bergstra and Bengio [2012], synthesis of short polymer fiber materials, alloy design, 3D bio-printing, and molecule design Greenhill et al. [2020], Shahriari et al. [2015], optimizing design parameters in computational fluid dynamics Morita et al. [2022], and scientific research (e.g., multilayer nanoparticle, photonic crystal topology) Kim et al. [2022]. Bayesian Optimization is a popular example of black-box optimization method. Typically, Bayesian Optimization algorithms use a probabilistic regression model, such as a Gaussian Process (GP), trained on existing function observations. This model is then utilized to create an acquisition function that balances exploration and exploitation to recommend the next evaluation point for the black-box functions. Various options exist for acquisition functions, including improvement-based methods like Probability of Improvement Kushner [1964], Expected Improvement Mockus et al. [1978], the Upper Confidence Bound Srinivas

Bayesian Optimization (BO) is an effective approach for global optimization of black-box functions when function evaluations are expensive. Most prior works use Gaussian processes to model the black-box function, however, the use of kernels in Gaussian processes leads to two problems: first, the kernel-based methods scale poorly with the number of data points and second, kernel methods are usually not effective on complex structured high dimensional data due to curse of dimensionality. Therefore, we propose a novel black-box optimization algorithm where the black-box function is modeled using a neural network. Our algorithm does not need a Bayesian neural network to estimate predictive uncertainty and is therefore computationally favorable. We analyze the theoretical behavior of our algorithm in terms of regret bound using advances in NTK theory showing its efficient convergence. We perform experiments with both synthetic and real-world optimization tasks and show that our algorithm is more sample efficient compared to existing methods.