Surrogate modeling for Bayesian optimization beyond a single Gaussian process

Technical Summary: Surrogate Modeling for Bayesian Optimization Beyond a Single Gaussian Process

Problem Statement
Bayesian Optimization (BO) is a principled framework for optimizing "expensive-to-evaluate" black-box functions, such as those found in hyperparameter tuning, drug discovery, and robotics. Standard BO relies on a statistical surrogate model to sequentially select query points, balancing exploration and exploitation. However, existing approaches typically depend on a single Gaussian Process (GP) with a pre-selected kernel function. This design requires significant domain expertise to choose the appropriate kernel type and hyperparameters. Furthermore, rigorous convergence guarantees for BO algorithms are often lacking, and parallelizing evaluations to reduce convergence time frequently necessitates additional hyperparameters or complex selection rules to ensure query diversity. The paper addresses the need for a BO method that minimizes tuning efforts, supports parallel operation, and provides theoretical convergence guarantees.

Methodology: EGP-TS
The proposed method, EGP-TS (Ensemble Gaussian Process with Thompson Sampling), introduces a novel framework that moves beyond a single GP surrogate.

1. Ensemble of GPs (EGP): Instead of a single kernel, the method leverages an ensemble of $M$ GPs, where each GP $m$ utilizes a kernel function $\kappa_m$ selected from a predefined dictionary $\mathcal{K}$. The prior over the objective function $f(x)$ is modeled as a weighted mixture of these GPs:
   $$f(x) \sim \sum_{m=1}^M w_m^0 \mathcal{GP}(0, \kappa_m(x, x'))$$
   The weights $w_m^t$ are updated adaptively on-the-fly based on the observed data $D_t$ using Bayes' rule, effectively selecting the most suitable surrogate model fit for the current stage of optimization.

2. Thompson Sampling (TS) Acquisition: To select the next query point, the method employs Thompson Sampling. Rather than optimizing a complex acquisition function, TS samples a function realization $\tilde{f}_t(x)$ from the posterior mixture distribution and selects the maximizer of this sampled function. This approach requires no additional design parameters.

3. Scalability via Random Features (RF): To ensure scalability, particularly for the sampling step required by TS, the method employs random feature-based kernel approximation for each GP in the ensemble. This converts the non-parametric GP learning into a parametric one, allowing for efficient function sampling and recursive Bayesian updates of the model parameters (weights and posterior means/covariances).

4. Parallelization: The EGP-TS framework naturally accommodates both synchronous and asynchronous parallel function evaluations. In a parallel setting with $K$ workers, multiple query points are generated by sampling from the current posterior mixture without requiring extra hyperparameters to enforce diversity, a common requirement in parallel BO using Upper Confidence Bound (UCB) or Expected Improvement (EI).

Key Contributions
The paper outlines four primary contributions:

• Adaptive Model Selection: It replaces the single GP with a pre-selected kernel with an ensemble of GPs that adaptively adjusts per-GP weights on-the-fly, removing the need for manual kernel selection.
• Parameter-Free Parallelism: The resulting EGP-TS approach supports both synchronous and asynchronous parallel evaluations without necessitating additional design parameters.
• Convergence Guarantees: The authors establish the convergence of EGP-TS to the global optimum by deriving sublinear Bayesian regret bounds for both sequential and parallel settings. The analysis adapts techniques from linear bandits with mixture priors to the BO context, addressing the challenges introduced by the EGP prior.
• Empirical Validation: Extensive tests on synthetic functions, robotic tasks (robot pushing), and real-world hyperparameter tuning tasks (for FNNs, SVMs, and Gradient Boosting) demonstrate the method's superiority over single GP-based TS, fully Bayesian GP-TS, and alternative ensemble approaches.

Results
Numerical experiments were conducted on standard synthetic benchmarks (Ackley-5d, Zakharov, DropWave, Eggholder) and real-world applications.

• Synthetic Functions: EGP-TS consistently achieved lower simple regret compared to GP-TS with pre-selected kernels (RBF, Matérn) and other ensemble methods like BanditBO and EXP3BO. It also outperformed fully Bayesian GP-TS.
• Robotics: In 3D and 4D robot pushing tasks, EGP-TS demonstrated superior performance in minimizing the distance to the goal location compared to all baselines, while also running significantly faster than fully Bayesian GP-TS.
• Hyperparameter Tuning: For tuning FNN, SVM, and Gradient Boosting models on datasets like Breast Cancer, Iris, and Wine, EGP-TS achieved higher validation accuracy with fewer function evaluations compared to competitors.
• Ablation: Preliminary results coupling the EGP surrogate with Expected Improvement (EGP-EI) also showed improved performance over standard GP-EI, suggesting the benefits of the ensemble model extend beyond Thompson Sampling.

Significance and Claims
The paper claims that EGP-TS offers a robust solution to the "design effort" bottleneck in Bayesian Optimization. By automating kernel selection through an ensemble approach and utilizing Thompson Sampling, the method reduces the reliance on expert domain knowledge. The theoretical contribution lies in establishing rigorous Bayesian regret bounds for an ensemble-based BO algorithm, proving that the method converges to the global optimum with diminishing average regret. The authors emphasize that while the ensemble concept has been used in supervised learning, its adaptation to BO for kernel selection, coupled with parallel scalability and convergence analysis, is a novel contribution. The work positions EGP-TS as a method that balances the expressiveness of ensemble learning with the efficiency and theoretical guarantees required for practical, high-cost optimization tasks.