Bayesian Optimization Cheat Sheet

Every formula from the Bayesian optimization explainer, with its punchline

companion to the Bayesian optimization explainer · 2026-08-02

The One-Pager

The loop

Fit GP posterior on all data → maximize acquisition on the model (cheap, thousands of queries) → evaluate f at the argmax (expensive, once) → repeat. Model computation buys evaluation frugality.

RBF kernel

k(x, x′) = exp( −‖x−x′‖²2ℓ² )

ℓ is a hypothesis about how fast f varies. Too long ⇒ confidently smooths over hidden peaks (the dangerous direction); too short ⇒ ignorance everywhere.

GP posterior (the two numbers)

μ_n(x) = k_*^T(K+σ_n²I)⁻¹y

σ_n²(x) = k(x,x) − k_*^T(K+σ_n²I)⁻¹k_*

Exact Gaussian conditioning. σ² depends on where you measured, not what you saw. Cost: one O(n³) factorization, then O(n) / O(n²) per query.

Marginal likelihood (fitting ℓ, σ_n)

log p(y|X,θ) = −½y^TKᵀ⁻¹y − ½log det Kᵀ − n2log 2π

Fit term vs complexity term (log-det) = automatic Occam’s razor. Surface can be multi-modal — restart or integrate (Snoek 2012).

Expected improvement

z = μ_n(x) − f^*_nσ_n(x); EI = (μ_n−f^*_n)Φ(z) + σ_nφ(z)

Exploit term + explore term. At z = 0: EI = σφ(0) ≈ 0.40σ — uncertainty alone has cash value. Default since EGO (1998).

Knowledge gradient

KG_n(x) = 𝔼_n[ max_x′ μ_n+1(x′) ] − max_x′ μ_n(x′)

Values a point by the recommendation it enables, not the value it reveals. Equals EI only when noiseless AND the final answer is restricted to sampled points. Wins under noise (EI's incumbent is a lucky draw) and when a point informs elsewhere without beating the incumbent. Cost: nested optimization — use one-shot KG.

PI & UCB

PI = Φ(z); UCB = μ_n(x) + β^½σ_n(x)

PI ignores improvement size (hugs the incumbent). UCB is explicit optimism; with β_n ~ log n, GP-UCB proves sublinear regret. All one-step criteria are myopic.

LogEI (NeurIPS 2023)

EI and its gradients underflow where improvement is unlikely → the acquisition optimizer silently stalls. Optimizing a numerically careful log EI fixes it. Decades of “EI underperforms” was partly this bug. Modern BoTorch default.

Batch: qEI

qEI = 𝔼[ max( max_j f(x_j) − f^*_n, 0 ) ]

Joint expectation via Monte-Carlo posterior samples (reparameterized, so gradients flow). The jointness is what stops q near-duplicate proposals.

Failure modes

Myopia (one-step lookahead); model mismatch (wrong ℓ ⇒ confident blindness); dimensionality (>~20D: contested territory). And if evaluations are cheap — just use random search.

The modern line

TPE/SMAC: non-GP surrogates (Optuna). TuRBO: trust regions. SAASBO: sparse dimension priors. πBO: user beliefs. qEHVI: parallel multi-objective. PFNs4BO/OptFormer/GIT-BO: pretrained transformer surrogates. LLAMBO: LLM warm-starts.

The live fights (2024–26)

High dimensions: vanilla GPs match specialized methods (ICML’24, ICLR’25) vs “we still don’t understand” (Nov’25). LLMs in the loop: good for priors and warm starts; budget-matched studies say not yet a surrogate.

When to reach for BO

Evaluations expensive (minutes+), budget small (tens), dimensions modest (≤~20), continuous-ish inputs. Otherwise: random search (cheap f), CMA-ES (cheap f, many dims), Optuna/TPE (conditional spaces).

Papers: GP-UCB · Snoek 2012 · Frazier tutorial · TuRBO · SAASBO · LogEI · PFNs4BO · LLAMBO · Garnett (book) — full story: the explainer · drills: review deck