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:
- 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.
- Subspace Decomposition: The RKHS was partitioned into two orthogonal components: one explored by the algorithm and one remaining "hidden."
- 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.
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