论文标题
有效全局优化的最严重复杂性的下限
Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization
论文作者
论文摘要
有效的全球优化是一种广泛使用的方法，用于优化昂贵的黑盒功能，例如调整超参数，设计新材料等。尽管它很受欢迎，但较少的关注来分析问题的固有硬度，尽管鉴于其广泛使用，但重要的是要了解有效的有效全球优化算法的基本限制非常重要。在本文中，我们研究了有效的全局优化问题的最严重的复杂性，与现有的内核特异性结果相反，我们得出了一个统一的下限，以在其相应地重现kernel Hilbert Space（RKHS）的相应重现的ball中，以有效全局优化的复杂性。具体而言，我们表明，如果存在确定性算法，该算法在$ t $函数评估中的任何函数$ f \ in s $ in s in s in $ t $ function评估中都达到了次级优先差距，则$ t $至少是$ t $至少$ω\ weft（\ frac {\ frac {\ log \ log \ \ \ \ \ \ \ mathcal {n} s（s） 4ε,\|\cdot\|_\infty)}{\log(\frac{R}ε)}\right)$, where $\mathcal{N}(\cdot,\cdot,\cdot)$ is the covering number, $S$ is the ball centered at $0$ with radius $R$ in the RKHS and $ s（\ MATHCAL {X}）$是可行套装$ \ Mathcal {x} $的$ s $的限制。此外，我们表明，这种下限几乎与非自适应搜索算法相匹配的上限与常用的平方指数内核和Matérn内核所获得的上限相匹配，并具有较大的平滑度参数$ν$，最多可以替换为$ d/2 $ $ d/2 $ by $ d $ $ d $ and a leogarithmic term $ \ log \ log \ f \ \ \ \ \ frac =也就是说，我们的下限对于这些内核几乎是最佳的。
Efficient global optimization is a widely used method for optimizing expensive black-box functions such as tuning hyperparameter, and designing new material, etc. Despite its popularity, less attention has been paid to analyzing the inherent hardness of the problem although, given its extensive use, it is important to understand the fundamental limits of efficient global optimization algorithms. In this paper, we study the worst-case complexity of the efficient global optimization problem and, in contrast to existing kernel-specific results, we derive a unified lower bound for the complexity of efficient global optimization in terms of the metric entropy of a ball in its corresponding reproducing kernel Hilbert space~(RKHS). Specifically, we show that if there exists a deterministic algorithm that achieves suboptimality gap smaller than $ε$ for any function $f\in S$ in $T$ function evaluations, it is necessary that $T$ is at least $Ω\left(\frac{\log\mathcal{N}(S(\mathcal{X}), 4ε,\|\cdot\|_\infty)}{\log(\frac{R}ε)}\right)$, where $\mathcal{N}(\cdot,\cdot,\cdot)$ is the covering number, $S$ is the ball centered at $0$ with radius $R$ in the RKHS and $S(\mathcal{X})$ is the restriction of $S$ over the feasible set $\mathcal{X}$. 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 $ν$, up to a replacement of $d/2$ by $d$ and a logarithmic term $\log\frac{R}ε$. That is to say, our lower bound is nearly optimal for these kernels.
