Exercises — Bayesian hyperparameter optimization

(a)→(ii), (b)→(iii), (c)→(i). These are exactly the three boxes of Figure s01: (a) is the lavender surrogate box, (b) is the coral acquisition box, (c) is the "bar to beat" that both refer to. The surrogate is the map, the acquisition function is the compass, and $f^{+}$ is the bar you're trying to clear.

When $\lambda ={\lambda }^{\prime }$ the Euclidean distance $\Vert \lambda -{\lambda }^{\prime }\Vert$ is $0$, so the exponent is $0$ and $\exp (0)=1$. Thus $k(\lambda ,\lambda )={\sigma }_f^2$. This is the variance of $f$ at a single point — the most a point can be correlated with is itself. The length-scale $\ell$ plays no role here (distance is $0$); it only controls how fast $k$ decays once $\lambda \ne {\lambda }^{\prime }$.

(B). Each real evaluation costs the same (a full training run), but Bayesian optimization spends those evaluations wisely by learning from every result. Compare 2.6.11-Grid-Search and 2.6.12-Random-Search, which choose points without looking at earlier outcomes.

$Z=\frac{{\mu }_n-f^{+}}{{\sigma }_n}=\frac{0.90-0.88}{0.05}=\frac{0.02}{0.05}=0.4$. Positive $Z$ means the mean already sits above the bar — exploitation looks promising here.

First term: $(0.90-0.88)\times 0.6554=0.02\times 0.6554=0.013108$. Second term: $0.05\times 0.3683=0.018415$. $\text{EI}=0.013108+0.018415=0.031523\approx 0.0315$. Notice both terms are positive: exploitation ($\mu >f^{+}$) and exploration ($\sigma >0$) contribute.

$\text{UCB}=0.90+2\times 0.05=0.90+0.10=1.00$. Why weight ${\sigma }_n$ linearly by a constant $\kappa$? A Gaussian posterior at $\lambda$ has mean ${\mu }_n$ and spread ${\sigma }_n$. Moving $\kappa$ standard deviations above the mean gives an optimistic high-quantile of the score: for a normal, ${\mu }_n+\kappa {\sigma }_n$ is roughly the "best plausible value" at confidence set by $\kappa$ (e.g. $\kappa \approx 2$ covers about the upper $\sim 2.5\%$ tail). Because the uncertainty of a Gaussian scales linearly with ${\sigma }_n$, the honest optimistic bound is ${\mu }_n$ plus a linear multiple of ${\sigma }_n$ — that is the entire justification for the simple sum. UCB literally reads as "mean plus $\kappa$ slices of the doubt."

Point A: $Z_A=\frac{0.86-0.85}{0.02}=0.5$. ${\text{EI}}_A=(0.01)(0.6915)+(0.02)(0.3521)=0.006915+0.007042=0.013957\approx 0.0140$. Point B: $Z_B=\frac{0.82-0.85}{0.10}=-0.3$. ${\text{EI}}_B=(-0.03)(0.3821)+(0.10)(0.3814)=-0.011463+0.038140=0.026677\approx 0.0267$. B wins ($0.0267>0.0140$). Even though B's mean is below the current best, its large $\sigma$ means it could still surprise us upward — EI values that gamble. This is exploration overruling exploitation.

Case (i): below-best mean (${\mu }_n<f^{+}$). The second term ${\sigma }_n\varphi (Z)\to 0$. And $Z=\frac{{\mu }_n-f^{+}}{{\sigma }_n}\to -\infty$ (numerator negative, denominator $\to 0^{+}$), so $\Phi (Z)\to 0$, killing the first term too. Therefore $\text{EI}\to 0$: a known point that isn't better is worthless to re-sample. Case (ii): above-best mean (${\mu }_n>f^{+}$). Again ${\sigma }_n\varphi (Z)\to 0$. But now $Z\to +\infty$ (numerator positive), so $\Phi (Z)\to 1$, and the first term $\to ({\mu }_n-f^{+})\cdot 1={\mu }_n-f^{+}$. Therefore $\text{EI}\to {\mu }_n-f^{+}>0$: a point we're certain about but that beats the bar is worth exactly its guaranteed improvement. This is the sensible limit — no uncertainty, so the improvement is just the deterministic gap. Together these two limits are why the piecewise definition sets $\text{EI}=\max (0,{\mu }_n-f^{+})$ at ${\sigma }_n=0$: zero in case (i), the plain gap in case (ii).

Current best $f^{+}=\max (0.80,0.86,0.79)=0.86$. Candidate P: $Z=\frac{0.85-0.86}{0.03}=-0.3333$. ${\text{EI}}_P=(-0.01)(0.3696)+(0.03)(0.3773)=-0.003696+0.011319=0.007623\approx 0.00762$. Candidate Q: $Z=\frac{0.83-0.86}{0.07}=-0.4286$. ${\text{EI}}_Q=(-0.03)(0.3341)+(0.07)(0.3639)=-0.010023+0.025473=0.015450\approx 0.01545$. Evaluate Q ($0.01545>0.00762$): higher uncertainty makes the bigger bet worthwhile. After evaluating Q: the GP refits with the new point; ${\sigma }_n$ collapses toward 0 near Q (we now know it), while the mean bends toward the observed $y$. If $y_Q>0.86$, $f^{+}$ updates and the whole landscape re-scores.

flowchart TD
  A["Init random points"] --> B["Fit GP get mu and sigma"]
  B --> C["Maximize acquisition alpha"]
  C --> D["Evaluate f at new point EXPENSIVE"]
  D --> E["Add point to data"]
  E --> F{"Budget left"}
  F -->|yes| B
  F -->|no| G["Return best lambda"]

Only step D pays a real training cost. Steps B and C are cheap math on the surrogate — that is exactly why we can afford to be clever about choosing D. This flowchart is Figure s01's loop drawn in boxes: B is the lavender surrogate, C the coral acquisition, D the mint evaluation, and the yes edge is the butter refit arrow.

The claim is broadly correct, and here's the mechanism. $\text{UCB}={\mu }_n+\kappa {\sigma }_n$. As $\kappa \to 0$, UCB $\to {\mu }_n$: pure exploitation (pick highest predicted mean, ignore doubt). As $\kappa \to \infty$, UCB is dominated by $\kappa {\sigma }_n$: pure exploration (pick the most uncertain point regardless of mean). EI's second term ${\sigma }_n\varphi (Z)$ is its built-in exploration bonus; early on, ${\sigma }_n$ is large everywhere (few points sampled), so EI naturally spreads out — matching large-$\kappa$ UCB. As data accumulates and ${\sigma }_n$ collapses, both methods drift toward exploitation. Verdict: similar tendency early; but UCB's balance is a fixed knob $\kappa$, whereas EI's balance is automatic and data-driven via $\Phi (Z)$ and $\varphi (Z)$.

Setup. Let $u=f(\lambda )-f^{+}$, so $u\sim \mathcal{N}(m,{\sigma }_n^2)$ with $m={\mu }_n-f^{+}$. We want $\mathbb{E}[\max (0,u)]={\int }_0^{\infty }u\cdot \frac{1}{{\sigma }_n}\varphi \left(\frac{u-m}{{\sigma }_n}\right)du$. Substitute $z=\frac{u-m}{{\sigma }_n}$, so $u={\sigma }_{n}z+m$ and $du={\sigma }_{n}dz$. The lower limit $u=0$ maps to $z=-m/{\sigma }_n=-Z$. $\text{EI}={\int }_{-Z}^{\infty }({\sigma }_{n}z+m)\varphi (z)dz={\sigma }_n{\int }_{-Z}^{\infty }z\varphi (z)dz+m{\int }_{-Z}^{\infty }\varphi (z)dz.$ First integral — why $\int z\varphi (z)dz=-\varphi (z)$. Recall $\varphi (z)=\frac{1}{\sqrt{2\pi }}{e}^{-z^2/2}$. Differentiate it: $\frac{d}{dz}\varphi (z)=\frac{1}{\sqrt{2\pi }}\cdot (-z)e^{-z^2/2}=-z\varphi (z)$. So $-\varphi (z)$ is an antiderivative of $z\varphi (z)$ — that's the whole justification. Evaluating: $[-\varphi (z){]}_{-Z}^{\infty }=0-(-\varphi (-Z))=\varphi (-Z)$. Why $\varphi (-Z)=\varphi (Z)$. The bell curve depends on $z$ only through $z^2$ (the exponent is $-z^2/2$), and $(-Z{)}^2=Z^2$. So $\varphi$ is an even function: reflecting the input sign leaves the height unchanged. Hence $\varphi (-Z)=\varphi (Z)$. Times ${\sigma }_n$ gives ${\sigma }_n\varphi (Z)$ — the uncertainty term. Second integral: ${\int }_{-Z}^{\infty }\varphi (z)dz=1-\Phi (-Z)$. Using the same evenness of $\varphi$, the CDF satisfies $\Phi (-Z)=1-\Phi (Z)$, so $1-\Phi (-Z)=\Phi (Z)$. Times $m=({\mu }_n-f^{+})$ gives $({\mu }_n-f^{+})\Phi (Z)$ — the improvement term. Summing: $\text{EI}=({\mu }_n-f^{+})\Phi (Z)+{\sigma }_n\varphi (Z)$. ∎ Numeric check: $Z=\frac{0.90-0.88}{0.05}=0.4$, $\Phi (0.4)=0.6554,\varphi (0.4)=0.3683$. $\text{EI}=0.02(0.6554)+0.05(0.3683)=0.013108+0.018415=0.031523\approx 0.0315$ — matching Exercise 2.2. The derivation and the formula agree.

Quick self-test before you leave: EI's exploration term ::: ${\sigma }_n(\lambda )\varphi (Z)$ EI's exploitation term ::: $({\mu }_n(\lambda )-f^{+})\Phi (Z)$ UCB as $\kappa \to 0$ ::: pure exploitation, picks max ${\mu }_n$ EI as ${\sigma }_n\to 0$ with ${\mu }_n>f^{+}$ ::: tends to ${\mu }_n-f^{+}$ (the deterministic gap) Why refit the GP each loop ::: so ${\sigma }_n$ shrinks where sampled and the acquisition updates