`

Timezone: »

 
Poster
Regret Bounds for Gaussian-Process Optimization in Large Domains
Manuel Wuethrich · Bernhard Schölkopf · Andreas Krause

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @ None #None

The goal of this paper is to characterize Gaussian-Process optimization in the setting where the function domain is large relative to the number of admissible function evaluations, i.e., where it is impossible to find the global optimum. We provide upper bounds on the suboptimality (Bayesian simple regret) of the solution found by optimization strategies that are closely related to the widely used expected improvement (EI) and upper confidence bound (UCB) algorithms. These regret bounds illuminate the relationship between the number of evaluations, the domain size (i.e. cardinality of finite domains / Lipschitz constant of the covariance function in continuous domains), and the optimality of the retrieved function value.In particular, we show that even when the number of evaluations is far too small to find the global optimum, we can find nontrivial function values (e.g. values that achieve a certain ratio with the optimal value).

Author Information

Manuel Wuethrich (Max Planck Institute for Intelligent Systems)
Bernhard Schölkopf (MPI for Biological Cybernetics)
Andreas Krause (ETH Zurich)

More from the Same Authors