Bayesian Optimization

Bayesian Optimization (BO) is a sequential model-based strategy for the global optimization of expensive black-box functions, combining a probabilistic surrogate model—typically a Gaussian Process—with an acquisition function that trades off exploration and exploitation to select the next evaluation point. It matters profoundly in modern AI because it underpins automated hyperparameter tuning, neural architecture search, and experimental design, enabling practitioners to find near-optimal configurations with orders of magnitude fewer function evaluations than grid or random search. A remarkable fact: under mild regularity conditions, Bayesian Optimization with GP-UCB achieves sublinear cumulative regret, meaning its average per-step error converges to zero even though the objective function is never explicitly modeled in closed form.

The core insight

The "aha moment" is this: instead of treating optimization as a purely algebraic problem, Bayesian Optimization treats the objective function itself as a random variable with a prior distribution, and every evaluation is a Bayesian update that sharpens our beliefs about where the optimum lies. The surrogate model gives us not just a prediction but a full posterior distribution over function values, encoding uncertainty—and the acquisition function turns that uncertainty into a decision, strategically querying the most informative point next. This is fundamentally different from gradient-based methods: you never need a derivative, only the ability to evaluate f(x) and pay the cost once per query. The power comes from spending cheap model-based computation to avoid expensive real-world evaluations.

Common trapCommon Misconception

The most pervasive mistake is conflating the surrogate model's uncertainty with the optimizer's convergence guarantee—practitioners often stop optimization when the GP posterior variance is uniformly low, concluding "we've learned the function." This is wrong for two reasons: (1) low posterior variance near observed points simply means the GP is confident about interpolation, not that the global optimum has been found—high-variance regions may remain entirely unexplored; and (2) the GP itself is a model with a fixed kernel and hyperparameters that may be misspecified, so low variance can reflect model overconfidence rather than true information. The correct mental model is that posterior variance measures epistemic uncertainty conditional on the kernel choice, not the absolute uncertainty about the true objective; always inspect acquisition function values and ensure sufficient exploration budget before terminating.

How It Works

Bayesian Optimization proceeds by maintaining a surrogate probabilistic model of the objective $f: \mathcal{X} \subseteq \mathbb{R}^d \to \mathbb{R}$ , which is assumed expensive to evaluate (e.g., each call takes minutes to hours). The canonical surrogate is a Gaussian Process.

Gaussian Process Prior. A GP is specified by a mean function $m: \mathcal{X} \to \mathbb{R}$ and a positive-definite kernel $k: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ :

\quad f(\mathbf{x}) \sim \mathcal{GP}\!\left(m(\mathbf{x}),\, k(\mathbf{x}, \mathbf{x}')\right)

Explanation: This asserts that any finite collection of function values is jointly Gaussian, with covariance structure determined entirely by the kernel encoding smoothness and lengthscale assumptions. Given $n$ noisy observations $\mathcal{D}_n = \{(\mathbf{x}_i, y_i)\}_{i=1}^n$ where $y_i = f(\mathbf{x}_i) + \varepsilon_i$ , $\varepsilon_i \sim \mathcal{N}(0, \sigma_n^2)$ , the GP posterior at a new point $\mathbf{x}_*$ is Gaussian with analytically tractable moments:

\quad \mu_n(\mathbf{x}_*) = m(\mathbf{x}_*) + \mathbf{k}_*^\top (\mathbf{K} + \sigma_n^2 \mathbf{I})^{-1}(\mathbf{y} - \mathbf{m})

Explanation: The posterior mean is the prior mean corrected by a weighted sum of residuals, where the weights are determined by how correlated the new point is to all observed points through the kernel matrix $\mathbf{K}$ . Here $\mathbf{K}_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)$ , $\mathbf{k}_* = [k(\mathbf{x}_*, \mathbf{x}_1), \ldots, k(\mathbf{x}_*, \mathbf{x}_n)]^\top$ , and $\mathbf{m} = [m(\mathbf{x}_1), \ldots, m(\mathbf{x}_n)]^\top$ . The posterior variance is:

\quad \sigma_n^2(\mathbf{x}_*) = k(\mathbf{x}_*, \mathbf{x}_*) - \mathbf{k}_*^\top(\mathbf{K} + \sigma_n^2 \mathbf{I})^{-1}\mathbf{k}_*

Explanation: Posterior variance equals prior variance minus the reduction in uncertainty attributable to the observed data, and is zero at observed points when noise is absent.

Acquisition Functions. The acquisition function $\alpha: \mathcal{X} \to \mathbb{R}$ is maximized (cheaply) to select the next query point $\mathbf{x}_{n+1} = \arg\max_{\mathbf{x}} \alpha(\mathbf{x})$ . Three canonical choices are:

Expected Improvement (EI), the most widely used:

\quad \alpha_{\mathrm{EI}}(\mathbf{x}) = \mathbb{E}\!\left[\max(f(\mathbf{x}) - f^+, 0)\right] = (\mu_n(\mathbf{x}) - f^+)\,\Phi(Z) + \sigma_n(\mathbf{x})\,\phi(Z)

Explanation: EI computes the expected amount by which a query at $\mathbf{x}$ would exceed the current best observed value $f^+ = \max_i y_i$ , where $Z = (\mu_n(\mathbf{x}) - f^+)/\sigma_n(\mathbf{x})$ and $\Phi, \phi$ are the standard normal CDF and PDF respectively.

GP-UCB (Upper Confidence Bound):

\quad \alpha_{\mathrm{UCB}}(\mathbf{x};\, \beta_t) = \mu_{t-1}(\mathbf{x}) + \sqrt{\beta_t}\;\sigma_{t-1}(\mathbf{x})

Explanation: UCB explicitly constructs an optimistic upper bound on the function value, where $\beta_t$ is a confidence parameter that grows with $t$ to ensure sufficient exploration; Srinivas et al. (2010) derive $\beta_t = 2\log(|\mathcal{X}| t^2 \pi^2 / 6\delta)$ to guarantee $1-\delta$ probability regret bounds.

Regret and Convergence. The cumulative regret after $T$ evaluations is $R_T = \sum_{t=1}^T [f(\mathbf{x}^*) - f(\mathbf{x}_t)]$ . Srinivas et al. (2010) establish that for a GP with squared-exponential kernel, GP-UCB achieves:

\quad \Pr\!\left(R_T = \mathcal{O}\!\left(\sqrt{T \gamma_T \log T}\right)\right) \geq 1 - \delta

Explanation: Here $\gamma_T$ is the maximum information gain after $T$ observations, which grows as $\mathcal{O}((\log T)^{d+1})$ for SE kernels—meaning $R_T/T \to 0$ and the algorithm is asymptotically no-regret.

Kernel Hyperparameter Learning. Kernel hyperparameters $\boldsymbol{\theta}$ (e.g., lengthscale $\ell$ , output scale $\sigma_f^2$ ) are typically fit by maximizing the log marginal likelihood:

\quad \log p(\mathbf{y} \mid \mathbf{X}, \boldsymbol{\theta}) = -\tfrac{1}{2}\mathbf{y}^\top \mathbf{C}^{-1}\mathbf{y} - \tfrac{1}{2}\log|\mathbf{C}| - \tfrac{n}{2}\log 2\pi

Explanation: This objective, where $\mathbf{C} = \mathbf{K}_{\boldsymbol{\theta}} + \sigma_n^2 \mathbf{I}$ , balances data fit (first term) against model complexity (second term, the Occam factor), and its gradients are analytically available, enabling efficient optimization via L-BFGS.

researcher · Harold Jeffrey Kushner | b. 1933 | Introduced stochastic approximation and early BO via the "P-algorithm"

Kushner was a control theorist and probabilist at Brown University whose work on stochastic differential equations led him to formulate one of the earliest probabilistic approaches to global optimization. In his 1964 paper "A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise", he proposed using a Wiener process prior and selecting the next evaluation point to maximize the probability of improvement—establishing the probabilistic acquisition function paradigm that BO inherits directly. Remarkably, Kushner's paper predates the term "Bayesian Optimization" by decades and was largely ignored by the machine learning community until the GP-BO renaissance of the 2000s.

researcher · Jonas Mockus | b. 1938 | Formalized Bayesian global optimization and the Expected Improvement criterion

Jonas Mockus, a Lithuanian mathematician working at the Institute of Mathematics and Informatics in Vilnius, developed what he called the "Bayesian approach to global optimization" throughout the 1970s, culminating in his 1989 monograph Bayesian Approach to Global Optimization. He rigorously formalized the notion of Expected Improvement as the optimal one-step-look-ahead acquisition function under a Bayesian decision-theoretic framework, proved existence and consistency results, and introduced the concept of the "efficient global optimization" loop that remains essentially unchanged today. A surprising historical note: Mockus worked largely in isolation behind the Iron Curtain, and his foundational contributions were rediscovered and popularized in the West through Jones, Schonlau & Welch's 1998 EGO paper, which cited him but introduced the ideas to an entirely new community.

researcher · Carl Edward Rasmussen | b. 1966 | Co-authored the definitive GP textbook and GPML software underpinning modern BO

Carl Rasmussen is a Danish machine learning researcher at the University of Cambridge whose co-authored textbook Gaussian Processes for Machine Learning (2006, with Christopher Williams) became the canonical reference for the GP machinery that powers virtually all modern Bayesian Optimization implementations. His GPML MATLAB toolbox operationalized GP inference and marginal likelihood optimization, directly enabling the wave of BO research in the late 2000s and 2010s. Rasmussen also made foundational contributions to automatic kernel discovery and model selection using GPs, which directly address the kernel misspecification problem that remains a central challenge in BO.

Figure

Bayesian Optimization Loop: Surrogate, Acquisition, and Sequential Query

Figure

Exploration-Exploitation Trade-off in Acquisition Functions

Intuition

The Mental Model

Imagine you are a gold prospector in an unmapped territory, and drilling a test well costs $50,000. You would not drill randomly—you'd use geology (your prior), the results of previous wells (your observations), and a strategy: drill where the rock looks promising and where you haven't looked yet. Bayesian Optimization is precisely this: the Gaussian Process is the geologist's model of subsurface gold concentration, updated every time a new well is drilled. The acquisition function is the prospector's decision rule: "I'll drill next at the place where I expect the highest amount of gold I haven't already found"—which forces you to visit uncertain regions when you're unsure, and to confirm strong signals when confidence is high. The crucial intuition for the posterior variance is this: think of a rubber sheet stretched tightly over the observed data points. Between known points, the sheet bows upward—that bowing is posterior uncertainty. The acquisition function sends you to places where the sheet bows highest and where the sheet's average height (the mean) is already elevated. When you drill a new well and observe the result, you anchor the sheet at that point—variance collapses to zero there—and the rest of the sheet re-adjusts. The whole game is anchoring the sheet in the right places with as few anchors as possible.

Historical Development

Origins · 1 minhow this was discovered

History

1964

Kushner introduces the "P-algorithm" using a Wiener process prior and probability of improvement criterion—the first probabilistic framework for sequential black-box optimization (Journal of Basic Engineering, ASME).

1978

Jonas Mockus, Tiešis & Žilinskas formalize the Bayesian approach to global optimization and introduce Expected Improvement as the optimal one-step Bayes-optimal decision under a Gaussian process prior (Towards Global Optimization 2, Springer).

1989

Mockus publishes his monograph Bayesian Approach to Global Optimization, providing the first book-length treatment including existence theorems, consistency results, and connections to decision theory.

1998

Jones, Schonlau & Welch publish "Efficient Global Optimization of Expensive Black-Box Functions" (Journal of Global Optimization), introducing the EGO algorithm and re-introducing EI to the engineering and statistics communities with compelling benchmark results—the paper that launched the modern BO era.

2006

Rasmussen & Williams publish Gaussian Processes for Machine Learning (MIT Press), codifying GP inference, kernel selection, and marginal likelihood optimization; the companion GPML toolbox enables reproducible BO research.

2010

Srinivas, Krause, Kakade & Seeger prove sublinear regret bounds for GP-UCB (Proceedings of ICML), providing the first rigorous theoretical framework connecting BO to the bandit literature with information-theoretic guarantees.

2012

Snoek, Larochelle & Adams publish "Practical Bayesian Optimization of Machine Learning Algorithms" (NeurIPS), demonstrating BO can reliably tune deep learning hyperparameters better than expert humans; the Spearmint software package follows.

2015

Hernández-Lobato, Hoffman & Ghahramani introduce Predictive Entropy Search, a fully information-theoretic acquisition function maximizing reduction in entropy of the location of the global optimum (NeurIPS), unifying exploration-exploitation under mutual information.

2020

Eriksson et al. publish TuRBO (NeurIPS), showing that local trust-region BO dramatically outperforms global BO in high-dimensional problems (

d > 20

) by maintaining multiple local models—directly addressing the