Regret Optimality of GP-UCB
Wenjia Wang Xiaowei Zhang Lu Zou
Gaussian Process Upper Confidence Bound (GP-UCB) is one of the most popular
methods for optimizing black-box functions with noisy observations, due to its
simple structure and superior performance. Its empirical successes lead to a
natural, yet unresolved question: Is GP-UCB regret optimal? In this paper, we
offer the first generally affirmative answer to this important open question in
the Bayesian optimization literature. We establish new upper bounds on both the
simple and cumulative regret of GP-UCB when the objective function to optimize
admits certain smoothness property. These upper bounds match the known minimax
lower bounds (up to logarithmic factors independent of the feasible region's
dimensionality) for optimizing functions with the same smoothness.
Intriguingly, our findings indicate that, with the same level of exploration,
GP-UCB can simultaneously achieve optimality in both simple and cumulative
regret. The crux of our analysis hinges on a refined uniform error bound for
online estimation of functions in reproducing kernel Hilbert spaces. This error
bound, which we derive from empirical process theory, is of independent
interest, and its potential applications may reach beyond the scope of this
study.