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

Wenjie Xu, Yuning Jiang, Emilio Tanowe Maddalena, Colin N. JonesarXiv 2022 · DOI · arXiv

Abstract

This paper establishes a fundamental "speed limit" for black-box optimization by linking the complexity of a function space to the number of samples required to find a global minimum. Using metric entropy, the authors derive a unified theoretical framework for establishing lower bounds on sample complexity in noiseless, worst-case scenarios. Their results demonstrate that for common kernels like Squared Exponential and Matérn, existing non-adaptive algorithms are nearly optimal.

Introduction

Efficient Global Optimization (EGO) is a critical methodology for "expensive" black-box optimization problems, such as hyperparameter tuning for deep neural networks or chemical compound design. In these scenarios, evaluating the objective function is costly, necessitating a strategy that finds the global minimum with minimal samples. While various algorithms like Bayesian Optimization with Expected Improvement (EI) are widely used, the fundamental theoretical limits—specifically the minimum number of samples required—have remained partially understood and often kernel-specific.

This research addresses this gap by providing a unified framework for EGO complexity. The authors establish a formula that quantifies the difficulty of an optimization problem based on the inherent complexity of the function space, specifically focusing on the non-Bayesian, noiseless setting where the function resides in a Reproducing Kernel Hilbert Space (RKHS) with a bounded norm.

Methodology

The researchers employed several mathematical strategies to derive these lower bounds:

  1. Metric Entropy: They utilized "covering numbers" ($\mathcal{N}$)—a measure of the number of small balls required to cover a set of functions—to quantify the richness of the RKHS.
  2. Subspace Decomposition: The RKHS was partitioned into two orthogonal components: one explored by the algorithm and one remaining "hidden."
  3. Adversarial Construction: The authors proved that for any deterministic algorithm, an "adversarial" function can be constructed that evaluates to zero at all sampled points but contains a deep minimum elsewhere, forcing a minimum number of steps to guarantee convergence.

Key Results

The core contribution is a general lower bound formula relating the number of evaluations $T$ to the covering number of the function space:

$$T = \Omega\left(\frac{\log \mathcal{N}(S(\mathcal{X}), 4\epsilon, \|\cdot\|_\infty)}{\log(R/\epsilon)}\right)$$

This unified bound allows for the derivation of specific limits for common kernels. For the Squared Exponential (SE) kernel, the authors established a lower bound of $T = \Omega((\log \frac{R}{\epsilon})^{d/2-1})$, the first such bound for the noiseless setting. For Matérn kernels with high smoothness ($\nu \ge d/2$), the lower bound closely matches existing upper bounds, differing only by a logarithmic factor and a slight shift in the exponent.

Comparison of lower bounds for sample complexity across different kernels and noise settings.

The table above summarizes how these new results fill gaps in the existing literature, particularly for noiseless SE and general kernels. Experimental validation in 1D and 3D settings confirmed that while popular algorithms like Lower Confidence Bound (LCB) and EI perform well on average, they struggle against the adversarial functions predicted by this theory, highlighting the reality of worst-case complexity bottlenecks.

Discussion and Future Work

A significant insight from this work is the "noiseless gap." In noisy settings, complexity is typically dominated by statistical noise ($1/\epsilon^2$). In the noiseless case, this term vanishes, and complexity is driven entirely by the geometry and smoothness of the kernel.

While these results provide a rigorous foundation for deterministic algorithms, several avenues for future research remain:

  • Randomized Algorithms: Extending the current proofs to include randomized optimization strategies.
  • Matérn Gap: Addressing the remaining gap between lower and upper bounds when the Matérn smoothness parameter $\nu$ is small relative to dimension $d$.
  • Average-Case Analysis: Moving beyond worst-case scenarios to characterize the "average" complexity, which often better reflects practical performance.

Summary updated

Abstract

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.
BibTeX
@misc{xu2022lower,
  author = {Wenjie Xu and Yuning Jiang and Emilio Tanowe Maddalena and Colin N. Jones},
  title = {{Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization}},
  year = {2022},
  eprint = {2209.09655},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.09655},
}
Figure