Sequential Search Based on Kriging: Convergence Analysis of Some Algorithms
Emmanuel Vazquez, Julien Bect
SUPELEC, Gif-sur-Yvette, France

The optimization of functions whose evaluation involves time-consuming computer programs has often to be carried out with a small budget of evaluations. In this context, Bayesian optimization has become a popular approach for it can lead to significant savings in the number of function evaluations over traditional optimization methods. The principle of Bayesian optimization is to combine evaluation results and prior information about the function to be optimized in order to efficiently select new evaluation points. Ideas supporting Bayesian optimization can be generalized to derive other types of sequential search algorithms, e.g. algorithms to estimate quantiles or excursion sets.

Moreover, choosing a Gaussian process prior makes it possible to obtain computationally tractable and easy-to-implement Bayesian algorithms. A Gaussian process prior is generally specified by choosing its covariance function in some parametric class of positive definite functions, the value of the parameters assumed to be unknown. There are chiefly two strategies to deal with these unknown parameters. The standard strategy consists in estimating the parameters from the evaluation results by maximum likelihood and then plugging the estimated parameters into the Bayesian sampling criterion. However, this plug-in approach may lead to disappointing results when the evaluation results do not carry enough information to estimate the parameters satisfactorily. An alternative approach is to adopt a fully Bayesian formulation of the sequential search problem, where the uncertainty about the parameters of the covariance function is also taken into account. Fully Bayesian algorithms are computationally more expensive than plug-in algorithms, but empirical convergence analysis shows that they tend to be more robust than plug-in algorithms.

Keywords: Sequential design of experiments; Gaussian processes; Computer experiments

Biography: Emmanuel Vazquez is an associate professor at SUPELEC, Gif-sur-Yvette, France. His research interests are in nonparametric methods for function approximation, in particular reproducing kernel methods and Gaussian processes.