KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

Bayesian Optimization (BO) is an effective framework for globally optimizing functions whose evaluations are expensive. It is particularly effective for optimizing functions defined over continuous domains and explicitly handles stochastic noise in evaluations. As a result, it is widely applied in areas such as hyperparameter tuning, robotics policy search, and scientific experiment design, where sample efficiency is essential. Its two-step procedure consists of model fitting followed by optimization of the acquisition function, which is often treated as a generic black-box problem despite its structured nature. In this work, we introduce KSOS-BO, a kernel-based framework for BO acquisition function optimization. KSOS-BO integrates the recently developed KernelSOS framework to formulate the optimization of the acquisition function as a semidefinite program with kernel-induced representations, enabling a structured global search. Across a diverse set of benchmark functions with varying landscape properties, KSOS-BO achieves the best final regret on 13 out of 20 benchmarks compared with Sobol Search, Differential Evolution, CMA-ES, and multi-start L-BFGS-B. On these 13 benchmarks, it improves final regret over the second-best optimizer by 81.08% on average. Wall-clock time experiments further show that, under the optimizer configurations considered in this study, KSOS-BO can reach high-quality solutions faster on many benchmarks despite the additional semidefinite optimization step.