Every learning algorithm has parameters it cannot learn from its own objective: learning rates, regularization strengths, tree depths, dropout rates. Grid search treats these as a lattice to enumerate, and its cost grows exponentially with dimension. Bergstra and Bengio showed in 2012 that random search outperforms grids when only a few hyperparameters matter, because random sampling does not waste evaluations repeating values along irrelevant axes. But random search also ignores everything it has already observed.

A more productive formalization starts with a configuration λ in a domain Λ. Let f(λ) be the validation loss obtained after training with λ. We seek the minimizer of f. Three properties define this problem class. The function is expensive, since each evaluation is a full training run. It is noisy, since initialization and data ordering perturb it. It is a black box, offering no gradients in general. Together, these properties determine which mathematical tools apply and which do not.

Two complementary ideas have reshaped the field. Bayesian optimization builds a probabilistic model of f and uses it to decide where to evaluate next, turning a sampling problem into a sequential decision problem. Multi-fidelity methods recognize that f can be approximated cheaply, through partial training or data subsets, and allocate computation adaptively. The theory becomes interesting where these two ideas meet: the interplay between modeling an unknown function and allocating finite resources to learn about it.

A Gaussian process places a prior directly over functions: f ~ GP(m, k). This means any finite collection of function values is jointly Gaussian, with mean given by m and covariance given by the kernel k. The kernel encodes assumptions about smoothness. Two configurations that are close in hyperparameter space are assumed to produce correlated validation losses, and length-scale parameters govern how strong that correlation is.

Suppose we have n observations y at configurations X, with Gaussian observation noise of variance σ². Conditioning on them yields a closed-form posterior. The predictive mean at a new point λ is μ(λ) = k(λ, X)[K + σ²I]⁻¹y. The predictive variance is s²(λ) = k(λ, λ) − k(λ, X)[K + σ²I]⁻¹k(X, λ). Here K is the n × n kernel matrix. The mean interpolates the observations in a smoothed way. The variance shrinks near evaluated points and returns to the prior far from them. This calibrated uncertainty, more than the mean, is what makes the GP useful for optimization.

The choice of kernel matters. The squared exponential kernel implies infinitely differentiable sample paths. Snoek, Larochelle and Adams argued that this is unrealistically smooth for validation loss surfaces. They advocated the Matérn 5/2 kernel, whose samples are twice differentiable, combined with automatic relevance determination, which assigns a separate length scale to each dimension. A large learned length scale signals a hyperparameter that barely affects performance, so the model performs an implicit form of variable selection. The kernel's own hyperparameters are fitted by maximizing the marginal likelihood or, more robustly, integrated out with slice sampling.

The cubic cost of inverting K, O(n³), rarely matters here, since n seldom exceeds a few hundred evaluations. The real limitations are structural. Stationary kernels assume the function varies at the same rate everywhere, yet loss surfaces are often flat across most of the domain and steep near its boundaries. Input warping through learned Beta cumulative distribution functions partly addresses this, as does placing learning rates on a logarithmic scale. Conditional and categorical spaces are harder. An optimizer choice that activates its own parameters, for example, strains the Euclidean geometry that kernels assume. This is why tree-structured Parzen estimators and random forest surrogates remain competitive.

The deeper point is that a surrogate states an inductive bias about the response surface, chosen before any data arrives. A GP succeeds when its smoothness assumptions roughly match reality. When they do not, it degrades relatively gracefully, because the posterior variance still reflects which regions have not been observed.

Takeaway

A surrogate model is only as useful as its uncertainty estimates. In optimization, knowing where you are ignorant matters more than predicting well where you have already looked.

The posterior alone does not say where to evaluate next. An acquisition function a(λ) maps the posterior to a scalar utility, and the next configuration is its maximizer. Because a depends only on the cheap surrogate, it can be optimized with multistart gradient methods or evolutionary search. This moves the difficulty of the expensive outer problem into a tractable inner loop.

Expected improvement is the workhorse. Let f* be the best loss observed so far. The improvement at λ is max(0, f* − f(λ)), and its expectation under the Gaussian posterior has a closed form: EI(λ) = (f* − μ)Φ(z) + sφ(z), where z = (f* − μ)/s and Φ and φ are the standard normal distribution and density functions. The first term rewards a low predicted mean. The second rewards high uncertainty. The exploration-exploitation trade-off is not imposed by a tuning constant; it emerges from the integral itself. Probability of improvement ignores the magnitude of the gain and counts only whether improvement occurs, which makes it tend toward excessive greed by comparison.

The upper confidence bound family makes the trade-off explicit. In minimization form, one selects the minimizer of μ(λ) − √β_t · s(λ). Srinivas, Krause, Kakade and Seeger proved in 2010 that, with an appropriate schedule for β_t, GP-UCB achieves cumulative regret of order √(T β_T γ_T). Here γ_T is the maximum information gain obtainable from T observations. For the squared exponential kernel, γ_T grows polylogarithmically in T, so average regret vanishes. This was among the first results to give Bayesian optimization rigorous no-regret guarantees, and it showed how kernel smoothness directly controls sample complexity.

Information-theoretic criteria take a different view. Entropy search and predictive entropy search choose evaluations that maximize the expected reduction in entropy of the distribution over the minimizer's location. Max-value entropy search targets the optimal value instead, which is cheaper to approximate. Thompson sampling draws a function from the posterior and evaluates its minimizer, a randomized strategy that parallelizes naturally. The knowledge gradient asks how much the final recommendation would improve, aligning acquisition with the decision actually made at the end.

No acquisition function dominates. Each encodes a different answer to the question of what an evaluation is for: immediate gain, optimism under uncertainty, or information about the optimum. In practice, a misspecified surrogate often matters more than the choice of acquisition function. Every guarantee holds relative to its assumptions.

Takeaway

Exploration need not be a hand-tuned constant. When uncertainty is modeled honestly, the balance between exploring and exploiting can follow from a single expectation.

Bayesian optimization treats each evaluation as atomic, but training is a process. A configuration's loss after a fraction of the epochs, or on a subset of the data, is a low-fidelity estimate of its final value. If poor configurations reveal themselves early, fully training them wastes compute. Multi-fidelity methods formalize this as an adaptive resource allocation problem.

Successive halving is the canonical algorithm. Karnin, Koren and Somekh introduced it for best-arm identification, and Jamieson and Talwalkar adapted it to hyperparameter search. The procedure is simple. Sample n configurations and give each an equal share of the budget. Discard the worse half, then repeat, doubling the resources given to each survivor. After log₂ n rounds a single configuration remains. Each round consumes roughly B / log₂ n of the total budget B, so most configurations are evaluated cheaply and only a few receive full training.

The guarantee rests on a minimal assumption: each configuration's intermediate loss converges to a limit, at a rate bounded by an envelope function γ(t). No parametric form for learning curves is required. Under this condition, Jamieson and Talwalkar showed that successive halving identifies the best configuration with a budget that scales with the sum of the inverse envelope, evaluated at the gap between each configuration and the best one. Poor configurations, with large gaps, are eliminated after tiny allocations, so resources concentrate where telling configurations apart is hard. Uniform allocation, by contrast, must pay the cost of the hardest gap on every configuration.

Successive halving leaves one parameter unresolved: n. Many configurations with small budgets risk eliminating slow starters. Few configurations with large budgets sacrifice breadth. Hyperband, by Li and colleagues, hedges against this choice by running several brackets with different trade-offs, and it provably performs within a logarithmic factor of the best bracket chosen in hindsight. Later extensions combine the two strands of the field. BOHB replaces Hyperband's random sampling with model-based proposals. ASHA removes synchronization barriers to enable massive parallelism. Freeze-thaw methods model learning curves directly with GPs.

The weak point is rank correlation across fidelities. Configurations with large learning rates often lead early and lose late, and strong regularization can do the reverse. When learning curves cross, early stopping systematically biases search toward fast learners rather than good ones. The speedup is real and provable, but it depends on an assumption about training dynamics that should be checked empirically for each problem.

Takeaway

Early stopping trades bias for budget. It provides a provable speedup when early rankings predict final ones, and a systematic distortion when they do not.

Viewed mathematically, hyperparameter optimization is not one problem but three: modeling an unknown function, deciding where to query it, and deciding how much to spend on each query. Gaussian processes supply calibrated beliefs. Acquisition functions turn those beliefs into decisions. Multi-fidelity schemes turn partial information into savings.

Each layer comes with guarantees that depend on assumptions: smoothness encoded in the kernel, regularity behind regret bounds, convergence behind elimination. When these methods fail in practice, the cause is usually a violated assumption rather than a flawed algorithm. Vapnik's lesson applies here too. The capacity and bias of a model class determine what can be learned from limited data, and the outer loop of learning is no exception.

The principle for algorithmic development follows directly. Make assumptions explicit, quantify uncertainty honestly, and spend computation where it most reduces uncertainty about the decision that matters. Methods built this way tend to stay useful long after their specific implementations are superseded.