How does Bayesian hyperparameter search pick the next configuration to evaluate?

## The problem Tuning hyperparameters means optimising a function `f(x)` where `x` is a configuration (learning rate, depth, regularisation strength, number of trees) and `f(x)` is the validation score you get after training a model with that configuration. This function is **black-box** (no formula, no gradient), **expensive** (one evaluation is a full training run, possibly cross-validated), and **noisy** (a different fold split or seed gives a slightly different score). Sampling configurations independently ignores everything the previous trials told you. Bayesian optimisation is the family of methods that reuses that information. ## The loop 1. Evaluate a handful of configurations to get an initial history `D = {(x_1, y_1), ..., (x_n, y_n)}`. 2. Fit a **surrogate**: a cheap probabilistic model of `f` given `D`. 3. Score every candidate `x` with an **acquisition function** built from the surrogate's beliefs. 4. Train the real model at the best-scoring candidate, append `(x, y)` to `D`, and go back to step 2. The surrogate costs milliseconds to fit and query; the real evaluation costs minutes to hours. That asymmetry is what makes the extra machinery worth it. ## Surrogates A **Gaussian process** treats `f` as a draw from a distribution over smooth functions. Given the observed points it returns, at any new `x`, a posterior mean `mu(x)` and a posterior standard deviation `sigma(x)`. Near observed points `sigma` is small; far from them it is large. Gaussian processes are excellent on a handful of continuous, roughly smooth knobs, and awkward when the space is high-dimensional, mostly discrete, or conditional (a knob that only exists when another knob takes a particular value). Fitting cost also grows steeply with the number of observations. A **tree-structured Parzen estimator** flips the modelling around. It splits the history into a good group and a bad group at some quantile of the observed scores, fits a density `l(x)` over the good configurations and a density `g(x)` over the rest, and prefers configurations that maximise the ratio `l(x) / g(x)` — points that look like the winners and unlike the losers. Under its assumptions that ratio is a monotone stand-in for expected improvement. It handles discrete, categorical and conditional parameters comfortably and scales better in the number of trials, at the price of modelling each dimension's density rather than the full joint interaction. ## Expected improvement For a maximisation problem with best-so-far `f_best`, expected improvement is `EI(x) = E[max(f(x) - f_best, 0)]`, the expected amount by which evaluating `x` would beat the incumbent, averaged over the surrogate's posterior at `x`. Two very different configurations can score highly: - one whose predicted mean is a little above `f_best` with small uncertainty (exploitation), and - one whose predicted mean is mediocre but whose uncertainty is wide, so the upper tail of its posterior still reaches well past `f_best` (exploration). That is the whole exploration/exploitation balance, and it falls out of the definition rather than being bolted on with a tuning knob. A pure greedy rule ("evaluate the highest predicted mean") would lock onto the first decent basin and never look elsewhere. Other acquisition rules exist — upper confidence bound `mu(x) + kappa * sigma(x)`, which exposes the balance as an explicit `kappa`, or probability of improvement, which is greedier than EI because it counts *any* improvement equally rather than weighting by how large it is. ## When it earns its keep, and when it does not It pays off when each evaluation is expensive and your total budget is tens of trials rather than thousands — exactly the regime where using history matters. It struggles when: the space is very high-dimensional (the surrogate needs data to be informative, and there is never enough); the scores are very noisy, so the surrogate chases lucky folds instead of real structure (repeated cross-validation or a noise-aware surrogate helps); or evaluations are so cheap that the sequential surrogate refit and the inability to saturate many workers cost more than they save. One subtlety worth naming: the acquisition function is itself optimised, usually by dense sampling plus local refinement over the configuration space. That inner optimisation is cheap because it only queries the surrogate, never the real model. ## What interviewers listen for A clean separation of the three pieces — surrogate (belief), acquisition (decision rule), real evaluation (ground truth) — and an explanation of why uncertainty is *rewarded* rather than penalised. Candidates who describe Bayesian search as "random sampling but smarter" without naming a surrogate have not understood it.