Bayesian Optimization, Step by Step

Prelude

The expensive-function problem

Tuning hyperparameters of a model that takes 8 hours to train. Picking the next concentration in a wet-lab experiment. Choosing where to deploy the next air-quality sensor. The function $f$ you're optimising is expensive, black-box, and possibly noisy. Random search burns a lot of calls; grid search burns even more. You want every evaluation to tell you the most.

The slogan. Fit a cheap surrogate to your observations; use it to predict with uncertainty; query the next point where the predicted-improvement is largest. Repeat.

Step 1

The two ingredients

Surrogate. A Gaussian process gives, at every point $x$, a posterior mean $\mu(x)$ and standard deviation $\sigma(x)$. Where $\sigma$ is large, we don't yet know $f$. Where $\sigma$ is small, the surrogate is confident. This is the same posterior story as the Bayesian linear regression in the Bayes posterior playground, with an RBF kernel instead of an explicit feature basis.
Acquisition function. A scalar score $a(x)$ on top of $(\mu, \sigma)$ that says "how worth evaluating is this $x$ next?". Different acquisition functions trade exploration vs exploitation differently.

Where $\Phi$ and $\phi$ are the standard normal CDF and PDF, and $z = (\mu(x) - f^* - \xi) / \sigma(x)$ for the current best $f^*$. UCB picks the upper-confidence bound; PI picks the probability of any improvement; EI picks the expected improvement (often the default).

Step 2

Run it

A hidden function (you'll see the true curve only after acquiring points). Press Acquire next to evaluate $f$ at $\arg\max a(x)$. The GP mean and 2σ band update; the acquisition function below reshapes; the convergence plot keeps score across all four acquisition strategies on the same hidden function.

active acquisition hidden function queries = 3 best-so-far = —

GP surrogate (μ ± 2σ) over hidden f

Acquisition function a(x)

Best-so-far convergence (4 strategies)

What to watch for. Early on, EI and UCB explore widely (the band is fat everywhere). After ~5 acquisitions they zoom into the best neighbourhood. PI gets stuck more often (it finds a near-optimum and stops exploring). Thompson sampling is a surprisingly strong baseline that's almost trivial to implement: draw a sample from the posterior and pick its arg-max.

Step 3

Why Bayesian optimisation, not grid search

Sample efficiency. BO finds the optimum of typical hyperparameter tasks in 20-50 evaluations where grid search needs 200-1000. The breakeven point in cost is around evaluation cost > 30 seconds.
Honest uncertainty. You get not just the optimum, but a posterior over all values of $f$. Useful when you want to know "would 5% better at another point also be acceptable?".
Constraints come for free. If evaluations have a constraint that some are infeasible, you can use a separate GP to model the constraint probability and multiply the acquisition by it.
Multi-fidelity extensions. When you have cheap-but-noisy and expensive-but-accurate evaluations (e.g., short vs full training run), BO can mix them automatically.

Step 4

The traps in real BO

Kernel choice matters. RBF is smooth; Matérn is rougher; periodic captures cycles. Pick a kernel that matches your function's actual structure or BO will burn evaluations on artefacts of the wrong kernel.
High dimensions hurt. Pure GP-BO becomes unreliable above ~20 dimensions. TuRBO, BoTorch, and embedding-based BO push the ceiling, but it's still hard.
Categorical hyperparameters. Need a kernel over categorical / integer dimensions; SMAC and tree-structured Parzen estimators handle this better than vanilla GPs.
Noise modelling. Stochastic objectives (training loss with random init) need a noise term in the GP. Otherwise the surrogate over-fits to a noisy point and BO chases it.
Acquisition-function maximisation. Inside BO you maximise $a(x)$. If $a$ is non-convex (it usually is), use multi-start optimisation; otherwise you'll land in a local optimum of the acquisition.

Step 5

Where Bayesian optimisation is the right tool

Hyperparameter tuning of expensive models. Anything that takes > 30 minutes to train per config. Use BoTorch / Ax / Optuna's TPE.
Sensor / experiment placement under uncertainty. Maximise expected reduction in posterior variance over a field model.
Wet-lab / hardware experimental design. Each experiment is a real-time evaluation. BO chooses the next concentration / temperature / dose.
Molecule and materials discovery. BO over a learned latent space of chemistry / crystals. The 2024 frontier — BOLT, ChemBO, AlphaFold-Design pipelines all use a BO loop on top of a learned surrogate.
Active learning on a budget. Pick the next batch of points that maximises expected information gain — the BO-active-learning hybrid called BALD or BOSS.

Final takeaway. Bayesian optimisation is the go-to whenever a single evaluation is expensive enough to make you think twice. It asks a simple question every step — "what's the most informative thing I could try next?" — and answers it using the same posterior machinery from the Bayesian playground article.

Step 6

Acquisition function deep dive

The four most-used acquisitions, with their closed forms and trade-offs:

Expected Improvement (EI). Closed-form (above), no hyperparameters, balanced exploration. The default when the surrogate is a GP; greedy-exploit early in the run, more exploratory once the best point has plateaued.
Upper Confidence Bound (UCB). $\mu(x) + \beta \sigma(x)$. One knob ($\beta$) controls exploitation vs exploration. Provably has $O(\sqrt{T \gamma_T})$ regret (Srinivas et al., 2010). Use when you want deterministic, knob-tunable behaviour.
Probability of Improvement (PI). $\Pr(f(x) > f^* + \xi)$. Easy to compute but greedy; tends to under-explore. Mostly historical interest.
Thompson Sampling. Draw $f \sim p(f|D)$ once, optimise it, evaluate. Naturally parallelisable (each parallel worker draws its own sample). Strong in batched / asynchronous settings.
Knowledge Gradient. Expected one-step lookahead value of the posterior. Expensive but optimal for the one-step Bayesian objective; the modern frontier in BoTorch.

Step 7

Batch and async BO

Real BO loops rarely evaluate one point at a time — you have $B$ parallel workers (GPUs, lab benches, simulator instances). Batch BO picks $B$ points per round.

q-Expected Improvement (qEI). Joint EI over $B$ points; intractable in closed form; computed by Monte Carlo via sampling from the GP posterior (Wilson et al., 2018). Default in BoTorch.
Hallucinated batches (Kriging Believer). Pick the first point greedily; pretend you observed $\mu(x)$; refit; pick the next; repeat. Cheap but suboptimal.
Thompson sampling. Each parallel worker draws its own sample. Trivially parallelisable; provably good regret.
Asynchronous BO. When workers return at different times, you can't pause; instead, condition on pending points (their posterior mean is your best guess of their unknown outcome).

Step 8

Reading list

Shahriari, Swersky, Wang, Adams, de Freitas (2016) — Taking the Human out of the Loop: A Review of Bayesian Optimization. Standard survey.
Snoek, Larochelle, Adams (2012) — Practical Bayesian Optimization of Machine Learning Algorithms.
Srinivas, Krause, Kakade, Seeger (2010) — Gaussian Process Optimization in the Bandit Setting. The UCB-regret paper.
Frazier (2018) — A Tutorial on Bayesian Optimization.
Eriksson et al. (2019) — TuRBO: Scalable Global Optimization via Local Bayesian Optimization. The high-dimensional-BO trust-region trick.
Garnett (2023) — Bayesian Optimization textbook. Free draft online; the definitive modern reference.
BoTorch / Ax — the standard modern libraries. Optuna's TPE for cheap categorical search.