Statistics – Machine Learning
Scientific paper
2011-01-18
J.Mach.Learn.Res. 12 (2011) 2879-2904
Statistics
Machine Learning
Scientific paper
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.
No associations
LandOfFree
Convergence rates of efficient global optimization algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Convergence rates of efficient global optimization algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergence rates of efficient global optimization algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-287215