jmlr jmlr2011 jmlr2011-18 jmlr2011-18-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Adam D. Bull
Abstract: In the efficient global optimization problem, we minimize an unknown function f , using as few observations f (x) as possible. It can be considered a continuum-armed-bandit problem, with noiseless data, and simple regret. Expected-improvement algorithms are perhaps the most popular methods for solving the problem; in this paper, we provide theoretical results on their asymptotic behaviour. Implementing these algorithms 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 its RKHS. We provide convergence rates for this procedure, optimal for functions of low smoothness, and describe a modified algorithm attaining optimal rates for smoother functions. In practice, however, priors are typically estimated sequentially from the data. For standard estimators, we show this procedure may never find 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. Keywords: convergence rates, efficient global optimization, expected improvement, continuumarmed bandit, Bayesian optimization
Milton Abramowitz and Irene A. Stegun, editors. Handbook of Mathematical Functions. Dover, New York, 1965. Robert J. Adler and Jonathan E. Taylor. Random Fields and Geometry. Springer Monographs in Mathematics. Springer, New York, 2007. Nachman Aronszajn. Theory of reproducing kernels. Trans. Amer. Math. Soc., 68(3):337–404, 1950. Alain Berlinet and Christine Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Kluwer Academic Publishers, Boston, Massachusetts, 2004. Eric Brochu, Mike Cora, and Nando de Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. Arxiv preprint arXiv:1012.2599, 2010. S´ bastien Bubeck, R´ mi Munos, and Gilles Stoltz. Pure exploration in multi-armed bandits probe e lems. In Proc. 20th International Conference on Algorithmic Learning Theory (ALT ’09), pages 23–37, Porto, Portugal, 2009. S´ bastien Bubeck, R´ mi Munos, Gilles Stoltz, and Csaba Szepesvari. X-armed bandits. Arxiv e e preprint arXiv:1001.4475, 2010. Persi Diaconis and David Freedman. On the consistency of Bayes estimates. Ann. Statist., 14(1): 1–26, 1986. 2902 C ONVERGENCE R ATES OF E FFICIENT G LOBAL O PTIMIZATION Peter Frazier, Warren Powell, and Savas Dayanik. The knowledge-gradient policy for correlated normal beliefs. INFORMS J. Comput., 21(4):599–613, 2009. David Ginsbourger, Rodolphe le Riche, and Laurent Carraro. A multi-points criterion for deterministic parallel global optimization based on Gaussian processes. HAL preprint hal-00260579, 2008. Steffen Grunewalder, Jean-Yves Audibert, Manfred Opper, and John Shawe-Taylor. Regret bounds for Gaussian process bandit problems. In Proc. 13th International Conference on Artificial Intelligence and Statistics (AISTATS ’10), pages 273–280, Sardinia, Italy, 2010. Pierre Hansen, Brigitte Jaumard, and Shi-Hui Lu. Global optimization of univariate Lipschitz functions: I. survey and properties. Math. Program., 55(1):251–272, 1992. Donald R. Jones, Cary D. Perttunen, and Bruce E. Stuckman. Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl., 79(1):157–181, 1993. Donald R. Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of expensive black-box functions. J. Global Optim., 13(4):455–492, 1998. Robert Kleinberg and Aleksandrs Slivkins. Sharp dichotomies for regret minimization in metric spaces. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA ’10), pages 827–846, Austin, Texas, 2010. Marco Locatelli. Bayesian algorithms for one-dimensional global optimization. J. Global Optim., 10(1):57–76, 1997. William G. Macready and David H. Wolpert. Bandit problems and the exploration / exploitation tradeoff. IEEE Trans. Evol. Comput., 20(1):2–22, 1998. Jonas Moˇ kus. On Bayesian methods for seeking the extremum. In Proc. IFIP Technical Conferc ence, pages 400–404, Novosibirsk, Russia, 1974. Francis J. Narcowich, Joseph D. Ward, and Holger Wendland. Refined error estimates for radial basis function interpolation. Constr. Approx., 19(4):541–564, 2003. Michael Osborne. Bayesian Gaussian processes for sequential prediction, optimisation and quadrature. DPhil thesis, University of Oxford, Oxford, UK, 2010. Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput., 26(2):350–368, 1997. Panos M. Pardalos and H. Edwin Romeijn, editors. Handbook of Global Optimization, Volume 2. Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht, the Netherlands, 2002. Emanuel Parzen. Probability density functionals and reproducing kernel Hilbert spaces. In Proc. Symposium on Time Series Analysis, pages 155–169, Providence, Rhode Island, 1963. Carl E. Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, Cambridge, Massachusetts, 2006. 2903 B ULL Thomas J. Santner, Brian J. Williams, and William I. Notz. The Design and Analysis of Computer Experiments. Springer Series in Statistics. Springer, New York, 2003. Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In Proc. 27th International Conference on Machine Learning (ICML ’10), Haifa, Israel, 2010. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: an Introduction. MIT Press, Cambridge, Massachusetts, 1998. Luc Tartar. An Introduction to Sobolev Spaces and Interpolation Spaces, volume 3 of Lecture Notes of the Unione Matematica Italiana. Springer, New York, 2007. Aad W. van der Vaart and J. Harry van Zanten. Reproducing kernel Hilbert spaces of Gaussian priors. In Pushing the Limits of Contemporary Statistics: Contributions in Honor of Jayanta K. Ghosh, volume 3 of Institute of Mathematical Statistics Collections, pages 200–222. Institute of Mathematical Statistics, Beachwood, Ohio, 2008. Aad W. van der Vaart and J. Harry van Zanten. Adaptive Bayesian estimation using a Gaussian random field with inverse gamma bandwidth. Ann. Statist., 37(5B):2655–2675, 2009. Emmanuel Vazquez and Julien Bect. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. J. Statist. Plann. Inference, 140(11):3088–3095, 2010. Holger Wendland. Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, UK, 2005. 2904