Equivalence of RKHS with high probability

Question

Suppose you have two PSD kernels $k(x,y)$ and $k'(x,y)$. Let $\mathcal{H}_k(\mathcal{D})$ and $\mathcal{H}_{k'}(\mathcal{D})$ be the corresponding RKHS's.

Now, if we know that for all $f \in \mathcal{H}_k(\mathcal{D})$ if $||f||_{k'}$ is bounded (here $||.||_k$ denotes the norm w.r.t kernel $k$), then $\mathcal{H}_{k'}(\mathcal{D}) = \mathcal{H}_k(\mathcal{D})$.

However, now suppose $k'(x,y)$ is created from a randomized algorithm and we can prove that with probability $1 - \delta$, $(1 - \epsilon) k(x,y) \leq k'(x,y) \leq (1 + \epsilon) k(x,y)$ for all $x,y$, for a fixed $\epsilon$.

In this case, can we conclude that with probability $1 - \delta$, $\mathcal{H}_{k'}(\mathcal{D}) = \mathcal{H}_k(\mathcal{D})$. I am not even sure whether such a statement is theoretically sound.

Answer 1

If I understand your question correctly, you are asking if $k'\le ck$ for a constant $c\ge1$ implies that $\mathcal{H}_{k'}\subset \mathcal{H}_{k}$. Now Theorem 3.11 in V.I. Paulsen, M. Raghupathi, An Introduction to the Theory of RKHS, Cambidge Univ. Press 2016 says the following: $f\in \mathcal{H}_{k'}$ with norm $\le1$ iff $(x,y)\mapsto k'(x,y) - f(x)\overline{f(y)}$ is a kernel function. I think this implies the claim.

If your set of inequalities holds for $k'=k'_\omega$ for $\omega $ in a measurable subset of the underlying probability space of probability $\ge 1-\delta$, then on this subset $\mathcal{H}_{k'_\omega} = \mathcal{H}_{k}$. In this sense the equality of RHKS (which might or might not be an event) occurs with probability $\ge 1-\delta$.