Convergence rates of efficient global optimization algorithms

Abstract

Efficient global optimization is the problem of minimizing an unknown function f, using as few evaluations f(x) as possible. It can be considered as a continuum-armed bandit problem, with noiseless data and simple regret. Expected improvement is perhaps the most popular method for solving this problem; the algorithm performs well in experiments, but little is known about its theoretical properties. Implementing expected improvement requires a choice of Gaussian process prior, which determines an associated space of functions, its reproducing-kernel Hilbert space (RKHS). When the prior is fixed, expected improvement is known to converge on the minimum of any function in the RKHS. We begin by providing convergence rates for this procedure. The rates are optimal for functions of low smoothness, and we modify the algorithm to attain optimal rates for smoother functions. For practitioners, however, these results are somewhat misleading. Priors are typically not held fixed, but depend on parameters estimated from the data. For standard estimators, we show this procedure may never discover the minimum of f. We then propose alternative estimators, chosen to minimize the constants in the rate of convergence, and show these estimators retain the convergence rates of a fixed prior.

References in corpus (2)

• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Reproducing kernel Hilbert spaces of Gaussian priors

Cited by in corpus (23)

• Safe Controller Optimization for Quadrotors with Gaussian Processes
• Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation
• The Automatic Neuroscientist: automated experimental design with real-time fMRI
• Confidence Intervals for Projections of Partially Identified Parameters
• Bayesian optimization with improved scalability and derivative information for efficient design of nanophotonic structures
• Cross-validation based adaptive sampling for Gaussian process models
• Machine Learning based optimization for interval uncertainty propagation
• Extending Expected Improvement for High-dimensional Stochastic Optimization of Expensive Black-Box Functions
• Finding safe 3D robot grasps through efficient haptic exploration with unscented Bayesian optimization and collision penalty
• Examples of inconsistency in optimization by expected improvement
• Co-Learning Bayesian Optimization
• BOATS: Bayesian Optimization for Active Control of ThermoacousticS
• Recognition of food-texture attributes using an in-ear microphone
• Bayesian Optimization of 2D Echocardiography Segmentation
• Univariate interpolation by exponential functions and gaussian RBFs for generic sets of nodes
• On the development of a practical Bayesian optimisation algorithm for expensive experiments and simulations with changing environmental conditions
• Regional medical inter-institutional cooperation in medical provider network constructed using patient claims data from Japan
• Directed Evolution of Proteins via Bayesian Optimization in Embedding Space
• MBORE: Multi-objective Bayesian Optimisation by Density-Ratio Estimation
• Relaxed Gaussian process interpolation: a goal-oriented approach to Bayesian optimization
• Self-Avoiding Random Dynamics on Integer Complex Systems
• One-parameter family of acquisition functions for efficient global optimization
• Global Optimisation of Black-Box Functions with Generative Models in the Wasserstein Space