# Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 30 Jan 2024.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Earth System Modeling 2.0: A Blueprint for Models That Learn From Observations and Targeted High-Resolution Simulations](https://mlsanity.com/paper/1709.00037/) (2017)
- [Convergence Guarantees for Adaptive Bayesian Quadrature Methods](https://mlsanity.com/paper/1905.10271/) (2019)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [Goal-Driven Dynamics Learning via Bayesian Optimization](https://mlsanity.com/paper/1703.09260/) (2017)
- [Inverse Problems and Data Assimilation](https://mlsanity.com/paper/1810.06191/) (2018)
- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Regret Bounds for Noise-Free Kernel-Based Bandits](https://mlsanity.com/paper/2002.05096/) (2020)
- [Efficient Batch Black-box Optimization with Deterministic Regret Bounds](https://mlsanity.com/paper/1905.10041/) (2019)
- [Alignment of Density Maps in Wasserstein Distance](https://mlsanity.com/paper/2305.12310/) (2023)
- [Optimization on Manifolds via Graph Gaussian Processes](https://mlsanity.com/paper/2210.10962/) (2022)
- [Introduction To Gaussian Process Regression In Bayesian Inverse Problems, With New ResultsOn Experimental Design For Weighted Error Measures](https://mlsanity.com/paper/2302.04518/) (2023)

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

- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [Voronoi Candidates for Bayesian Optimization](https://mlsanity.com/paper/2402.04922/) (2024)
- [Efficient optimization of expensive black-box simulators via marginal means, with application to neutrino detector design](https://mlsanity.com/paper/2508.01834/) (2025)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Sampling as Bandits: Evaluation-Efficient Design for Black-Box Densities](https://mlsanity.com/paper/2509.01437/) (2025)
- [Bayesian Optimization on Networks](https://mlsanity.com/paper/2510.27643/) (2025)
- [Exploration strategies for Gaussian process bandit optimization with inference regret guarantees](https://mlsanity.com/paper/2610.16187/) (2026)

## Abstract (arXiv)

This paper proposes novel noise-free Bayesian optimization strategies that rely on a random exploration step to enhance the accuracy of Gaussian process surrogate models. The new algorithms retain the ease of implementation of the classical GP-UCB algorithm, but the additional random exploration step accelerates their convergence, nearly achieving the optimal convergence rate. Furthermore, to facilitate Bayesian inference with an intractable likelihood, we propose to utilize optimization iterates for maximum a posteriori estimation to build a Gaussian process surrogate model for the unnormalized log-posterior density. We provide bounds for the Hellinger distance between the true and the approximate posterior distributions in terms of the number of design points. We demonstrate the effectiveness of our Bayesian optimization algorithms in non-convex benchmark objective functions, in a machine learning hyperparameter tuning problem, and in a black-box engineering design problem. The effectiveness of our posterior approximation approach is demonstrated in two Bayesian inference problems for parameters of dynamical systems.