---
abstract: 'We consider asymptotic distributions of maximum deviations of sample covariance matrices, a fundamental problem in high-dimensional inference of covariances. Under mild dependence conditions on the entries of the data matrices, we establish the Gumbel convergence of the maximum deviations. Our result substantially generalizes earlier ones where the entries are assumed to be independent and identically distributed, and it provides a theoretical foundation for high-dimensional simultaneous inference of covariances.'
address:
- |
     501 Hill Center\
    110 Frelinghuysen Road\
    Piscataway, NJ 08854\
- |
     Department of Statistics\
    5734 S. University Ave\
    Chicago, IL 60637\
author:
- 
- 
bibliography:
- 'mybib.bib'
title: Simultaneous Inference of Covariances
---

Introduction
============

Let $\boldsymbol{X}_n=\left(X_{ij}\right)_{1\leq i \leq n, 1\leq j
\leq m}$ be a data matrix whose $n$ rows form independent samples from some population distribution with mean vector ${\boldsymbol{\mu}}_n$ and covariance matrix $\Sigma_n$. High dimensional data increasingly occur in modern statistical applications in biology, finance and wireless communication, where the dimension $m$ may be comparable to the number of observations $n$, or even much larger than $n$. Therefore, it is necessary to study the asymptotic behavior of statistics of $\boldsymbol{X}_n$ under the setting that $m=m_n$ grows to infinity as $n$ goes to infinity.

In many empirical examples, it is often assumed that $\Sigma_n=I_m$, where $I_m$ is the $m\times m$ identity matrix, so it is important to perform the test $$\label{eq:1.test}
  H_0:\; \Sigma_n=I_m$$ before carrying out further estimation or inference procedures. Due to high dimensionality, conventional tests often do not work well or cannot be implemented. For example, when $m>n$, the likelihood ratio test (LRT) cannot be used because the sample covariance matrix is singular; and even when $m<n$, the LRT is drifted to infinity and lead to many false rejections if $m$ is also large [@bai:2009]. [@ledoit:2003] found that the empirical distance test [@nagao:1973] is not consistent when both $m$ and $n$ are large. The problem has been studied by several authors under the “large $n$, large $m$” paradigm. [@bai:2009] and [@ledoit:2003] proposed corrections to the LRT and the empirical distance test respectively. Assuming that the population distribution is Gaussian with ${\boldsymbol{\mu}}_n=0$, [@johnstone:2001] used the largest eigenvalue of the sample covariance matrix $\boldsymbol{X}_n^\top\boldsymbol{X}_n$ as the test statistic, and proved that its limiting distribution follows the Tracy-Widom law [@tracy:1994]. Here we use the superscript $\top$ to denote the transpose of a matrix or a vector. His work was extended to the non-Gaussian case by [@soshnikov:2002] and [@peche:2009], where they assumed the entries of $\boldsymbol{X}_n$ are independent and identically distributed (i.i.d.) with sub-Gaussian tails.

Let $x_{1},x_{2},\ldots,x_{m}$ be the $m$ columns of $\boldsymbol{X}_n$. In practice, the entries of the mean vector ${\boldsymbol{\mu}}_n$ are often unknown, and are estimated by $\bar x_i =
(1/n)\sum_{k=1}^n X_{ki}$. Write $x_i-\bar x_i$ for the vector $x_i-\bar x_i {\boldsymbol{1}}_n$, where ${\boldsymbol{1}}_n$ is the $n$-dimensional vector with all entries being one. Let $\sigma_{ij} = {\rm Cov}(X_{1 i},
X_{1 j})$, $1 \le i, j \le m$, be the covariance function, namely, the $(i, j)$th entry of $\Sigma_n$. The sample covariance between columns $x_{i}$ and $x_{j}$ is defined as $$  \hat\sigma_{ij} = \frac{1}{n}{(x_{i}-\bar x_{i})^\top(x_{j}-\bar x_{j})}.$$ In high-dimensional covariance inference, a fundamental problem is to establish an asymptotic distributional theory for the maximum deviation $$M_n = \max_{1\leq i<j\leq m} |\hat\sigma_{ij}-\sigma_{ij}|.$$ With such a distributional theory, one can perform statistical inference for structures of covariance matrices. For example, one can use $M_n$ to test the null hypothesis $H_0:\;\Sigma_n = \Sigma^{(0)}$, where $\Sigma^{(0)}$ is a pre-specified matrix. Here the null hypothesis can be that the population distribution is a stationary process so that $\Sigma_n$ is Toeplitz, or that $\Sigma_n$ has a banded structure.

It is very challenging to derive an asymptotic theory for $M_n$ if we allow dependence among $X_{11}, \ldots, X_{1 m}$. Many of the earlier results assume that the entries of the data matrix $\boldsymbol{X}_n$ are i.i.d.. In this case $\sigma_{i j} = 0$ if $i \not= j$. [@jiang:2004] derived the asymptotic distribution of $$L_n  = \max_{1\leq i<j\leq m} |\hat\sigma_{ij}|.$$

\[thm:jiang\] Suppose $X_{i,j},\;i,j=1,2,\ldots$ are independent and identically distributed as $\xi$ which has variance one. Suppose ${{\mathbb{E}}}|\xi|^{30-\epsilon}<\infty$ for any $\epsilon>0$. If $n/m\rightarrow c\in(0,\infty)$, then for any $y\in{{\mathbb{R}}}$, $$\lim_{n\rightarrow\infty}P\left(nL_n^2 - 4\log m + \log(\log m) + \log(8\pi) \leq y\right) = \exp\left(-e^{-y/2}\right).$$

Jiang’s work has attracted considerable attention, and been followed by [@li:2010], [@liu:2008], [@zhou:2007] and [@li:2006]. Under the same setup that $\boldsymbol{X}_n$ consists of i.i.d. entries, these works focus on three directions (i) reduce the moment condition; (ii) allow a wider range of $p$; and (iii) show that some moment condition is necessary. In a recent article, [@cai:2011a] extended those results in two ways: (i) the dimension $p$ could grow exponentially as the sample size $n$ provided exponential moment conditions; and (ii) they showed that the test statistic $\max_{|i-j|>s_n} |\hat \sigma_{ij}|$ also converges to the Gumbel distribution if each row of $\boldsymbol{X}_n$ is Gaussian and is $s_n$-dependent. The latter generalization is important since it is one of the very few results that allow dependent entries.

In this paper we shall show that a self-normalized version of $M_n$ converges to the Gumbel distribution under mild dependence conditions on the vector $(X_{11}, \ldots, X_{1 m})$. Thus our result provides a theoretical foundation for high-dimensional simultaneous inference of covariances.

The rest of this article is organized as follows. We present the main result in Section \[sec:main\]. In Section \[sec:example\], we use two examples on linear processes and nonlinear processes to demonstrate that the technical conditions are easily satisfied. We discuss three tests for the covariance structure using our main result in Section \[sec:cov\_structure\]. The proof is given in Section \[sec:proof\], and some auxiliary results are collected in Section \[sec:auxiliary\].

Main result {#sec:main}
===========

We consider a slightly more general situation where population distribution can depend on $n$. Let ${\boldsymbol{X}}_n =
(X_{n,k,i})_{1\leq k\leq n, 1\leq i \leq m}$ be a data matrix whose $n$ rows are i.i.d. $m$-dimensional random vectors with mean ${\boldsymbol{\mu}}_n=(\mu_{n,i})_{1\leq i \leq m}$ and covariance matrix $\Sigma_n=(\sigma_{n,i,j})_{1\leq i,j \leq m}$. Let $x_{1},x_{2},\ldots,x_{m}$ be the $m$ columns of $\boldsymbol{X}_n$. Let $\bar x_i = (1/n)\sum_{k=1}^n X_{n,k,i}$, and write $x_i-\bar x_i$ for the vector $x_i-\bar x_i {\boldsymbol{1}}_n$. The sample covariance between $x_{i}$ and $x_{j}$ is defined as $$  \hat\sigma_{n,i,j}
  = \frac{1}{n}{(x_{i}-\bar x_{i})^\top(x_{j}-\bar x_{j})}.$$ It is unnatural to study the maximum of a collection of random variables which are on different scales, so we consider the normalized version $|\hat\sigma_{n,i,j}-\sigma_{n,i,j}|/\tau_{n,i,j}$, where $$\tau_{n,i,j}
  = \operatorname{Var}\left[(X_{n,1,i}-\mu_{n,i})(X_{n,1,j}-\mu_{n,j})\right].$$ In practice, $\tau_{n,i,j}$ are usually unknown, and can be estimated by $$\hat\tau_{n,i,j}
  = \frac{1}{n} \left|(x_{i}-\bar x_{i})\circ(x_{j}-\bar x_{j})
  -\hat\sigma_{n,i,j}\cdot {\boldsymbol{1}}_n\right|^2.$$ where $\circ$ denotes the Hadamard product defined as $A\circ
B:=(a_{ij}b_{ij})$ for two matrices $A=(a_{ij})$ and $B=(b_{ij})$ with the same dimensions. We thus consider $$\label{eq:max_cov}
  M_n = \max_{1 \leq i<j \leq m} \frac{|\hat\sigma_{n,i,j}-\sigma_{n,i,j}|}{\sqrt{\hat\tau_{n,i,j}}}.$$ Due to the normalization procedure, we can assume without loss of generality that $\sigma_{n,i,i}=1$ and $\mu_{n,i}=0$ for each $1\leq i
\leq m$. Define the index set $\mathcal{I}_n=\{(i,j):\,1\leq i<j \leq m\}$, and for $\alpha=(i,j)\in\mathcal{I}_n$, let $X_{n,\alpha}:=X_{n,1,i}X_{n,1,j}$. Define $$\begin{aligned}
  & \mathcal{K}_n(t,p)
   = \sup_{1\leq i \leq m} {{\mathbb{E}}}\exp\left(t |X_{n,1,i}|^p\right), \\
  & \mathcal{M}_n(p)
   = \sup_{1\leq i \leq m} {{\mathbb{E}}}(|X_{n,1,i}|^{p}), \\
  & \tau_n = \inf_{1 \leq i<j \leq m} \tau_{n,i,j}, \\
  & \gamma_n = \sup_{\alpha, \beta \in\mathcal{I}_n
  \hbox{ {\tiny and} } \alpha\neq\beta}
  \left|\operatorname{Cor}(X_{n,\alpha},X_{n,\beta})\right|,  \\
  & \gamma_n(b)=\sup_{\alpha\in\mathcal{I}_n}
  \sup_{\mathcal{A}\subset\mathcal{I}_n,|\mathcal{A}|=b}
  \inf_{\beta \in \mathcal{A}}
    \left|\operatorname{Cor}(X_{n,\alpha},X_{n,\beta})\right|.\end{aligned}$$ We need the following technical conditions. $$\begin{aligned}
  & ({\boldsymbol{\mathrm{A1}}}).\quad \liminf_{n \rightarrow\infty} \tau_n > 0. \\
  & ({\boldsymbol{\rm A2}}).\quad \limsup_{n} \gamma_n<1. \\
  & ({\boldsymbol{\rm A3}}).\quad \gamma_n(b_n) \cdot (\log b_n) = o(1)
  \hbox{ for any sequence $(b_n)$ such that $b_n\rightarrow\infty$.}\\
  & ({\boldsymbol{\rm A3'}}).\quad \gamma_n(b_n) = o(1)
  \hbox{ for any sequence $(b_n)$ such that $b_n\rightarrow\infty$, and}\\
  & \qquad\qquad \sum_{\alpha,\beta\in\mathcal{I}_n}
  \left[\operatorname{Cov}(X_{n,\alpha},X_{n,\beta})\right]^2 = O(m^{4-\epsilon})
  \hbox{for some constant $\epsilon>0$}. \\
  & ({\boldsymbol{\rm A4}}).\quad \log m = o\left(n^{p/(4+2p)}\right) \hbox{ and
  }
  \limsup_{n\rightarrow\infty}\mathcal{K}_n(t,p) < \infty \hbox{ for some constants} \\
  & \qquad \quad\;\;\;\hbox{$t>0$ and $0<p\leq 4$}. \\
  & ({\boldsymbol{\rm A4'}}).\quad m=O(n^q) \hbox{ and }
  \limsup_{n\rightarrow\infty}\mathcal{M}_n(4q+4+\delta)<\infty \hbox{
    for some constants}\\
  & \qquad \quad\;\;\;\hbox{$q>0$ and $\delta>0$}.\end{aligned}$$ The two conditions ($\mathrm{A3}$) and ($\mathrm{A3'}$) require that the dependence among $X_{n,\alpha},\;\alpha\in\mathcal{I}_n$, are not too strong. They are translations of (B1) and (B2) in Section \[sec:normal\_comparison\] (see Remark \[rk:empirical\] for some equivalent versions), and either of them will make our results valid. We use (A2) to get rid of the case where they may be lots of pairs $(\alpha,\beta)\in\mathcal{I}_n$ such that $X_{n,\alpha}$ and $X_{n,\beta}$ are perfectly correlated. Assumptions ($\mathrm{A4}$) and ($\mathrm{A4'}$) connect the growth speed of $m$ relative to $n$ and the moment conditions. They are typical in the context of high dimensional covariance matrix estimation. Condition (A1) excludes the case that $X_{n,\alpha}$ is a constant.

\[thm:max\_cov\] Suppose that ${\boldsymbol{X}}_n = (X_{n,k,i})_{1\leq k\leq n, 1\leq i \leq m}$ is a data matrix whose $n$ rows are i.i.d. $m$-dimensional random vectors, and whose entries have mean zero and variance one. Assume (A1), (A2), either of ($\mathrm{A3}$) and ($\mathrm{A3'}$), and either of ($\mathrm{A4}$) and ($\mathrm{A4'}$), then for any $y \in {{\mathbb{R}}}$, $$\lim_{n\rightarrow\infty}
    P\left(nM_n^2 - 4\log m + \log(\log m)
    + \log(8\pi) \leq y\right)
    = \exp\left(-e^{-y/2}\right).$$

Examples {#sec:example}
========

Except for ($\mathrm{A4}$) and ($\mathrm{A4'}$), which put conditions on every single entry of the random vector $(X_{n,1,i})_{1\leq i \leq m}$, all the other conditions of Theorem \[thm:max\_cov\] are related to the dependence among these entries, which can be arbitrarily complicated. In this section we shall provide examples which satisfy the four conditions (A1), (A2), ($\mathrm{A3}$) and ($\mathrm{A3'}$). Observe that if each row of ${\boldsymbol{X}}_n$ is a random vector with uncorrelated entries (specifically, the entries are independent), then all these conditions are automatically satisfied. They are also satisfied if the number of non-zero covariances is bounded.

Stationary Processes
--------------------

Suppose $(X_{n,k,i})=(X_{k,i})$, and each row of $(X_{k,i})_{1\leq i
  \leq m}$ is distributed as a stationary process $(X_i)_{1\leq i \leq
  m}$ of the form $$\begin{aligned}
  X_i=g(\epsilon_i,\epsilon_{i-1},\ldots)\end{aligned}$$ where $\epsilon_i$’s are i.i.d. random variables, and $g$ is a measurable function such that $X_i$ is well-defined. Let $(\epsilon_i')_{i\in{{\mathbb{Z}}}}$ be an i.i.d. copy of $(\epsilon_i)_{i\in{{\mathbb{Z}}}}$, and $X_i'=g(\epsilon_i,\ldots,\epsilon_1,\epsilon_0',\epsilon_{-1},\epsilon_{-2},\ldots)$. Following [@wu:2005], define the [*physical dependence measure*]{} of order $p$ by $$\begin{aligned}
  \delta_p(i)=\|X_i-X_i'\|_p.\end{aligned}$$ Define the squared tail sum $$\begin{aligned}
  \Psi_p(k)=\left[\sum_{j=k}^\infty (\delta_p(i))^2\right]^{1/2},\end{aligned}$$ and use $\Psi_p$ as a shorthand for $\Psi_p(0)$.

We give sufficient conditions for (A1), (A2), ($\mathrm{A3}$) and ($\mathrm{A3'}$) in the following lemma and leave its proof to the supplementary file.

\[thm:stationary\]

-   If $0<\Psi_4<\infty$ and $\operatorname{Var}(X_iX_j)>0$ for all $i,j\in{{\mathbb{Z}}}$, then (A1) holds.

-   If in addition, $|\operatorname{Cor}(X_iX_j,X_kX_l)|<1$ for all $i,j,k,l$ such that they are not all the same, then (A2) holds.

-   Assume that the conditions of (i) and (ii) hold. If $\Psi_p(k)=o(1/\log k)$ as $k\rightarrow\infty$, then ($\mathrm{A3}$) holds. If $\sum_{j=0}^m (\Psi_4(j))^2 =
        O(m^{1-\delta})$ for some $\delta>0$, then ($\mathrm{A3'}$) holds.

Let $g$ be a linear function with $g(\epsilon_i, \epsilon_{i-1},
\ldots) = \sum_{j=0}^\infty a_j \epsilon_{i-j}$, where $\epsilon_j$ are i.i.d. with mean $0$ and ${{\mathbb{E}}}(|\epsilon_j|^p) <
\infty$ and $a_j$ are real coefficients with $\sum_{j=0}^\infty
a_j^2 < \infty$. Then the physical dependence measure $\delta_p(i)
= |a_i| \|\epsilon_0 - \epsilon_0'\|_p$. If $a_i = i^{-\beta}
\ell(i)$, where $1/2 < \beta < 1$ and $\ell$ is a slowly varying function, then $(X_i)$ is a long memory process. Smaller $\beta$ indicates stronger dependence. Condition (iii) holds for all $\beta \in (1/2, 1)$. Moreover, if $a_i = i^{-1/2}
(\log(i))^{-2}$, $i \ge 2$, which corresponds to the extremal case with very strong dependence $\beta = 1/2$, we also have $\Psi_p(k)
= O( (\log k)^{-3/2} ) = o(1/\log k)$. So our dependence conditions are actually quite mild.

If $(X_i)$ is a linear process which is not identically zero, then the following regularity conditions are automatically satisfied: $\Psi_4>0$, $\operatorname{Var}(X_iX_j)>0$ for all $i,j\in{{\mathbb{Z}}}$, and $|\operatorname{Cor}(X_i
X_j, X_k X_l)|<1$ for all $i,j,k,l$ such that they are not all the same.

Non-stationary Linear Processes
-------------------------------

Assume that each row of $(X_{n,k,i})$ is distributed as $(X_{n,i})_{1\leq i
  \leq m}$, which is of the form $$\begin{aligned}
  X_{n,i}=\sum_{t\in{{\mathbb{Z}}}} f_{n,i,t}\epsilon_{i-t},\end{aligned}$$ where $\epsilon_i,\,i\in{{\mathbb{Z}}}$ are i.i.d. random variables with mean zero, variance one and finite fourth moment, and the sequence $(f_{n,i,t})$ satisfies $\sum_{t\in {{\mathbb{Z}}}} f_{n,i,t}^2=1$. Denote by $\kappa_4$ the fourth cumulant of $\epsilon_0$. For $1\leq i,j,k,l
\leq m$, we have $$\begin{aligned}
  \sigma_{n,i,j} & = \sum_{t\in{{\mathbb{Z}}}} f_{n,i,i-t}f_{n,j,j-t}, \\
  \operatorname{Cov}(X_{n,i}X_{n,j},X_{n,k}X_{n,l})
  & = \mathrm{Cum}(X_{n,i},X_{n,j},X_{n,k},X_{n,l})
  + \sigma_{n,i,k}\sigma_{n,j,l}+\sigma_{n,i,l}\sigma_{n,j,k},\end{aligned}$$ where $\mathrm{Cum}(X_{n,i},X_{n,j},X_{n,k},X_{n,l})$ is the fourth order joint cumulant of the random vector $(X_{n,i},X_{n,j},X_{n,k},X_{n,l})^\top$, which can be expressed as $$\begin{aligned}
  \mathrm{Cum}(X_{n,i},X_{n,j},X_{n,k},X_{n,l})
  = \sum_{t\in{{\mathbb{Z}}}} f_{n,i,i-t}f_{n,j,j-t}f_{n,k,k-t}f_{n,l,l-t}\kappa_4,\end{aligned}$$ by the multilinearity of cumulants. In particular, we have $$\begin{aligned}
  \operatorname{Var}(X_iX_j) = 1 + \sigma_{n,i,j}^2
  + \kappa_4\cdot\sum_{t \in {{\mathbb{Z}}}} f_{n,i,t}^2f_{n,j,t}^2.\end{aligned}$$ Since $\kappa_4 = \operatorname{Var}(\epsilon_0^2) - 2 \left({{\mathbb{E}}}\epsilon_0^2\right)^2 \geq -2$, the condition $$\begin{aligned}
  \label{eq:cumulant}
  \kappa_4>-2\end{aligned}$$ guarantees ($\mathrm{A1}$) in view of $$\begin{aligned}
  \operatorname{Var}(X_iX_j) \geq (1 + \sigma_{n,i,j}^2)(1+\min\{\kappa/2,0\})
  \geq \min\{1,1+\kappa/2\}>0.\end{aligned}$$

To ensure the validity of ($\mathrm{A2}$), it is natural to assume that no pairs $X_{n,i}$ and $X_{n,j}$ are strongly correlated, [ *i.e.*]{} $$\begin{aligned}
  \label{eq:corr}
  \limsup_{n\rightarrow\infty}\sup_{1\leq i<j\leq m}\left|\sum_{t\in{{\mathbb{Z}}}}f_{n,i,i-t}f_{n,j,j-t}\right|<1.\end{aligned}$$ We need the following lemma, whose proof is elementary and will be given in the supplementary file.

\[thm:normal\] The condition (\[eq:corr\]) suffices for ($\mathrm{A2}$) if $\epsilon_i$’s are i.i.d. $N(0,1)$.

As an immediate consequence, when $\epsilon_i$’s are i.i.d. $N(0,1)$, we have $$\begin{aligned}
  \ell:=\limsup_{n\rightarrow\infty} \inf_{\ast}\inf_{\rho\in{{\mathbb{R}}}}\operatorname{Var}\left(X_{n,i}X_{n,j}-\rho X_{n,k}X_{n,l}\right) > 0,\end{aligned}$$ where $\inf_{\ast}$ is taken over all $1\leq i,j,k,l \leq m$ such that $i<j$, $k<l$ and $(i,j)\neq(k,l)$. Observe that when $\epsilon_i$’s are i.i.d. $N(0,1)$, $$\begin{aligned}
  \label{eq:var}
  \operatorname{Var}\left(X_{n,i}X_{n,j}-\rho X_{n,k}X_{n,l}\right) & =
  2\cdot\sum_{t\in{{\mathbb{Z}}}}(f_{n,i,i-t}f_{n,j,j-t}-\rho f_{n,k,k-t}f_{n,l,l-t})^2\\ \nonumber
  & + \sum_{s<t}
    \left(f_{n,i,i-t}f_{n,j,j-s}+f_{n,i,i-s}f_{n,j,j-t} \right.\\ \nonumber
    & \quad\;
    \left. -\rho f_{n,k,k-t}f_{n,l,l-s}-\rho f_{n,k,k-s}f_{n,l,l-t}\right)^2;\end{aligned}$$ and when $\epsilon_i$’s are arbitrary variables, the variance is given by the same formula with the number 2 in (\[eq:var\]) being replaced by $2+\kappa_4$. Therefore, if (\[eq:cumulant\]) holds, then $$\begin{aligned}
  \limsup_{n\rightarrow\infty} \inf_{\ast}\inf_{\rho\in{{\mathbb{R}}}}\operatorname{Var}\left(X_{n,i}X_{n,j}-\rho X_{n,k}X_{n,l}\right)
  \geq \min\{1,1+\kappa_4/2\}\cdot\ell>0,\end{aligned}$$ which implies $(\mathrm{A2})$ holds. To summarize, we have shown that (\[eq:cumulant\]) and (\[eq:corr\]) suffice for $(\mathrm{A2})$.

Now we turn to Conditions ($\mathrm{A3}$) and ($\mathrm{A3'}$). Set $$\begin{aligned}
  h_n(k)=\sup_{1\leq i \leq m}\left(\sum_{|t|={\lfloor k/2 \rfloor}}^\infty f_{n,i,t}^2\right)^{1/2},\end{aligned}$$ where ${\lfloor x \rfloor}=\max\{y\in{{\mathbb{Z}}}\,:\,y \leq x\}$ for any $x\in{{\mathbb{E}}}$, then we have $$\begin{aligned}
  |\sigma_{n,i,j}| \leq 2h_n(0)h_n(|i-j|) = 2h_n(|i-j|).\end{aligned}$$ Fixing a subset $\{i,j\}$, for any integer $b>0$, there are at most $8b^2$ subsets $\{k,l\}$ such that $\{k,l\}\subset B(i;b)\cup B(j;b)$, where $B(x;r)$ is the open ball $\{y:|x-y|<r\}$. For all other subsets $\{k,l\}$, we have $$\begin{aligned}
  |\operatorname{Cov}(X_{n,i}X_{n,j},X_{n,k}X_{n,l})| \leq (4+2\kappa_4)h_n(b),\end{aligned}$$ and hence ($\mathrm{A3}$) holds if we assume $h_n(k_n)\log k_n = o(1)$ for any positive sequence $(k_n)$ such that $k_n\rightarrow\infty$. ($\mathrm{A3'}$) holds if we assume $$\begin{aligned}
  \sum_{k=1}^m [h_n(k)]^2 = O\left(m^{1-\delta}\right).\end{aligned}$$ for some $\delta>0$, because $$\begin{aligned}
  \left|\operatorname{Cov}(X_{n,i}X_{n,j},X_{n,k}X_{n,l})\right| \leq 2\kappa_4h_n(|i-j|) + 2h_n(|i-k|) + 2h_n(|i-l|).\end{aligned}$$

Testing for covariance structures {#sec:cov_structure}
=================================

The asymptotic distribution given in Theorem \[thm:max\_cov\] has several statistical applications. One of them is in high dimensional covariance matrix regularization, because Theorem \[thm:max\_cov\] implies a uniform convergence rate for all sample covariances. Recently, [@cai:2011b] explored this direction, and proposed a thresholding procedure for sparse covariance matrix estimation, which is adaptive to the variability of each individual entry. Their method is superior to the uniform thresholding approach studied by [@bickel:2008b].

Testing structures of covariance matrices is also a very important statistical problem. As mentioned in the introduction, when the data dimension is high, conventional tests often cannot be implemented or do not work well. Let $\Sigma_n$ and $R_n$ be the covariance matrix and correlation matrix of the random vector $(X_{n,1,i})_{1\leq i \leq m}$ respectively. Two types of tests have been studied under the large $n$, large $m$ paradigm. [@chen:2010], [@bai:2009], [@ledoit:2003] and [@johnstone:2001] considered the test $$\label{eq:3.identity}
  H_0:\;\Sigma_n=I_m;$$ and [@liu:2008], [@schott:2005], [@srivastava:2005] and [@jiang:2004] studied the problem of testing for complete independence $$\label{eq:3.sphericity}
  H_0:\;R_n=I_m.$$ Their testing procedures are all based on the critical assumption that the entries of the data matrix ${\boldsymbol{X}}_n$ are i.i.d., while the hypotheses themselves only require the entries of $(X_{n,1,i})_{1\leq
  i \leq m}$ to be uncorrelated. Evidently, we can use $M_n$ in (\[eq:max\_cov\]) to test (\[eq:3.sphericity\]), and we only require the uncorrelatedness for the validity of the limiting distribution established in Theorem \[thm:max\_cov\], as long as the mild conditions of the theorem are satisfied. On the other hand, we can also take the sample variances into consideration, and use the following test statistic $$M_n' = \max_{1 \leq i\leq j \leq m} \frac{|\hat\sigma_{n,i,j}-\sigma_{n,i,j}|}{\sqrt{\hat\tau_{n,i,j}}}.$$ to test the identity hypothesis (\[eq:3.identity\]), where $\sigma_{n,i,j}=I\{i=j\}$. It is not difficult to verify that $M_n'$ has the same asymptotic distribution as $M_n$ under the same conditions with the only difference being that we now have to take sample variances into account as well, namely, the index set $\mathcal{I}_n$ in Section \[sec:main\] is redefined as $\mathcal{I}_n = \{(i,j):\,1\leq i\leq j\leq m\}$. Clearly, we can also use $M_n'$ to test $H_0:\;\Sigma_n=\Sigma^0$ for some known covariance matrix $\Sigma^0$.

By checking the proof of Theorem \[thm:max\_cov\], it can be seen that if instead of taking the maximum over the set $\mathcal{I}_n=\{(i,j):\,1\leq i<j \leq m\}$, we only take the maximum over some subset $A_n\subset\mathcal{I}_n$ whose cardinality $|A_n|$ converges to infinity, then the maximum also has the Gumbel type convergence with normalization constants which are functions of the cardinality of the set $A_n$. Based on this observation, we are able to consider three more testing problems.

Test for stationarity
---------------------

Suppose we want to test whether the population is a stationary time series. Under the null hypothesis, each row of the data matrix ${\boldsymbol{X}}_n$ is distributed as a stationary process $(X_i)_{1\leq i \leq
  m}$. Let $\gamma_l=\operatorname{Cov}(X_0,X_l)$ be the autocovariance at lag $l$. In principle, we can use the following test statistic $$\tilde T_n = \max_{1 \leq i\leq j \leq m} \frac{|\hat\sigma_{n,i,j}-\gamma_{i-j}|}{\sqrt{\hat\tau_{n,i,j}}}.$$ The problem is that $\gamma_l$ are unknown. Fortunately, they can not only be estimated, but also be estimated with higher accuracy $$\hat{\gamma}_{n,l} = \frac{1}{nm}\sum_{k=1}^n\sum_{i=|l|+1}^n (X_{n,k,i-|l|}-\hat\mu_n)(X_{n,k,i}-\hat\mu_n),$$ where $\hat\mu_n = (1/nm) \sum_{k=1}^n\sum_{i=1}^m X_{n,k,i}$, and we are lead to the test statistic $$T_n = \max_{1 \leq i\leq j \leq m} \frac{|\hat\sigma_{n,i,j}-\hat\gamma_{i-j}|}{\sqrt{\hat\tau_{n,i,j}}}.$$ Using similar arguments of Theorem 2 of [@wu:2011a], under suitable conditions, we have $$\max_{0 \leq l \leq m-1} |\hat\gamma_{n,l}-\gamma_l| = O_P(\sqrt{\log m/nm}).$$ Therefore, the limiting distribution for $M_n$ in Theorem \[thm:max\_cov\] also holds for $T_n$.

Test for bandedness
-------------------

In time series and longitudinal data analysis, it can be of interest to test whether $\Sigma_m$ has the banded structure. The hypothesis to be tested is $$\label{eq:3.bandedness}
  H_0:\; \sigma_{n,i,j}=0 \hbox{ if } |i-j|>B,$$ where $B=B_n$ may depend on $n$. [@cai:2011a] studied this problem under the assumption that each row of the data matrix ${\boldsymbol{X}}_n$ is a Gaussian random vector. They proposed to use the maximum sample correlation outside the band $$\tilde T_n = \max_{|i-j|>B} \frac{\hat\sigma_{n,i,j}}{\sqrt{\hat\sigma_{n,i,i}\hat\sigma_{n,j,j}}}$$ as the test statistic, and proved that $T_n$ also has the Gumbel type convergence provided that $B_n=o(m)$ and several other technical conditions hold.

Apparently, our Theorem \[thm:max\_cov\] can be employed to test (\[eq:3.bandedness\]). If all the conditions of the theorem are satisfied, the test statistic $$T_n = \max_{|i-j|>B_n} \frac{|\hat\sigma_{n,i,j}|}{\sqrt{\hat\tau_{n,i,j}}}.$$ has the same asymptotic distribution as $M_n$ as long as $B_n=o(m)$. Our theory does not need the normality assumption.

Assess the tapering procedure
-----------------------------

Banding and tapering are commonly used regularization procedures in high dimensional covariance matrix estimation. Convergence rates were first obtained by [@bickel:2008a], and later on improved by [@cai:2010]. Let us introduce a weaker version of the latter result. Suppose each row of ${\boldsymbol{X}}_n$ is distributed as the random vector $X=(X_i)_{1\leq i \leq m}$ with mean $\mu$ and covariance matrix $\Sigma=(\sigma_{ij})$. Let $K_0,K$ and $t$ be positive constants, and $\mathscr{C}_{\eta}(K_0, K, t)$ be the class of $m$-dimensional distributions which satisfy the following conditions $$\begin{aligned}
  & \max_{|i-j|=k} |\sigma_{ij}| \leq Kk^{-(1+\eta)} \quad\hbox{for all } k; \label{eq:3.decay} \\
  & \lambda_{\max}(\Sigma) \leq K_0; \cr
  & P\left[|v^\top(X-\mu)|>x\right] \leq e^{-tx^2/2} \quad \hbox{for all $x>0$ and $\|v\|=1$}; \nonumber\end{aligned}$$ where $\lambda_{\max}(\Sigma)$ is the largest eigenvalue of $\Sigma$. For a given even integer $1\leq B \leq m$, define the tapered estimate of the covariance matrix $\Sigma$ $$\begin{aligned}
  \hat\Sigma_{n,B_n} = \left(w_{ij}\hat\sigma_{n,i,j}\right),\end{aligned}$$ where the weights correspond to a flat top kernel and are given by $$\begin{aligned}
  w_{ij} = \left\{
    \begin{array}{ll}
      1, & \hbox{when } |i-j| \leq B_n/2, \\
      2-2|i-j|/B_n, & \hbox{when } B_n/2<|i-j|\leq B_n, \\
      0, & \hbox{otherwise}.
    \end{array}\right.\end{aligned}$$

\[thm:cai\] If $m \geq n^{1/(2\eta+1)}$, $\log m = o(n)$ and $B_n=n^{1/(2\eta+1)}$, then there exists a constant $C>0$ such that $$\begin{aligned}
    \sup_{\mathscr{C}_\eta} {{\mathbb{E}}}\left[{\lambda({\hat{\Sigma}_{n,B_n}-\Sigma})}\right]^2
    \leq Cn^{-2\eta/(2\eta+1)} + C\frac{\log m}{n}.
  \end{aligned}$$

We see that it is the parameter $\eta$ that decides the convergence rate under the operator norm. After such a tapering procedure has been applied, it is important to ask whether it is appropriate, and in particular, whether (\[eq:3.decay\]) is satisfied. We propose to use $$\begin{aligned}
  T_n = \max_{|i-j|>B_n} \frac{|\hat\sigma_{n,i,j}|}{\sqrt{\hat\tau_{n,i,j}}}\end{aligned}$$ as the test statistic. According to the observation made at the beginning of Section \[sec:cov\_structure\], if the conditions of Theorem \[thm:max\_cov\] are satisfied, then $$\begin{aligned}
  T_n'= \max_{|i-j|>B_n} \frac{|\hat\sigma_{n,i,j}-\sigma_{i,j}|}{\sqrt{\hat\tau_{n,i,j}}}\end{aligned}$$ has the same limiting law as $M_n$. On the other hand, (\[eq:3.decay\]) implies that $$\begin{aligned}
  \max_{|i-j|>B_n} |\sigma_{i,j}| = O\left(n^{-(1+\eta)/(2\eta+1)}\right),\end{aligned}$$ so $T_n$ has the same limiting distribution as $T_n'$ if we further assume $\log m = o\left(n^{2/(4\eta+2)}\right)$.

Proof {#sec:proof}
=====

The proofs of Theorem \[thm:max\_cov\] under ($\mathrm{A4}$) and ($\mathrm{A4'}$) are very similar, and they share a common Poisson approximation step, which we will formulate in Section \[sec:max\_mean\] under a more general context, where the limiting distribution of the maximum of sample means is obtained. Since the proof under ($\mathrm{A4'}$) is more involved, we provide the detailed proof under this assumption in Section \[sec:a4’\], and point out in Section \[sec:a4\] how it can be adapted to give a proof under ($\mathrm{A4}$).

Maximum of Sample Means: An Intermediate Step {#sec:max_mean}
---------------------------------------------

In this section we provide a general result on the maximum of sample means. Let ${\boldsymbol{Y}}_n=(Y_{n,k,i})_{1\leq k \leq n,\,i\in\mathcal{I}_n}$ be a data matrix whose $n$ rows are independent and identically distributed, and whose entries have mean zero and variance one, where $\mathcal{I}_n$ is an index set with cardinality $|\mathcal{I}_n|=s_n$. For each $i \in \mathcal{I}_n$, let $y_i$ be the $i$-th column of ${\boldsymbol{Y}}_n$, $\bar y_i = (1/n)\sum_{k=1}^n
Y_{n,k,i}$. Define $$\label{eq:max_mean}
      W_n = \max_{i \in \mathcal{I}_n} {|\bar y_i|}.$$ Let $\Sigma_n$ be the covariance matrix of the $s_n$-dimensional random vector $(Y_{n,1,i})_{i \in \mathcal{I}_n}$.

\[thm:max\_mean\] Assume $\Sigma_n$ satisfies either (B1) or (B2) of Section \[sec:normal\_comparison\] and $\log s_n
  =o(n^{1/3})$. Suppose there is a constant $C>0$ such that $Y_{n,k,i}
  \in \mathscr{B}(1,Ct_n)$ for each $1\leq k \leq
  n,\;i\in\mathcal{I}_n$, with $$t_n = \frac{\sqrt{n}\delta_n}{(\log s_n)^{3/2}}, $$ where $(\delta_n)$ is a sequence of positive numbers such that $\delta_n=o(1)$ and $(\log s_n)^3/n=o(\delta_n)$, and the definition of the collection $\mathscr{B}(d,\tau)$ is given in (\[eq:bernstein\]). Then $$\label{eq:max_mean_convergence}
    \lim_{n\rightarrow\infty}P\left(nW_n^2 - 2\log s_n + \log (\log s_n) + \log \pi \leq z \right)
    =\exp\left(-e^{-z/2}\right).$$

For each $z\in{{\mathbb{R}}}$, let $z_n=a_{2s_n}z/2 + b_{2s_n}$. Let $(Z_{n,i})_{i\in\mathcal{I}_n}$ be a mean zero normal random vector with covariance matrix $\Sigma_n$. For any subset $A=\{i_1,i_2,\ldots,i_d\} \subset \mathcal{I}_n$, let $y_A=\sqrt{n}(\bar y_{i_1}, \bar y_{i_2}, \ldots, \bar
  y_{i_d})^\top$ and $Z_{A}=(Z_{i_1}, Z_{i_2}, \ldots, Z_{i_d})$. By Lemma \[thm:zaitsev\], we have for $\theta_n =
  \delta_n^{1/2}/\sqrt{\log s_n}$ that $$\begin{aligned}
    P\left(|y_{A}|_\bullet > z_n\right) & \leq P(|Z_A|_{\bullet}>z_n - \theta_n)
    + C_d\exp\left\{-\frac{\theta_n}{C_d \delta_n(\log s_n)^{-3/2}}\right\} \\
    & \leq P(|Z_A|_{\bullet}>z_n - \theta_n) + C_d\exp\left\{-(\log s_n)\delta_n^{-1/2}\right\}
  \end{aligned}$$ Therefore, $$\begin{aligned}
    \sum_{A \subset \mathcal{I}_n, |A|=d} & P\left(|y_{A}|_\bullet > z_n\right) \\
    & \leq \sum_{A \subset \mathcal{I}_n, |A|=d} P(|Z_A|_{\bullet}>z_n - \theta_n)
    + C_ds_n^d \exp\left\{-(\log s_n)\delta_n^{-1/2}\right\}.
  \end{aligned}$$ Similarly, we have $$\begin{aligned}
    \sum_{A \subset \mathcal{I}_n, |A|=d} & P\left(|y_{A}|_\bullet > z_n\right) \\
    & \geq \sum_{A \subset \mathcal{I}_n, |A|=d} P(|Z_A|_{\bullet}>z_n + \theta_n)
    - C_ds_n^d \exp\left\{-(\log s_n)\delta_n^{-1/2}\right\}.
  \end{aligned}$$ Since $(z_n\pm\theta_n)^2 = 2\log s_n - \log (\log s_n) - \log \pi +
  z + o(1)$, by Lemma \[thm:normal\_comparison\], we know $$\begin{aligned}
    \lim_{n\rightarrow\infty} \sum_{A \subset \mathcal{I}_n, |A|=d} P(|Z_A|_{\bullet}>z_n \pm \theta_n)
    = \frac{e^{-dz/2}}{d\,!},
  \end{aligned}$$ and hence $$\begin{aligned}
    \lim_{n\rightarrow\infty}\sum_{A \subset \mathcal{I}_n, |A|=d} P\left(|y_{A}|_\bullet > z_n\right)
    = \frac{e^{-dz/2}}{d\,!}.
  \end{aligned}$$ The proof is complete in view of Lemma \[thm:poisson\].

Proof under ($\mathrm{A4'}$) {#sec:a4'}
----------------------------

We divide the proof into three steps. The first one is a truncation step, which will make the Gaussian approximation result Lemma \[thm:zaitsev\] and the Bernstein inequality applicable, so that we can prove Theorem \[thm:max\_cov\] under the assumption that all the involved mean and variance parameters are known. In the next two steps we show that plugging in estimated mean and variance parameters does not change the limiting distribution.

#### 

For notational simplicity we let $q=p/(4+2p)$. Define $$\begin{aligned}
  \label{eq:3.truncation}
  \tilde X_{n,k,i} = X_{n,k,i}I\left\{|X_{n,k,i}|\leq n^{1/(4+2p)}\right\},\end{aligned}$$ and define $\tilde M_n$ similarly as $M_n$ with $X_{n,k,i}$ being replaced by its truncated version $\tilde X_{n,k,i}$. Since $\log m =
o (n^{q})$, we have $$\begin{aligned}
  P\left(\tilde M_n \neq M_n\right) & \leq \sum_{k=1}^n\sum_{i=1}^m
  P\left[|X_{n,k,i}| > n^{1/(4+2p)}\right] \\
  & \leq nm \mathcal{K}_n(t,p) \exp\left\{-t n^{p/(4+2p)}\right\} \\
  & = \mathcal{K}_n(t,p) \exp\left\{-tn^{q} + \log m + \log n\right\}
  = o(1).\end{aligned}$$ Therefore, in the rest of the proof, it suffices to consider $\tilde
X_{n,k,i}$. For notational simplicity, we still use $\tilde X_{n,k,i}$ to denote its centered version with mean zero.

Define $\tilde \sigma_{n,i,j}={{\mathbb{E}}}\left(\tilde X_{n,1,i}\tilde
  X_{n,1,j}\right)$, and $\tilde \tau_{n,i,j} = \operatorname{Var}\left(\tilde
X_{n,1,i}\tilde X_{n,1,j}\right)$. Set $$\begin{aligned}
  M_{n,1} & = \max_{1\leq i<j \leq m} \frac{1}{\sqrt{\tilde \tau_{n,i,j}}}
  \left|\frac{1}{n} \sum_{k=1}^n \tilde X_{n,k,i}\tilde X_{n,k,j} -\tilde \sigma_{n,i,j} \right|; \\
  M_{n,2} & = \max_{1\leq i<j \leq m} \frac{1}{\sqrt{\tilde \tau_{n,i,j}}}
  \left|\frac{1}{n} \sum_{k=1}^n \tilde X_{n,k,i}\tilde X_{n,k,j} - \sigma_{n,i,j} \right|. \\\end{aligned}$$ Elementary calculations show that $$\begin{aligned}
  \label{eq:3.2}
  \max_{1\leq i \leq j \leq m} |\tilde \sigma_{n,i,j} - \sigma_{n,i,j}| & \leq C \exp \left\{-tn^{q}/2
    \right\},\quad\hbox{and} \\ \label{eq:3.3}
  \max_{\alpha, \beta \in \mathcal{I}_n} \left|\operatorname{Cov}(\tilde X_{n,\alpha}, \tilde X_{n,\beta} ) -
  \operatorname{Cov}(X_{n,\alpha}, X_{n,\beta})\right| & \leq C \exp \left\{-tn^{q}/2
    \right\}.\end{aligned}$$ By (\[eq:3.3\]), we know the covariance matrix of $(\tilde
X_{n,\alpha})_{\alpha\in\mathcal{I}_n}$ satisfies either (B1) or (B2) if $\Sigma_n$ satisfies (B1) or (B2) correspondingly. On the other hand, we have by elementary calculation that there exists a constant $C_{p}>0$ such that $$\begin{aligned}
  \limsup_{n\rightarrow\infty}\max_{\alpha \in \mathcal{I}_n} {{\mathbb{E}}}\exp\{C_p t  |\tilde X_{n,\alpha}|^{p/2}\} < \infty.\end{aligned}$$ It follows that when $0<p<2$, for each integer $r \geq 3$ $$\begin{aligned}
  {{\mathbb{E}}}|\tilde X_{n,\alpha}|^{r} & \leq {{\mathbb{E}}}|\tilde X_{n,\alpha}|^{rp/2} \cdot \left(4 n^{2/(4+2p)}\right)^{r(1-p/2)} \\
  & \leq \left(4 n^{2/(4+2p)}\right)^{r(1-p/2)} r! (C_pt)^{-r} {{\mathbb{E}}}\exp\{C_p t |X_{n,\alpha}|^{p/2}\}.\end{aligned}$$ Therefore, $$\begin{aligned}
  {{\mathbb{E}}}_0\tilde X_{n,\alpha} \in \mathscr{B}\left[1,C\frac{\sqrt{n}}{n^{2p/(4+2p)}}\right].\end{aligned}$$ When $2 \leq p \leq 4$, it is easily seen that ${{\mathbb{E}}}_0\tilde X_{n,\alpha}
\in \mathscr{B}(1,C)$. Since $\log m = o (n^q)$, we know all the conditions of Lemma \[thm:max\_mean\] are satisfied, and hence $$\label{eq:3.4}
  \lim_{n\rightarrow\infty}P\left(nM_{n,1}^2 - 4\log m + \log(\log m) + \log(8\pi) \leq y\right)
  = \exp\left(-e^{-y/2}\right).$$ Combining (\[eq:3.2\]) and (\[eq:3.3\]), we know the preceding equation (\[eq:3.4\]) also holds with $M_{n,1}$ being replaced by $M_{n,2}$.

#### 

Set $\bar X_{n,i} = (1/n)\sum_{k=1}^n \tilde X_{n,k,i}$. Define $$\begin{aligned}
  M_{n,3} = \max_{1\leq i<j \leq m} \frac{1}{\sqrt{\tilde \tau_{n,i,j}}}
  \left|\frac{1}{n} \sum_{k=1}^n (\tilde X_{n,k,i}-\bar X_{n,i})(\tilde X_{n,k,j}-\bar X_{n,j}) - \sigma_{n,i,j} \right|.\end{aligned}$$ In this step we show that (\[eq:3.4\]) also holds for $M_{n,3}$. Observe that $$\begin{aligned}
  \left|M_{n,3} - M_{n,2}\right| \leq \max_{1\leq i<j \leq m} \frac{|\bar X_{n,i}\bar{X}_{n,j}|}{\sqrt{\tilde \tau_{n,i,j}}}
  \leq \max_{1 \leq i \leq m}|\bar X_{n,i}|^2 \cdot \left(\min_{1 \leq i<j \leq m} \tilde \tau_{n,i,j}\right)^{-1/2}.\end{aligned}$$ Since each $X_{n,k,i}$ is bounded by $2n^{1/(4+2p)}$, by Bernstein’s inequality we have for any constant $K>0$, $$\begin{aligned}
  \max_{1\leq i \leq m}P\left(|\bar X_{n,i}| > 2K\sqrt{\log m \over n}\right)
  & \leq C \exp\left\{ -\frac{2K^2 n \log m}{C n + 2K \sqrt{n\log m}
      \cdot 2n^{1/(4+2p)}} \right\} \\
  & \leq C m^{-K^2/C},\end{aligned}$$ and hence $$\begin{aligned}
  \label{eq:3.1}
  \max_{1 \leq i \leq m}|\bar X_{n,i}| = O_P\left(\sqrt{\frac{\log m}{n}}\right),\end{aligned}$$ which together with (\[eq:3.3\]) implies that $$\begin{aligned}
  \left|M_{n,3} - M_{n,2}\right| = O_P\left(\frac{\log m}{n}\right) = o_P\left(\sqrt{\frac{1}{n \log m}}\right).\end{aligned}$$ Therefore, (\[eq:3.4\]) also holds for $M_{n,3}$.

#### 

Denote by $\check{\sigma}_{n,i,j}$ the estimate of $\tilde\sigma_{n,i,j}$ $$\begin{aligned}
  {\check\sigma_{n,i,j}} = \frac{1}{n} \sum_{k=1}^n (\tilde X_{n,k,i}-\bar X_{n,i})(\tilde X_{n,k,j}-\bar X_{n,j}).\end{aligned}$$ In the definition of $\tilde M_n$, $\tilde\tau_{n,i,j}$ is unknown, and is estimated by $$\begin{aligned}
  {\check\tau_{n,i,j}} = \frac{1}{n}\sum_{k=1}^n
  \left[(\tilde X_{n,k,i} - \bar X_{n,i}) (\tilde X_{n,k,j} - \bar X_{n,j}) - {\check\sigma_{n,i,j}}\right]^2\end{aligned}$$ In this step we show that (\[eq:3.4\]) holds for $\tilde M_{n}$. Since $$\begin{aligned}
  n\left|M_{n,3}^2-\tilde M_n^2\right| \leq nM_{n,3}^2 \cdot \max_{1\leq i<j\leq m}|1-\tilde\tau_{n,i,j}/\check\tau_{n,i,j}|,\end{aligned}$$ it suffices to show that $$\begin{aligned}
  \label{eq:3.5}
    \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j}-\tilde\tau_{n,i,j}\right| = o_P(1/\log m).\end{aligned}$$ Set $$\begin{aligned}
  \check\tau_{n,i,j,1} & = \frac{1}{n}\sum_{k=1}^n
  \left[(\tilde X_{n,k,i} - \bar X_{n,i}) (\tilde X_{n,k,j} - \bar X_{n,j}) - {\tilde\sigma_{n,i,j}}\right]^2 \\
    \check\tau_{n,i,j,2} & = \frac{1}{n}\sum_{k=1}^n
  \left(\tilde X_{n,k,i} \tilde X_{n,k,j} - {\tilde\sigma_{n,i,j}}\right)^2.\end{aligned}$$ Observe that $$\begin{aligned}
  \check\tau_{n,i,j,1} - \check\tau_{n,i,j} = (\check\sigma_{n,i,j} - \tilde\sigma_{n,i,j})^2\end{aligned}$$ which in together with (\[eq:3.4\]) implies that $$\begin{aligned}
  \label{eq:3.6}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,1}-\check\tau_{n,i,j}\right| = O_P \left(\log m/n\right).\end{aligned}$$ Note that $\tilde X_{n,k,i,j}$ are uniformly bounded according to the truncation (\[eq:3.truncation\]), so $$\begin{aligned}
  \left(\tilde X_{n,k,i} \tilde X_{n,k,j} - {\tilde\sigma_{n,i,j}}\right)^2 \leq 64 n^{4/(4+2p)}.\end{aligned}$$ By Bernstein’s inequality, we have $$\begin{aligned}
  \max_{1\leq i<j\leq m} P\left(|\check\tau_{n,i,j,2}-\tilde\tau_{n,i,j}| \geq  2n^{-q}\right)
  & \leq \exp\left\{-\frac{2 n^{2(1-q)}}{Cn + 2n^{1-q} \cdot 128n^{4/(4+2p)}/3}\right\} \\
  & \leq \exp\left(-n^q/100\right),\end{aligned}$$ and it follows that $$\begin{aligned}
  \label{eq:3.7}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,2}-\tilde\tau_{n,i,j}\right| 
  = O_P(n^{-q}).$$ In view of (\[eq:3.6\]), (\[eq:3.7\]), and the assumption $\log
m=o(n^q)$, we know to show (\[eq:3.5\]), it remains to prove $$\begin{aligned}
  \label{eq:3.8}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,1}-\check\tau_{n,i,j,2}\right| = o_P(1/\log m).\end{aligned}$$ Elementary calculations show that $$\begin{aligned}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,1}-\check\tau_{n,i,j,2}\right|
  \leq 4h_{n,1}^2h_{n,2} +  3h_{n,1}^4 + 4h_{n,4}^{1/2}h_{n,2}^{1/2}h_{n,1} 
  + 2h_{n,3}h_{n,1}^2,\end{aligned}$$ where $$\begin{aligned}
  h_{n,1} & =\max_{1\leq i \leq m} |\bar X_{n,i}| \\
  h_{n,2} & = \max_{1\leq i \leq m} \frac{1}{n}\sum_{k=1}^n \tilde X_{n,k,i}^2 \\
  h_{n,3} & = \max_{1\leq i\leq j \leq m}
  \left|\frac{1}{n}\sum_{k=1}^n \tilde X_{n,k,i} \tilde X_{n,k,j} - \tilde\sigma_{n,i,j}\right|\\
  h_{n,4} & = \check\tau_{n,i,j,2}.\end{aligned}$$ By (\[eq:3.1\]), we know $h_{n,1}=O_P(\sqrt{\log m/n})$. By (\[eq:3.7\]) we have $h_{n,4}=O_P(1)$. Combining (\[eq:3.truncation\]) and the Bernstein’s inequality, we can show that $$\begin{aligned}
    h_{n,3}= O_P\left(\sqrt{{\log m}/{n}}\right).\end{aligned}$$ As an immediate consequence, we know $h_{n,2}=O_P(1)$. Therefore, $$\begin{aligned}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,1}-\check\tau_{n,i,j,2}\right| = O_P\left(\sqrt{{\log m}/{n}}\right),\end{aligned}$$ and (\[eq:3.8\]) holds by using the assumption $\log m
=o(n^{q})=o(n^{1/3})$. The proof of Theorem \[thm:max\_cov\] under ($\mathrm{A4'}$) is now complete.

Proof under (A4) {#sec:a4}
----------------

We follow the proof in Section \[sec:a4’\], and point out necessary modifications to make it work under (A4). If not specified, all the notations have the same definitions as in Section \[sec:a4’\]. For notational simplicity, we let $p=4(1+q)+\delta$.

#### 

We truncate $X_{n,k,i}$ by $$\begin{aligned}
  \tilde X_{n,k,i} = X_{n,k,i}I\left\{|X_{n,k,i}|\leq n^{1/4}/\log n\right\},\end{aligned}$$ then $$\begin{aligned}
  P\left(\tilde M_n \neq M_n\right) \leq nm \mathcal{M}_n(p) n^{-p/4}(\log n)^p
  \leq C \mathcal{M}_n(p) n^{-\delta/4}(\log n)^p = o(1).\end{aligned}$$ Therefore, in the rest of the proof, it suffices to consider $\tilde
X_{n,k,i}$. For notational simplicity, we still use $\tilde X_{n,k,i}$ to denote its centered version with mean zero.

Elementary calculations show that $$\begin{aligned}
  \label{eq:3.11}
  \max_{1\leq i \leq j \leq m} |\tilde \sigma_{n,i,j} - \sigma_{n,i,j}| & \leq C n^{-(p-2)/4} (\log n)^{p-2},
  \quad\hbox{and} \\ \label{eq:3.12}
  \max_{\alpha, \beta \in \mathcal{I}_n} \left|\operatorname{Cov}(\tilde X_{n,\alpha}, \tilde X_{n,\beta} ) -
  \operatorname{Cov}(X_{n,\alpha}, X_{n,\beta})\right| & \leq C n^{-(p-4)/4} (\log n)^{p-4}.\end{aligned}$$ By (\[eq:3.11\]), we know the covariance matrix of $(\tilde
X_{n,\alpha})_{\alpha\in\mathcal{I}_n}$ satisfies either (B1) or (B2) if $\Sigma_n$ satisfies (B1) or (B2) correspondingly. Since $${{\mathbb{E}}}_0\tilde X_{n,\alpha} \in \mathscr{B}\left[1,8\sqrt{n}/(\log
  n)^2\right],$$ we know all the conditions of Lemma \[thm:max\_mean\] are satisfied, and hence (\[eq:3.4\]) holds for $M_{n,1}$. Combining (\[eq:3.11\]) and (\[eq:3.12\]), we know (\[eq:3.4\]) also holds with if we replace $M_{n,1}$ by $M_{n,2}$.

#### 

Using Bernstein’s inequality, we can show $$\begin{aligned}
  \max_{1 \leq i \leq m}|\bar X_{n,i}| = O_P\left(\sqrt{\frac{\log n}{n}}\right),\end{aligned}$$ which implies that $$\begin{aligned}
  \left|M_{n,3} - M_{n,2}\right| = O_P\left(\frac{\log n}{n}\right) $$ and hence (\[eq:3.4\]) also holds for $M_{n,3}$.

#### 

It suffices to show that $$\begin{aligned}
  \label{eq:3.13}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j}-\tilde\tau_{n,i,j}\right| = o_P(1/\log n).\end{aligned}$$ Using (\[eq:3.4\]), we know $$\begin{aligned}
  \label{eq:3.15}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,1}-\check\tau_{n,i,j}\right| = O_P \left(\log n/n\right).\end{aligned}$$ Since $$\begin{aligned}
  \left(\tilde X_{n,k,i} \tilde X_{n,k,j} - {\tilde\sigma_{n,i,j}}\right)^2 \leq 64 n/(\log n)^4.\end{aligned}$$ By Corollary 1.6 of [@nagaev:1979] (with $x=n/(\log n)^2$ and $y=n/[2(\log n)^3]$ in their inequality (1.22)), we have $$\begin{aligned}
  \max_{1\leq i<j\leq m}
  P\left(|\check\tau_{n,i,j,2}-\tilde\tau_{n,i,j}| \geq (\log
    n)^{-2}\right) & \leq \left[\frac{Cn}{n(\log n)^{-2} \cdot [n(\log
      n)^{-3}/2]^{q\wedge 1}}\right]^{\log n} \\
  & \leq \left[\frac{C(\log n)^5}{n^{q\wedge 1}}\right]^{\log n},\end{aligned}$$ and it follows that $$\begin{aligned}
  \label{eq:3.16}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,2}
  -\tilde\tau_{n,i,j}\right| = O_P\left[(\log n)^{-2}\right].\end{aligned}$$ In view of (\[eq:3.15\]), (\[eq:3.16\]), we know to show (\[eq:3.13\]), it remains to prove $$\begin{aligned}
  \label{eq:3.17}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,1}-\check\tau_{n,i,j,2}\right| = o_P(1/\log n).\end{aligned}$$ We know $h_{n,1}=O_P(\sqrt{\log n/n})$ and $h_{n,4}=O_P(1)$. Using the Bernstein’s inequality, we can show that $$\begin{aligned}
    h_{n,3}= O_P\left(\sqrt{{\log n}/{n}}\right),\end{aligned}$$ and it follows that $h_{n,2}=O_P(1)$. Therefore, $$\begin{aligned}
  \max_{1\leq i<j\leq m} \left|\check\tau_{n,i,j,1}-\check\tau_{n,i,j,2}\right| = O_P\left(\sqrt{{\log n}/{n}}\right),\end{aligned}$$ and (\[eq:3.17\]) holds. The proof of Theorem \[thm:max\_cov\] under ($\mathrm{A4}$) is now complete.

Some auxiliary results {#sec:auxiliary}
======================

In this section we provide a normal comparison principle and a Gaussian approximation result, and a Poisson convergence theorem.

A normal comparison principle {#sec:normal_comparison}
-----------------------------

Suppose for each $n\geq 1$, $(X_{n,i})_{i\in\mathcal{I}_n}$ is a Gaussian random vector whose entries have mean zero and variance one, where $\mathcal{I}_n$ is an index set with cardinality $|\mathcal{I}_n|=s_n$. Let $\Sigma_n=(r_{n,i,j})_{i,j\in\mathcal{I}_n}$ be the covariance matrix of $(X_{n,i})_{i\in\mathcal{I}_n}$. Assume that $s_n\rightarrow\infty$ as $n\rightarrow\infty$.

We impose either of the following two conditions. $$  \begin{aligned}
    \hbox{({\bf B1}) } & \hbox{For any sequence $(b_n)$ such that $b_n\rightarrow\infty$, }
    \gamma(n,b_n)= o\left({1}/{\log b_n}\right);\\
    & \hbox{and } \limsup_{n\rightarrow\infty}\gamma_n<1. \\
    \hbox{({\bf B2}) } & \hbox{For any sequence $(b_n)$ such that $b_n\rightarrow\infty$, }
    \gamma(n,b_n)=o(1);\\
    & \sum_{i\neq j \in \mathcal{I}_n} r_{n,i,j}^2=O\left(s_n^{2-\delta}\right)
     \hbox{ for some } \delta>0; \hbox{ and }
    \limsup_{n\rightarrow\infty}\gamma_n<1.
  \end{aligned}$$ where $$\begin{aligned}
  & \gamma(n,b_n):=\sup_{i\in\mathcal{I}_n}
  \sup_{\mathcal{A}\subset\mathcal{I}_n,|\mathcal{A}|=b_n}
  \inf_{j\in \mathcal{A}}
  \left|r_{n,i,j}\right|\\
  & \hbox{and} \quad
  \gamma_n:=\sup_{i,j\in\mathcal{I}_n;\; i\neq j}|r_{n,i,j}|.\end{aligned}$$

\[thm:normal\_comparison\] Assume either (B1) or (B2). For a positive real number $z_n$, define $$A_{n,i}'=\{|X_{n,i}| > z_n\} \quad\hbox{and}\quad
    Q_{n,d}' = \sum_{\mathcal{A}\subset\mathcal{I}_n,|\mathcal{A}|=d}
    P\left(\bigcap_{i\in\mathcal{A}} A_{n,i}'\right).$$ If $z_n$ satisfies that $z_n^2 = 2\log s_n - \log\log s_n -\log
  \pi + 2z + o(1)$, then for all $d \geq 1$. $$\lim_{n \to \infty} Q_{n,d}' = \frac{e^{-dz}}{d\,!},$$

Lemma \[thm:normal\_comparison\] is a refined version of Lemma 20 in [@wu:2011a], so we omit the proof and put the details in a supplementary file.

\[rk:empirical\] The conditions imposed on $\gamma(n,b_n)$ seem a little involved. We have the following equivalent versions. Define $$\begin{aligned}
    G_n(t) = \max_{i \in \mathcal{I}_n} \sum_{j\in\mathcal{I}_n}
    I\{|r_{n,i,j}|>t\}.
  \end{aligned}$$ Then (i) $\gamma(n,b_n)=o(1)$ for any sequence $b_n \to \infty$ if and only if the sequence $[G_n(t)]_{n\geq 1}$ is bounded for all $t>0$; and (ii) $\gamma(n,b_n)(\log b_n)=o(1)$ for any sequence $b_n \to \infty$ if and only if $G_n(t_n) = \exp \{o(1/t_n)\}$ for any positive sequence $(t_n)$ converging to zero.

A Gaussian approximation result
-------------------------------

For a positive integer $d$, let $\mathfrak{B}_d$ be the Borel $\sigma$-field on the Euclidean space $\mathbb{R}^d$. For two probability measures $P$ and $Q$ on $\left(\mathbb{R}^d,
  \mathfrak{B}_d\right)$ and $\lambda>0$, define the quantity $$  \pi(P,Q;\lambda) =
  \sup_{A\in\mathfrak{B}_d}\left\{\max \left[P(A) - Q\left(A^\lambda\right),Q(A) - P\left(A^\lambda\right)\right]\right\},$$ where $A^{\lambda}$ is the $\lambda$-neighborhood of $A$ $$A^\lambda := \left\{x \in \mathbb{R}^d:\;\inf_{y\in A}|x-y|<\lambda\right\}.$$ For $\tau>0$, let $\mathscr{B}(d,\tau)$ be the collection of $d$-dimensional random variables which satisfy the multivariate analogue of the Bernstein’s condition. Denote by $(x,y)$ the inner product of two vectors $x$ and $y$. $$\label{eq:bernstein}
  \begin{aligned}
    \mathscr{B}(d,\tau)=& \left\{
    \xi \hbox{ is a random variable}:\;{{\mathbb{E}}}\xi=0, \hbox{ and }
      \phantom{\langle\xi,t\rangle^2}\right.\\
    & \left| {{\mathbb{E}}}\left[(\xi,t)^2(\xi,u)^{m-2}\right] \right|
      \leq \frac{1}{2}m!\tau^{m-2}\|u\|^{m-2}{{\mathbb{E}}}\left[(\xi,t)^2\right]  \\
    & \left.\hbox{for every }
    m=3,4,\ldots \hbox{ and for all } t,u\in\mathbb{R}^d
    \right\}.
  \end{aligned}$$ The following Lemma on the Gaussian approximation is taken from [@zaitsev:1987].

\[thm:zaitsev\] Let $\tau>0$, and $\xi_1,\xi_2,\ldots,\xi_n \in {{\mathbb{R}}}^d$ be independent random vectors such that $\xi_i\in\mathscr{B}(d,\tau)$ for $i=1,2,\ldots,n$. Let $S=\xi_1+\xi_2+\ldots+\xi_n$, and $\mathscr{L}(S)$ be the induced distribution on ${{\mathbb{R}}}^d$. Let $\Phi$ be the Gaussian distribution with the zero mean and the same covariance matrix as that of $S$. Then for all $\lambda>0$ $$\pi[\mathscr{L}(S),\Phi;\lambda]
    \leq c_{1,d} \exp\left(-\frac{\lambda}{c_{2,d}\tau}\right),$$ where the constants $c_{j,d},\;j=1,2$ may be taken in the form $c_{j,d} = c_j d^{5/2}$.

Poisson approximation: moment method
------------------------------------

\[thm:poisson\] Suppose for each $n\geq 1$, $(A_{n,i})_{i\in\mathcal{I}_n}$ is a finite collection of events. Let $I_{A_{n,i}}$ be the indicator function of $A_{n,i}$, and $W_n=\sum_{i\in\cal I}I_{A_{n,i}}$. For each $d \geq 1$, define $$Q_{n,d} = \sum_{\mathcal{A}\subset\mathcal{I}_n,|\mathcal{A}|=d}
    P\left(\bigcap_{i\in\mathcal{A}} A_{n,i}\right).$$ Suppose there exists a $\lambda>0$ such that $$\lim_{n\rightarrow\infty} Q_{n,d} = {\lambda^d}/{d\,!} \hbox{ for each } d\geq 1.$$ Then $$\lim_{n\rightarrow\infty} P(W_n = k) = \lambda^ke^{-\lambda}/k\,! \hbox{ for each } k\geq 0.$$

Observe that for each $d\geq 1$, the $d$-th factorial moment of $W_n$ is given by $${{\mathbb{E}}}\left[W_n(W_n-1)\cdots(W_n-d+1)\right] = d\,! \cdot  Q_{n,d},$$ so Lemma \[thm:poisson\] is essentially the moment method. The proof is elementary, and we omit details.
