Skip to main content
MathOverflow

Return to Answer

The conspicuous absence of correct spacing was caused by this omission.
Source Link
Michael Hardy
Michael Hardy
  • 1
  • 12
  • 85
  • 126

The best I can prove has an extra $K$, but I think it does not matter too much for the proof of the original paper.

\begin{align} n t^2 \mathbb{E}\left(Y_{kij}^2 e^{t|Y_{kij}|} \right) &= n (\eta\sqrt{\log p /n})^2 \mathbb{E}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \eta^2\log p \mathbb{E}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \log p \mathbb{E}\left((\eta Y_{kij})^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &\leq \log p \mathbb{E}\left((\eta Y_{kij})^2 e^{\eta\cdot\eta^{1/2}|Y_{kij}|} \right) \\ &= \eta^{-1}\log p \mathbb{E}\left((\eta^{3/2} Y_{kij})^2 e^{\eta^{3/2}|Y_{kij}|} \right)\\ &\leq \eta^{-1}K^3\log p \tag{1}\label{eq6} \end{align}\begin{align} n t^2 \operatorname{\mathbb{E}}\left(Y_{kij}^2 e^{t|Y_{kij}|} \right) &= n (\eta\sqrt{\log p /n})^2 \operatorname{\mathbb{E}}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \eta^2\log p \operatorname{\mathbb{E}} \left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \log p \operatorname{\mathbb{E}}\left((\eta Y_{kij})^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &\leq \log p \operatorname{\mathbb{E}}\left((\eta Y_{kij})^2 e^{\eta\cdot\eta^{1/2}|Y_{kij}|} \right) \\ &= \eta^{-1}\log p \operatorname{\mathbb{E}}\left((\eta^{3/2} Y_{kij})^2 e^{\eta^{3/2}|Y_{kij}|} \right)\\ &\leq \eta^{-1}K^3\log p \tag{1}\label{eq6} \end{align}

The first inequality is by $\log p/n\leq\eta$. The second inequality is proved as follows:

It suffices to show that \begin{equation} \tag{2}\label{eq1} \mathbb{E}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq K^, \quad \mbox{for all } |\lambda|\leq\eta/2. \end{equation}\begin{equation} \tag{2}\label{eq1} \operatorname{\mathbb{E}}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq K^, \quad \mbox{for all } |\lambda|\leq\eta/2. \end{equation} Then by $0<\eta<1/4$ we have $\eta^{3/2}<\eta/2$, hence the result is proved.

Now prove \eqref{eq1}. Since $s^2\leq e^s$ for $s>0$, we have \begin{equation} \tag{3}\label{eq2} \mathbb{E}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq \mathbb{E}\left(e^{2\lambda|Y_{kij}|} \right). \end{equation}\begin{equation} \tag{3}\label{eq2} \operatorname{\mathbb{E}}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq \operatorname{\mathbb{E}}\left(e^{2\lambda|Y_{kij}|} \right). \end{equation} By definition, we have $$Y_{kij} = \frac{1}{4}\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \mathbb{E}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}.$$$$Y_{kij} = \frac{1}{4}\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \operatorname{\mathbb{E}}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}.$$ Then following \eqref{eq2} we have \begin{align} \mathbb{E}\left(e^{2\lambda|Y_{kij}|} \right) &= \mathbb{E}\left(e^{\frac{1}{2}\lambda\left\lvert\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \mathbb{E}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}\right\rvert} \right) \\ &\leq \mathbb{E}\left(e^{\frac{1}{2}\lambda(X_{ki}+X_{kj})^2 + \frac{1}{2}\lambda(X_{ki}-X_{kj})^2 + \mathbb{E}\left[(X_{ki}+X_{kj})^2 \right] + \mathbb{E}\left[(X_{ki}-X_{kj})^2 \right] } \right) \\ &= \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) + \mathbb{E}(X_{ki}^2+X_{kj}^2) } \right) \\ &= e^{\lambda\mathbb{E}(X_{ki}^2+X_{kj}^2)} \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right). \tag{4}\label{eq3} \end{align}\begin{align} \operatorname{\mathbb{E}}\left(e^{2\lambda|Y_{kij}|} \right) &= \operatorname{\mathbb{E}}\left(e^{\frac{1}{2}\lambda\left\lvert\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \operatorname{\mathbb{E}}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}\right\rvert} \right) \\ &\leq \operatorname{\mathbb{E}}\left(e^{\frac{1}{2}\lambda(X_{ki}+X_{kj})^2 + \frac{1}{2}\lambda(X_{ki}-X_{kj})^2 + \operatorname{\mathbb{E}}\left[(X_{ki}+X_{kj})^2 \right] + \operatorname{\mathbb{E}}\left[(X_{ki}-X_{kj})^2 \right] } \right) \\ &= \operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) + \operatorname{\mathbb{E}}(X_{ki}^2+X_{kj}^2) } \right) \\ &= e^{\lambda\operatorname{\mathbb{E}}(X_{ki}^2+X_{kj}^2)} \operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right). \tag{4}\label{eq3} \end{align} By Hölder's inequality, $$\mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq \mathbb{E}^{1/2}\left(e^{2\lambda X_{ki}^2 } \right)\mathbb{E}^{1/2}\left(e^{2\lambda X_{kj}^2 } \right). $$$$\operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq \operatorname{\mathbb{E}}^{1/2}\left(e^{2\lambda X_{ki}^2 } \right) \operatorname{\mathbb{E}}^{1/2}\left(e^{2\lambda X_{kj}^2 } \right). $$ By the exponential-type tail condition, we have $$\mathbb{E} e^{2\lambda X_i^2} \leq K, \quad \mbox{for all } |\lambda|\leq\eta/2.$$$$\operatorname{\mathbb{E}} e^{2\lambda X_i^2} \leq K, \quad \mbox{for all } |\lambda|\leq\eta/2.$$ Hence, \begin{equation} \tag{5}\label{eq4} \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq K. \end{equation}\begin{equation} \tag{5}\label{eq4} \operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq K. \end{equation} By Jensen's inequality, \begin{equation} \tag{6}\label{eq5} e^{\lambda\mathbb{E}(X_{ki}^2+X_{kj}^2)} = e^{\mathbb{E}\lambda X_{ki}^2}e^{\mathbb{E}\lambda X_{kj}^2} \leq \mathbb{E}e^{\lambda X_{ki}^2} \mathbb{E}e^{\lambda X_{kj}^2} \leq K^2 \end{equation}\begin{equation} \tag{6}\label{eq5} e^{\lambda\operatorname{\mathbb{E}}(X_{ki}^2+X_{kj}^2)} = e^{\operatorname{\mathbb{E}}\lambda X_{ki}^2}e^{\operatorname{\mathbb{E}}\lambda X_{kj}^2} \leq \operatorname{\mathbb{E}}e^{\lambda X_{ki}^2} \operatorname{\mathbb{E}}e^{\lambda X_{kj}^2} \leq K^2 \end{equation} Combining \eqref{eq3}, \eqref{eq4} and \eqref{eq5}, \eqref{eq6} is proved.

The best I can prove has an extra $K$, but I think it does not matter too much for the proof of the original paper.

\begin{align} n t^2 \mathbb{E}\left(Y_{kij}^2 e^{t|Y_{kij}|} \right) &= n (\eta\sqrt{\log p /n})^2 \mathbb{E}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \eta^2\log p \mathbb{E}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \log p \mathbb{E}\left((\eta Y_{kij})^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &\leq \log p \mathbb{E}\left((\eta Y_{kij})^2 e^{\eta\cdot\eta^{1/2}|Y_{kij}|} \right) \\ &= \eta^{-1}\log p \mathbb{E}\left((\eta^{3/2} Y_{kij})^2 e^{\eta^{3/2}|Y_{kij}|} \right)\\ &\leq \eta^{-1}K^3\log p \tag{1}\label{eq6} \end{align}

The first inequality is by $\log p/n\leq\eta$. The second inequality is proved as follows:

It suffices to show that \begin{equation} \tag{2}\label{eq1} \mathbb{E}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq K^, \quad \mbox{for all } |\lambda|\leq\eta/2. \end{equation} Then by $0<\eta<1/4$ we have $\eta^{3/2}<\eta/2$, hence the result is proved.

Now prove \eqref{eq1}. Since $s^2\leq e^s$ for $s>0$, we have \begin{equation} \tag{3}\label{eq2} \mathbb{E}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq \mathbb{E}\left(e^{2\lambda|Y_{kij}|} \right). \end{equation} By definition, we have $$Y_{kij} = \frac{1}{4}\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \mathbb{E}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}.$$ Then following \eqref{eq2} we have \begin{align} \mathbb{E}\left(e^{2\lambda|Y_{kij}|} \right) &= \mathbb{E}\left(e^{\frac{1}{2}\lambda\left\lvert\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \mathbb{E}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}\right\rvert} \right) \\ &\leq \mathbb{E}\left(e^{\frac{1}{2}\lambda(X_{ki}+X_{kj})^2 + \frac{1}{2}\lambda(X_{ki}-X_{kj})^2 + \mathbb{E}\left[(X_{ki}+X_{kj})^2 \right] + \mathbb{E}\left[(X_{ki}-X_{kj})^2 \right] } \right) \\ &= \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) + \mathbb{E}(X_{ki}^2+X_{kj}^2) } \right) \\ &= e^{\lambda\mathbb{E}(X_{ki}^2+X_{kj}^2)} \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right). \tag{4}\label{eq3} \end{align} By Hölder's inequality, $$\mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq \mathbb{E}^{1/2}\left(e^{2\lambda X_{ki}^2 } \right)\mathbb{E}^{1/2}\left(e^{2\lambda X_{kj}^2 } \right). $$ By the exponential-type tail condition, we have $$\mathbb{E} e^{2\lambda X_i^2} \leq K, \quad \mbox{for all } |\lambda|\leq\eta/2.$$ Hence, \begin{equation} \tag{5}\label{eq4} \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq K. \end{equation} By Jensen's inequality, \begin{equation} \tag{6}\label{eq5} e^{\lambda\mathbb{E}(X_{ki}^2+X_{kj}^2)} = e^{\mathbb{E}\lambda X_{ki}^2}e^{\mathbb{E}\lambda X_{kj}^2} \leq \mathbb{E}e^{\lambda X_{ki}^2} \mathbb{E}e^{\lambda X_{kj}^2} \leq K^2 \end{equation} Combining \eqref{eq3}, \eqref{eq4} and \eqref{eq5}, \eqref{eq6} is proved.

The best I can prove has an extra $K$, but I think it does not matter too much for the proof of the original paper.

\begin{align} n t^2 \operatorname{\mathbb{E}}\left(Y_{kij}^2 e^{t|Y_{kij}|} \right) &= n (\eta\sqrt{\log p /n})^2 \operatorname{\mathbb{E}}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \eta^2\log p \operatorname{\mathbb{E}} \left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \log p \operatorname{\mathbb{E}}\left((\eta Y_{kij})^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &\leq \log p \operatorname{\mathbb{E}}\left((\eta Y_{kij})^2 e^{\eta\cdot\eta^{1/2}|Y_{kij}|} \right) \\ &= \eta^{-1}\log p \operatorname{\mathbb{E}}\left((\eta^{3/2} Y_{kij})^2 e^{\eta^{3/2}|Y_{kij}|} \right)\\ &\leq \eta^{-1}K^3\log p \tag{1}\label{eq6} \end{align}

The first inequality is by $\log p/n\leq\eta$. The second inequality is proved as follows:

It suffices to show that \begin{equation} \tag{2}\label{eq1} \operatorname{\mathbb{E}}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq K^, \quad \mbox{for all } |\lambda|\leq\eta/2. \end{equation} Then by $0<\eta<1/4$ we have $\eta^{3/2}<\eta/2$, hence the result is proved.

Now prove \eqref{eq1}. Since $s^2\leq e^s$ for $s>0$, we have \begin{equation} \tag{3}\label{eq2} \operatorname{\mathbb{E}}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq \operatorname{\mathbb{E}}\left(e^{2\lambda|Y_{kij}|} \right). \end{equation} By definition, we have $$Y_{kij} = \frac{1}{4}\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \operatorname{\mathbb{E}}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}.$$ Then following \eqref{eq2} we have \begin{align} \operatorname{\mathbb{E}}\left(e^{2\lambda|Y_{kij}|} \right) &= \operatorname{\mathbb{E}}\left(e^{\frac{1}{2}\lambda\left\lvert\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \operatorname{\mathbb{E}}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}\right\rvert} \right) \\ &\leq \operatorname{\mathbb{E}}\left(e^{\frac{1}{2}\lambda(X_{ki}+X_{kj})^2 + \frac{1}{2}\lambda(X_{ki}-X_{kj})^2 + \operatorname{\mathbb{E}}\left[(X_{ki}+X_{kj})^2 \right] + \operatorname{\mathbb{E}}\left[(X_{ki}-X_{kj})^2 \right] } \right) \\ &= \operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) + \operatorname{\mathbb{E}}(X_{ki}^2+X_{kj}^2) } \right) \\ &= e^{\lambda\operatorname{\mathbb{E}}(X_{ki}^2+X_{kj}^2)} \operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right). \tag{4}\label{eq3} \end{align} By Hölder's inequality, $$\operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq \operatorname{\mathbb{E}}^{1/2}\left(e^{2\lambda X_{ki}^2 } \right) \operatorname{\mathbb{E}}^{1/2}\left(e^{2\lambda X_{kj}^2 } \right). $$ By the exponential-type tail condition, we have $$\operatorname{\mathbb{E}} e^{2\lambda X_i^2} \leq K, \quad \mbox{for all } |\lambda|\leq\eta/2.$$ Hence, \begin{equation} \tag{5}\label{eq4} \operatorname{\mathbb{E}}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq K. \end{equation} By Jensen's inequality, \begin{equation} \tag{6}\label{eq5} e^{\lambda\operatorname{\mathbb{E}}(X_{ki}^2+X_{kj}^2)} = e^{\operatorname{\mathbb{E}}\lambda X_{ki}^2}e^{\operatorname{\mathbb{E}}\lambda X_{kj}^2} \leq \operatorname{\mathbb{E}}e^{\lambda X_{ki}^2} \operatorname{\mathbb{E}}e^{\lambda X_{kj}^2} \leq K^2 \end{equation} Combining \eqref{eq3}, \eqref{eq4} and \eqref{eq5}, \eqref{eq6} is proved.

Source Link
Hepdrey
Hepdrey
  • 100
  • 8

The best I can prove has an extra $K$, but I think it does not matter too much for the proof of the original paper.

\begin{align} n t^2 \mathbb{E}\left(Y_{kij}^2 e^{t|Y_{kij}|} \right) &= n (\eta\sqrt{\log p /n})^2 \mathbb{E}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \eta^2\log p \mathbb{E}\left(Y_{kij}^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &= \log p \mathbb{E}\left((\eta Y_{kij})^2 e^{\eta\sqrt{\log p /n}|Y_{kij}|} \right) \\ &\leq \log p \mathbb{E}\left((\eta Y_{kij})^2 e^{\eta\cdot\eta^{1/2}|Y_{kij}|} \right) \\ &= \eta^{-1}\log p \mathbb{E}\left((\eta^{3/2} Y_{kij})^2 e^{\eta^{3/2}|Y_{kij}|} \right)\\ &\leq \eta^{-1}K^3\log p \tag{1}\label{eq6} \end{align}

The first inequality is by $\log p/n\leq\eta$. The second inequality is proved as follows:

It suffices to show that \begin{equation} \tag{2}\label{eq1} \mathbb{E}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq K^, \quad \mbox{for all } |\lambda|\leq\eta/2. \end{equation} Then by $0<\eta<1/4$ we have $\eta^{3/2}<\eta/2$, hence the result is proved.

Now prove \eqref{eq1}. Since $s^2\leq e^s$ for $s>0$, we have \begin{equation} \tag{3}\label{eq2} \mathbb{E}\left((\lambda Y_{kij})^2 e^{\lambda|Y_{kij}|} \right)\leq \mathbb{E}\left(e^{2\lambda|Y_{kij}|} \right). \end{equation} By definition, we have $$Y_{kij} = \frac{1}{4}\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \mathbb{E}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}.$$ Then following \eqref{eq2} we have \begin{align} \mathbb{E}\left(e^{2\lambda|Y_{kij}|} \right) &= \mathbb{E}\left(e^{\frac{1}{2}\lambda\left\lvert\left\{(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 - \mathbb{E}\left[(X_{ki}+X_{kj})^2 - (X_{ki}-X_{kj})^2 \right]\right\}\right\rvert} \right) \\ &\leq \mathbb{E}\left(e^{\frac{1}{2}\lambda(X_{ki}+X_{kj})^2 + \frac{1}{2}\lambda(X_{ki}-X_{kj})^2 + \mathbb{E}\left[(X_{ki}+X_{kj})^2 \right] + \mathbb{E}\left[(X_{ki}-X_{kj})^2 \right] } \right) \\ &= \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) + \mathbb{E}(X_{ki}^2+X_{kj}^2) } \right) \\ &= e^{\lambda\mathbb{E}(X_{ki}^2+X_{kj}^2)} \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right). \tag{4}\label{eq3} \end{align} By Hölder's inequality, $$\mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq \mathbb{E}^{1/2}\left(e^{2\lambda X_{ki}^2 } \right)\mathbb{E}^{1/2}\left(e^{2\lambda X_{kj}^2 } \right). $$ By the exponential-type tail condition, we have $$\mathbb{E} e^{2\lambda X_i^2} \leq K, \quad \mbox{for all } |\lambda|\leq\eta/2.$$ Hence, \begin{equation} \tag{5}\label{eq4} \mathbb{E}\left(e^{\lambda(X_{ki}^2+X_{kj}^2) } \right) \leq K. \end{equation} By Jensen's inequality, \begin{equation} \tag{6}\label{eq5} e^{\lambda\mathbb{E}(X_{ki}^2+X_{kj}^2)} = e^{\mathbb{E}\lambda X_{ki}^2}e^{\mathbb{E}\lambda X_{kj}^2} \leq \mathbb{E}e^{\lambda X_{ki}^2} \mathbb{E}e^{\lambda X_{kj}^2} \leq K^2 \end{equation} Combining \eqref{eq3}, \eqref{eq4} and \eqref{eq5}, \eqref{eq6} is proved.