Bayesian Optimization

Why it exists (motivation before formulas)

Many real optimization problems don’t match the assumptions that make classical optimization fast:

• •f(x) is expensive: each evaluation could be minutes to days.
• •f(x) is derivative-free: you can’t compute ∇f, and finite differences are too costly.
• •f(x) is nonconvex: local methods can get stuck.
• •f(x) can be noisy: repeated evaluations differ.

If each evaluation is precious, the core question becomes:

Which x should I evaluate next to learn the most about where the optimum might be?

Bayesian optimization answers this using probability: it represents uncertainty about f and uses that uncertainty to guide where to sample.

Definition (what it is)

Let f(x) be an unknown objective you want to minimize or maximize over a domain 𝒳 ⊂ ℝᵈ.

Bayesian optimization is a sequential decision procedure that:

1. 1)Maintains a probabilistic surrogate model for f.
2. 2)Uses the surrogate’s predictive distribution at each x to compute an acquisition function a(x).
3. 3)Selects the next evaluation point by optimizing the acquisition:

xₙ₊₁ ∈ argmaxₓ∈𝒳 a(x)

4. 4)Evaluates the real objective (expensive): yₙ₊₁ = f(xₙ₊₁) (possibly with noise)
5. 5)Updates the surrogate with the new data and repeats.

The surrogate gives, at any x:

• •Predictive mean μ(x) (what we think f(x) is)
• •Predictive variance σ²(x) (how uncertain we are)

This pair (μ, σ²) is the “sufficient interface” most BO algorithms need.

Key intuition: exploration vs exploitation

If you only chase the best current μ(x), you might get stuck exploiting a wrong region.

If you only chase high σ(x), you waste evaluations in uncertain but unpromising regions.

Acquisition functions formalize a trade-off:

• •Exploitation: favor x with good predicted objective value.
• •Exploration: favor x where uncertainty is high and you could discover better outcomes.

What BO is not

It’s not “Bayesian” in the sense that your final answer must be a full posterior over the optimum; often we just want a good x after few evaluations.

It’s not restricted to Gaussian processes (GPs), though GPs are the canonical choice.

It’s not guaranteed to find the global optimum in finite time—but it is often extremely effective when evaluations are expensive.

A minimal mathematical statement

Assume we have data 𝒟ₙ = {(xᵢ, yᵢ)}ᵢ₌₁ⁿ.

A surrogate produces a predictive distribution for f(x) given 𝒟ₙ.

We summarize that as:

f(x) | 𝒟ₙ ≈ 𝒩( μₙ(x), σ²ₙ(x) )

Then a common pattern is:

aₙ(x) = Acquisition( μₙ(x), σₙ(x) )

and choose xₙ₊₁ maximizing aₙ.

This single loop—model → acquisition → evaluate → update—is the heart of Bayesian optimization.

Why surrogates matter

If evaluations are expensive, you want to extract maximum value from each one. A surrogate is a cheaper function you can evaluate anywhere, with uncertainty that reflects limited data.

A good surrogate should:

• •Fit observed data well
• •Generalize smoothly (if appropriate)
• •Provide calibrated uncertainty: σ²(x) large where you haven’t learned, small near data

That uncertainty is what enables principled exploration.

The canonical surrogate: Gaussian Processes (GPs)

A GP is a distribution over functions. Informally:

f(·) ∼ GP(m(·), k(·, ·))

• •m(x) is the prior mean (often 0)
• •k(x, x′) is the kernel (covariance) controlling smoothness and correlation

If observations are noisy:

yᵢ = f(xᵢ) + εᵢ, εᵢ ∼ 𝒩(0, σ²_noise)

Given data, the GP posterior at a test point x is Gaussian:

f(x) | 𝒟ₙ ∼ 𝒩( μₙ(x), σ²ₙ(x) )

The GP posterior (showing the key structure)

Let X ∈ ℝⁿˣᵈ be the matrix of inputs, y ∈ ℝⁿ be outputs, and define:

• •K = k(X, X) ∈ ℝⁿˣⁿ with Kᵢⱼ = k(xᵢ, xⱼ)
• •k(x) = k(X, x) ∈ ℝⁿ with kᵢ(x) = k(xᵢ, x)

With Gaussian noise, the effective covariance is K + σ²_noise I.

Then:

μₙ(x) = m(x) + k(x)ᵀ ( K + σ²_noise I )⁻¹ ( y − m(X) )

σ²ₙ(x) = k(x, x) − k(x)ᵀ ( K + σ²_noise I )⁻¹ k(x)

What these formulas are saying (intuition)

• •μₙ(x) is a weighted combination of observed values, where weights depend on similarity via the kernel.
• •σ²ₙ(x) is prior variance minus explained variance. It shrinks near observed points.

A useful mental model:

• •If x is near many data points, k(x) is large in magnitude, and uncertainty shrinks.
• •If x is far from data, k(x) is near 0, and σ²ₙ(x) ≈ k(x, x): you revert to prior uncertainty.

Kernel choice and hyperparameters

The kernel encodes your belief about f.

Common kernels:

Hyperparameters (lengthscales, variance, noise) are often learned by maximizing marginal likelihood.

Beyond GPs (when and why)

GPs scale as 𝒪(n³) with n evaluations due to matrix inversion (though there are approximations). In high d or with many evaluations, you might use:

BO doesn’t require GPs; it requires predictive distributions (or at least μ and σ).

The role of noise

Many objectives are noisy: y = f(x) + ε.

Noise affects:

• •How aggressively σ shrinks at data points
• •Whether repeated sampling at the same x is valuable

With high noise, the surrogate remains uncertain even near observed x, which can lead the acquisition to re-sample.

A geometric interpretation (uncertainty as distance)

For stationary kernels (like RBF/Matérn), correlation decays with distance. So σ(x) tends to increase as x moves away from observed points.

This gives you a helpful picture:

• •μ(x) is “interpolating/extrapolating” values.
• •σ(x) is “how far you are from what you know,” adjusted by kernel geometry.

This is precisely what BO needs: a map of promising regions and unknown regions.

Why an acquisition function is needed

Even with a perfect surrogate posterior, you still need a rule to decide the next experiment.

We want a(x) to be:

• •Cheap to evaluate (compared to f)
• •High where sampling is expected to help
• •Able to balance exploration/exploitation

The acquisition is a utility function computed from the predictive distribution at x.

Assume for simplicity (common in GPs):

f(x) | 𝒟ₙ ∼ 𝒩( μ(x), σ²(x) )

(We’ll omit subscript n for readability.)

Expected Improvement (EI)

Idea

If you are minimizing f, define the best observed value so far:

f_best = minᵢ yᵢ

Improvement at x is:

I(x) = max(0, f_best − f(x))

Because f(x) is random under the surrogate, I(x) is random. EI takes its expectation:

EI(x) = 𝔼[ I(x) ]

Closed form under Gaussian predictive distributions

Let Z = (f_best − μ(x)) / σ(x) (for σ(x) > 0).

Let φ and Φ be the standard normal PDF and CDF.

Then:

EI(x) = (f_best − μ(x)) Φ(Z) + σ(x) φ(Z)

Interpreting the two terms

• •(f_best − μ) Φ(Z) is the exploitation component: large when μ is better than f_best.
• •σ φ(Z) is the exploration component: large when uncertainty σ is high.

If σ → 0, EI tends to max(0, f_best − μ): pure exploitation.

Practical notes

• •EI can become numerically tricky when σ is tiny.
• •With observation noise, “best observed” can be misleading; variants use best posterior mean.

Probability of Improvement (PI)

Idea

Prefer x where f(x) beats f_best with high probability:

PI(x) = 𝔼[ 1{ f(x) ≤ f_best − ξ } ]

(For minimization; ξ ≥ 0 is a margin encouraging exploration.)

With Gaussian predictive distribution:

PI(x) = Φ( (f_best − ξ − μ(x)) / σ(x) )

PI is simple but can over-exploit: it ignores how much improvement you get.

Upper/Lower Confidence Bound (UCB/LCB)

Idea

Construct an optimistic bound using uncertainty.

For maximization:

UCB(x) = μ(x) + κ σ(x)

For minimization (lower confidence bound):

LCB(x) = μ(x) − κ σ(x)

Choose x that maximizes UCB (or minimizes LCB). κ controls exploration:

• •Larger κ → more exploration
• •Smaller κ → more exploitation

Why this is attractive

• •Very simple
• •Often strong theoretical guarantees (GP-UCB under assumptions)
• •Works naturally with batch variants and constraints

Thompson Sampling (TS)

Idea

Instead of building a deterministic a(x), sample a function from the posterior and optimize it.

1. 1)Sample f̃(·) ∼ posterior
2. 2)Pick xₙ₊₁ ∈ argminₓ f̃(x)

This naturally balances exploration and exploitation through posterior randomness.

Comparing acquisitions (when to use what)

Acquisition optimization is its own optimization problem

Key subtlety: the acquisition a(x) is nonconvex even if the surrogate is smooth.

So BO typically nests two optimizations:

• •Outer: optimize f via sequential evaluations
• •Inner: optimize a(x) cheaply but carefully

Common inner-loop strategies:

• •Multi-start gradient-based optimization (if a is differentiable)
• •Random search + local refinement
• •Evolutionary methods (CMA-ES) when a is rugged or constraints are complex

Because evaluating a(x) is cheap, you can afford many restarts.

Constraints and feasibility

Sometimes you optimize f(x) subject to constraints cⱼ(x) ≤ 0.

A common idea: model constraints with surrogates too, and modify acquisition:

• •Multiply by probability of feasibility:

a_constrained(x) = a(x) · P(feasible | x)

This encourages points that are both promising and likely feasible.

Summary of the acquisition role

Surrogates provide beliefs (μ, σ²). Acquisition functions convert beliefs into actions (which x to try next). The “Bayesian” part is not just uncertainty estimation—it’s decision-making under uncertainty.

Why the closed loop matters

Bayesian optimization is fundamentally adaptive experimentation.

A non-adaptive baseline would pre-select a grid or random set of points and evaluate all of them. BO instead uses each new y to redirect future evaluations. This adaptivity is what yields sample efficiency.

The standard BO loop (step-by-step)

We’ll write it for minimization.

0) Define the problem

• •Domain 𝒳 ⊂ ℝᵈ (box constraints, manifolds, or mixed spaces)
• •Evaluation budget N (max number of expensive calls)
• •Optional noise model and constraints

1) Initialization (space-filling)

Choose n₀ initial points, often via:

• •Latin hypercube sampling
• •Sobol sequences
• •Random uniform

You want broad coverage so early uncertainty is meaningful.

2) Fit/update surrogate

Given 𝒟ₙ, fit GP hyperparameters (or update posterior).

Compute μₙ(x), σ²ₙ(x) as needed.

3) Choose acquisition aₙ(x)

Common defaults:

• •EI for many continuous problems
• •LCB/UCB when you want a stable knob κ

4) Optimize acquisition (inner problem)

Compute:

xₙ₊₁ ∈ argmaxₓ aₙ(x)

In practice, you approximate this argmax with multi-start optimization.

5) Evaluate the true objective

Observe yₙ₊₁ = f(xₙ₊₁) + ε.

Update 𝒟ₙ₊₁ = 𝒟ₙ ∪ {(xₙ₊₁, yₙ₊₁)}.

6) Stop

Stop when budget is exhausted or improvement saturates.

Return:

x* = argmin_{(xᵢ, yᵢ) ∈ 𝒟} yᵢ

or return argmin μₙ(x) if you prefer posterior mean minimizer.

Practical choices that strongly affect results

1) Input scaling and warping

BO is sensitive to geometry. If one coordinate spans [0, 10⁶] and another [0, 1], kernels can behave poorly.

Standard practice:

• •Normalize each dimension to [0, 1]
• •Consider log transforms for positive scale parameters

2) Handling categorical and conditional parameters

Hyperparameter tuning often has:

• •categorical choices (optimizer ∈ {SGD, Adam})
• •conditional parameters (momentum only if SGD)

GPs struggle with pure categorical spaces unless encoded carefully.

Alternatives:

• •Tree-structured Parzen estimator (TPE)
• •Random-forest surrogates
• •One-hot with specialized kernels (works sometimes)

3) Batch Bayesian optimization (parallel evaluations)

If you can evaluate B points in parallel, you want {x₁,…,x_B}.

Approaches:

• •q-EI (joint expected improvement)
• •Thompson sampling draws multiple posterior samples
• •Greedy with “fantasy” observations (update surrogate with predicted outcomes)

Batch BO is harder because points should be diverse, not redundant.

4) High-dimensional BO

BO with standard GPs can degrade when d is large (say d ≥ 20–50).

Reasons:

• •Distances concentrate; kernels become less informative
• •Acquisition optimization becomes harder

Common mitigations:

5) Multi-fidelity and cost-aware BO

Sometimes you can evaluate cheaper approximations:

• •fewer training epochs
• •smaller dataset
• •lower-resolution simulation

Multi-fidelity BO models f(x, s) where s is fidelity (cost). The acquisition trades off information vs cost.

6) Connections to Bayesian inference and decision theory

You already know Bayesian inference: prior → posterior.

BO adds an action layer:

posterior → decision rule (acquisition) → new data → posterior

This is a small instance of Bayesian experimental design.

When BO is a good fit

Use BO when:

• •evaluations are expensive (≲ 10³ evaluations)
• •derivatives are not available
• •dimension is moderate or structure exists

Avoid or rethink BO when:

• •evaluations are cheap (use gradient-based or evolutionary methods)
• •dimension is huge with no structure
• •objective is extremely noisy and nonstationary without modeling that noise

A mental model to keep

Think of BO as building a “map” of f:

• •μ(x) is the current best guess of the landscape.
• •σ(x) is the fog-of-war.
• •The acquisition decides where to scout next.

With that model, most design decisions become: how should the fog behave, and what scouting strategy do you want?