2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you! I edited the question to include \mathcal{F} is the unit ball. $\endgroup$ Jul 19, 2016 at 14:42
  • $\begingroup$ Kind of annoying to have a well written accepted answer and zero votes. Unfortunately analysis and probability is not well represented in Mathoverflow. $\endgroup$ May 19, 2018 at 13:04

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.