Lower Bounds on the Noiseless Worst-Case Complexity of Efficient Global Optimization

Abstract

Efficient global optimization is a widely used method for optimizing expensive black-box functions. In this paper, we study the worst-case oracle complexity of the efficient global optimization problem. In contrast to existing kernel-specific results, we derive a unified lower bound for the oracle complexity of efficient global optimization in terms of the metric entropy of a ball in its corresponding reproducing kernel Hilbert space. Moreover, we show that this lower bound nearly matches the upper bound attained by non-adaptive search algorithms, for the commonly used squared exponential kernel and the Matérn kernel with a large smoothness parameter $\nu$. This matching is up to a replacement of d/2 by d and a logarithmic term $log\frac{R}{ϵ}$, where d is the dimension of input space, R is the upper bound for the norm of the unknown black-box function, and $ϵ$ is the desired accuracy. That is to say, our lower bound is nearly optimal for these kernels.

Keywords: Efficient global optimization; Reproducing Kernel Hilbert space; Worst-case complexity.