Convergence properties of the expected improvement algorithm with fixed mean and covariance functions

By Emmanuel Vazquez, Julien Bect. 2007

252 citations recorded by the source corpus.

This paper deals with the convergence of the expected improvement algorithm, a popular global optimization algorithm based on a Gaussian process model of the function to be optimized. The first result is that under some mild hypotheses on the covariance function k of the Gaussian process, the expected improvement algorithm produces a dense sequence of evaluation points in the search domain, when the function to be optimized is in the reproducing kernel Hilbert space generated by k. The second result states that the density property also holds for P-almost all continuous functions, where P is the (prior) probability distribution induced by the Gaussian process.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Surrogate-based methods for black-box optimization (2017, methodology): “Under mild assumptions, the iterates from EGO are dense [55], so it can be used to ﬁnd a global optimum.”
Bayesian Multi-Scale Optimistic Optimization (2014, background): “…theoretical concerns about the behaviour of BO algorithms because the typical theoretical convergence guarantees are only valid on the assumption that the optimum of the acquisition function can be found exactly; see for example Srinivas et al. (2010); Vazquez & Bect (2010) and Bull (2011).”
Convergence Rates of Efficient Global Optimization Algorithms (2011, background): “Vazquez and Bect (2010) show that when π is a ﬁxed Gaussian process prior of ﬁnite smoothness, expected improvement converges on the minimum of any f ∈ H , and almost surely for f drawn from π .”
Gaussian Processes for history-matching: application to an unconventional gas reservoir (2017, methodology): “ties of GP-based optimization methods [112], which can prove that, given enough samples, it will cover the search space uniformly by finding all global and local optima.”
Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations (2012, methodology): “This problem was also studied by (Vazquez & Bect, 2010) and (Bull, 2011), but using the Expected Improvement surrogate instead of UCB.”
Bayesian Optimization in a Billion Dimensions via Random Embeddings (2013, unknown): “|D t ) (Moˇckus, 1982; Vazquez & Bect, 2010; Bull, 2011).”