Algorithm 40 · Phase 8 · Advanced

Bayesian Optimization

Finding the best input when every guess is expensive
Bayesian Optimization chalkboard infographic: Gaussian Process posterior, acquisition function, exploration vs exploitation
Visual style: chalkboard · generated with gpt-image-2

◆Core Concept

You have a function you can only poke, not read. Each poke costs real money — a 9-hour training run, a wet-lab experiment, a wind-tunnel test. You get no gradient, just a noisy number back. Bayesian Optimization answers: where do I poke next? It builds a cheap probabilistic model of the expensive function, then optimizes that model instead — asking not "where is the best value?" but "where is the best bet?"

Grid search asks every question. Random search asks arbitrary questions. Bayesian Optimization asks the most informative next question — and typically finds a good optimum in tens of evaluations where random search needs thousands.

x* = argmaxx f(x)  subject to: f is black-box, expensive, no gradients, possibly noisy Two moving parts: a surrogate (belief about f) and an acquisition function (how to act on that belief).

▣Key Components

1 · Surrogate Model

Usually a Gaussian Process. Gives a posterior mean μ(x) — the best guess — plus a standard deviation σ(x) that widens where you haven't looked. The uncertainty is the whole point.

2 · Acquisition Function

Turns (μ, σ) into a single "worth trying" score. Cheap to evaluate, so you can optimize it hard with gradients or random restarts. Its argmax is your next experiment.

3 · Explore / Exploit Dial

Chase low μ (exploit what looks good) or high σ (explore what's unknown). The acquisition function encodes this trade-off explicitly instead of leaving it to luck.

4 · Sequential Loop

Observe → update posterior → re-optimize acquisition → observe again. Every evaluation reshapes the belief, so the search gets smarter with each expensive step.

↻How It Works

  1. Seed. Evaluate f at a handful of points (Latin hypercube or Sobol, ~5–10 for low dimensions). You cannot model nothing.
  2. Fit the surrogate. Condition a GP on all observed pairs. Out comes μ(x) and σ(x) over the whole domain — a full posterior, not a point estimate.
  3. Score every candidate. Compute the acquisition function across the domain. It is analytic and cheap, so this step costs nothing compared to one real evaluation.
  4. Pick the argmax. The peak of the acquisition surface is your next x. Note it may sit far from the current best — that's deliberate exploration, not a bug.
  5. Pay for one evaluation. Run the expensive experiment at that single point. Add (x, y) to the dataset.
  6. Repeat until budget dies. Stop on evaluation count, wall-clock, or when expected improvement falls under a threshold. Return the best observed point.
EI(x) = E[max(0, f_best − f(x))] = (f_best−μ)Φ(z) + σφ(z), z = (f_best−μ)/σ Expected Improvement: analytic, parameter-free, self-balancing. Compare UCB(x) = μ(x) − κσ(x) (minimization) where κ is an explicit exploration knob, and PI(x) = Φ(z), which is greedier and gets stuck more easily.
ExploitSample where μ is already promising. Fast local gains, real risk of settling into a local optimum.
ExploreSample where σ is wide. Expensive-looking, but this is what buys you the global optimum.

◎Real-World Applications

  • Hyperparameter tuning. Learning rate, depth, weight decay for a model that takes 8 hours per run — the canonical use case (Optuna, Ax/BoTorch, SMAC, Vizier).
  • Drug & materials discovery. Each candidate compound is a physical synthesis. BO chooses which molecule to make next.
  • A/B testing & pricing. Each configuration costs real traffic and revenue; BO minimizes how many bad variants users ever see.
  • Robotics & control. Tuning gait or PID parameters on hardware, where each trial risks wear and a fall.
  • Chip & simulation design. Layout or CFD parameters where one simulation burns hours of cluster time.

Where it breaks: GPs scale as O(n³) in observations, so past a few hundred points you switch to sparse GPs, random forests (SMAC), or TPE. It also degrades above roughly 20 dimensions unless you exploit structure — and if evaluations are cheap, plain random search is the better tool.

?Checkpoint — answer before you move on

  1. Why does Bayesian Optimization need a model of uncertainty — why isn't a plain regression fit of the observed points enough to choose the next point? Hint: what would a point-estimate model ever recommend outside the region you've already sampled?
  2. Expected Improvement and UCB both trade exploration against exploitation. What is the concrete difference in how each one lets you control that balance? Hint: count the free parameters in each formula.
  3. You need to tune 40 hyperparameters and each evaluation takes 2 seconds. Is Bayesian Optimization the right tool? Defend your answer with two specific reasons. Hint: think about GP cost per iteration versus the cost of one evaluation, and about dimensionality.
10-minute practice: Take any function you can plot — say f(x) = sin(3x) + 0.3x² on [−2, 2]. Hand-pick 3 points, sketch your own guess at μ and an uncertainty band, then mark where you would sample next and write one sentence justifying it as explore or exploit. Then run scikit-optimize's gp_minimize on the same function with 12 calls and compare its chosen points to yours.