Estimation of the covariance structure of heavy-tailed distributions

Introduction

Estimation of the covariance matrix is one of the fundamental problems in data analysis: many important statistical tools, such as Principal Component Analysis(PCA) and regression analysis, involve covariance estimation as a crucial step. For instance, PCA has immediate applications to nonlinear dimension reduction and manifold learning techniques , genetics , computational biology , among many others.

However, assumptions underlying the theoretical analysis of most existing estimators, such as various modifications of the sample covariance matrix, are often restrictive and do not hold for real-world scenarios. Usually, such estimators rely on heuristic (and often bias-producing) data preprocessing, such as outlier removal. To eliminate such preprocessing step from the equation, one has to develop a class of new statistical estimators that admit strong performance guarantees, such as exponentially tight concentration around the unknown parameter of interest, under weak assumptions on the underlying distribution, such as existence of moments of only low order. In particular, such heavy-tailed distributions serve as a viable model for data corrupted with outliers – an almost inevitable scenario for applications.

We make a step towards solving this problem: using tools from the random matrix theory, we will develop a class of robust estimators that are numerically tractable and are supported by strong theoretical evidence under much weaker conditions than currently available analogues. The term “robustness” refers to the fact that our estimators admit provably good performance even when the underlying distribution is heavy-tailed.

Few comments about organization of the material in the rest of the paper: section 1.2 provides an overview of the related work. Section 2 contains the mains results of the paper. The proofs are outlined in section 4; longer technical arguments can be found in the supplementary material.

2 Problem formulation and overview of the existing work

In the discussion accompanying the paper by , write that “data from real-world experiments oftentimes tend to be corrupted with outliers and/or exhibit heavy tails. In such cases, it is not clear that those covariance matrix estimators described in this article remain optimal” and “..what are the other possible strategies to deal with heavy tailed distributions warrant further studies.” This motivates our main goal: develop new estimators of the covariance matrix that (i) are computationally tractable and perform well when applied to heavy-tailed data and (ii) admit strong theoretical guarantees (such as exponentially tight concentration around the unknown covariance matrix) under weak assumptions on the underlying distribution. Note that, unlike the majority of existing literature, we do not impose any further conditions on the moments of $X$, or on the “shape” of its distribution, such as elliptical symmetry.

Main results

Definition of our estimator has its roots in the technique proposed by . Let

be the usual truncation function. As before, let $X_{1},\ldots,X_{m}$ be i.i.d. copies of $X$, and assume that $\widehat{\mu}$ is a suitable estimator of the mean $\mu_{0}$ from these samples, to be specified later. We define $\widehat{\Sigma}$ as

where $\theta\simeq m^{-1/2}$ is small (the exact value will be given later). It easily follows from the definition of the matrix function that

hence it is easily computable. Note that $\psi(x)=x$ in the neighborhood of ; it implies that whenever all random variables $\theta\left\|X_{i}-\widehat{\mu}\right\|_{2}^{2},\ 1\leq i\leq m$ are “small” (say, bounded above by $1$) and $\hat{\mu}$ is the sample mean, $\widehat{\Sigma}$ is close to the usual sample covariance estimator. On the other hand, $\psi$ “truncates” $\left\|X_{i}-\widehat{\mu}\right\|_{2}^{2}$ on level $\simeq\sqrt{m}$, thus limiting the effect of outliers. Our results (formally stated below, see Theorem 2.1) imply that for an appropriate choice of $\theta=\theta(t,m,\sigma)$,

with probability $\geq 1-de^{-\beta}$ for some positive constant $C_{0}$, where

Let $1<\beta<\infty$ be the confidence parameter, and set k=\Big{\lfloor}3.5\beta\Big{\rfloor}+1; we will assume that $k\leq\frac{m}{2}$. Divide the sample $X_{1},\ldots,X_{m}$ into $k$ disjoint groups $G_{1},\ldots,G_{k}$ of size \Big{\lfloor}\frac{m}{k}\Big{\rfloor} each, and define

It then follows from Corollary 4.1 in that

2 Robust covariance estimation

Let $\widehat{\Sigma}$ be the estimator defined in (2) with $\widehat{\mu}$ being the “median-of-means” estimator (2.1). Then $\widehat{\Sigma}$ admits the following performance guarantees:

Assume that $\sigma\geq\sigma_{0}$, and set $\theta=\frac{1}{\sigma}\sqrt{\frac{\beta}{m}}$. Moreover, let $\overline{d}:=\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}$, and suppose that $m\geq C\overline{d}\beta$, where $C>0$ is an absolute constant. Then

with probability at least $1-5de^{-\beta}$.

The quantity $\bar{d}$ is a measure of “intrinsic dimension” akin to the “effective rank” $r=\frac{\mbox{tr}\left(\Sigma_{0}\right)}{\|\Sigma_{0}\|}$; see Lemma 2.3 below for more details. Moreover, note that the claim of Lemma 2.1 holds for any $\sigma\geq\sigma_{0}$, rather than just for $\sigma=\sigma_{0}$; this “degree of freedom” allows construction of adaptive estimators, as it is shown below.

The statement above suggests that one has to know the value of (or a tight upper bound on) the “matrix variance” $\sigma_{0}^{2}$ in order to obtain a good estimator $\widehat{\Sigma}$. More often than not, such information is unavailable. To make the estimator completely data-dependent, we will use Lepski’s method . To this end, assume that $\sigma_{\mbox{\footnotesize{min}\,}},\ \sigma_{\mbox{\footnotesize{max}\,}}$ are “crude” preliminary bounds such that

Usually, $\sigma_{\mbox{\footnotesize{min}\,}}$ and $\sigma_{\mbox{\footnotesize{max}\,}}$ do not need to be precise, and can potentially differ from $\sigma_{0}$ by several orders of magnitude. Set

and $\widehat{\Sigma}_{\ast}:=\widehat{\Sigma}_{m,j_{\ast}}$. Note that the estimator $\widehat{\Sigma}_{\ast}$ depends only on $X_{1},\ldots,X_{m}$, as well as $\sigma_{\mbox{\footnotesize{min}\,}},\ \sigma_{\mbox{\footnotesize{max}\,}}$. Our main result is the following statement regarding the performance of the data-dependent estimator $\widehat{\Sigma}_{\ast}$:

Suppose $m\geq C\overline{d}\beta$, then, the following inequality holds with probability at least $1-5d\log_{2}\left(\frac{2\sigma_{\mbox{\footnotesize{max}\,}}}{\sigma_{\mbox{\footnotesize{min}\,}}}\right)e^{-\beta}$:

An immediate corollary of Theorem 2.1 is the quantitative result for the performance of PCA based on the estimator $\widehat{\Sigma}_{\ast}$. Let $\mbox{{\rm Proj}}_{k}$ be the orthogonal projector on a subspace corresponding to the $k$ largest positive eigenvalues $\lambda_{1},\ldots,\lambda_{k}$ of $\Sigma_{0}$ (here, we assume for simplicity that all the eigenvalues are distinct), and $\widehat{\mbox{{\rm Proj}}_{k}}$ – the orthogonal projector of the same rank as $\mbox{{\rm Proj}}_{k}$ corresponding to the $k$ largest eigenvalues of $\widehat{\Sigma}_{\ast}$. The following bound follows from the Davis-Kahan perturbation theorem , more specifically, its version due to [[]Theorem 3 ]Zwald2006On-the-Converge00.

Let $\Delta_{k}=\lambda_{k}-\lambda_{k+1}$, and assume that $\Delta_{k}\geq 72\sigma_{0}\sqrt{\frac{\beta}{m}}$. Then

with probability $\geq 1-5d\log_{2}\left(\frac{2\sigma_{\mbox{\footnotesize{max}\,}}}{\sigma_{\mbox{\footnotesize{min}\,}}}\right)e^{-\beta}$.

where $C_{1}>0$ is an absolute constant. The main difference between (7) and the bounds of Lemma 2.1 and Theorem 2.1 is that the latter are expressed in terms of $\sigma_{0}^{2}$, while the former is in terms of $B$. The following lemma demonstrates that our bounds are at least as good:

It follows from the above lemma that $\overline{d}=\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}\lesssim d$. Hence, By Theorem 2.1, the error rate of estimator $\widehat{\Sigma}_{\ast}$ is bounded above by $\mathcal{O}(\sqrt{d/m})$ if $m\gtrsim d$. It has been shown (for example, see ) that the minimax lower bound of covariance estimation is of order $\Omega(\sqrt{d/m})$. Hence, the bounds of as well as our results imply correct order of the error. That being said, the “intrinsic dimension” $\bar{d}$ reflects the structure of the covariance matrix and can potentially be much smaller than $d$, as it is shown in the next section.

3 Bounds in terms of intrinsic dimension

In this section, we show that under a slightly stronger assumption on the fourth moment of the random vector $X$, the bound $\mathcal{O}(\sqrt{d/m})$ is suboptimal, while our estimator can achieve a much better rate in terms of the “intrinsic dimension” associated to the covariance matrix. This makes our estimator useful in applications involving high-dimensional covariance estimation, such as PCA. Assume the following uniform bound on the kurtosis of linear forms $\langle Z,v\rangle$:

The intrinsic dimension of the covariance matrix $\Sigma_{0}$ can be measured by the effective rank defined as

Note that we always have $\mathbf{r}(\Sigma_{0})\leq\text{rank}(\Sigma_{0})\leq d$, and it some situations $\mathbf{r}(\Sigma_{0})\ll\text{rank}(\Sigma_{0})$, for instance if the covariance matrix is “approximately low-rank”, meaning that it has many small eigenvalues. The constant $\sigma_{0}^{2}$ is closely related to the effective rank as is shown in the following lemma (the proof of which is included in the supplementary material):

As a result, we have $\mathbf{r}(\Sigma_{0})\leq\overline{d}\leq R^{2}\mathbf{r}(\Sigma_{0})$. The following corollary immediately follows from Theorem 2.1 and Lemma 2.3:

Suppose that $m\geq C\beta\mathbf{r}(\Sigma_{0})$ for an absolute constant $C>0$ and that (8) holds. Then

with probability at least $1-5d\log_{2}\left(\frac{2\sigma_{\mbox{\footnotesize{max}\,}}}{\sigma_{\mbox{\footnotesize{min}\,}}}\right)e^{-\beta}$.

Applications: low-rank covariance estimation

In many data sets encountered in modern applications (for instance, gene expression profiles ), dimension of the observations, hence the corresponding covariance matrix, is larger than the available sample size. However, it is often possible, and natural, to assume that the unknown matrix possesses special structure, such as low rank, thus reducing the “effective dimension” of the problem. The goal of this section is to present an estimator of the covariance matrix that is “adaptive” to the possible low-rank structure; such estimators are well-known and have been previously studied for the bounded and sub-Gaussian observations . We extend these results to the case of heavy-tailed observations; in particular, we show that the estimator obtained via soft-thresholding applied to the eigenvalues of $\widehat{\Sigma}_{\ast}$ admits optimal guarantees in the Frobenius (as well as operator) norm.

Let $\widehat{\Sigma}_{\ast}$ be the estimator defined in the previous section, see equation (6), and set

where $\tau>0$ controls the amount of penalty. It is well-known (e.g., see the proof of Theorem 1 in ) that $\widehat{\Sigma}_{2n}^{\tau}$ can be written explicitly as

where $\lambda_{i}(\widehat{\Sigma}_{\ast})$ and $v_{i}(\widehat{\Sigma}_{\ast})$ are the eigenvalues and corresponding eigenvectors of $\widehat{\Sigma}_{\ast}$. We are ready to state the main result of this section.

For any $\tau\geq 36\sigma_{0}\sqrt{\frac{\beta}{m}},$

with probability $\geq 1-5d\log_{2}\left(\frac{2\sigma_{\mbox{\footnotesize{max}\,}}}{\sigma_{\mbox{\footnotesize{min}\,}}}\right)e^{-\beta}$.

In particular, if $\mbox{{\rm rank}}(\Sigma_{0})=r$ and $\tau=36\sigma_{0}\sqrt{\frac{\beta}{m}}$, we obtain that

with probability $\geq 1-5d\log_{2}\left(\frac{2\sigma_{\mbox{\footnotesize{max}\,}}}{\sigma_{\mbox{\footnotesize{min}\,}}}\right)e^{-\beta}$.

Proofs

The result is a simple corollary of the following statement.

Set $\theta=\frac{1}{\sigma}\sqrt{\frac{\beta}{m}}$, where $\sigma\geq\sigma_{0}$ and $m\geq\beta$. Let $\overline{d}:=\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}$. Then, with probability at least $1-5de^{-\beta}$,

where $C^{\prime}>1$ is an absolute constant.

Now, by Corollary 5.1 in the supplement, it follows that $\overline{d}=\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}\geq\mbox{tr}(\Sigma_{0})/\|\Sigma_{0}\|\geq 1$. Thus, assuming that the sample size satisfies $m\geq(6C^{\prime})^{4}\overline{d}\beta$, then, $\overline{d}\beta/m\leq 1/(6C^{\prime})^{4}<1$, and by some algebraic manipulations we have that

For completeness, a detailed computation is given in the supplement. This finishes the proof.

2 Proof of Lemma 4.1

for any $\|\mu\|_{2}\leq B_{\beta}$. We begin by noting that the error can be bounded by the supremum of an empirical process indexed by $\mu$, i.e.

with probability at least $1-e^{-\beta}$. We first estimate the second term $\left\|\Sigma_{\mu}-\Sigma_{0}\right\|$. For any $\|\mu\|_{2}\leq B_{\beta}$,

with probability at least $1-e^{-\beta}$. It follows from Corollary 5.1 in the supplement that with the same probability

Our main task is then to bound the first term in (12). To this end, we rewrite it as a double supremum of an empirical process:

It remains to estimate the supremum above.

Set $\theta=\frac{1}{\sigma}\sqrt{\frac{\beta}{m}}$, where $\sigma\geq\sigma_{0}$ and $m\geq\beta$. Let $\overline{d}:=\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}$. Then, with probability at least $1-4de^{-\beta}$,

where $C^{\prime\prime}>1$ is an absolute constant.

Note that $\sigma\geq\sigma_{0}$ by defnition, thus, $\overline{d}\leq\sigma^{2}/\|\Sigma_{0}\|^{2}$. Combining the above lemma with (12) and (13) finishes the proof.

3 Proof of Theorem 2.1

Define $\bar{j}:=\min\left\{j\in\mathcal{J}:\ \sigma_{j}\geq\sigma_{0}\right\}$, and note that $\sigma_{\bar{j}}\leq 2\sigma_{0}$. We will demonstrate that $j_{\ast}\leq\bar{j}$ with high probability. Observe that

where we applied (5) to estimate each of the probabilities in the sum under the assumption that the number of samples $m\geq C\overline{d}\beta$ and $\sigma_{k}\geq\sigma_{\bar{j}}\geq\sigma_{0}$. It is now easy to see that the event

of probability $\geq 1-5d\log_{2}\left(\frac{2\sigma_{\mbox{\footnotesize{max}\,}}}{\sigma_{\mbox{\footnotesize{min}\,}}}\right)e^{-\beta}$ is contained in $\mathcal{E}=\left\{j_{\ast}\leq\bar{j}\right\}$. Hence, on $\mathcal{B}$

4 Proof of Theorem 3.1

The proof is based on the following lemma:

Inequality (10) holds on the event $\mathcal{E}=\left\{\tau\geq 2\left\|\widehat{\Sigma}_{\ast}-\Sigma_{0}\right\|\right\}$.

To verify this statement, it is enough to repeat the steps of the proof of Theorem 1 in , replacing each occurrence of the sample covariance matrix by its “robust analogue” $\widehat{\Sigma}_{\ast}$. It then follows from Theorem 2.1 that $\Pr(\mathcal{E})\geq 1-5d\log_{2}\left(\frac{2\sigma_{\mbox{\footnotesize{max}\,}}}{\sigma_{\mbox{\footnotesize{min}\,}}}\right)e^{-\beta}$ whenever $\tau\geq 36\sigma_{0}\sqrt{\frac{\beta}{m}}$.

References

Supplement

The above lemma is useful in our context mainly due to the following lemma,

The truncation function $\frac{1}{\theta}\psi(\theta x)=\textrm{sign}(x)\cdot\left(|x|\wedge\frac{1}{\theta}\right)$ satisfies the assumption (14) in Lemma 5.1.

Denote $f_{1}(x)=-\frac{1}{\theta}\log\left(1-\theta x+\theta^{2}x^{2}\right)$, $f_{2}(x)=\frac{1}{\theta}\log\left(1+\theta x+\theta^{2}x^{2}\right)$ and $g(x)=\textrm{sign}(x)\cdot\left(|x|\wedge\frac{1}{\theta}\right)$. Note first that

Next, we take the derivative of $f_{2}(x)$ and compare it to the derivative of $g(x)$.

The following lemma demonstrates the importance of matrix logarithm function in matrix analysis, whose proof can be found in and ,

is concave on the cone of positive semi-definite matrices.

The following lemma is a generalization of Chebyshev’s association inequality. See Theorem 2.15 of for proof.

The following corollary follows immediately from the FKG inequality.

where the last inequality follows from FKG inequality by taking $f\left(Y_{1}^{2},~{}\cdots,~{}Y_{d}^{2}\right)=Y_{1}^{2}$ and $g\left(Y_{1}^{2},~{}\cdots,~{}Y_{d}^{2}\right)=\|Y\|_{2}^{2}$. ∎

2 Additional computation in the proof of Lemma 2.1

In order to show (11), it is enough to show that

Note that $\overline{d}=\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}\geq\mbox{tr}(\Sigma_{0})/\|\Sigma_{0}\|\geq 1$, and assuming that the sample size satisfies $m\geq(6C^{\prime})^{4}\overline{d}\beta$, we have $\overline{d}\beta/m\leq 1/(6C^{\prime})^{4}<1$. We then bound each of the 6 terms on the left side.

thus, the rest three terms can be bounded as follows,

3 Proof of Lemma 4.2

First of all, by definition of $\widehat{\Sigma}_{\mu}$, we have

Expanding the squares on the right hand side gives

We will then bound these three terms separately. Note that given $\|\widehat{\mu}-\mu_{0}\|_{2}\leq B_{\beta}$, the term (III) can be readily bounded as follows using the fact that $0\leq\psi(x)\leq x,~{}\forall x\geq 0$,

where the second from the last inequality follows from Corollary 5.1 and the last inequality follows from $\overline{d}=\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}$.

The rest two terms are bounded through the following lemma whose proof is delayed to the next section:

Given $\|\widehat{\mu}-\mu_{0}\|_{2}\leq B_{\beta}$, with probability at least $1-4de^{-\beta}$, we have the following two bounds hold,

Note that since $\sigma\geq\sigma_{0}$, we have $\sigma/\|\Sigma_{0}\|\geq\sigma_{0}/\|\Sigma_{0}\|=\sqrt{\overline{d}}$. Combining the above lemma with (15) finishes the proof of Lemma 4.2.

4 Proof of Lemma 5.5

Before proving the Lemma, we introduce the following abbreviations:

Our analysis relies on the following simply yet important fact which gives deterministic upper and lower bound of $h_{\mu}(Z_{i})$ around 1. Its proof is delayed to the next section.

For any $\mu$ such that $\|\mu\|_{2}\leq B_{\beta}$, the following holds:

The following Lemma gives a general concentration bound for heavy tailed random matrices under a mapping $\phi(\cdot)$.

Specifically, if the assumption (14) holds for $\theta=\frac{t}{2\sqrt{m}\sigma_{A}^{2}}$, then we obtain the subgaussian tail $2d\exp(-t^{2}/4\sigma_{A}^{2})$.

The intuition behind this lemma is that the $\log(1+x)$ tends to “robustify” a random variable by implicitly trading the bias for a tight concentration. A scalar version of such lemma with a similar idea is first introduced in the seminal work . The proof of the current matrix version is similar to Lemma 3.1 and Theorem 3.1 of by modifying only the constants. We omitted the details here for brevity. Note that this lemma is useful in our context by choosing $\phi(x)=\frac{1}{\theta}\psi(\theta x)$. Next, we prove two parts of Lemma 5.5 separately.

Using the abbreviation introduced at the beginning of this section, we have

We further split it into two terms as follows:

The two terms in (16) are bounded as follows:

For the second term in (16), note that we can write it back into the matrix form as

Note that the matrix $Z_{i}Z_{i}^{T}$ is a rank one matrix with the eigenvalue equal to $\|Z_{i}\|_{2}^{2}$, so it follows from the definition of matrix function,

Now, applying Lemma 5.2 setting $\theta=\frac{t}{2\sigma^{2}\sqrt{m}}$ together with Lemma 5.7 gives

Setting $t=2\sigma\sqrt{\beta}$ (which results in $\theta=\frac{1}{\sigma}\sqrt{\frac{\beta}{m}}$) gives

with probability at least $1-2de^{-\beta}$.

For the first term in (16), by the fact that $g_{\mathbf{v}}(Z_{i})\geq 0$ and Lemma 5.6,

with probability at least $1-2de^{-\beta}$. Now we substitute $B_{\beta}=11\sqrt{2\mbox{tr}(\Sigma_{0})\beta/m}$ and $\theta=\frac{1}{\sigma}\sqrt{\frac{\beta}{m}}$ into the above bound gives

Substitute these two bounds into the bound of (I) gives the final bound for (I) stated in Lemma 5.5 with probability at least $1-2de^{-\beta}$. ∎

Similar to the analysis of (I), we further split the above term into two terms and get

For the first term, by Cauchy-Schwarz inequality and then Lemma 5.6, we get

Note that $\frac{1}{\theta}\psi\left(\theta\|Z_{i}\|_{2}^{2}\right)/\|Z_{i}\|_{2}^{2}\leq 1$, then, it follows,

Thus, by the same analysis leading to (17), we get

Now by Cauchy-Schwarz inequality and then Markov inequality, we obtain,

where the last two inequalities both follow from Lemma 5.1. This gives the second term in (22) is given by $B_{\beta}\left(\frac{\sigma^{2}}{m}\beta\right)^{1/4}$.

and furthermore, the matrix $\left[\begin{matrix}0&\mathbf{x}^{T}\\ \mathbf{x}&0\end{matrix}\right]$ has two same eigenvalues equal to $\|\mathbf{x}\|_{2}$, which follows from

By matrix Bernstein’s inequality (), we obtain the bound

where $c$ is a fixed positive constant. Taking $t=3\sqrt{\frac{\sigma^{2}\beta}{\|\Sigma_{0}\|m}}$ gives

where $\overline{d}=\sigma^{2}/\|\Sigma_{0}\|^{2}\geq\sigma_{0}^{2}/\|\Sigma_{0}\|^{2}\geq\mbox{tr}(\Sigma_{0})/\|\Sigma_{0}\|\geq 1$ and the last inequality follows from the assumption that $m\geq\beta$. Overall, term (V) is bounded as follows

with probability at least $1-2de^{-\beta}$. Substituting $B_{\beta}=11\sqrt{\frac{2\mbox{tr}(\Sigma_{0})\beta}{m}}$ and $\theta=\frac{1}{\sigma}\sqrt{\frac{\beta}{m}}$ gives

Using the bounds (18) and (19) with some algebraic manipulations, we have the second bound in Lemma 5.5 holds with probability at least $1-2de^{-\beta}$. ∎

5 Proof of Lemma 5.6

We divide our analysis into the following four cases:

If $\|Z_{i}\|_{2}^{2}\leq 1/\theta$ and $\|Z_{i}-\mu\|_{2}^{2}\leq 1/\theta$, then, we have $h_{\mu}(Z_{i})=1$.

If $\|Z_{i}\|_{2}^{2}\leq 1/\theta$ and $\|Z_{i}-\mu\|_{2}^{2}>1/\theta$. Since $\|\mu\|\leq B_{\beta}$, it follows $\|Z_{i}-\mu\|_{2}\leq\sqrt{1/\theta}+B_{\beta}$, and we have

where the last inequality follows from the fact $\frac{1}{1+x}\geq 1-x,~{}\forall x\geq 0$.

If $\|Z_{i}\|_{2}^{2}>1/\theta$ and $\|Z_{i}-\mu\|_{2}^{2}\leq 1/\theta$. Since $\|\mu\|_{2}\leq B_{\beta}$, it follows $\|Z_{i}\|_{2}\leq\sqrt{1/\theta}+B_{\beta}$, and we have

If $\|Z_{i}\|_{2}^{2}>1/\theta$ and $\|Z_{i}-\mu\|_{2}^{2}>1/\theta$. Then, we have

6 Proof of Lemma 2.2

Taking the supremum from both sides of the above inequality and use the previous bound on $B$, we get

7 Proof of Lemma 2.3

where the first inequality uses the fact that the kurtosis is bounded.