Deduce a probability inequality via "standard symmetrization argument"

Question

Let $\boldsymbol{A}\in\mathbb{R}^{n_1\times n_2}$ be some fixed matrix, and $\{\boldsymbol{X}_i\}_{i=1}^n$ be independent random matrices for which $\mathbb{E}(\boldsymbol{X}_i)=\boldsymbol{A}$. I would like to deduce the following probability inequality $$ \mathbb{P}\left\{\left\|\frac{1}{n}\sum_{i=1}^n\boldsymbol{X}_i-\boldsymbol{A}\right\|\ge 3t\right\}\le\max_{\|\boldsymbol{u}\|=\|\boldsymbol{v}\|=1}\mathbb{P}\left\{\left\langle\frac{1}{n}\sum_{i=1}^n\boldsymbol{X}_i-\boldsymbol{A},\boldsymbol{u}\boldsymbol{v}^\top\right\rangle\ge t\right\}+4\mathbb{P}\left\{\left\|\frac{1}{n}\sum_{i=1}^n\varepsilon_i\boldsymbol{X}_i\right\|\ge t\right\}, $$ where the $\|\cdot\|$ is the matrix spectral norm, $\{\varepsilon_i\}_{i=1}^n$ are i.i.d. Rademacher (i.e., symmetric Bernoulli) random variables.

The probability inequality above is a simplified version of the first step in Proof of Theorem 2 in (the arxiv version of)

Yuan, M., & Zhang, C. H. (2017). Incoherent tensor norms and their applications in higher order tensor completion. IEEE Transactions on Information Theory, 63(10), 6753-6766.

see https://arxiv.org/pdf/1606.03504.pdf, which was concerning tensors and their more specialized norms, so as to adapt the problem to a wider audience. The paper said "the standard symmetrization argument gives" the above inequality, but I totally have no idea about how to do this standard step. I know how to use the symmetrization technique to derive inequalities regarding expectations, such as $\mathbb{E}\left\|\sum_{i=1}^n \boldsymbol{X}_i\right\| \leq 2 \mathbb{E}\left\|\sum_{i=1}^n \varepsilon_i \boldsymbol{X}_i\right\|$, but I don't know how to apply this to bound probabilities. The paper also gave the following reference about the used "standard symmetrization argument"

Giné, E., & Zinn, J. (1984). Some limit theorems for empirical processes. The Annals of Probability, 929-989.

see https://www.jstor.org/stable/2243347, but unfortunately the contents of the paper are too advanced to be understandable to me. I am wondering if someone can give me a hint on how to deduce this standard inequality, or point out for me which part of the latter reference implies the result. Thanks in advance.

Answer 1

Let $\mathcal F$ be the set of functions $$f(\boldsymbol M) = \left\langle \boldsymbol M, \boldsymbol u\boldsymbol v^\intercal\right\rangle$$ for all $\left\|u\right\| = \left\|v\right\| =1$.

Given a sequence $\boldsymbol X$ of random matrices, $\varepsilon$ a sequence of Rademacher (i.e., symmetric Bernoulli) random variables and $f\in \mathcal F$, let

$$\mathbb Ef = \mathbb E\left[f\left(\boldsymbol{X}_i\right)\right] = f\left(\boldsymbol A\right),$$

$$\mathbb E_{n, \boldsymbol X}f = \frac1n \sum_{i=1}^n f\left(\boldsymbol X_i\right)$$

and

$$\mathbb E_{n, \varepsilon, \boldsymbol X}f = \frac1n \sum_{i=1}^{n}\epsilon_i f\left(\boldsymbol X_i\right)$$ and for a functional $\boldsymbol L$ on $\mathcal F$ $$\left\|\boldsymbol L\right\|_{\mathcal F} = \sup_{f\in \mathcal F} \left\|\boldsymbol Lf\right\|.$$

Finally, we denote by $\alpha$ the value pf $\sup_{f\in \mathcal F}\mathbb P\left[\left|\mathbb E_{n, \boldsymbol X}f - \mathbb Ef\right| \ge t\right]$ and $$B=\left\{\left\|\mathbb E_{n,\boldsymbol X} - \mathbb E\right\|_{\mathcal F}> 3t\right\}.$$

The inequality that you are looking for is equivalent to

$$\mathbb P\left[B\right] \le \alpha + 4\mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F}> t\right].$$

Let $\boldsymbol Y$ be a sequence of random matrices independant from $\boldsymbol X$ and has the same distribution as $\boldsymbol X$.

Since if $\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E\right\|_{\mathcal F} > 3t$ there will be $g\in \mathcal F$ such that $$\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t,$$

then $$\sup_{g\in\mathcal F}\mathbb P\left[\left.\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\,\Big|\right.\boldsymbol X\right] = \mathbf 1_{B}$$

\begin{align} \mathbb P\left[\left.\left\{\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right\}\cap B\,\Big|\right.\boldsymbol X\right] &\ge\sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb E_{n, \boldsymbol Y}g\right| > 2t\right\} \cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right. \boldsymbol X\right]\\ &= \sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| - \left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| > 2t\right\}\cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right.\boldsymbol X\right]\\ &= \sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| < \left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| - 2t \right\}\cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right.\boldsymbol X\right]\\ &\ge \sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| < t\right\}\cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right.\boldsymbol X\right]\\ &= \sup_{g\in\mathcal F}\left(\mathbb P\left[\left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| < t\right]\mathbb P\left[\left.\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\,\Big|\right.\boldsymbol X\right]\right)\\ &\ge \left(\inf_{f\in\mathcal F} \mathbb P\left[\left|\mathbb E_{n, \boldsymbol Y}f - \mathbb Ef\right| < t\right]\right)\left(\sup_{g\in\mathcal F}\mathbb P\left[\left.\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\,\Big|\right. \boldsymbol X\right]\right)\\ &= \left(1 - \sup_{f\in\mathcal F} \mathbb P\left[\left|\mathbb E_{n, \boldsymbol Y}f - \mathbb Ef\right| \ge t\right]\right)\mathbf 1_B\\ &= \left(1 - \alpha\right)\mathbf 1_B. \end{align}

This proves that,

\begin{align} \mathbb P\left[\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right] &\ge \mathbb P\left[\left\{\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right\}\cap B\right]\\ &= \mathbb E\left[\mathbb P\left[\left.\left\{\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right\}\cap B\,\Big|\right.\boldsymbol X\right]\right]\\ &\ge \left(1-\alpha\right) \mathbb E\left[\mathbf 1_{B}\right]\\ &= \left(1-\alpha\right) \mathbb P\left[B\right] \end{align}

On the other hand,

\begin{align} \mathbb P\left[\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right] &= \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X} - \mathbb E_{n, \varepsilon, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right]\\ &\le \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} + \left\|\mathbb E_{n, \varepsilon, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right]\\ &\le \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} > t\right] + \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol Y}\right\|_{\mathcal F} > t\right]\\ &= 2 \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} > t\right] \end{align}

Finally,

\begin{align} \mathbb P\left[B\right] &= \alpha \mathbb P\left[B\right] + (1-\alpha)\mathbb P\left[B\right]\\ &\le \alpha + (1-\alpha)\mathbb P\left[B\right]\\ &\le \alpha + \mathbb P\left[\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right]\\ &\le \alpha + 2\mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} > t\right]. \end{align}

and that finishes the proof.