Optimizing an Expensive Black Box

Most optimization you meet assumes evaluations are cheap and gradients are available: run the function millions of times, follow the slope downhill. A large class of real problems breaks both assumptions.

Training a neural network to score one hyperparameter setting can take hours on a GPU. Measuring the yield of one chemical recipe means running a physical experiment. Simulating one aircraft wing takes a compute cluster overnight. In each case a single evaluation is expensive, so your entire budget might be fifty or a hundred tries, not millions.

These functions are also black boxes. You put in a configuration and get out a number, with no formula to differentiate and no gradient to follow. Bayesian optimization is the standard method for exactly this regime: derivative-free, expensive, and evaluation-limited.

The reflex for tuning a few knobs is grid search: pick several values per knob and try every combination. It has two fatal properties when evaluations are expensive.

First, it is exponential. Five values across four hyperparameters is 625 evaluations before you have looked anywhere in between. Second, and less obvious, it spends the budget uniformly even though most knobs barely matter.

James Bergstra and Yoshua Bengio showed this precisely in their 2012 paper "Random Search for Hyper-Parameter Optimization". Because typically only a few hyperparameters actually affect the result, a grid wastes most of its trials varying the ones that do not. Random search, drawing each configuration at random, covers the important dimensions far better for the same budget, and became the recommended baseline overnight.

Random search fixes grid search's worst habit, but it has a ceiling of its own: every query is chosen with no memory of the previous ones. The hundredth sample is drawn exactly as blindly as the first, ignoring everything you have learned about where good regions lie.

That is the opening Bayesian optimization exploits. If evaluations are expensive, it is worth spending real computation between them to decide where to look next. A few seconds of modelling is negligible next to a six-hour training run, so you can afford to think hard about each query.

The idea is to build a model of the objective from the evaluations so far, and let that model propose the next point. The model is cheap to query; the true function is not. Every observation makes the model sharper.

Bayesian optimization is a loop with two moving parts.

The surrogate is a cheap probabilistic model fitted to the evaluations so far. It predicts the objective everywhere, and crucially it also reports how uncertain that prediction is.

The acquisition function turns those predictions into a score for every candidate point, encoding a policy for what to try next. It is cheap, so you can optimize it thoroughly to pick the single most promising point. You then pay for one expensive evaluation there, add the result, and repeat.

This structure is what Bobak Shahriari and colleagues called "taking the human out of the loop" in their 2016 review: the loop itself decides where to sample, replacing a human squinting at results between runs.

A plain regression model would predict the objective and stop there. That is not enough, because a point predicted to be mediocre might be somewhere the model has simply never looked, and could hide the true optimum.

So the surrogate must be probabilistic: at every point it returns not just a best guess but a measure of how unsure it is. Uncertainty is high in unexplored regions and low near points you have already evaluated.

That single extra quantity is what lets the loop balance two competing urges. Exploitation samples where the predicted value is best. Exploration samples where the uncertainty is highest, in case something better is hiding. An optimizer that only exploits gets stuck in the first decent region it finds; one that only explores never converges. The next two lessons are, in effect, how to model uncertainty and how to trade it off.

Suppose you are tuning a single hyperparameter, a learning rate, and each trial is one training run.

You start with three random rates and their validation scores. The surrogate fits a curve through them with a confidence band: narrow at the three points, wide in the gaps. The acquisition function scans the whole range and finds that a rate between two of your points has a promising predicted score and meaningful uncertainty, so it scores highest there. You run that one trial.

The new result collapses the uncertainty around that rate. Maybe it was excellent, and the model now concentrates there; maybe it was poor, and the model rules the region out and sends the next query elsewhere. Either way you spent one expensive run and learned the most any single run could have told you.

The technique earns its keep wherever evaluations are the bottleneck.

The best-known application is tuning machine-learning models: learning rates, regularization strengths, architecture choices, where each configuration costs a full training run. It also drives experimental design in the physical sciences, choosing the next chemical, alloy, or material to synthesize when each experiment takes days in a lab. Engineers use it to tune simulators, and roboticists to tune control policies where each trial risks hardware.

The common thread is never the number of dimensions or the shape of the function. It is the cost per evaluation. If a single measurement is slow, costly, or risky, and you have no gradient, this is the family of methods to reach for.

The method is a specialist, and using it in the wrong regime just adds overhead.

If evaluations are cheap, the surrogate machinery is pure waste. Running the true function a million times is fine, so random search or an evolutionary method will beat the modelling cost. If you have gradients, as you do inside a differentiable model, gradient descent is enormously more efficient than treating the function as a black box.

Standard Bayesian optimization also fades as dimensionality climbs into the hundreds, because uncertainty becomes hard to estimate when data is sparse in a huge space. The comfortable zone is roughly up to a few dozen dimensions with a tight evaluation budget.

You now have the shape of the method: a loop that fits a probabilistic surrogate to past evaluations and uses an acquisition function to choose the next expensive query. Everything specific reduces to two design choices.

First, what surrogate models the objective and its uncertainty? The dominant answer is the Gaussian process, which gives a principled predicted mean and variance at every point, and is the subject of the next lesson. It assumes some familiarity with distributions; the probability-and-statistics-for-ml cursus covers that groundwork.

Second, how does the acquisition function convert mean and uncertainty into a single decision about where to look? That is the third lesson, and it is where the exploration-exploitation trade-off, familiar from the bandit setting in reinforcement-learning-foundations, gets made concrete.