Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization

2025/07/13 by Takeno, Shion, Inatsu, Yu, Karasuyama, Masayuki +1
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2507.09828

Abstract

Bayesian optimization is a powerful tool for optimizing an expensive-to-evaluate black-box function. In particular, the effectiveness of expected improvement (EI) has been demonstrated in a wide range of applications. However, theoretical analyses of EI are limited compared with other theoretically established algorithms. This paper analyzes a randomized variant of EI, which evaluates the EI from the maximum of the posterior sample path. We show that this posterior sampling-based random EI achieves the sublinear Bayesian cumulative regret bounds under the assumption that the black-box function follows a Gaussian process. Finally, we demonstrate the effectiveness of the proposed method through numerical experiments.

Citations

• Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization
• Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance
• On the convergence rate of noisy Bayesian Optimization with Expected Improvement
• Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds
• Unexpected Improvements to Expected Improvement for Bayesian Optimization
• Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds
• Joint Entropy Search for Multi-objective Bayesian Optimization
• Joint Entropy Search for Maximally-Informed Bayesian Optimization
• Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization
• Distributionally Robust Bayesian Optimization with φ-divergences
• Optimal Order Simple Regret for Gaussian Process Bandits
• High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning
• On Information Gain and Regret Bounds in Gaussian Process Bandits
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding
• Bandit optimisation of functions in the Matérn kernel RKHS
• Tight Regret Bounds for Bayesian Optimization in One Dimension
• A Flexible Framework for Multi-Objective Bayesian Optimization using\n Random Scalarizations
• Constrained Bayesian Optimization with Noisy Experiments
• On Kernelized Multi-armed Bandits
• Max-value Entropy Search for Efficient Bayesian Optimization
• Bayesian Optimization with Safety Constraints: Safe and Automatic\n Parameter Tuning in Robotics
• Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters
• Bayesian Optimization with Unknown Constraints
• Learning to Optimize via Information-Directed Sampling
• Approximating Mills ratio
• Learning to Optimize Via Posterior Sampling
• Learning to Optimize via Posterior Sampling
• Practical Bayesian Optimization of Machine Learning Algorithms
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Convergence properties of the expected improvement algorithm
• Taking the Human Out of the Loop: A Review of Bayesian Optimization

Related

• Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization
• Bayesian Optimization with Expected Improvement: No Regret and the Choice of Incumbent
• Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds
• A Corrected Expected Improvement Acquisition Function Under Noisy Observations
• Regret Analysis for Randomized Gaussian Process Upper Confidence Bound