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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ν</mml:mi> </mml:math> . This matching is up to a replacement of d /2 by d and a logarithmic term $$\log \frac{R}{\epsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>log</mml:mo> <mml:mfrac> <mml:mi>R</mml:mi> <mml:mi>ϵ</mml:mi> </mml:mfrac> </mml:mrow> </mml:math> , where d is the dimension of input space, R is the upper bound for the norm of the unknown black-box function, and $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> is the desired accuracy. That is to say, our lower bound is nearly optimal for these kernels.