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?


1 Answer 1


The question was answered on MathOverflow by Iosif Pinelis:

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.