A Computationally Efficient Approach to Black-box Optimization using Gaussian Process Models

We consider sequential optimization of an unknown function under Gaussian process models. We develop a computationally efficient algorithm that reduces the complexity of the prevailing GP-UCB family of algorithms by a factor of $O(T^{2d-1})$ (where $T$ is the time horizon and $d$ the dimension of the function domain). The algorithm is also shown to have order-optimal regret performance (up to a poly-logarithmic factor). The basic structure of the proposed algorithm is a tree-based \emph{localized} search strategy guided by a localized optimization procedure for finding function values exceeding an iteratively updated threshold. More specifically, the global optimum is approached through a sequence of localized searches in the domain of the function guided by an iterative search in the range of the function.