Surrogate modeling for Bayesian optimization beyond a single Gaussian process

1 INTRODUCTION

• The work targets BO that reduces design effort, supports parallel evaluations, and has convergence guarantees, addressing needs identified for time-consuming black-box optimization.The introduction also motivates these goals by the expertise required to choose surrogate models, kernels, and acquisition functions.Source: §1 · p. 1

1.1 Related works

• Prior work had explored ensembles of acquisition functions for a single GP, but not the complementary setting of an ensemble of GP surrogate models with a given acquisition function.The related-work discussion also identifies automatic kernel selection for GP-based BO as unexplored.Source: §1.1 · pp. 1–2
• TS offers BO acquisition without additional design parameters, but its mixture-prior counterpart with regret analysis had not been studied in BO.Parallel BO using other acquisition rules typically relies on additional hyperparameters or selection rules for query diversity.Source: §1.1 · pp. 1–2

1.2 Contributions

• EGP-TS adaptively weights an ensemble of GPs, uses random-feature approximation for scalable function sampling, and supports synchronous or asynchronous parallel evaluations.The method uses TS without additional design parameters.Source: §1.2 · p. 2
• The paper establishes sublinear Bayesian regret for EGP-TS in sequential and parallel settings and tests it on synthetic functions, three-model hyperparameter tuning, and robot pushing.The tests compare EGP-TS with single GP-based TS and alternative ensemble approaches.Source: §1.2 · p. 2
• Unlike the prior supervised-learning use of EGP, this BO adaptation actively selects query points and uses random features to scale TS function sampling with limited labeled data.The contribution discussion notes that kernel-hyperparameter updates require extra weight and model reinitialization.Source: §1.2 · p. 2

2 PRELIMINARIES

• BO seeks the maximizing feasible input of a black-box objective that is expensive to evaluate and lacks an available analytic expression.These properties make exhaustive enumeration and conventional gradient-based solvers unsuitable in the described setting.Source: §2 · p. 2
• BO iteratively fits a surrogate posterior from observed input-output pairs and maximizes an acquisition function designed to balance exploration and exploitation.The procedure selects the next query using the posterior over the objective.Source: §2 · p. 2

2.1 GP-based surrogate model and TS for acquisition

• A GP prior models the unknown function using a positive-definite kernel to encode pairwise input similarity, while observations are linked to function values through a noisy likelihood.The posterior is updated from the acquired data, and TS selects a query by sampling a function from that posterior and maximizing it.Source: §2.1 · pp. 2–3
• Random-feature approximation converts learning with stationary kernels into a parametric form that can support scalable sampling of functions from the GP posterior.The text presents it as one approach to function sampling for TS.Source: §2.1 · p. 3

3 ENSEMBLE GPS WITH TS FOR BO

• EGP forms a non-Gaussian surrogate from an ensemble of GPs with distinct kernels, weighting each model’s contribution to the sought function.The posterior mixture weights are informed by the acquired data’s marginal likelihood under each GP.Source: §3 · p. 3

3.1 RF-based EGP-TS

• EGP-TS samples a GP model according to its mixture weight and draws a function path using random features, enabling differentiable and incrementally updated sampling.The resulting sampled function is maximized to select the next evaluation input.Source: §3 · p. 3, §3.1 · p. 3
• After each evaluation, Bayes’ rule updates the per-GP weights; kernel hyperparameters are periodically re-estimated using all acquired data, followed by weight reinitialization.Between such updates, the function posterior is propagated incrementally.Source: §3.1 · p. 4

3.2 Parallel EGP-TS

• EGP-TS supports synchronous batches by sampling once per worker and asynchronous operation by updating the posterior whenever a worker finishes.Both parallel settings use the same posterior-based query-selection procedure without extra design.Source: §3.2 · p. 4
• The EGP surrogate can also be paired with EI or UCB, but devising those rules directly from the GP-mixture posterior is left for future investigation.When kernels share a type, the EGP prior corresponds to a pseudo-Bayesian GP with hyperparameters chosen from a finite set.Source: §3.2 · pp. 4–5

4 BAYESIAN REGRET ANALYSIS

• Assumption 1 requires smooth GP sample paths on a compact, convex domain; it holds for several four-times-differentiable stationary kernels, including Gaussian and Matérn kernels with ν > 2.The section also identifies MIG as an information-theoretic measure of BO’s statistical difficulty and uses it in the regret bound.Source: §4 · p. 5
• The sequential proof splits regret into two terms, bounding one with single-GP results and the other through latent-model confidence sets and posterior standard deviations.The second term is further bounded using maximum information gain (MIG).Source: §4 · p. 5
• For K-worker asynchronous and synchronous evaluations, the paper gives cumulative regret bounds; in the asynchronous setting, the first term scales by √ρ_K relative to the sequential bound.The bounds concern evaluation counts, which typically exceed those in the sequential setup.Source: §4 · pp. 5–6
• Across sequential and parallel settings, cumulative Bayesian regret is O(MT^(c+1) log T), yielding diminishing average regret when 0 ≤ c < 1.The paper states that the bound is sublinear in the number of evaluations in this range.Source: §4 · p. 6

5 NUMERICAL TESTS

• The experiments compare EGP-TS with GP-EI, GP-TS variants, fully Bayesian GP-TS, BanditBO, and EXP3BO, using 10 repetitions and reporting average performance and standard deviation.Unless stated otherwise, EGP-TS hyperparameters are refitted every 50 iterations, versus every iteration for other baselines; TS methods use 50 spectral features for fairness.Source: §5 · p. 6

5.1 Tests on synthetic functions

• On synthetic functions, EGP-TS improves on GP-TS counterparts and BanditBO/EXP3BO; with 11 RBF lengthscales, it outperforms all competitors.The tests include Ackley-5d, Zakharov, Drop-wave, and Eggholder; GP-EI is superior to GP-TS on Zakharov, but EGP-TS performs better than GP-EI there.Source: §5.1 · pp. 6–7

5.2 Robot pushing tasks

• On both robot-pushing tasks, EGP-TS outperforms the tested competitors with a four-kernel dictionary and also beats fully Bayesian GP-TS in simple regret while running faster.The tasks use 3 and 4 input variables; the four-kernel dictionary combines RBF kernels with and without ARD and Matérn kernels with ν = 3/2 and 5/2.Source: §5.2 · p. 7, Figure 3 · p. 7

5.3 Hyperparameter tuning tasks

• Across NN, SVM, and gradient-boosting hyperparameter tuning, EGP-TS performs better than competitors in most cases with either kernel-form or RBF-lengthscale dictionaries.The evaluation covers Breast cancer, Iris, Transportation, and Wine datasets; validation accuracy is measured on held-out data.Source: §5.3 · p. 7

5.4 Preliminary results for EGP-EI

• For EGP-EI, results favor it over GP-EI on three of four synthetic functions and both robot-pushing tasks.The preliminary comparison uses kernel hyperparameters updated each iteration and no random-feature approximation.Source: §5.4 · p. 7, Figure 10 · p. 9, Figure 11 · p. 9

6 CONCLUSIONS

• EGP-TS combines an adaptive ensemble GP prior with random-feature sampling and Thompson sampling, and has sublinear cumulative Bayesian regret in sequential and parallel settings.The conclusion identifies other acquisition functions and frequentist-regret analysis as future work.Source: §6 · p. 9

7.1.1 Proof for Lemma 4

• The confidence set C_t misses the optimal model m* with probability at most 2MT^-1 at each time t.Source: §7.1 · p. 10

7.1 Proof of Theorem 1

• Theorem 1’s proof combines a GP sample-path supremum bound and confidence-set control to bound EGP-TS cumulative Bayesian regret.It uses η = 2√log T and β^(1/2)_T ≈ √(d log T).Source: §7.1 · pp. 9–11

7.1.2 Proof for Lemma 5

• The proof bounds the expected difference between the sampled model’s posterior mean and function value by 3B.Source: §7.1 · p. 9, §7.1.2 · p. 12

7.2 Proof of Theorem 2

• The asynchronous parallel proof establishes a cumulative Bayesian-regret bound for EGP-TS over T function evaluations.Source: §7.2 · p. 12

7.3 Proof of Theorem 3

• The synchronous parallel proof likewise derives the cumulative Bayesian-regret bound in Theorem 3.Source: §7.3 · pp. 12–13

APPENDIX A RANDOM FEATURE (RF) APPROXIMATION FOR GP

• Random Fourier features approximate shift-invariant kernels, allowing the nonparametric GP prior to be represented through a finite feature-based posterior.The approximation draws i.i.d. spectral samples and uses them to construct the feature map.Source: Appendix A · pp. 15–16

• The appendix presents ablation studies to further assess EGP-TS performance.Source: §B.1 · p. 16

B.1.1 Function sampled from a GP prior

• EGP-TS(mixed) had slightly inferior but comparable regret to GP-TS (Matern ν = 3/2), while the matching expert weight w3 went to 1 as data accumulated.The black-box function was drawn from a Matern ν = 3/2 GP prior with lengthscale 1, matching the GP-TS kernel.Source: §B.1.1 · p. 16

B.1.2 Effect of the number M of kernels

• On Robot pushing 3D, increasing M improved performance, but gains shrank from 3 to 7; the useful dictionary size depends on the problem and available domain knowledge.The authors suggest gains may saturate when the sought posterior has more modes than the ensemble has components.Source: §B.1.2 · p. 16

B.1.3 Effect of the number D of spectral features

• On Robot pushing 3D, increasing spectral features D from 50 to 1000 produced negligible performance gain.Source: §B.1.3 · p. 16

B.2 Results of parallel EGP-TS

• Increasing K reduced runtime with slightly larger regret on Robot pushing 3D and 4D; EGP-TS also stood out against parallel TS-based baselines on Ackley-5d.Source: §B.2 · p. 16

B.3 Average runtimes on synthetic functions and robotic tasks

• EGP-TS requires slightly increased runtime relative to the single GP-TS alternatives.The comparison concerns average runtimes on synthetic functions and robotic tasks.Source: §B.3 · p. 16
• The fully Bayesian GP method is omitted because its time-consuming MCMC step requires a much larger runtime.Source: §B.3 · p. 16

B.4 Additional information about synthetic functions

• For parallel Ackley-5d regret, the figure varies K using a dictionary of 11 RBF kernels with characteristic lengthscales {10c}6 c=−4.Source: Figure 15 · p. 17
• Table 3 provides candidate values, the corresponding maximizer x∗, and f(x∗) for the synthetic functions.Source: §B.4 · p. 17, Table 3 · p. 17
• The latter three synthetic functions are the opposites of their standard forms to make them maximization problems.Source: §B.4 · p. 17