3. Bayesian optimization foundations

Bayesian optimization (BO) is the workhorse for optimizing expensive black-box objectives — a simulator run, a hardware experiment, a training pipeline — where each evaluation costs minutes to days and gradients are unavailable. The core idea is to place a probabilistic surrogate model over the objective, then use an acquisition function to decide where to sample next. This chapter builds the three pillars: Gaussian process (GP) surrogates, acquisition functions, and the exploration–exploitation trade-off that ties them together. In multi-objective settings these same pillars reappear, so getting them right here pays off directly in later chapters.

Gaussian processes as surrogate models

A Gaussian process defines a distribution over functions. Any finite set of input points X = {x₁, …, xₙ} yields function values f = (f(x₁), …, f(xₙ)) that are jointly Gaussian:

f ~ N(m(X), K(X, X))
K_ij = k(x_i, x_j) = σ_f² · exp(-‖x_i - x_j‖² / (2ℓ²))   # squared-exponential kernel

The mean function m(x) encodes prior belief (often zero after standardization). The kernel k encodes smoothness and length-scale ℓ; the signal variance σ_f² sets the vertical scale. Given observations y = f(X) + ε with noise variance σ_n², the posterior predictive at a new point x* is Gaussian with closed-form mean and variance:

μ(x*) = m(x*) + k(x*, X) [K(X, X) + σ_n² I]⁻¹ (y - m(X))
σ²(x*) = k(x*, x*) - k(x*, X) [K(X, X) + σ_n² I]⁻¹ k(X, x*)

Two properties matter operationally. First, the posterior mean interpolates observed points (up to noise) and reverts to the prior mean far from data. Second, the posterior variance grows with distance from observations — this is the model's own statement of uncertainty, and it is exactly what acquisition functions exploit. In practice, hyperparameters ℓ, σ_f², σ_n² are fit by maximizing the log marginal likelihood, typically with L-BFGS from a few random restarts. A poorly fit length-scale is the most common failure: too short and the model overfits noise; too long and it flattens real structure.

Acquisition functions

An acquisition function α(x) scores candidate points using only the posterior μ(x) and σ(x). It is cheap to evaluate, so we can optimize it densely (e.g., random sampling plus local refinement) to pick the next query. Three families dominate:

• Probability of Improvement (PI): α_PI(x) = Φ((μ(x) - f⁺ - ξ) / σ(x)), where f⁺ is the best observed value and ξ ≥ 0 is a margin. Simple, but tends to be overly greedy.
• Expected Improvement (EI): α_EI(x) = (μ(x) - f⁺ - ξ) Φ(z) + σ(x) φ(z), with z = (μ(x) - f⁺ - ξ)/σ(x). EI balances the size of improvement against the probability of achieving it and is the default in most BO libraries.
• Upper Confidence Bound (UCB): α_UCB(x) = μ(x) + κ σ(x). A single scalar κ directly tunes optimism; larger κ explores more.

For minimization, flip the sign of μ or use the lower confidence bound. In multi-objective BO, EI generalizes to Expected Hypervolume Improvement (EHVI), which we cover later; the underlying logic — integrate improvement over the posterior — is identical.

The exploration–exploitation trade-off

Every acquisition function is a policy for trading off two urges. Exploitation samples where μ(x) is high, refining a promising region. Exploration samples where σ(x) is high, reducing uncertainty that might hide a better optimum. The trade-off is not a one-time choice but a schedule: early in the run, data is sparse and uncertainty dominates, so exploration is cheap and valuable; later, the posterior tightens and exploitation should dominate.

UCB makes this explicit through κ. A common practical schedule is to start with κ ≈ 2–3 and decay toward κ ≈ 0.5–1 as the budget depletes. EI and PI encode the trade-off implicitly through σ(x) in their formulas, but the margin ξ plays a similar role: larger ξ biases toward exploration. The figure below shows how the posterior mean, uncertainty band, and EI surface co-evolve as observations accumulate.

A reproducible worked example

Consider a one-dimensional synthetic objective f(x) = sin(3x) + 0.3x² on x ∈ [-2, 3], treated as a black box with Gaussian noise σ_n = 0.05. We minimize it with EI over a budget of 10 evaluations, starting from 3 random points. The procedure is:

1. Standardize inputs and outputs; fit a GP with a squared-exponential kernel by maximizing log marginal likelihood.
2. Compute μ(x) and σ(x) on a dense grid of 500 candidate points.
3. Evaluate α_EI(x) on the grid; select x⁺ = argmax α_EI.
4. Query the black box at x⁺, append the noisy observation, refit, and repeat.

With a fixed random seed, a typical run converges to x* ≈ -1.4 within 7–8 evaluations, with the last two queries landing within 0.05 of the optimum. If instead the run stalls — successive queries cluster in one region and the best value stops improving — the usual causes are: (a) the length-scale collapsed too short, so σ(x) is near zero everywhere and EI has no gradient; (b) the noise variance was underestimated, causing the GP to interpolate noise and over-exploit; or (c) the EI margin ξ is too small, making the policy greedy. Diagnose by plotting σ(x) across the domain: if it is uniformly small after only a few points, refit hyperparameters with a prior on ℓ or add jitter to the kernel matrix.

Practical checklist for a BO loop

These three pillars — a calibrated GP posterior, an acquisition function that integrates improvement over that posterior, and an explicit or implicit exploration schedule — form the engine that later chapters extend to multiple objectives and to trust-aware deployment constraints. The key engineering discipline is to keep the surrogate honest (fit hyperparameters, standardize, watch σ) and to keep the acquisition policy from collapsing into greedy resampling.