I am looking for a concentration inequality of a double sum….
Let $X_1,\dots, X_n$ be iid r.v. and also let $Y_1,\dots ,Y_n$ be iid such that even $X_i$ and $Y_j$ are independent.
I am looking for a high probability bound for the event
$$ A=\left\{\left\|\frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^n f(X_i,Y_j)-E_{X,Y}(f(X,Y))\right\|_H\leq\cdots\right\}\,, $$
where $f$ is some bounded function in a Hilbert space $H$.
$\newcommand\de\delta$Let $a:=Ef(X_1,Y_1)$. Replacing $f$ by $f-a$, assume without loss of generality (wlog) that $Ef(X_i,Y_j)=0$ for all $i,j$. Let
$$Z:=\frac1{n^2}\sum_{i,j=1}^n Z_{ij},\quad Z_{ij}:=f(X_i,Y_j).$$
Then, letting $\cdot$ denote the inner product, we get
$$\begin{aligned}
n^4E\|Z\|^2&=nE\|Z_{11}\|^2 \\
&+2n(n-1)(EZ_{11}\cdot Z_{12}+EZ_{11}\cdot Z_{21}) \\
&+n(n-1)(EZ_{12}\cdot Z_{12}+EZ_{12}\cdot Z_{21}) \\
&+n(n-1)(n-2)(EZ_{12}\cdot Z_{13}+EZ_{21}\cdot Z_{31}
+EZ_{12}\cdot Z_{31}+EZ_{21}\cdot Z_{13}) \\
&\le Cn^3
\end{aligned}$$
for a certain real $C>0$ depending only on $f$ and the distributions of $X_i,Y_j$.
So, for any real $\de>0$, $$P(\|Z\|\ge\de)\le\frac{E\|Z\|^2}{\de^2}\le\frac C{n\de^2}\to0$$ as $n\to\infty$.
In principle, one can bound other (higher) moments of $\|Z\|$ to get better bounds on $P(\|Z\|\ge\de)$, but that is much harder technically -- cf. the 41-page treatment by Adamczak and Latała of the case of U-statistics with completely degenerate kernels. Note that $Z$ is a V-statistic (or order $2$), which is harder to deal with than with U-statistics of the same order. However, Adamczak and Latała deal with arbitrary orders.
