Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization
This work provides theoretical guarantees for a variant of expected improvement, addressing a gap in Bayesian optimization theory, which is incremental but important for researchers and practitioners in optimization and machine learning.
The paper tackles the lack of theoretical analysis for expected improvement in Bayesian optimization by analyzing a randomized variant based on posterior sampling, showing it achieves sublinear Bayesian cumulative regret bounds under Gaussian process assumptions, with effectiveness demonstrated through numerical experiments.
Bayesian optimization is a powerful tool for optimizing an expensive-to-evaluate black-box function. In particular, the effectiveness of expected improvement (EI) has been demonstrated in a wide range of applications. However, theoretical analyses of EI are limited compared with other theoretically established algorithms. This paper analyzes a randomized variant of EI, which evaluates the EI from the maximum of the posterior sample path. We show that this posterior sampling-based random EI achieves the sublinear Bayesian cumulative regret bounds under the assumption that the black-box function follows a Gaussian process. Finally, we demonstrate the effectiveness of the proposed method through numerical experiments.