How to compute bounding coefficients for McDiarmid's inequality?

Question

I am trying to understand the proof in Sec. A2 of Gretton et al.. To make the question self-contained, I summarize below the key ingredients. At the end of the post, I state my question.

Given a Reproducing Kernel Hilbert Space $\mathcal{F}$, we know that any function $f\in\mathcal{F}$ can be evaluated in a point $a$ as $f(a) = \langle f, \phi(a)\rangle$, where the feature mapping $\phi(a)$ takes the usual canonical form $\phi(a) = k(a, \cdot)$. Here $k$ is kernel and $k(a,b) = \langle\phi(a),\phi(b)\rangle$. Moreover, we restrict ourselves to the case of a bounded kernel, specifically $0\leq k(a,b)\leq K$, for any $a$ and $b$.

Let MMD$(\mathcal{F},p,q)$ be the Maximum Mean Discrepancy between two distribution $p$ and $q$ defined in Gretton et al. as: $$\text{MMD}(\mathcal{F},p,q) = \sup_{f\in\mathcal{F}}({\bf E}_x[f(x)]-{\bf E}_y[f(y)]),$$ where $x\sim p$ and $y\sim q$. A biased empirical estimate can be obtained by replacing the population expectations with empirical expectations computed on the samples $X=\{x_1, x_2, \dots, x_m\}$ and $Y=\{y_1, y_2, \dots, y_n\}$, such that $x_i\sim p$ and $y_i\sim q$ for all $i$. Then: $$\text{MMD}_b(\mathcal{F},X,Y) = \sup_{f\in\mathcal{F}}\left(\frac{1}{m}\sum_{i=1}^mf(x_i)-\frac{1}{n}\sum_{i=1}^nf(y_i)\right).$$

It is easy to see that the absolute difference $|\text{MMD}(\mathcal{F},p,q)-\text{MMD}_b(\mathcal{F},X,Y)|$ is upper bounded by $\Delta(p,q,X,Y)$ defined as: $$\Delta(p,q,X,Y) = \sup_{f\in\mathcal{F}}\left|{\bf E}_x[f(x)]-{\bf E}_y[f(y)] - \frac{1}{m}\sum_{i=1}^mf(x_i)+\frac{1}{n}\sum_{i=1}^nf(y_i) \right|.$$

One step of the proof requires to compute McDiarmid's inequality where the function allowed to change is $\Delta(p,q,X,Y)$ with respect to all $x_i$ and $y_i$. In order to compute the bounding coefficients for McDiarmid's inequality, at the beginning of page 757 of the referenced paper the authors state that changing either of $x_i$ or $y_i$ in $\Delta(p,q,X,Y)$ results in changes of at most $\frac{2}{m}\sqrt{K}$ or $\frac{2}{n}\sqrt{K}$, respectively. Recall that $K$ is the bounding value for the kernel.

Now the question is simply: why the bounding values for the McDiarmid's inequality are $\frac{2}{m}\sqrt{K}$ and $\frac{2}{n}\sqrt{K}$ when changing $x_i$ and $y_i$, respectively?

Edit: the RKHS $\mathcal{F}$ is actually the unit ball.

Answer 1

The paper you refer to says (in line 1 of Sect. 2.2) that $\mathcal{F}$ is the unit ball of a reproducing kernel Hilbert space (not the entire RKHS). So, $|f(a)|=|\langle f, \phi(a)\rangle|\le\|f\| \|\phi(a)\|\le1\times\sqrt{\langle\phi(a),\phi(a)\rangle}=\sqrt{k(a,a)}\le\sqrt K$ for all $f\in\mathcal{F}$ and all points $a$. So, any change of the value of $x_i$ incurs a change of $\Delta(p,q,X,Y)$ not exceeding $\frac1m\,\times2\times\sqrt K=\frac{2}{m}\sqrt{K}$ (in absolute value).