The Gaussian Process Surrogate

Ordinary regression fits one function to your data. A Gaussian process does something stranger and more useful: it represents a probability distribution over all functions that could fit, and updates that distribution as data arrives.

Before seeing data, the GP prior expresses a vague belief, typically that the function is smooth and hovers around some mean. After observing a few points, the posterior keeps only the functions consistent with them. Where you have data, almost all plausible functions pass through the same place, so the spread is tiny. Away from data, many functions remain compatible, so the spread is wide.

The standard reference is the 2006 book "Gaussian Processes for Machine Learning" by Carl Rasmussen and Christopher Williams, which remains the definitive treatment.

Concretely, a fitted GP answers two questions at any input x you ask about. The posterior mean is its best single prediction of the objective there. The posterior variance is how uncertain that prediction is.

That pair is the entire product. Query a point near your data and you get a confident prediction: a mean close to nearby observations and a small variance. Query a point far from everything and you get a hedged prediction: the mean drifts back toward the prior, and the variance grows large.

This is precisely the probabilistic surrogate the previous lesson demanded. The acquisition function in the next lesson consumes exactly these two numbers, the mean and the variance, at each candidate point, and nothing else about the GP.

How does the GP decide two inputs should have similar outputs? Through the kernel, a function that measures similarity between any two points. The kernel is where all your assumptions about the objective live.

The most common choice is the squared-exponential, or RBF, kernel: similarity falls off smoothly with distance, so nearby inputs are strongly correlated and distant ones are nearly independent. It encodes a belief that the function is very smooth.

The Matern family relaxes that. It adds a roughness parameter, and at its common setting produces functions that are continuous and once-differentiable rather than infinitely smooth. For real objectives, which are rarely perfectly smooth, Matern is often the better default, a point Rasmussen and Williams make directly.

Picture the GP as a shaded band around a mean curve: the band is a confidence interval, roughly the mean plus or minus two standard deviations.

The prior band is uniformly wide, since you know almost nothing. When you observe the true function at one point, the band pinches shut there, because the GP now knows the value exactly, and the mean is pulled to pass through it. The kernel spreads that new certainty to neighbours: just beside the point the band is still narrow, and it widens back to prior width as you move away.

Add a second observation and the same thing happens around it. The mean becomes a curve threading every observation, and the band is a sequence of pinches at your data joined by bulges in the gaps. Those bulges are where the optimizer will want to look.

The reason a GP can produce a mean and variance in closed form is that it assumes any finite set of function values is jointly Gaussian. Conditioning a joint Gaussian on some of its components has a known formula, and that is all the GP posterior is.

Given observed inputs X with values y, and a new point x, the posterior at x is

mean(x)     = k(x, X) K^-1 y
variance(x) = k(x, x) - k(x, X) K^-1 k(X, x)

where K is the matrix of kernel similarities among the observed points and k(x, X) the similarities between x and them. You do not need to manipulate these, but two things are worth reading off. The mean is a weighted average of observed values, weighted by kernel similarity. The variance starts from the prior k(x, x) and is reduced by how well the observed points cover x. If nothing is similar to x, the subtracted term is near zero and the variance stays at its prior maximum.

A kernel has a few knobs of its own, called hyperparameters, and they matter as much as the kernel family. The main ones are the lengthscale, how far apart two inputs must be before their outputs decouple, and the output scale, how far the function swings vertically.

A short lengthscale makes a wiggly, cautious GP that trusts data only very locally; a long one makes a smooth GP that generalizes far from each point. Set these badly and the surrogate is misleading in either direction.

They are not guessed. The standard practice is to choose them by maximizing the marginal likelihood, the probability the GP assigns to the data actually observed, which automatically penalizes both overly wiggly and overly rigid fits. Every GP library does this refit as new points arrive.

So far the GP is assumed to pass exactly through each observation. Real evaluations are often noisy: retrain the same network twice and validation accuracy wobbles because of random initialization and data shuffling.

Gaussian processes handle this with one addition, a noise term added to the diagonal of the kernel matrix. Its effect is intuitive. With noise, the band no longer pinches all the way to zero at an observation, because the GP no longer fully trusts any single measurement. Repeated evaluations at the same point then genuinely help, each one shrinking the residual uncertainty there.

Getting this term right matters. Set the noise to zero on a noisy objective and the GP contorts itself to interpolate the wobble, producing a wildly overconfident surrogate that sends the optimizer chasing noise.

The GP posterior requires inverting the kernel matrix K, whose size is the number of observations squared. That inversion costs on the order of n-cubed time for n observations.

At Bayesian optimization's usual scale this is a non-issue and even a convenience. With a budget of a hundred evaluations, inverting a hundred-by-hundred matrix is instant, and it happens to align with the regime where evaluations are expensive: you will never have enough data for the cost to bite.

The cost does bite if you try to push a plain GP to tens of thousands of points, which is why GPs are a poor fit for cheap-evaluation problems and why scalable approximations exist. But it reinforces the previous lesson's boundary: the GP surrogate and the expensive-evaluation setting are matched to each other.

You now have a model that, from a handful of expensive evaluations, predicts the objective everywhere and reports calibrated uncertainty: small near data, large in the gaps, tuned to the data through the kernel and its hyperparameters.

That is the raw material, but it does not yet make a decision. The GP will happily tell you the mean and variance at any point; it will not tell you which point to pay to evaluate next. A point could be attractive because its predicted mean is high, or because its uncertainty is high, or both, and those pull in different directions.

Resolving that pull into a single next query is the job of the acquisition function, and it is where Andreas Krause's work on GP-UCB enters. That is the next lesson.