Book contents
Contents
raw Math
RAW Book Machine Learning Gaussian Processes

Bayesian Optimization

Robert Eisele

When each experiment is expensive, optimization is not just a question of where the minimum lies. It is also a question of which measurement is worth taking next.

Bayesian optimization combines a probabilistic model of an unknown objective with a rule for choosing experiments. The model describes what is plausible; the decision rule turns those beliefs into a measurement. Repeating this cycle can locate a good solution with relatively few evaluations.

Optimization when evaluations are expensive

Imagine tuning a positioning controller. Each setting \(x\) requires a physical test, and the loss \(f(x)\) measures its tracking error. A small value is better, but the result is unknown until the test finishes. We have a limited budget and cannot simply evaluate every setting.

\[x^*\in\operatorname*{arg\,min}_{x\in\mathcal X}f(x),\qquad y_i=f(x_i)+\epsilon_i.\]

The feasible set \(\mathcal X\) contains settings we may test. A black box need not be mysterious internally: the term describes the interface available to the optimizer, which chooses an input and receives a result. The observation \(y_i\) can differ from the latent objective \(f(x_i)\) because of measurement noise.

A limited set of experiments leaves multiple plausible minimaThree measurements agree with two possible loss curves. One curve has a deeper unexplored valley than the other. Same observations, different possible objectivessetting x
Both curves are consistent with the same three observations. Choosing the next experiment means deciding where resolving that ambiguity is most useful.

If both curves fit the measurements, how sure are we about where the minimum is? A posterior distribution gives us a way to make that uncertainty visible: draw a whole possible function, find its lowest point, and repeat. Every minimum casts one vote at its location. The machine is not tested again; only our model is sampled.

Where might the minimum be?

Possible functions and their minimaThe top plot shows posterior function draws and their minima at fixed observations. The lower plot shows the fraction of all draws whose minimum falls in each interval.
Fixed observationsRecent posterior draws and minimaFraction of draws

Drawing functions requires JavaScript.

The upper panel shows the most recent draws, while the histogram counts all draws. Initially its horizontal axis is the location of the minimum, aligned with the upper plot. Switching to minimum loss instead shows the distribution of its value on a different horizontal axis. Both are approximations conditional on the fixed squared-exponential GP and the 101-point grid; different priors or a finer grid can change them. The sampler uses a small numerical diagonal term and pins the three exact measurements to their known values.

There are two distinct decisions: which setting to test next, and which setting to use when testing ends. An informative experiment can be worth running even when it is not the setting we would currently deploy.

From predictions to experiments

After \(n\) evaluations, write the data as \(D_n=\{(x_i,y_i)\}_{i=1}^{n}\). The Gaussian process regression model supplies a posterior distribution for the unknown function. At one candidate \(x\), this is a normal distribution with mean \(\mu_n(x)\) and latent standard deviation \(s_n(x)\):

\[f(x)\mid D_n\sim\mathcal N\!\left(\mu_n(x),s_n^2(x)\right),\qquad s_n^2(x)=k_n(x,x).\]

The posterior covariance \(k_n(x,x')\) also tells us how the values at different settings move together. For independent Gaussian observation noise of variance \(\sigma_n^2\), a future reading has variance \(s_n^2(x)+\sigma_n^2\). The uncertainty about the function and the variability of another measurement are not interchangeable.

Choosing only the lowest posterior mean exploits the current model but may miss a deeper unexplored valley. Choosing only the largest uncertainty explores regardless of whether a good value is plausible. Instead, we assign each possible experiment a score \(\alpha_n(x)\), called an acquisition function, and pick a maximizer:

\[x_{n+1}\in\operatorname*{arg\,max}_{x\in\mathcal X}\alpha_n(x),\qquad D_{n+1}=D_n\cup\{(x_{n+1},y_{n+1})\}.\]
The sequential optimization loopData are used to fit a posterior, score candidates, choose and evaluate one experiment, and add its result back to the data.DataPosteriorScoreChooseEvaluateAdd one outcome, then update the model
The expensive objective is called only at the evaluation step. The inner candidate search uses the current posterior.

The acquisition is computed from the current posterior, without querying the expensive objective. Its maximization is an inner optimization problem; only the selected point is actually evaluated. Once its outcome arrives, we update the posterior and the acquisition changes.

Posterior and acquisition are different functionsThe lowest posterior mean and the maximum of the acquisition occur at different inputs. The acquisition maximum determines the next measurement. Posterior mean and uncertaintyAcquisition: larger is betternext experimentsetting x
Schematic: the acquisition combines predictions and uncertainty. Its maximum need not coincide with the minimum of the posterior mean.

When the budget is exhausted and any feasible setting may be deployed, a risk-neutral decision maker minimizing expected latent loss can choose \(\hat x\in\operatorname*{arg\,min}_{x\in\mathcal X}\mu_n(x)\). If only tested settings are eligible, minimize over those instead. This deployment recommendation differs from the next experiment.

What is an improvement worth?

For now assume noise-free evaluations. Let \(b_n=\min_{1\le i\le n}y_i\) be the best observed loss. If one more experiment yields a value \(v\), keeping the better of the old and new settings reduces that loss by

\[b_n-\min(b_n,v)=\max(b_n-v,0).\]

A poor trial has zero improvement, not negative improvement: we can still keep the previous solution. More generally, choose a margin \(\xi\ge0\), set a target \(\tau=b_n-\xi\), and let \(I(x)=(\tau-f(x))_+\), where \((a)_+=\max(a,0)\). With \(\xi=0\), this is exactly the reduction in the best observed loss. A positive margin defines a stricter, different payoff.

Improvement is an asymmetric payoffImprovement decreases linearly as loss approaches the target from below and is zero for outcomes at or above the target.Improvementtarget τpossible loss vτ − vno improvement
Only outcomes below the target earn a payoff. Their gain grows with the distance below it.

At a candidate \(x\), abbreviate \(\mu=\mu_n(x)\), \(s=s_n(x)\), \(\delta=\tau-\mu\), and, for \(s>0\), \(z=\delta/s\). Let \(\phi\) and \(\Phi\) be the standard normal density and cumulative distribution function.

Probability of improvement pays one for any outcome below the target and zero otherwise. Standardizing the normal variable gives

\[\operatorname{PI}(x)=P\!\left(f(x)<\tau\mid D_n\right)=\Phi(z).\]

Expected improvement (EI) instead pays the magnitude of the gain. Average the payoff over the posterior density, substitute \(v=\mu+st\), and use \(\phi'(t)=-t\phi(t)\) [JonesSchonlauWelch1998]:

\[\begin{aligned}\operatorname{EI}(x)&=\mathbb E[(\tau-f(x))_+\mid D_n]\\&=\int_{-\infty}^{\tau}(\tau-v)\,\frac1s\phi\!\left(\frac{v-\mu}{s}\right)\,dv\\&=\int_{-\infty}^{z}(\delta-st)\phi(t)\,dt=\delta\Phi(z)+s\phi(z).\end{aligned}\]

PI measures the probability mass below the target. EI weights that mass by the size of each possible improvement. For a known value \(s=0\), avoid division by zero: \(\operatorname{EI}=(\tau-\mu)_+\) and, for the strict inequality above, \(\operatorname{PI}=\mathbf1_{\{\mu<\tau\}}\). At an already evaluated noise-free incumbent, EI is zero when \(\xi=0\).

Probability of improvement and expected improvement as areasThe left panel shades Gaussian probability density below a target. The right panel shades the same density weighted by its distance below that target. PI: density below τEI: density × gaintarget τtarget τpossible loss vpossible loss v
Schematic: PI is the shaded probability mass. In EI, each density value is multiplied by its distance below the target before taking the area. The two vertical scales have different units.

A less likely win can be more valuable

Suppose the target is 1.00. Candidate A has \((\mu,s)=(0.95,0.02)\); candidate B has \((1.02,0.20)\). A has a roughly 99.4% chance of improving and EI about 0.050. B improves only about 46.0% of the time, but its EI is about 0.070. PI prefers A; EI prefers B because B's rarer gains can be much larger.

Probability versus magnitude

Comparing probability and expected improvementBoth curves use the same vertical scale. Their shaded areas show either probability of improvement or expected improvement, according to the selected view.

The comparison requires JavaScript.

Both curves share the same axes within each view. In the probability view, shaded area is the probability of improvement. In the gain view, height is the density multiplied by the improvement, so the shaded area is expected improvement. The vertical scale changes between views because the quantities have different units. The displayed scores use the normal distribution; the drawing truncates negligible tails.

At fixed \(\mu\), differentiation of the EI formula gives \(\partial\operatorname{EI}/\partial s=\phi(z)>0\). More latent uncertainty increases EI for that fixed mean and target. This does not mean uncertainty is always desirable: another candidate can have a substantially better mean.

Watch a sequence of decisions

The best tested gain is 0.38. The model would deploy 0.44. Why does it want to spend the next run at 0.60? Inspect that setting, then evaluate it.

A limited experiment budget

Data, surrogate and acquisitionThree plots share the same horizontal input axis: the observed data, the surrogate mean and uncertainty, and the acquisition score. Vertical lines mark the proposed and inspected settings.Loading model and acquisition
ObservationsSurrogate and intervalAcquisitionNext experimentInspected settingObjective when revealed
Predicted loss at the inspected settingThe shaded part of the predicted Gaussian density lies below the best observed loss and approximates the probability of improvement.

The experiment requires JavaScript.

Initially, with the squared-exponential GP and EI, the best observed loss is about 0.661 at \(x=0.38\). The lowest posterior mean is at \(x=0.44\), but EI proposes \(x=0.60\). There the predicted mean is about 0.682 and the standard deviation is 0.289: although the mean is worse than the incumbent, the uncertainty makes improvement plausible. PI is about 0.471 and EI about 0.105. Evaluating that proposal gives a loss of about 0.553; conditioning on the new observation changes the model and the next proposal to \(x=0.73\).

To inspect another input, move the slider or select its horizontal position in any of the three aligned plots. The gold marker follows the inspected input; it does not change the orange proposal. For the noise-free GP, the display pins previously measured inputs to their exact known values and zero latent uncertainty, correcting the tiny numerical effect of jitter at those inputs. The quadratic model can retain uncertainty because it assumes measurement noise and only permits quadratic curves.

The shaded band is \(\mu_n\pm1.96s_n\): under the selected model it is a 95% pointwise interval for the latent function at each fixed input, not a simultaneous 95% band for the entire curve. The smaller plot shows the predicted loss distribution at the inspected setting; its orange line is the best observed loss. The shaded fraction approximates PI, with the tails truncated for display. EI additionally weights the winning outcomes by their improvement. The graphs use a finite grid; a continuous optimizer might propose a different point.

Other ways to value an experiment

Optimism: the lower confidence bound

For minimization, a candidate's optimistic lower bound is \(\operatorname{LCB}(x)=\mu_n(x)-\kappa s_n(x)\), with \(\kappa\ge0\). Minimize this bound, or maximize its negative to fit the acquisition convention:

\[\alpha_{\mathrm{LCB}}(x)=-\mu_n(x)+\kappa s_n(x).\]

At \(\kappa=0\), the rule selects the lowest mean. Increasing \(\kappa\) gives uncertainty more weight. If \(\kappa=1.96\), the bound is the 2.5% pointwise posterior quantile under a Gaussian model; it is not automatically a simultaneous confidence guarantee across a domain or a sequence of adaptive experiments. GP-UCB theory uses a schedule and additional assumptions [SrinivasEtAl2010]. For maximization the corresponding optimistic bound is \(\mu_n+\kappa s_n\).

Thompson sampling: one possible world

Draw one whole function \(g\) from the posterior and evaluate its minimizer. This is the marked location of one draw in the earlier histogram, now used as the next experiment. Repeat with a new draw at the next decision. On a finite grid, if \(K_n=LL^\mathsf T\) is the joint posterior covariance and \(z\sim\mathcal N(0,I)\), then \(g=\mu_n+Lz\). Drawing an independent normal value at every point destroys the posterior correlations and invents spurious, jagged minima. If the covariance is singular, use a suitable positive-semidefinite factorization or a carefully documented numerical approximation. Thompson sampling originated in a different setting, sequential allocation between alternatives [Thompson1933].

Value of information

Improvement evaluates a new point against an incumbent. An experiment can also change the recommended setting elsewhere. Let \(M(D)=\min_{z\in\mathcal X}\mu_D(z)\) be the current minimum expected deployment loss. The knowledge gradient values an experiment by the expected reduction in this best achievable posterior mean [FrazierPowellDayanik2009]:

\[\alpha_{\mathrm{KG}}(x)=M(D_n)-\mathbb E_{Y\mid x,D_n}\!\left[M\!\left(D_n\cup\{(x,Y)\}\right)\right].\]

Each hypothetical reading updates the posterior and may change which setting we would deploy. With a fixed decision set and an exact model, KG is nonnegative: after observing the result we can always keep the old decision. Unlike classical noise-free EI, KG can value a repeat measurement for reducing uncertainty.

Entropy search: learning where the minimum is

Let \(X^*=\operatorname*{arg\,min}_{x\in\mathcal X}f(x)\). Because the objective is unknown, the location of its minimum is uncertain too. Entropy search asks how much a measurement at \(x\) is expected to reduce that uncertainty [HennigSchuler2012]. For a finite set of possible locations, write \(H(X^*\mid D_n)=-\sum_j p_j\log_2 p_j\), where \(p_j=P(X^*=x_j\mid D_n)\). Then

\[\alpha_{\mathrm{ES}}(x)=H(X^*\mid D_n)-\mathbb E_{Y\mid x,D_n}\!\left[H(X^*\mid D_n,x,Y)\right]=I(X^*;Y\mid D_n,x).\]

The second term averages over measurements we have not yet made. It is the expected remaining uncertainty about the optimum after learning the outcome, like asking which experiment would most clarify the earlier histogram of minimum locations. The difference is mutual information in bits: it is nonnegative in exact arithmetic, although a particular surprising outcome can increase entropy. Unlike EI, this score need not be large where an immediate improvement is likely; a measurement can be useful because it distinguishes competing explanations of where the minimum lies.

The dropdown uses an educational approximation, not the original continuous entropy-search algorithm. It draws 4,096 correlated posterior functions on the 101-point grid and records the minimum among 21 evenly spaced representer points. For each candidate, it also samples a prospective reading, including the quadratic model's assumed observation noise, and bins it into five equal-probability intervals under that candidate's predictive normal distribution. A joint frequency table estimates the mutual information between the representer-point winner and the binned reading. A fixed seed makes comparisons reproducible. GP observations already known exactly are assigned zero information in this noise-free bench.

More precisely, for a candidate \(x\), let \(N_{jk}(x)\) count draws in which representer \(j\) is the minimum and the prospective reading falls in bin \(k\). With \(S\) joint draws, estimate \(\hat p_{jk}=N_{jk}/S\), \(\hat p_{j\cdot}=\sum_k\hat p_{jk}\), and \(\hat p_{\cdot k}=\sum_j\hat p_{jk}\). The plotted score is

\[\widehat I(X^*;Y_{\mathrm{bin}}\mid D_n,x)=\sum_{j,k:\,\hat p_{jk}>0}\hat p_{jk}\log_2\frac{\hat p_{jk}}{\hat p_{j\cdot}\hat p_{\cdot k}}.\]

Each draw must preserve the dependence between the candidate value and the entire set of representer values. Drawing independent marginal values would change the distribution of the minimum and give a different, incorrect score. The outcome bins are fixed from the current predictive distribution before seeing the hypothetical reading; they are not refitted for each draw.

A small case gives a useful check. Let two independent candidate losses be standard normal, let \(X^*\) identify the lower of them, and observe only whether the first loss is below zero. Both locations are initially equally likely to win. Given a negative first loss, its chance of winning is \(3/4\); given a positive one, it is \(1/4\). Thus the sign reveals \(1+\tfrac34\log_2\tfrac34+\tfrac14\log_2\tfrac14\approx0.189\) bits about the winner. This is information about where the minimum is, not expected improvement in loss.

Discretizing the minimum and the reading changes the information being measured, while finite-sample frequency estimates have sampling error and an upward bias. A small numerical diagonal stabilizes the joint Gaussian factorization. The resulting curve is an approximation that can be jagged; small differences between peaks should not be overinterpreted. In particular, its bits are not EI's units of loss. Practical continuous entropy-search methods use more sophisticated approximations and may make different decisions.

Further acquisition rules

Scaled expected improvement divides expected improvement by the standard deviation of the improvement payoff, not the standard deviation of the predicted function [NoeHusmeier2018]:

\[\operatorname{ScaledEI}(x)=\frac{\mathbb E[I(x)\mid D_n]}{\sqrt{\operatorname{Var}(I(x)\mid D_n)}}.\]

It compares the mean gain with its variability, including the probability of zero gain. It requires a separate convention when the denominator is zero. Its goal differs from maximizing expected gain alone.

Predictive entropy search (PES) targets the same information about the minimum's location as ES, but uses the symmetry of mutual information to express it in terms of the distribution of a future observation [HernandezLobatoEtAl2014]:

\[I(X^*;Y\mid D_n,x)=H(Y\mid D_n,x)-\mathbb E_{X^*\mid D_n}\!\left[H(Y\mid D_n,x,X^*)\right].\]

For continuous observations, these are differential entropies; the conditional predictive distributions generally need approximation. The exact information objective is the same as ES, but practical ES and PES approximations need not give the same numbers.

Max-value entropy search (MES) asks instead about the optimum value \(F^*=\min_x f(x)\), scoring \(I(F^*;Y\mid D_n,x)\) [WangJegelka2017]. In the earlier experiment, switching the histogram from minimum location to minimum loss changes precisely the quantity being summarized. Two draws can place their minima in different valleys while attaining the same loss: knowing the optimum value is not the same as knowing where to find it.

Beyond the noise-free experiment

Noisy measurements

With noise, the smallest observed \(y_i\) may be a lucky negative error, not a good value of \(f\). Classical EI using this record as an exact incumbent can chase an unrealistically low target. A simple approximation replaces it with the lowest posterior mean among tested inputs. This plug-in baseline is convenient, but it ignores uncertainty and correlation in the baseline.

Another choice is noisy expected improvement: sample the latent values at the tested points and the candidate jointly, compute \((\min_i f(x_i)-f(x))_+\) in each draw, and average. This integrates over the uncertain latent baseline. At an identical previously tested input this particular latent-improvement utility is zero, although a repeat can still be useful for learning; KG or a replication-aware policy addresses a different decision problem.

Costs and constraints

If evaluations take different known times \(t(x)>0\), EI divided by \(t(x)\) is a useful gain-per-time heuristic, not a universally optimal finite-budget policy. If time is random, \(\mathbb E[I/T]\) and \(\mathbb E[I]/\mathbb E[T]\) are different objectives. Modeling durations and accounting for pending experiments matter when wall-clock time is the budget [SnoekLarochelleAdams2012].

Known constraints should restrict \(\mathcal X\) directly. For an unknown constraint \(g(x)\le0\), let the incumbent be the best previously observed feasible loss, and model feasibility alongside improvement. A constrained score is \(\mathbb E[I(x)\mathbf1_{\{g(x)\le0\}}\mid D_n]\). If improvement and feasibility are conditionally independent given the data, this reduces to \(\operatorname{EI}(x)P(g(x)\le0\mid D_n)\). If no feasible incumbent is known, this improvement baseline is unavailable and a separate feasibility-finding policy is needed. A high estimated probability of feasibility is not a safety guarantee; experiments with unacceptable risk need an explicit safety policy.

Parallel evaluations

Selecting the \(q\) largest single-point EI scores independently may send all workers to almost the same place. Batch EI scores the best outcome of the joint set:

\[q\operatorname{EI}(x_1,\ldots,x_q)=\mathbb E\!\left[\left(b_n-\min_{1\le j\le q}f(x_j)\right)_+\middle|D_n\right].\]

The joint posterior accounts for correlation. Two identical candidate points give the same latent outcome in every draw and therefore have no more batch improvement than one. In asynchronous settings, pending experiments can be incorporated by averaging over hypothetical outcomes; cheaper approximations use temporary pseudo-observations. Neither is equivalent to pretending pending jobs do not exist.

Build the optimizer

Consider a concrete first implementation: minimize a deterministic function on a bounded one-dimensional interval, use a fixed GP prior, choose points from a finite grid, and score them with EI at \(\xi=0\). The procedure below is complete for those assumptions. It counts the initial evaluations in the budget and returns both the best observation and a model-based recommendation.

1. Specify the prior and the observations

Choose an initial set of distinct grid points \(X=(x_1,\ldots,x_n)\) and evaluate them. A GP prior needs a mean function \(m(x)\) and a positive-semidefinite covariance kernel \(k(x,x')\). A concrete choice in one dimension is the squared-exponential kernel, with positive length scale \(\ell\) and signal standard deviation \(\sigma_f\):

\[k(x,x')=\sigma_f^2\exp\!\left(-\frac{(x-x')^2}{2\ell^2}\right),\qquad K_{ij}=k(x_i,x_j).\]

Nearby inputs have similar prior function values when their distance is small compared with \(\ell\). The diagonal \(k(x,x)=\sigma_f^2\) is the prior variance, not a noise variance. Construct the residual vector \(r=y-m(X)\): the data update the prior by how far the observations lie above or below the prior mean.

2. Condition on the measured values

For one candidate \(x\), let \(k_x=k(X,x)\) be the column vector of its covariances with the observed inputs. Under independent Gaussian measurement noise of variance \(\sigma_n^2\), the observation covariance is \(A=K+\sigma_n^2I\). The prior joint distribution and the Gaussian conditioning rule give

\[\begin{bmatrix}y\\ f(x)\end{bmatrix}\sim\mathcal N\!\left(\begin{bmatrix}m(X)\\m(x)\end{bmatrix},\begin{bmatrix}A&k_x\\k_x^\mathsf T&k(x,x)\end{bmatrix}\right),\qquad\begin{aligned}\mu_n(x)&=m(x)+k_x^\mathsf TA^{-1}r,\\s_n^2(x)&=k(x,x)-k_x^\mathsf TA^{-1}k_x.\end{aligned}\]

The first correction transports the observed residuals to \(x\); the second subtracts the uncertainty explained by the observations. These are predictions for the latent function. A new noisy reading has variance \(s_n^2(x)+\sigma_n^2\), not \(s_n^2(x)\). For the deterministic implementation below set \(\sigma_n=0\); the small numerical jitter introduced next is separate from the model.

3. Replace the inverse by triangular solves

Rather than forming \(A^{-1}\), factor a positive-definite \(A\) as \(LL^\mathsf T\). In the noise-free pseudocode, use \(A=K+\eta I\) with a small positive jitter \(\eta\), and solve

\[Lq=r,\qquad L^\mathsf T\alpha=q,\qquad Lv(x)=k_x.\]

The first two solves give \(\alpha=A^{-1}r\). For the variance, \(A^{-1}=L^{-\mathsf T}L^{-1}\), so \(k_x^\mathsf TA^{-1}k_x=(L^{-1}k_x)^\mathsf T(L^{-1}k_x)=v(x)^\mathsf Tv(x)\). Thus the quantities used by the acquisition are

\[\mu_n(x)=m(x)+k_x^\mathsf T\alpha,\qquad s_n^2(x)=k(x,x)-v(x)^\mathsf Tv(x).\]
QuantityDimensionsMeaning
\(K,A,L\)\(n\times n\)Observed covariances and their factor
\(r,\alpha,k_x,v(x)\)\(n\times1\)Residuals, solved weights, and candidate covariances
\(\mu_n(x),s_n^2(x)\)scalarsCandidate's latent mean and variance

The factorization and the residual solves are done once per outer iteration. Each candidate gets a new covariance vector and one forward solve. Jitter is a numerical approximation, not physical measurement noise; it can leave a tiny posterior variance at an observed point. Tiny negative computed variances from rounding may be clamped to zero. A materially negative variance or repeated Cholesky failure is a diagnostic, not something to conceal by clamping.

4. Work through one candidate

Use a zero-mean prior with \(\sigma_f=\ell=1\) and one exact observation \((x_1,y_1)=(0,1)\). At \(x=1/2\), take \(\eta=0\) for this hand calculation. Then \(K=[1]\), \(k_x=[e^{-1/8}]\), \(L=[1]\), and \(\alpha=[1]\). The equations above give

\[\mu_1(1/2)=e^{-1/8}\approx0.88250,\qquad s_1^2(1/2)=1-e^{-1/4}\approx0.22120,\qquad s_1(1/2)\approx0.47032.\]

The incumbent is \(b_1=1\), so \(\delta=1-0.88250\approx0.11750\) and \(z=\delta/s\approx0.24984\). Substituting these into the previously derived formulas gives \(\operatorname{PI}\approx0.59864\) and \(\operatorname{EI}\approx0.25221\). PI is a probability; EI is an expected reduction in the units of the objective. This is the complete path from a kernel and one observation to an acquisition score.

5. Assemble the loop

The initial set should cover the domain reasonably, because a single early observation says little about length scale. The grid determines the resolution of both the experiment and the recommendation. For each iteration, factor the training covariance once, evaluate EI at each eligible grid point, select the largest score, and only then call the objective. Break ties by the first grid point to keep the result reproducible. Here \(\operatorname{normalCDF}\) and \(\operatorname{normalPDF}\) are reliable standard-normal routines; a production implementation should use a numerical library rather than approximate the tail by naive subtraction.

function expectedImprovement(mean, variance, incumbent):
    delta = incumbent - mean
    if variance == 0:
        return max(delta, 0)
    s = sqrt(variance)
    z = delta / s
    return max(0, delta * normalCDF(z) + s * normalPDF(z))

  function checkedVariance(priorVariance, reduction, tiny):
    variance = priorVariance - reduction
    tolerance = 1e-10 * max(abs(priorVariance), abs(reduction), tiny)
    if variance < -tolerance:
      fail("Posterior variance is materially negative")
    return max(variance, 0)

  function posteriorOnGrid(D, grid, mean, kernel, jitter, tiny):
    X, y = inputs(D), outputs(D)
    K = kernelMatrix(X, X)
    L = cholesky(K + jitter * identity(size(X)))
    residuals = y - mean(X)
    weights = solveTranspose(L, solveLower(L, residuals))

    for x in grid:
      covariance = kernelVector(X, x)
      projection = solveLower(L, covariance)
      posteriorMean[x] = mean(x) + dot(covariance, weights)
      posteriorVariance[x] = checkedVariance(
        kernel(x, x), dot(projection, projection), tiny)

    return posteriorMean, posteriorVariance

  function bayesianOptimize(objective, grid, initialPoints, budget,
                mean, kernel, jitter, tiny):
    require 1 <= size(initialPoints) <= budget
    require grid is nonempty and contains only distinct, finite points
    require jitter and tiny are finite and positive
    require initialPoints are distinct members of grid
    D = []
    for x in initialPoints:
      value = objective(x)
      require value is finite
      D.append((x, value))

    while size(D) < budget:
        candidates = grid excluding inputs(D)
        if candidates is empty:
            break
      posteriorMean, posteriorVariance = posteriorOnGrid(
        D, grid, mean, kernel, jitter, tiny)
      incumbent = min(outputs(D))
        next = argmax over candidates of expectedImprovement(
            posteriorMean[x], posteriorVariance[x], incumbent)
      value = objective(next)
      require value is finite
      D.append((next, value))

    posteriorMean, posteriorVariance = posteriorOnGrid(
      D, grid, mean, kernel, jitter, tiny)
    bestObserved = argmin over D of observed value
    bestPredicted = argmin over grid of posteriorMean[x]
    return D, bestObserved, bestPredicted

Here tiny is a small positive floating-point scale, and the relative tolerance is an illustrative numerical choice, not a theorem. Report the jitter and investigate failed factorizations; increasing it can change the model's predictions. The final recomputation matters: after the last evaluation, the posterior used to choose that evaluation does not yet include its result. If an initial or later experiment fails or produces a non-finite value, stop or handle that failure explicitly rather than inserting it into the GP. Do not silently interpret a failed run as a valid loss.

From a grid to a real search space

For a continuous domain, maximize EI using bounded multistart optimization, preferably seeded by a space-filling candidate set. The acquisition can have several local maxima, so one local start is not a global guarantee. In higher dimensions, a full grid grows exponentially; mixed discrete and categorical choices require representations and search methods that respect their structure.

Input scaling makes length scales comparable; it must preserve the mapping back to physical settings. Outcome centering and scaling can improve conditioning, but the incumbent, \(\xi\), noise standard deviation, and reported values must be transformed consistently. The kernel and its length scales encode assumptions about which settings are similar. Re-estimating hyperparameters changes the posterior; conditioning on a single fitted value ignores hyperparameter uncertainty.

For differentiable \(\mu\) and \(s>0\), acquisition optimization can use the gradient

\[\nabla\operatorname{EI}(x)=-\Phi(z)\nabla\mu_n(x)+\phi(z)\nabla s_n(x),\]

where the incumbent and margin are fixed while optimizing the current acquisition. When \(z\) is very negative, the two terms in the EI formula nearly cancel; accurate Gaussian tail functions or a log-EI implementation are preferable to an unexamined zero caused by underflow. A Cholesky factorization takes \(O(n^3)\) time and \(O(n^2)\) memory; repeated candidate predictions and acquisition optimization add further cost.

What the answer does and does not guarantee

Bayesian optimization is most attractive when a single evaluation is costly relative to fitting and searching the surrogate. It is not a proof that the returned setting is the global optimum. A kernel that is too smooth, a misleading prior, unmodeled drift, hidden constraints, or a coarse candidate set can all make the proposed experiments systematically unhelpful. Pointwise GP intervals are conditional on the model, not automatically calibrated coverage under an arbitrary real objective.

Keep a record of every attempted setting, outcome, duration, failure, and model version. Compare against simple baselines such as random or space-filling search under the same budget. For noisy problems, validate the final recommendation with independent repeats when possible. A stopping rule based on a small acquisition value is only as trustworthy as the model and the numerical search; an exhausted budget is a much clearer reason to stop.

The central separation: the GP describes uncertainty about the objective; the acquisition encodes what an experiment is worth; the deployment rule determines what to use after experimentation. Each is a modeling or decision choice, and changing one can change the answer.

References

  • [Thompson1933]Thompson, W. R. (1933). On the Likelihood That One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3/4), 285-294.
  • [JonesSchonlauWelch1998]Jones, D. R., Schonlau, M., & Welch, W. J. (1998). Efficient Global Optimization of Expensive Black-Box Functions. Journal of Global Optimization, 13, 455-492.
  • [FrazierPowellDayanik2009]Frazier, P., Powell, W., & Dayanik, S. (2009). The Knowledge-Gradient Policy for Correlated Normal Beliefs. INFORMS Journal on Computing, 21(4), 599-613.
  • [SrinivasEtAl2010]Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. (2010). Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. Proceedings of ICML, 1015-1022.
  • [HennigSchuler2012]Hennig, P., & Schuler, C. J. (2012). Entropy Search for Information-Efficient Global Optimization. Journal of Machine Learning Research, 13, 1809-1837.
  • [SnoekLarochelleAdams2012]Snoek, J., Larochelle, H., & Adams, R. P. (2012). Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems, 25.
  • [HernandezLobatoEtAl2014]Hernández-Lobato, J. M., Hoffman, M. W., & Ghahramani, Z. (2014). Predictive Entropy Search for Efficient Global Optimization of Black-box Functions. Advances in Neural Information Processing Systems, 27, 918-926.
  • [WangJegelka2017]Wang, Z., & Jegelka, S. (2017). Max-value Entropy Search for Efficient Bayesian Optimization. Proceedings of the 34th International Conference on Machine Learning, PMLR 70, 3627-3635.
  • [NoeHusmeier2018]Noè, U., & Husmeier, D. (2018). On a New Improvement-Based Acquisition Function for Bayesian Optimization. arXiv preprint, arXiv:1808.06918.