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

arXiv: https://arxiv.org/abs/2209.09655 · HTML: https://mlsanity.com/paper/2209.09655/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 20 Sep 2022.

## Builds on (most cited first, 12 of 12)

- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Deterministic error bounds for kernel-based learning techniques under bounded noise](https://mlsanity.com/paper/2008.04005/) (2020)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)
- [Goal-Driven Dynamics Learning via Bayesian Optimization](https://mlsanity.com/paper/1703.09260/) (2017)
- [VABO: Violation-Aware Bayesian Optimization for Closed-Loop Control Performance Optimization with Unmodeled Constraints](https://mlsanity.com/paper/2110.07479/) (2021)

## Built on by (most cited first, 7 of 7)

- [Principled Preferential Bayesian Optimization](https://mlsanity.com/paper/2402.05367/) (2024)
- [Adaptive Feature-based Low-Rank Compression of Large Language Models via Bayesian Optimization](https://mlsanity.com/paper/2405.10616/) (2024)
- [Violation-Aware Contextual Bayesian Optimization for Controller Performance Optimization with Unmodeled Constraints](https://mlsanity.com/paper/2301.12099/) (2023)
- [CONFIG: Constrained Efficient Global Optimization for Closed-Loop Control System Optimization with Unmodeled Constraints](https://mlsanity.com/paper/2211.11822/) (2022)
- [Primal-Dual Contextual Bayesian Optimization for Control System Online Optimization with Time-Average Constraints](https://mlsanity.com/paper/2304.06104/) (2023)
- [Data-driven adaptive building thermal controller tuning with constraints: A primal-dual contextual Bayesian optimization approach](https://mlsanity.com/paper/2310.00758/) (2023)
- [Bayesian Optimization of Expensive Nested Grey-Box Functions](https://mlsanity.com/paper/2306.05150/) (2023)

## Abstract (arXiv)

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∈ S in T function evaluations, it is necessary that T is at least Omegaleft(fraclogN(S(X), 4ε,|·|_∞)log(fracRε)right), where N(·,·,·) is the covering number, S is the ball centered at 0 with radius R in the RKHS and S(X) is the restriction of S over the feasible set 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'ern kernel with a large smoothness parameter nu, up to a replacement of d/2 by d and a logarithmic term logfracRε. That is to say, our lower bound is nearly optimal for these kernels.