Regret Bounds for Gaussian-Process Optimization in Large Domains. (arXiv:2104.14113v3 [cs.LG] UPDATED)

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 …

arxiv gaussian-process optimization process