Bayesian Optimization with Gaussian Process Surrogates

The foundations of Bayesian optimization trace back to work on efficient global optimization (EGO) (Jones et al. 1998), which introduced expected improvement as an acquisition function for response surface optimization. The theoretical framework using Gaussian processes draws heavily on the standard textbook treatment in (Rasmussen and Williams 2006).

Modern tutorials (Brochu et al. 2010; Frazier 2018) provide accessible introductions to the field, while (Shahriari et al. 2016) offers an extensive review covering methodological advances and applications. The GP-UCB algorithm (Srinivas et al. 2012) established regret bounds connecting Bayesian optimization to the bandit literature.

Practical Bayesian optimization for machine learning hyperparameter tuning was shown by (Snoek et al. 2012), showing that careful GP prior design produced test errors below the best hand-tuned results reported at the time. High-dimensional extensions include random embeddings (Wang et al. 2016), local trust regions (Eriksson et al. 2019), and sparse axis-aligned subspaces (Eriksson and Jankowiak 2021).

Information-theoretic acquisition functions (Hernández-Lobato et al. 2014) provide principled approaches to exploration, while portfolio methods (Brochu et al. 2011) combine multiple acquisition strategies. Multi-fidelity methods (Kandasamy et al. 2017; Li et al. 2020; Swersky et al. 2014) use cheap approximations to accelerate optimization. Transfer learning (Feurer et al. 2022; Swersky et al. 2013) enables knowledge transfer across related optimization tasks.

Scalable Gaussian process inference (Snelson and Ghahramani 2006; Titsias 2009; Matthews et al. 2016) underpins practical BO implementations, with GPyTorch (Gardner et al. 2018) providing efficient GPU-accelerated computation. Applications span neural architecture search (Kandasamy et al. 2018; Falkner et al. 2018), biological sequence design (Stanton et al. 2022), and safe exploration (Sui et al. 2015).

Read as a list of names that is a heap. It becomes a chapter once one question is put to every row: where does the GP posterior stop paying for itself, and what does this method give up to buy that place back? EGO and GP-UCB pay nothing and work only where the posterior is already cheap and accurate, in low dimension with few observations. Sparse and variational GPs give up exactness of the posterior to survive $n \sim 10^4$ . REMBO, TuRBO and SAASBO give up the assumption that the posterior is a single global object, respectively by projecting, by localising, and by zeroing most coordinates. Multi-fidelity and freeze-thaw methods give up the requirement that every evaluation be the true objective. Transfer methods give up the requirement that every observation come from the current task. Safe and constrained BO give up free access to the design space. The table below records that trade for each row: Regime is where the posterior still pays, Headline result is what the trade bought.

The following leaderboard summarises the methods this chapter dissects, organised by the regime each one targets. Read the table top-down as exploitation/exploration first, then scalability, then dimensionality, then setting-specific extensions.

Leaderboard of canonical BO methods organised by regime. *Surrogate* records the inference primitive, *Acq.* the acquisition rule, *Regime* when the method is the right default, and *Headline result* one claim the cited paper makes for itself. The headline column reproduces each paper's own reported figure on its own benchmark; the rows are not measurements from a common head-to-head study and should not be compared across rows as if they were. The chapter weaves each row into prose with full citations.
Method	Surrogate	Acq.	Regime	Headline result
EGO (Jones et al. 1998)	Kriging	EI	low-D smooth deterministic	EI acquisition plus the 1 percent stopping rule
GP-UCB (Srinivas et al. 2012)	exact GP	UCB	bandit-style with regret bound	$R_T = O^*(\sqrt{T \beta_T \gamma_T})$ sublinear
PES (Hernández-Lobato et al. 2014)	exact GP + EP	PES	low-D, very expensive evals	lower regret than EI on Branin and Hartmann-6
GP-Hedge (Brochu et al. 2011)	exact GP	portfolio	unknown landscape, kernel uncertainty	beats best-individual on 28/32 synthetic benchmarks
Spearmint (Snoek et al. 2012)	MCMC GP	EI per sec	ML hyperparameter tuning	14.98 percent CIFAR-10 vs 18 percent hand-tuned
q-EI-SGA (Wang et al. 2020)	exact GP	q-EI	parallel batch, q up to 50	7x speedup at $q = 8$ on ATO simulator
SPGP / FITC (Snelson and Ghahramani 2006)	sparse GP	any	mid-data $N \sim 10^4$	$M = 50$ inducing points reach 95 percent of full GP
VFE (Titsias 2009)	variational GP	any	mid-data, hyperparameter-safe	bound monotone in inducing set
BBMM (GPyTorch) (Gardner et al. 2018)	exact GP via CG	any	large-data $N \sim 10^6$	exact GP on 1M points in 6 min on V100
REMBO (Wang et al. 2016)	low-D GP	EI	low effective dim, $d_{\text{eff}}\!\ll\! D$	3-5x sample efficiency on 69D MIP-tuning
TuRBO (Eriksson et al. 2019)	local GPs	TS	high-D rough, up to $D = 200$	wins on 200D Ackley, beats CMA-ES on 60D Rover
SAASBO (Eriksson and Jankowiak 2021)	NUTS GP horseshoe	EI	high-D sparse, expensive evals	best on 124D Mopta08 and 388D SVM at equal budget
Add-GP (Duvenaud et al. 2011)	additive GP	EI/UCB	low-order interactions	dominates SE on 9 of 11 UCI regression sets
BOCA (Kandasamy et al. 2017)	MF-GP	cost-UCB	continuous fidelity	lower regret per unit cost, NN tuning and supernova LL
DNN-MFBO (Li et al. 2020)	cascaded BNN	MES	discrete fidelity, deep models	60 vs 200 samples on 8D 3-fidelity FEM
Freeze-thaw (Swersky et al. 2014)	curve-kernel GP	per-action ES	training-curve fidelity	3x wall-clock vs Spearmint on PMF/MovieLens-10M
Multi-task GP (Swersky et al. 2013)	ICM joint GP	cost-ES	warm-start from related tasks	10 vs 30 target evals on small-MNIST to MNIST
RGPE (Feurer et al. 2022)	source-GP ensemble	EI	hyperparameter-free transfer	3-5x wall-clock saved across 2086 OpenML tasks
PESC (Hernández-Lobato et al. 2016)	constraint GPs	PESC	active black-box constraints	5x regret gap vs EIC on Hartmann6-C1
SafeOpt (Sui et al. 2015)	exact GP + Lipschitz	max-var	safety-critical online	99.4 percent safe rate on MovieLens-3.5
NASBOT (Kandasamy et al. 2018)	OTMANN-kernel GP	TS	neural architecture search	11.07 percent CIFAR-10 in 200 evals
BOHB (Falkner et al. 2018)	TPE per budget	density-ratio	Hyperband-augmented HPO	2x BO and 1.5x Hyperband on CartPole PPO
LaMBO (Stanton et al. 2022)	latent-space MTGP	NEHVI	discrete biological sequences	40 percent over GA on GFP at 500 rounds
Policy-search BO (Letham and Bakshy 2019)	rank-1 ICM	TS	online + offline policy search	5+50 vs 25+ online evals at Facebook
FBO (Ha et al. 2019)	exact GP	EI + box test	unknown search bounds	40 vs 200+ evals on log-scale SVM hyperparameters

References

Brochu, Eric, Vlad M. Cora, and Nando de Freitas. 2010. A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning. arXiv. https://doi.org/10.48550/arXiv.1012.2599.

Brochu, Eric, Matthew W. Hoffman, and Nando de Freitas. 2011. Portfolio Allocation for Bayesian Optimization. arXiv. https://doi.org/10.48550/arXiv.1009.5419.

Duvenaud, David, Hannes Nickisch, and Carl Edward Rasmussen. 2011. Additive Gaussian Processes. arXiv. https://doi.org/10.48550/arXiv.1112.4394.

Eriksson, David, and Martin Jankowiak. 2021. High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces. arXiv. https://doi.org/10.48550/arXiv.2103.00349.

Eriksson, David, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. 2019. Scalable Global Optimization via Local Bayesian Optimization.

Falkner, Stefan, Aaron Klein, and Frank Hutter. 2018. "BOHB: Robust and Efficient Hyperparameter Optimization at Scale." International Conference on Machine Learning (ICML), July. https://doi.org/10.48550/arXiv.1807.01774.

Feurer, Matthias, Benjamin Letham, Frank Hutter, and Eytan Bakshy. 2022. "Practical Transfer Learning for Bayesian Optimization." Transactions on Machine Learning Research (TMLR), ahead of print, October. https://doi.org/10.48550/arXiv.1802.02219.

Frazier, Peter I. 2018. A Tutorial on Bayesian Optimization. arXiv. https://doi.org/10.48550/arXiv.1807.02811.

Gardner, Jacob R., Geoff Pleiss, David Bindel, Kilian Q. Weinberger, and Andrew Gordon Wilson. 2018. "GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration." Advances in Neural Information Processing Systems (NeurIPS), June. https://doi.org/10.48550/arXiv.1809.11165.

Ha, Huong, Santu Rana, Sunil Gupta, Thanh Nguyen, Hung Tran-The, and Svetha Venkatesh. 2019. Bayesian Optimization with Unknown Search Space. arXiv. https://doi.org/10.48550/arXiv.1910.13092.

Hernández-Lobato, José Miguel, Michael A. Gelbart, Ryan P. Adams, Matthew W. Hoffman, and Zoubin Ghahramani. 2016. "A General Framework for Constrained Bayesian Optimization Using Information-Based Search." Journal of Machine Learning Research (JMLR), ahead of print, September. https://doi.org/10.48550/arXiv.1511.09422.

Hernández-Lobato, José Miguel, Matthew W. Hoffman, and Zoubin Ghahramani. 2014. Predictive Entropy Search for Efficient Global Optimization of Black-Box Functions. arXiv. https://doi.org/10.48550/arXiv.1406.2541.

Jones, Donald R., Matthias Schonlau, and William J. Welch. 1998. "Efficient Global Optimization of Expensive Black-Box Functions." Journal of Global Optimization 13 (4): 455-92. https://doi.org/10.1023/A:1008306431147.

Kandasamy, Kirthevasan, Gautam Dasarathy, Jeff Schneider, and Barnabas Poczos. 2017. "Multi-Fidelity Bayesian Optimisation with Continuous Approximations." International Conference on Machine Learning (ICML), March. https://doi.org/10.48550/arXiv.1703.06240.

Kandasamy, Kirthevasan, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric Xing. 2018. "Neural Architecture Search with Bayesian Optimisation and Optimal Transport." Advances in Neural Information Processing Systems (NeurIPS), March. https://doi.org/10.48550/arXiv.1802.07191.

Letham, Benjamin, and Eytan Bakshy. 2019. "Bayesian Optimization for Policy Search via Online-Oﬄine Experimentation." Annals of Applied Statistics.

Li, Shibo, Wei Xing, Mike Kirby, and Shandian Zhe. 2020. "Multi-Fidelity Bayesian Optimization via Deep Neural Networks." Advances in Neural Information Processing Systems (NeurIPS), December. https://doi.org/10.48550/arXiv.2007.03117.

Matthews, Alexander G. de G., James Hensman, Richard E. Turner, and Zoubin Ghahramani. 2016. "On Sparse Variational Methods and the Kullback-Leibler Divergence Between Stochastic Processes." International Conference on Artificial Intelligence and Statistics (AISTATS), December. https://doi.org/10.48550/arXiv.1504.07027.

Rasmussen, Carl Edward, and Christopher K. I. Williams. 2006. Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning. MIT Press.

Shahriari, Bobak, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. 2016. "Taking the Human Out of the Loop: A Review of Bayesian Optimization." Proceedings of the IEEE 104 (1): 148-75. https://doi.org/10.1109/JPROC.2015.2494218.

Snelson, Edward, and Zoubin Ghahramani. 2006. "Sparse Gaussian Processes Using Pseudo-Inputs." Advances in Neural Information Processing Systems (NeurIPS).

Snoek, Jasper, Hugo Larochelle, and Ryan P. Adams. 2012. Practical Bayesian Optimization of Machine Learning Algorithms. arXiv. https://doi.org/10.48550/arXiv.1206.2944.

Srinivas, Niranjan, Andreas Krause, Sham M. Kakade, and Matthias Seeger. 2012. "Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design." IEEE Transactions on Information Theory 58 (5): 3250-65. https://doi.org/10.1109/TIT.2011.2182033.

Stanton, Samuel, Wesley Maddox, Nate Gruver, et al. 2022. Accelerating Bayesian Optimization for Biological Sequence Design with Denoising Autoencoders. arXiv. https://doi.org/10.48550/arXiv.2203.12742.

Sui, Yanan, Alkis Gotovos, Joel W Burdick, and Andreas Krause. 2015. "Safe Exploration for Optimization with Gaussian Processes." International Conference on Machine Learning (ICML).

Swersky, Kevin, Jasper Snoek, and Ryan P Adams. 2013. "Multi-Task Bayesian Optimization." Advances in Neural Information Processing Systems (NeurIPS).

Swersky, Kevin, Jasper Snoek, and Ryan Prescott Adams. 2014. Freeze-Thaw Bayesian Optimization. arXiv. https://doi.org/10.48550/arXiv.1406.3896.

Titsias, Michalis K. 2009. "Variational Learning of Inducing Variables in Sparse Gaussian Processes." International Conference on Artificial Intelligence and Statistics (AISTATS).

Wang, Jialei, Scott C. Clark, Eric Liu, and Peter I. Frazier. 2020. "Parallel Bayesian Global Optimization of Expensive Functions." Operations Research, ahead of print, May. https://doi.org/10.48550/arXiv.1602.05149.

Wang, Ziyu, Masrour Zoghi, Frank Hutter, David Matheson, and Nando de Freitas. 2016. "Bayesian Optimization in High Dimensions via Random Embeddings." Journal of Artificial Intelligence Research (JAIR).