  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.
