Convergence Rates of Efficient Global Optimization Algorithms

By Adam D. Bull. 2011

719 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Scalable Bayesian Optimization Using Deep Neural Networks (2015, background): “Recent innovation has resulted in signiﬁcant progress in Bayesian optimization, including elegant theoretical results (Srinivas et al., 2010; Bull, 2011; de Fre-itas et al., 2012), multitask and transfer optimization (Krause & Ong, 2011; Swersky et al., 2013; Bar-denet et al., 2013) and the…”
Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “These improvement strategies have been empirically studied in the literature [82], [81], [27] and recently convergence rates have been proven for EI [32].”
On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “Moreover, if the decay is geometric as r i , then we get d ( λ ) 6 log( R 2 /λ ) , and thus n > (log m ) 2 , which is even more signiﬁcant.”
Freeze-Thaw Bayesian Optimization (2014, background): “Recent work has developed compelling theoretical convergence guarantees [6, 7, 8], more rigorous methodologies [9, 10] and methods tailored to speciﬁc applications such as hyperparameter optimization [11, 4, 3] and sensor set selection [12].”
Automatic Discovery of Privacy–Utility Pareto Fronts (2019, neutral): “, [9]).”
FixNorm: Dissecting Weight Decay for Training Deep Neural Networks (2021, background): “Random search(Bull, 2011) is a popular alternative that select hyperparameter combinations randomly, which can be more efficient when the resource is constrained.”
Modeling an augmented Lagrangian for improved blackbox constrained optimization (2014, background): “They ignore potential feedback loops between surface ﬁts, predictive distributions, improvement calculations, and search (see, e.g., Bull, 2011); in practice, these can pathologically slow convergence and/or lead to local rather than global solutions.”
Bayesian Multi-Scale Optimistic Optimization (2014, background): “It is also interesting to note that the same type of bound on the standard deviation was used by Bull (2011), who achieved similar convergence rates to the ones in this paper. de Freitas et al. (2012) showed that if the samples form a δ -cover on a subset of D ⊆ X , then the standard deviation of…”
Optimization as Estimation with Gaussian Processes in Bandit Settings (2015, background): “The GP-EI strategy [22] selects the point maximizing the expected improvement over a pre-specified thresholdθt [22].”
Self-Avoiding Random Dynamics on Integer Complex Systems (2011, background): “This is a standard acquisition function for which asymptotic rates of convergence have been proved [Bull 2011].”
Bayesian Optimization for Categorical and Category-Specific Continuous Inputs (2019, neutral): “A notable strength of BO is that its convergence is well studied (Bull 2011).”
Adaptive MCMC with Bayesian Optimization (2012, background): “This is a standard acquisition function for which asymptotic rates of convergence have been proved (Bull, 2011).”
BayesOpt: a Bayesian optimization library for nonlinear optimization, experimental design and bandits (2014, background): “We found evidence that updating θ every iteration might be unnecessary or even counterproductive (Bull, 2011).”
Bayesian Optimization with Unknown Constraints (2014, background): “One such choice is the Expected Improvement (EI) criterion (Mockus et al., 1978), an acquisition function shown to have strong theoretical guarantees (Bull, 2011) and empirical eﬀectiveness (e.g., Snoek et al., 2012).”