\section{Introduction.}
\label{section:intro}

Since being introduced by W. Hoeffding \cite{hoeffding1948class}, U-statistics have become an active topic of research. 
Many classical results in estimation and testing are related to U-statistics; detailed treatment of the subject can be found in excellent monographs \cite{Decoupling, korolyuk2013theory,serfling2009approximation,kowalski2008modern}. 
A large body of research has been devoted to understanding the asymptotic behavior of real-valued U-statistics. 
Such asymptotic results, as well as moment and concentration inequalities, are discussed in the works \cite{PM-decoupling-1995,Decoupling,gine2000exponential,gine1992hoffmann,ibragimov1999analogues, gine2001lil,houdre2003exponential}, among others. 
The case of vector-valued and matrix-valued U-statistics received less attention; natural examples of matrix-valued U-statistics include various estimators of covariance matrices, such as the usual sample covariance matrix and the estimators based on Kendall's tau \cite{wegkamp2016adaptive,han2017statistical}. 

Exponential and moment inequalities for Hilbert space-valued U-statistics have been developed in \cite{adamczak2008lil}. 
The goal of the present work is to obtain moment and concentration inequalities for generalized degenerate U-statistics of order 2 with values in the set of matrices with complex-valued entries equipped with the operator (spectral) norm. 
The emphasis is made on expressing the upper bounds in terms of \emph{computable} parameters. 
Our results extend the matrix Rosenthal's inequality for the sums of independent random matrices due to Chen, Gittens and Tropp \cite{chen2012masked} (see also \cite{junge2013noncommutative,mackey2014matrix}) to the framework of U-statistics. 
As a corollary of our bounds, we deduce a variant of the Matrix Bernstein inequality for U-statistics of order 2. 

We also discuss connections of our bounds with general moment inequalities for Banach space-valued U-statistics due to R. Adamczak \cite{adamczak2006moment}, and leverage Adamczak's inequalities to obtain additional refinements and improvements of the results. 


We note that U-statistics with values in the set of self-adjoint matrices have been considered in \cite{chen2016bootstrap}, however, most results in that work deal with the element-wise sup-norm, while we are primarily interested in results about the moments and tail behavior of the spectral norm of U-statistics. 
Another recent work \cite{minsker2018robust} investigates robust estimators of covariance matrices based on U-statistics, but deals only with the case of non-degenerate U-statitistics that can be reduced to the study of independent sums.

The key technical tool used in our arguments is the extension of the non-commutative Khintchine's inequality (Lemma \ref{bound-on-expectation}) which could be of independent interest.



\section{Notation and background material.}

Given $A\in \mathbb C^{d_1\times d_2}$, $A^\ast\in \mathbb C^{d_2\times d_1}$ will denote the Hermitian adjoint of $A$. 
$\mathbb H^d\subset \mathbb C^{d\times d}$ stands for the set of all self-adjoint matrices. 
If $A=A^\ast$, we will write $\lambda_{\mbox{\footnotesize{max}\,}}(A)$ and $\lambda_{\mbox{\footnotesize{min}\,}}(A)$ for the largest and smallest eigenvalues of $A$. 

Everywhere below, $\|\cdot\|$ stands for the spectral norm $\|A\|:=\sqrt{\lambda_{\mbox{\footnotesize{max}\,}}(A^\ast A)}$. 
If $d_1=d_2=d$, we denote by $\mbox{tr\,} (A)$ the trace of $A$. 
The Schatten p-norm of a matrix $A$ is defined as $\|A\|_{S_p} = \left( \mbox{tr\,} (A^\ast A)^{p/2} \right)^{1/p}.$
When $p=1$, the resulting norm is called the nuclear norm and will be denoted by $\|\cdot\|_\ast$. 
The Schatten 2-norm is also referred to as the Frobenius norm or the Hilbert-Schmidt norm, and is denoted by $\|\cdot\|_{\mathrm{F}}$; and the associated inner product is 
$\dotp{A_1}{A_2}=\mbox{tr\,}(A_1^\ast A_2)$. 

Given $z\in \mathbb C^d$, $\left\| z \right\|_2=\sqrt{z^\ast z}$ stands for the usual Euclidean norm of $z$. 
Let $A,~B\in\mathbb{H}^{d}$. 
We will write $A\succeq B  (\textrm{or}A\succ B)$ iff $A-B$ is nonnegative (or positive) definite.
For $a,b\in \mathbb R$, we set $a\vee b:=\max(a,b)$ and $a\wedge b:=\min(a,b)$. 
We use $C$ to denote absolute constants that can take different values in various places.  

Finally, we introduce the so-called Hermitian dilation which is a tool that often allows to reduce the problems involving general rectangular matrices to the case of Hermitian matrices. 
\begin{definition}
Given a rectangular matrix $A\in\mathbb C^{d_1\times d_2}$, the Hermitian dilation $\mathcal D: \mathbb C^{d_1\times d_2}\mapsto \mathbb C^{(d_1+d_2)\times (d_1+d_2)}$ is defined as
\begin{align}
\label{eq:dilation}
&
\mathcal D(A)=\begin{pmatrix}
0 & A \\
A^\ast & 0
\end{pmatrix}.
\end{align}
\end{definition}
\noindent Since 
$\mathcal D(A)^2=\begin{pmatrix}
A A^\ast & 0 \\
0 & A^\ast A
\end{pmatrix},$ 
it is easy to see that $\| \mathcal D(A) \|=\|A\|$. 


The rest of the paper is organized as follows. 
Section \ref{sec:setup} contains the necessary background on U-statistics. 
Section \ref{sec:moment} contains our main results -- bounds on the $\mathbb H^d$-valued Rademacher chaos and moment inequalities for $\mathbb H^d$-valued U-statistics of order 2. 
Section \ref{section:adamczak} provides comparison of our bounds to relevant results in the literature, and discusses further improvements. 
Finally, Section \ref{sec:proof} contains the technical background and proofs of the main results. 


\subsection{Background on U-statistics.}
\label{sec:setup}


Consider a sequence of i.i.d. random variables $X_1,\ldots,X_n$ ($n\geq2$) taking values in a measurable space 
$(\mathcal S,\mathcal{B})$, and let $P$ denote the distribution of $X_1$. 
Define 
\[
I_n^m:=\{(i_1,\ldots,i_m):~1\leq i_j\leq n,,~i_j\neq i_k~\textrm{if}~j\neq k\},
\] 
and assume that $H_{i_1,\ldots,i_m}: \mathcal S^m\rightarrow\mathbb H^d$, $(i_1,\ldots,i_m)\in I_n^m$, $2\leq m\leq n$, are $\mathcal{S}^m$-measurable, permutation-symmetric kernels, meaning that $H_{i_1,\ldots,i_m}(x_1,\ldots,x_m) = H_{i_{\pi_1},\ldots,i_{\pi_m}}(x_{\pi_1},\ldots,x_{\pi_m})$ for any $(x_1,\ldots,x_m)\in \mathcal S^m$ and any permutation $\pi$. For example, when $m=2$, this conditions reads as $H_{i_1,i_2}(x_1,x_2) = H_{i_2,i_1}(x_2,x_1)$ for all $i_1\ne i_2$ and $x_1,x_2$. 
The generalized U-statistic is defined as \cite{Decoupling}
\begin{equation}
\label{u-stat}
U_n:=\sum_{(i_1,\ldots,i_m)\in I_n^m}H_{i_1,\ldots,i_m}(X_{i_1},\ldots,X_{i_m}).
\end{equation} 
When $H_{i_1,\ldots,i_m}\equiv H$, we obtain the classical U-statistics. 
It is often easier to work with the decoupled version of $U_n$ defined as 
\[
U'_n =  \sum_{(i_1,\ldots, i_m)\in I_n^m} H_{i_1,\ldots,i_m}\left( X^{(1)}_{i_1},\ldots,X^{(m)}_{i_m} \right),  
\]
where $\left\{ X_i^{(k)} \right\}_{i=1}^n, \ k=1,\ldots,m$ are independent copies of the sequence $X_1,\ldots,X_n$. 
Our ultimate goal is to obtain the moment and deviation bounds for the random variable $\| U_n  - \mathbb E U_n \|$.   
 
Next, we recall several useful facts about U-statistics.  
The projection operator $\pi_{m,k}~(k\leq m)$ is defined as 
\[
\pi_{m,k}H(\mathbf{x}_{i_1},\ldots,\mathbf{x}_{i_k})
:= (\delta_{\mathbf{x}_{i_1}}- P)\ldots(\delta_{\mathbf{x}_{i_k}} - P) P^{m-k}H,
\]
where 
\[
\mathcal{Q}^mH := \int\ldots\int H(\mathbf{y}_1,\ldots,\mathbf{y}_m)dQ(\mathbf{y}_1)\ldots dQ(\mathbf{y}_m),
\] 
for any probability measure $Q$ on $(\mathcal S,\mathcal{B})$, and $\delta_{x}$ is a Dirac measure concentrated at $x\in \mathcal S$. 
For example, $\pi_{m,1}H(x) = \mathbb E \left[ H(X_1,\ldots,X_m)| X_1=x\right] - \mathbb E H(X_1,\ldots,X_m)$.
\begin{definition}
Let $F: \mathcal S^m\rightarrow\mathbb H^d$ be a measurable function. We will say that $F$ is $P$-degenerate of order $r$ 
($1\leq r<m$) iff 
\[
\mathbb EF(\mathbf{x}_1,\ldots,\mathbf{x}_r,X_{r+1},\ldots,X_m)=0~\forall \mathbf{x}_1,\ldots,\mathbf{x}_r\in \mathcal S,
\]
and $\mathbb E F(\mathbf{x}_1,\ldots,\mathbf{x}_r, \mathbf{x}_{r+1},X_{r+2},\ldots,X_m)$ is not a constant function. 
Otherwise, $F$ is non-degenerate.
\end{definition}
For instance, it is easy to check that $\pi_{m,k}H$ is degenerate of order $k-1$.  
If $F$ is degenerate of order $m-1$, then it is called \emph{completely degenerate}. 
From now on, we will only consider generalized U-statistics of order $m=2$ with completely degenerate (that is, degenerate of order 1) kernels. 
The case of non-degenerate U-statistics is easily reduced to the degenerate case via the \emph{Hoeffding's decomposition;} see page 137 in \cite{Decoupling} for the details. 

	
\section{Main results.}
\label{sec:moment}

Rosenthal-type moment inequalities for sums of independent matrices 
have appeared in a number of previous works, including \cite{chen2012masked, mackey2014matrix, JT-matrix}. For example, the following inequality follows from Theorem A.1 in \cite{chen2012masked}:
\begin{lemma}[Matrix Rosenthal inequality]
\label{lemma:rosenthal-1}
Suppose that $q \geq 1$ is an integer and fix $r\geq q\vee \log d$. Consider a finite sequence of $\{\mathbf{Y}_i\}$ of independent $\mathbb H^d$-valued random matrices. Then
\begin{multline}
\label{iid-rosenthal}
\left(\mathbb E\left\| \sum_i \left( \mathbf{Y}_i -\mathbb E \mathbf{Y}_i \right)\right\|^{2q} \right)^{1/2q}\leq 2\sqrt{er}\left\|  \left(\sum_i \mathbb E 
\left( \mathbf{Y}_i - \mathbb E\mathbf{Y}_i \right)^2 \right)^{1/2}  \right\| 
\\
+4\sqrt{2} er\left( \mathbb E\max_i\|\mathbf{Y}_i - \mathbb E\mathbf{Y}_i \|^{2q} \right)^{1/2q}.
\end{multline}
\end{lemma}
The bound above improves upon the moment inequality that follows from the matrix Bernstein's inequality (see Theorem 1.6.2 in \cite{JT-matrix}):
\begin{lemma}[Matrix Bernstein's inequality]
\label{bernstein}
Consider a finite sequence of $\{\mathbf{Y}_i\}$ of independent $\mathbb H^d$-valued random matrices such that 
$\|\mathbf{Y}_i - \mathbb E\mathbf{Y}_i\|\leq B$ almost surely. Then 
\[
\Pr\left( \left\|  \sum_i \left( \mathbf{Y}_i -\mathbb E\mathbf{Y}_i \right)  \right\| \geq 2\sigma\sqrt{u} + \frac{4}{3}Bu \right)\leq 2de^{-u},
\]
where $\sigma^2:= \left\| \sum_i \mathbb E\left(\mathbf{Y}_i -\mathbb E\mathbf{Y}_i\right)^2 \right\|$. 
\end{lemma}
\noindent Indeed, Lemma \ref{tail-to-moment} implies, with $a_0 = C\left(\sigma\sqrt{\log(2d)} +B\log (2d)\right)$ for some absolute constant $C>0$ and after some simple algebra, that
\[
\left( \mathbb E\left\|  \sum_i \left( \mathbf{Y}_i - \mathbb E\mathbf{Y}_i \right) \right\|^q \right)^{1/q}\leq C_2\left( \sqrt{q+\log(2d)}\,\sigma + (q+\log(2d))B \right),
\]
for an absolute constant $C_2>0$ and all $q\geq1$. 
This bound is weaker than \eqref{iid-rosenthal} as it requires almost sure boundedness of $\|\mathbf{Y}_i - \mathbb E \mathbf{Y}_i\|$ for all $i$. 
One the the main goals of this work is to obtain operator norm bounds similar to inequality \eqref{iid-rosenthal} for $\mathbb H^d$-valued U-statistics of order 2. 


\subsection{Degenerate U-statistics of order 2.}


Moment bounds for scalar U-statistics are well-known, see for example the work \cite{gine2000exponential} and references therein. 
Moreover, in \cite{adamczak2006moment}, author obtained moment inequalities for general Banach-space valued U-statistics. 
Here, we aim at improving these bounds for the special case of $\mathbb H^d$-valued U-statistics of order 2. 
We discuss connections and provide comparison of our results with the bounds obtained by R. Adamczak \cite{adamczak2006moment} in Section \ref{section:adamczak}.


\subsection{Matrix Rademacher chaos.}


The starting point of our investigation is a moment bound for the matrix Rademacher chaos of order 2. 
This bound generalizes the spectral norm inequality for the matrix Rademacher series, see \cite{JT-matrix, tropp2016expected, tropp2016second,random-matrix-2010}.
We recall Khintchine's inequality for the matrix Rademacher series for the ease of comparison: let $A_1,\ldots,A_n\in\mathbb{H}^{d}$ be a sequence of fixed matrices, and $\varepsilon_1,\ldots,\varepsilon_n$ -- a sequence of i.i.d. Rademacher random variables. Then
\begin{align}
\label{matrix-Khintchine}
&
\left( \mathbb E\left\|\sum_{i=1}^n\varepsilon_i A_i\right\|^2 \right)^{1/2}\leq \sqrt{e(1+2\log d)}\cdot
\left\| \sum_{i=1}^n A_i^2 \right\|^{1/2}.
\end{align}
Furthermore, Jensen's inequality implies this bound is tight (up to a logarithmic factor). 
Note that the expected norm of $\sum \varepsilon_i A_i$ is controlled by the single ``matrix variance'' parameter  $\left\| \sum_{i=1}^n A_i^2 \right\|$. 
Next, we state the main result of this section, the analogue of inequality \eqref{matrix-Khintchine} for the Rademacher chaos of order 2.
\begin{lemma}
\label{bound-on-expectation}
Let $\{A_{i_1,i_2}\}_{i_1,i_2=1}^{n}\in \mathbb H^d$ be a sequence of fixed matrices.
Assume that $\left\{\varepsilon_j^{(i)}\right\}_{j\in\mathbb{N}}, \ i=1,2,$ are two independent sequences of i.i.d. Rademacher random variables, and define
\[
X= \sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)}.
\]
Then for any $q\geq1$,
\begin{multline}
\label{eq:khintchine}
\max\left\{\left\|GG^\ast \right\|,  \left\| \sum_{(i_1,i_2)\in I_n^2}A_{i_1,i_2}^2 \right\| \right\}^{1/2}
\leq \left( \mathbb E\|X\|^{2q}\right)^{1/(2q)} \\
\leq
\frac{4}{\sqrt{e}}\cdot r\cdot\max\left\{  \left\| GG^\ast \right\|, \left\| \sum_{(i_1,i_2)\in I_n^2}A_{i_1,i_2}^2 \right\| \right\}^{1/2},
\end{multline}
where $r:= q \vee\log d$, and the matrix $G\in\mathbb{H}^{nd}$ is defined via its block structure as
\begin{equation}
\label{eq:G}
G:=
\left(
\begin{array}{cccc}
0  & A_{1,2}  & \ldots & A_{1,n}  \\
A_{2,1}  & 0  & \ldots & A_{2,n}  \\
\vdots  & \vdots  &   \ddots & \vdots \\
A_{n,1} & A_{n,2} & \ldots & 0 
\end{array}
\right).
\end{equation}
\end{lemma}

\begin{remark}[Constants in Lemma \ref{bound-on-expectation}]
\label{remark:log-constant}
Matrix Rademacher chaos of order 2 has been studied previously in \cite{rauhut2009circulant}, \cite{pisier1998non} and \cite{HR-CS}, where Schatten-$p$ norm upper bounds were obtained by iterating Khintchine's inequality for Rademacher series. Specifically, the following bound holds for all $p\geq 1$ (see Lemma \ref{k-inequality-2} for the details):
\begin{align*}
&
\mathbb E\left\| X \right\|_{S_{2p}}^{2p}
\leq
2\left( \frac{2\sqrt 2}{e} p\right)^{2p}
\max\left\{  \left\|  \left(G  G^\ast \right)^{1/2}\right\|_{S_{2p}}^{2p}, \left\|\left(\sum_{i_1,i_2=1}^n A_{i_1,i_2}^2\right)^{1/2}\right\|_{S_{2p}}^{2p} \right\}.
\end{align*}
Using the fact that for any $B\in\mathbb{H}^{d}$, $\|B\|\leq\|B\|_{S_{2p}}\leq d^{1/2p}\|B\|$
and taking $p=q\vee \log(nd)$, one could obtain a ``na\"{i}ve'' extension of the inequality above, namely
\begin{align*}
&
\left( \mathbb E\|X\|^{2q}\right)^{1/(2q)}\leq
C\max\left( q,\log(nd) \right) \max\left\{  \left\| GG^\ast \right\|, \left\|\sum_{(i_1,i_2)\in I^n_2}A_{i_1,i_2}^2\right\| \right\}^{1/2}
\end{align*}
that contains an extra $\log(n)$ factor which is removed in Lemma \ref{bound-on-expectation}. 
\end{remark}


One may wonder if the term $\left\| GG^\ast \right\|$ in Lemma \ref{bound-on-expectation} is redundant. 
For instance, in the case when $\{A_{i_1,i_2}\}_{i_1,i_2}$ are scalars, it is easy to see 
$\left\| \sum_{(i_1,i_2)\in I_n^2 } A_{i_1,i_2}^2\right\|\geq\left\| GG^\ast \right\|$. 
However, a more careful examination shows that there is no strict dominance among $\left\| GG^\ast \right\|$ and 
$\left\| \sum_{(i_1,i_2)\in I_n^2 } A_{i_1,i_2}^2\right\|$. 
The following example presents a situation where $\left\| \sum_{(i_1,i_2)\in I_n^2 } A_{i_1,i_2}^2\right\|<\left\| GG^\ast \right\|$.
\begin{example}
\label{example:01}
Assume that $d~\geq~n~\geq~2$, let 
$\{\mathbf{a}_1,\ldots,\mathbf{a}_d\}$ be any orthonormal basis in $\mathbb{R}^d$, 
and $\mathbf{a}:=[\mathbf{a}_1^T,\ldots,\mathbf{a}_n^T]^T \in \mathbb R^{nd}$ be the ``vertical concatenation'' of $\mathbf{a}_1,\ldots,\mathbf{a}_d$. 
Define
\[
A_{i_1,i_2} := \mathbf{a}_{i_1}\mathbf{a}_{i_2}^T + \mathbf{a}_{i_2}\mathbf{a}_{i_1}^T,
~~i_1,i_2\in\{1,2,\ldots,n\},
\]
and
\[
X:= \sum_{(i_1,i_2)\in I_n^2} \varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)}
A_{i_1,i_2}.
\]
Then $\left\| GG^\ast \right\|  = \left\| GG^T \right\| \geq (n-2) \| \mathbf{a}\|_{2}^2 = (n-2)n$, and 
$\left\|  \sum_{(i_1,i_2)\in I_n^2}  A_{i_1,i_2}^2 \right\| = 2(n-1)$. 
Details are outlined in Section \ref{section:example-proof}.
\end{example}
\noindent It follows from Lemma \ref{lemma:block-matrix} that 
\begin{align}
\label{eq:useful-bound}
&
\left\| GG^\ast \right\| \leq \sum_{i_1}\left\| \sum_{i_2: i_2\ne i_1} A^2_{i_1,i_2}\right\|.
\end{align}
Often, this inequality yields a ``computable'' upper bound for the right-hand side of the inequality \eqref{eq:khintchine}, however, in some cases it results in the loss of precision, as the following example demonstrates.
\begin{example}
\label{example:02}
Assume that $n$ is even, $d~\geq~n~\geq~2$, let 
$\{\mathbf{a}_1,\ldots,\mathbf{a}_d\}$ be an orthonormal basis in $\mathbb{R}^d$, and let $\mathcal C\in \mathbb R^{n\times n}$ be an orthogonal matrix with entries $c_{i,j}$ such that $c_{i,i}=0$ for all $i$. Define 
\[
A_{i_1,i_2}= c_{i_1,i_2}\left(\mathbf{a}_{i_1}\mathbf{a}_{i_2}^T + \mathbf{a}_{i_2}\mathbf{a}_{i_1}^T \right),
~~i_1,i_2\in\{1,2,\ldots,n\},
\]
and $X:= \sum_{(i_1,i_2)\in I_n^2} \varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)} A_{i_1,i_2}.$ 
Then $\left\| GG^\ast \right\| = 1$, $\left\|  \sum_{(i_1,i_2)\in I_n^2}  A_{i_1,i_2}^2 \right\| = 2$, but 
\[
\sum_{i_1} \left\| \sum_{i_2:i_2\neq i_1}A_{i_1,i_2}^2\right\| = n.
\] 
Details are outlined in Section \ref{section:example-proof}.
\end{example}




\subsection{Moment inequalities for degenerate U-statistics of order 2.}
\label{sec:main-results}

Let $H_{i_1,i_2}:\mathcal{S}\times \mathcal{S}\mapsto \mathbb H^d$, $(i_1,i_2)\in I_n^2$, be a sequence of degenerate kernels, for example, $H_{i_1,i_2}(x_1,x_2)=\pi_{2,2}\widehat H_{i_1,i_2}(x_1,x_2)$ for some non-degenerate permutation-symmetric $\widehat H_{i_1,i_2}$. 
Recall that $U_n$, the generalized U-statistic of order 2, has the form 
\[
U_n:=\sum_{(i_1,i_2)\in I_n^2}H_{i_1,i_2}(X_{i_1},X_{i_2}).
\]
Everywhere below, $\mathbb E_j[\cdot], \ j=1,2,$ stands for the expectation with respect to $\left\{X_i^{(j)}\right\}_{i=1}^n$ only (that is, conditionally on all other random variables). 
The following Theorem is our most general result; it can be used as a starting point to derive more refined bounds. 
\begin{theorem}
\label{thm:degen-moment}
Let $\left\{X_i^{(j)}\right\}_{i=1}^n, \ j=1,2,$ be $\mathcal{S}$-valued i.i.d. random variables, $H_{i,j}:\mathcal{S}\times \mathcal{S}\mapsto \mathbb H^d$ -- permutation-symmetric degenerate kernels. Then for all $q \geq 1$ and $r=\max(q ,\log (ed))$,
\begin{align*}
\left(\mathbb E \left\| U_n \right\|^{2q}  \right)^{1/2q}
\leq  &
4 \left(\mathbb E \left\| \sum_{(i_1,i_2)\in I^2_n} H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{2q}\right)^{1/2q} 
\\ 
\leq &
128/\sqrt{e} \Bigg[
16 r^{3/2} \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1 } H^2_{i_1,i_2} \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)} 
\\
&
+ r  \left\| \sum_{(i_1,i_2)\in I_n^2 } \mathbb E H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{1/2}  
+ r\left( \mathbb E\left\|   \mathbb E_2 \widetilde G \widetilde G^\ast \right\|^{q}\right)^{1/2q} \Bigg],
\end{align*}
where the matrix $\widetilde G\in \mathbb H^{n d}$ is defined as
\begin{align}
\label{eq:g}
&
\widetilde G:=
\left(
\begin{array}{cccc}
0  & H_{1,2}\left(X_{1}^{(1)}, X_{2}^{(2)} \right)  & \ldots & H_{1,n}\left(X_{1}^{(1)}, X_{n}^{(2)} \right)  \\
H_{2,1}\left(X_{2}^{(1)}, X_{1}^{(2)} \right)  & 0  & \ldots & H_{2,n}\left(X_{2}^{(1)}, X_{n}^{(2)} \right)  \\
\vdots  & \vdots  &   \ddots & \vdots \\
H_{n,1}\left(X_{n}^{(1)}, X_{1}^{(2)} \right) & H_{n,2}\left(X_{n}^{(1)}, X_{2}^{(2)} \right) & \ldots & 0 
\end{array}
\right).
\end{align}
\end{theorem}
\begin{proof}
See Section \ref{proof:degen-moment}. 
\end{proof}


The following lower bound (proven in Section \ref{proof:lower}) demonstrates that all the terms in the bound of Theorem \ref{thm:degen-moment} are necessary.
\begin{lemma}
\label{lemma:degen-lower-bound}
Under the assumptions of Theorem \ref{thm:degen-moment},
\begin{multline*}
\left(\mathbb E \left\| U_n \right\|^{2q}  \right)^{1/2q} \geq 
C \left[
\left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)} \right.
\\
\left.+   \left( \mathbb E\left\| \mathbb E_2 \widetilde G \widetilde G^\ast \right\|^{q}\right)^{1/2q} + 
\left( \mathbb E\left\| \sum_{(i_1,i_2)\in I_n^2 } \mathbb E_2 H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{q} \right)^{1/2q}\right]
\end{multline*}
where $C>0$ is an absolute constant.
\end{lemma}
\begin{example}
Let $\{ A_{i_1,i_2} \}_{1\leq i_1<i_2\leq n}$ be fixed elements of $\mathbb H^d$ and $X_1,\ldots,X_n$ -- centered i.i.d. real-valued random variables such that $\mbox{Var}(X_1)=1$. Consider $\mathbf{Y}:=\sum_{i_1\ne i_2} A_{i_1,i_2} X_{i_1}X_{i_2}$, where $A_{i_2,i_1}=A_{i_1,i_2}$ for $i_2>i_1$. 
We will apply Theorem \ref{thm:degen-moment} to obtain the bounds for $\left( \mathbb E\|\mathbf{Y}\|^{2q} \right)^{1/2q}$. In this case, $H_{i_1,i_2} \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) = A_{i_1,i_2}X_{i_1}^{(1)} X_{i_2}^{(2)}$, and it is easy to see that
\[
\left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1 } H^2_{i_1,i_2} \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)} \leq 
\max_i \left\| \sum_{j\ne i} A^2_{i,j}\right\|^{1/2} \left( \mathbb E\max_{1\leq i\leq n} |X_i|^{2q}  \right)^{1/q}
\]
and $ \left\| \sum_{(i_1,i_2)\in I_n^2 } \mathbb E H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{1/2} = \left\| \sum_{(i_1,i_2)\in I_n^2} A^2_{i_1,i_2}\right\|^{1/2}$. Moreover,  
\[
\left( \mathbb E_2 \widetilde G \widetilde G^\ast \right)_{i,j} = X_i^{(1)} X_j^{(1)}\sum_{k\ne i,j} A_{i,k} A_{j,k},
\] 
implying that $\mathbb E_2 \widetilde G \widetilde G^\ast  = D \, G \, D$, where $G$ is defined as in \eqref{eq:G} and $D\in \mathbb H^{n d}$ is a diagonal matrix $D = \mathrm{diag}(X_1^{(1)},\ldots,X_n^{(1)}) \otimes I_d$, where $\otimes$ denotes the Kronecker product. 
It yields that $\left\| \mathbb E_2 \widetilde G \widetilde G^\ast \right\| \leq \max_i \left| X_i^{(1)} \right|^2 \cdot \left\| G G^\ast\right\|$, hence 
\[
\left( \mathbb E\left\|  \mathbb E_2 \widetilde G \widetilde G^\ast \right\|^{q}\right)^{1/2q} \leq \left\| G G^\ast\right\|^{1/2} \left( \mathbb E\max_{1\leq i\leq n} |X_i|^{2q}  \right)^{1/2q}.
\]
Combining the inequalities above, we deduce from Theorem \ref{thm:degen-moment} that 
\begin{multline}
\label{eq:polynomial}
\left( \mathbb E\|\mathbf{Y}\|^{2q} \right)^{1/2q} \leq C\Bigg[ r \left( \left\| \sum_{(i_1,i_2)\in I_n^2} A^2_{i_1,i_2}\right\|^{1/2} + \left( \mathbb E\max_{1\leq i\leq n} |X_i|^{2q}  \right)^{1/2q} \left\| GG^\ast \right\|^{1/2} \right) \\
+ r^{3/2} \max_{i_1} \left\| \sum_{i_2\ne i_1} A^2_{i_1,i_2}\right\|^{1/2} \left( \mathbb E\max_{1\leq i\leq n} |X_i|^{2q}  \right)^{1/q} \Bigg],
\end{multline}
where $r = \max(q,\log (ed))$. If for instance $|X_1|\leq M$ almost surely for some $M\geq 1$, it follows that 
\begin{equation*}
\left( \mathbb E\|\mathbf{Y}\|^{2q} \right)^{1/2q} \leq C\Bigg[ r \left( M \, \left\| GG^\ast \right\|^{1/2} + \left\| \sum_{(i_1,i_2)\in I_n^2} A^2_{i_1,i_2}\right\|^{1/2} \right)
+ r^{3/2} M^2 \max_{i_1} \left\| \sum_{i_2\ne i_1} A^2_{i_1,i_2}\right\|^{1/2} \Bigg].
\end{equation*}
On the other hand, if $X_1$ is not bounded but is sub-Gaussian, meaning that $\left(\mathbb E|X_1|^q \right)^{1/q} \leq C \sigma \sqrt{q}$ for all $q\in \mathbb N$ and some $\sigma>0$, then it is easy to check that 
\[
\left(\mathbb E\max_{1\leq i\leq n} |X_i|^{2q}\right)^{1/2q} \leq C_1 \sqrt{\log(n)} \sigma \sqrt{2q},
\]
and the estimate for $\left(\mathbb E \left\|\mathbf{Y} \right\|^{2q}\right)^{1/2q}$ follows from \eqref{eq:polynomial}.
\end{example}


Our next goal is to obtain more ``user-friendly'' versions of the upper bound, and we first focus on the term 
$ \mathbb E \big\| \mathbb E_2 \widetilde G \widetilde G^\ast \big\|^q$ appearing in Theorem \ref{thm:degen-moment} that might be difficult to deal with directly.  
It is easy to see that the $(i,j)$-th block of the matrix $\mathbb E_2 \widetilde G\widetilde G^\ast$ is 
\[
\left( \mathbb E_2 \widetilde G \widetilde G^\ast\right)_{i,j} = \sum_{k\ne i,j} \mathbb E_2 \left[ H_{i,k}(X_i^{(1)},X_k^{(2)}) H_{j,k}(X_j^{(1)},X_k^{(2)})\right].
\]
It follows from Lemma \ref{lemma:block-matrix} that
\begin{align}
\label{eq:d20}
\| \mathbb E_2 \widetilde G \widetilde G^\ast \| & \leq \sum_{i}  \left\| \left( \mathbb E_2 \widetilde G \widetilde G^\ast\right)_{i,i}\right\| = 
\sum_{i_1}  \left\| \sum_{i_2:i_2\ne i_1}\mathbb E_2 H_{i_1,i_2}^2\left(X^{(1)}_{i_1}, X_{i_2}^{(2)}\right) \right\|, 
\end{align}
hence 
\begin{multline*}
\left( \mathbb E\left\| \mathbb E_2\widetilde G \widetilde G^\ast \right\|^{q}\right)^{1/2q}\leq 
\left( \mathbb E \left( \sum_{i_1} \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left(X^{(1)}_{i_1}, X_{i_2}^{(2)}\right) \right\| \right)^q \right)^{1/2q} 
\\ 
\leq \left( \sum_{i_1}\mathbb E\left\|  \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left( X^{(1)}_{i_1}, X_{i_2}^{(2)}\right)\right\| \right)^{1/2}  \\
+ 2\sqrt{2eq} \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left( X^{(1)}_{i_1}, X_{i_2}^{(2)}\right)\right\|^q \right)^{1/2q},
\end{multline*}
where we used Rosenthal's inequality (Lemma \ref{lemma:rosenthal-pd} applied with $d=1$) in the last step. 
Together with the fact that $\left\| \mathbb E H^2\left( X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \leq \mathbb E\left\| \mathbb E_2 H^2\left( X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|$ for all $i_1,i_2$, and the inequality
\[
\left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left( X^{(1)}_{i_1}, X_{i_2}^{(2)}\right)\right\|^q \right)^{1/2q}
\leq
\left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)}, 
\]
we obtain the following result.
\begin{corollary}
\label{cor:simple}
Under the assumptions of Theorem \ref{thm:degen-moment}, 
\begin{align*}
\left(\mathbb E \left\| U_n\right\|^{2q}  \right)^{1/2q}
\leq &
256/\sqrt{e}\Bigg[
r  \left( \sum_{i_1}\mathbb E\left\|  \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left( X^{(1)}_{i_1}, X_{i_2}^{(2)}\right)\right\| \right)^{1/2}
\\
&
+ 11 \, r^{3/2}\left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)} 
\Bigg].
\end{align*}

\end{corollary}

\begin{remark}
Assume that $H_{i,j} = H$ is independent of $i,j$ and is such that $\|H(x_1,x_2)\|\leq M$ for all $x_1,x_2\in S$. 
Then
\[
\mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q 
\leq (n-1)^q M^{2q},
\]
and it immediately follows from Lemma \ref{moment-to-tail} and Corollary \ref{cor:simple} that for all $t\geq 1$ and an absolute constant $C>0$, 
\begin{align}
\label{eq:concentration}
&
\Pr\left( \left\| U_n \right\| \geq C\left( \sqrt{ \mathbb E\left\| \mathbb E_2 H^2(X_1^{(1)},X_2^{(2)})\right\| }\,\left(t+\log d\right)\cdot n + M\sqrt{n} \left(t+\log d\right)^{3/2}  \right) \right)\leq e^{-t}.
\end{align}
\end{remark}

\noindent Next, we obtain further refinements of the result that follow from estimating the term 
\[
r^{3/2}\left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)} .
\]
\begin{lemma}
\label{lemma:remainder}
Under the assumptions of Theorem \ref{thm:degen-moment}, 
\begin{multline*}
r^{3/2} \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)} \\
\leq 
4e\sqrt{2} \sqrt{1 + \frac{\log d}{q}} \Bigg[  r \left( \sum_{i_1} \mathbb E \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|\right)^{1/2} 
\\
+ r^{3/2}\left(  \mathbb E\max_{i_1}\left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/2q}
\\ 
+ r^2 \left( \sum_{i_1}\mathbb E\max_{i_2:i_2\ne i_1} \left\|  H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/2q}
\Bigg].
\end{multline*}
\end{lemma}
\begin{proof}
See Section \ref{proof:extraterm}.
\end{proof}


One of the key features of the bounds established above is the fact that they yield estimates for $\mathbb E \left\| U_n \right\|$: for example, 
Theorem \ref{thm:degen-moment} implies that 
\begin{align}
\label{eq:mom1}
\nonumber
\mathbb E\left\| U_n \right\|  \leq \,& C\log d\bigg( \left( \mathbb E \left\| \mathbb E_2 \widetilde G \widetilde G^\ast \right\| \right)^{1/2} + 
 \left\| \sum_{(i_1,i_2)\in I_n^2 } \mathbb E H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{1/2} \\
&
+\sqrt{\log d} \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1 } H^2_{i_1,i_2} \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \right)^{1/2}\Bigg)
\end{align}
for some absolute constant $C$. 
On the other hand, direct application of the non-commutative Khintchine's inequality \eqref{matrix-Khintchine} followed by Rosenthal's inequality (Lemma \ref{lemma:rosenthal-pd}) only gives that 
\begin{align}
\label{eq:mom3}
\nonumber
\mathbb E\left\| U_n \right\| \leq &C \log d \left( \sum_{i_1} \mathbb E\left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \right)^{1/2} 
\\
\leq & C\log d \Bigg( \left(\sum_{i_1} \mathbb E \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \right)^{1/2} 
\\ \nonumber
&+ \sqrt{\log d}\left( \sum_{i_1}\mathbb E \max_{i_2: i_2\ne i_1} \left\| H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|\right)^{1/2} \Bigg),
\end{align}
and it is easy to see that the right-hand side of \eqref{eq:mom1} is never worse than the bound \eqref{eq:mom3}. 
To verify that it can be strictly better, consider the framework of Example \ref{example:02}, where it is easy to check  (following the same calculations as those given in Section \ref{section:example-proof}) that
\begin{multline*}
 \left( \mathbb E \left\| \mathbb E_2 \widetilde G \widetilde G^\ast \right\| \right)^{1/2} = 1, \
 \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1 } H^2_{i_1,i_2} \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \right)^{1/2} = 1, 
 \\
 \left\| \sum_{(i_1,i_2)\in I_n^2 } \mathbb E H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{1/2} = 2 , 
\end{multline*}
while $\left(\sum_{i_1} \mathbb E \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H^2_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \right)^{1/2} = \sqrt{n}.$
\begin{remark}[Extensions to rectangular matrices]
All results in this section can be extended to the general case of $\mathbb C^{d_1\times d_2}$ - valued kernels by considering 
the Hermitian dilation $\mathcal D(U_n)$ of $U_n$ as defined in \eqref{eq:dilation}, namely
\[
\mathcal D(U_n) = \sum_{(i_1,i_2)\in I_n^2} \mathcal D\left( H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)} \right) \right) \in \mathbb H^{d_1+d_2},
\]
and observing that $\|U_n\| = \left\| \mathcal D(U_n)\right\|$. 
\end{remark}





\section{Adamczak's moment inequality for U-statistics.}
\label{section:adamczak}

The paper \cite{adamczak2006moment} by R. Adamczak developed moment inequalities for general Banach space-valued completely degenerate U-statistics of arbitrary order. 
More specifically, application of Theorem 1 in \cite{adamczak2006moment} to our scenario $\mathbb{B} = \left(\mathbb{H}^{d},~\|\cdot\|\right)$ and $m=2$ yields the following bounds for all $q\geq 1$ and $t\geq 2$:
\begin{align}
\label{adam-1}
&
\left( \mathbb E\| U_n \|^{2q} \right)^{1/(2q)} 
\leq C \Bigg( \mathbb E \left\| U_n \right\| 
+ \sqrt{q}\cdot A + q \cdot B 
+ q^{3/2}\cdot \Gamma + q^2\cdot D \Bigg), \\
& 
\nonumber
\Pr\left( \|U_n\| \geq C \left( \mathbb E \left\| U_n \right\| +  \sqrt{t}\cdot A + t \cdot B 
+ t^{3/2}\cdot \Gamma + t^2\cdot D\right) \right)\leq e^{-t},
\end{align} 
where $C$ is an absolute constant, and the quantities $A,B,\Gamma,D$ will be specified below (see Section \ref{section:adamczak-calculations} for the complete statement of Adamczak's result). 
Notice that inequality \eqref{adam-1} contains the ``sub-Gaussian'' term corresponding to $\sqrt{q}$ that did not appear in the previously established bounds. 

We should mention another important distinction between \eqref{adam-1} and the results of Theorem \ref{thm:degen-moment} and its corollaries, such as inequality \eqref{eq:concentration}: while \eqref{adam-1} describes the deviations of $\| U_n \|$ from its expectation, \eqref{eq:concentration} states that $U_n$ is close to its expectation \emph{as a random matrix}; similar connections exist between the Matrix Bernstein inequality \cite{tropp2012user} and Talagrand's concentration inequality \cite{boucheron2013concentration}. 
It particular, \eqref{adam-1} can be combined with a bound \eqref{eq:mom1} for $\mathbb E\| U_n \|$ to obtain a moment inequality that is superior (in a certain range of $q$) to the results derived from Theorem \ref{thm:degen-moment}. 
\begin{theorem}
\label{thm:adamczak}
Inequalities \eqref{adam-1} hold with the following choice of $A,B,\Gamma$ and $D$:
\begin{align*}
A = &
\sqrt{\log(de)} \left( \mathbb E\left\|  \mathbb E_2 \widetilde G \widetilde G^\ast \right\| +  
\left\|  \sum_{(i_1,i_2)\in I_n^2} \mathbb E H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)} \right)\right\| \right)^{1/2} \\
& +\log (de) \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \right)^{1/2},
\\ 
B  = &  \left(  \sup_{z\in \mathbb C^d:\| z \|_2\leq 1}  \sum_{(i_1,i_2)\in I_n^2} \mathbb E\left( z^\ast H_{i_1,i_2}\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) z  \right)^2\right)^{1/2} 
\\
&\leq \left(\left\| \sum_{(i_1,i_2)\in I_n^2} \mathbb E H_{i_1,i_2}^2(X^{(1)}_{i_1},X^{(2)}_{i_2})\right\| \right)^{1/2},  
\\
\Gamma = & \,\sqrt{1+\frac{\log d}{q}} \left( \sum_{i_1}\, \mathbb E_1 \left\| \sum_{i_2: i_2\ne i_1} \mathbb E_2  H_{i_1,i_2}^2\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\|^{q} \right)^{1/2q}, 
\\
D = & \left( \sum_{(i_1,i_2)\in I_n^2} \mathbb E\left\| H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{q} \right)^{1/(2q)}
\\
&+ \left( 1 + \frac{\log d}{q} \right)\left( \sum_{i_1}\,\mathbb E \max_{i_2: i_2\ne i_1} \left\| H^2_{i_1,i_2}\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right)\right\|^{q}\right)^{1/2q},
\end{align*}
where $\widetilde G_i$ were defined in \eqref{eq:g}.
\end{theorem}
\begin{proof}
See Section \ref{section:adamczak-calculations}.
\end{proof}
\noindent It is possible to further simplify the bounds for $A$ (via Lemma \ref{lemma:remainder}) and $D$ to deduce that one can choose 
\begin{align}
\nonumber
A = &
\log(de) \left( \mathbb E\left\|   \mathbb E_2 \widetilde G \widetilde G^\ast \right\| +  
\left\|  \sum_{(i_1,i_2)\in I_n^2} \mathbb E H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)} \right)\right\| \right)^{1/2}, 
\\
\nonumber
B  = &   \left(  \sup_{z\in \mathbb C^d:\| z \|_2\leq 1}  \sum_{(i_1,i_2)\in I_n^2} \mathbb E\left( z^\ast H_{i_1,i_2}\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) z  \right)^2\right)^{1/2}, 
\\
\nonumber
\Gamma = & \,(\log(de))^{3/2} \left( \sum_{i_1}\, \mathbb E_1 \left\| \sum_{i_2: i_2\ne i_1} \mathbb E_2  H_{i_1,i_2}^2\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\|^{q} \right)^{1/2q}, 
\\
\label{eq:adam-simplified}
D = & \log(de)\left( \sum_{(i_1,i_2)\in I_n^2} \mathbb E\left\| H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{q} \right)^{1/(2q)}.
\end{align}
The upper bound for $A$ can be modified even further as in \eqref{eq:d20}, using the fact that
\[
\mathbb E\left\| \mathbb E_2 \widetilde G \widetilde G^\ast \right\| \leq
\sum_{i_1} \mathbb E \left\| \sum_{i_2:i_2\ne i_1}\mathbb E_2 H_{i_1,i_2}^2\left(X^{(1)}_{i_1}, X_{i_2}^{(2)}\right) \right\|.
\]

	\begin{comment}

\begin{remark}
We note that all results obtained in this paper can be easily extended to the case of Hilbert space-valued U-statistics.
Indeed, assume that $H_{i_1,i_2}:=H_{i_1,i_2}\left(X_{i_1}^{(1)}, X_{i_2}^{(2)} \right) \in \mathbb C^d$ and note that the Hermitian dilation of $H_{i_1,i_2}$ satisfies
\[
\mathcal D^2\left( H_{i_1,i_2} \right) = \begin{pmatrix}
H_{i_1,i_2} H_{i_1,i_2}^\ast & 0 \\
0 & H_{i_1,i_2}^\ast H_{i_1,i_2} 
\end{pmatrix},
\]
hence $\left\| \mathcal D^2\left( H_{i_1,i_2}\right) \right\| = \left\| H_{i_1,i_2}\right\|^2_2$.
\end{remark}

	\end{comment}
	
 	\begin{comment}


\section{Bounds for vector-valued U-statistics. REMOVE}
\label{section:vector}

In this section, we show that obtained results easily adapt to the case of Hilbert space-valued U-statistics, that is, when $H_{i_1,i_2}\in \mathbb C^d$ for all $i_1,i_2$; for brevity, we will write $H_{i_1,i_2}$ for $H_{i_1,i_2}\left(X_{i_1}^{(1)}, X_{i_2}^{(2)} \right)$. 
Note that the Hermitian dilation of $H_{i_1,i_2}$ satisfies
\[
\mathcal D^2\left( H_{i_1,i_2} \right) = \begin{pmatrix}
H_{i_1,i_2} H_{i_1,i_2}^\ast & 0 \\
0 & H_{i_1,i_2}^\ast H_{i_1,i_2} 
\end{pmatrix},
\]
hence $\left\| \mathcal D^2\left( H_{i_1,i_2}\right) \right\| = \left\| H_{i_1,i_2}\right\|^2_2$ and 
\begin{align*}
\sum_{i_1}\mathbb E \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2  \mathcal D^2\left( H_{i_1,i_2}\right) \right\| &= 
\Bigg\| \sum_{(i_1,i_2)\in I_n^2} \mathbb E  \mathcal D^2\left( H_{i_1,i_2}\right) \Bigg\|
= \mathbb E \sum_{(i_1,i_2)\in I_n^2} \left\| H_{i_1,i_2} \right\|_2^2. 
\end{align*} 
Moreover, it is easy to see that 
\[
\mathbb E\max_{i_1}\left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 \mathcal D^2\left( H_{i_1,i_2} \right) \right\|^q 
= \mathbb E \max_{i_1} \left( \sum_{i_2:i_2\ne i_1} \mathbb E_2 \left\| H_{i_1,i_2} \right\|_2^2 \right)^q
\]
and $\sum_{i_1}\mathbb E\max_{i_2:i_2\ne i_1} \left\|  \mathcal D^2\left( H_{i_1,i_2} \right) \right\|^q = \sum_{i_1} \mathbb E\max_{i_2:i_2\ne i_1}\left\| H_{i_1,i_2} \right\|_2^{2q}$. 
Theorem \ref{thm:degen-moment} and Lemma \ref{lemma:remainder} imply that for all $q\geq 1$ and $r=q\vee \log d$, 
\begin{multline*}
\left( \mathbb E \left\| U_n \right\|_2^{2q} \right)^{1/2q} \leq 
C\sqrt{1+\frac{\log d}{q}} \Bigg[
r  \left( \mathbb E \sum_{(i_1,i_2)\in I_n^2} \left\| H_{i_1,i_2} \right\|_2^2 \right)^{1/2}   \\
+r^{3/2} \left( \mathbb E \max_{i_1} \left( \sum_{i_2:i_2\ne i_1} \mathbb E_2 \left\| H_{i_1,i_2} \right\|_2^2 \right)^q \right)^{1/(2q)} 
+r^2 \left(   \sum_{i_1} \mathbb E\max_{i_2:i_2\ne i_1}\left\| H_{i_1,i_2} \right\|_2^{2q} \right)^{1/2q}\Bigg]. 
\end{multline*}
If moreover $m,M$ are such that $\left\| H_{i_1,i_2} \right\|_2\leq M$ and $\sqrt{\mathbb E_2 \left\| H_{i_1,i_2} \right\|_2^2}\leq m$ almost surely for all $i_1,i_2$, then Lemma \ref{moment-to-tail} implies that for an absolute constant $C>0$ and all $t\geq 1$, 
\begin{multline}
\label{eq:exp1}
\Pr\Bigg( \left\| U_n \right\|_2 \geq C\sqrt{1+\log(d)/t}\Bigg(\left( \mathbb E \sum_{(i_1,i_2)\in I_n^2} \left\| H_{i_1,i_2} \right\|_2^2 \right)^{1/2} 
(t+\log d)  \\
+ m \sqrt{n} (t^{3/2}+\log^{3/2}(d)) + M n^{1/2t} (t^2 + \log^{2} d) 
 \Big) \Bigg) 
\leq e^{-t}.
\end{multline}
To provide comparison and illustrate the improvements achievable via Theorem \ref{thm:adamczak}, observe that \eqref{eq:adam-simplified} and Lemma \ref{moment-to-tail} imply (after some simple algebra) the following bound for all $t\geq 1$:  
\begin{multline*}
\Pr\Bigg( \left\| U_n \right\|_2 \geq C\Bigg(\log(de)\left( \mathbb E \sum_{(i_1,i_2)\in I_n^2} \left\| H_{i_1,i_2} \right\|_2^2 \right)^{1/2}\sqrt{t}  + 
\left\| \mathbb E \sum_{(i_1,i_2)\in I_n^2} H_{i_1,i_2}H_{i_1,i_2}^\ast \right\|^{1/2} t \\
+ m \sqrt{n} \log^{3/2}(de) \, t^{3/2} + M \log(de) n^{1/2t} \,t^2
 \Big) \Bigg) 
\leq e^{-t},
\end{multline*}
which is better than \eqref{eq:exp1} for small values of $t$.

	\end{comment}



\section{Proofs.}
\label{sec:proof}

\subsection{Tools from probability theory and linear algebra.}

This section summarizes several facts that will be used in our proofs. 
The first inequality is a bound connecting the norm of a matrix to the norms of its blocks.
\begin{lemma}
\label{lemma:block-matrix}
Let $M\in \mathbb H^{d_1+ d_2}$ be nonnegative definite and such that 
$M=\begin{pmatrix}
A & X \\
X^\ast & B
\end{pmatrix}
$, where $A\in \mathbb H^{d_1}$ and $B\in \mathbb H^{d_2}$. 
Then 
\[
\vvvert M \vvvert\leq \vvvert A \vvvert + \vvvert B \vvvert
\]
for any unitarily invariant norm $\vvvert \cdot \vvvert$.
\end{lemma}
\begin{proof}
It follows from the result in \cite{bourin2012unitary} that under the assumptions of the lemma, there exist unitary operators $U,V$ such that 
\[
\begin{pmatrix}
A & X \\
X^\ast & B
\end{pmatrix} = 
U \begin{pmatrix}
A & 0 \\
0 & 0
\end{pmatrix} U^\ast +
V\begin{pmatrix}
0 & 0 \\
0 & B
\end{pmatrix} V^\ast,
\]
hence the result is a consequence of the triangle inequality. 
\end{proof}


The second result is the well-known decoupling inequality for U-statistics due to de la Pena and Montgomery-Smith \cite{PM-decoupling-1995}.
\begin{lemma}
\label{decoupling-lemma}
Let $\{X_i\}_{i=1}^n$ be a sequence of independent random variables with values in a measurable space $(S,\mathcal{S})$, and let $\{X_i^{(k)}\}_{i=1}^n$, $k=1,2,\ldots,m$ be $m$ independent copies of this sequence. 
Let $B$ be a separable Banach space and, for each $(i_1,\ldots,i_m)\in I^m_n$, let $H_{i_1,\ldots,i_m}: S^m\rightarrow B$ be a measurable function.  
Moreover, let $\Phi:[0,\infty)\rightarrow[0,\infty)$ be a convex nondecreasing function such that 
\[
\mathbb E\Phi(\|H_{i_1,\ldots,i_m}(X_{i_1},\ldots, X_{i_m})\|) < \infty 
\] 
for all $(i_1,\ldots,i_m)\in I^m_n$. Then
\begin{multline*}
\mathbb E\Phi\left(\left\|\sum_{(i_1,\ldots,i_m)\in I^m_n}H_{i_1,\ldots,i_m}(X_{i_1},\ldots, X_{i_m})\right\|\right) 
\leq 
\\
\mathbb E\Phi\left(C_m\left\|\sum_{(i_1,\ldots,i_m)\in I^m_n}H_{i_1,\ldots,i_m}\left(X_{i_1}^{(1)},\ldots, X_{i_m}^{(m)}\right)\right\|\right),
\end{multline*}
where $C_m:=2^m(m^m-1)\cdot((m-1)^{m-1}-1)\cdot\ldots\cdot 3$. 
Moreover, if $H_{i_1,\ldots,i_m}$ is $P$-canonical, then the constant $C_m$ can be taken to be $m^m$. 
Finally, there exists a constant $D_m>0$ such that for all $t>0$,
\begin{multline*}
\Pr\left(\left\|\sum_{(i_1,\ldots,i_m)\in I^m_n}H_{i_1,\ldots,i_m}(X_{i_1},\ldots, X_{i_m})\right\|\geq t\right)\\
\leq
D_m \Pr\left(D_m\left\|\sum_{(i_1,\ldots,i_m)\in I^m_n}H_{i_1,\ldots,i_m}\left(X_{i_1}^{(1)},\ldots, X_{i_m}^{(m)}\right)\right\|\geq t\right).
\end{multline*}
Furthermore, if $H_{i_1,\ldots,i_m}$ is permutation-symmetric, then, both of the above inequalities can be reversed (with different constants $C_m$ and $D_m$).
\end{lemma}

		

The following results are the variants of the non-commutative Khintchine's inequalities (that first appeared in the works by Lust-Piquard and Pisier) for the Rademacher sums and the Rademacher chaos with explicit constants, see \cite{lust1991non,lust1986inegalites}, page 111 in \cite{pisier1998non}, Theorems 6.14, 6.22 in \cite{HR-CS} and Corollary 20 in \cite{tropp2008conditioning}.
\begin{lemma}
\label{k-inequality}
Let $B_{j}\in\mathbb{C}^{r\times t} \ ,j=1,\ldots,n$ be the matrices of the same dimension, and let 
$\{\varepsilon_j\}_{j\in\mathbb{N}}$ be a sequence of i.i.d. Rademacher random variables. 
Then for any $p\geq1$,
\begin{align*}
&
\mathbb E\left\|\sum_{j=1}^n\varepsilon_j B_{j}\right\|_{S_{2p}}^{2p}
\leq
\left( \frac{2\sqrt 2}{e} p\right)^p \cdot
\max\left\{\left\|\left(\sum_{j=1}^n B_{j}B_{j}^*\right)^{1/2}\right\|_{S_{2p}}^{2p},
\left\|\left(\sum_{j=1}^n B_{j}^*B_{j}\right)^{1/2}\right\|_{S_{2p}}^{2p}\right\}.
\end{align*}
\end{lemma}

\begin{lemma}
\label{k-inequality-2}
Let $\{A_{i_1,i_2}\}_{i_1,i_2=1}^{n}$ be a sequence of Hermitian matrices of the same dimension, and let 
$\left\{\varepsilon_i^{(k)}\right\}_{i=1}^n, \ k=1,2,$ be i.i.d. Rademacher random variables. 
Then for any $p\geq 1$,
\begin{multline*}
\mathbb E\left\| \sum_{i_1=1}^n\sum_{i_2=1}^n A_{i_1,i_2}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)} \right\|_{S_{2p}}^{2p}
\leq 
\\
2\left( \frac{2\sqrt 2}{e} p\right)^{2p}
\max\left\{  \left\| \left( G G^\ast \right)^{1/2}\right\|_{S_{2p}}^{2p}, \left\|\left(\sum_{i_1,i_2=1}^n A_{i_1,i_2}^2\right)^{1/2}\right\|_{S_{2p}}^{2p} \right\},
\end{multline*}
where the matrix $G\in\mathbb{H}^{nd}$ is defined as
\[
G:=
\left(
\begin{array}{cccc}
A_{11}  & A_{12}  & \ldots & A_{1n}  \\
A_{21}  & A_{22}  & \ldots & A_{2n}  \\
\vdots  & \vdots  &   \ddots & \vdots \\
A_{n1} & A_{n2} & \ldots & A_{nn} 
\end{array}
\right).
\]
\end{lemma}

The following result (Theorem A.1 in \cite{chen2012masked}) is a variant of matrix Rosenthal's inequality for nonnegative definite matrices.  
\begin{lemma}
\label{lemma:rosenthal-pd}
Let $Y_1,\ldots,Y_n\in \mathbb H^d$ be a sequence of independent nonnegative definite random matrices. 
Then for all $q\geq 1$ and $r=\max(q, \log(d))$,
\[
\left( \mathbb E \left\| \sum_j Y_j \right\|^q \right)^{1/2q} \leq \left\| \sum_j \mathbb E Y_j \right\|^{1/2} + 2\sqrt{2er} \left( \mathbb E\max_j \|Y_j\|^q\right)^{1/2q}. 
\] 
\end{lemma}


The next inequality (see equation (2.6) in \cite{gine2000exponential}) allows to replace the sum of moments of nonnegative random variables with maxima. 
\begin{lemma}
\label{lemma:sum-max}
Let $\xi_1,\ldots,\xi_n$ be independent random variables. Then for all $q>1$ and $\alpha\geq 0$, 
\[
q^{\alpha q} \sum_{i=1}^n |\xi_i|^q \leq 2(1 + q^{\alpha})\max\left( q^{\alpha q} \mathbb E\max_i |\xi_i|^q, \left(\sum_{i=1}^n \mathbb E|\xi_i| \right)^q \right).
\] 
\end{lemma}

Finally, the following inequalities allow transitioning between moment and tail bounds. 
\begin{lemma}
\label{moment-to-tail}
Let $X$ be a random variable satisfying
$
\left(\mathbb E |X|^p\right)^{1/p}\leq a_4 p^2 + a_3 p^{3/2} + a_2 p + a_1\sqrt{p} + a_0
$
for all $p\geq 2$ and some positive real numbers $a_j, \ j=0,\ldots,3$. 
Then for any $u\geq 2$,
\[
\Pr \left(|X| \geq e(a_4 u^2 + a_3 u^{3/2} + a_2 u + a_1\sqrt{u} + a_0)\right)\leq\exp\left(-u\right).
\]
\end{lemma}
\noindent See Proposition 7.11 and 7.15 in \cite{foucart2013mathematical} for the proofs of closely related bounds. 
\begin{lemma}
\label{tail-to-moment}
Let $X$ be a random variable such that 
$
\Pr\left( |X| \geq a_0 + a_1\sqrt{u} + a_2 u \right) \leq e^{-u}
$
for all $u\geq 1$ and some $0\leq a_0,a_1,a_2<\infty$. Then 
\[
\left( \mathbb E |X|^p \right)^{1/p}\leq C(a_0 + a_1\sqrt{p} + a_2 p)
\]
for an absolute constant $C>0$ and all $p\geq 1$.
\end{lemma}
The proof follows from the formula $\mathbb E|X|^p = p\int_0^\infty \Pr\left( |X|\geq t\right)t^{p-1} dt$, see Lemma A.2 in \cite{dirksen2015tail} and Proposition 7.14 in \cite{foucart2013mathematical} for the derivation of similar inequalities. 
Next, we will use Lemma \ref{decoupling-lemma} combined with a well-known argument to obtain the symmetrization inequality for degenerate U-statistics.
\begin{lemma}
\label{lemma:symmetry}
Let $H_{i_1,i_2}:S\times S\mapsto \mathbb H^d$ be degenerate kernels, $X_1,\ldots,X_n$ -- i.i.d. $S$-valued random variables, and assume that $\{X_i^{(k)}\}_{i=1}^n$, $k=1,2,$ are independent copies of this sequence. 
Moreover, let $\left\{\varepsilon_i^{(k)}\right\}_{i=1}^n, \ k=1,2,$ be i.i.d. Rademacher random variables. 
Define
\begin{align}
\label{eq:v'}
U'_n := \sum_{(i_1,i_2)\in I^2_n}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)} H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right).
\end{align}
Then for any $p\geq1$,
\begin{equation*}
\Big( \mathbb E\left\| U_n  \right\|^p \Big)^{1/p}
\leq 16\Big( \mathbb E\left\| U'_n  \right\|^p \Big)^{1/p}.
\end{equation*}
\end{lemma}

\begin{proof}
Note that 
\begin{align*}
\mathbb E\|U_n\|^p =& \mathbb E \left\|\sum_{(i_1,i_2)\in I^2_n} H_{i_1,i_2}(X_{i_1},X_{i_2})\right\|^p \\
\leq
&  \mathbb E\left\| 2^2\sum_{(i_1,i_2)\in I^2_n}  H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right)\right\|^p,
\end{align*}
where the inequality follows from the fact that $H_{i_1,i_2}$ is $\mathcal{P}$-canonical, hence Lemma \ref{decoupling-lemma} applies with constant equal to $C_2=4$. 

Next, for $i=1,2$, let $\mathbb{E}_i[\cdot]$ stand for the expectation with respect to $\left\{ X_j^{(i)}, \varepsilon_j^{(i)} \right\}_{j\geq 1}$ only (that is, conditionally on $\left\{ X_j^{(k)}, \varepsilon_j^{(k)} \right\}_{j\geq 1}, \ k\ne i$).
Using iterative expectations and the symmetrization inequality for the Rademacher sums twice (see Lemma 6.3 in \cite{LT-book-1991}), we deduce that 
\begin{align*}
\mathbb E\|U_n\|^p
\leq
&4^p\,\mathbb E\left\| \sum_{(i_1,i_2)\in I^2_n} H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right)\right\|^p
\\
=&4^p\,\mathbb E\left[ \mathbb{E}_1 \left\|  \sum_{i_1=1}^n\sum_{i_2\ne i_1} H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right)\right\|^p\right] 
\\ \leq &
4^p\,\expect{\mathbb{E}_1 \left\| 2\sum_{i_1=1}^n \varepsilon_{i_1}^{(1)} \sum_{i_2\ne i_1} 
H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right)\right\|^p }
\\ =&
4^p\,\expect{\mathbb{E}_2 \left\| 2\sum_{i_2=1}^n 
\sum_{i_1\ne i_2} \varepsilon_{i_1}^{(1)} H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right)\right\|^p }
\\ \leq &
4^p\,\expect{\left\| 4 \sum_{(i_1,i_2)\in I^2_n}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)}
H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right)\right\|^p}.
\end{align*}
\end{proof}

\subsection{Proofs of results in Section \ref{sec:moment}.}
\subsubsection{Proof of Lemma \ref{bound-on-expectation}.}

Recall that 
\[
X=\sum_{i_1=1}^n\sum_{i_2\neq i_1} A_{i_1,i_2}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)},
\] 
where $A_{i_1,i_2}\in \mathbb H^d$ for all $i_1,i_2$, and let 
$C_p:=2\left( \frac{2\sqrt 2}{e} p\right)^{2p}$. 
We will first establish the upper bound. 
Application of Lemma \ref{k-inequality-2} (Khintchine's inequality) to the sequence of matrices $\left\{ A_{i_1,i_2}\right\}_{i_1,i_2=1}^n$ such that $A_{j,j}=0$ for $j=1,\ldots,n$ yields
\begin{align}
\label{main-bound}
&
\left(\mathbb E\|X\|_{S_{2p}}^{2p} \right)^{1/2p} \leq 2^{1/2p} \frac{2\sqrt 2 }{e}\cdot p \cdot
\max\left\{\left\|\left(GG^\ast\right)^{1/2}\right\|_{S_{2p}}, \left\|\left(\sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}^2\right)^{1/2}\right\|_{S_{2p}}\right\},
\end{align}
where 
\[
G:=
\left(
\begin{array}{cccc}
0  & A_{12}  & \ldots & A_{1n}  \\
A_{21}  & 0  & \ldots & A_{2n}  \\
\vdots  & \vdots  &   \ddots & \vdots \\
A_{n1} & A_{n2} & \ldots & 0 
\end{array}
\right) \in \mathbb R^{nd\times nd}.
\]
Our goal is to obtain a version of inequality \eqref{main-bound} for $p=\infty$. 
To this end, we need to find an upper bound for 
\[
\inf_{p\geq q} \left[ \frac{p \cdot
\max\left\{\left\|\left(GG^\ast\right)^{1/2}\right\|_{S_{2p}}, \left\|\left(\sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}^2\right)^{1/2}\right\|_{S_{2p}}\right\}}
{\max\left\{\left\|\left(GG^\ast\right)^{1/2}\right\|, \left\|\left(\sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}^2\right)^{1/2}\right\| \right\}} \right].
\]
Since $G$ is a $nd\times nd$ matrix, a naive upper bound is of order $\log(nd)$. 
We will show that it can be improved to $\log d$.
To this end, we need to distinguish between the cases when the maximum in \eqref{main-bound} is attained by the first or second term. 
Define 
\[
\widehat{B}_{i_1,i_2} = [0~|~0~|\ldots|~A_{i_1,i_2}~|\ldots|~0~|~0]\in\mathbb{C}^{d\times nd},
\]
where $A_{i_1i_2}$ sits on the $i_1$-th position of the above block matrix. Moreover, let 
\begin{align}
\label{eq:b}
B_{i_2}=\sum_{i_1:i_1\neq i_2}\widehat{B}_{i_1,i_2}.
\end{align}
Then it is easy to see that 
\begin{align*}
GG^\ast & = \sum_{i_2} B_{i_2}^\ast  B_{i_2}, \\
\sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}^2 & = \sum_{i_2}  B_{i_2}  B_{i_2}^\ast.
\end{align*}
The following bound gives a key estimate.

\begin{lemma}
\label{lemma:eigen-compare}
Let $M_1,\ldots,M_N$ be a sequence of $\mathbb C^{d\times nd}$-valued matrices. 
Let $\lambda_1,\ldots,\lambda_{nd}$ be eigenvalues of $\sum_{j} M_{j}^\ast M_{j}$ and let 
$\nu_1,\ldots,\nu_d$ be eigenvalues of $\sum_{j} M_{j}  M_{j}^\ast$. 
Then 
$\sum_{i=1}^{nd}\lambda_i = \sum_{j=1}^d\nu_j$. 
Furthermore,
if $\max_i\lambda_i\leq\frac{1}{d}\sum_{j=1}^d\nu_j$, then
\[
\left\|\left(\sum_{j}M_{j} M_{j}^\ast\right)^{1/2}\right\|_{S_{2p}}^{2p} \geq \left\|\left(\sum_{j} M_{j}^\ast M_{j}\right)^{1/2}
\right\|_{S_{2p}}^{2p},
\]
for any integer $p\geq2$.
\end{lemma}
The proof of the Lemma is given in Section \ref{sec:proof-eigencompare}. 
We will apply this fact with $M_j = B_j$, $j=1,\ldots,n$.  
Assuming that $\max_i \lambda_i\leq\frac{1}{d}\sum_{j=1}^{nd}\lambda_j$, it is easy to see that the second term in the maximum in \eqref{main-bound} dominates, hence
\begin{multline}
\mathbb E\|X\|_{S_{2p}}^{2p} \leq C_p \left\|\left(\sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}^2\right)^{1/2}\right\|_{S_{2p}}^{2p}
=C_p \, \mbox{tr\,} \left(\sum_{(i_1,i_2)\in I_n^2}A_{i_1i_2}^2\right)^p
\\
\leq C_p \cdot d \cdot\left\|\left(\sum_{(i_1,i_2)\in I_n^2} A_{i_1i_2}^2\right)^p\right\| 
= C_p \cdot d\cdot\left\|\sum_{(i_1,i_2)\in I^2_n}A_{i_1,i_2}^2\right\|^p,
\label{inter-square-bound}
\end{multline}
where the last equality follows from the fact that for any positive semidefinite matrix $H$, $\|H^p\|=\|H\|^p$. 
On the other hand, when $\max_i \lambda_i>\frac{1}{d}\sum_{j=1}^{nd}\lambda_j$, it is easy to see that for all $p\geq 1$,
\begin{align*}
d>\sum_{j=1}^{nd}\frac{\lambda_j}{\max_i \lambda_i}\geq
\sum_{j=1}^{nd}\left(\frac{\lambda_j}{\max_i \lambda_i}\right)^{p},
\end{align*}
which in turn implies that
\begin{align}
\label{eq:eig1}
d \left(\max_i\lambda_i\right)^{p}\geq\sum_{j=1}^{nd}\lambda_j^{p}.
\end{align}
Moreover, 
\begin{align}
\label{eq:eig2}
\left\|\left(\sum_{i_2}B_{i_2}^\ast B_{i_2}\right)^{1/2}
\right\|_{S_{2p}}^{2p} = 
\mbox{tr\,}\left(\left(\sum_{i_2}B_{i_2}^\ast B_{i_2}\right)^p\right) = \sum_{i=1}^{nd}\lambda_i^{p}.
\end{align}
Combining \eqref{eq:eig1}, \eqref{eq:eig2}, we deduce that
\[
\left\|\left(\sum_{i_2}B_{i_2}^\ast B_{i_2} \right)^{1/2}
\right\|_{S_{2p}}^{2p} \leq d \left\| \left(\sum_{i_2}B_{i_2}^\ast B_{i_2}\right)^p \right\| = d\left\| \left(GG^\ast\right)^p \right\|
=d\left\| GG^\ast \right\|^p,
\]
where the second from the last equality follows again from the fact that for any positive semi-definite matrix $H$, $\|H^p\|=\|H\|^p$. Thus, combining the bound above with \eqref{main-bound} and \eqref{inter-square-bound}, we obtain
\[
\mathbb E\|X\|_{S_{2p}}^{2p}
\leq d\cdot C_p\max\left\{  \left\| GG^\ast \right\|^p, \left\|\sum_{(i_1,i_2)\in I^2_n}A_{i_1,i_2}^2\right\|^p \right\}.
\]
Finally, set $p=\max(q, \log(d))$ and note that $d^{1/2p}\leq \sqrt{e}$, hence
\[
\left( \mathbb E\|X\|^{2q}\right)^{1/2q}\leq \left( \mathbb E\|X\|^{2p}\right)^{1/2p}\leq \frac{4}{\sqrt{e}}\max\{\log d, q\}\cdot\max\left\{  \left\| GG^\ast\right\|, \left\|\sum_{(i_1,i_2)\in I^n_2}A_{i_1,i_2}^2\right\| \right\}^{1/2}.
\]
This finishes the proof of upper bound.

	
Now, we turn to the lower bound. 
Let $\mathbb E_{1}[\cdot]$ stand for the expectation with respect to $\left\{ \varepsilon_j^{(1)}\right\}_{j\geq 1}$ only. 
Then 
\begin{align*}
\left( \mathbb E\|X\|^{2p}\right)^{1/(2p)}\geq& \left(\mathbb E\|X\|^{2}\right)^{1/2} =
\left(\mathbb{E}\mathbb{E}_1 \left\| \left(\sum_{(i_1,i_2)\in I_n^2} \varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)}A_{i_1,i_2} \right)^2\right\| \right)^{1/2}\\
\geq&
\left( \mathbb{E}\left\|\mathbb{E}_1\left(\sum_{(i_1,i_2)\in I_n^2} \varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)}A_{i_1,i_2}\right)^2 \right\| \right)^{1/2}\\
=& 
\left( \mathbb{E}\left\|\sum_{i_1} \left(\sum_{i_2:i_2\neq i_1}\varepsilon_{i_2}^{(2)}A_{i_1,i_2}\right)^2\right\| \right)^{1/2}.
\end{align*}
It is easy to check that 
\[
\sum_{i_1=1}^n\left(\sum_{i_2:i_2\neq i_1}\varepsilon_{i_2}^{(2)}A_{i_1,i_2}\right)^2 = 
\left(\sum_{i_2}\varepsilon_{i_2}^{(2)}B_{i_2}\right) \left(\sum_{i_2}\varepsilon_{i_2}^{(2)} B_{i_2}\right)^\ast,
\]
where $B_i$ were defined in \eqref{eq:b}. Hence
\[
\left(\mathbb E\|X\|^{2p}\right)^{1/(2p)}\geq \left( \mathbb E\left\|\left(\sum_{i_2}\varepsilon_{i_2}^{(2)}B_{i_2}\right)
\left(\sum_{i_2}\varepsilon_{i_2}^{(2)}B_{i_2}\right)^\ast \right\| \right)^{1/2}.
\]
Next, for any matrix $A\in\mathbb{C}^{d_1\times d_2}$, 
\begin{align*}
\left\|
\left(
\begin{array}{ccc}
0  &  A^\ast     \\
A  &   0   \\   
\end{array}
\right)^2
\right\|
=
\left\|
\left(
\begin{array}{ccc}
A^\ast A  &  0    \\
0  &   A A^\ast   \\   
\end{array}
\right)
\right\| 
= \max\{\|A^\ast A\|, \|A A^\ast\|\}=\|AA^\ast\|,
\end{align*}
where the last equality follows from the fact that $\|AA^\ast\|=\|A^\ast A\|$. 
Taking $A=\sum_{i_2}\varepsilon_{i_2}^{(2)}B_{i_2}$ yields that
\begin{align*}
\left(\mathbb E\|X\|^{2p}\right)^{1/(2p)}
\geq& 
\left( \mathbb E \left\| BB^\ast \right\| \right)^{1/2}
=\left( \mathbb E
  \left\| \left( \sum_{i_2}\varepsilon_{i_2}^{(2)}\left(
\begin{array}{ccc}
0  &  B_{i_2}^\ast     \\
B_{i_2}  &   0   \\   
\end{array}
\right)  \right)^2\right\| \right)^{1/2}
\\
\geq &
\left\| \mathbb E \left( \sum_{i_2}\varepsilon_{i_2}^{(2)}\left(
\begin{array}{ccc}
0  &  B_{i_2}^\ast     \\
B_{i_2}  &   0   \\   
\end{array}
\right) \right)^2 \right\|
^{1/2}
=\left\|\sum_{i_2}\left(
\begin{array}{ccc}
B_{i_2}^\ast B_{i_2}  & 0      \\
0  &  B_{i_2} B_{i_2}^\ast  \\   
\end{array}
\right)  \right\|
^{1/2}\\
=&\max\left\{\left\| \sum_{i_2}B_{i_2}^\ast B_{i_2} \right\|,  \left\| \sum_{i_2}B_{i_2} B_{i_2}^\ast \right\|\right\}^{1/2}
= \max\left\{  \left\| GG^\ast\right\|, \left\|\sum_{(i_1,i_2)\in I^2_n}A_{i_1,i_2}^2\right\| \right\}^{1/2}.
\end{align*}



\subsubsection{Proof of Lemma \ref{lemma:eigen-compare}.}
\label{sec:proof-eigencompare}

The equality of traces is obvious since
\[
\mbox{tr\,}\left( \sum_{j=1}^N M_j M_j^\ast\right) = \sum_{j=1}^N  \mbox{tr\,} \left(M_j M_j ^\ast\right) = 
\sum_{j=1}^N  \mbox{tr\,} \left(M_j^\ast M_j \right) = \mbox{tr\,}\left( \sum_{j=1}^N M_j^\ast M_j\right).
\]
Set
\[
S:=\sum_{i=1}^{nd}\lambda_i = \sum_{i=1}^d\nu_i.
\]
Note that 
\begin{align*}
&\left\|\left(\sum_{j=1}^N M_{j}^\ast M_{j}\right)^{1/2}\right\|_{S_{2p}}^{2p} = \mbox{tr\,}\left(\left(\sum_{j=1}^N M_{j}^\ast M_{j}\right)^p\right) = 
\sum_{i=1}^{nd}\lambda_i^p, \\
&\left\|\left(\sum_{j=1}^N M_{j} M_{j}^\ast\right)^{1/2}\right\|_{S_{2p}}^{2p}=\mbox{tr\,}\left(\left(\sum_{j=1}^N M_{j}M_{j}^\ast\right)^p\right) = 
\sum_{i=1}^{d}\nu_i^p.
\end{align*}
Moreover, $\lambda_i\geq0$, $\nu_j\geq0$ for all $i,j$, and $\max_i\lambda_i\leq \frac{1}{d}\sum_{j=1}^d \nu_j = \frac{S}{d}$ by assumption. 
It is clear that 
\begin{align*}
&\left\|\left(\sum_{j=1}^N M_{j}^\ast M_{j}\right)^{1/2}\right\|_{S_{2p}}^{2p} \leq \max_{0\leq\lambda_i\leq\frac{S}{2d},~\sum_{i=1}^{nd}\lambda_i= S}\sum_{i=1}^{nd}\lambda_i^p, \\
&\left\|\left(\sum_{j=1}^N M_{j} M_{j}^\ast\right)^{1/2}\right\|_{S_{2p}}^{2p}\geq\min_{\nu_i\geq0~,\sum_{i=1}^{d}\nu_i= S}\sum_{i=1}^{d}\nu_i^p.
\end{align*}
Hence, it is enough to show that
\begin{align}
\label{optimize-problem}
\max_{0\leq\lambda_i\leq\frac{S}{d},~\sum_{i=1}^{nd}\lambda_i=S}\sum_{i=1}^{nd}\lambda_i^p
\leq \min_{\nu_i\geq0,~\sum_{i=1}^{d}\nu_i= S}\sum_{i=1}^{d}\nu_i^p.
\end{align}
The right hand side of the inequality \eqref{optimize-problem} can be estimated via Jensen's inequality as
\begin{multline}
\label{rhs}
\min_{\nu_i\geq0,~\sum_{i=1}^{d}\nu_i= S}\sum_{i=1}^{d}\nu_i^p
=d\cdot\min_{\nu_i\geq0,~\sum_{i=1}^{d}\nu_i= S}\frac1d\sum_{i=1}^{d}\nu_i^p \\
\geq d\cdot\min_{\nu_i\geq0,~\sum_{i=1}^{d}\nu_i= S}\left(\frac{1}{d}\sum_{i=1}^{d}\nu_i\right)^p
= d\cdot\left(\frac{S}{d}\right)^{p}.
\end{multline}
It remains to show that $\sum_{i=1}^{nd} \lambda_i^p \leq d\cdot\left(\frac{S}{d}\right)^{p}$. 
For a sequence $\left\{ a_j \right\}_{j=1}^N \subset \mathbb R$, let $a_{(j)}$ be the j-th smallest element of the sequence, where the ties are broken arbitrary. 
A sequence $\left\{ a_j \right\}_{j=1}^N$ majorizes a sequence $\left\{ b_j \right\}_{j=1}^N$ whenever 
$\sum_{j=0}^k a_{(N-j)} \geq \sum_{j=0}^k b_{(N-j)}$ for all $0\leq k\leq N-2$, and $\sum_j a_j = \sum_j b_j$. 
A function $g:\mathbb R^N\mapsto \mathbb R$ is called Schur-convex if $g( a_1,\ldots, a_N)\geq g(b_1,\ldots,b_N)$ whenever 
$\left\{ a_j \right\}_{j=1}^N$ majorizes $\left\{ b_j \right\}_{j=1}^N$. It is well known that if $f:\mathbb R\mapsto \mathbb R$ is convex, then $g(a_1,\ldots,a_N)=\sum_{j=1}^N f(a_j)$ is Schur convex. In particular, 
$g(a_1,\ldots,a_N) = \sum_{j=1}^N a_j^p$, where $a_1,\ldots,a_N\geq 0$, is Schur convex for $p\geq 1$. 
Consider the sequence $a_1=\ldots=a_d = \frac{S}{d}, \ a_{d+1}=\ldots = a_{nd}=0$ and $b_1 = \lambda_1,\ldots,b_{nd} = \lambda_{nd}$. 
Since $\max_i\lambda_i\leq\frac{S}{d}$ by assumption, the sequence $\{a_j\}$ majorizes $\{b_j\}$, hence Schur convexity yields that $\sum_{i=1}^{nd} \lambda_i^p \leq \sum_{i=1}^d \left( \frac{S}{d}\right)^p = d\cdot \left( \frac{S}{d}\right)^p$, implying the result. 
\footnote{We are thankful to the anonymous Referee for suggesting an argument based on Schur convexity, instead of the original proof that was longer and not as elegant.}




	\begin{comment}

Given positive integers $K\geq d$ and $K'\geq d'$, we will write $(K,d)>(K',d')$ if $K\geq K'$, $d\geq d'$ and at least one of the inequalities is strict. 
We will now prove by induction that for all $(K,d), \ K\geq d$ and any $S>0$,
\[
\max_{\lambda_1,\ldots,\lambda_K\in \Lambda(K,d,S)}\sum_{i=1}^{K}\lambda_i^p = d\left(\frac{S}{d}\right)^p,
\]
where 
\[
\Lambda(K,d,S)=\left\{\lambda_1,\ldots,\lambda_K: \  0\leq\lambda_j\leq \frac{S}{d} \ \forall j,~\sum_{i=1}^{K}\lambda_i = S \right\}.
\]
The inequality is obvious for all pairs $(K,d)$ with $K=d$ or with $d=1$. 
Fix $(K,d)$ with $K>d>1$, and assume that the claim holds for all $(K',d')$ such that $K'\geq d'$ and $(K,d)>(K',d')$. 
It is easy to check that the only critical point of the Lagrangian 
\[
F(\lambda_1,\ldots,\lambda_K,\tau)=\sum_{i=1}^K \lambda_i^p +\tau\left(\sum_{i=1}^K \lambda_i - S\right)
\]
in the relative interior of the set $\Lambda(K,d,S)$ is $\hat\lambda_1=\ldots=\hat\lambda_K=S/K$ where the function achieves its minimum, hence the maximum is attained on the boundary of the set $\Lambda(K,d,S)$. 
There are 2 possibilities: 
\begin{enumerate}
\item Without loss of generality, $\lambda_1=0$. Then the situation is reduced to $(K',d')=(K-1,d)$, whence we conclude that 
\[
\max\limits_{\lambda_1,\ldots,\lambda_{K-1}\in \Lambda(K-1,d,S)}\sum_{i=1}^{K-1}\lambda_i^p = d\left(\frac{S}{d}\right)^p.
\]
\item Without loss of generality, $\lambda_1=S/d$. Then the situation is reduced to $(K',d')=(K-1,d-1)$ for $S'=S(d-1)/d$, hence 
\[
(S/d)^p + \max\limits_{\lambda_1,\ldots,\lambda_{K-1}\in \Lambda(K-1,d-1,S')}\sum_{i=1}^{K-1}\lambda_i^p =
(S/d)^p + (d-1)\left(\frac{S'}{d-1}\right)^p = d(S/d)^p.
\]
\end{enumerate}

	\end{comment}



\subsubsection{Proof of Theorem \ref{thm:degen-moment}.}
\label{proof:degen-moment}

The first inequality in the statement of the theorem follows immediately from Lemma \ref{decoupling-lemma}. Next, it is easy to deduce from the proof of Lemma \ref{lemma:symmetry} that
\begin{equation}
\label{initial-1}
 \left(\mathbb E \left\| \sum_{(i_1,i_2)\in I^2_n} H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{2q}\right)^{1/2q} 
\leq 4\Big( \mathbb E\left\| U'_n  \right\|^{2q} \Big)^{1/2q},
\end{equation}
where $U'_n$ was defined in \eqref{eq:v'}. 
Applying Lemma \ref{bound-on-expectation} conditionally on $\{X_i^{(j)}\}_{i=1}^{n}, \ j=1,2$, we get
\begin{multline}
\label{inter-chaos-1}
\Big( \mathbb E\left\| U'_n  \right\|^{2q} \Big)^{1/2q}=
\left( \mathbb E\left\| \sum_{(i_1,i_2)\in I_n^2}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)} H_{i_1,i_2}(X_{i_1}^{(1)},X_{i_2}^{(2)}) \right\|^{2q} \right)^{1/(2q)} 
\\
\leq 4e^{-1/2}\max(q,\log d) \,
\left( \mathbb E\max\left\{ \| \widetilde G \widetilde G^\ast\|, \left\|\sum_{(i_1,i_2)\in I_n^2} H_{i_1,i_2}^2\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\|   \right\}^q  \right)^{1/2q},
\end{multline}
where $\widetilde G$ was defined in \eqref{eq:g}.  
Let $\widetilde G_i$ be the $i$-th column of $\widetilde G$, then
\[
\widetilde G \widetilde G^\ast = \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast,
~~\sum_{(i_1,i_2)\in I_n^2} H_{i_1,i_2}^2(X_{i_1}^{(1)},X_{i_2}^{(2)}) = \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i.
\]
Let $Q_i\in\mathbb{H}^{(n+1)d\times(n+1)d}$ be defined as
\[
Q_i = 
\left(
\begin{array}{ccc}
0  &  \widetilde G_{i}^\ast     \\
\widetilde G_{i}  &   0   \\   
\end{array}
\right),
\]
so that
\[
Q_i^2 = 
\left(
\begin{array}{ccc}
\widetilde G_{i}^\ast \widetilde G_i & 0     \\
0 & \widetilde G_{i} \widetilde G_i^\ast   \\   
\end{array}
\right).
\]
Inequality \eqref{inter-chaos-1} implies that
\begin{equation}
\label{inter-chaos-2}
\left( \mathbb E\left\| \sum_{(i_1,i_2)\in I_n^2}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)} H_{i_1,i_2}\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{2q} \right)^{1/(2q)}
\leq 4e^{-1/2}\max(q,\log d) \left( \mathbb E\left\| \sum_{i=1}^n Q_i^2 \right\|^q\right)^{1/(2q)}.
\end{equation}
Let $\mathbb{E}_2[\cdot]$ stand for the expectation with respect to $\left\{X^{(2)}_i\right\}_{i=1}^n$ only (that is, conditionally on 
$\left\{X^{(1)}_i\right\}_{i=1}^n$). 
Then Minkowski inequality followed by the symmetrization inequality imply that
\begin{align}
\left( \mathbb E\left\| \sum_{i=1}^n Q_i^2 \right\|^q\right)^{1/(2q)} \leq
& 
\left( \mathbb E\left\| \sum_{i=1}^n \left( Q_i^2 - \mathbb E_2 Q_i^2\right)  \right\|^q \right)^{1/(2q)}  + 
\left( \mathbb E \left\| \sum_{i=1}^n \mathbb E_2 Q_i^2 \right\|^{q}  \right)^{1/2q}
\nonumber\\
=& \left( \mathbb{E}\,\mathbb{E}_2 \left\|  \sum_{i=1}^n Q_i^2 - \mathbb E_2{Q_i^2} \right\|^q \right)^{1/(2q)} + 
\left( \mathbb E \left\| \sum_{i=1}^n \mathbb E_2 Q_i^2 \right\|^{q}  \right)^{1/2q}  
\nonumber\\
 \leq& \sqrt 2 \left( \mathbb E\left\|  \sum_{i=1}^n\varepsilon_i Q_i^2 \right\|^q \right)^{1/(2q)} + 
\left( \mathbb E \left\| \sum_{i=1}^n \mathbb E_2 Q_i^2 \right\|^{q}  \right)^{1/2q}.
 \label{inter-chaos-3}
\end{align}
\noindent 
Next, we obtain an upper bound for $ \left( \mathbb E\left\|  \sum_{i=1}^n\varepsilon_i Q_i^2 \right\|^q \right)^{1/(2q)}$. 
To this end, we apply Khintchine's inequality (Lemma \ref{k-inequality}). 
Denote $C_r:=\left( \frac{2\sqrt 2}{e} r\right)^{2r}$, and let 
$\mathbb{E}_{\varepsilon}[\cdot]$ be the expectation with respect to $\{\varepsilon_i\}_{i=1}^n$ only. 
Then for $r>q$ we deduce that
\begin{align*}
\mathbb{E}_{\varepsilon}\left\| \sum_{i=1}^n\varepsilon_i Q_i^2 \right\|_{S_{2r}}^{2r} \leq& 
C_r^{1/2} \left\| \left(\sum_{i=1}^n Q_i^4\right)^{1/2}  \right\|_{S_{2r}}^{2r} 
\\
=& C_r^{1/2} \mbox{tr\,} \left(\sum_{i=1}^n Q_i^4\right)^r \leq C_r^{1/2} \mbox{tr\,} \left(\sum_{i=1}^n Q_i^2\cdot \left\| Q_i^2 \right\|\right)^r \\
\leq& C_r^{1/2} \max_i \left\| Q_i^2 \right\|^r  \cdot  \left\| \left(\sum_{i=1}^n Q_i^2\right)^{1/2}  \right\|_{S_{2r}}^{2r},
\end{align*}
where we used the fact that $Q_i^4\preceq \|Q_i^2\| Q_i^2$ for all $i$, and the fact that $A\preceq B$ implies that $\mbox{tr\,} \,g(A)\leq \mbox{tr\,} \,g(B)$ for any non-decreasing $g:\mathbb R\mapsto \mathbb R$.
Next, we will focus on the term 
\[
\left\| \left( \sum_{i=1}^n Q_i^2 \right)^{1/2}  \right\|_{S_{2r}}^{2r}
= \mbox{tr\,}\left( \left(\sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast\right)^r \right) + \mbox{tr\,}\left( \left(\sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i\right)^r \right).
\] 
Applying Lemma \ref{lemma:eigen-compare} with $M_j = \widetilde G_j^\ast, \ j=1,\ldots,n$, we deduce that
\begin{itemize}
\item if $\left\| \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast  \right\| \leq \frac{1}{d}\mbox{tr\,}\left( \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i \right)$, then
$\left\| \left(\sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast\right)^{1/2} \right\|_{S_{2r}}^{2r}\leq \left\| \left(\sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i\right)^{1/2} \right\|_{S_{2r}}^{2r}$, which implies that 
$\mbox{tr\,}\left( \left(\sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast \right)^r \right)\leq \mbox{tr\,}\left( \left(\sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i\right)^r \right)$, and
\begin{align*}
&
 \left\| \left(\sum_{i=1}^n Q_i^2\right)^{1/2}  \right\|_{S_{2r}}^{2r} 

 \leq 2d\cdot\left\| \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i \right\|^r.
 \end{align*}
 
\item if $\left\| \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast  \right\| > \frac{1}{d}\mbox{tr\,}\left( \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i \right)$, let $\lambda_j$ be the $j$-th eigenvalue of $\sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast$, and note that
\begin{multline*}
d > \frac{\mbox{tr\,}\left( \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i \right)}{\left\| \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast  \right\|} = 
\frac{\mbox{tr\,}\left( \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast \right)}{\left\| \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast  \right\|} 
= \sum_{i=1}^{nd} \frac{\lambda_i}{\max_j \lambda_j}\geq \sum_{i=1}^{nd} \left(\frac{\lambda_i}{\max_j\lambda_j}\right)^r,\end{multline*}
where $r\geq 1$. In turn, it implies that
\begin{equation*}
\mbox{tr\,}  \left(\left( \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast \right)^r\right) <
d \left\| \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast  \right\|^r. 
\end{equation*}
Thus
\begin{align*}
\left\| \left(\sum_{i=1}^n Q_i^2\right)^{1/2}  \right\|_{S_{2r}}^{2r} =& \mbox{tr\,}\left( \left(\sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast\right)^r \right) + \mbox{tr\,}\left( \left(\sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i\right)^r \right)\\
\leq& d \left\| \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast  \right\|^r + d \left\| \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i  \right\|^r.
\end{align*}
\end{itemize}
Putting the bounds together, we obtain that
\begin{align}
\label{eq:f10}
\mathbb{E}_{\varepsilon} \left\| \sum_{i=1}^n\varepsilon_i Q_i^2 \right\|_{S_{2r}}^{2r}  \leq
&
2d C_r^{1/2} \max_i \left\| Q_i^2 \right\|^r  \max \left\{ \left\| \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast  \right\|^r, \left\| \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i  \right\|^r \right\} \\
\nonumber 
\leq & 
2d C_r^{1/2} \max_i \left\| Q_i^2 \right\|^r \cdot\left\| \sum_{i=1}^n Q_i^2  \right\|^r.
\end{align}
Next, observe that for $r$ such that $2r\geq q$, 
$\mathbb E_\varepsilon \left\| \sum_{j=1}^n \varepsilon_j Q_j^2 \right\|^{q}\leq \left( \mathbb E_\varepsilon \left\| \sum_{j=1}^n \varepsilon_j Q_j^2 \right\|^{2r}\right)^{q/2r}$ by H\"{o}lder's inequality, hence
\begin{align*}
\left( \mathbb E \left\| \sum_{j=1}^n \varepsilon_j Q_j^2 \right\|^q \right)^{1/2q} &
= \left( \mathbb E \mathbb E_\varepsilon \left\| \sum_{j=1}^n \varepsilon_j Q_j^2 \right\|^{q} \right)^{1/2q} 
\\
& \leq \left( \mathbb E \left( \mathbb E_\varepsilon \left\| \sum_{j=1}^n \varepsilon_j Q_j^2 \right\|^{2r} \right)^{q/2r} \right)^{1/2q}
\leq \left( \mathbb E \left( \mathbb E_\varepsilon \left\| \sum_{j=1}^n \varepsilon_j Q_j^2 \right\|_{S_{2r}}^{2r} \right)^{q/2r} \right)^{1/2q}
\\
&\leq \left( 2d C_r^{1/2}\right)^{1/4r} \left( \mathbb E  \left[ \max_i \left\| Q_i^2 \right\|^{q/2} \cdot\left\| \sum_{i=1}^nQ_i^2  \right\|^{q/2}\right] \right)^{1/2q}.
\end{align*}
Set $r = q\vee\log d$ and apply Cauchy-Schwarz inequality to deduce that
\begin{align}
\label{eq:f20}
&
\left( \mathbb E \left\| \sum_{j=1}^n \varepsilon_j Q_j^2 \right\|^q \right)^{1/2q} \leq
(8r)^{1/4}
\left(\mathbb E \max_i \left\| Q_i^2 \right\|^{q}\right)^{1/(4q)} \left( \mathbb E\left\| \sum_{i=1}^n Q_i^2  \right\|^{q}\right)^{1/(4q)}.
\end{align}
Substituting bound \eqref{eq:f20} into \eqref{inter-chaos-3} and letting
\[
R_q := \left( \mathbb E\left\| \sum_{i=1}^n Q_i^2  \right\|^{q}\right)^{1/(2q)},
\]
we obtain
\[
R_q \leq (8r)^{1/4}\sqrt{2R_q} \, \left( \mathbb E\max_i \left\| Q_i^2 \right\|^{q}\right)^{1/(4q)} + 
\left( \mathbb E \left\| \sum_{i=1}^n \mathbb E_2 Q_i^2 \right\|^{q}  \right)^{1/2q}.
\]
If $x,a,b>0$ are such that $x\leq a\sqrt{x}+b$, then $x\leq 4a^2 \vee 2b$, hence
\[
R_q\leq 16\sqrt{2r} \left( \mathbb E\max_i \left\| Q_i^2 \right\|^{q}\right)^{1/(2q)} + 
2\left( \mathbb E \left\| \sum_{i=1}^n \mathbb E_2 Q_i^2 \right\|^{q}  \right)^{1/2q}.
\]
Finally, it follows from \eqref{inter-chaos-2} that
\begin{align}
\label{eq:d10}
\nonumber
\Bigg( \mathbb E\Bigg\| \sum_{(i_1,i_2)\in I_n^2}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)} & H(X_{i_1}^{(1)},X_{i_2}^{(2)}) \Bigg\|^{2q}\Bigg)^{1/(2q)} \\
\leq \nonumber
64\sqrt{\frac{2}{e}} \, r^{3/2} & \left( \mathbb E\max_i \left\| Q_i^2 \right\|^{q}\right)^{1/(2q)} + 
\frac{8}{\sqrt{e}} r \left( \mathbb E \left\| \sum_{i=1}^n \mathbb E_2 Q_i^2 \right\|^{q}  \right)^{1/2q}
\\ \nonumber
\leq 
64\sqrt{\frac{2}{e}} \, r^{3/2} & \left(\mathbb E \max_i \left\| \widetilde G_i^\ast \widetilde G_i \right\|^q \right)^{1/(2q)} 
+\frac{8}{\sqrt{e}} r \left( \mathbb E\left\|  \sum_{i=1}^n \mathbb E_2 \widetilde G_i \widetilde G_i^\ast \right\|^q + \mathbb E  \left\|  \sum_{i=1}^n \mathbb E_2 \widetilde G_i^\ast \widetilde G_i \right\|^{q} \right)^{1/2q}
\\ \nonumber
=
64\sqrt{\frac{2}{e}} r^{3/2} & \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)}
\\
&
+ \frac{8}{\sqrt{e}} r \left( \mathbb E\left\|  \sum_{i=1}^n \mathbb E_2 \widetilde G_i \widetilde G_i^\ast \right\|^{q} +  
\mathbb E\left\|  \sum_{i_1=1}^n \left( \sum_{i_2:i_2\ne i_1} \mathbb E_2H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right)\right\|^{q} \right)^{1/2q},
\end{align}
where the last equality follows from the definition of $\widetilde G_i$. 
To bring the bound to its final form, we will apply Rosenthal's inequality (Lemma \ref{lemma:rosenthal-pd}) to the last term in \eqref{eq:d10} to get that
\begin{multline*}
\left(\mathbb E\left\|  \sum_{i_1=1}^n \left( \sum_{i_2:i_2\ne i_1} \mathbb E_2H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right) \right\|^{q} \right)^{1/2q}
\leq \left\| \sum_{(i_1, i_2)\in I_n^2} \mathbb EH_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^{1/2}  
\\
+2\sqrt{2er} \left( \mathbb E \max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/2q}.
\end{multline*}
Moreover, Jensen's inequality implies that
\begin{align*}
&
\mathbb E \max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q 
 \leq 
 \mathbb E \max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)} \right)\right\|^q,
\end{align*}
hence this term can be combined with one of the terms in \eqref{eq:d10}. 

\subsubsection{Proof of Lemma \ref{lemma:degen-lower-bound}.}
\label{proof:lower}

Let $\mathbb E_i[\cdot]$ stand for the expectation with respect to the variables with the upper index $i$ only. 
Since $H_{i_1,i_2}\left(\cdot, \cdot\right)$ are permutation-symmetric, we can apply the second part of Lemma \ref{decoupling-lemma} and (twice) the desymmetrization inequality (see Theorem 3.1.21 in \cite{gine2016mathematical}) to get that for some absolute constant $C_0>0$
\begin{align*}
\left( \mathbb E\left\| U_n \right\|^{2q} \right)^{1/(2q)}\geq 
& \frac{1}{C_0} \left( \mathbb E\left\| \sum_{(i_1,i_2)\in I_n^2} H_{i_1,i_2}\left(X_{i_1}^{(1)}, X_{i_2}^{(2)}\right) \right\|^{2q} \right)^{1/(2q)}
\\
=& \frac{1}{C_0} \left( \mathbb E_2\,\mathbb{E}_1 \left\|  \sum_{i_1}\sum_{i_2:i_2\ne i_1} H_{i_1,i_2}\left(X_{i_1}^{(1)}, X_{i_2}^{(2)}\right) \right\|^{2q} \right)^{1/(2q)}
\\
\geq& 
\frac{1}{2C_0} \left( \mathbb E\left\|  \sum_{i_1}\varepsilon_{i_1}^{(1)}\sum_{i_2:i_2\ne i_1} H_{i_1,i_2}\left(X_{i_1}^{(1)}, X_{i_2}^{(2)}\right) \right\|^{2q} \right)^{1/(2q)} 
\\
=&  \frac{1}{2C_0}\left( \mathbb E\mathbb{E}_2 \left\|  \sum_{i_2}\sum_{i_1:i_1\ne i_2}\varepsilon_{i_1}^{(1)} H_{i_1,i_2}\left(X_{i_1}^{(1)}, X_{i_2}^{(2)}\right) \right\|^{2q} \right)^{1/(2q)} 
\\
\geq&  
\frac{1}{4C_0} \left( \mathbb E\left\|  \sum_{(i_1,i_2)\in I_n^2}\varepsilon_{i_1}^{(1)}\varepsilon_{i_2}^{(2)} H_{i_1,i_2}\left(X_{i_1}^{(1)}, X_{i_2}^{(2)}\right) \right\|^{2q} \right)^{1/(2q)}.
\end{align*}
Applying the lower bound of Lemma \ref{bound-on-expectation} conditionally on $\left\{ X_{i}^{(1)} \right\}_{i=1}^n$ and $\left\{ X_{i}^{(2)} \right\}_{i=1}^n$, we obtain
\begin{align}
\left( \mathbb E\left\| U_n \right\|^{2q}\right)^{1/(2q)}
\geq&
c \left(\mathbb E\max\left\{ \left\| \sum_i \widetilde G_i^\ast \widetilde G_i \right\|, \left\| \sum_i \widetilde G_i \widetilde G_i^\ast \right\| \right\}^{q} \right)^{1/2q} 
\label{lower-bound-1}\\
\geq&\frac{1}{4\sqrt 2C_0} \left( \left( \mathbb E\left\|  \sum_{i} \widetilde G_i \widetilde G_i^\ast \right\|^{q} \right)^{1/2q} +  
\left( \mathbb E\left\|  \sum_{i} \widetilde G_i^\ast \widetilde G_i\right\|^{q} \right)^{1/2q} \right)
\nonumber \\
\geq & \frac{1}{4\sqrt{2} C_0} \left( \left( \mathbb E\left\|  \sum_{i} \mathbb E_2 \widetilde G_i \widetilde G_i^\ast \right\|^{q}\right)^{1/2q} +  
\left( \mathbb E\left\|  \sum_{i}\mathbb E_2 \widetilde G_i^\ast \widetilde G_i\right\|^{q} \right)^{1/2q} \right),
\nonumber
\end{align}
where $\widetilde G_i$ is the $i$-th column if the matrix $\widetilde G$ defined in \eqref{eq:g}; we also used the identities 
$\widetilde G \widetilde G^\ast = \sum_{i=1}^n \widetilde G_i \widetilde G_i^\ast,
~~\sum_{(i_1,i_2)\in I_n^2} H_{i_1,i_2}^2(X_{i_1}^{(1)},X_{i_2}^{(2)}) = \sum_{i=1}^n \widetilde G_i^\ast \widetilde G_i$. 
The inequality above takes care of the second and third terms in the lower bound of the lemma. 
To show that the first term is necessary, let
\[
Q_i = 
\left(
\begin{array}{ccc}
0 & \widetilde G_i^\ast     \\
\widetilde G_i & 0   \\   
\end{array}
\right).
\]
It follows from the first line of \eqref{lower-bound-1} that
\begin{align*}
\left( \mathbb E\left\| U_n \right\|^{2q} \right)^{1/(2q)}
\geq&
\frac{1}{4 C_0} \left( \mathbb E\left\| \sum_{i=1}^n Q_i^2 \right\|^{q} \right)^{1/(2q)}.
\end{align*}
Let $i_\ast$ be the smallest value of $i\leq n$ where $\max_i \left\| Q_i^2 \right\|$ is achieved. 
Then
$
\sum_{i=1}^n Q_i^2  \succeq Q_{i_\ast}^2,
$
hence $\left\|Q_{i_\ast}^2\right\|\leq \left\|\sum_{i=1}^n Q_i^2\right\|$. 
Jensen's inequality implies that
\begin{align*}
\left( \mathbb E\left\| U_n \right\|^{2q} \right)^{1/(2q)}
&\geq \frac{1}{4 C_0}\left( \mathbb E\left\| \sum_{i=1}^n Q_i^2 \right\|^{q} \right)^{1/(2q)}
\\
&\geq
\frac{1}{4 C_0} \left( \mathbb E\max_i \left\|Q_i^2\right\|^q \right)^{1/(2q)}
\geq 
\frac{1}{4 C_0} \left( \mathbb E \max_{i}\left\| \widetilde G_i^\ast \widetilde G_i \right\|^q \right)^{1/2q},
\end{align*}
where the last equality holds since $\left\| \widetilde G_i^\ast \widetilde G_i \right\| = \left\| \widetilde G_i \widetilde G_i^\ast \right\|$. 
The claim follows.

\subsubsection{Proof of Lemma \ref{lemma:remainder}.}
\label{proof:extraterm}

Note that 
\begin{multline}
\label{eq:app20}
r^{3/2} \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)} 
\\
\leq 
r^{3/2} \left( \mathbb E\sum_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)}  
\\
=r^{3/2} \left( \mathbb E_1\sum_{i_1} \mathbb E_2 \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)}.
\end{multline}
Next, Lemma \ref{lemma:rosenthal-pd} implies that, for $r=\max(q,\log(d))$, 
\begin{align}
\label{eq:app25}
\mathbb E_2 \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q 
\leq 
2^{2q-1} \Bigg[ & \left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \\ 
& \nonumber
+(2\sqrt{2e})^{2q} r^{q} \, \mathbb E_2 \max_{i_2:i_2\ne i_1} \left\| H^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right)\right\|^q  \Bigg].
\end{align}
We will now apply Lemma \ref{lemma:sum-max} with $\alpha=1$ and 
$\xi_{i_1}:= \left\| \sum_{i_2\ne i_1} \mathbb E_2 H^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|$ to get that
\begin{multline}
\label{eq:app30}
\sum_{i_1}\mathbb E\xi^q_{i_1} \leq 
2(1 + q) \Bigg( \mathbb E\max_{i_1}\left\| \sum_{i_2: i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q 
\\
+q^{-q} \left( \sum_{i_1} \mathbb E\left\| \sum_{i_2:i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\| \right)^q \Bigg).
\end{multline}
Combining \eqref{eq:app20} with \eqref{eq:app25} and \eqref{eq:app30}, we obtain (using the inequality $1+q\leq e^q$) that
\begin{multline}
\label{eq:app40}
r^{3/2} \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/(2q)}
\\
\leq 4e\sqrt{2} \Bigg[ r^{3/2}\left(  \mathbb E\max_{i_1}\left\|  \sum_{i_2: i_2\ne i_1}  \mathbb E_2 H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{2}^{(2)}\right) \right\|^q \right)^{1/2q} \\
+ r \sqrt{1 + \frac{\log d}{q}}\left( \sum_{i_1} \mathbb E \left\|  \sum_{i_2: i_2\ne i_1} \mathbb E_2 H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|\right)^{1/2}
\\
+ r^2 \left( \sum_{i_1}\mathbb E\max_{i_2:i_2\ne i_1} \left\|  H_{i_1,i_2}^2 \left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|^q \right)^{1/2q}
\Bigg],
\end{multline}
which yields the result.


\subsection{Proof of Theorem \ref{thm:adamczak}.}
\label{section:adamczak-calculations}

Let $J\subseteq I\subseteq \{1,2\}$. 
We will write $\mathbf i$ to denote the multi-index $(i_1,i_2)\in \{1,\ldots,n\}^2$. 
We will also let $\mathbf i_I$ be the restriction of $\mathbf i$ onto its coordinates indexed by $I$, and, for a fixed value of 
$\mathbf i_{I^c}$, let $\left( H_\mathbf i \right)_{\mathbf i_I}$ be the array $\left\{ H_\mathbf i, \ \mathbf i_I \in \{1,\ldots,n\}^{| I |} \right\}$, where 
$H_{\mathbf i}:=H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2})$. 
Finally, we let $\mathbb E_I$ stand for the expectation with respect to the variables with upper indices contained in $I$ only. 
Following section 2 in \cite{adamczak2006moment}, we define 
\begin{align}
\label{eq:adam-norm}
\nonumber
\left\| \left( H_\mathbf i \right)_{\mathbf i_I}\right\|_{I,J} = \mathbb E_{I\setminus J}
\sup & \left\{ \mathbb E_J \sum_{\mathbf i_I}\langle \Phi, H_\mathbf i\rangle \prod_{j\in J} f^{(j)}_{ i_j}(X^{(j)}_{ i_j}): \ \|\Phi\|_\ast\leq 1,  \right.
\\
& 
\left. f_i^{(j)}:S\mapsto \mathbb R \text{ for all } i,j, \text{ and } 
\sum_i \mathbb E \left| f_i^{(j)}(X_i^{(j)})\right|^2 \leq 1, \ j\in J \right\}
\end{align}
and $\big\| \left( H_\mathbf i \right)_{\mathbf i_\emptyset}\big\|_{\emptyset,\emptyset}:=\left\| H_\mathbf i\right\|$, 
where $\langle A_1,A_2\rangle:=\mbox{tr\,}(A_1\,A_2^\ast)$ for $A_1,A_2\in \mathbb H^d$ and $\|\cdot\|_\ast$ denotes the nuclear norm. 
Theorem 1 in \cite{adamczak2006moment} states that for all $q\geq 1$,
\begin{align*}
&
\left( \mathbb E \left\| U_n \right\|^{2q} \right)^{1/2q}\leq C \left[ \sum_{I\subseteq \{1,2\} }\sum_{J\subseteq I} 
q^{|J|/2 + | I^c |}  \left( \sum_{\mathbf i_{I^c}} \mathbb E_{I^c} \left\| \left( H_\mathbf i \right)_{\mathbf i_I}\right\|^{2q}_{I,J} \right)^{1/2q}
\right],
\end{align*}
where $C$ is an absolute constant. Obtaining upper bounds for each term in the sum above, we get that 
\begin{align*}
&
\left( \mathbb E \left\| U_n \right\|^{2q} \right)^{1/2q}\leq C\, \Big[ \mathbb E\left\| U_n \right\| + 
\sqrt{q} \cdot A + q\cdot B + q^{3/2}\cdot \Gamma + q^2 \cdot D \Big],
\end{align*}
where
\begin{align*}
A \leq & 2 \, \mathbb E_1 \left(\sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_2} \mathbb E_2 \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi \right\rangle^2  \right)^{1/2}, \\
B \leq & \left(  \sup_{\Phi:\|\Phi\|_\ast\leq 1}  \sum_{(i_1, i_2) \in I_n^2} \mathbb E\left\langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi \right\rangle^2\right)^{1/2} \\
&+ 2\left( \sum_{i_2} \mathbb E_2 \left( \mathbb E_1 \sup_{\Phi:\|\Phi\|_\ast\leq 1} \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi  \right\rangle\right)^{2q}\right)^{1/2q}, \\
\Gamma \leq & 2 \left( \sum_{i_2} \mathbb E_2 \left( \sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_1} \mathbb E_1 \left\langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2\right)^{q} \right)^{1/2q}, \\
D \leq & \left( \sum_{(i_1, i_2) \in I_n^2} \mathbb E \left\| H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}) \right\|^{2q}\right)^{1/2q}.
\end{align*}
The bounds for $A,B,\Gamma,D$ above are obtained from \eqref{eq:adam-norm} via the Cauchy-Schwarz inequality. 
For instance, to get a bound for $A$, note that it corresponds to the choice $I = \{1,2\}$ and $J=\{1\}$ or $J=\{2\}$. Due to symmetry of the kernels, it suffices to consider the case $J=\{2\}$, and multiply the upper bound by a factor of $2$. 
When $J=\{2\}$, 
\begin{multline*}
\left( \sum_{\mathbf i_{I^c}} \mathbb E_{I^c} \left\| \left( H_\mathbf i \right)_{\mathbf i_I}\right\|^{2q}_{I,J} \right)^{1/2q} = 
\left\| \left( H_\mathbf i \right)_{\mathbf i_{\{1,2\}}}\right\|_{\{1,2\},\{2\}} 
\\
= \mathbb E_1 \sup\left\{ \mathbb E_2 \sum_{(i_1,i_2)\in I_n^2 } \langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi\rangle \cdot f^{(2)}_{i_2}\left( X^{(2)}_{i_2}\right) : \|\Phi\|_\ast \leq 1, \ \sum_{i_2} \mathbb E\left|f^{(2)}_{i_2}\left( X^{(2)}_{i_2}\right)\right|^2 \leq 1 \right\} 
\\
= \mathbb E_1\sup\left\{ \mathbb E_2 \sum_{i_2} \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle \cdot f^{(2)}_{i_2}\left( X^{(2)}_{i_2}\right) : \|\Phi\|_\ast \leq 1, \ \sum_{i_2} \mathbb E\left|f^{(2)}_{i_2}\left( X^{(2)}_{i_2}\right)\right|^2 \leq 1  \right\}
\\
\leq \mathbb E_1 \sup_{\Phi, f^{(2)}_{1},\ldots, f^{(2)}_{n} }\left\{ \sum_{i_2} \sqrt{ \mathbb E_2 \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2 }
\sqrt{\mathbb E  \left|f^{(2)}_{i_2}\left( X^{(2)}_{i_2}\right)\right|^2} \right\} 
\\
\leq \mathbb E_1 \sup \left\{ \left( \sum_{i_2} \mathbb E_2  \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2 \right)^{1/2} : \|\Phi\|_\ast \leq 1\right\} 
\\
= \mathbb E_1 \left(\sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_2} \mathbb E_2 \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi \right\rangle^2  \right)^{1/2}.
\end{multline*}
It is not hard to see that the inequality above is in fact an equality, and it is attained by setting, for every fixed $\Phi$, 
\[
f^{(2)}_{i_2}\left( X_{i_2}^{(2)}\right) = \alpha_{i_2}\frac{ \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle}
{ \sqrt{ \mathbb E_2 \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2} },
\]
where $\alpha_{i_2} = \frac{ \sqrt{\mathbb E_2  \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2} }
{\sqrt{ \sum_{i_2}  \mathbb E_2  \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2 }  }$ are such that $\sum_{i_2} \alpha^2_{i_2}=1$. 
The bounds for other terms are obtained quite similarly. 
Next, we will further simplify the upper bounds for $A,B,\Gamma,D$ by analyzing the supremum over $\Phi$ with nuclear norm not exceeding $1$. To this end, note that 
\[
\Phi\mapsto \mathbb E\left\langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi \right\rangle^2
\] 
is a convex function, hence its maximum over the convex set $\{\Phi\in\mathbb H^d: \  \|\Phi \|_\ast \leq 1\}$ is attained at an extreme point that in the case of a unit ball for the nuclear norm must be a rank-1 matrix of the form $\phi \phi^\ast$ for some $\phi\in \mathbb C^d$. 
It implies that 
\begin{align}
\label{eq:app70}\nonumber
\sup_{\Phi:\|\Phi\|_\ast\leq 1} \mathbb E\left\langle H_{i_1,i_2}(X^{(1)}_{1},X^{(2)}_{2}), \Phi \right\rangle^2 
&\leq \sup_{\phi:\|\phi\|_2\leq 1} \mathbb E \left\langle H_{i_1,i_2}(X^{(1)}_{1},X^{(2)}_{2}), \phi \phi^\ast \right\rangle^2 \\
&
\leq \left\| \mathbb E H_{i_1,i_2}^2(X^{(1)}_{1},X^{(2)}_{2})\right\|.
\end{align}
Moreover, 
\begin{multline}
\label{eq:app80}
\sum_{i_2} \mathbb E_2 \left( \mathbb E_1 \sup_{\Phi:\|\Phi\|_\ast\leq 1} \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi  \right\rangle\right)^{2q} 
\\ 
= \sum_{i_2} \mathbb E_2 \left( \mathbb E_1 \left\| \sum_{i_1} H_{i_1,i_2}\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\| \right)^{2q} 
\\
\leq \sum_{i_2} \mathbb E_2\, \mathbb E_1  \left\| \sum_{i_1} H_{i_1,i_2}\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\|^{2q} 
\\
\leq 
\sum_{i_2} \mathbb E_2 \Bigg( 2\sqrt{er}\left\| \sum_{i_1} \mathbb E_1  H_{i_1,i_2}^2\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\|^{1/2} 
\\
+4\sqrt{2} e r \left( \mathbb E_1 \max_{i_1} \left\| H_{i_1,i_2}\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right)\right\|^{2q} \right)^{1/2q}  \Bigg)^{2q},
\end{multline}
where we have used Lemma \ref{lemma:rosenthal-1} in the last step, and $r=q\vee \log d$. 
Combining \eqref{eq:app70},\eqref{eq:app80}, we get that 
\begin{multline}
\label{eq:app90}
B\leq  \left( \left\| \sum_{(i_1, i_2) \in I_n^2} \mathbb E H_{i_1,i_2}^2(X^{(1)}_{i_1},X^{(2)}_{i_2})\right\| \right)^{1/2} 
+4\sqrt{er} \left( \sum_{i_2}\, \mathbb E_2 \left\| \sum_{i_1} \mathbb E_1  H_{i_1,i_2}^2\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\|^{q} \right)^{1/2q} \\
+ 8\sqrt{2}er \left( \sum_{i_2}\,\mathbb E \max_{i_1} \left\| H_{i_1,i_2}\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right)\right\|^{2q}\right)^{1/2q}.
\end{multline}
It is also easy to get the bound for $\Gamma$: first, recall that 
\[
\Phi\mapsto \sum_{i_1} \mathbb E_1 \left\langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2
\]
is a convex function, hence its maximum over the convex set $\{\Phi\in\mathbb H^d: \  \|\Phi \|_\ast \leq 1\}$ is attained at an extreme point of the form $\phi \phi^\ast$ for some unit vector $\phi$. 
Moreover, 
\begin{multline*}
\left\langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\phi\phi^\ast \right\rangle^2 = 
\phi^\ast H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2})\phi \phi^\ast H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}) \phi 
\\
\leq \phi^\ast H^2_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}) \phi 
\end{multline*}
due to the fact that $\phi\phi^\ast \preceq I$. Hence
\begin{multline*}
\sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_1} \mathbb E_1 \left\langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2 \leq 
\sup_{\phi: \ \|\phi\|_2=1} \sum_{i_1} \mathbb E_1 \left(\phi^\ast H^2_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}) \phi \right)
\\
= \sup_{\phi: \ \|\phi\|_2=1}  \phi^\ast \left( \mathbb E_1 \sum_{i_1}  H^2_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}) \right)\phi 
= \left\| \mathbb E_1 \sum_{i_1}  H^2_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}) \right\|,
\end{multline*}
and we conclude that
\begin{multline}
\label{eq:a110}
\Gamma \leq 2 \left( \sum_{i_2} \mathbb E_2 \left( \sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_1} \mathbb E_1 \left\langle H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}),\Phi \right\rangle^2\right)^{q} \right)^{1/2q}  
\\
\leq  2 \left( \sum_{i_2} \mathbb E_2 \left\| \sum_{i_1} \mathbb E_1 H_{i_1,i_2}^2\left(X^{(1)}_{i_1},X^{(2)}_{i_2}\right) \right\|^{q} \right)^{1/2q}.
\end{multline}
The bound for $A$ requires a bit more work. The following inequality holds:
\begin{lemma}
\label{lemma:A-bound}
The following inequality holds: 
\begin{multline*}
A\leq 2\mathbb E_1 \left(\sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_2} \mathbb E_2 \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi \right\rangle^2  \right)^{1/2} \leq \\
64\sqrt{e}\log (de) \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|\right)^{1/2}
\\
+8\sqrt{2e\log (de)} \left( \mathbb E\left\|  \sum_{i} \mathbb E_2 \widetilde G_i \widetilde G_i^\ast \right\| +  
\left\|  \sum_{(i_1,i_2)\in I_n^2} \mathbb E H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)} \right)\right\| \right)^{1/2},
\end{multline*}
where $\widetilde G$ was defined in \eqref{eq:g}.
\end{lemma}
Combining the bounds \eqref{eq:app90}, \eqref{eq:a110} and Lemma \ref{lemma:A-bound}, and grouping the terms with the same power of $q$, we get the result of Theorem \ref{thm:adamczak}.

It remains to prove Lemma \ref{lemma:A-bound}. 
To this end, note that Jensen's inequality and an argument similar to \eqref{eq:app70} imply that 
\begin{multline*}
\mathbb E_1 \left(\sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_2} \mathbb E_2 \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi \right\rangle^2  \right)^{1/2} \\ 
\leq 
\left( \mathbb E \sup_{\Phi:\|\Phi\|_\ast\leq 1} \sum_{i_2} \left\langle \sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2}), \Phi \right\rangle^2  \right)^{1/2}
\\
\leq \left(\mathbb E\left\| \sum_{i_2} \left(\sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2})\right)^2 \right\| \right)^{1/2}.
\end{multline*}
Next, arguing as in the proof of Lemma \ref{bound-on-expectation}, we define 
\[
\widehat{B}_{i_1,i_2} = [0~|~0~|\ldots|~H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2})~|\ldots|~0~|~0]\in\mathbb{R}^{d\times nd},
\]
where $H_{i_1,i_2}$ sits on the $i_1$-th position of the block matrix above. Moreover, let 
\begin{align}
\label{eq:b}
B_{i_2}=\sum_{i_1:i_1\neq i_2}\widehat{B}_{i_1,i_2}.
\end{align}
Using the representation \eqref{eq:b}, we have
\begin{multline*}
\left(\mathbb E\left\| \sum_{i_2} \left(\sum_{i_1} H_{i_1,i_2}(X^{(1)}_{i_1},X^{(2)}_{i_2})\right)^2 \right\| \right)^{1/2}
= \left( \mathbb E\left\| \left(\sum_{i_2}B_{i_2}\right)\left(\sum_{i_2}B_{i_2}\right)^\ast \right\| \right)^{1/2} \\
=\left( \mathbb E
  \left\| \left( \sum_{i_2}\left(
\begin{array}{ccc}
0  &  B_{i_2}^\ast     \\
B_{i_2}  &   0   \\   
\end{array}
\right)  \right)^2\right\| \right)^{1/2}
\leq2\left( \mathbb E
  \left\| \left( \sum_{i_2}\varepsilon_{i_2}\left(
\begin{array}{ccc}
0  &  B_{i_2}^\ast     \\
B_{i_2}  &   0   \\   
\end{array}
\right)  \right)\right\|^2 \right)^{1/2},
\end{multline*}
where $\left\{\varepsilon_{i_2}\right\}_{i_2=1}^n$ is sequence of i.i.d. Rademacher random variables, and the last step follows from the symmetrization inequality. 
Next, Khintchine's inequality \eqref{matrix-Khintchine} yields that
\begin{align*}
A\leq& 4\sqrt{e(1+2\log d)}\left(\mathbb E\left\|\sum_{i_2}\left(
\begin{array}{ccc}
B_{i_2}^\ast B_{i_2}  & 0      \\
0  &  B_{i_2}B_{i_2}^\ast   \\   
\end{array}
\right)  \right\|\right)
^{1/2}\\
=&4\sqrt{e(1+2\log d)}\left(\mathbb E\max\left\{\left\| \sum_{i_2}B_{i_2}^\ast B_{i_2} \right\|,  \left\| \sum_{i_2}B_{i_2}B_{i_2}^\ast \right\|\right\}\right)^{1/2}
\\
=& 4\sqrt{e(1+2\log d)}\left( \mathbb E\max\left\{  \left\| \widetilde G\widetilde G^\ast\right\|, \left\|\sum_{(i_1,i_2)\in I^2_n}H_{i_1,i_2}^2\left( X^{(1)}_{i_1},X^{(2)}_{i_2} \right) \right\| \right\} \right)^{1/2}.
\end{align*}
Note that the last expression is of the same form as equation \eqref{inter-chaos-1} in the proof of Theorem \ref{thm:degen-moment} with $q=1$. Repeating the same argument, one can show that  
\begin{align*}
A \leq 64\sqrt{e}\log (de)& \left( \mathbb E\max_{i_1} \left\| \sum_{i_2:i_2\ne i_1} H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)}\right) \right\|\right)^{1/2}
\\
&
+8\sqrt{2e\log (de)} \left( \mathbb E\left\|  \sum_{i} \mathbb E_2 \widetilde G_i \widetilde G_i^\ast \right\| +  
\left\|  \sum_{(i_1,i_2)\in I_n^2} \mathbb E H_{i_1,i_2}^2\left(X_{i_1}^{(1)},X_{i_2}^{(2)} \right)\right\| \right)^{1/2},
\end{align*}
which is an analogue of \eqref{eq:d10}. 
	


\subsection{Calculations related to Examples \ref{example:01} and \ref{example:02}.}
\label{section:example-proof}

We will first estimate $\left\|GG^\ast\right\|$. Note that the $(i,i)$-th block of the matrix $GG^\ast$ is
\[
\left(GG^\ast\right)_{ii} = \sum_{j:j\neq i}A_{i,j}^2 = \sum_{j:j\neq i}\left(\mathbf{a}_i\mathbf a_j^T+\mathbf a_j\mathbf a_i^T\right)^2
=(n-1)\mathbf a_i\mathbf a_i^T + \sum_{j\neq i}\mathbf a_j\mathbf a_j^T.
\]
The $(i,j)$-block for $j\neq i$ is
\[
\left(GG^\ast\right)_{ij} = \sum_{k\neq i,j}A_{i,k}A_{j,k}
=\sum_{k\neq i,j}\left(\mathbf a_i\mathbf a_k^T+\mathbf a_k\mathbf a_i^T\right)\left(\mathbf a_j\mathbf a_k^T+\mathbf a_k\mathbf a_j^T\right)=(n-2)\mathbf a_i\mathbf a_j^T.
\]
We thus obtain that
\begin{align*}
GG^\ast = (n-2)\mathbf{a}\mathbf{a}^T + \mathrm{Diag}\left( \underbrace{ \sum_{j=1}^n\mathbf{a}_j\mathbf{a}_j^T
,\ldots, \sum_{j=1}^n\mathbf{a}_j\mathbf{a}_j^T }_{\text{n terms}}\right),
\end{align*}
where  $\mathrm{Diag}(\cdot)$ denotes the block-diagonal matrix with diagonal blocks in the brackets.
Since 
$$\mathrm{Diag}\left( \sum_{j=1}^n\mathbf{a}_j\mathbf{a}_j^T
,\ldots, \sum_{j=1}^n\mathbf{a}_j\mathbf{a}_j^T\right)\succeq 0,$$ 
it follows that 
\[
\left\|GG^\ast \right\| \geq (n-2) \|\mathbf{a}\|^2_2=(n-2)n.
\]
On the other hand, 
\begin{multline*}
\left\| \sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}^2\right\|
= \left\| \sum_{(i_1,i_2)\in I_n^2} \left(  \mathbf{a}_{i_1}\mathbf{a}_{i_2}^T + \mathbf{a}_{i_2}\mathbf{a}_{i_1}^T \right)^2\right\|
= \left\| \sum_{(i_1,i_2)\in I_n^2} \left( \mathbf{a}_{i_1}\mathbf{a}_{i_1}^T +\mathbf{a}_{i_2}\mathbf{a}_{i_2}^T  \right)  \right\| 
\\
=2(n-1)\left\| \sum_{i} \mathbf{a}_{i}\mathbf{a}_{i}^T \right\| = 2(n-1).
\end{multline*}
where the last equality follows from the fact that $\{\mathbf{a}_1,\ldots,\mathbf{a}_n\}$ are orthonormal. 

For Example \ref{example:02}, we similarly obtain that 
\begin{align*}
\left(GG^\ast\right)_{ii} &= \sum_{j:j\neq i}c^2_{i,j}\left(\mathbf{a}_i\mathbf a_j^T+\mathbf a_j\mathbf a_i^T\right)^2
\\
&=\left( \sum_{j:j\ne i} c^2_{i,j}\right)\mathbf a_i\mathbf a_i^T + \sum_{j:j\neq i} c^2_{i,j}\mathbf a_j\mathbf a_j^T 
= \mathbf a_i\mathbf a_i^T + \sum_{j:j\neq i} c^2_{i,j}\mathbf a_j\mathbf a_j^T,
\\
\left(GG^\ast\right)_{ij} &= \sum_{k\neq i,j}c_{i,k}c_{j,k}\left(\mathbf a_i\mathbf a_k^T+\mathbf a_k\mathbf a_i^T\right)\left(\mathbf a_j\mathbf a_k^T+\mathbf a_k\mathbf a_j^T\right)=0, \ i\ne j,
\end{align*}
hence $\left\| GG^\ast \right\|=\max_i \left\| (GG^\ast)_{ii}\right\|=1$. On the other hand, 
\begin{multline*}
\left\| \sum_{(i_1,i_2)\in I_n^2} A_{i_1,i_2}^2\right\|
= \left\| \sum_{(i_1,i_2)\in I_n^2} c^2_{i_1,i_2}\left(  \mathbf{a}_{i_1}\mathbf{a}_{i_2}^T + \mathbf{a}_{i_2}\mathbf{a}_{i_1}^T \right)^2\right\| \\
= \left\| \sum_{(i_1,i_2)\in I_n^2} c^2_{i_1,i_2}\left( \mathbf{a}_{i_1}\mathbf{a}_{i_1}^T +\mathbf{a}_{i_2}\mathbf{a}_{i_2}^T  \right)  \right\| = 2\left\| \sum_{i} \mathbf{a}_{i} \mathbf{a}_{i}^T \right\|=2,
\end{multline*}
and 
\begin{multline*}
\sum_{i_1} \left\| \sum_{i_2:i_2\neq i_1}A_{i_1,i_2}^2\right\| = \sum_{i_1} \left\| \sum_{i_2\neq i_1} c^2_{i_1,i_2}\left(  \mathbf{a}_{i_1}\mathbf{a}_{i_2}^T + \mathbf{a}_{i_2}\mathbf{a}_{i_1}^T \right)^2\right\| \\
= \sum_{i_1}\left\| \sum_{i_2:i_2\ne i_1} c_{i_1,i_2}^2 \left(  \mathbf{a}_{i_1} \mathbf{a}_{i_1}^T +  \mathbf{a}_{i_2}  \mathbf{a}_{i_2}^T\right) \right\| 
= \sum_{i_1}\left\|  \mathbf{a}_{i_1} \mathbf{a}_{i_1}^T  + \sum_{i_2:i_2\ne i_1} c_{i_1,i_2}^2   \mathbf{a}_{i_2}  \mathbf{a}_{i_2}^T \right\| = n.
\end{multline*}
















  


