Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration
This work addresses the challenge of costly function evaluations in optimization, offering a parallel method that is incremental but provides dimension-free theoretical guarantees.
The paper tackles the problem of optimizing an expensive, noisy black-box function by introducing GP-UCB-PE, a parallel batch algorithm that combines UCB and pure exploration strategies, achieving a theoretical regret improvement of order sqrt{K} over sequential methods and demonstrating empirical efficiency on real and synthetic problems.
In this paper, we consider the challenge of maximizing an unknown function f for which evaluations are noisy and are acquired with high cost. An iterative procedure uses the previous measures to actively select the next estimation of f which is predicted to be the most useful. We focus on the case where the function can be evaluated in parallel with batches of fixed size and analyze the benefit compared to the purely sequential procedure in terms of cumulative regret. We introduce the Gaussian Process Upper Confidence Bound and Pure Exploration algorithm (GP-UCB-PE) which combines the UCB strategy and Pure Exploration in the same batch of evaluations along the parallel iterations. We prove theoretical upper bounds on the regret with batches of size K for this procedure which show the improvement of the order of sqrt{K} for fixed iteration cost over purely sequential versions. Moreover, the multiplicative constants involved have the property of being dimension-free. We also confirm empirically the efficiency of GP-UCB-PE on real and synthetic problems compared to state-of-the-art competitors.