A remark on moment-dependent phase transitions in high-dimensional Gaussian approximations

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

15,717 characters · 3 sections · 15 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

tabular[tabular omitted — 170 chars of source]

\and

tabular[tabular omitted — 174 chars of source]

}

abstractIn 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.

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 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)

align[align omitted — 136 chars of source]

have been established over various classes of subsets $\mathcal{A}$ of $\mathbb{R}^d$ with particular emphasis on hyperrectangles and closely related sets; chernozhukov2017central, deng2020beyond, lopes2020bootstrapping, kuchibhotla2020high, das2021central, koike2021notes, kuchibhotla2021high, lopes2022central, chernozhuokov2022improved, chernozhukov2023nearly. We refer to the review in chernozhukov2023high for further references. Results for $\mathcal{A}$ the class of convex sets can be found in nagaev2006estimate, senatov1981uniform, gotze1991rate, bentkus2003dependence, bentkus2005lyapunov, fang2020large. Recently, the class of Euclidean balls has been studied in 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 zhangwu2017 constructed i.i.d. $\bm{X}_{ij}$ possessing exactly $m\in(2,\infty)$ moments such that

align[align omitted — 202 chars of source]

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

align*[align* omitted — 67 chars of source]

On the other hand, it known (and a simple consequence of, e.g., Theorem 2 in chernozhukov2023high as detailed in Theorem (ref) 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

align*[align* omitted — 130 chars of source]

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:

enumerate• (Very) high-dimensional central limit theorems are only possible for distributions with light tails. It is necessary to impose that 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 chernozhukov2023high) or ii) consider families of sets strictly smaller than $\mathcal{H}$. • 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$. • 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 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$.

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).} 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

align[align omitted — 183 chars of source]

but not the stronger property

align[align omitted — 224 chars of source]

typically focused on in the literature. In particular, even though there exist distributions with $m$ moments such that (ref) fails to be true when $\limsup_{n\to\infty}d/n^{m/2-1+\varepsilon}>0$ by the mentioned result in zhangwu2017, the statistically important approximation in (ref) 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 zhangwu2017 satisfy that

align*[align* omitted — 178 chars of source]

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 (ref) by 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.

The phase transition at Gaussian critical values

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

align[align omitted — 139 chars of source]

The distributions $P_m$ on $\mathbb{R}$ used in the following theorem are given in explicit form in (ref) in Section (ref). Recall that $\bm{S}_n=n^{-1/2}\sum_{i=1}^n\bm{X}_i$.

theoremLet $m\in(2,\infty)$, $\alpha\in(0,1)$, and $c_d(\alpha)$ be a sequence that satisfies (ref). 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} \limsup_{n\to\infty}\frac{d}{n^{m/2-1+\varepsilon}}>0, \end{align} then \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}

The consequences of (ref) relative to (ref) and $\rho_n(\mathcal{H})\to 0$ for hypothesis testing are discussed further in Section (ref) 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 chernozhukov2023high.

theoremLet $m\in[4,\infty)$. If there exists an $\varepsilon\in(0,\infty)$ such that \begin{align} \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*}

Together Theorems (ref) and (ref) 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.

Consequences for high-dimensional hypothesis testing

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

align*[align* omitted — 109 chars of source]

A canonical test with targeted asymptotic size $\alpha\in(0,1)$ of $H_0$ is

align*[align* omitted — 91 chars of source]

where $c_{d}(\alpha)$ is the sequence of critical values from (ref), 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 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) that

align*[align* omitted — 129 chars of source]

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) satisfy $H_0$, it follows from (ref) 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

align[align omitted — 113 chars of source]

that is, the asymptotic size of $\varphi_n$ jumps to one once $d$ exceeds the phase transition threshold.

Thus, (ref) 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 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 (ref) would converge to zero or one (as in the construction of zhangwu2017), this would be of less importance for testing. Similarly, it is alarming that the right-hand side of (ref) is not merely positive but equal to $1-\alpha$, implying an asymptotic size of one rather than “only” something slightly exceeding $\alpha$.

remarkFor 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\qquadas d\to\infty, \end{align*} one can actually show (slightly adapting the proof of Theorem (ref)) that (ref) 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}}$.