I'm trying to understand the proofs to bound Maximum Mean Discrepancy (MMD) in the paper "A Kernel Two-Sample Test" by Gretton et al. (2012). These are given in the appendix. Specifically, I am stuck with A.3 (Bound when $p=q$ and $m=n$, p. 758) on how to bound the expected value of $MMD_b$.
The step I am having trouble with is the following, with samples $X, X'$ following the same distribution and both having the same number of samples $m$. The individual samples are are $x_i, x_i'$, respectively.
\begin{align} &\frac{1}{m} \mathbb E_{X,X'}\left[\sum_{i=1}^m\sum_{j=1}^m\left(k(x_i, x_j) + k(x_i', x_j') -k(x_i,x_j') - k(x_i',x_j)\right)\right]^\frac{1}{2} \\ \leq & \frac{1}{m}\left[2m\mathbb E_xk(x,x) + 2m(m-1)\mathbb E_{x,x'}k(x,x')-2m^2\mathbb E_{x,x'}k(x,x')\right]^\frac{1}{2} \end{align}
I am assuming that the inequality follows from Jensen's inequality and the concavity of the square root. Also, I am guessing that we are using the fact that for a function $g$ it holds that $\mathbb E [g] = \mathbb E_{X'}[\hat{\mathbb E}_{X'}(g)] = \mathbb E_{X'}[\frac{1}{m}\sum_{i=1}^mg(x_i')]$, where the $x_i'$ are from $X'$. Still, I am not seeing how to formally derive the second line from the first one.
Thanks in advance!
Related question on stats.SE.
The trick is to handle the diagonal elements ($i=j$) separately, which gives the $2mE_xk(x,x)$ part. The rest follows from this.