IEDA Seminar - On the Minimax Optimality of the Gaussian Process Upper Confidence Bound Algorithm
Gaussian process upper confidence bound (GP-UCB) is a popular online algorithm for optimizing unknown functions. Its empirical successes call for a deeper theoretical understanding of this algorithm. This paper concerns the minimax optimality of GP-UCB, which has remained an open problem despite numerous studies in recent years. When the objective function has a specific smoothness property, a significant gap exists between established upper bounds on the regret (simple or cumulative) of GP-UCB and minimax lower bounds for any algorithm to optimize an arbitrary function with the same smoothness. We bridge the gap in this paper, proving new upper bounds on both types of regrets of GP-UCB. These upper bounds match the corresponding minimax lower bounds up to logarithmic factors independent of the dimensionality of the feasible region. The key in our analysis is a refined uniform error bound—which we derive from empirical process theory and are of independent interest—for online estimation of smooth functions with kernel methods.
Xiaowei Zhang is an assistant professor in the Faculty of Business and Economics, University of Hong Kong. He received his PhD in Management Science and Engineering from Stanford University and B.S. in Mathematics from Nankai University. His recent research interests include high-dimensional simulation optimization.