Distribution of the RKHS norm of the posterior of a Gaussian process

Question

In a classical noisy regression setting, let $\big(f(x)\big)_{x\in\cal X}$ be a centered Gaussian process of covariance $k$ on a compact $\cal X$, and $\mathcal{F}_n$ be the filtration generated by some noisy measurements $\big(y_i = f(x_i)+\epsilon_i\big)_{i\leq n}$ where $\epsilon_i \overset{iid}{\sim} \mathcal{N}(0,\eta^2)$. Then, let $\mu_n(x) = \mathbb{E}[f(x) \mid \mathcal{F_n}]$ be the posterior mean of the GP given the noisy observations. Even if $f$ is not in the corresponding RKHS $\cal H_k$ with probability 1 in the general case, we know that $\mu_n$ does. Is it possible to prove tail bound for the distribution of $\lVert \mu_n \rVert_{\cal H_k}$ ?

We know that $\lVert \mu_n \rVert_{\cal H_k}^2=\rm Y^T(\rm K + \eta^2 \rm I)^{-1 T}(\rm K+\eta^2\rm I)^{-1}\rm Y$, where $\rm Y$ is the Gaussian vector of the observations $y_i$ and $\rm K$ is the kernel matrix of the $x_i$, but the inverse terms make the upper bound difficult to grasp...

We further know that $\mu_n$ solves the following regularized regression problem: $$\arg\!\min_{\hat{f} \in \cal H_k} \frac 1 2 \lVert \hat{f} \rVert_{\cal H_k}^2 + \frac 1 {2\eta^2} \sum_{i=1}^n \big(y_i - \hat{f}(x_i)\big)^2.$$

Answer 1

Take the easiest example first: $f$ is brownian, $\eta=0$ (no noise) and $x_i=i/n$. Then $\mu_n$ is piecewise linear and $\int_0^1 \mu'_n(x)^2\ dx$ is a sum of $n$ squared unit variance independent Gaussian variables, i.e. a "chi-square with $n$ degrees of freedom". Everything is explicit in this case, I hope it helps approach more general situations.

Answer 2

It is possible to get tail inequalities of such a quadratic form of a Gaussian vector using the results from (Hsu et al, 2012).

They prove that if $\rm C=A^\top A$ is a psd matrix and $\rm Y$ is a $\sigma$-sub-Gaussian random vector, that is $\exists \sigma \in \mathbb{R},~ \forall \rm \alpha \in \mathbb{R}^n$: $$\mathbb{E}\Big[e^{\rm \alpha^\top Y}\Big] < e^\frac{\lVert \alpha \rVert^2 \sigma^2}{2}~,$$ then for all $t>0$, $$\mathbb{P}\Bigg[\mathrm{Y^\top C Y} = \lVert \mathrm{A Y} \rVert^2 > \sigma^2\Big(\mathrm{tr(C)}+2\sqrt{\mathrm{tr(C^2)}t}+2\lVert\mathrm{C}\rVert t\Big) \Bigg] \leq e^{-t}~.$$

Here the condition is satisfied for $\rm C = (K+\eta^2 I)^{-1}$ which is psd and $\rm Y$ is $\sqrt{2}\lVert A \rVert$-sub-Gaussian.

It is indeed a generalization of chi-square variables as Jean Duchon mentioned.

---

Hsu, Kakade, Zhang, A tail inequality for quadratic forms of subgaussian random vectors, ECP (2012)