# Optimizing Posterior Samples for Bayesian Optimization via Rootfinding

arXiv: https://arxiv.org/abs/2410.22322 · HTML: https://mlsanity.com/paper/2410.22322/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 53 references that are in the map.
- First posted on arXiv 29 Oct 2024.

## Builds on (most cited first, 22 of 22)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2006.05078/) (2020)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Maximizing acquisition functions for Bayesian optimization](https://mlsanity.com/paper/1805.10196/) (2018)
- [Structure Discovery in Nonparametric Regression through Compositional Kernel Search](https://mlsanity.com/paper/1302.4922/) (2013)
- [Hilbert Space Methods for Reduced-Rank Gaussian Process Regression](https://mlsanity.com/paper/1401.5508/) (2014)
- [Variational Fourier features for Gaussian processes](https://mlsanity.com/paper/1611.06740/) (2016)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Pathwise Conditioning of Gaussian Processes](https://mlsanity.com/paper/2011.04026/) (2020)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [Joint Entropy Search for Multi-objective Bayesian Optimization](https://mlsanity.com/paper/2210.02905/) (2022)
- [Parallel Bayesian Global Optimization of Expensive Functions](https://mlsanity.com/paper/1602.05149/) (2016)
- [Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions](https://mlsanity.com/paper/1511.07130/) (2015)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [A General Framework for User-Guided Bayesian Optimization](https://mlsanity.com/paper/2311.14645/) (2023)
- [On Local Optimizers of Acquisition Functions in Bayesian Optimization](https://mlsanity.com/paper/1901.08350/) (2019)

## Built on by (most cited first, 5 of 5)

- [Multi-fidelity Machine Learning for Uncertainty Quantification and Optimization](https://mlsanity.com/paper/2410.23482/) (2024)
- [Sampling from Gaussian Processes: A Tutorial and Applications in Global Sensitivity Analysis and Optimization](https://mlsanity.com/paper/2507.14746/) (2025)
- [Bayesian Optimization under Uncertainty for Training a Scale Parameter in Stochastic Models](https://mlsanity.com/paper/2510.06439/) (2025)
- [Local Entropy Search over Descent Sequences for Bayesian Optimization](https://mlsanity.com/paper/2511.19241/) (2025)
- [An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions](https://mlsanity.com/paper/2605.00855/) (2026)

## Abstract (arXiv)

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 .