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

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

Problem Statement
Bayesian Optimization (BO) is a standard framework for globally optimizing expensive black-box functions, widely used in hyperparameter tuning, robotics, and scientific design. The BO procedure involves two steps: fitting a surrogate model (typically a Gaussian Process) and optimizing an acquisition function to select the next query point. While significant research has focused on improving surrogate models and acquisition function design, the optimization of the acquisition function itself remains a critical bottleneck. In practice, this inner optimization problem is often non-convex, multimodal, and high-dimensional. Existing derivative-free optimizers (e.g., Differential Evolution, CMA-ES, Sobol Search) often treat this as a generic black-box problem, failing to explicitly exploit the structured nature of acquisition landscapes. Consequently, these methods can become trapped in local optima or require excessive evaluations to find high-quality candidates, limiting the overall efficiency of the BO process.

Methodology: KSOS-BO
The authors propose KSOS-BO, a kernel-based, derivative-free framework designed specifically to optimize acquisition functions. The method adapts the Kernel Sum-of-Squares (KernelSOS) approach to the BO setting.

1. Formulation: The core idea is to reformulate the minimization of the acquisition function $\alpha(x)$ as a global optimization problem seeking the largest lower bound $c$ such that $\alpha(x) - c \geq 0$ for all $x$ in the domain.
2. Kernel Relaxation: Unlike classical Sum-of-Squares (SOS) methods restricted to polynomial objectives, KSOS-BO utilizes Reproducing Kernel Hilbert Spaces (RKHS). It replaces finite-dimensional polynomial bases with kernel functions. The non-negativity constraint is relaxed into a semidefinite program (SDP) involving a kernel matrix $K$ derived from a finite set of sampled points.
3. Optimization and Recovery: The algorithm solves an SDP to find a kernel-based surrogate representation of the shifted acquisition function. Instead of directly optimizing in the input space, it recovers a continuous candidate point $x^*$ as a weighted combination of the sampled points. This allows the method to perform a structured global search using only function evaluations.
4. Integration: In each BO iteration, KSOS-BO samples points to evaluate the current acquisition function, constructs the KernelSOS surrogate, solves the SDP to find the next candidate, and updates the BO model.

Key Contributions

• Structured Global Search: The paper introduces a novel application of KernelSOS to acquisition optimization, moving beyond generic black-box search to exploit the smooth, structured nature of acquisition landscapes induced by Gaussian Process surrogates.
• Derivative-Free Framework: The method operates without requiring gradients, making it compatible with standard derivative-free settings while providing a principled alternative to heuristic population-based searches.
• Performance Gains: The authors demonstrate that despite a higher per-iteration computational cost due to the SDP step, KSOS-BO achieves faster convergence in wall-clock time by reaching high-quality solutions with fewer acquisition evaluations.

Experimental Results
The authors evaluated KSOS-BO against three derivative-free baselines (Sobol Search, Differential Evolution, and CMA-ES) across 15 benchmark functions with varying landscape properties (multimodal, bowl-shaped, valley-shaped, plate-shaped, and steep drops) in 10 dimensions.

• Regret Improvement: KSOS-BO achieved the best performance on 10 out of 15 benchmarks. On these top-performing functions, it showed an average regret improvement of 81.16% compared to the second-best optimizer.
• Wall-Clock Efficiency: Although KSOS-BO incurs higher computational overhead per iteration, it converged faster in real time. On the 10 benchmarks where it ranked first, it achieved an average wall-clock time improvement of 93.55%, effectively halving the time required to reach the same accuracy as the baselines.
• Landscape Sensitivity: The method excelled on highly multimodal functions (e.g., Ackley, Rastrigin, Griewank) and smooth unimodal functions (e.g., Rosenbrock, Dixon Price). However, performance degraded on functions with extreme curvature, steep drops, or plate-shaped regions (e.g., Michalewicz, Zakharov, Styblinski Tang), where the kernel-based representation was found to be less adequate.
• Robustness: Ablation studies indicated that KSOS-BO is robust to variations in initial design size, evaluation budgets, and kernel choices (Gaussian vs. Laplace), though it consistently outperformed baselines on the majority of test cases.

Significance and Claims
The paper claims that enhancing the acquisition optimization step alone yields measurable improvements in overall Bayesian Optimization performance. The primary significance lies in demonstrating that treating acquisition optimization as a structured problem solvable via KernelSOS relaxations is superior to treating it as a generic black-box problem.

The authors modestly note that while KSOS-BO is effective for diverse landscape structures, it is not a universal solution; it struggles with specific geometric features like steep drops or flat plateaus. Furthermore, the method introduces a computational trade-off: the SDP step is more expensive than standard evolutionary strategies, but this cost is justified by the reduction in the number of expensive function evaluations required to find optimal solutions. The work suggests that future directions should focus on improving the scalability of KSOS-BO, exploring hybrid strategies with local refinement, and testing in higher-dimensional or constrained settings.