Bayesian Optimization: Why a Surrogate Model Plus an Acquisition Function Beats Grid Search

Some functions are expensive to evaluate, and that changes everything about optimisation. Tuning a large model can take hours per configuration. Running a wet-lab experiment can take days. Testing a new alloy, a new drug candidate, or a new controller on real hardware can cost real money and real time. In that world, the question is not "what is the best optimisation algorithm in the limit?" It is "what should I try next, given the handful of results I already have?"

Bayesian optimisation is an answer to that second question. It builds a probabilistic model of the unknown function, uses that model to reason about uncertainty, and then chooses the next point by balancing what looks promising against what is still unknown. It is not magic, and it is not always the right tool. But for expensive, noisy, low-to-moderate dimensional problems, it is often dramatically more sample-efficient than grid search or random search.

The problem: an expensive black box

Suppose we want to maximise an unknown function

f:X→R

over some search space X . We can evaluate f at a point x , but each evaluation is costly, we have no gradient, and the observation may be noisy:

We have a small budget, say 20, 50, or 100 evaluations, not 100,000. Grid search wastes that budget in two ways. First, it spends evaluations in regions that early results already suggest are bad. Second, it scales terribly with dimension: a grid with 10 values per dimension needs 100 points in two dimensions and 10,000 points in four. Random search is better than grid search because it does not waste effort on irrelevant dimensions in the same rigid way, but it still learns nothing from one evaluation to the next. It has no memory, and no notion of uncertainty.

Bayesian optimisation adds both. It keeps a model of what it has learned, and a principled rule for what to try next.

Step 1: the surrogate model

The surrogate is a cheap, probabilistic stand-in for the expensive function. The classic choice is a Gaussian process (GP). A GP places a prior directly over functions: before seeing any data, we assume

where m(x) is a mean function, often taken as zero after centring the data, and k(x,x′) is a kernel that says how similar the function values at two points should be. A common choice is the squared-exponential kernel,

where σf2​ controls the overall scale of variation and ℓ , the length scale, controls how quickly the function can change. Points close together, relative to ℓ , have highly correlated values. Points far apart are nearly independent.

After observing data D=(xi​,yi​)i=1n​ , the GP posterior at a new point x is again Gaussian, with mean and variance

Here K is the kernel matrix over the observed points, k(x,X) is the vector of kernel values between x and each observed point, and y is the vector of observations.

This is the whole point of the surrogate. The posterior mean μ(x) is our best guess for f(x) . The posterior standard deviation σ(x) tells us how uncertain that guess is. Near observed points, uncertainty is low. Far from any observation, uncertainty is high. Bayesian optimisation exploits both quantities, not just the mean.

A GP is not the only possible surrogate. Random forests and tree-based models are popular in practice, especially for mixed categorical and conditional spaces, because they handle discrete variables and tree-structured search spaces naturally. Neural network ensembles and Bayesian neural networks are also used. The logic is the same in every case: the surrogate must give both a prediction and an uncertainty estimate. A point predictor alone cannot drive a good search, because it cannot tell the difference between "confidently bad" and "unknown, possibly excellent".

Step 2: the acquisition function

Given the surrogate, we need a rule that scores every candidate point and picks the winner. That rule is the acquisition function. It formalises the exploration-exploitation trade-off: exploit regions with high predicted value, and explore regions with high uncertainty, because that is where a better value might be hiding.

Let f+=maxi​yi​ be the best value observed so far. Three classic acquisition functions illustrate the trade-off from different angles.

Expected Improvement

Expected Improvement (EI) asks: how much better than f+ do we expect a new point to be, on average? For a GP surrogate, it has a closed form. Define

Then

where Φ and ϕ are the standard normal cumulative distribution and density functions.

Read the two terms. The first term rewards a high predicted mean: if μ(x) is well above f+ , EI is large. The second term rewards uncertainty: if σ(x) is large, there is a real chance the true value beats f+ by a lot, even if the mean is mediocre. EI is zero, or close to it, only when a point is both predicted to be bad and known with confidence. That is exactly the set of points we should stop wasting evaluations on.

Upper Confidence Bound

The Upper Confidence Bound (UCB) rule is simpler and more transparent:

where β controls the balance. A large β favours exploration; a small β favours exploitation. UCB is an optimistic rule: it acts as if each point were as good as its uncertainty plausibly allows, then picks the most optimistic point. The parameter β can be scheduled to grow slowly with the number of evaluations, which gives theoretical regret guarantees in the GP setting, but in practice it is often tuned as a hyperparameter of the search itself.

Probability of Improvement

Probability of Improvement (PI) is the simplest of the three:

It measures only the chance of any improvement, not its size. That makes it myopic: a point with a 51 percent chance of a tiny improvement scores higher than a point with a 49 percent chance of a huge improvement. PI is useful as a teaching example and as a baseline, but EI and UCB are usually better defaults.

In each iteration, Bayesian optimisation maximises the acquisition function over X using a cheap optimiser, evaluates the expensive function at the winner, adds the result to the data, refits the surrogate, and repeats. The acquisition function itself is cheap to evaluate, so spending real effort optimising it is worthwhile. This is a key structural point: we replace one expensive optimisation problem with a sequence of cheap ones, guided by a model that gets better with every evaluation.

A concrete example: tuning two hyperparameters

Imagine tuning a learning rate and a weight decay for a neural network. Each training run takes an hour. A grid of 8 learning rates by 8 weight decays would take 64 hours, and most of those runs would be wasted on combinations that are clearly too aggressive or too timid after the first few results.

A Bayesian optimisation loop looks like this in sketch form:

# Sketch, not a complete implementation: the surrogate and the
# acquisition function are the two pieces you must choose.
observations = evaluate_initial_points(n=6)  # space-filling design

for step in range(30):
    surrogate.fit(observations)              # GP posterior mean and variance
    next_point = maximise_acquisition(surrogate, acquisition="EI")
    result = train_and_evaluate(next_point)  # the expensive step
    observations.append((next_point, result))

best = max(observations, key=lambda pair: pair[1])

The initial points matter. A space-filling design, such as a Latin hypercube or a Sobol sequence, spreads the first evaluations across the space so the surrogate starts with a reasonable picture everywhere, rather than a cluster in one corner. Six to ten initial points in two or three dimensions is a common starting point; in higher dimensions, more are needed, which is itself a warning sign about dimensionality.

After a few iterations, a typical pattern emerges. Early picks explore broadly, because uncertainty is high almost everywhere. Later picks concentrate near the best region, but still occasionally probe an uncertain corner. That occasional probe is not a bug. It is how the method avoids getting trapped by an early, misleading result, especially when observations are noisy.

Why it beats grid and random search

The advantage is sample efficiency, and it comes from three sources.

First, the surrogate generalises across points. A GP with a sensible kernel learns that nearby configurations behave similarly, so one evaluation informs many nearby candidates. Grid search does not share information between grid points at all.

Second, uncertainty directs the search. Random search samples uniformly forever. Bayesian optimisation stops sampling regions that are confidently bad and spends its remaining budget where the model is uncertain or optimistic.

Third, the method adapts to the function. If one dimension barely matters, the kernel can learn a long length scale in that dimension, effectively ignoring it. This is automatic relevance determination, and it is why Bayesian optimisation can sometimes work in nominally higher-dimensional spaces than a grid ever could: the effective dimension is what matters, not the nominal one.

None of this means Bayesian optimisation is universally better. If evaluations are cheap, random search or even grid search can be fine, and their simplicity is a real virtue. If you can evaluate millions of points, use a method designed for that regime. Bayesian optimisation earns its complexity only when each evaluation is expensive enough that saving tens of evaluations is worth the overhead of fitting a surrogate.

Limitations and common pitfalls

Bayesian optimisation fails in instructive ways, and most of them trace back to the surrogate or the acquisition function being a poor match for the real problem.

High dimensions hurt. A GP in 50 dimensions with 100 observations is mostly guessing. The kernel distances become uninformative, uncertainty is high everywhere, and the acquisition function has no strong signal to follow. Practical fixes include restricting the search to the dimensions that matter, using additive or structured kernels, or embedding the search in a lower-dimensional space. None of these is automatic. If your problem genuinely has dozens of equally important dimensions and expensive evaluations, Bayesian optimisation alone is probably not the answer.

The kernel is an assumption, not a detail. A squared-exponential kernel assumes smooth, stationary variation: the function wiggles at the same rate everywhere. Many real functions do not. A function with a sharp cliff in one region and a flat plateau elsewhere will be badly modelled by a single length scale. Mismatched kernels produce overconfident or underconfident uncertainty, and the acquisition function then explores the wrong places. Checking the surrogate matters: hold out a few observations, compare predicted means and uncertainties against actual values, and be suspicious if the model is confident and wrong.

Noise is easy to underestimate. If observations are noisy and the noise level is fixed too low, the surrogate will chase noise: it will treat a lucky evaluation as a genuine peak and exploit around it. Estimating the noise level from data, or at least allowing a non-trivial noise term, is essential when evaluations involve random training runs, stochastic simulations, or measurement error.

Optimising the acquisition function is itself a problem. In higher dimensions, a simple local search over the acquisition function can miss its global maximum, so the method ends up evaluating a mediocre point for no good reason. Multi-start optimisation, or a dense random sample followed by local refinement, is a cheap safeguard.

Myopia and batching. Standard Bayesian optimisation is greedy: it picks one point at a time, assuming that is the last evaluation. It does not plan several steps ahead, and it does not naturally handle parallel evaluations. Batch variants exist, but they add complexity and their own approximations. If you can run 16 evaluations in parallel, a naive sequential loop leaves most of your hardware idle.

Categorical and conditional variables need care. A GP kernel over one-hot encoded categories can work, but it treats categories as if they lived in a continuous space, which they do not. Tree-based surrogates or specially designed kernels handle this better. Conditional spaces, where a hyperparameter only exists if another choice is made, are harder still, and are a common reason to prefer a tree-based optimiser in practice.

Do not confuse the best observed value with the best true value. Under noise, the best observation so far may be a lucky outlier. Reporting it as the optimum, or selecting a final configuration purely by observed value, overstates what was found. A safer final choice is the point with the best posterior mean, or a point re-evaluated to confirm its value.

A practical checklist

Before reaching for Bayesian optimisation, check that the problem fits: evaluations are expensive, gradients are unavailable or unreliable, the dimension is modest, and you can afford tens rather than thousands of evaluations.

Then get the basics right. Use a space-filling initial design. Choose a surrogate that can express uncertainty and matches the variable types in your space. Let the kernel hyperparameters and noise level be learned from data rather than fixed by guesswork. Use Expected Improvement or UCB as a default acquisition function, not Probability of Improvement. Optimise the acquisition function properly. Log every evaluation, including failures, because a failed evaluation is still information about the space. And validate the surrogate occasionally: if its predictions are badly calibrated, fix the model before blaming the search.

Finally, keep expectations honest. Bayesian optimisation does not remove the need for domain knowledge. A well-chosen search space, sensible bounds, and a meaningful objective matter far more than the choice between EI and UCB. The method is a smart way to spend a small budget inside a space you already understand. It is not a substitute for understanding the space.

Takeaway

Grid search spends a fixed budget blindly. Random search spends it blindly but more evenly. Bayesian optimisation spends it adaptively: a surrogate model summarises what has been learned, with uncertainty attached, and an acquisition function turns that summary into a decision about what to try next. When each evaluation is expensive and the dimension is manageable, that adaptivity is worth a lot. When evaluations are cheap or dimensions are high, simpler methods win. Knowing which regime you are in is the real skill.

Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial