Abstract
Bayesian optimization devolves the global optimization of a costly objectivefunction to the global optimization of a sequence of acquisition functions.This inner-loop optimization can be catastrophically difficult if it involvesposterior sample paths, especially in higher dimensions. We introduce anefficient global optimization strategy for posterior samples based on globalrootfinding. It provides gradient-based optimizers with two sets of judiciouslyselected starting points, designed to combine exploration and exploitation. Thenumber of starting points can be kept small without sacrificing optimizationquality. Remarkably, even with just one point from each set, the global optimumis discovered most of the time. The algorithm scales practically linearly tohigh dimensions, breaking the curse of dimensionality. For Gaussian processThompson sampling (GP-TS), we demonstrate remarkable improvement in both inner-and outer-loop optimization, surprisingly outperforming alternatives like EIand GP-UCB in most cases. Our approach also improves the performance of otherposterior sample-based acquisition functions, such as variants of entropysearch. Furthermore, we propose a sample-average formulation of GP-TS, whichhas a parameter to explicitly control exploitation and can be computed at thecost of one posterior sample. Our implementation is available athttps://github.com/UQUH/TSRoots .