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.
39,155 characters · 8 sections · 72 citation commands
Superconsistency of Tests in High Dimensions
\and
}
A major challenge in the current “big-data era” is to extract signals from huge databases. Often, an applied researcher proceeds in a two-step fashion: First, in order to decide whether there is any signal in the data at all, one performs an aggregate test of the global null hypothesis of no signal. This global null hypothesis is typically formulated as the high-dimensional target parameter being the zero vector. Second, if the global null hypothesis was rejected by the test, further analysis is undertaken to uncover the precise nature of the signal. Much research has been directed to studying properties of such a sequential rejection principle, cf. romano2005exact, yekutieli2008hierarchical, rosenbaum2008testing, meinshausen2008hierarchical, goeman2010sequential, heller2, bogomolov2020hypotheses and references therein.
Using a powerful test for the global null hypothesis in the first step of such a hierarchical multi-step procedure is of course crucial, and the development of tests for this hypothesis has therefore attracted much research in its own right. A typical choice, employed in, e.g., heller, is to use a test based on the Euclidean norm of the estimator. This also leads to the likelihood ratio (LR) test in the Gaussian sequence model they considered, which is also the framework in the present article. Although the LR test is a natural choice, one may ask: Do tests for the global null exist that are consistent against substantially more alternatives than the LR test? This question is practically relevant, because one can choose from a large menu of well-established tests, yet precisely which one to use is not obvious: For example, one could use tests based on other norms than the Euclidean one, a natural class of tests being based on $p$-norms, cf. the classic monograph of ingster. One could also use a test based on combining different $p$-norms as suggested by the power enhancement principle of fan2015 and in kp2. The possibility of increasing power by combining tests has recently been applied in many types of high-dimensional testing problems, cf. xu2016adaptive, yang2017weighted, yu2020fisher, he2021asymptotically, yu2021power [testing high-dimensional means and covariance matrices]; zhang2021adaptive [change point detection]; jammalamadaka2020sobolev [tests for uniformity on the sphere]; feng2020max [tests for cross-sectional independence in high-dimensional panel data models]. Another test that has gained popularity in recent years is the Higher Criticism. This test dates back to tukey1976t13 and its strong power properties against deviations from the global null were first exhibited by donoho and have led to much subsequent research, cf. donoho2009feature, hall2010innovated, tony2011optimal, arias2011global, barnett2014analytical, li2015higher, arias2019detection and porter2020beyond. Alternatively, one could use tests based on combining p-values for coordinate-wise zero restrictions. Important early work includes fisher1934statistical, tippett1931methods, pearson1933method, stouffer1949american and simes1986improved. For a review of the classic literature see cousins2007annotated, more recent contributions are owen09, duan2020interactive and vovk2020combining, vovk2020values. It is crucial to highlight here that many of the above mentioned tests are consistent against strictly more alternatives than the LR test, i.e., they dominate the LR test in terms of their consistency properties; indeed, this is the main motivation of the power enhancement principle. Hence, the question of interest in the present article is not whether one can do better than the LR test at all, but whether one can do substantially better.
We consider the question raised in the previous paragraph from a high-dimensional perspective. In the Gaussian sequence model, we investigate whether aggregate tests can be obtained that are consistent against substantially more alternatives than the likelihood ratio test. We show that relative to a uniform prior on the parameter space this is impossible: essentially, we prove that for any given test the set of alternatives against which it is consistent, but the LR test is not, has vanishing relative Lebesgue measure. Hence, no test for the global null hypothesis can substantially improve on the LR test. From a technical perspective, our proofs are based on results by ss concerning the asymptotic volume of intersections of $p$-norm balls and on the concentration phenomenon for Lipschitz continuous functions on spheres as exposited in braz or vershynin_2018.
Our finding is reminiscent of lecam1953, who showed (in finite-dimensional settings) that the set of possible superefficiency points of an estimator relative to the maximum likelihood estimator cannot be larger than a Lebesgue null set; cf. also vanderVaart1997. Note that our result does not imply that one should always use the LR test and not think carefully about the choice of test in high-dimensional testing problems. If, for example, one is interested in particular types of deviations from the null, e.g., sparse ones, there may be good reasons to use a test based on the supremum norm or the Higher Criticism. Furthermore, albeit very natural, the magnitude of the consistency set is merely one of many properties that can be used to compare tests. For example, tests are also frequently compared in terms of, e.g., their minimax detection properties or their local power against deviations from the null of a specific type. Nevertheless, in analogy to lecam1953, regardless of how clever an alternative test is designed, the amount of alternatives against which one achieves an improvement as compared to the LR test cannot be substantial in terms of relative volume. This also supports basing a combination procedure, such as the power enhancement principle by fan2015, on the Euclidean norm.
We consider the Gaussian sequence model
where $y_{1,d}, \hdots, y_{d,d}$ are the observations, the parameters $\theta_{i,d} \in \mathbb{R}$ are unknown, and where the unobserved terms $\varepsilon_i$ are independent and standard normal. Writing $\bm{y}_d = (y_{1,d}, \hdots y_{d,d})'$, $\bm{\varepsilon}_d = (\varepsilon_1, \hdots, \varepsilon_d)'$, and $\bm{\theta}_d = (\theta_{1,d}, \hdots, \theta_{d,d})' \in \mathbb{R}^d$, one can equivalently state the model in (ref) as $\bm{y}_d=\bm{\theta}_d+\bm{\varepsilon}_d$. We observe a single realization of a $d$-dimensional Gaussian vector $\bm{y}_d$ with mean $\bm{\theta}_d$ and identity covariance matrix for each $d\in\mathbb{N}$. In this sense the “sample size” is one for each $d$ (but cf. Remark (ref) below). The asymptotic analysis in the Gaussian sequence model then relies on $d\to\infty$. This is a high-dimensional regime in the sense that the number of parameters, $d$, tends to infinity. In the model (ref), we are interested in the testing problem
where $\bm{0}_d$ denotes the origin in $\mathbb{R}^d$. The null hypothesis $H_{0, d}$ is typically referred to as the “global null” of no effect.
For a given $d \in \mathbb{N}$, a (possibly randomized) test $\varphi_d$, say, for (ref) is a (measurable) function from the sample space $\mathbb{R}^d$ to the closed unit interval. In the asymptotic framework we consider, we are interested in properties of sequences of tests $\{\varphi_d\}$, where $\varphi_d$ is a test for (ref) for every $d \in \mathbb{N}$. To lighten the notation, we shall write $\varphi_d$ instead of $\{\varphi_d\}$ whenever there is no risk of confusion. We are particularly interested in the consistency properties of sequences of tests. As usual, we say that a sequence of tests $\varphi_d$ is consistent against the array of parameters $\bm{\vartheta} = \{\bm{\theta}_d : d \in \mathbb{N}\}$, where $\bm{\theta}_d \in \mathbb{R}^d$ for every $d \in \mathbb{N}$, if and only if (as $d \to \infty$)
To every sequence of tests $\varphi_d$ we associate its consistency set $\mathscr{C}(\varphi_d)$, say. The consistency set $\mathscr{C}(\varphi_d)$ is the set of all arrays of parameters $\bm{\vartheta}$ the sequence of tests $\varphi_d$ is consistent against. By definition $$\mathscr{C}(\varphi_d) \subseteq \bigtimes_{d = 1}^{\infty} \mathbb{R}^d =: \bm{\Theta},$$ the latter denoting the set of all possible arrays of parameters.
Recall that a sequence of tests $\varphi_d$ is said to have asymptotic size $\alpha \in [0, 1]$ if
In this article, following the Neyman-Pearson paradigm, we focus on the case where $\alpha \in (0, 1)$, which we shall implicitly assume in the discussions throughout unless mentioned otherwise.
It is well-known that the LR test for (ref) rejects if the Euclidean norm $\|\cdot\|_2$ of the observation vector $\bm{y}_d$ exceeds a critical value $\kappa_{d,2}$ chosen to satisfy the given size constraints. That is, the LR test is given by $\mathds{1}\{\|\cdot\|_2 \geq \kappa_{d,2}\}$. For notational simplicity, we abbreviate the sequence of tests $\{\mathds{1}\{\|\cdot\|_2 \geq \kappa_{d,2}\} \}$ by $\{2, \kappa_{d,2}\}$ and thus write $\mathscr{C}(\{2, \kappa_{d,2}\})$ for its consistency set. The following result is contained in ingster, cf. also Theorem 3.1 in kp2 for extensions.
Theorem (ref) shows that the consistency set of the LR test is precisely characterized by the asymptotic behavior of the Euclidean norms of the array of alternatives under consideration. That the consistency set of the LR test can be completely characterized in terms of the norm its test statistic is based on seems natural, but is quite specific to the LR test, see Theorem 3.1 and the ensuing discussion in kp2.
Although the LR test is a canonical choice of a test for the testing problem (ref), there are many other reasonable tests available. For example, classic results by birnbaum1955 and stein1956 show that any test with convex acceptance region (i.e., the complement of its rejection region) is admissible. anderson1955integral's (anderson1955integral) theorem implies that if the acceptance region is furthermore symmetric around the origin then the test is also unbiased. Thus, any convex symmetric (around the origin) set delivers an admissible unbiased test, which is hence reasonable from a non-asymptotic point of view.
One class of tests that is intimately related to the LR tests consists of tests based on other $p$-norms than the Euclidean one. For $\bm{x} = (x_1, \hdots, x_d)' \in \mathbb{R}^d$ and $p \in (0, \infty]$, define the $p$-norm as usual via\footnote{Strictly speaking, $||\cdot||_p$ defines a norm on $\mathbb{R}^d$ only for $p\in[1,\infty]$ and a quasi-norm for $p \in (0, 1)$.}
In analogy to the LR test, $p$-norm based tests reject if the $p$-norm of the observation vector exceeds a critical value $\kappa_{d,p}$. Special cases, which have an established tradition in high-dimensional inference, are the $1$- and the supremum norm. We shall denote the sequence of tests $\{\mathds{1}\{\|\cdot \|_p \geq \kappa_{d,p}\}\}$ by $\{p, \kappa_{d,p}\}$. Clearly, $p$-norm based tests are unbiased and admissible for $p\in[1,\infty]$ as a consequence of the discussion in the first paragraph of this section.
Concerning the consistency sets $\mathscr{C}(\{p, \kappa_{d,p}\})$ of general $p$-norm based tests, it is a somewhat surprising fact that
see kp2 for formal statements.\footnote{Recall that throughout the present article we implicitly impose the condition that all tests have asymptotic size in $(0, 1)$ if not otherwise mentioned.} From (i) it follows that any $p$-norm based test with $p \in (2, \infty)$ has a strictly larger consistency set than the LR test. We stress that this asymptotic strict domination of the LR test in terms of consistency sets is not in contradiction to its admissibility for each $d\in\mathbb{N}$.
Other tests that strictly dominate the LR test can be obtained, e.g., through combination procedures that enhance the LR test with a sequence of tests $\eta_d$ that is sensitive against alternatives of a different “type” than the LR test in the sense that $$\mathscr{C}(\eta_d) \setminus \mathscr{C}(\{2, \kappa_{d,2}\}) \neq \emptyset.$$ To see how this can be achieved, note that the consistency set of the sequence of tests $\psi_d$, say, where $\psi_d$ rejects if the LR test or $\eta_d$ rejects, contains $\mathscr{C}(\{2, \kappa_{d,2}\}) \cup \mathscr{C}(\eta_d)$, and hence dominates the LR test in terms of consistency. Essentially, this is the power enhancement principle of fan2015; see kp1 for related results. Note that if $\eta_d$ has asymptotic size $0$, which is an assumption imposed on $\eta_d$ in the context of the power enhancement principle, nothing is lost in terms of asymptotic size when using $\psi_d$ instead of the LR test, because both sequences of tests then have the same asymptotic size.\footnote{If $\eta_d$ has a positive asymptotic size that is smaller than the asymptotic size targeted in the final combination test, one can work with a LR test with small enough asymptotic size in the combination procedure to obtain a test that dominates the LR test in terms of consistency (recall from Theorem (ref) that the consistency set of the LR test does not depend on the specific value of the asymptotic size).}
To clarify how much can possibly be gained in terms of consistency by using a sequence of tests $\varphi_d$ other than the LR test, we shall consider the corresponding set $$\mathscr{C}(\varphi_d) \setminus \mathscr{C}(\{2, \kappa_{d,2}\}),$$ which we refer to as the superconsistency points of the sequence of tests $\varphi_d$ (relative to the LR test). Note that the set of superconsistency points is defined for any sequence of tests, regardless of whether it dominates the LR test or not (in the sense that its consistency set includes that of the LR test).\footnote{To provide an example, for any $p \in (2,\infty)$ the set of superconsistency points of the $p$-norm based test is fully characterized by Corollary 3.2 in Kock and Preinerstorfer (2021), cf. also their Theorem 3.4 which essentially shows that these superconsistency points are approximately sparse and have at least one large entry.} On a conceptual level, superconsistency points are related to superefficiency points of estimators relative to the maximum likelihood estimator in classic parametric theory.
The central question we consider in this article is how “large” the set of superconsistency points $\mathscr{C}(\varphi_d) \setminus \mathscr{C}(\{2, \kappa_{d,2}\})$ can possibly be for a sequence of tests $\varphi_d$ with asymptotic size in $(0, 1)$. Note that the larger $\mathscr{C}(\varphi_d) \setminus \mathscr{C}(\{2, \kappa_{d,2}\})$ is, the larger is the set of alternatives the sequence of tests $\varphi_d$ is consistent against but the LR test is not consistent against. Although we already know from the examples discussed in Section (ref) that $\mathscr{C}(\varphi_d) \setminus \mathscr{C}(\{2, \kappa_{d,2}\})$ is non-empty for many $\varphi_d$, we here investigate whether one can substantially enlarge the consistency set by using another test than the LR test.
To make the above question amenable to a formal treatment, note that Theorem (ref) implies that for any sequence of LR tests $\{2, \kappa_{d,2}\}$ with asymptotic size $\alpha \in (0, 1)$, the complement of $\mathscr{C}(\{2, \kappa_{d,2}\})$ satisfies
if the sequence $r_d > 0$ is such that $r_d/d^{1/4}$ is bounded and where $\mathbb{B}_2^d(r)$ denotes the Euclidean ball with radius $r$ centered at the origin. That is, the LR test is inconsistent against any element of $\bigtimes_{d = 1}^{\infty} \mathbb{B}_2^d(r_d)$. We now investigate how many inconsistency points of the LR test can be removed from any such benchmark $\bigtimes_{d = 1}^{\infty} \mathbb{B}_2^d(r_d)$ by erasing all superconsistency points of a sequence of tests $\varphi_d$.
Formally, this is to be understood in the following sense: let $\varphi_d$ be a sequence of tests with consistency set $\mathscr{C}(\varphi_d)$ and let $r_d$ be such that $r_d/d^{1/4}$ is bounded. Let $\mathbb{D}_d \subseteq \mathbb{B}_2^d(r_d)$ be such that $$\bigtimes_{d = 1}^{\infty} \mathbb{D}_d \subseteq \mathscr{C}(\varphi_d).$$ Note that all elements of $\bigtimes_{d = 1}^{\infty} \mathbb{D}_d$ are superconsistency points of $\varphi_d$ which are also contained in the benchmark $\bigtimes_{d = 1}^{\infty} \mathbb{B}_2^d(r_d)$ (cf. the illustration in Figure (ref)). Denoting by $\text{vol}_d$ the $d$-dimensional Lebesgue measure, we investigate the asymptotic behavior of the relative volume measure
Obviously, the ratio in (ref) is a number in $[0, 1]$. On the one hand, if this ratio is asymptotically close to $1$, this means that, in terms of relative volume, many elements of the benchmark $\bigtimes_{d = 1}^{\infty} \mathbb{B}_2^d(r_d)$ are superconsistency points of the sequence of tests $\varphi_d$. That is, one can substantially improve upon the LR test by using $\varphi_d$ (or by combining the LR test with $\varphi_d$ through the power enhancement principle). On the other hand, if this ratio is asymptotically close to $0$, this means that in terms of relative volume only few elements of the benchmark are superconsistency points of $\varphi_d$.
We emphasize that using the (normalized) Lebesgue measure to assess the asymptotic magnitude of the set of superconsistency points is one among many possible choices. Other measures would be possible too, but the uniform prior over $\mathbb{B}_2^d(r_d)$ is a natural choice as in many situations there is no clear guidance concerning the type of alternative one wishes to favor.\footnote{Our results remain valid if, instead of measuring the magnitude of $\mathbb{D}_d$ w.r.t. the uniform probability measure on $\mathbb{B}_2^d(r_d)$, one measures its magnitude w.r.t. the uniform probability measure on the Euclidean sphere of radius $r_d$. We will comment on this in Remark (ref), but will focus on the uniform distribution on $\mathbb{B}_2^d(r_d)$ throughout the article.}
Note that the ratio in (ref) depends on two ingredients:
Therefore, one could suspect that the asymptotic behavior of (ref) depends in a complicated way on the interplay between these two components. Nevertheless, it turns out that the asymptotic behavior of (ref) has a simple description that does not depend on any of the two ingredients just described. In fact, we shall prove in Section (ref) that the limit of the sequence is $0$ for all sequences of tests $\varphi_d$. Hence, it is impossible to improve on the LR test in terms of the magnitude of its consistency set apart from a set of superconsistency points that is negligible in a relative volume sense.
In the following Section (ref), we shall first establish this result for $\varphi_d$ a sequence of $p$-norm based tests with $p \in (2, \infty)$. Note that all these tests have a strictly larger consistency set than the LR test as discussed in Section (ref). A general result, the proof of which is a bit more involved, will be presented in Section (ref).
We now consider the asymptotic behavior of the sequence (ref) for the special case where $\varphi_d$ is a sequence of $p$-norm based tests with $p \in (2, \infty)$ being fixed. For this class of tests, we can exploit the characterization of their consistency sets provided in Theorem 3.1 and Corollary 3.2 of kp2, together with results from asymptotic geometry developed in ss based on earlier results in sz. These ingredients lead to a direct proof of the limit of the sequence in (ref) being $0$.
Hence, even though $\mathscr{C}(\{p, \kappa_{d, p}\})$ contains the consistency set of the LR test as a strict subset for every $p \in (2, \infty)$ as discussed in Section (ref), the subset of those alternatives in each benchmark $\bigtimes_{d = 1}^{\infty} \mathbb{B}_2^d(r_d)$ for which the test $\{p, \kappa_{d, p}\}$ provides an improvement over the LR test is “negligible” in (relative) volume. That this result is not specific to $p$-norm based tests, but extends to all tests will be shown next.
The proof of Theorem (ref) builds heavily on the particular structure of the consistency set of $p$-norm based tests. We shall now establish that no test can improve substantially on the LR test. In the absence of any structure on the tests, one can no longer exploit specific properties of the consistency set stemming from the test being based on a $p$-norm. Instead we rely on concentration results for Lipschitz continuous functions on the sphere as exposited in braz or vershynin_2018.
The proof of Theorem (ref) can be found in Appendix (ref). Note that Theorem (ref) not only shows that the magnitude of superconsistency points of tests is asymptotically negligible for any test --- it also shows that the measure of these points converges to zero quickly in the dimension $d$.
So far, all our results concerned consistency properties of tests. We were interested in the possible magnitude of the superconsistency points of a sequence of tests relative to the LR test and have seen that the magnitude of such points cannot be substantial. Although we now know that one cannot substantially improve on the LR test in terms of consistency (in the sense of Theorem (ref)), there could in principle exist sequences of tests that have larger power than the LR test on substantial portions of the parameter space (without the power there being close to $1$). A non-asymptotic question one can therefore ask is: how large can such portions of the parameter space be? To answer this question, we introduce some more notation: let $\alpha \in [0, 1]$ and denote for every $r > 0$ by $\beta_{d, \alpha}(r)$ the power of the LR test of size $\alpha$ against alternatives $\bm{\theta} \in \mathbb{R}^d$ such that $\|\bm{\theta}\|_2 = r$ (noting that the power of the LR test coincides for all such parameters as it is rotationally invariant).\footnote{With this notation it is worth noting that the proof of Theorem (ref) shows that $\epsilon$ in that theorem can be chosen as $(1-\limsup_{d \to \infty} \beta_{d, \alpha_d}(r_d))/2,$ where $\alpha_d$ denotes the size of $\psi_d$.} Denote the set of all tests $\psi: \mathbb{R}^d \to [0, 1]$ by $\Psi_{d}$, and define for every $\alpha \in [0, 1]$, $\epsilon > 0$, and $\psi \in \Psi_{d}$ the set $\mathbb{F}_d(\epsilon, \psi)$ as the subset of parameters against which the power of $\psi$ exceeds the power of the LR test of the same size as $\psi$ by more than $\epsilon$, i.e.,
The question is: how large can this set be made by cleverly choosing $\psi$? The following theorem provides a non-asymptotic upper bound on its measure w.r.t. to the uniform distribution $\rho_{d, r}$ on $\mathbb{S}_d^{d-1}(r)$. The upper bound decreases exponentially in $d$.
The proof of Proposition (ref) follows from the following ingredients: (i) L\'evy's concentration theorem, i.e., the fact that any Lipschitz continuous function on the sphere $\mathbb{S}^{d-1}(r)$ concentrates around its average w.r.t. $\rho_{d, r}$, see, e.g., Theorem 1.7.9 of braz; (ii) the observation that power functions of tests in the model considered are Lipschitz continuous in the parameter vector; and (iii) the fact that the LR test maximizes (among all tests) the average power w.r.t. $\rho_{d, r}$ against alternatives on the sphere $\mathbb{S}^{d-1}(r)$. The proof of Theorem (ref) is based on the inequality in Proposition (ref).
In high-dimensional testing problems, the choice of a test implicitly or explicitly determines the type of alternative it prioritizes. In the Gaussian sequence model, the LR test is based on the Euclidean norm. Many tests exist that are consistent against alternatives the LR test isn't consistent against (or are even consistent against strictly more alternatives than the LR test), i.e., they possess what we refer to as superconsistency points. We have shown that for any test, the corresponding set of superconsistency points is negligible in an asymptotic sense. This can be interpreted as a high-dimensional testing analogue of Le Cam's famous result that the set of superefficiency points relative to the maximum likelihood estimator is at most a Lebesgue null set, cf. lecam1953. In analogy to that classic finding, our result does not suggest that one should always use the LR test. But it shows that there exists no test for which one can expect substantial improvements.