Bayesian Optimization
Some functions are brutally expensive to evaluate: training a model to read off its validation accuracy, running a physical experiment, a costly simulation. You can't afford thousands of samples, and you have no gradients. Bayesian optimization (BO) finds the optimum of such a black box in as few evaluations as possible by being strategic about where to look next — using a probabilistic model of the function to decide. It's the standard tool for hyperparameter tuning and experiment design — an optimization method one level up from gradient descent: it searches the hyperparameter space (learning rate, depth, regularization) instead of the weight space, when each evaluation is a full training run.
Real-world examples: hyperparameter tuning (learning rate, architecture choices), AutoML, optimizing chemical/materials experiments, tuning robotics controllers, and A/B-test design.
The setup: expensive, black-box, derivative-free
BO targets functions that are:
- Expensive: each evaluation costs minutes/hours/dollars, so you want few.
- Black-box: no formula, just inputs→outputs.
- Derivative-free: no gradients, so gradient descent is out.
- Often noisy.
The strategy: build a cheap probabilistic model of from the few points seen so far, use it to decide the single most promising next point, evaluate there, update, repeat.
Two ingredients
1. A surrogate model. A Gaussian process (previous lesson) is the standard surrogate: it predicts everywhere with calibrated uncertainty — exactly what we need to reason about where the optimum might hide. The GP gives a posterior mean and standard deviation at every candidate point.
Gaussian process regression
Five observations pin down a distribution over functions. The blue band is the ±2σ posterior: it pinches to zero at each data point and balloons where there's no data. The length-scale controls smoothness — small values let the function wiggle to hit every point (and stay uncertain between them); large values force a smooth, confident fit.
2. An acquisition function. A cheap function , computed from the surrogate's and , that scores how worth evaluating each point is. We optimize the acquisition function (cheap — it's just the GP) to pick the next , then evaluate the expensive only there.
The explore–exploit trade-off
The acquisition function must balance two pulls:
- Exploitation: sample where the surrogate mean is already good.
- Exploration: sample where uncertainty is high, because the optimum might be hiding in an unexplored region.
Pure exploitation gets stuck in a local optimum; pure exploration wastes budget. Common acquisition functions encode the balance differently:
Upper Confidence Bound is the simplest: prefer high mean and high uncertainty, with tuning the trade-off (large → more exploration).
Expected Improvement scores the expected amount by which would beat the current best — it automatically values both promising means and uncertain regions, and is the most popular default. (Written here for maximization; when minimizing a loss, swap the improvement to .)
Other acquisition functions
Probability of Improvement (PI) scores the chance of beating (but ignores by how much). Thompson sampling draws one function from the GP posterior and optimizes that sample. Entropy search picks the point that most reduces uncertainty about the location of the optimum. EI and UCB dominate in practice for their simplicity and strong performance.
The Bayesian optimization loop
1. Fit the GP surrogate to all (x, f(x)) seen so far.
2. Maximize the acquisition function α(x) over the surrogate → x_next.
3. Evaluate the expensive f(x_next). ← the only costly step
4. Add (x_next, f(x_next)) to the data. Repeat until budget exhausted.
Each iteration spends one expensive evaluation but lots of cheap surrogate computation — exactly the right trade when evaluations are the bottleneck.
Why BO beats grid and random search for HPO
Grid and random search are non-adaptive: they ignore everything learned from past trials. BO is adaptive — every result reshapes where it looks next, so it finds good hyperparameters in far fewer trials. The catch: BO is sequential (each step needs the last result), so when you can run hundreds of trials fully in parallel, random search or Hyperband can be more practical.
Limitations
- Dimensionality. Standard BO works best in low dimensions (≲ 20); GP surrogates and acquisition optimization degrade in very high-dimensional spaces.
- Sequential. The basic loop evaluates one point at a time (batch/parallel BO variants exist but are harder).
- Surrogate cost. Inherits the GP's — fine, since BO deliberately uses few evaluations.
Exercise
Why is a Gaussian process the standard surrogate model in Bayesian optimization?
Need a hint?
What does the acquisition function need from the surrogate?
Exercise
What is the role of the acquisition function in Bayesian optimization?
Need a hint?
What does BO optimize cheaply to decide the next expensive evaluation?
Exercise
In the UCB acquisition function α(x) = μ(x) + κ·σ(x), what happens as you increase κ?
Need a hint?
Which term gets more weight — mean or uncertainty?
Common mistakes
- Pure exploitation. Always sampling the current best-looking point gets trapped in a local optimum; the term (exploration) is essential.
- Using BO when evaluations are cheap. If is fast, random/grid search with thousands of cheap trials can beat BO's sequential overhead.
- Applying it in very high dimensions. Vanilla BO struggles past ~20 dimensions without specialized variants.
- Ignoring noise. Set the GP's noise term for noisy objectives, or the surrogate will chase observation noise.
Key takeaways
- Bayesian optimization minimizes/maximizes expensive, black-box, gradient-free functions in few evaluations by modeling them probabilistically.
- It uses a GP surrogate (mean + uncertainty) plus an acquisition function that's cheap to optimize and picks the next point.
- Acquisition functions (UCB , EI) balance exploitation (high mean) against exploration (high uncertainty).
- The loop (fit surrogate → maximize acquisition → evaluate once → update) makes BO adaptive, beating grid/random search for hyperparameter tuning when trials are costly.
Related concepts
- Gaussian Processes: the surrogate model BO is built on
- Bayesian Linear Regression: where the predictive uncertainty BO exploits first appeared
- Validation Strategies: the validation scores BO optimizes when tuning hyperparameters
- Hyperparameter Optimization & AutoML: where BO sits among grid, random, and Hyperband