Optimizing Posterior Samples for Bayesian Optimization via Rootfinding
This work addresses a critical bottleneck in Bayesian optimization for researchers and practitioners, offering an incremental improvement in efficiency and scalability for posterior sample-based methods.
The paper tackles the difficulty of optimizing posterior sample paths in Bayesian optimization, especially in high dimensions, by introducing a global rootfinding strategy that provides efficient starting points for gradient-based optimizers, achieving linear scaling and outperforming alternatives like EI and GP-UCB in most cases.
Bayesian optimization devolves the global optimization of a costly objective function to the global optimization of a sequence of acquisition functions. This inner-loop optimization can be catastrophically difficult if it involves posterior sample paths, especially in higher dimensions. We introduce an efficient global optimization strategy for posterior samples based on global rootfinding. It provides gradient-based optimizers with two sets of judiciously selected starting points, designed to combine exploration and exploitation. The number of starting points can be kept small without sacrificing optimization quality. Remarkably, even with just one point from each set, the global optimum is discovered most of the time. The algorithm scales practically linearly to high dimensions, breaking the curse of dimensionality. For Gaussian process Thompson sampling (GP-TS), we demonstrate remarkable improvement in both inner- and outer-loop optimization, surprisingly outperforming alternatives like EI and GP-UCB in most cases. Our approach also improves the performance of other posterior sample-based acquisition functions, such as variants of entropy search. Furthermore, we propose a sample-average formulation of GP-TS, which has a parameter to explicitly control exploitation and can be computed at the cost of one posterior sample. Our implementation is available at https://github.com/UQUH/TSRoots .