Notation

The book uses one notation throughout, and this appendix collects it. Each entry points to the section that introduces the symbol, where it is explained in words before it is used in a formula. Where the literature uses several conventions, the entry says which one the book follows.

A few typographic rules hold everywhere. Scalars are italic ( $x$ , $\sigma$ ), vectors are bold lowercase ( $\vx$ , $\vy$ ), and matrices are bold uppercase ( $\mK$ , $\mL$ ). A transpose is written $^\T$ . Inputs live in a domain $\X$ , usually the unit cube $[0, 1]^d$ after rescaling, where $d$ is the number of inputs; when an index runs over the inputs, as for one lengthscale per input, it is $j = 1, \dots, d$ . A finite set of candidate inputs is also written $\X$ , with $|\X|$ elements, even where the papers the book reports write $D$ . "Larger is better" throughout: the book maximizes, and a function that is naturally minimized, such as an error rate, is negated.

A.1 Sets, vectors, and matrices #

Table A.1 Linear algebra.

Symbol	Meaning	Introduced
$\R$ , $\R^d$	the real numbers; vectors of $d$ real numbers	Section 3.1
$d$	the number of inputs (dimension of $\X$ )	Section 1.2, Section 3.1
$\vx$ , $x_i$	a vector and its $i$ -th entry	Section 3.1
$\vx^\T$ , $\mA^\T$	transpose of a vector and of a matrix	Section 3.1, Section 3.2.3
$\mI$	identity matrix	Section 3.2.2
$\mA^{-1}$	inverse of $\mA$ (computed by solving, never formed)	Section 3.2.2
$\mL$	lower-triangular Cholesky factor, $\mL\mL^\T = \mA$	Section 3.5.3
$\mA \backslash \mathbf{b}$	the solution $\mathbf{z}$ of $\mA\mathbf{z} = \mathbf{b}$	Section 8.4
$\det \mA$ , $\log\det\mA$	determinant, and its logarithm (from the Cholesky diagonal)	Section 3.6, Section 3.6.1
$\tr \mA$	trace, the sum of the diagonal	Section 6.2.2, Section 9.4.1

A.2 Probability #

Table A.2 Probability.

Symbol	Meaning	Introduced
$\Prob(A)$	probability of an event	Section 2.1.2
$p(x)$ , $p(x \given y)$	density or mass function; conditional on $y$	Section 2.1.3
$X \sim p$	$X$ is distributed according to $p$	Section 2.1.3
$\D$	the observed data	Section 2.5
$\E[X]$ , $\E_n[\cdot]$	expectation; expectation under the posterior after $n$ observations	Section 2.6.1, Section 12.1
$\Var[X]$ , $\Cov[X, Y]$	variance; covariance	Section 2.6.2, Section 2.6.3
$\N(\mu, \sigma^2)$ , $\N(\vmu, \mSigma)$	Gaussian with mean and variance; with mean vector and covariance matrix	Section 4.1, Section 4.2
$\phi(z)$ , $\Phi(z)$	standard normal density and cumulative distribution function	Section 4.1.1
$\operatorname{sigmoid}(z)$	logistic function $1/(1 + e^{-z})$ , the Bradley-Terry link	Section 16.4
$H(p)$ , $H(X)$	entropy of a distribution or of a random variable	Section 6.1.2
$\KL(p \,\Vert\, q)$	Kullback-Leibler divergence	Section 6.2.1
$I(X; Y)$	mutual information	Section 6.3
$\delta$	failure probability: a high-probability statement holds with probability at least $1 - \delta$	Section 13.2.2
$R$ -sub-Gaussian	a mean-zero $Z$ with $\E[e^{\lambda Z}] \le e^{\lambda^2 R^2/2}$ for all $\lambda$ ; this $R$ is not the regret $R_T$	Section 13.2.2

The book writes $\N(\mu, \sigma^2)$ with the variance as the second argument, as most statistics texts do, and states the standard deviation $\sigma$ separately where it matters.

A.3 Gaussian processes #

Table A.3 Gaussian processes.

Symbol	Meaning	Introduced
$f$	the unknown objective (or latent utility)	Section 1.1
$\X$	the domain of inputs	Section 1.1
$\lvert\X\rvert$	the number of candidates, when the domain is a finite set	Section 12.4
$\GP(m, k)$	Gaussian process with mean function $m$ and kernel $k$	Section 7.3
$k(\vx, \vx')$	kernel (covariance function)	Section 3.1.1, Section 7.1.2
$\ell$ , $\ell_j$	lengthscale; one lengthscale per input $j$ (ARD)	Section 3.1.1, Section 9.2
$\sigma_f^2$	squared amplitude, $k(\vx, \vx)$ for a stationary kernel	Section 7.2.1
$\sigma_n^2$	observation noise variance	Section 2.6.4, Section 8.3
$X$ , $\vy$	observed inputs and observed values	Section 8.1
$\mK$	kernel matrix of the observed inputs, $[\mK]_{ij} = k(\vx_i, \vx_j)$	Section 7.3, Section 8.1
$\vk(\vx)$	covariances between $\vx$ and the observed inputs	Section 8.1
$\mu(\vx)$ , $\mu_n(\vx)$	posterior mean (after $n$ observations)	Section 8.1, Section 11.2
$\sigma^2(\vx)$ , $\sigma_n^2(\vx)$	posterior variance of the latent value (after $n$ observations)	Section 8.1, Section 11.2
$\bm{\alpha}$	weights $(\mK + \sigma_n^2\mI)^{-1}\vy$ in the posterior mean	Section 3.5.1, Section 8.2.1
$M$	number of features of a linear model; for random Fourier features, the number of frequencies drawn	Section 7.1, Section 10.4.3
$\mathcal{H}_k$ , $\langle f, g\rangle_k$ , $\lVert f\rVert_k$	reproducing kernel Hilbert space (RKHS) of $k$ , its inner product, and its norm	Section 10.2
$B$	bound on the RKHS norm; some papers bound $\lVert f\rVert_k$ , others $\lVert f\rVert_k^2$	Section 10.2.4
$\mathcal{K}$ , $q(\vx)$	integral operator of a kernel, and the weighting density it integrates against	Section 10.1.3
$\lambda_i$ , $\varphi_i$	eigenvalues and eigenfunctions of $\mathcal{K}$ (Mercer's theorem)	Section 10.3
$s(\boldsymbol{\omega})$ , $p(\boldsymbol{\omega})$	spectral density of a stationary kernel; the same normalized to a probability density	Section 10.4

One collision is worth knowing about. $\sigma_n^2$ , with no argument, is the noise variance, following Rasmussen and Williams (2006); its subscript stands for noise. $\sigma_n(\vx)$ , always written with its argument, is the posterior standard deviation after $n$ observations, following Srinivas et al. (2010). The argument $(\vx)$ tells them apart. Where both appear in one formula (Section 12.6), the noise variance is written $\sigma_\varepsilon^2$ . In Chapter 10, $\lambda_i$ with an index is an eigenvalue and $q$ a weighting density; elsewhere $\lambda$ is the inverse Mills ratio or a lapse rate, and $q$ the number of options in a query.

Sources cited in Section A.3 2

Rasmussen and Williams (2006) Gaussian Processes for Machine Learning
Srinivas et al. (2010) Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design

A.4 Optimization and preferences #

Table A.4 Optimization and preferences.

Symbol	Meaning	Introduced
$\vx^\star$ , $f^\star$	a maximizer and the maximum	Section 6.4.2, Section 11.1
$f^*_n$	the incumbent, the best value observed after $n$ evaluations	Section 12.2
$a_n(\vx)$	an acquisition function, after $n$ observations	Section 11.2
$\PI$ , $\EI$ , $\UCB$	probability of improvement, expected improvement, upper confidence bound	Section 12.2, Section 12.3, Section 12.4
$\beta$ , $\beta_t$	exploration weight of UCB, written $\mu_n(\vx) + \beta^{1/2}\sigma_n(\vx)$	Section 11.2.1, Section 12.4
$\xi$	improvement margin in PI and EI (a choice of experiment in Section 6.4)	Section 12.2
$r_t$ , $R_T$	instantaneous regret; cumulative regret over $T$ rounds	Section 13.1
$\gamma_T$	maximum information gain of a kernel after $T$ observations	Section 6.5.2
$\vx \succ \vx'$	$\vx$ is preferred to $\vx'$	Section 16.3
$g$ or $f$	latent utility of a person (the book uses $f$ when the GP machinery is shared)	Section 18.1
$\sigma$ (in a link)	noise scale of a person's evaluation of one option	Section 16.3
$\tau$	scale of the logistic link, $\operatorname{sigmoid}\big((g_i - g_j)/\tau\big)$	Section 16.4
$\lambda(z)$	inverse Mills ratio $\phi(z)/\Phi(z)$ , only in the chapters that define it	Section 17.3, Section 18.2
$\lambda_{\text{lapse}}$	lapse rate, the probability that an answer is a random slip	Section 20.4.2
$\mW$	negative Hessian of the log-likelihood; for pairwise answers, a weighted graph Laplacian	Section 17.2, Section 18.2
$\EUBO(\vx_1, \vx_2)$	expected utility of the best option	Section 19.4
$q$	number of options shown in one query (qEUBO)	Section 19.4

Regret bounds are stated with $\tilde O(\cdot)$ , which hides logarithmic factors, and every rate in the book is given with its assumptions and its regret unit (Section 29.4).

References

Rasmussen, C. E., and Williams, C. K. I. (2006). Gaussian Processes for Machine Learning. MIT Press. Cited in §A.3
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. (2010). Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. ICML 2010. Cited in §A.3