Abstract
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.
The Challenge of Thompson Sampling
Bayesian Optimization (BO) is the gold standard for optimizing expensive black-box functions, such as tuning chemical processes or large-scale neural networks. BO operates in two loops: an outer loop that samples the expensive function and an inner loop that optimizes an acquisition function to determine the next sample point.
Thompson Sampling (TS) is a powerful acquisition strategy, but its inner loop involves finding the global minimum of a posterior sample path. These paths are often highly non-convex and "wiggly," making global optimization "catastrophically difficult" in high dimensions. Traditional approaches like random restarts or genetic algorithms are often inefficient or fail to find the global optimum as dimensionality increases.
The TS-roots Methodology
Researchers from the University of Houston have introduced TS-roots, a method that makes optimizing posterior samples efficient and scalable by leveraging the mathematical property of "separability" in Gaussian Process (GP) priors.
The approach relies on three key pillars:
- Pathwise Conditioning: The posterior sample is decomposed into a prior sample and a data adjustment term.
- Exploiting Separability: By choosing a separable GP prior, a $d$-dimensional prior sample becomes a product of $d$ independent 1D functions. This transforms a complex $d$-dimensional search into $d$ simple 1D problems.
- Global Rootfinding: Using Chebyshev polynomial approximation, the algorithm finds all roots of the derivatives of these 1D functions, identifying the exact local minima of the prior sample.
Judicious Starting Points
Instead of relying on thousands of random starts, TS-roots selects a small set of "judicious" starting points to initialize gradient-based optimizers:
- Exploration Set ($S_e$): The best local minima of the prior sample.
- Exploitation Set ($S_x$): The locations of existing data points.
The core insight is that the prior sample's landscape is an excellent surrogate for the posterior sample's landscape. Remarkably, starting from just one point in each set often discovers the global optimum. Because the rootfinding occurs in 1D, the computational cost scales linearly with the number of dimensions, effectively breaking the curse of dimensionality.
Results and Impact
The method was evaluated on synthetic benchmarks (e.g., 10D Levy, 16D Ackley) and a real-world ten-bar truss engineering design problem.
- Superior Performance: TS-roots outperformed standard methods like Expected Improvement (EI) and Lower Confidence Bound (LCB) on complex functions.
- Efficiency: It found significantly better acquisition values in a fraction of the time compared to genetic algorithms.
- Versatility: TS-roots also improves other advanced BO strategies, such as Max-value Entropy Search (MES), by providing higher-quality samples.
Limitations and Future Work
The current algorithm requires a separable GP prior, which excludes certain complex kernels. Future work will extend the method to other spectral representations and provide a deeper theoretical analysis of failure probabilities relative to subset sizes.
Implementation available at: https://github.com/UQUH/TSRoots
Summary updated