An informational approach to the global optimization of expensive-to-evaluate functions

By Julien Villemonteix, Emmanuel Vazquez, Éric Walter. 2006

359 citations recorded by the source corpus.

In many global optimization problems motivated by engineering applications, the number of function evaluations is severely limited by time or cost. To ensure that each evaluation contributes to the localization of good candidates for the role of global minimizer, a sequential choice of evaluation points is usually carried out. In particular, when Kriging is used to interpolate past evaluations, the uncertainty associated with the lack of information on the function can be expressed and used to compute a number of criteria accounting for the interest of an additional evaluation at any given point. This paper introduces minimizers entropy as a new Kriging-based criterion for the sequential choice of points at which the function should be evaluated. Based on stepwise uncertainty reduction, it accounts for the informational gain on the minimizer expected from a new evaluation. The criterion is approximated using conditional simulations of the Gaussian process model behind Kriging, and then inserted into an algorithm similar in spirit to the Efficient Global Optimization (EGO) algorithm. An empirical comparison is carried out between our criterion and expected improvement, one of the reference criteria in the literature. Experimental results indicate major evaluation savings over EGO. Finally, the method, which we call IAGO (for Informational Approach to Global Optimization), is extended to robust optimization problems, where both the factors to be tuned and the function evaluations are corrupted by noise.

Subfields: Computational Theory and Mathematics, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

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

In Computational Theory and Mathematics

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “x by selecting the point that is expected to cause the largest reduction in entropy of the distribution p?ðx j DnÞ [67], [69], [155].”
Learning to Learn for Global Optimization of Black Box Functions (2016, background): “…variety of strategies, including Thompson sampling [Thompson, 1933, Scott, 2010, Chapelle and Li, 2011, Agrawal and Goyal, 2013], information gain [Villemonteix et al., 2009, Hennig and Schuler, 2012, Russo and Van Roy, 2014, Shahriari et al., 2014, Hern ´ andez-Lobato et al., 2015], probability…”
Entropy Search for Information-Efficient Global Optimization (2011, methodology): “[Note added in proof: It has been pointed out to us that a related approach, using sampling, was previously studied by Villemonteix et al. (2009).]”
Predictive Entropy Search for Efficient Global Optimization of Black-box Functions (2014, methodology): “We can then maximize this function to obtain x ( i ) = arg max x ∈X f ( i ) ( x ) , which is approximately distributed according to p ( x (cid:63)”
FLASH: Fast Bayesian Optimization for Data Analytic Pipelines (2016, methodology): “e acquisition function is chosen to be relatively cheap to evaluate, so that the most promising next input for querying can be found quickly. Various forms of acquisition functions have been proposed [43,20,45,21]. One of the most prominent acquisition function is the Expected Improvement (EI) funct”
Bayesian Optimization of Text Representations (2015, background): “Other options for the acquisition function include maximum probability of improvement (Jones, 2001), minimum conditional entropy (Villemonteix et al., 2006), Gaussian process upper conﬁdence bound (Srinivas et al., 2010), or a combination of them (Hoffman et al., 2011).”
Kriging is well-suited to parallelize optimization (2010, neutral): “The current Chapter is devoted to the optimization of black-box functions using a kriging metamodel [14, 22, 49, 51].”
Collaborative hyperparameter tuning (2013, background): “…(EI; Jones, 2001) is the most common such criterion, but others also include the probability of improvement of (Jones, 2001), minimizing the conditional entropy of the minimizer (Villemonteix et al., 2006), or, more recently, a criterion based on multi-armed bandits (Srinivas et al., 2010).”
An Entropy Search Portfolio for Bayesian Optimization (2014, methodology): “More recently a wide variety of more advanced techniques have been proposed which include Bayesian upper conﬁdence bounds [28, 8, 33] and information-theoretic approaches [31, 11].”
Surrogating the surrogate: accelerating Gaussian-process-based global optimization with a mixture cross-entropy algorithm (2010, methodology): “This is a major draw-back of these methods especially when the evaluation involves Monte Carlo sampling from the GP (Villemonteix et al., 2006), so these methods are used mostly to optimize “expensive-Surrogating to-evaluate” functions when the computational time to evaluate the functions justiﬁes…”
Learning hyperparameter optimization initializations (2015, background): “Further acquisition functions are the probability of improvement [7], the conditional entropy of the minimizer [19] or a multi-armed bandit based criterion [20].”
Multi-Information Source Optimization (2016, background): “Their acquisition criterion is a cost-sensitive formulation of Entropy Search [Hennig and Schuler, 2012, Villemonteix et al., 2009]: here one samples in each iteration a point that yields a maximum reduction in the uncertainty over the location of the optimum.”
Algorithms for Hyper-Parameter Optimization (2011, methodology): “Other criteria have been suggested, such as Probability of Improvement and Expected Improvement [10], minimizing the Conditional Entropy of the Minimizer [11], and the bandit-based criterion described in [12].”
Critical Hyper-Parameters: No Random, No Cry (2017, methodology): “Published methods for hyper-parameters search include evolution strategies [2], Gaussian processes [10, 23], pattern search [4], grid sampling and random sampling [1].”
Efficient Transfer Learning Method for Automatic Hyperparameter Tuning (2014, methodology): “For the evaluation criterion of SMBO, we can use: Expected Improvement (EI) (Jones, 2001), maximum probability of improvement (Jones, 2001), minimum conditional entropy (Villemonteix et al., 2006), GP upper confidence bound (Srinivas et al., 2010), or a combination of them (Hoffman et al., 2011).”