  Bayesian optimization (BO), which uses a Gaussian process (GP) as a surrogate
to model its objective function, is popular for black-box optimization.
However, due to the limitations of GPs, BO underperforms in some problems such
as those with categorical, high-dimensional or image inputs. To this end,
recent works have used the highly expressive neural networks (NNs) as the
surrogate model and derived theoretical guarantees using the theory of neural
tangent kernel (NTK). However, these works suffer from the limitations of the
requirement to invert an extremely large parameter matrix and the restriction
to the sequential (rather than batch) setting. To overcome these limitations,
we introduce two algorithms based on the Thompson sampling (TS) policy named
Sample-Then-Optimize Batch Neural TS (STO-BNTS) and STO-BNTS-Linear. To choose
an input query, we only need to train an NN (resp. a linear model) and then
choose the query by maximizing the trained NN (resp. linear model), which is
equivalently sampled from the GP posterior with the NTK as the kernel function.
As a result, our algorithms sidestep the need to invert the large parameter
matrix yet still preserve the validity of the TS policy. Next, we derive regret
upper bounds for our algorithms with batch evaluations, and use insights from
batch BO and NTK to show that they are asymptotically no-regret under certain
conditions. Finally, we verify their empirical effectiveness using practical
AutoML and reinforcement learning experiments.
