# Question regarding the assumption for Gaussian process regression error and Bayesian optimization

I am wondering in the research of Bayesian optimization and Gaussian process regression how the function error could be rigorously quantified. I am aware that in general either of the following assumptions would be made to quantify the regression error: (1) the true function is a sample from the GP prior (2) the true function has a bounded RKHS norm.

Regarding assumption (1), I cannot understand why in [Lemma 5.1, 1] $$f$$ complies with the posterior GP $$f(x) \sim N\left(\mu_{t-1}(\boldsymbol{x}), \sigma_{t-1}^2(\boldsymbol{x})\right)$$ after having the assumption of $$f$$ being a sample path of the GP prior.

I am aware that in [Section 7.3, 2], the target function is assumed to be a sample path of GP prior, and in Eq. (7.23) only the GP prior impacts the statistical analysis of the regression performance.

Should the error bound in [1] only be dependent on the GP prior as it is not assumed that $$f$$ complies with the posterior GP? Or does the assumption of being a sample path of the GP prior implicitly imply $$f$$ complies with the posterior GP?

Any hints would be really appreciated. Thanks!

[1] Srinivas, Niranjan, et al. "Information-theoretic regret bounds for gaussian process optimization in the bandit setting." IEEE transactions on information theory 58.5 (2012): 3250-3265.

[2] Williams, Christopher KI, and Carl Edward Rasmussen. Gaussian processes for machine learning. Vol. 2. No. 3. Cambridge, MA: MIT press, 2006.

• What exactly is the contradiction that you see here?
– Tim
Commented Jul 7, 2023 at 11:03
• I cannot fully understand the assumptions made for GPR. Contradiction for me: (1) The unknown function $f$ is assumed as a sample path of prior GP. This is already a realization of the prior GP, why it still complies with the posterior GP (as another distribution)? (Or could you please explain why would f comply with posterior GP not any other distribution.) (2) By assuming the RKHS norm, it assumes implicitly that the unknown function lives in the corresponding RKHS. However, the function we want to learn generally does not live in such RKHS; hence, the theorem seems to not hold in practice. Commented Jul 8, 2023 at 20:39
• I'm afraid I don't understand what you mean by that. Could you edit to give us more details on what is not clear to you?
– Tim
Commented Jul 8, 2023 at 21:53
• I think the core problem is that I could not understand why it is assumed that the unknown function $f$ is a sample path of GP prior. What role does this assumption play in providing error bounds? Commented Jul 10, 2023 at 10:21
• The role of GP prior is the same as the role of any other prior in a Bayesian model. You should probably edit the question to clarify it if you expect someone to answer it.
– Tim
Commented Jul 10, 2023 at 10:45

Should the error bound in [1] only be dependent on the GP prior as it is not assumed that 𝑓 complies with the posterior GP? Or does the assumption of being a sample path of the GP prior implicitly imply 𝑓 complies with the posterior GP?

The short answer is "yes", regarding the second question. The assumption of $$f$$ being a sample path of the GP prior implies that $$f$$ will also be a sample path of the GP posterior.

By the GP modelling assumptions, both the vector of observations $$\mathbf{y}_t := [y_1, ..., y_t]^\mathtt{T}$$, where $$y_i := f(x_i) + \epsilon_i$$, with $$\epsilon_i\sim N(0,\sigma^2)$$, for $$i \in \{1,\dots, t\}$$, and the value of $$f$$ at an arbitrary point $$x$$ in its domain will be jointly Gaussian distributed, as: $$\begin{bmatrix} \mathbf{y}_t\\ f(x) \end{bmatrix} \sim N \left( \begin{bmatrix} \mathbf{0}\\ 0 \end{bmatrix}, \begin{bmatrix} \mathbf{K}_t + \sigma^2\mathbf{I} & \mathbf{k}_t(x)\\ \mathbf{k}_t(x)^\mathtt{T} & k(x,x) \end{bmatrix} \right),$$ where $$\mathbf{K}_t := [k(x_i, x_j)]_{i, j = 1}^{t,t} \in \mathbb{R}^{t\times t}$$ and $$\mathbf{k}_t(x) := [k(x, x_1),\dots, k(x, x_t)]^\mathtt{T} \in \mathbb{R}^t$$. Solving for $$f(x)$$, we have the GP predictive equations with $$f(x) \sim N(\mu_{t}(x), \sigma_t^2(x))$$, with: \begin{align} \mu_t(x) &:= \mathbf{k}_t(x)^\mathtt{T}(\mathbf{K}_t + \sigma^2\mathbf{I})^{-1}\mathbf{y}_t\\ \sigma_t^2(x) &:= k(x,x) - \mathbf{k}_t(x)^\mathtt{T}(\mathbf{K}_t + \sigma^2\mathbf{I})^{-1}\mathbf{k}_t(x). \end{align} For a discrete domain with a finite number of points, we can then apply union bounds to derive the error bound in Lemma 5.1 of Srinivas et al. [1].

For the second assumption, where $$f \in H_k$$, with $$H_k$$ being the reproducing kernel Hilbert space (RKHS) associated with the GP covariance function $$k$$, note that this does not imply that $$f$$ is a sample from a GP. For a continuous domain and most kernels, $$f \sim GP(0, k)$$ usually implies $$f \notin H_k$$. It is possible to show that $$f$$ is in the RKHS associated with a fractional power of the kernel, though (see Theorem 4.12 in Kanagawa et al. (2018), below). In any case, the toolset to derive error bounds for $$f(x)$$ in this second assumption is different, and it usually involves analysing Martingale difference sequences and sub-Gaussian noise assumptions.

Kanagawa, M., Hennig, P., Sejdinovic, D., & Sriperumbudur, B. K. (2018). Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences. ArXiv. http://arxiv.org/abs/1807.02582

• Thank you so much for your reply. I agree with what you said about the second assumption. They showed in the paper that the sample path lives in an RKHS infinitesimally larger than the one corresponding to the kernel. However, I am still confused about the one with the posterior distribution. The GP predictive equations can only give an estimated distribution over f, but cannot guarantee that f complies with this posterior distribution, right? From my understanding, the only guarantee is that f complies with the prior given by assumption. Commented Jul 18, 2023 at 15:58
• @zzgsam, under the Bayesian formulation, the true data-generating model will be a sample from both the prior and the posterior distribution under a few mild assumptions, if there's no model misspecification. It's even so that, by the Bernstein-von Mises theorem (and extensions of it to non-parametric models and non-iid data), asymptotically in the limit of infinite data, the posterior distribution will converge to a point mass at the "true" data-generating model. So, in principle, the true $f$ will always be a sample from the GP posterior, assuming there's no model misspecification. Commented Jul 20, 2023 at 10:46
• Thanks again! I am wondering if you could share some references to support your statement, i.e. "a sample from both the prior and the posterior distribution under a few mild assumptions". I would love to learn what kind of assumptions are required. Commented Jul 21, 2023 at 7:19
• You're welcome. Here are a few references: * Ismaël Castillo, Richard Nickl. "Nonparametric Bernstein–von Mises theorems in Gaussian white noise." The Annals of Statistics, 41(4) 2013 * A. W. van der Vaart, J. H. van Zanten. "Rates of contraction of posterior distributions based on Gaussian process priors." The Annals of Statistics, 36(3) 2008. * Ghosal, Subhashis, and Aad van der Vaart. "Convergence Rates of Posterior Distributions for Noniid Observations." The Annals of Statistics (2007): 192-223. Commented Jul 22, 2023 at 9:19