The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
15,597 characters
A remark on moment-dependent phase transitions in high-dimensional Gaussian approximations
\title{A remark on moment-dependent phase transitions in high-dimensional Gaussian approximations\footnote{
We thank Moritz Jirak for pointing out the work of~\cite{zhangwu2017} to us.}
}
\author{
\begin{tabular}{c}
Anders Bredahl Kock \\
\small University of Oxford \\
\small St.~Hilda's College\\
\small 10 Manor Rd, Oxford OX1 3UQ
\\
\small {\small [email removed]}
\end{tabular}
\and
\begin{tabular}{c}
David Preinerstorfer \\
{\small SEPS-SEW} \\
{\small University of St.Gallen} \\
{\small Varnb\"uelstrasse 14, 9000 St.Gallen } \\
{\small [email removed]}
\end{tabular}
}
\maketitle
\begin{abstract}
In this article, we study the critical growth rates of dimension below which Gaussian critical values can be used for hypothesis testing but beyond which they cannot. We are particularly interested in how these growth rates depend on the number of moments that the observations possess.
\end{abstract}
\newpage
\section{Introduction}
Let~$\bm{X}_1,\hdots,\bm{X}_n$ be centered independent random vectors in~$\mathbb{R}^d$ and let~$\bm{S}_n=n^{-1/2}\sum_{i=1}^n\bm{X}_i$. Since the path-breaking paper of \cite{chernozhukov2013gaussian} there has been a huge interest in Gaussian approximations to the distribution of~$\bm{S}_n$ when~$d$ is large relative to $n$. In particular, letting~$\bm{Z}~\sim \mathsf{N}_d(\bm{0}_d,\bm{\Sigma})$, with~$\bm{\Sigma}=n^{-1}\sum_{i=1}^n E[\bm{X}_i\bm{X}_i']$, increasingly refined upper bounds on the ``Gaussian approximation error'' (GAE)
\begin{align}\label{eq:approxerror}
\rho_n(\mathcal{A})=\sup_{A\in \mathcal{A}}\envert[1]{P\del[1]{\bm{S}_n\in A}-P\del[1]{\bm{Z}\in A}}
\end{align}
have been established over various classes of subsets~$\mathcal{A}$ of~$\mathbb{R}^d$ with particular emphasis on hyperrectangles and closely related sets; \cite{chernozhukov2017central, deng2020beyond, lopes2020bootstrapping, kuchibhotla2020high, das2021central, koike2021notes, kuchibhotla2021high, lopes2022central, chernozhuokov2022improved, chernozhukov2023nearly}. We refer to the review in~\cite{chernozhukov2023high} for further references. Results for~$\mathcal{A}$ the class of convex sets can be found in \cite{nagaev2006estimate, senatov1981uniform, gotze1991rate, bentkus2003dependence, bentkus2005lyapunov, fang2020large}. Recently, the class of Euclidean balls has been studied in~\cite{zhilova2020nonclassical,zhilova2022new}.
It is crucial to know the critical growth rate of dimension~$d$ as a function of the sample size~$n$ for which~$\rho_n(\mathcal{A})$ vanishes asymptotically. In particular, in their Remark 2~\cite{zhangwu2017} constructed i.i.d.~$\bm{X}_{ij}$ possessing exactly~$m\in(2,\infty)$ moments such that
\begin{align}\label{eq:breakdwonzw}
\lim_{n\to\infty}\envert[3]{\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{S}_{nj}> \sqrt{2\log(d)}}-\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{Z}_j> \sqrt{2\log(d)}}}=1
\end{align}
as soon as~$\lim_{n\to\infty}d/n^{m/2-1+\varepsilon}>0$ for some~$\varepsilon\in(0,\infty)$. This implies~$\lim_{n\to\infty}\rho_n(\mathcal{H})= 1$ where
\begin{align*}
\mathcal{H}=\cbr[2]{(-\infty,t]^d: t\in\mathbb{R}}.
\end{align*}
On the other hand, it known (and a simple consequence of, e.g.,~Theorem~2 in~\cite{chernozhukov2023high} as detailed in Theorem~\ref{thm:cherno} below) that~$\lim_{n\to\infty}\rho_n(\mathcal{R})=0$ uniformly over a large family of distributions with bounded~$m$th moments if there exists an~$\varepsilon\in(0,\infty)$ such that~$\lim_{n\to\infty}d/n^{m/2-1-\varepsilon}=0$, where
\begin{align*}
\mathcal{R}=\cbr[3]{\prod_{j=1}^{d}[a_j,b_j] \cap \mathbb{R} :\ -\infty\leq a_j\leq b_j\leq \infty,\ j=1,\hdots,d}.
\end{align*}
Because~$\mathcal{H}\subseteq\mathcal{R}$, it follows that for Gaussian approximations over~$\mathcal{H}$ and~$\mathcal{R}$ a critical phase transition occurs at~$d=n^{m/2-1}$. As~$d$ passes this threshold from below, the limiting GAE jumps from zero to one. We emphasize the following consequences of this phase transition:
\begin{enumerate}
\item \emph{(Very) high-dimensional central limit theorems are only possible for distributions with light tails.} It is \emph{necessary} to impose that \emph{all} moments of the $\bm{X}_{ij}$ exist if one wishes~$\rho_n(\mathcal{H})$ to vanish under exponential growth rates of~$d$ unless one is willing to either i) further restrict the class of distributions under consideration (cf.~the example following Theorem 2 in~\cite{chernozhukov2023high}) or ii) consider families of sets strictly smaller than~$\mathcal{H}$.
\item \emph{Minimum number of moments needed for a target polynomial growth rate of~$d$.} For a desired polynomial growth rate~$d=n^{\zeta}$ for some~$\zeta\in(0,\infty)$, a necessary condition for~$\rho_n(\mathcal{H})\to 0$ is that~$m\geq 2(\zeta+1)$. Thus, one needs the~$\bm{X}_{ij}$ to have roughly ``twice as many moments''~$m$ as the desired growth exponent~$\zeta$ of~$d=n^\zeta$.
\item \emph{The gain in growth rate of~$d$ from considering~$\mathcal{H}$ instead of convex sets.} Let~$\mathcal{C}=\cbr[0]{C\subseteq\mathbb{R}^{d}:C\text{ is convex}}$. Theorem 1.1 in~\cite{bentkus2003dependence} implies that for i.i.d.~triangular arrays $\bm{X}_{i}$ with mean zero,~$\bm{\Sigma}=\mathbf{I}$, and bounded third moments one has~$\rho_n(\mathcal{C})\to 0$ if~$d=n^{2/7}$ while from the above~$\rho_n(\mathcal{H})\to 1$ if~$d$ increases slightly faster than~$n^{1/2}$. Thus, the most one can generically gain by considering the smaller~$\mathcal{H}$ instead of~$\mathcal{C}$ in the setting of bounded third moments is a growth rate of~$d$ of~$n^{1/2}$ over~$\mathcal{H}$ instead of~$n^{2/7}$ over~$\mathcal{C}$; in particular, one still needs~$d/n\to 0$ in order for~$\rho_n(\mathcal{H})\to 0$.
\end{enumerate}
However, a primary reason for the surge of interest in high-dimensional Gaussian approximations is that they justify the use of Gaussian critical values for hypothesis testing and for the construction of confidence sets based on the statistic~$\max_{1\leq j\leq d}\bm{S}_{nj}$.\footnote{Although we focus on the statistic~$\max_{1\leq j\leq d}\bm{S}_{nj}$, our findings remain valid for the statistic~$\max_{1\leq j\leq d}|\bm{S}_{nj}|$, cf.~Remark~\ref{rem:suptest}.} For this purpose it is enough that the Gaussian approximation is valid at the critical values~$c_d(\alpha)$ of the targeted size~$\alpha\in(0,1)$ of the test only rather than uniformly over~$\mathcal{H}$. That is, only for fixed~$\alpha\in(0,1)$ and~$c_d(\alpha)$ satisfying $\mathbb{P}\del[1]{\max_{1\leq j\leq d}\bm{Z}_j> c_d(\alpha)}\to\alpha$ as~$d\to\infty$, one needs
\begin{align}\label{eq:us}
\lim_{n\to\infty}\envert[3]{\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{S}_{nj}> c_d(\alpha)}-\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{Z}_j> c_d(\alpha)}}=0,
\end{align}
but not the stronger property
\begin{align}\label{eq:wu}
\lim_{n\to\infty}\rho_n(\mathcal{H})
=
\lim_{n\to\infty}\sup_{t\in\mathbb{R}}\envert[3]{\mathbb{P}\del[3]{\max_{1\leq j\leq d}\bm{S}_{nj}> t}-\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{Z}_j> t}}=0
\end{align}
typically focused on in the literature. In particular, even though there exist distributions with~$m$ moments such that~\eqref{eq:wu} fails to be true when $\limsup_{n\to\infty}d/n^{m/2-1+\varepsilon}>0$ by the mentioned result in~\cite{zhangwu2017}, the statistically important approximation in~\eqref{eq:us} could still hold. This would open the door to Gaussian critical values being valid even for~$d$ growing much faster than~$n^{m/2-1}$. We show that this is not the case as already the distributions constructed in~\cite{zhangwu2017} satisfy that
\begin{align*}
\limsup_{n\to\infty}\sbr[3]{\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{S}_{nj}> c_d(\alpha)}-\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{Z}_j> c_d(\alpha)}}=1-\alpha,
\end{align*}
as soon as~$\limsup_{n\to\infty}d/n^{m/2-1+\varepsilon}>0$ for some~$\varepsilon\in(0,\infty)$.\footnote{The sequence~$\sqrt{2\log(d)}$ used to reveal the breakdown of the Gaussian approximation in~\eqref{eq:breakdwonzw} by~\cite{zhangwu2017} satisfies~$\mathbb{P}\del[1]{\max_{1\leq j\leq d}\bm{Z}_j> \sqrt{2\log(d)}}\to 0$ and thus implies an asymptotic size of zero.} Thus, the phase transition also takes place at the critical values, irrespectively of the choice of~$\alpha\in(0,1)$. From a statistical perspective, our results imply that the asymptotic size of max-type tests based on critical values obtained from Gaussian approximations jumps from a desired level~$\alpha\in(0,1)$ to 1 when~$d$ passes the above threshold --- a complete breakdown in size control rather than only a slight inflation.
We emphasize here that we do not show the dependence on $d$ of many quantities introduced above (e.g., $\bm{S}_n$ or $\bm{X}_i$, $\mathcal{H}$ and $\mathcal{R}$, etc.). Furthermore, the dependence of $d$ on $n$ is notationally suppressed. This is done to simplify the presentation. All proofs are given in the Appendix.
\section{The phase transition at Gaussian critical values}\label{sec:LB}
To present our results, from now on let~$\bm{Z}$ be a random vector in~$\mathbb{R}^{d}$ distributed as $\mathsf{N}_{d}(\bm{0}_{d},\mathbf{I}_{d})$ and for~$\alpha\in(0,1)$ denote by~$c_{d}(\alpha)$ a sequence (of critical values) satisfying
\begin{align}\label{eq:critvalmaxtest}
\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{Z}_{j}> c_{d}(\alpha)}\to\alpha\qquad\text{as }d\to\infty.
\end{align}
The distributions~$P_m$ on $\mathbb{R}$ used in the following theorem are given in explicit form in~\eqref{eq:P_m} in Section~\ref{sec:dist}. Recall that~$\bm{S}_n=n^{-1/2}\sum_{i=1}^n\bm{X}_i$.
\begin{theorem}\label{thm:LB}
Let~$m\in(2,\infty)$,~$\alpha\in(0,1)$, and~$c_d(\alpha)$ be a sequence that satisfies~\eqref{eq:critvalmaxtest}. There exist~i.i.d.~random vectors~$\bm{X}_1,\hdots,\bm{X}_n$ with independent entries~$\bm{X}_{ij}\sim P_m$, and~$P_m$ depending neither on~$n$ nor~$d$, having mean zero, variance one, and finite~$m$th absolute moment, such that if for some~$\varepsilon\in(0,\infty)$ it holds that
\begin{align}\label{eq:ratecondtion}
\limsup_{n\to\infty}\frac{d}{n^{m/2-1+\varepsilon}}>0,
\end{align}
then
\begin{align}\label{eq:LB1}
\limsup_{n\to\infty} \sbr[3]{\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{S}_{nj}> c_{d}(\alpha)}-\mathbb{P}\del[2]{\max_{1\leq j\leq d}\bm{Z}_{j}> c_{d}(\alpha)}}=1-\alpha.
\end{align}
\end{theorem}
The consequences of~\eqref{eq:LB1} relative to~\eqref{eq:breakdwonzw} and~$\rho_n(\mathcal{H})\to 0$ for hypothesis testing are discussed further in Section~\ref{sec:consequencestesting} below.
Let~$m\in[4,\infty)$, $c$ and $C$ such that~$0 < c \leq C^{2/m} < \infty$, and denote by~$\mathsf{P}(m,c,C)$ the class of distributions such that the~$\bm{X}_{i}$ are i.i.d., with entries having mean zero, covariance matrix~$\bm{\Sigma}$, $\min_{1\leq j\leq d}E\bm{X}_{1j}^2\geq c$, and $\max_{1\leq j\leq d}E|\bm{X}_{1j}|^m\leq C$.\footnote{Note that if $c > C^{2/m}$ then~$\mathsf{P}(m,c,C)$ is empty.} The following theorem, which provides sufficient conditions for Gaussian approximations to hold when~$d/n^{m/2-1-\varepsilon}\to 0$ for some~$\varepsilon\in (0,\infty)$, is a special case of Theorem 2 in~\cite{chernozhukov2023high}.
\begin{theorem}\label{thm:cherno}
Let~$m\in[4,\infty)$. If there exists an~$\varepsilon\in(0,\infty)$ such that
\begin{align}\label{eq:chernorate}
\frac{d}{n^{m/2-1-\varepsilon}} \to 0,
\end{align}
then for $c$ and $C$ such that~$0 < c \leq C^{2/m} < \infty$ one has
\begin{align*}
\lim_{n\to\infty}\sup_{R\in\mathcal{R}} \sup_{P\in \mathsf{P}(m,c,C)} \envert[2]{P\del[1]{\bm{S}_n\in R}-\mathbb{P}\del[1]{\bm{\Sigma}^{1/2}\bm{Z}\in R} }= 0.
\end{align*}
\end{theorem}
Together Theorems~\ref{thm:LB} and~\ref{thm:cherno} reveal a critical phase transition in the asymptotic behavior of the Gaussian approximation error at the critical values~$c_d(\alpha)$ at~$d=n^{m/2-1}$. We next discuss the consequences of this for hypothesis testing.
\section{Consequences for high-dimensional hypothesis testing}\label{sec:consequencestesting}
To appreciate the statistical importance of our results, assume that the mean~$\bm{\mu}\in\mathbb{R}^d$ of the~$\bm{X}_i$ is unknown and that the $\bm{X}_{ij}$ possess $m \in (2, \infty)$ moments. One then frequently wishes to test
\begin{align*}
H_0: \bm{\mu}=\bm{0}_d\quad \text{against}\quad H_1:\bm{\mu}_j>0\text{ for some }j=1,\hdots,d.
\end{align*}
A canonical test with \emph{targeted} asymptotic size~$\alpha\in(0,1)$ of~$H_0$ is
\begin{align*}
\varphi_n=\mathds{1}\del[2]{\max_{1\leq j\leq d}\bm{S}_{nj}> c_{d}(\alpha)},
\end{align*}
where~$c_{d}(\alpha)$ is the sequence of critical values from~\eqref{eq:critvalmaxtest}, i.e.,~they are based on Gaussian critical values.\footnote{In practice the covariance matrix of the~$\bm{X}_i$ is of course unknown and not necessarily equal to~$\mathbf{I}_d$, which the~$c_d(\alpha)$ are based on. However, the point here is to show that even if one \emph{knows} that the covariance matrix is~$\mathbf{I}_d$, the asymptotic size of~$\varphi_n$ is one for~$d$ exceeding the threshold for phase transition in the limiting GAE.} If there exists an~$\varepsilon\in(0,\infty)$ such that~$d/n^{m/2-1-\varepsilon}\to 0$, it indeed follows from Theorem~\ref{thm:cherno} that
\begin{align*}
\lim_{n\to\infty}\sup_{P\in \mathsf{P}(m,c,C)}P\del[2]{\max_{1\leq j\leq d}\bm{S}_{nj}> c_{d}(\alpha)}
=
\alpha;
\end{align*}
that is, the asymptotic size of~$\varphi_n$ over~$\mathsf{P}(m,c,C)$ is~$\alpha$ as desired.
However, since the distributions used in Theorem~\ref{thm:LB} satisfy~$H_0$, it follows from~\eqref{eq:LB1} that for $c \leq 1$ and $C$ sufficiently large there exists a~$P\in\mathsf{P}(m,c,C)$ such that as soon as~$d/n^{m/2-1+\varepsilon}\not\to 0$ for some~$\varepsilon\in(0,\infty)$, we have
\begin{align}\label{eq:sizeone}
\limsup_{n\to\infty}P\del[2]{\max_{1\leq j\leq d}\bm{S}_{nj}> c_{d}(\alpha)}
=
1;
\end{align}
that is, the asymptotic size of~$\varphi_n$ jumps to one once~$d$ exceeds the phase transition threshold.
Thus,~\eqref{eq:LB1} is important as it shows that Gaussian approximations of the cdf of $\max_{1\leq j\leq d}\bm{S}_{nj}$ by the one of~$\max_{1\leq j\leq d}\bm{Z}_{j}$ break down \emph{not} at statistically irrelevant regions but precisely
at the quantiles~$c_d(\alpha)$ of the latter, which are used as critical values for testing. Had the approximations broken down at sequences for which~\eqref{eq:critvalmaxtest} would converge to zero or one (as in the construction of~\cite{zhangwu2017}), this would be of less importance for testing. Similarly, it is alarming that the right-hand side of~\eqref{eq:LB1} is not merely positive but equal to~$1-\alpha$, implying an asymptotic size of one rather than ``only'' something slightly exceeding~$\alpha$.
\begin{remark}\label{rem:suptest}
For any~$\bm{x}\in\mathbb{R}^d$ let~$||\bm{x}||_\infty=\max_{1\leq j\leq d}|\bm{x}_j|$. Then, with~$c_d'(\alpha)$ satisfying
\begin{align*}
\mathbb{P}\del[2]{||\bm{Z}||_\infty> c'_{d}(\alpha)}\to\alpha\qquad\text{as }d\to\infty,
\end{align*}
one can actually show (slightly adapting the proof of Theorem~\ref{thm:LB}) that \eqref{eq:ratecondtion} also implies that
\begin{align*}
\limsup_{n\to\infty} \sbr[3]{\mathbb{P}\del[2]{||\bm{S}_{n}||_\infty> c'_{d}(\alpha)}-\mathbb{P}\del[2]{||\bm{Z}||_\infty > c'_{d}(\alpha)}}=1-\alpha.
\end{align*}
Hence an identical observation to the one above holds for tests based on~$\max_{1\leq j\leq d}\envert[0]{\bm{S}_{nj}}$.
\end{remark}