Introduction
Modern classification problems often involve high-dimensional representations, where the number of measured features p p p is large but the discriminating information is concentrated in a small subset of coordinates. This sparse-useful-feature structure arises naturally in genomics, text, tabular data, and learned representations, and it motivates feature-screening methods that identify informative coordinates before classification. Such identification is also known to be crucial when data are scarce or the noise level is high [18 , 13 , 15 , 3 ] . Understanding when classification is possible in this rare-and-weak useful-feature regime is important for assessing sample complexity, the value of feature engineering, and the role of dimensionality reduction or feature screening.
40th Conference on Neural Information Processing Systems (NeurIPS 2026).
In the binary case, rare-and-weak useful-feature models provide a sharp theoretical framework for understanding this phenomenon [11 ] . They characterize regimes in which classification is possible despite individual signals being weak [19 , 13 , 27 ] . However, multiclass classification introduces qualitatively new issues. A feature may be useful not because it separates one class from another, but because it induces a pattern of variation across many classes [6 , 1 , 32 , 20 ] . This raises a basic question: how does the number of classes affect the boundary between possible and impossible classification?
We address this question through a Gaussian multiclass Rare-and-Weak Useful Feature model in which class centroids are largely identical, except in a small fraction of the coordinates which individually exhibit statistically detectable diversity signal across classes. This model is designed to isolate the effect of the number of classes on classification in high-dimensions. Our main contribution is a phase-transition analysis for this model that separates classification with accuracy tending to one from classification with accuracy tending to chance level. When the number of classes is fixed, the classification boundary agrees with the binary rare/weak theory [11 , 13 , 19 , 12 ] . In contrast, when the number of classes grows logarithmically with the number of features, a new phase transition emerges, capturing the additional difficulty introduced by many classes.
The achievability side of the theory is established by a simple diversity-based screening procedure that computes a diversity score for each feature individually, then applies the higher-criticism threshold for selecting features [11 ] . We call this screening procedure Diversity Pursuit Higher Criticism Thresholding (DP-HCT). Under the rare-and-weak useful feature model, DP-HCT followed by a simple centroid-similarity classifier asymptotically achieves perfect classification throughout the region where nontrivial classification is possible. Complementing this theoretical characterization of the classification boundary, experiments on several real-world multiclass benchmarks show performance gains from DP-HCT.
Contributions
A fundamental limit for multiclass classification with rare and weak useful features. We introduce a multiclass Rare-and-Weak Useful Feature model in which the number of classes grows logarithmically with the number of features p p p . The model is governed by three calibration parameters: β \beta β , which controls feature rarity; s s s , which controls the growth rate of the number of classes; and r r r , which controls signal strength. Our main result establishes a sharp phase transition as p → ∞ p \to\infty p → ∞ : there exists a function ξ ⋆ ( β , s ) \xi^{\star}(\beta,s) ξ ⋆ ( β , s ) such that if r < ξ ⋆ ( β , s ) r < \xi^{\star}(\beta,s) r < ξ ⋆ ( β , s ) , no classifier achieves accuracy beyond chance asymptotically, whereas if r > ξ ⋆ ( β , s ) r > \xi^{\star}(\beta,s) r > ξ ⋆ ( β , s ) , classification with accuracy tending to one is possible. The function ξ ⋆ ( β , s ) \xi^{\star}(\beta,s) ξ ⋆ ( β , s ) is illustrated in Figure 1 .
Figure 1. Multiclass classification boundary ξ ⋆ ( β , s ) \xi^{\star}(\beta,s) ξ ⋆ ( β , s ) of (20) . Left: boundary as a function of the feature-rarity exponent β \beta β , for several values of the class-growth parameter s s s . Right: boundary as a function of s s s , for several values of β \beta β . Dashed lines represent the large s s s approximation 2 s r \sqrt{2sr} 2 sr . The case s → 0 s \to0 s → 0 corresponds to the binary Rare-and-Weak Useful Feature boundary [11 , 19 ] . Larger s s s shifts the boundary upward, indicating the larger signal strength r r r required for nontrivial classification.
Constructive achievability via Diversity Pursuit Higher Criticism Thresholding. We prove that this fundamental limit is attained by a simple diversity-based screening procedure. Specifically, when r > ξ ⋆ ( β , s ) r > \xi^\star(\beta,s) r > ξ ⋆ ( β , s ) , applying higher-criticism thresholding to ANOVA p p p -values, followed by a centroid-similarity classifier on the selected features, achieves classification accuracy tending to one.
Numerical validation and empirical evidence on multiclass benchmarks. We run large-scale Monte Carlo experiments across the model’s defining parameters. The simulations show that HC thresholding, despite not using the model parameters, closely tracks the oracle threshold and yields empirical accuracy consistent with the predicted phase-transition curve ξ ⋆ ( β , s ) \xi^\star(\beta,s) ξ ⋆ ( β , s ) . We also compare classification post-DP-HCT to alternative screening rules, including Bonferroni and Benjamini–Hochberg FDR [5 ] . Finally, we evaluate classification post-DP-HCT on five real multiclass benchmarks: gene expression (Heart-Circadian, Worm-Bacteria), metabolomics (Blood-Diet, Zebrafish-BPF) and miRNA expression (Biliary-miRNA). Across these datasets, DP-HCT substantially improves the kernel SVM and logistic-regression baselines, providing proof-of-concept evidence for diversity-based HC screening in multiclass problems.
Significance of the contributions compared to previous work. The phase transition expression we derive provides an accurate description of the effect of the number of classes on the possibility of successful classification. By using this expression as a pivot, one can assess the sample complexity of classification problems or the amount of feature engineering needed to achieve successful classification. Similar attempts in related models are provided in Abramovich et al. [ [2 ] , Thrampoulidis et al. [ [32 ] . To the best of our knowledge, our setting is the first to incorporate the number of classes in an asymptotic phase transition analysis.
Classification under a rare-and-weak useful-feature setting has been studied by Donoho and Jin [ [11 , 13 ] , who also proposed using higher criticism for feature screening. The impossibility of classification in such a model was established in Jin [ [19 ] . Our work is best seen as an extension of this result to the multiclass setting with an increasing number of classes. Our phase transition curve accounts for the change in the full useful-feature tail rate caused by the added degrees of freedom, an effect absent from the binary and fixed-class settings. Other rare-and-weak useful-feature settings can be found in Azar and Nadler [ [3 ] , Verzelen and Arias-Castro [ [33 ] and references therein. More closely related to the multiclass setting, the works Jin and Wang [ [20 ] , Jin et al. [ [21 ] , Ma et al. [ [28 ] proposed using higher criticism to identify useful features for clustering. Their setting can also be seen as a diversity-seeking situation among several groups, for which higher criticism has provided promising empirical results. The associated theoretical analysis, however, does not incorporate growth in the number of groups. We believe that ideas from our work can refine the theoretical understanding of clustering as well.
Analysis Overview The contributions combine several techniques. We derive the useful-feature tail exponent directly from the noncentral chi-square moment-generating function, using a Chernoff bound and an exponential tilting adjusted to the increase in the degrees of freedom. This analysis extends the fixed-degree chi-square approximations in Kipnis [ [22 ] , Donoho and Jin [ [10 ] . Concentration of the within-class variance transfers this exponent to the exact ANOVA F-test p p p -values. We distinguish two regimes: C = o ( log p ) C = o(\log p) C = o ( log p ) , including fixed C C C , which recovers the binary boundary; and C − 1 ∼ 2 s log p C - 1 \sim2s \log p C − 1 ∼ 2 s log p with fixed s > 0 s > 0 s > 0 , which yields the growing-class boundary.
When C C C is fixed (or grows as o ( log p ) o(\log p) o ( log p ) ), the analysis recovers the classical Gaussian boundary [10 , 11 ] ; when C ∼ 2 s log p C \sim2s \log p C ∼ 2 s log p , it produces a strictly different boundary. The new boundary represents an increase in the difficulty of classification due to the increased number of classes.
The impossibility region follows from a truncated likelihood-ratio second-moment argument for the joint training and test experiment. Above the boundary, HC attains a polynomially large score, which guarantees polynomially many useful selections and a favorable ratio of squared useful selections to total selections. Uniform threshold bounds transfer these properties to the data-chosen threshold.
Organization Section 2 introduces DP-HCT for feature screening. In Section 3, we specify the multiclass Rare-and-Weak Useful Feature framework. In Section 4, we derive the asymptotic phase transition for successful classification and we show that DP-HCT based on ANOVA and a centroid-similarity classifier achieves the theoretical detectability region. Section 5 reports simulation and real-data results. Additional simulation results and full proofs are provided in the Supplementary Material.
Algorithm 1 DP-HCT: Diversity Pursuit with Higher Criticism Thresholding.
Require: training data { ( X i , Y i ) } i = 1 n \{(X_i,Y_i)\}_{i=1}^{n} {( X i , Y i ) } i = 1 n ; diversity test D D D ;
for j = 1 , … , p j=1,\ldots,p j = 1 , … , p do
compute D j D_j D j on { ( X i , j , Y i ) } i = 1 n \{(X_{i,j},Y_i)\}_{i=1}^{n} {( X i , j , Y i ) } i = 1 n ; obtain p-value π j \pi_j π j .
end for
sort: π ( 1 ) ≤ π ( 2 ) ≤ ⋯ ≤ π ( p ) \pi_{(1)}\leq\pi_{(2)}\leq\cdots\leq\pi_{(p)} π ( 1 ) ≤ π ( 2 ) ≤ ⋯ ≤ π ( p ) .
for j = 1 , … , ⌊ γ 0 p ⌋ j=1,\ldots,\lfloor\gamma_0p\rfloor j = 1 , … , ⌊ γ 0 p ⌋ , set H C p , j ← p ( j / p − π ( j ) ) / ( j / p ) ( 1 − j / p ) \mathrm{HC}_{p,j}\leftarrow\sqrt{p}(j/p-\pi_{(j)})/\sqrt{(j/p)(1-j/p)} HC p , j ← p ( j / p − π ( j ) ) / ( j / p ) ( 1 − j / p ) .
j ⋆ ← arg max 1 ≤ j ≤ ⌊ γ 0 p ⌋ H C p , j j^\star\leftarrow\operatorname{arg\,max}_{1\leq j\leq\lfloor\gamma_0p\rfloor}\mathrm{HC}_{p,j} j ⋆ ← arg max 1 ≤ j ≤ ⌊ γ 0 p ⌋ HC p , j ;
J ^ ← { j ∈ [ p ] : π j ≤ π ( j ⋆ ) } \widehat{J}\leftarrow\{j\in[p]:\pi_j\leq\pi_{(j^\star)}\} J ← { j ∈ [ p ] : π j ≤ π ( j ⋆ ) } . Ensure: selected set J ^ \widehat{J} J
Diversity Pursuit with HC Thresholding
We now introduce the DP-HCT feature-screening procedure. Subsequent sections justify this procedure theoretically and empirically.
Feature screening
We have a training dataset { ( X i , Y i ) } i = 1 n \{(X_i,Y_i)\}_{i=1}^{n} {( X i , Y i ) } i = 1 n with X i ∈ R p X_i\in\mathbb{R}^{p} X i ∈ R p and Y i ∈ [ C ] : = { 1 , … , C } Y_i\in[C]:=\{1,\ldots,C\} Y i ∈ [ C ] := { 1 , … , C } . For j ∈ [ p ] j\in[p] j ∈ [ p ] and c ∈ [ C ] c\in[C] c ∈ [ C ] , let P c , j P_{c,j} P c , j denote the class-conditional marginal distribution of feature j j j . A feature j j j is useless (a.k.a. null ) if
H 0 ( j ) : P 1 , j = P 2 , j = ⋯ = P C , j , (1) H_0^{(j)}: P_{1,j}=P_{2,j}=\cdots=P_{C,j}, \tag*{(1)} H 0 ( j ) : P 1 , j = P 2 , j = ⋯ = P C , j , (1)
and useful otherwise. Our goal is to improve classification performance by removing useless features. We propose the following DP-HCTscreening procedure, which decomposes into three steps.
(i) Per-feature diversity testing. For each j j j , compute a test statistic D j D_j D j of (1) on { ( X i , j , Y i ) } i = 1 n \{(X_{i,j},Y_i)\}_{i=1}^{n} {( X i , j , Y i ) } i = 1 n and convert it to a p-value π j ∈ [ 0 , 1 ] \pi_j\in[0,1] π j ∈ [ 0 , 1 ] .
(ii) Higher Criticism Thresholding. Let π ( 1 ) ≤ ⋯ ≤ π ( p ) \pi_{(1)}\leq\cdots\leq\pi_{(p)} π ( 1 ) ≤ ⋯ ≤ π ( p ) denote the order statistics of { π j } j = 1 p \{\pi_j\}_{j=1}^{p} { π j } j = 1 p . The Higher Criticism Thresholding (HCT) procedure selects a set of indices J ^ ⊆ [ p ] \widehat{J}\subseteq[p] J ⊆ [ p ] whose p-values are below a threshold π ( j ⋆ ) \pi_{(j^\star)} π ( j ⋆ ) , where j ⋆ j^\star j ⋆ is the index that maximizes the Higher Criticism statistic. Specifically, with
H C p , j ≜ p ⋅ j / p − π ( j ) t j ( 1 − t j ) , j = 1 , … , p , \mathrm{HC}_{p,j}\triangleq\sqrt{p}\cdot\frac{j/p-\pi_{(j)}}{\sqrt{t_j(1-t_j)}},\qquad j=1,\ldots,p, HC p , j ≜ p ⋅ t j ( 1 − t j ) j / p − π ( j ) , j = 1 , … , p ,
where t j : = j / p t_j:=j/p t j := j / p . The HC statistic and the HCT are defined as in Donoho and Jin [ [11 , 13 , 12 ] :
H C p : = H C p , j ⋆ , j ⋆ : = arg max 1 ≤ j ≤ ⌊ p γ 0 ⌋ H C p , j , (2) \mathrm{HC}_p:=\mathrm{HC}_{p,j^\star},\qquad j^\star:=\underset{1\leq j\leq\lfloor p\gamma_0\rfloor}{\operatorname{arg\,max}}\ \mathrm{HC}_{p,j}, \tag*{(2)} HC p := HC p , j ⋆ , j ⋆ := 1 ≤ j ≤ ⌊ p γ 0 ⌋ arg max HC p , j , (2)
where γ 0 \gamma_0 γ 0 is a tunable parameter that reflects prior knowledge about the proportion of useful features; we used γ 0 = 1 / 2 \gamma_0=1/2 γ 0 = 1/2 in all evaluations.
(iii) Selection. The higher criticism-selected set is
J ^ : = { j ∈ [ p ] : π j ≤ π ( j ⋆ ) } . \widehat{J}:=\{j\in[p]:\pi_j\leq\pi_{(j^\star)}\}. J := { j ∈ [ p ] : π j ≤ π ( j ⋆ ) } .
The selection procedure (i)-(iii) is summarized in Algorithm 1.
Given the selected set J ^ \widehat{J} J , we define the feature-screened data as
X i [ J ^ ] : = ( X i , j ) j ∈ J ^ ∈ R ∣ J ^ ∣ . (3) X_i[\widehat{J}]:=(X_{i,j})_{j\in\widehat{J}}\in\mathbb{R}^{|\widehat{J}|}. \tag*{(3)} X i [ J ] := ( X i , j ) j ∈ J ∈ R ∣ J ∣ . (3)
We train a multiclass classifier h ^ \widehat{h} h on { ( X i [ J ^ ] , Y i ) } i = 1 n \{(X_i[\widehat{J}],Y_i)\}_{i=1}^{n} {( X i [ J ] , Y i ) } i = 1 n . For a test point X n + 1 X_{n+1} X n + 1 , predict Y ^ n + 1 : = h ^ ( X n + 1 [ J ^ ] ) \widehat{Y}_{n+1}:=\widehat{h}(X_{n+1}[\widehat{J}]) Y n + 1 := h ( X n + 1 [ J ]) .
Diversity Statistics
Any per-feature test of (1) that produces a null-calibrated p-value fits the template, and different tests can even be applied to different features. Two canonical tests that we explain in detail and apply in practice are the classical Analysis of Variance (ANOVA) F-test and the Kruskal–Wallis test [24 ] . Aside from these tests, other procedures can be used as diversity statistics, such as the Friedman test and permutation-based tests [25 Ch. 7] . Post-hoc tests such as Tukey’s method [25 Ch. 9] may be useful in extensions of the framework to hierarchical features.
ANOVA F-test. Let n c : = ∣ { i : Y i = c } ∣ n_c := |\{i : Y_i = c\}| n c := ∣ { i : Y i = c } ∣ be the number of observations in class c c c and assume n c ≥ 2 n_c \ge2 n c ≥ 2 . At feature j j j , denote the class sample mean by
μ ^ c , j : = 1 n c ∑ i : Y i = c X i , j , c = 1 , … , C , (4) \hat{\mu}_{c,j} := \frac{1}{n_c} \sum_{i : Y_i = c} X_{i,j}, \qquad c = 1,\ldots,C, \tag*{(4)} μ ^ c , j := n c 1 i : Y i = c ∑ X i , j , c = 1 , … , C , (4)
Define the within- and between-class sums of squares as
SS b e t w e e n ( j ) = ∑ c = 1 C n c ( μ ^ c , j − n − 1 ∑ a = 1 C n a μ ^ a , j ) 2 , SS w i t h i n ( j ) = ∑ c = 1 C ∑ i : Y i = c ( X i , j − μ ^ c , j ) 2 , (5) \operatorname{SS}_{\mathrm{between}}(j) = \sum_{c=1}^{C} n_c \left(\hat{\mu}_{c,j} - n^{-1}\sum_{a=1}^{C} n_a\hat{\mu}_{a,j}\right)^2,\qquad\operatorname{SS}_{\mathrm{within}}(j) = \sum_{c=1}^{C}\sum_{i : Y_i=c}\left(X_{i,j}-\hat{\mu}_{c,j}\right)^2, \tag*{(5)} SS between ( j ) = c = 1 ∑ C n c ( μ ^ c , j − n − 1 a = 1 ∑ C n a μ ^ a , j ) 2 , SS within ( j ) = c = 1 ∑ C i : Y i = c ∑ ( X i , j − μ ^ c , j ) 2 , (5)
and
f j : = SS b e t w e e n ( j ) / ( C − 1 ) SS w i t h i n ( j ) / ( n − C ) . (6) f_j := \frac{\operatorname{SS}_{\mathrm{between}}(j)/(C-1)}{\operatorname{SS}_{\mathrm{within}}(j)/(n-C)}. \tag*{(6)} f j := SS within ( j ) / ( n − C ) SS between ( j ) / ( C − 1 ) . (6)
With F C − 1 , n − C F_{C-1,n-C} F C − 1 , n − C denoting the F F F distribution with ( C − 1 , n − C ) (C-1,n-C) ( C − 1 , n − C ) degrees of freedom, p-values are provided by
π j : = P { F C − 1 , n − C ≥ f j } , j = 1 , … , p . (7) \pi_j := \mathbb{P}\{F_{C-1,n-C} \ge f_j\}, \qquad j=1,\ldots,p. \tag*{(7)} π j := P { F C − 1 , n − C ≥ f j } , j = 1 , … , p . (7)
This test is appropriate under H 0 ( j ) H_0^{(j)} H 0 ( j ) of (1) when the class-conditional marginals are Gaussian, i.e., P c , j = N ( μ c ( j ) , σ 2 ) P_{c,j} = \mathcal{N}(\mu_c^{(j)},\sigma^2) P c , j = N ( μ c ( j ) , σ 2 ) , with an unknown common variance σ 2 \sigma^2 σ 2 .
Kruskal–Wallis Test. This test is often seen as the rank-based analogue of the ANOVA F-test. Rank-based diversity is invariant to monotone transformations and requires no parametric assumption. Therefore, the Kruskal–Wallis (KW) test is particularly useful when class-conditional marginals are heavy-tailed, skewed, or contaminated [25 Ch. 7] .
Let R i , j R_{i,j} R i , j be the rank of X i , j X_{i,j} X i , j in { X 1 , j , … , X n , j } \{X_{1,j},\ldots,X_{n,j}\} { X 1 , j , … , X n , j } and R ˉ c , j : = n c − 1 ∑ i : Y i = c R i , j \bar{R}_{c,j} := n_c^{-1}\sum_{i:Y_i=c}R_{i,j} R ˉ c , j := n c − 1 ∑ i : Y i = c R i , j be the class mean rank at feature j j j . The KW statistic of the j j j -th feature is defined as
K W j : = 12 n ( n + 1 ) ∑ c = 1 C n c ( R ˉ c , j − n + 1 2 ) 2 . (8) \mathrm{KW}_j := \frac{12}{n(n+1)}\sum_{c=1}^{C} n_c\left(\bar{R}_{c,j}-\frac{n+1}{2}\right)^2. \tag*{(8)} KW j := n ( n + 1 ) 12 c = 1 ∑ C n c ( R ˉ c , j − 2 n + 1 ) 2 . (8)
As n → ∞ n \to\infty n → ∞ under H 0 ( j ) H_0^{(j)} H 0 ( j ) with continuous marginals, K W j \mathrm{KW}_j KW j converges to a χ C − 1 2 \chi^2_{C-1} χ C − 1 2 distribution. Thus, (asymptotic) p-values are provided by
π j : = P { χ C − 1 2 ≥ K W j } , j = 1 , … , p . (9) \pi_j := \mathbb{P}\{\chi^2_{C-1} \ge\mathrm{KW}_j\}, \qquad j=1,\ldots,p. \tag*{(9)} π j := P { χ C − 1 2 ≥ KW j } , j = 1 , … , p . (9)
Multiclass Rare-and-Weak Useful Feature Model
Overview
We consider a model with C C C classes, where only a vanishing fraction of features are useful for inter-class discrimination. We call a feature useful if it promotes discrimination among classes in a way that can be detected by a per-feature diversity test, such as (7) or (9) . We introduce a single parameter τ \tau τ that controls the strength of the useful class-mean contrasts. To enforce rarity, we suppose that each feature belongs to the set of useful features J ⊆ [ p ] \mathcal{J} \subseteq[p] J ⊆ [ p ] with probability ϵ \epsilon ϵ , for some small number ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) . The resulting Multiclass Rare-and-Weak Useful Feature model is denoted by MCRW( p , C , ϵ , τ ) (p,C,\epsilon,\tau) ( p , C , ϵ , τ ) .
Multiclass Gaussian data
Suppose that, conditional on Y i = c Y_i=c Y i = c ,
X i ∣ Y i = c ∼ N ( μ c , σ 2 I p ) , μ c = ( μ c ( 1 ) , … , μ c ( p ) ) ∈ R p . (10) X_i\mid Y_i=c \sim\mathcal{N}(\mu_c,\sigma^2 I_p),\qquad\mu_c=(\mu_c^{(1)},\ldots,\mu_c^{(p)})\in\mathbb{R}^p. \tag*{(10)} X i ∣ Y i = c ∼ N ( μ c , σ 2 I p ) , μ c = ( μ c ( 1 ) , … , μ c ( p ) ) ∈ R p . (10)
Here μ c \mu_c μ c is the class-c c c centroid and σ 2 > 0 \sigma^2>0 σ 2 > 0 is a shared noise-scaling parameter. For simplicity, we assume that n c = n / C n_c=n/C n c = n / C is an integer, and that the design is balanced with n c n_c n c observations per class. Unbalanced designs are interesting in some contexts [23 ] , but we leave their analysis as future work.
Rare useful features
Inter-class diversity in the generation process (10) is encoded by the class means μ 1 , … , μ C \mu_1,\ldots,\mu_C μ 1 , … , μ C . Let J ⊂ [ p ] \mathcal{J}\subset[p] J ⊂ [ p ] denote the coordinates of features that promote inter-class separation in the following sense. For j ∉ J j\notin\mathcal{J} j ∈ / J , all class means have the same j j j -th coordinate value, whereas for j ∈ J j\in\mathcal{J} j ∈ J , some class means may have j j j -th coordinates that differ from the others. The set of useful features J \mathcal{J} J is assumed to be random, with each coordinate belonging to J \mathcal{J} J with probability ϵ \epsilon ϵ independently of the others.
Deterministic constructions of J \mathcal{J} J that directly control ∣ J ∣ |\mathcal{J}| ∣ J ∣ are also possible [30 ] ; they are slightly more difficult to analyze, yet behave similarly under the asymptotic regime of interest introduced below.
Spherically symmetric diversity model of useful features
Let
V : = 1 ⊥ = { u ∈ R C : 1 T u = 0 } , P = I C − 1 C 11 T . \mathcal{V}:=1^\perp=\{u\in\mathbb{R}^C:1^\mathsf{T}u=0\},\qquad P=I_C-\frac{1}{C}11^\mathsf{T}. V := 1 ⊥ = { u ∈ R C : 1 T u = 0 } , P = I C − C 1 1 1 T .
For each j ∈ J j\in\mathcal{J} j ∈ J , draw independently
U ( j ) ∼ Unif { u ∈ V : ∥ u ∥ 2 = 1 } , U^{(j)}\sim\operatorname{Unif}\{u\in\mathcal{V}:\|u\|_2=1\}, U ( j ) ∼ Unif { u ∈ V : ∥ u ∥ 2 = 1 } ,
and set
v ( j ) : = C U ( j ) , μ ( j ) : = τ v ( j ) = ( μ 1 ( j ) , … , μ C ( j ) ) T . (11) v^{(j)}:=\sqrt{C}U^{(j)},\qquad\mu^{(j)}:=\tau v^{(j)}=(\mu_1^{(j)},\ldots,\mu_C^{(j)})^\mathsf{T}. \tag*{(11)} v ( j ) := C U ( j ) , μ ( j ) := τ v ( j ) = ( μ 1 ( j ) , … , μ C ( j ) ) T . (11)
For j ∉ J j\notin\mathcal{J} j ∈ / J , all class means are equal in coordinate j j j , equivalently P μ ( j ) = 0 P\mu^{(j)}=0 P μ ( j ) = 0 . We say that this construction is spherically symmetric because, for each j ∈ J j\in\mathcal{J} j ∈ J ,
1 T μ ( j ) = 0 , ∥ μ ( j ) ∥ 2 2 = τ 2 C . 1^\mathsf{T}\mu^{(j)}=0,\qquad\|\mu^{(j)}\|_2^2=\tau^2 C. 1 T μ ( j ) = 0 , ∥ μ ( j ) ∥ 2 2 = τ 2 C .
The spherical contrast prior is a symmetry-preserving way to extend the binary Rare-and-Weak Useful Feature model of Donoho and Jin to multiple classes. When C = 2 C=2 C = 2 , the centered contrast space 1 ⊥ 1^\perp 1 ⊥ is one-dimensional, and the uniform distribution on its unit sphere reduces to a random sign. For C > 2 C>2 C > 2 , the same construction gives the rotationally invariant prior on the centered class-contrast space. Such spherical priors are common in high-dimensional inference and random matrix theory because they preserve the symmetries of the null model and often lead to analytically tractable, least-favorable alternatives; see, for example, Baik et al. [ [4 ] , Perry et al. [ [29 ] , and El Alaoui et al. [ [14 ] . Other multiclass sparse-feature constructions are possible, including the high-dimensional normal model of Abramovich and Pensky [ [1 ] , but it is unclear whether these can yield an interesting asymptotic behavior.
We denote the data-generation model defined so far as MCRW( p , C , ϵ , τ ) (p,C,\epsilon,\tau) ( p , C , ϵ , τ ) . We keep the dependence of the model on σ 2 \sigma^2 σ 2 and n n n implicit, since these parameters do not directly affect the asymptotic behavior.
The ideal threshold
For simplicity of the analysis, but also due to asymptotic optimality under MCRW( p , C , ϵ , τ ) (p,C,\epsilon,\tau) ( p , C , ϵ , τ ) , we consider a maximum-inner-product classification rule over the selected features:
h ^ ( x ; J ) : = arg max c ∈ [ C ] [ x [ J ] ] T μ ^ c [ J ] . (12) \widehat{h}(x;\mathcal{J}):=\underset{c\in[C]}{\arg\max}\;[x[\mathcal{J}]]^\mathsf{T}\widehat{\mu}_c[\mathcal{J}]. \tag*{(12)} h ( x ; J ) := c ∈ [ C ] arg max [ x [ J ] ] T μ c [ J ] . (12)
where μ ^ c = ( μ ^ c , 1 , … , μ ^ c , p ) \widehat{\mu}_c=(\widehat{\mu}_{c,1},\ldots,\widehat{\mu}_{c,p}) μ c = ( μ c , 1 , … , μ c , p ) collects the class sample means (4) and x [ J ] x[\mathcal{J}] x [ J ] is coordinate selection operation (3) . For a general threshold t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , define the selected set of features based on ANOVA p-values as
J ^ ( t ) : = { j ∈ [ p ] : π j ≤ t } . (13) \widehat{\mathcal{J}}(t):=\{j\in[p]:\pi_j\le t\}. \tag*{(13)} J ( t ) := { j ∈ [ p ] : π j ≤ t } . (13)
Notice that under this construction, the expected misclassification error under MCRW ( p , C , ϵ , τ ) \operatorname{MCRW}(p,C,\epsilon,\tau) MCRW ( p , C , ϵ , τ ) is a function of the threshold t t t . We denote this function by
e ( t ) : = E MCRW ( p , C , ϵ , τ ) [ 1 { h ^ ( X ; J ^ ( t ) ) ≠ Y } ] . e(t):=\mathbb{E}_{\operatorname{MCRW}(p,C,\epsilon,\tau)}\left[1\{\widehat{h}(X;\widehat{\mathcal{J}}(t))\ne Y\}\right]. e ( t ) := E MCRW ( p , C , ϵ , τ ) [ 1 { h ( X ; J ( t )) = Y } ] .
The ideal threshold, denoted by t ⋆ t^\star t ⋆ , is the one that minimizes e ( t ) e(t) e ( t ) :
t ⋆ : = arg min t ∈ [ 0 , 1 ] e ( t ) . (14) t^\star:=\underset{t\in[0,1]}{\arg\min}\ e(t). \tag*{(14)} t ⋆ := t ∈ [ 0 , 1 ] arg min e ( t ) . (14)
It is not clear how to compute e ( t ) e(t) e ( t ) , as even the case of C = 2 C=2 C = 2 is challenging and was not fully solved in Donoho and Jin [ [13 ] . However, we can approximate e ( t ) e(t) e ( t ) , and thus t ⋆ t^\star t ⋆ , relatively straightforwardly using Monte Carlo simulations, as demonstrated in Figure 3 below.
Figure 3. Threshold comparison: classification error vs. β \beta β for a fixed r r r value and several value of C C C (p = 2,000 p = 2{,}000 p = 2 , 000 , n M o n t e = 150 n_{\mathrm{Monte}} = 150 n Monte = 150 ). Solid black: ideal threshold of (14) ; dashed blue: DP-HCT; dash-dot orange: Benjamini-Hochberg’s False-Discovery Rate (BH-FDR) at level 0.10; dotted green: Bonferroni (α = 0.05 \alpha= 0.05 α = 0.05 ). Dashed grey: chance-level error 1 − 1 / C 1 - 1/C 1 − 1/ C . It can be seen that DP-HCT classification performance closely follows the ideal threshold’s performance.
The ideal threshold t ⋆ t^\star t ⋆ depends on the latent model parameters ϵ \epsilon ϵ and τ \tau τ , hence it is not accessible to the data analyst. We hope that HCT approximates the ideal threshold, at least in the parts of the parameter space above and nearby the detection threshold, where non-trivial classification is challenging but possible.
Model calibration for asymptotic analysis
We consider the asymptotic limit as p → ∞ p\to\infty p → ∞ , where the model parameters are calibrated to p p p through fixed parameters ( β , r , s ) (\beta,r,s) ( β , r , s ) . The rarity level is
ϵ = p − β , β ∈ ( 1 / 2 , 1 ) . (15) \epsilon=p^{-\beta},\qquad\beta\in(1/2,1). \tag*{(15)} ϵ = p − β , β ∈ ( 1/2 , 1 ) . (15)
The signal amplitude is calibrated by
τ 2 = σ 2 n 2 r log p , r > 0. (16) \tau^2=\frac{\sigma^2}{n}2r\log p,\qquad r>0. \tag*{(16)} τ 2 = n σ 2 2 r log p , r > 0. (16)
Notice that under the spherical contrast construction, every useful feature has ANOVA non-centrality
λ j = n c σ 2 μ ( j ) T P μ ( j ) = n C C τ 2 σ 2 = 2 r log p , j ∈ J . (17) \lambda_j=\frac{n_c}{\sigma^2}\mu^{(j)\mathsf{T}}P\mu^{(j)}=\frac{n}{C}\frac{C\tau^2}{\sigma^2}=2r\log p,\qquad j\in\mathcal{J}. \tag*{(17)} λ j = σ 2 n c μ ( j ) T P μ ( j ) = C n σ 2 C τ 2 = 2 r log p , j ∈ J . (17)
Thus, r r r is the standardized ANOVA-visible rare and weak signal strength [10 ] .
For the number of classes, we focus on the logarithmic multiclass regime
C ∼ 2 s log p , s > 0. (18) C\sim2s\log p,\qquad s>0. \tag*{(18)} C ∼ 2 s log p , s > 0. (18)
We also discuss the fixed- or slowly-growing-class regime C = o ( log p ) C=o(\log p) C = o ( log p ) as a comparison case. For the ANOVA F F F -test analysis, we assume
log p = o ( n ) , (19) \log p=o(n), \tag*{(19)} log p = o ( n ) , (19)
so that the normalized within-class variance denominator of the F F F statistic concentrates at σ 2 \sigma^2 σ 2 . Consequently, ( C − 1 ) f j (C-1)f_j ( C − 1 ) f j has the same polynomial-tail exponent as a non-central chi-square random variable with C − 1 C-1 C − 1 degrees of freedom and non-centrality parameter λ j \lambda_j λ j .
Main Results: Classification Phase Transition and Optimality of DP-HCT
We now state the main theoretical consequences for DP-HCT under the MCRW ( p , C , ϵ , τ ) \operatorname{MCRW}(p,C,\epsilon,\tau) MCRW ( p , C , ϵ , τ ) framework of § 4 . Throughout, π j \pi_j π j denotes the p-values obtained from the one-way ANOVA F F F -test (7) .
The classification boundary
For s > 0 s>0 s > 0 , let x s ( q ) ≥ s x_s(q)\ge s x s ( q ) ≥ s solve
g s ( x s ( q ) ) = q , g s ( x ) = x − s − s log ( x / s ) , g_s(x_s(q))=q,\qquad g_s(x)=x-s-s\log(x/s), g s ( x s ( q )) = q , g s ( x ) = x − s − s log ( x / s ) ,
and set x 0 ( q ) = q x_0(q)=q x 0 ( q ) = q . Define
Ψ r , s ( q ) = J r , s ( x s ( q ) ) , J r , s ( x ) = sup 0 ≤ θ < 1 { θ x + s log ( 1 − θ ) − r θ 1 − θ } . \Psi_{r,s}(q)=J_{r,s}(x_s(q)),\qquad J_{r,s}(x)=\sup_{0\le\theta<1}\left\{\theta x+s\log(1-\theta)-\frac{r\theta}{1-\theta}\right\}. Ψ r , s ( q ) = J r , s ( x s ( q )) , J r , s ( x ) = 0 ≤ θ < 1 sup { θ x + s log ( 1 − θ ) − 1 − θ r θ } .
For fixed ( β , s ) (\beta,s) ( β , s ) , the signal-strength boundary function is defined by
ξ ⋆ ( β , s ) : = inf { r > 0 : max 0 ≤ q ≤ 1 ( 1 2 − β + q 2 − Ψ r , s ( q ) ) > 0 } . (20) \xi^\star(\beta,s):=\inf\left\{r>0:\max_{0\le q\le1}\left(\frac{1}{2}-\beta+\frac{q}{2}-\Psi_{r,s}(q)\right)>0\right\}. \tag*{(20)} ξ ⋆ ( β , s ) := inf { r > 0 : 0 ≤ q ≤ 1 max ( 2 1 − β + 2 q − Ψ r , s ( q ) ) > 0 } . (20)
The maximum in (20) has an explicit optimizer, given in Section H of the Supplementary Material. The boundary function ξ ⋆ ( β , s ) \xi^\star(\beta,s) ξ ⋆ ( β , s ) is strictly increasing in s s s and has the following limiting forms.
As s → 0 s\to0 s → 0 , ξ ⋆ ( β , s ) → ρ ⋆ ( β ) \xi^\star(\beta,s)\to\rho^\star(\beta) ξ ⋆ ( β , s ) → ρ ⋆ ( β ) , where ρ ⋆ ( β ) \rho^\star(\beta) ρ ⋆ ( β ) is the Ingster-Donoho-Jin rare signal detection boundary function
ρ ⋆ ( β ) : = { β − 1 2 , 1 2 < β < 3 4 , ( 1 − 1 − β ) 2 , 3 4 ≤ β < 1. \rho^\star(\beta):=
\begin{cases}
\beta-\frac{1}{2}, & \frac{1}{2}<\beta<\frac{3}{4},\\
(1-\sqrt{1-\beta})^2, & \frac{3}{4}\le\beta<1.
\end{cases} ρ ⋆ ( β ) := { β − 2 1 , ( 1 − 1 − β ) 2 , 2 1 < β < 4 3 , 4 3 ≤ β < 1.
This is also the boundary for C = o ( log p ) C=o(\log p) C = o ( log p ) , fixed C C C in particular.
As s → ∞ s\to\infty s → ∞ , ξ ⋆ ( β , s ) ∼ 2 s ρ ⋆ ( β ) \xi^\star(\beta,s)\sim\sqrt{2s}\,\rho^\star(\beta) ξ ⋆ ( β , s ) ∼ 2 s ρ ⋆ ( β ) . This is an iterated limit of the fixed-s s s boundary. The ANOVA numerator has null standard deviation 2 ( C − 1 ) \sqrt{2(C-1)} 2 ( C − 1 ) , so its standardized non-centrality is λ / 2 ( C − 1 ) ∼ r log p / s \lambda/\sqrt{2(C-1)}\sim r\sqrt{\log p/s} λ / 2 ( C − 1 ) ∼ r log p / s . Thus additional degrees of freedom reduce per-feature separation. The large-s s s approximation is shown as dashed reference lines in Figure 1 (right).
Impossibility below the boundary
Theorem 1 (Impossibility below the boundary). Under MCRW ( p , C , ϵ , τ ) \operatorname{MCRW}(p,C,\epsilon,\tau) MCRW ( p , C , ϵ , τ ) with calibrations (15)–(19) and a uniformly distributed independent test label, if r < ξ ⋆ ( β , s ) r<\xi^\star(\beta,s) r < ξ ⋆ ( β , s ) , then every measurable classifier h ^ \hat h h ^ satisfies
P { h ^ ( X n + 1 ) = Y n + 1 } ≤ 1 C + o ( 1 ) . \mathbb{P}\{\hat h(X_{n+1})=Y_{n+1}\}\le\frac{1}{C}+o(1). P { h ^ ( X n + 1 ) = Y n + 1 } ≤ C 1 + o ( 1 ) . Consequently,
sup h ^ P { h ^ ( X n + 1 ) = Y n + 1 } = 1 C + o ( 1 ) . \sup_{\hat h}\mathbb{P}\{\hat h(X_{n+1})=Y_{n+1}\}=\frac{1}{C}+o(1). h ^ sup P { h ^ ( X n + 1 ) = Y n + 1 } = C 1 + o ( 1 ) .
The proof is in Section F of the Supplementary Material. It uses a truncated likelihood-ratio second-moment argument to establish vanishing total variation for the joint training and test experiment; see Butucea and Ingster [ [8 ] for a related use of this method.
DP-HCT succeeds above the boundary
Theorem 2 (DP-HCT succeeds above the boundary). Under MCRW ( p , C , ϵ , τ ) \operatorname{MCRW}(p,C,\epsilon,\tau) MCRW ( p , C , ϵ , τ ) with calibrations (15)–(19) and n = p o ( 1 ) n=p^{o(1)} n = p o ( 1 ) , let J ^ \hat J J ^ be the selected set of features based on ANOVA p p p -values (7) and threshold (13), and let h ^ \hat h h ^ be the maximum-inner-product classifier (12) with J ~ = J ^ \tilde J=\hat J J ~ = J ^ . If r > ξ ⋆ ( β , s ) r>\xi^\star(\beta,s) r > ξ ⋆ ( β , s ) , then, for an independent test point ( X n + 1 , Y n + 1 ) ∼ MCRW ( p , C , ϵ , τ ) (X_{n+1},Y_{n+1})\sim\operatorname{MCRW}(p,C,\epsilon,\tau) ( X n + 1 , Y n + 1 ) ∼ MCRW ( p , C , ϵ , τ ) ,
P { h ^ ( X n + 1 ; J ^ ) ≠ Y n + 1 } = o ( 1 ) . \mathbb{P}\{\hat h(X_{n+1};\hat J)\ne Y_{n+1}\}=o(1). P { h ^ ( X n + 1 ; J ^ ) = Y n + 1 } = o ( 1 ) .
We leave for future work the study of DP-HCT optimality under other sample-size regimes, including polynomial growth n = p θ + o ( 1 ) n=p^{\theta+o(1)} n = p θ + o ( 1 ) with fixed θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) .
Experiments
Verification of successful classification region
Setup. We simulate from the MCRW( p , C , ϵ , τ ) (p, C, \epsilon, \tau) ( p , C , ϵ , τ ) model with p = 2,000 p = 2{,}000 p = 2 , 000 and ϵ \epsilon ϵ , τ \tau τ , and C C C as in, respectively, (15), (16), and (18). We use n M o n t e = 150 n_{\mathrm{Monte}} = 150 n Monte = 150 independent problem instances per ( β , r ) (\beta, r) ( β , r ) grid point. After feature screening, classification is performed with the centroid-similarity classifier of (12).
Misclassification phase transition. Figure 2 shows the misclassification rate over a grid of ( β , r ) (\beta, r) ( β , r ) values for C ∈ { 2 , 5 , 10 } C \in\{2, 5, 10\} C ∈ { 2 , 5 , 10 } ; configurations in which the misclassification rate is significantly above chance are marked with black frames. As C C C increases, the boundary rises, reflecting the increased difficulty of multiclass discrimination; two theoretical phase-transition boundaries are overlaid on every heatmap: (1) the boundary r = ξ ∗ ( β , s ) r = \xi^{*}(\beta, s) r = ξ ∗ ( β , s ) of (20) (solid) and (2) the boundary r = ρ ∗ ( β ) r = \rho^{*}(\beta) r = ρ ∗ ( β ) (dotted). The boundary (1), established in Theorems 1 and 2 , assumes that C C C increases with p p p . The boundary (2), derived in Donoho and Jin [ [11 ] , corresponds to a fixed C C C . The figure shows that the above-chance region better follows boundary (1), even for small C C C . Additional figures characterizing the ideal threshold and per-C C C side-by-side comparisons are collected in the Supplementary Material, Section A.
Figure 2. DP-HCT misclassification phase transition. Misclassification rate (color) over a grid of ( β , r ) (\beta, r) ( β , r ) values for C ∈ { 2 , 5 , 10 } C \in\{2, 5, 10\} C ∈ { 2 , 5 , 10 } , under the Gaussian multiclass Rare-and-Weak Useful Feature model with p = 2,000 p = 2{,}000 p = 2 , 000 , n M o n t e = 150 n_{\mathrm{Monte}} = 150 n Monte = 150 . The x-axis is the sparsity exponent β \beta β and the y-axis is the calibrated signal strength r r r . Configurations in which the misclassification rate is above chance are marked with black frames. Solid white: the theoretical phase transition curve (Theorem 2 ). Dotted white: the phase transition curve corresponding to a fixed number of classes, derived in Donoho and Jin [ [11 ] .
Comparison with other thresholds. Figure 3 compares four feature-selection rules for data sampled from the MCRW( p , C , ϵ , τ ) (p, C, \epsilon, \tau) ( p , C , ϵ , τ ) . The ideal threshold of (14), which achieves the best performance achievable by thresholding the ANOVA p p p -values, but is not a function of the data. We compare it with DP-HCT, Benjamini-Hochberg’s False-Discovery Rate at level 0.10 [5 ] , and selection after Bonferroni’s correction with α = 0.05 \alpha= 0.05 α = 0.05 .
Real data benchmarks
The main theoretical justification for DP-HCT is its role in a classification pipeline that attains the multiclass Rare-and-Weak Useful Feature phase transition. To complement this theoretical characterization, we evaluate classification following DP-HCT against baseline methods on five public biological multiclass benchmarks with p > n p > n p > n , spanning gene expression, metabolomics, and miRNA expression; see Section B.1 of the Supplementary Material for preprocessing details.
Heart-Circadian (GSE10045; Bray et al., [7 ] ): n = 130 n = 130 n = 130 mouse-heart expression profiles, C = 8 C = 8 C = 8 times of day, p = 46,120 p = 46{,}120 p = 46 , 120 probes.
Worm-Bacteria (GSE15923; Coolon et al., [9 ] ): n = 72 n = 72 n = 72 C. elegans expression profiles, C = 4 C = 4 C = 4 bacterial diets, p = 672 p = 672 p = 672 features.
Blood-Diet (ST002019; Ferguson, [16 ] , Metabolomics Workbench): n = 70 n = 70 n = 70 blood LC–MS profiles from 35 participants, C = 4 C = 4 C = 4 diet × \times × study-phase groups, p = 736 p = 736 p = 736 metabolite features.
Zebrafish-BPF (ST003804; [17 Metabolomics Workbench] ): n = 62 n = 62 n = 62 zebrafish-liver LC–MS profiles, C = 4 C = 4 C = 4 exposure levels of bisphenol F, p = 117 p = 117 p = 117 metabolite features.
Biliary-miRNA (GSE140001; [26 ] ): n = 36 n = 36 n = 36 microdissected tissue samples from 12 patients, C = 3 C = 3 C = 3 tissue types, p = 803 p = 803 p = 803 miRNAs.
For the diversity test we use either ANOVA F (7) or KW (9) , depending on which one obtained higher classification accuracy. We evaluate two classifiers before and after feature screening: a radial-basis-function SVM (DP-HCT-SVM) and ℓ 2 \ell_2 ℓ 2 -regularized multinomial logistic regression (DP-HCT-LoR). All baselines apply the same classifiers to the full, unselected feature matrix; see Section B of the Supplementary Material for full protocol details. Table 1 reports mean cross-validated accuracy for both classifiers pre- and post-DP-HCT, and the number of features retained ("# Sel.").
Table 1. CV accuracy (mean ± \pm ± SEM, % ) for classification post-DP-HCT feature screening with ANOVA F ("F") or KW ("KW") tests; results are averaged over 10-fold, unit stratified cross-validation (7-fold for Heart-Circadian). “# Sel.” is the mean number of features retained by DP-HCT.
We also stress-test the pipeline, either by adding independent noise to every entry, scaled to each feature’s own standard deviation, or by appending many pure-noise (useless) features. With added noise, DP-HCT-LoR substantially improves over the baseline at small noise levels in most cases. The improvement also holds up when a substantial number of pure-noise features is appended; the details and the results are in Section B.4 of the Supplementary Material.
Conclusion
DP-HCT extends higher-criticism feature screening to multiclass problems in which useful features are rare and individually weak. The theory identifies a multiclass phase transition that depends explicitly on the growth of the number of classes, and shows that diversity-based HC screening attains this boundary with a simple centroid-similarity classifier. Simulations confirm the predicted transition, while real-data benchmarks and stress tests show that the same screening principle can substantially improve classification when irrelevant or noisy coordinates dominate the feature space.
Synthetic-Data Simulations: Additional Figures
All figures in this section use the Gaussian multiclass Rare-and-Weak Useful Feature model MCRW(p , C , ϵ , τ p, C, \epsilon, \tau p , C , ϵ , τ ) with n M o n t e = 150 n_{\mathrm{Monte}} = 150 n Monte = 150 Monte Carlo draws per ( β , r ) (\beta, r) ( β , r ) grid point, unless stated otherwise. The ideal threshold for MCRW(p , C , ϵ , τ p, C, \epsilon, \tau p , C , ϵ , τ ), HCT, BH-FDR (q = 0.10 q = 0.10 q = 0.10 ), and Bonferroni (α = 0.05 \alpha= 0.05 α = 0.05 ) selectors are all followed by a centroid similarity classifier. Phase boundaries overlaid on heatmaps are the multiclass boundary r = ξ ∗ ( β , s ) r = \xi^{*}(\beta, s) r = ξ ∗ ( β , s ) (solid) and the fixed-number-of-classes boundary of Donoho and Jin [ [11 ] (dotted).
Figure 4. Ideal-threshold misclassification rate heatmaps for C ∈ { 2 , 3 , 4 , 5 , 7 , 10 } C \in\{2, 3, 4, 5, 7, 10\} C ∈ { 2 , 3 , 4 , 5 , 7 , 10 } . Color encodes misclassification rate. Solid white: the multiclass boundary r = ξ ∗ ( β , s ) r = \xi^{*}(\beta, s) r = ξ ∗ ( β , s ) of (20) . Dotted white: the fixed-class Donoho–Jin boundary r = ρ ∗ ( β ) r = \rho^{*}(\beta) r = ρ ∗ ( β ) . The transition from high to low error closely tracks the multiclass boundary; as C C C increases, the boundary rises, reflecting the harder multiclass discrimination problem.
Figure 5. Empirical false-discovery rate of the threshold rules. The empirical FDR is the average, over Monte Carlo draws, of the proportion of selected features that are null. Left: FDR vs. r r r for C = 5 C = 5 C = 5 , β = 0.6 \beta= 0.6 β = 0.6 . Middle: FDR vs. r r r for C = 5 C = 5 C = 5 , β = 0.8 \beta= 0.8 β = 0.8 . Right: FDR vs. the number of classes C ∈ { 2 , … , 10 } C \in\{2,\ldots,10\} C ∈ { 2 , … , 10 } for r = 1 r = 1 r = 1 , β = 0.6 \beta= 0.6 β = 0.6 . Solid black: ideal threshold of (14) ; dashed blue: DP-HCT; dash-dot orange: Benjamini–Hochberg’s False-Discovery Rate (q = 0.10 q = 0.10 q = 0.10 ); dotted green: Bonferroni (α = 0.05 \alpha= 0.05 α = 0.05 ); dashed grey: the nominal level 0.10. Shaded bands are 95% confidence intervals of the Monte Carlo mean (p = 2,000 p = 2{,}000 p = 2 , 000 , n M o n t e = 300 n_{\mathrm{Monte}} = 300 n Monte = 300 ). Draws in which DP-HCT does not reject the global null (HC statistic below 1.9) select no features and count as an FDR of zero. The figure shows that DP-HCT closely tracks the ideal threshold in the regime where detection is possible. These two rules are tuned for classification rather than for error control, and therefore admit many false discoveries. BH attains its nominal level and Bonferroni is conservative.
Real-Data Experimental Details
Datasets
The 5 datasets are listed in Table 2 .
Table 2. Five real-data benchmarks, their sizes, and additional relevant information. “Units” is the number of independent patients, participants, animals or arrays (equal to n n n when samples are independent).
Preprocessing. We use the matrices provided by the repositories (GEO series matrices, Metabolomics Workbench data tables [31 ] ). Features with fewer than 95% finite values are removed, remaining missing values are imputed by the feature median, log 2 ( x + 1 ) \log_2(x + 1) log 2 ( x + 1 ) is applied when the matrix is non-negative with maximum above 100, and constant features are dropped. The values of p p p reported below are counted after these steps. No other preprocessing is applied beyond per-fold standardization inside the classifiers.
Cross-validation protocol
Classification accuracy results use stratified CV with K = 10 K = 10 K = 10 folds (K = 7 K = 7 K = 7 for Heart-Circadian, the largest number of folds that leaves at least one unit of every class in each fold). Table 3 reports averages over five CV runs with different seeds. Stress-test results use K = 10 K = 10 K = 10 folds with three repeats (K = 7 K = 7 K = 7 with a single repeat for Heart-Circadian, whose stress runs are the slowest).
Table 3. CV accuracy (mean ± \pm ± SEM, %) for the five datasets, averaged over five CV runs with different seeds (the SEM is the mean within-run SEM across folds). The diversity test is given next to each dataset (F = ANOVA F, KW = Kruskal–Wallis); raw p-values; HC with γ 0 = 1 / 2 \gamma_0 = 1/2 γ 0 = 1/2 . “Frac. sel.” = mean fraction of features selected by HC.
We use stratified group folds when a patient, participant, animal or array contributes several samples, so that all samples of a unit are in the same fold and no unit appears in both a training and a test fold. Otherwise the repeated samples of a unit leak across the split and inflate the accuracy of both the baseline and the screened classifier. The units are listed in Table 2 .
DP-HCT pipeline
We executes the following steps within each fold on training data only.
Diversity p-values. Compute the ANOVA F or Kruskal–Wallis statistic per feature on the training split, and convert it to a p-value π j \pi_j π j from the F C − 1 , n − C F_{C-1,n-C} F C − 1 , n − C or χ C − 1 2 \chi^2_{C-1} χ C − 1 2 reference distribution. p-values are clipped to [ 10 − 300 , 1 − 10 − 15 ] [10^{-300},\ 1 - 10^{-15}] [ 1 0 − 300 , 1 − 1 0 − 15 ] . The lower clip exists only to keep exact zeros out of the HC denominator and must lie below the smallest p-value the data produce.
HC thresholding (HCT). Obtain j ⋆ j^\star j ⋆ of (2) and set J ^ = { j : π j ≤ π ( j ⋆ ) } \hat{J} = \{j : \pi_j \leq\pi_{(j^\star)}\} J ^ = { j : π j ≤ π ( j ⋆ ) } .
Classifiers. Two plug-in classifiers are evaluated on J ^ \hat{J} J ^ :
SVM: RBF-kernel SVC (sklearn, random_state=0), features standardized with StandardScaler.
Logistic: ℓ 2 \ell_2 ℓ 2 -penalized multinomial logistic regression (saga solver).
Table 3 : CV accuracy (mean ± \pm ± SEM, %) for the five datasets, averaged over five CV runs with different seeds (the SEM is the mean within-run SEM across folds). The diversity test is given next to each dataset (F = ANOVA F, KW = Kruskal–Wallis); raw p-values; HC with γ 0 = 1 / 2 \gamma_0 = 1/2 γ 0 = 1/2 . “Frac. sel.” = mean fraction of features selected by HC.
Stress-test protocol
We perturb each of the five datasets by one of:
Noise injection (σ \sigma σ sweep): independent N ( 0 , σ 2 ) \mathcal{N}(0, \sigma^2) N ( 0 , σ 2 ) noise is added per fold to every element of X t r a i n X_{\mathrm{train}} X train and X t e s t X_{\mathrm{test}} X test for σ ∈ { 0 , 0.5 , 1.0 , 1.5 , 2.0 } \sigma\in\{0, 0.5, 1.0, 1.5, 2.0\} σ ∈ { 0 , 0.5 , 1.0 , 1.5 , 2.0 } .
Nuisance feature inflation (p e x t r a p_{\mathrm{extra}} p extra sweep): p e x t r a ∈ { 0 , 10 3 , 2.5 × 10 3 , 5 × 10 3 , 10 4 , 2.5 × 10 4 , 5 × 10 4 } p_{\mathrm{extra}} \in\{0, 10^3, 2.5 \times10^3, 5 \times10^3, 10^4, 2.5 \times10^4, 5 \times10^4\} p extra ∈ { 0 , 1 0 3 , 2.5 × 1 0 3 , 5 × 1 0 3 , 1 0 4 , 2.5 × 1 0 4 , 5 × 1 0 4 } additional N ( 0 , 1 ) \mathcal{N}(0, 1) N ( 0 , 1 ) columns are concatenated per fold.
Both perturbations occur after the train/test split and before feature selection, so HC is never exposed to test-fold data. Both perturbations are regenerated independently for each fold, as explained below in more detail. The results are illustrated in Figure 6 .
Figure 6. Classification with LoR pre- and post-feature screening by DP-HCT with added noise (left column) or nuisance features (right column). p p p -values are obtained either from ANOVA F (ANOVA) or Kruskal–Wallis (KW) as indicated for each panel; HC with γ 0 = 1 / 2 \gamma_0 = 1/2 γ 0 = 1/2 ; error bars indicate ± \pm ± SEM over the pooled CV folds (10 folds × \times × 3 repeats; 7 folds for Heart-Circadian); the uniform chance level 1 / C 1/C 1/ C is shown as a dashed horizontal line.
Noise injection. X i j ← X i j + σ s ^ j ε i j X_{ij} \leftarrow X_{ij} + \sigma\hat{s}_j \varepsilon_{ij} X ij ← X ij + σ s ^ j ε ij with ε i j \varepsilon_{ij} ε ij i.i.d. N ( 0 , 1 ) \mathcal{N}(0, 1) N ( 0 , 1 ) drawn fresh per fold, where s ^ j \hat{s}_j s ^ j is the standard deviation of feature j j j on the training fold. Grid: σ ∈ { 0.0 , 0.5 , 1.0 , 1.5 , 2.0 } \sigma\in\{0.0, 0.5, 1.0, 1.5, 2.0\} σ ∈ { 0.0 , 0.5 , 1.0 , 1.5 , 2.0 } . The noise is scaled relative to each feature’s own spread because the panels differ in units (the median feature
standard deviation ranges from 0.3 on Blood-Diet to 511 on Worm-Bacteria). Scales are estimated on the training fold only to prevent test information leakage.
Nuisance feature inflation. X ← [ X , G ] X \leftarrow[X,G] X ← [ X , G ] where G G G has i.i.d. N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 ) entries. Grid: p e x t r a ∈ { 0 , 10 3 , 2.5 × 10 3 , 5 × 10 3 , 10 4 , 2.5 × 10 4 , 5 × 10 4 } p_{\mathrm{extra}} \in\{0, 10^3, 2.5 \times10^3, 5 \times10^3, 10^4, 2.5 \times10^4, 5 \times10^4\} p extra ∈ { 0 , 1 0 3 , 2.5 × 1 0 3 , 5 × 1 0 3 , 1 0 4 , 2.5 × 1 0 4 , 5 × 1 0 4 } . Because the grid is absolute while p p p varies across panels, the resulting feature ratio ( p + p e x t r a ) / p (p+p_{\mathrm{extra}})/p ( p + p extra ) / p depends on the size of the dataset.
Notation and auxiliary facts
We collect the notation used throughout the proofs and record several auxiliary facts about the chi-squared distribution that will be invoked repeatedly.
Notation
Throughout, p → ∞ p \to\infty p → ∞ indexes the asymptotic regime, and all probabilistic statements are understood in this limit unless stated otherwise. We write a p = O ( b p ) a_p = O(b_p) a p = O ( b p ) if ∣ a p ∣ / ∣ b p ∣ \lvert a_p\rvert/\lvert b_p\rvert ∣ a p ∣ / ∣ b p ∣ is eventually bounded, a p = o ( b p ) a_p = o(b_p) a p = o ( b p ) if a p / b p → 0 a_p/b_p \to0 a p / b p → 0 , and a p ≍ b p a_p \asymp b_p a p ≍ b p if both a p = O ( b p ) a_p = O(b_p) a p = O ( b p ) and b p = O ( a p ) b_p = O(a_p) b p = O ( a p ) . Probabilistic versions O P O_{\mathbb{P}} O P , o P o_{\mathbb{P}} o P are defined analogously in probability. For a set Q Q Q , we write a p ( q ) = o ( b p ( q ) ) a_p(q) = o(b_p(q)) a p ( q ) = o ( b p ( q )) uniformly in q ∈ Q q \in Q q ∈ Q if sup q ∈ Q ∣ a p ( q ) / b p ( q ) ∣ → 0 \sup_{q \in Q} \lvert a_p(q)/b_p(q)\rvert\to0 sup q ∈ Q ∣ a p ( q ) / b p ( q )∣ → 0 .
We use C C C , K K K , c c c , c ′ c' c ′ to denote positive constants that may change from line to line but do not depend on p p p unless explicitly indicated.
Model and objects
We work under the Gaussian multiclass rare/weak model of § 4.2 . Thus
X i ∣ Y i = c ∼ N ( μ c , σ 2 I p ) , n c = n / C , X_i \mid Y_i=c \sim\mathcal{N}(\mu_c,\sigma^2 I_p), \qquad n_c = n/C, X i ∣ Y i = c ∼ N ( μ c , σ 2 I p ) , n c = n / C ,
and the set of useful features J ⊂ [ p ] \mathcal{J} \subset[p] J ⊂ [ p ] has rarity ϵ p = p − β \epsilon_p = p^{-\beta} ϵ p = p − β , β ∈ ( 1 / 2 , 1 ) \beta\in(1/2,1) β ∈ ( 1/2 , 1 ) . On J \mathcal{J} J , the spherical homogeneous contrast construction (11) –(17) gives λ j = 2 r log p \lambda_j = 2r \log p λ j = 2 r log p for j ∈ J j \in\mathcal{J} j ∈ J and λ j = 0 \lambda_j = 0 λ j = 0 for j ∉ J j \notin\mathcal{J} j ∈ / J . Class-c c c sample means are μ ^ c , j \hat{\mu}_{c,j} μ ^ c , j as in (4) , and
μ ^ ⋅ , j : = ( μ ^ 1 , j , … , μ ^ C , j ) T \hat{\mu}_{\cdot,j} := (\hat{\mu}_{1,j},\ldots,\hat{\mu}_{C,j})^\mathsf{T} μ ^ ⋅ , j := ( μ ^ 1 , j , … , μ ^ C , j ) T
is the vector of those means at feature j j j . The model means are the superscript coordinates μ c ( j ) \mu_c^{(j)} μ c ( j ) of
μ ( j ) = ( μ 1 ( j ) , … , μ C ( j ) ) T . \mu^{(j)} = (\mu_1^{(j)},\ldots,\mu_C^{(j)})^\mathsf{T}. μ ( j ) = ( μ 1 ( j ) , … , μ C ( j ) ) T .
For the numerator-based analysis, define
T j : = S S b e t w e e n ( j ) σ 2 , π j χ : = F ‾ χ k 2 ( T j ) , k : = C − 1 , T_j := \frac{\mathrm{SS}_{\mathrm{between}}^{(j)}}{\sigma^2}, \qquad\pi_j^\chi:= \overline{F}_{\chi_k^2}(T_j), \qquad k := C-1, T j := σ 2 SS between ( j ) , π j χ := F χ k 2 ( T j ) , k := C − 1 ,
and
Y j χ : = − 2 log π j χ = G k ( T j ) , G k ( t ) : = − 2 log F ‾ χ k 2 ( t ) . Y_j^\chi:= -2\log\pi_j^\chi= G_k(T_j), \qquad G_k(t) := -2\log\overline{F}_{\chi_k^2}(t). Y j χ := − 2 log π j χ = G k ( T j ) , G k ( t ) := − 2 log F χ k 2 ( t ) .
Chi-squared tail: quantitative expansion
The following one-sided tail expansion records useful auxiliary estimates. The exact exponent in Theorem 7 is proved separately by exponential tilting.
Lemma 3 (Chi-squared tail expansion). Let F ‾ k ( t ) : = P ( χ k 2 ≥ t ) \overline{F}_k(t) := \mathbb{P}(\chi_k^2 \ge t) F k ( t ) := P ( χ k 2 ≥ t ) denote the survival function of a central chi-squared random variable with k ≥ 1 k \ge1 k ≥ 1 degrees of freedom, and define
G k ( t ) : = − 2 log F ‾ k ( t ) , c k : = ( k − 2 ) log 2 + 2 log Γ ( k / 2 ) . G_k(t) := -2\log\overline{F}_k(t), \qquad c_k := (k-2)\log2 + 2\log\Gamma(k/2). G k ( t ) := − 2 log F k ( t ) , c k := ( k − 2 ) log 2 + 2 log Γ ( k /2 ) . Fix η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) . Uniformly over integers k ≥ 1 k \ge1 k ≥ 1 and real numbers t → ∞ t \to\infty t → ∞ satisfying
k t ≤ 1 − η , \frac{k}{t} \le1-\eta, t k ≤ 1 − η , we have
F ‾ k ( t ) = t ( k − 2 ) / 2 e − t / 2 2 ( k − 2 ) / 2 Γ ( k / 2 ) [ 1 + k − 2 t + O η ( ( k + 1 ) 2 t 2 ) ] . (21) \overline{F}_k(t) = \frac{t^{(k-2)/2}e^{-t/2}}{2^{(k-2)/2}\Gamma(k/2)}
\left[1+\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right)\right]. \tag*{(21)} F k ( t ) = 2 ( k − 2 ) /2 Γ ( k /2 ) t ( k − 2 ) /2 e − t /2 [ 1 + t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ] . (21)
Consequently,
G k ( t ) = t − ( k − 2 ) log t + c k + r k ( t ) , (22) G_k(t)=t-(k-2)\log t+c_k+r_k(t), \tag*{(22)} G k ( t ) = t − ( k − 2 ) log t + c k + r k ( t ) , (22)
where
r k ( t ) = − 2 log [ 1 + k − 2 t + O η ( ( k + 1 ) 2 t 2 ) ] . (23) r_k(t)=-2\log\left[1+\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right)\right]. \tag*{(23)} r k ( t ) = − 2 log [ 1 + t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ] . (23)
In particular, if additionally k / t = o ( 1 ) k/t=o(1) k / t = o ( 1 ) , then
r k ( t ) = − 2 ( k − 2 ) t + O ( ( k + 1 ) 2 t 2 ) . (24) r_k(t)=-\frac{2(k-2)}{t}+O\left(\frac{(k+1)^2}{t^2}\right). \tag*{(24)} r k ( t ) = − t 2 ( k − 2 ) + O ( t 2 ( k + 1 ) 2 ) . (24)
Moreover, in the same uniform regime,
G k ′ ( t ) = 1 − k − 2 t + O η ( ( k + 1 ) 2 t 2 ) , (25) G'_k(t)=1-\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right), \tag*{(25)} G k ′ ( t ) = 1 − t k − 2 + O η ( t 2 ( k + 1 ) 2 ) , (25)
and
G k ′ ′ ( t ) = k − 2 t 2 + O η ( ( k + 1 ) 2 t 3 ) . (26) G''_k(t)=\frac{k-2}{t^2}+O_\eta\left(\frac{(k+1)^2}{t^3}\right). \tag*{(26)} G k ′′ ( t ) = t 2 k − 2 + O η ( t 3 ( k + 1 ) 2 ) . (26)
Finally, as k → ∞ k\to\infty k → ∞ ,
c k = k log k − k − log k + O ( 1 ) . (27) c_k=k\log k-k-\log k+O(1). \tag*{(27)} c k = k log k − k − log k + O ( 1 ) . (27)
Proof. Write
s = k 2 , x = t 2 . s=\frac{k}{2},\qquad x=\frac{t}{2}. s = 2 k , x = 2 t .
Then
F ‾ k ( t ) = Γ ( s , x ) Γ ( s ) , \overline{F}_k(t)=\frac{\Gamma(s,x)}{\Gamma(s)}, F k ( t ) = Γ ( s ) Γ ( s , x ) ,
where
Γ ( s , x ) = ∫ x ∞ u s − 1 e − u d u \Gamma(s,x)=\int_x^\infty u^{s-1}e^{-u}\,du Γ ( s , x ) = ∫ x ∞ u s − 1 e − u d u
is the upper incomplete gamma function.
We first prove the tail expansion. Integrating by parts once gives
Γ ( s , x ) = x s − 1 e − x + ( s − 1 ) ∫ x ∞ u s − 2 e − u d u . \Gamma(s,x)=x^{s-1}e^{-x}+(s-1)\int_x^\infty u^{s-2}e^{-u}\,du. Γ ( s , x ) = x s − 1 e − x + ( s − 1 ) ∫ x ∞ u s − 2 e − u d u .
Integrating by parts a second time gives
∫ x ∞ u s − 2 e − u d u = x s − 2 e − x + ( s − 2 ) ∫ x ∞ u s − 3 e − u d u . \int_x^\infty u^{s-2}e^{-u}\,du=x^{s-2}e^{-x}+(s-2)\int_x^\infty u^{s-3}e^{-u}\,du. ∫ x ∞ u s − 2 e − u d u = x s − 2 e − x + ( s − 2 ) ∫ x ∞ u s − 3 e − u d u .
Therefore
Γ ( s , x ) = x s − 1 e − x [ 1 + s − 1 x + ( s − 1 ) ( s − 2 ) x 2 ∫ x ∞ u s − 3 e − u d u x s − 3 e − x ] . \Gamma(s,x)=x^{s-1}e^{-x}\left[1+\frac{s-1}{x}+\frac{(s-1)(s-2)}{x^2}\frac{\int_x^\infty u^{s-3}e^{-u}\,du}{x^{s-3}e^{-x}}\right]. Γ ( s , x ) = x s − 1 e − x [ 1 + x s − 1 + x 2 ( s − 1 ) ( s − 2 ) x s − 3 e − x ∫ x ∞ u s − 3 e − u d u ] .
We now bound the remainder. Since k / t ≤ 1 − η k/t\leq1-\eta k / t ≤ 1 − η , we have
s x = k t ≤ 1 − η . \frac{s}{x}=\frac{k}{t}\leq1-\eta. x s = t k ≤ 1 − η .
For u ≥ x u\geq x u ≥ x ,
u s − 3 e − u = x s − 3 e − x ( u x ) s − 3 e − ( u − x ) . u^{s-3}e^{-u}=x^{s-3}e^{-x}\left(\frac{u}{x}\right)^{s-3}e^{-(u-x)}. u s − 3 e − u = x s − 3 e − x ( x u ) s − 3 e − ( u − x ) .
Using the change of variables u = x + v u=x+v u = x + v ,
∫ x ∞ u s − 3 e − u d u x s − 3 e − x = ∫ 0 ∞ ( 1 + v x ) s − 3 e − v d v . \frac{\int_x^\infty u^{s-3}e^{-u}\,du}{x^{s-3}e^{-x}}=\int_0^\infty\left(1+\frac{v}{x}\right)^{s-3}e^{-v}\,dv. x s − 3 e − x ∫ x ∞ u s − 3 e − u d u = ∫ 0 ∞ ( 1 + x v ) s − 3 e − v d v .
For v ≥ 0 v \ge0 v ≥ 0 and s / x ≤ 1 − η s/x \le1-\eta s / x ≤ 1 − η ,
( 1 + v x ) s − 3 ≤ exp ( s v x ) ≤ exp ( ( 1 − η ) v ) . \left(1+\frac{v}{x}\right)^{s-3} \le\exp\left(\frac{sv}{x}\right) \le\exp((1-\eta)v). ( 1 + x v ) s − 3 ≤ exp ( x s v ) ≤ exp (( 1 − η ) v ) .
Hence
∫ x ∞ u s − 3 e − u d u x s − 3 e − x ≤ ∫ 0 ∞ e − η v d v = 1 η . \frac{\int_x^\infty u^{s-3}e^{-u}\,\mathrm{d}u}{x^{s-3}e^{-x}} \le\int_0^\infty e^{-\eta v}\,\mathrm{d}v = \frac{1}{\eta}. x s − 3 e − x ∫ x ∞ u s − 3 e − u d u ≤ ∫ 0 ∞ e − η v d v = η 1 .
Substituting this remainder bound into the expansion of Γ ( s , x ) \Gamma(s,x) Γ ( s , x ) gives
Γ ( s , x ) = x s − 1 e − x [ 1 + s − 1 x + O η ( ( s + 1 ) 2 x 2 ) ] , \Gamma(s,x)=x^{s-1}e^{-x}\left[1+\frac{s-1}{x}+O_\eta\left(\frac{(s+1)^2}{x^2}\right)\right], Γ ( s , x ) = x s − 1 e − x [ 1 + x s − 1 + O η ( x 2 ( s + 1 ) 2 ) ] ,
uniformly in the stated regime. Dividing by Γ ( s ) \Gamma(s) Γ ( s ) and substituting s = k / 2 s=k/2 s = k /2 , x = t / 2 x=t/2 x = t /2 , we obtain
F ‾ k ( t ) = ( t / 2 ) k / 2 − 1 e − t / 2 Γ ( k / 2 ) [ 1 + k − 2 t + O η ( ( k + 1 ) 2 t 2 ) ] . \overline{F}_k(t)=\frac{(t/2)^{k/2-1}e^{-t/2}}{\Gamma(k/2)}\left[1+\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right)\right]. F k ( t ) = Γ ( k /2 ) ( t /2 ) k /2 − 1 e − t /2 [ 1 + t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ] .
This proves (21) .
Taking logarithms of (21) ,
log F ‾ k ( t ) = k − 2 2 log t − t 2 − k − 2 2 log 2 − log Γ ( k / 2 ) + log [ 1 + k − 2 t + O η ( ( k + 1 ) 2 t 2 ) ] . \log\overline{F}_k(t)=\frac{k-2}{2}\log t-\frac{t}{2}-\frac{k-2}{2}\log2-\log\Gamma(k/2)+\log\left[1+\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right)\right]. log F k ( t ) = 2 k − 2 log t − 2 t − 2 k − 2 log 2 − log Γ ( k /2 ) + log [ 1 + t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ] .
Multiplying by − 2 -2 − 2 yields
G k ( t ) = t − ( k − 2 ) log t + ( k − 2 ) log 2 + 2 log Γ ( k / 2 ) − 2 log [ 1 + k − 2 t + O η ( ( k + 1 ) 2 t 2 ) ] . G_k(t)=t-(k-2)\log t+(k-2)\log2+2\log\Gamma(k/2)-2\log\left[1+\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right)\right]. G k ( t ) = t − ( k − 2 ) log t + ( k − 2 ) log 2 + 2 log Γ ( k /2 ) − 2 log [ 1 + t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ] .
Since
c k = ( k − 2 ) log 2 + 2 log Γ ( k / 2 ) , c_k=(k-2)\log2+2\log\Gamma(k/2), c k = ( k − 2 ) log 2 + 2 log Γ ( k /2 ) ,
this proves (22) –(23) . If k / t = o ( 1 ) k/t=o(1) k / t = o ( 1 ) , then the logarithm may be expanded as log ( 1 + u ) = u + O ( u 2 ) \log(1+u)=u+O(u^2) log ( 1 + u ) = u + O ( u 2 ) , giving (24) .
It remains to prove the derivative expansions. We use the hazard representation rather than differentiating the remainder in (21) . The chi-squared density is
f k ( t ) = 1 2 k / 2 Γ ( k / 2 ) t k / 2 − 1 e − t / 2 . f_k(t)=\frac{1}{2^{k/2}\Gamma(k/2)}t^{k/2-1}e^{-t/2}. f k ( t ) = 2 k /2 Γ ( k /2 ) 1 t k /2 − 1 e − t /2 .
Since F ‾ k ′ ( t ) = − f k ( t ) \overline{F}_k'(t)=-f_k(t) F k ′ ( t ) = − f k ( t ) ,
G k ′ ( t ) = − 2 F ‾ k ′ ( t ) F ‾ k ( t ) = 2 f k ( t ) F ‾ k ( t ) . G_k'(t)=-2\frac{\overline{F}_k'(t)}{\overline{F}_k(t)}=2\frac{f_k(t)}{\overline{F}_k(t)}. G k ′ ( t ) = − 2 F k ( t ) F k ′ ( t ) = 2 F k ( t ) f k ( t ) .
But (21) is equivalently
F ‾ k ( t ) = 2 f k ( t ) [ 1 + k − 2 t + O η ( ( k + 1 ) 2 t 2 ) ] . \overline{F}_k(t)=2f_k(t)\left[1+\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right)\right]. F k ( t ) = 2 f k ( t ) [ 1 + t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ] .
Therefore
G k ′ ( t ) = [ 1 + k − 2 t + O η ( ( k + 1 ) 2 t 2 ) ] − 1 . G_k'(t)=\left[1+\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right)\right]^{-1}. G k ′ ( t ) = [ 1 + t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ] − 1 .
Expanding the reciprocal gives
G k ′ ( t ) = 1 − k − 2 t + O η ( ( k + 1 ) 2 t 2 ) , G_k'(t)=1-\frac{k-2}{t}+O_\eta\left(\frac{(k+1)^2}{t^2}\right), G k ′ ( t ) = 1 − t k − 2 + O η ( t 2 ( k + 1 ) 2 ) ,
which proves (25) .
For the second derivative, set a = ( k − 2 ) / 2 a=(k-2)/2 a = ( k − 2 ) /2 and use the exact integral
H k ( t ) : = F ‾ k ( t ) 2 f k ( t ) = 1 2 ∫ 0 ∞ ( 1 + v t ) a e − v / 2 d v . H_k(t):=\frac{\overline{F}_k(t)}{2f_k(t)}=\frac{1}{2}\int_0^\infty\left(1+\frac{v}{t}\right)^a e^{-v/2}\,\mathrm{d}v. H k ( t ) := 2 f k ( t ) F k ( t ) = 2 1 ∫ 0 ∞ ( 1 + t v ) a e − v /2 d v .
In the stated regime this integral is bounded above and below by positive constants depending only on η \eta η , and H k ( t ) = 1 + O η ( ( k + 1 ) / t ) H_k(t)=1+O_\eta((k+1)/t) H k ( t ) = 1 + O η (( k + 1 ) / t ) . Differentiation under the integral is justified by an exponentially decaying dominating function, because a / t ≤ ( 1 − η ) / 2 a/t\le(1-\eta)/2 a / t ≤ ( 1 − η ) /2 . Consequently,
H k ′ ( t ) = − a 2 t 2 ∫ 0 ∞ v ( 1 + v / t ) a − 1 e − v / 2 d v = − k − 2 t 2 + O η ( ( k + 1 ) 2 t 3 ) . H_k'(t)=-\frac{a}{2t^2}\int_0^\infty v(1+v/t)^{a-1}e^{-v/2}\,dv=-\frac{k-2}{t^2}+O_\eta\left(\frac{(k+1)^2}{t^3}\right). H k ′ ( t ) = − 2 t 2 a ∫ 0 ∞ v ( 1 + v / t ) a − 1 e − v /2 d v = − t 2 k − 2 + O η ( t 3 ( k + 1 ) 2 ) .
For the remainder, apply the mean value theorem to ( 1 + v / t ) a − 1 − 1 (1+v/t)^{a-1}-1 ( 1 + v / t ) a − 1 − 1 and integrate the bound ∣ a − 1 ∣ ( v / t ) exp ( ( a − 1 ) + v / t ) |a-1|(v/t)\exp((a-1)_+v/t) ∣ a − 1∣ ( v / t ) exp (( a − 1 ) + v / t ) . Since G k ′ = H k − 1 G_k'=H_k^{-1} G k ′ = H k − 1 , it follows that
G k ′ ′ ( t ) = − H k ′ ( t ) H k ( t ) − 2 = k − 2 t 2 + O η ( ( k + 1 ) 2 t 3 ) , G_k''(t)=-H_k'(t)H_k(t)^{-2}=\frac{k-2}{t^2}+O_\eta\left(\frac{(k+1)^2}{t^3}\right), G k ′′ ( t ) = − H k ′ ( t ) H k ( t ) − 2 = t 2 k − 2 + O η ( t 3 ( k + 1 ) 2 ) ,
proving (26) .
Finally, Stirling’s formula gives
log Γ ( z ) = z log z − z − 1 2 log z + O ( 1 ) , z → ∞ . \log\Gamma(z)=z\log z-z-\frac{1}{2}\log z+O(1),\qquad z\to\infty. log Γ ( z ) = z log z − z − 2 1 log z + O ( 1 ) , z → ∞.
Taking z = k / 2 z=k/2 z = k /2 ,
2 log Γ ( k / 2 ) = k log ( k / 2 ) − k − log ( k / 2 ) + O ( 1 ) . 2\log\Gamma(k/2)=k\log(k/2)-k-\log(k/2)+O(1). 2 log Γ ( k /2 ) = k log ( k /2 ) − k − log ( k /2 ) + O ( 1 ) .
Thus
2 log Γ ( k / 2 ) = k log k − k log 2 − k − log k + O ( 1 ) . 2\log\Gamma(k/2)=k\log k-k\log2-k-\log k+O(1). 2 log Γ ( k /2 ) = k log k − k log 2 − k − log k + O ( 1 ) .
Adding ( k − 2 ) log 2 = k log 2 + O ( 1 ) (k-2)\log2=k\log2+O(1) ( k − 2 ) log 2 = k log 2 + O ( 1 ) yields
c k = k log k − k − log k + O ( 1 ) , c_k=k\log k-k-\log k+O(1), c k = k log k − k − log k + O ( 1 ) ,
as claimed.
Lemma 4 (Gaussian moderate-deviation bound). Let Z ∼ N ( 0 , 1 ) Z\sim\mathcal{N}(0,1) Z ∼ N ( 0 , 1 ) and x p → ∞ x_p\to\infty x p → ∞ . Then
− log P ( Z ≥ x p ) = x p 2 2 + log ( x p 2 π ) + O ( x p − 2 ) . -\log\mathbb{P}(Z\ge x_p)=\frac{x_p^2}{2}+\log(x_p\sqrt{2\pi})+O(x_p^{-2}). − log P ( Z ≥ x p ) = 2 x p 2 + log ( x p 2 π ) + O ( x p − 2 ) . In particular, if x p 2 / ( 2 log p ) → ℓ ∈ [ 0 , ∞ ) x_p^2/(2\log p)\to\ell\in[0,\infty) x p 2 / ( 2 log p ) → ℓ ∈ [ 0 , ∞ ) , then P ( Z ≥ x p ) = p − ℓ + o ( 1 ) \mathbb{P}(Z\ge x_p)=p^{-\ell+o(1)} P ( Z ≥ x p ) = p − ℓ + o ( 1 ) .
The proof is simply Mills’ ratio.
ANOVA F-statistic and reduction to the chi-square numerator
We derive the exact distribution of the one-way ANOVA F-statistic under the Gaussian model and explain why, on the moderate-deviation scale used in Theorem 7 , it suffices to analyze the noncentral chi-square numerator.
Let
k : = C − 1 , m : = n − C . k:=C-1,\qquad m:=n-C. k := C − 1 , m := n − C .
For feature j j j , define
T j : = S S b e t w e e n ( j ) σ 2 , U j : = S S w i t h i n ( j ) σ 2 . T_j:=\frac{\mathrm{SS}_{\mathrm{between}}(j)}{\sigma^2},\qquad U_j:=\frac{\mathrm{SS}_{\mathrm{within}}(j)}{\sigma^2}. T j := σ 2 SS between ( j ) , U j := σ 2 SS within ( j ) .
Thus
f j = T j / k U j / m . f_j=\frac{T_j/k}{U_j/m}. f j = U j / m T j / k .
Lemma 5 (Exact ANOVA distribution). Under model (10) , for each j ∈ [ p ] j\in[p] j ∈ [ p ] ,
T j ∼ χ k 2 ( λ j ) , U j ∼ χ m 2 , T j ⊥ U j , T_j\sim\chi_k^2(\lambda_j),\qquad U_j\sim\chi_m^2,\qquad T_j\perp U_j, T j ∼ χ k 2 ( λ j ) , U j ∼ χ m 2 , T j ⊥ U j , where
λ j = n c σ 2 μ ( j ) ⊤ P μ ( j ) , μ ( j ) : = ( μ 1 ( j ) , … , μ C ( j ) ) T . \lambda_j=\frac{n_c}{\sigma^2}\mu^{(j)\top}P\mu^{(j)},\qquad\mu^{(j)}:=(\mu_1^{(j)},\ldots,\mu_C^{(j)})^\mathsf{T}. λ j = σ 2 n c μ ( j ) ⊤ P μ ( j ) , μ ( j ) := ( μ 1 ( j ) , … , μ C ( j ) ) T . Consequently,
f j ∼ F k , m ( λ j ) . f_j\sim F_{k,m}(\lambda_j). f j ∼ F k , m ( λ j ) . For j ∉ J j\notin\mathcal{J} j ∈ / J , λ j = 0 \lambda_j=0 λ j = 0 , so f j ∼ F k , m f_j\sim F_{k,m} f j ∼ F k , m and the F-test p-value is uniform under H 0 ( j ) H_0^{(j)} H 0 ( j ) . For j ∈ J j\in\mathcal{J} j ∈ J , under the spherical homogeneous calibration (17) ,
λ j = 2 r log p . \lambda_j=2r\log p. λ j = 2 r log p .
Proof. The vector of class sample means at feature j j j satisfies
μ ^ ⋅ , j = ( μ ^ 1 , j , … , μ ^ C , j ) T ∼ N ( μ ( j ) , σ 2 n c I C ) . \hat{\mu}_{\cdot,j}=(\hat{\mu}_{1,j},\ldots,\hat{\mu}_{C,j})^{\mathsf{T}}\sim\mathcal{N}\left(\mu^{(j)},\frac{\sigma^2}{n_c}I_C\right). μ ^ ⋅ , j = ( μ ^ 1 , j , … , μ ^ C , j ) T ∼ N ( μ ( j ) , n c σ 2 I C ) .
Since P P P is the orthogonal projection onto 1 ⊥ 1^\perp 1 ⊥ ,
T j = n c σ 2 μ ^ ⋅ , j T P μ ^ ⋅ , j T_j=\frac{n_c}{\sigma^2}\hat{\mu}_{\cdot,j}^{\mathsf{T}}P\hat{\mu}_{\cdot,j} T j = σ 2 n c μ ^ ⋅ , j T P μ ^ ⋅ , j
is a noncentral chi-square random variable with k = C − 1 k=C-1 k = C − 1 degrees of freedom and non-centrality
λ j = n c σ 2 μ ( j ) T P μ ( j ) . \lambda_j=\frac{n_c}{\sigma^2}\mu^{(j)\mathsf{T}}P\mu^{(j)}. λ j = σ 2 n c μ ( j ) T P μ ( j ) .
The within-class residual sum of squares is independent of the class sample means in the Gaussian one-way ANOVA model, and
U j = S S w i t h i n ( j ) σ 2 ∼ χ n − C 2 . U_j=\frac{\mathrm{SS}_{\mathrm{within}}(j)}{\sigma^2}\sim\chi^2_{n-C}. U j = σ 2 SS within ( j ) ∼ χ n − C 2 .
Therefore T j ⊥ U j T_j\perp U_j T j ⊥ U j , and
f j = T j / k U j / m ∼ F k , m ( λ j ) . f_j=\frac{T_j/k}{U_j/m}\sim F_{k,m}(\lambda_j). f j = U j / m T j / k ∼ F k , m ( λ j ) .
Finally, if j ∈ J j\in\mathcal{J} j ∈ J , then by (17) ,
λ j = 2 r log p . \lambda_j=2r\log p. λ j = 2 r log p .
If j ∉ J j\notin\mathcal{J} j ∈ / J , then P μ ( j ) = 0 P\mu^{(j)}=0 P μ ( j ) = 0 , so λ j = 0 \lambda_j=0 λ j = 0 .
Lemma 6 (Reduction from F p-values to the chi-square numerator). Let π j F \pi_j^F π j F be the ANOVA F F F -test p p p -value at the feature j j j , as defined in (7) and let
π j χ = P { χ k 2 ≥ T j } \pi_j^\chi=\mathbb{P}\{\chi_k^2\geq T_j\} π j χ = P { χ k 2 ≥ T j } be the oracle chi-square numerator p p p -value. Suppose
log p = o ( m ) , m = n − C . \log p=o(m),\qquad m=n-C. log p = o ( m ) , m = n − C . Assume also k / ( 2 log p ) → s ≥ 0 k/(2\log p)\to s\geq0 k / ( 2 log p ) → s ≥ 0 , λ p / ( 2 log p ) → r > 0 \lambda_p/(2\log p)\to r>0 λ p / ( 2 log p ) → r > 0 , and use the continuous exponent Ψ r , s \Psi_{r,s} Ψ r , s derived directly in Section E of the Supplementary Material. If, for q q q in a compact subset of ( 0 , 1 ) (0,1) ( 0 , 1 ) ,
P ( π j χ ≤ p − q ∣ j ∈ J ) = p − Ψ p ( q ) + o ( 1 ) \mathbb{P}(\pi_j^\chi\leq p^{-q}\mid j\in\mathcal{J})=p^{-\Psi_p(q)+o(1)} P ( π j χ ≤ p − q ∣ j ∈ J ) = p − Ψ p ( q ) + o ( 1 ) uniformly in q q q , then
P ( π j F ≤ p − q ∣ j ∈ J ) = p − Ψ p ( q ) + o ( 1 ) \mathbb{P}(\pi_j^F\leq p^{-q}\mid j\in\mathcal{J})=p^{-\Psi_p(q)+o(1)} P ( π j F ≤ p − q ∣ j ∈ J ) = p − Ψ p ( q ) + o ( 1 ) uniformly in q q q .
Proof. Write
f j = T j / k R j / m , R j ∼ χ m 2 , R j ⊥ T j . f_j=\frac{T_j/k}{R_j/m},\qquad R_j\sim\chi_m^2,\qquad R_j\perp T_j. f j = R j / m T j / k , R j ∼ χ m 2 , R j ⊥ T j .
Put L = log p L=\log p L = log p and η p = ( L / m ) 1 / 4 \eta_p=(L/m)^{1/4} η p = ( L / m ) 1/4 , so that η p → 0 \eta_p\to0 η p → 0 . The chi-square concentration inequality gives
a p : = P { ∣ R j / m − 1 ∣ > η p } ≤ 2 exp { − c η p 2 m } = 2 exp { − c m L } = p − ω ( 1 ) . (28) a_p:=\mathbb{P}\{|R_j/m-1|>\eta_p\}\leq2\exp\{-c\eta_p^2m\}=2\exp\{-c\sqrt{mL}\}=p^{-\omega(1)}. \tag*{(28)} a p := P { ∣ R j / m − 1∣ > η p } ≤ 2 exp { − c η p 2 m } = 2 exp { − c m L } = p − ω ( 1 ) . (28)
On the event ∣ R j / m − 1 ∣ ≤ η p |R_j/m-1|\leq\eta_p ∣ R j / m − 1∣ ≤ η p ,
{ T j ≥ 2 L x ( 1 + η p ) } ⊆ { k f j ≥ 2 L x } ⊆ { T j ≥ 2 L x ( 1 − η p ) } . \{T_j\geq2Lx(1+\eta_p)\}\subseteq\{kf_j\geq2Lx\}\subseteq\{T_j\geq2Lx(1-\eta_p)\}. { T j ≥ 2 Lx ( 1 + η p )} ⊆ { k f j ≥ 2 Lx } ⊆ { T j ≥ 2 Lx ( 1 − η p )} .
Adding the exceptional denominator event gives the corresponding probability bounds. The central and noncentral numerator rates derived directly in Section E of the Supplementary Material are continuous in x x x , and the moving thresholds converge to x x x , so both bounds have the same exponent uniformly on compact q q q -intervals bounded away from zero. The additive error a p a_p a p is negligible compared with every fixed polynomial tail. Applying the same bracketing to the central quantiles transfers the numerator quantile to the central-F F F quantile and proves the claimed uniform expansion.
Moderate-deviation exponent of ANOVA p-values
For x ≥ 0 x \ge0 x ≥ 0 , define
J r , s ( x ) = sup 0 ≤ θ < 1 { θ x + s log ( 1 − θ ) − r θ 1 − θ } . (29) J_{r,s}(x)=\sup_{0\le\theta<1}\left\{\theta x+s\log(1-\theta)-\frac{r\theta}{1-\theta}\right\}. \tag*{(29)} J r , s ( x ) = 0 ≤ θ < 1 sup { θ x + s log ( 1 − θ ) − 1 − θ r θ } . (29)
This upper-tail rate equals zero for x ≤ s + r x\le s+r x ≤ s + r . For x > s + r x>s+r x > s + r , put d = s 2 + 4 r x d=\sqrt{s^2+4rx} d = s 2 + 4 r x and y = 2 x / ( s + d ) > 1 y=2x/(s+d)>1 y = 2 x / ( s + d ) > 1 ; then
J r , s ( x ) = x + r − d − s log y . (30) J_{r,s}(x)=x+r-d-s\log y. \tag*{(30)} J r , s ( x ) = x + r − d − s log y . (30)
For s = 0 s=0 s = 0 , this is ( x − r ) 2 (\sqrt{x}-\sqrt{r})^2 ( x − r ) 2 . For s > 0 s>0 s > 0 , let g s ( x ) = x − s − s log ( x / s ) g_s(x)=x-s-s\log(x/s) g s ( x ) = x − s − s log ( x / s ) on x ≥ s x\ge s x ≥ s , and let x s ( q ) x_s(q) x s ( q ) be its increasing inverse; set x 0 ( q ) = q x_0(q)=q x 0 ( q ) = q . Write L = log p L=\log p L = log p . The p-value exponent is Ψ r , s ( q ) = J r , s ( x s ( q ) ) \Psi_{r,s}(q)=J_{r,s}(x_s(q)) Ψ r , s ( q ) = J r , s ( x s ( q )) .
Theorem 7 (Uniform p-value tail exponent). Suppose k / ( 2 L ) → s ≥ 0 k/(2L)\to s\ge0 k / ( 2 L ) → s ≥ 0 , λ p / ( 2 L ) → r > 0 \lambda_p/(2L)\to r>0 λ p / ( 2 L ) → r > 0 , and m / L → ∞ m/L\to\infty m / L → ∞ , with integer k , m ≥ 1 k,m\ge1 k , m ≥ 1 . Let T ∼ χ k 2 ( λ p ) T\sim\chi_k^2(\lambda_p) T ∼ χ k 2 ( λ p ) and R ∼ χ m 2 R\sim\chi_m^2 R ∼ χ m 2 be independent. If π \pi π is the central-F k , m F_{k,m} F k , m upper-tail p-value of ( T / k ) / ( R / m ) (T/k)/(R/m) ( T / k ) / ( R / m ) , then, for every fixed Q < ∞ Q<\infty Q < ∞ ,
P ( π ≤ p − q ) = p − Ψ p ( q ) + o ( 1 ) , Ψ p ( q ) : = Ψ r , s ( q ) , uniformly for q ∈ [ 0 , Q ] . (31) \mathbb{P}(\pi\le p^{-q})=p^{-\Psi_p(q)+o(1)},\qquad\Psi_p(q):=\Psi_{r,s}(q),\qquad\text{uniformly for }q\in[0,Q]. \tag*{(31)} P ( π ≤ p − q ) = p − Ψ p ( q ) + o ( 1 ) , Ψ p ( q ) := Ψ r , s ( q ) , uniformly for q ∈ [ 0 , Q ] . (31) The same conclusion holds for the numerator p-value π χ = P ( χ k 2 ≥ T ) \pi^\chi=\mathbb{P}(\chi_k^2\ge T) π χ = P ( χ k 2 ≥ T ) .
For later use, define the boundary exponent (the HC growth exponent under null-variance normalization)
E p ( q ) : = 1 2 − β + q 2 − Ψ p ( q ) . (32) E_p(q):=\frac{1}{2}-\beta+\frac{q}{2}-\Psi_p(q). \tag*{(32)} E p ( q ) := 2 1 − β + 2 q − Ψ p ( q ) . (32)
Noncentral numerator tails
Let W p = T / ( 2 L ) W_p=T/(2L) W p = T / ( 2 L ) . For θ < 1 \theta<1 θ < 1 ,
Λ p ( θ ) : = L − 1 log E e L θ W p = − k 2 L log ( 1 − θ ) + λ p 2 L θ 1 − θ ⟶ Λ ( θ ) : = − s log ( 1 − θ ) + r θ 1 − θ . \Lambda_p(\theta):=L^{-1}\log\mathbb{E}e^{L\theta W_p}=-\frac{k}{2L}\log(1-\theta)+\frac{\lambda_p}{2L}\frac{\theta}{1-\theta}\longrightarrow\Lambda(\theta):=-s\log(1-\theta)+\frac{r\theta}{1-\theta}. Λ p ( θ ) := L − 1 log E e L θ W p = − 2 L k log ( 1 − θ ) + 2 L λ p 1 − θ θ ⟶ Λ ( θ ) := − s log ( 1 − θ ) + 1 − θ r θ .
The first two derivatives converge at each fixed θ < 1 \theta<1 θ < 1 . Chernoff’s bound gives
lim inf p − L − 1 log P ( W p ≥ x ) ≥ J r , s ( x ) . \liminf_{p}-L^{-1}\log\mathbb{P}(W_p\ge x)\ge J_{r,s}(x). p lim inf − L − 1 log P ( W p ≥ x ) ≥ J r , s ( x ) .
For the matching lower bound when x > s + r x>s+r x > s + r , choose ϵ > 0 \epsilon>0 ϵ > 0 and the unique θ ϵ ∈ ( 0 , 1 ) \theta_\epsilon\in(0,1) θ ϵ ∈ ( 0 , 1 ) satisfying Λ ′ ( θ ϵ ) = x + ϵ \Lambda'(\theta_\epsilon)=x+\epsilon Λ ′ ( θ ϵ ) = x + ϵ ; existence follows from Λ ′ ( 0 ) = s + r \Lambda'(0)=s+r Λ ′ ( 0 ) = s + r and Λ ′ ( θ ) ↑ ∞ \Lambda'(\theta)\uparrow\infty Λ ′ ( θ ) ↑ ∞ . Tilt the law by
d P θ ϵ d P = exp { L θ ϵ W p − L Λ p ( θ ϵ ) } . \frac{\mathrm{d}\mathbb{P}_{\theta_\epsilon}}{\mathrm{d}\mathbb{P}}=\exp\{L\theta_\epsilon W_p-L\Lambda_p(\theta_\epsilon)\}. d P d P θ ϵ = exp { L θ ϵ W p − L Λ p ( θ ϵ )} .
Under this law, the mean of W p W_p W p tends to x + ϵ x+\epsilon x + ϵ and its variance is Λ p ′ ′ ( θ ϵ ) / L → 0 \Lambda_p''(\theta_\epsilon)/L\to0 Λ p ′′ ( θ ϵ ) / L → 0 . Thus A ϵ = { x ≤ W p ≤ x + 2 ϵ } A_\epsilon=\{x\le W_p\le x+2\epsilon\} A ϵ = { x ≤ W p ≤ x + 2 ϵ } has tilted probability tending to one, and
P ( W p ≥ x ) ≥ e − L θ ϵ ( x + 2 ϵ ) + L Λ p ( θ ϵ ) P θ ϵ ( A ϵ ) . \mathbb{P}(W_p\ge x)\ge e^{-L\theta_\epsilon(x+2\epsilon)+L\Lambda_p(\theta_\epsilon)}\mathbb{P}_{\theta_\epsilon}(A_\epsilon). P ( W p ≥ x ) ≥ e − L θ ϵ ( x + 2 ϵ ) + L Λ p ( θ ϵ ) P θ ϵ ( A ϵ ) .
Taking logarithms, then p → ∞ p\to\infty p → ∞ and ϵ → 0 \epsilon\to0 ϵ → 0 , proves the matching exponent. Below s + r s+r s + r , W p → s + r W_p\to s+r W p → s + r in probability because its variance is O ( L − 1 ) O(L^{-1}) O ( L − 1 ) , so the upper-tail exponent is zero. At x = s + r x=s+r x = s + r , bound the tail below by its value at x + ϵ x+\epsilon x + ϵ and let ϵ → 0 \epsilon\to0 ϵ → 0 . This proves the rate at every x ≥ 0 x\ge0 x ≥ 0 .
The optimizer above the mean satisfies x = s / ( 1 − θ ) + r / ( 1 − θ ) 2 x=s/(1-\theta)+r/(1-\theta)^2 x = s / ( 1 − θ ) + r / ( 1 − θ ) 2 . Writing y = ( 1 − θ ) − 1 y=(1-\theta)^{-1} y = ( 1 − θ ) − 1 gives x = s y + r y 2 x=sy+ry^2 x = sy + r y 2 , whose positive root is 2 x / ( s + s 2 + 4 r x ) 2x/(s+\sqrt{s^2+4rx}) 2 x / ( s + s 2 + 4 r x ) . Substitution proves (30) . These formulas also show continuity of the rate.
Central numerator tails and quantiles
For T 0 ∼ χ k 2 T_0\sim\chi_k^2 T 0 ∼ χ k 2 and s > 0 s>0 s > 0 , the preceding argument with r = 0 r=0 r = 0 gives upper-tail rate zero for x ≤ s x\le s x ≤ s and g s ( x ) g_s(x) g s ( x ) for x > s x>s x > s . When s = 0 s=0 s = 0 , for any fixed x > 0 x>0 x > 0 and 0 < θ < 1 0<\theta<1 0 < θ < 1 , Chernoff’s bound gives
lim inf p − L − 1 log P ( T 0 ≥ 2 L x ) ≥ θ x . \liminf_{p}-L^{-1}\log\mathbb{P}(T_0\ge2Lx)\ge\theta x. p lim inf − L − 1 log P ( T 0 ≥ 2 Lx ) ≥ θ x .
Letting θ ↑ 1 \theta\uparrow1 θ ↑ 1 gives the lower bound x x x on the exponent. Since k ≥ 1 k\ge1 k ≥ 1 , T 0 T_0 T 0 stochastically dominates a squared standard normal, whose tail at 2 L x 2Lx 2 Lx is p − x + o ( 1 ) p^{-x+o(1)} p − x + o ( 1 ) . This gives the opposite bound. Thus the rate is x = g 0 ( x ) x=g_0(x) x = g 0 ( x ) in this case.
For every fixed q > 0 q>0 q > 0 , the central chi-square upper quantile at probability p − q p^{-q} p − q , divided by 2 L 2L 2 L , tends to x s ( q ) x_s(q) x s ( q ) . Indeed, evaluate the tail at x s ( q ) − ε x_s(q)-\varepsilon x s ( q ) − ε and x s ( q ) + ε x_s(q)+\varepsilon x s ( q ) + ε , choosing the lower point above s s s when s > 0 s>0 s > 0 ; strict monotonicity of g s g_s g s brackets the quantile. Applying the noncentral rate to these same brackets proves the numerator p-value exponent for fixed q > 0 q>0 q > 0 .
Transfer to exact F p-values
Let D = R / m D=R/m D = R / m , η p = ( L / m ) 1 / 4 → 0 \eta_p=(L/m)^{1/4}\to0 η p = ( L / m ) 1/4 → 0 , and a p = P ( ∣ D − 1 ∣ > η p ) a_p=\mathbb{P}(|D-1|>\eta_p) a p = P ( ∣ D − 1∣ > η p ) . By (28) ,
a p ≤ 2 e − c m L = p − ω ( 1 ) . a_p\le2e^{-c\sqrt{mL}}=p^{-\omega(1)}. a p ≤ 2 e − c m L = p − ω ( 1 ) .
For every fixed x > 0 x>0 x > 0 , the variable V = T / D = k F V=T/D=kF V = T / D = k F satisfies
P ( T ≥ 2 L x ( 1 + η p ) ) − a p ≤ P ( V ≥ 2 L x ) ≤ P ( T ≥ 2 L x ( 1 − η p ) ) + a p . \mathbb{P}\bigl(T\ge2Lx(1+\eta_p)\bigr)-a_p\le\mathbb{P}(V\ge2Lx)\le\mathbb{P}\bigl(T\ge2Lx(1-\eta_p)\bigr)+a_p. P ( T ≥ 2 Lx ( 1 + η p ) ) − a p ≤ P ( V ≥ 2 Lx ) ≤ P ( T ≥ 2 Lx ( 1 − η p ) ) + a p .
The moving numerator thresholds have the same rate as x x x , by bracketing them between fixed x ± ε x\pm\varepsilon x ± ε and using continuity. The additive error is negligible relative to every fixed polynomial tail. These statements hold for both central and noncentral numerators. Consequently, if c p ( q ) c_p(q) c p ( q ) is the central-F k , m F_{k,m} F k , m upper quantile at p − q p^{-q} p − q , then k c p ( q ) / ( 2 L ) → x s ( q ) kc_p(q)/(2L)\to x_s(q) k c p ( q ) / ( 2 L ) → x s ( q ) for each fixed q > 0 q>0 q > 0 . Applying the noncentral bounds at this moving quantile yields (31) pointwise for q > 0 q>0 q > 0 . At q = 0 q=0 q = 0 , the event is { π ≤ 1 } \{\pi\le1\} { π ≤ 1 } , with probability one, so its exponent is zero. We do not claim convergence of the scaled quantile to x s ( 0 ) x_s(0) x s ( 0 ) at q = 0 q=0 q = 0 when s > 0 s>0 s > 0 .
Uniformity and interpretation
The functions f p ( q ) = − L − 1 log P ( π ≤ p − q ) f_p(q)=-L^{-1}\log\mathbb{P}(\pi\le p^{-q}) f p ( q ) = − L − 1 log P ( π ≤ p − q ) are nondecreasing, and their pointwise limit Ψ r , s \Psi_{r,s} Ψ r , s is continuous and nondecreasing. On [ 0 , Q ] [0,Q] [ 0 , Q ] , choose a finite partition so that the oscillation of the limit on each subinterval is at most ε \varepsilon ε . Pointwise convergence at its endpoints and monotonicity bound ∣ f p − Ψ r , s ∣ |f_p-\Psi_{r,s}| ∣ f p − Ψ r , s ∣ by 2 ε 2\varepsilon 2 ε everywhere for all large p p p . This proves uniformity; the numerator argument is identical. All useful features have the same non-centrality, so feature-wise uniformity follows as well. This completes the proof of Theorem 7 .
In particular, for s > 0 s>0 s > 0 ,
Ψ r , s ( q ) = 0 ⟺ q ≤ g s ( s + r ) = r − s log ( 1 + r / s ) . \Psi_{r,s}(q)=0\quad\Longleftrightarrow\quad q\le g_s(s+r)=r-s\log(1+r/s). Ψ r , s ( q ) = 0 ⟺ q ≤ g s ( s + r ) = r − s log ( 1 + r / s ) .
Local Gaussian approximations can describe fluctuations near this location, but do not determine the full tail exponent at fixed q q q . The tail-equivalence condition in Kipnis [ [22 ] must be verified for a proposed shifted-square approximation; our direct calculation instead supplies the exact rate needed here.
Local expansion at the useful-feature mean
For s > 0 s>0 s > 0 , define
μ ˉ = r − s log ( 1 + r / s ) , ν ˉ 2 = ( r r + s ) 2 s + 2 r 2 μ ˉ . \bar{\mu}=r-s\log(1+r/s),\qquad\bar{\nu}^{2}=\left(\frac{r}{r+s}\right)^{2}\frac{s+2r}{2\bar{\mu}}. μ ˉ = r − s log ( 1 + r / s ) , ν ˉ 2 = ( r + s r ) 2 2 μ ˉ s + 2 r .
These parameters describe a local expansion, not the full polynomial-tail rate. Indeed, g s ′ ( s + r ) = r / ( s + r ) > 0 g_s'(s+r)=r/(s+r)>0 g s ′ ( s + r ) = r / ( s + r ) > 0 , so as q → μ ˉ q\to\bar{\mu} q → μ ˉ from above,
x s ( q ) − ( s + r ) = s + r r ( q − μ ˉ ) + O ( ( q − μ ˉ ) 2 ) . x_s(q)-(s+r)=\frac{s+r}{r}(q-\bar{\mu})+O((q-\bar{\mu})^2). x s ( q ) − ( s + r ) = r s + r ( q − μ ˉ ) + O (( q − μ ˉ ) 2 ) .
The cumulant function satisfies Λ ′ ′ ( 0 ) = s + 2 r \Lambda''(0)=s+2r Λ ′′ ( 0 ) = s + 2 r . Consequently,
J r , s ( s + r + h ) = h 2 2 ( s + 2 r ) + O ( h 3 ) , h → 0. J_{r,s}(s+r+h)=\frac{h^2}{2(s+2r)}+O(h^3),\qquad h\to0. J r , s ( s + r + h ) = 2 ( s + 2 r ) h 2 + O ( h 3 ) , h → 0.
and therefore
Ψ r , s ( q ) = ( s + r ) 2 2 r 2 ( s + 2 r ) ( q − μ ˉ ) 2 + O ( ( q − μ ˉ ) 3 ) = ( q − μ ˉ ) 2 ν ˉ 2 + O ( ( q − μ ˉ ) 3 ) . \Psi_{r,s}(q)=\frac{(s+r)^2}{2r^2(s+2r)}(q-\bar{\mu})^2+O((q-\bar{\mu})^3)=\frac{(\sqrt{q}-\sqrt{\bar{\mu}})^2}{\bar{\nu}^2}+O((q-\bar{\mu})^3). Ψ r , s ( q ) = 2 r 2 ( s + 2 r ) ( s + r ) 2 ( q − μ ˉ ) 2 + O (( q − μ ˉ ) 3 ) = ν ˉ 2 ( q − μ ˉ ) 2 + O (( q − μ ˉ ) 3 ) .
Below μ ˉ \bar{\mu} μ ˉ , both upper-tail expressions are zero when the positive part is used. The displayed expansion holds locally as q → μ ˉ q\to\bar{\mu} q → μ ˉ ; it does not justify replacing Ψ r , s \Psi_{r,s} Ψ r , s at other fixed thresholds.
Proof of Theorem 1 (Impossibility below the boundary)
We prove the impossibility result under the spherical homogeneous contrast model. Let
V = 1 ⊥ = { v ∈ R C : 1 ⊤ v = 0 } , P = I C − 1 C 11 ⊤ . \mathcal{V}=1^\perp=\{v\in\mathbb{R}^{C}:1^\top v=0\},\qquad P=I_C-\frac{1}{C}11^\top. V = 1 ⊥ = { v ∈ R C : 1 ⊤ v = 0 } , P = I C − C 1 1 1 ⊤ .
Each feature is randomly set as useful independently with probability
ϵ p : = ϵ = p − β , β ∈ ( 1 / 2 , 1 ) . \epsilon_p:=\epsilon=p^{-\beta},\qquad\beta\in(1/2,1). ϵ p := ϵ = p − β , β ∈ ( 1/2 , 1 ) .
If j ∉ J j\notin\mathcal{J} j ∈ / J , then μ ( j ) = 0 \mu^{(j)}=0 μ ( j ) = 0 . If j ∈ J j\in\mathcal{J} j ∈ J , then
μ ( j ) = a p U j , U j ∼ Unif { u ∈ V : ∥ u ∥ 2 = 1 } , \mu^{(j)}=a_pU_j,\qquad U_j\sim\operatorname{Unif}\{u\in\mathcal{V}:\lVert u\rVert_2=1\}, μ ( j ) = a p U j , U j ∼ Unif { u ∈ V : ∥ u ∥ 2 = 1 } ,
independently over j j j , where
a p = σ n c 2 r log p . a_p=\frac{\sigma}{\sqrt{n_c}}\sqrt{2r\log p}. a p = n c σ 2 r log p .
Thus every useful feature has ANOVA non-centrality
λ j = n c σ 2 μ ( j ) ⊤ P μ ( j ) = 2 r log p . \lambda_j=\frac{n_c}{\sigma^2}\mu^{(j)\top}P\mu^{(j)}=2r\log p. λ j = σ 2 n c μ ( j ) ⊤ P μ ( j ) = 2 r log p .
For feature j j j , define the normalized ANOVA statistic
T j = n c σ 2 μ ^ ⋅ , j ⊤ P μ ^ ⋅ , j , T_j=\frac{n_c}{\sigma^2}\hat{\mu}_{\cdot,j}^{\top}P\hat{\mu}_{\cdot,j}, T j = σ 2 n c μ ^ ⋅ , j ⊤ P μ ^ ⋅ , j ,
and its null-calibrated p-value
π j = P { χ C − 1 2 ≥ T j } . \pi_j=\mathbb{P}\{\chi^2_{C-1}\geq T_j\}. π j = P { χ C − 1 2 ≥ T j } .
Let
Q j = − log p π j . Q_j=-\log_p\pi_j. Q j = − log p π j .
By Theorem 7 , under a useful feature,
P s i g ( Q j ≥ q ) = p − Ψ p ( q ) + o ( 1 ) \mathbb{P}_{\mathrm{sig}}(Q_j\geq q)=p^{-\Psi_p(q)+o(1)} P sig ( Q j ≥ q ) = p − Ψ p ( q ) + o ( 1 )
uniformly on compact q q q -intervals, where
Ψ p ( q ) : = Ψ r , s ( q ) . \Psi_p(q):=\Psi_{r,s}(q). Ψ p ( q ) := Ψ r , s ( q ) .
Here we have used the equivalence between Q j ≥ q Q_j\geq q Q j ≥ q and − 2 log π j ≥ 2 q log p -2\log\pi_j\geq2q\log p − 2 log π j ≥ 2 q log p . Recall the boundary exponent from (32) ,
E p ( q ) = 1 2 − β + q 2 − Ψ p ( q ) . E_p(q)=\frac{1}{2}-\beta+\frac{q}{2}-\Psi_p(q). E p ( q ) = 2 1 − β + 2 q − Ψ p ( q ) .
For the exact exponent, the below-boundary assumption is equivalently that the positive-exponent gap is strict. Hence there exist constants η > 0 \eta>0 η > 0 and a > 0 a>0 a > 0 such that
sup 0 ≤ q ≤ 1 + η E p ( q ) ≤ − a (33) \sup_{0\leq q\leq1+\eta}E_p(q)\leq-a \tag*{(33)} 0 ≤ q ≤ 1 + η sup E p ( q ) ≤ − a (33)
for all sufficiently large p p p . We prove the result under the equivalent strict-below-boundary formulation (33) .
Let P 0 ( p ) P_0^{(p)} P 0 ( p ) and P 1 ( p ) P_1^{(p)} P 1 ( p ) denote the null and rare/weak alternative laws of the training data D n = { ( X i , Y i ) } i = 1 n \mathcal{D}_n=\{(X_i,Y_i)\}_{i=1}^n D n = {( X i , Y i ) } i = 1 n . The ancillary residual components have the same law under both models, so it is enough to control the likelihood ratio of the independent feature scores. We first prove
TV ( P 1 ( p ) , P 0 ( p ) ) → 0 \operatorname{TV}(P_1^{(p)},P_0^{(p)})\to0 TV ( P 1 ( p ) , P 0 ( p ) ) → 0
for this training experiment. The additional test-observation argument is given after the truncated-moment calculation.
Reduction to the ANOVA p-value experiment
For each feature j j j , define
W j = n c σ P μ ^ ⋅ , j ∈ V . W_j = \frac{\sqrt{n_c}}{\sigma}P\widehat{\mu}_{\cdot,j} \in\mathcal{V}. W j = σ n c P μ ⋅ , j ∈ V .
Under the null,
W j ∼ N V ( 0 , I V ) . W_j \sim N_{\mathcal{V}}(0,I_{\mathcal{V}}). W j ∼ N V ( 0 , I V ) .
Under a useful feature,
W j ∣ U j ∼ N V ( θ p U j , I V ) , θ p = 2 r log p , W_j \mid U_j \sim N_{\mathcal{V}}(\theta_pU_j,I_{\mathcal{V}}), \qquad\theta_p=\sqrt{2r\log p}, W j ∣ U j ∼ N V ( θ p U j , I V ) , θ p = 2 r log p ,
where
U j ∼ Unif { u ∈ V : ∥ u ∥ 2 = 1 } . U_j \sim\operatorname{Unif}\{u\in\mathcal{V}:\lVert u\rVert_2=1\}. U j ∼ Unif { u ∈ V : ∥ u ∥ 2 = 1 } .
The within-class residuals and the grand mean across classes have the same distribution under the null and alternative and are independent of W j W_j W j : the mean contrast lies in V \mathcal{V} V , and the Gaussian projections onto V \mathcal{V} V and its orthogonal complement are independent. Thus the feature-wise likelihood ratio depends only on W j W_j W j .
Under the spherical prior, the useful-feature density is
f 1 ( w ) = ∫ { u ∈ V : ∥ u ∥ 2 = 1 } ϕ V ( w − θ p u ) d σ ( u ) . f_1(w)=\int_{\{u\in\mathcal{V}:\lVert u\rVert_2=1\}}\phi_{\mathcal{V}}(w-\theta_pu)\,d\sigma(u). f 1 ( w ) = ∫ { u ∈ V : ∥ u ∥ 2 = 1 } ϕ V ( w − θ p u ) d σ ( u ) .
where d σ d\sigma d σ is the uniform probability measure on the unit sphere in V \mathcal{V} V . Since d σ d\sigma d σ is rotationally invariant, f 1 ( w ) f_1(w) f 1 ( w ) depends only on ∥ w ∥ 2 \lVert w\rVert_2 ∥ w ∥ 2 . The null density
f 0 ( w ) = ϕ V ( w ) f_0(w)=\phi_{\mathcal{V}}(w) f 0 ( w ) = ϕ V ( w )
also depends only on ∥ w ∥ 2 \lVert w\rVert_2 ∥ w ∥ 2 . Hence f 1 ( w ) / f 0 ( w ) f_1(w)/f_0(w) f 1 ( w ) / f 0 ( w ) depends only on ∥ w ∥ 2 \lVert w\rVert_2 ∥ w ∥ 2 . But
∥ W j ∥ 2 2 = n c σ 2 μ ^ ⋅ , j T P μ ^ ⋅ , j = T j . \lVert W_j\rVert_2^2=\frac{n_c}{\sigma^2}\widehat{\mu}_{\cdot,j}^{\mathsf T}P\widehat{\mu}_{\cdot,j}=T_j. ∥ W j ∥ 2 2 = σ 2 n c μ ⋅ , j T P μ ⋅ , j = T j .
Therefore the full likelihood ratio depends on feature j j j only through T j T_j T j , equivalently through π j \pi_j π j , equivalently through Q j = − log p π j Q_j=-\log_p\pi_j Q j = − log p π j . Thus we may work with the independent scores
Q 1 , … , Q p . Q_1,\ldots,Q_p. Q 1 , … , Q p .
One-feature likelihood ratios
Under the null, π j ∼ Unif ( 0 , 1 ) \pi_j\sim\operatorname{Unif}(0,1) π j ∼ Unif ( 0 , 1 ) . Hence
P 0 ( Q j ≥ q ) = p − q , \mathbb{P}_0(Q_j\ge q)=p^{-q}, P 0 ( Q j ≥ q ) = p − q ,
and the null density of Q j Q_j Q j is
h 0 ( q ) = ( log p ) p − q , q ≥ 0. h_0(q)=(\log p)p^{-q},\qquad q\ge0. h 0 ( q ) = ( log p ) p − q , q ≥ 0.
Let h s i g h_{\mathrm{sig}} h sig denote the density of Q j Q_j Q j conditional on j ∈ J j\in\mathcal{J} j ∈ J , and define
ℓ p ( q ) = h s i g ( q ) h 0 ( q ) . \ell_p(q)=\frac{h_{\mathrm{sig}}(q)}{h_0(q)}. ℓ p ( q ) = h 0 ( q ) h sig ( q ) .
This is the likelihood ratio of a useful feature versus a null feature at score q q q .
The rare/weak one-feature likelihood ratio is
L j ( q ) = 1 − ϵ p + ϵ p ℓ p ( q ) . L_j(q)=1-\epsilon_p+\epsilon_p\ell_p(q). L j ( q ) = 1 − ϵ p + ϵ p ℓ p ( q ) .
Since features are independent,
L p = d P 1 ( p ) d P 0 ( p ) = ∏ j = 1 p L j ( Q j ) . L_p=\frac{dP_1^{(p)}}{dP_0^{(p)}}=\prod_{j=1}^{p}L_j(Q_j). L p = d P 0 ( p ) d P 1 ( p ) = j = 1 ∏ p L j ( Q j ) .
A likelihood-ratio upper bound
We need a pointwise upper bound on ℓ p ( q ) \ell_p(q) ℓ p ( q ) . Let T ∼ χ k 2 T \sim\chi_k^2 T ∼ χ k 2 under the null and T ∼ χ k 2 ( λ p ) T \sim\chi_k^2(\lambda_p) T ∼ χ k 2 ( λ p ) under a useful feature, with k = C − 1 k=C-1 k = C − 1 and λ p = 2 r log p \lambda_p=2r\log p λ p = 2 r log p . Let f 0 f_0 f 0 and f 1 f_1 f 1 be their densities, and define
R p ( t ) = f 1 ( t ) f 0 ( t ) . R_p(t)=\frac{f_1(t)}{f_0(t)}. R p ( t ) = f 0 ( t ) f 1 ( t ) .
The noncentral chi-square density has the Poisson mixture representation
f 1 ( t ) = e − λ p / 2 ∑ m = 0 ∞ ( λ p / 2 ) m m ! f k + 2 m ( t ) . f_1(t)=e^{-\lambda_p/2}\sum_{m=0}^{\infty}\frac{(\lambda_p/2)^m}{m!}f_{k+2m}(t). f 1 ( t ) = e − λ p /2 m = 0 ∑ ∞ m ! ( λ p /2 ) m f k + 2 m ( t ) .
Moreover,
f k + 2 m ( t ) f k ( t ) = Γ ( k / 2 ) 2 m Γ ( k / 2 + m ) t m . \frac{f_{k+2m}(t)}{f_k(t)}=\frac{\Gamma(k/2)}{2^m\Gamma(k/2+m)}t^m. f k ( t ) f k + 2 m ( t ) = 2 m Γ ( k /2 + m ) Γ ( k /2 ) t m .
Therefore
R p ( t ) = e − λ p / 2 ∑ m = 0 ∞ a m t m . R_p(t)=e^{-\lambda_p/2}\sum_{m=0}^{\infty}a_m t^m. R p ( t ) = e − λ p /2 m = 0 ∑ ∞ a m t m .
where all coefficients satisfy a m ≥ 0 a_m\ge0 a m ≥ 0 . Hence R p ( t ) R_p(t) R p ( t ) is nondecreasing in t t t .
The map t ↦ Q = − log p S 0 ( t ) t\mapsto Q=-\log_p S_0(t) t ↦ Q = − log p S 0 ( t ) , where S 0 ( t ) = P ( χ k 2 ≥ t ) S_0(t)=\mathbb{P}(\chi_k^2\ge t) S 0 ( t ) = P ( χ k 2 ≥ t ) , is increasing. Therefore q ↦ ℓ p ( q ) q\mapsto\ell_p(q) q ↦ ℓ p ( q ) is nondecreasing. Hence, for any q q q ,
P s i g ( Q ≥ q ) = ∫ q ∞ ℓ p ( u ) h 0 ( u ) d u ≥ ℓ p ( q ) ∫ q ∞ h 0 ( u ) d u = ℓ p ( q ) P 0 ( Q ≥ q ) . \mathbb{P}_{\mathrm{sig}}(Q\ge q)=\int_q^\infty\ell_p(u)h_0(u)\,du
\ge\ell_p(q)\int_q^\infty h_0(u)\,du
=\ell_p(q)\mathbb{P}_0(Q\ge q). P sig ( Q ≥ q ) = ∫ q ∞ ℓ p ( u ) h 0 ( u ) d u ≥ ℓ p ( q ) ∫ q ∞ h 0 ( u ) d u = ℓ p ( q ) P 0 ( Q ≥ q ) .
Thus
ℓ p ( q ) ≤ P s i g ( Q ≥ q ) P 0 ( Q ≥ q ) . \ell_p(q)\le\frac{\mathbb{P}_{\mathrm{sig}}(Q\ge q)}{\mathbb{P}_0(Q\ge q)}. ℓ p ( q ) ≤ P 0 ( Q ≥ q ) P sig ( Q ≥ q ) .
Using Theorem 7 and the exact null tail,
P s i g ( Q ≥ q ) = p − Ψ p ( q ) + o ( 1 ) , P 0 ( Q ≥ q ) = p − q , \mathbb{P}_{\mathrm{sig}}(Q\ge q)=p^{-\Psi_p(q)+o(1)},\qquad\mathbb{P}_0(Q\ge q)=p^{-q}, P sig ( Q ≥ q ) = p − Ψ p ( q ) + o ( 1 ) , P 0 ( Q ≥ q ) = p − q ,
we obtain
ℓ p ( q ) ≤ p q − Ψ p ( q ) + o ( 1 ) . (34) \ell_p(q)\le p^{q-\Psi_p(q)+o(1)}. \tag*{(34)} ℓ p ( q ) ≤ p q − Ψ p ( q ) + o ( 1 ) . (34)
uniformly for q ∈ [ 0 , 1 + η ] q\in[0,1+\eta] q ∈ [ 0 , 1 + η ] .
Truncation
Define
A p = { max 1 ≤ j ≤ p Q j ≤ 1 + η } . A_p=\left\{\max_{1\le j\le p}Q_j\le1+\eta\right\}. A p = { 1 ≤ j ≤ p max Q j ≤ 1 + η } .
We first show that A p A_p A p is typical under both P 0 ( p ) P_0^{(p)} P 0 ( p ) and P 1 ( p ) P_1^{(p)} P 1 ( p ) .
Under the null,
P 0 ( Q j > 1 + η ) = p − ( 1 + η ) . \mathbb{P}_0(Q_j>1+\eta)=p^{-(1+\eta)}. P 0 ( Q j > 1 + η ) = p − ( 1 + η ) .
By the union bound,
P 0 ( A p c ) ≤ p ⋅ p − ( 1 + η ) = p − η → 0. \mathbb{P}_0(A_p^c)\le p\cdot p^{-(1+\eta)}=p^{-\eta}\to0. P 0 ( A p c ) ≤ p ⋅ p − ( 1 + η ) = p − η → 0.
Under the alternative,
P 1 ( Q j > 1 + η ) = ( 1 − ϵ p ) P 0 ( Q j > 1 + η ) + ϵ p P s i g ( Q j > 1 + η ) ≤ p − ( 1 + η ) + p − β − Ψ p ( 1 + η ) + o ( 1 ) . \mathbb{P}_1(Q_j>1+\eta)=(1-\epsilon_p)\mathbb{P}_0(Q_j>1+\eta)+\epsilon_p\mathbb{P}_{\mathrm{sig}}(Q_j>1+\eta)
\le p^{-(1+\eta)}+p^{-\beta-\Psi_p(1+\eta)+o(1)}. P 1 ( Q j > 1 + η ) = ( 1 − ϵ p ) P 0 ( Q j > 1 + η ) + ϵ p P sig ( Q j > 1 + η ) ≤ p − ( 1 + η ) + p − β − Ψ p ( 1 + η ) + o ( 1 ) .
Therefore,
P 1 ( A p c ) ≤ p − η + p 1 − β − Ψ p ( 1 + η ) + o ( 1 ) . \mathbb{P}_1(A_p^c)\le p^{-\eta}+p^{1-\beta-\Psi_p(1+\eta)+o(1)}. P 1 ( A p c ) ≤ p − η + p 1 − β − Ψ p ( 1 + η ) + o ( 1 ) .
Since
E p ( 1 + η ) = 1 − β + η 2 − Ψ p ( 1 + η ) , E_p(1+\eta)=1-\beta+\frac{\eta}{2}-\Psi_p(1+\eta), E p ( 1 + η ) = 1 − β + 2 η − Ψ p ( 1 + η ) ,
and by (33) E p ( 1 + η ) ≤ − a E_p(1+\eta)\le-a E p ( 1 + η ) ≤ − a , we have
1 − β − Ψ p ( 1 + η ) ≤ − a − η 2 < 0. 1-\beta-\Psi_p(1+\eta)\le-a-\frac{\eta}{2}<0. 1 − β − Ψ p ( 1 + η ) ≤ − a − 2 η < 0.
Thus
P 1 ( A p c ) → 0. \mathbb{P}_1(A_p^c)\to0. P 1 ( A p c ) → 0.
Equivalently, since L p = d P 1 ( p ) / d P 0 ( p ) L_p=\mathrm{d}P_1^{(p)}/\mathrm{d}P_0^{(p)} L p = d P 1 ( p ) / d P 0 ( p ) ,
E 0 [ L p 1 A p ] = P 1 ( A p ) → 1. (35) \mathbb{E}_0[L_p1_{A_p}]=\mathbb{P}_1(A_p)\to1. \tag*{(35)} E 0 [ L p 1 A p ] = P 1 ( A p ) → 1. (35)
Truncated second moment
Because
L p = ∏ j = 1 p L j ( Q j ) , A p = ⋂ j = 1 p { Q j ≤ 1 + η } , L_p=\prod_{j=1}^{p}L_j(Q_j),\qquad A_p=\bigcap_{j=1}^{p}\{Q_j\le1+\eta\}, L p = j = 1 ∏ p L j ( Q j ) , A p = j = 1 ⋂ p { Q j ≤ 1 + η } ,
we have, under P 0 ( p ) P_0^{(p)} P 0 ( p ) ,
E 0 [ L p 2 1 A p ] = ( E 0 [ L 1 ( Q ) 2 1 { Q ≤ 1 + η } ] ) p . \mathbb{E}_0[L_p^2 1_{A_p}]=\left(\mathbb{E}_0[L_1(Q)^2 1_{\{Q\le1+\eta\}}]\right)^p. E 0 [ L p 2 1 A p ] = ( E 0 [ L 1 ( Q ) 2 1 { Q ≤ 1 + η } ] ) p .
Now
L 1 ( q ) = 1 − ϵ p + ϵ p ℓ p ( q ) , L_1(q)=1-\epsilon_p+\epsilon_p\ell_p(q), L 1 ( q ) = 1 − ϵ p + ϵ p ℓ p ( q ) ,
so
L 1 ( q ) 2 = ( 1 − ϵ p ) 2 + 2 ϵ p ( 1 − ϵ p ) ℓ p ( q ) + ϵ p 2 ℓ p ( q ) 2 . L_1(q)^2=(1-\epsilon_p)^2+2\epsilon_p(1-\epsilon_p)\ell_p(q)+\epsilon_p^2\ell_p(q)^2. L 1 ( q ) 2 = ( 1 − ϵ p ) 2 + 2 ϵ p ( 1 − ϵ p ) ℓ p ( q ) + ϵ p 2 ℓ p ( q ) 2 .
Using
P 0 ( Q ≤ 1 + η ) ≤ 1 \mathbb{P}_0(Q\le1+\eta)\le1 P 0 ( Q ≤ 1 + η ) ≤ 1
and
E 0 [ ℓ p ( Q ) 1 { Q ≤ 1 + η } ] ≤ E 0 [ ℓ p ( Q ) ] = 1 , \mathbb{E}_0[\ell_p(Q)1_{\{Q\le1+\eta\}}]\le\mathbb{E}_0[\ell_p(Q)]=1, E 0 [ ℓ p ( Q ) 1 { Q ≤ 1 + η } ] ≤ E 0 [ ℓ p ( Q )] = 1 ,
we get
E 0 [ L 1 ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ 1 + ϵ p 2 E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] . \mathbb{E}_0[L_1(Q)^2 1_{\{Q\le1+\eta\}}]\le1+\epsilon_p^2\mathbb{E}_0[\ell_p(Q)^2 1_{\{Q\le1+\eta\}}]. E 0 [ L 1 ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ 1 + ϵ p 2 E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] .
Moreover,
E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] = ∫ 0 1 + η ℓ p ( q ) 2 h 0 ( q ) d q ≤ ∫ 0 1 + η p 2 q − 2 Ψ p ( q ) + o ( 1 ) ( log p ) p − q d q = ( log p ) ∫ 0 1 + η p q − 2 Ψ p ( q ) + o ( 1 ) d q . \begin{aligned}
\mathbb{E}_0[\ell_p(Q)^2 1_{\{Q\le1+\eta\}}]=\int_0^{1+\eta}\ell_p(q)^2h_0(q)\,\mathrm{d}q \\
&\le\int_0^{1+\eta}p^{2q-2\Psi_p(q)+o(1)}(\log p)p^{-q}\,\mathrm{d}q \\
&=(\log p)\int_0^{1+\eta}p^{q-2\Psi_p(q)+o(1)}\,\mathrm{d}q.
\end{aligned} E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] = ∫ 0 1 + η ℓ p ( q ) 2 h 0 ( q ) d q ≤ ∫ 0 1 + η p 2 q − 2 Ψ p ( q ) + o ( 1 ) ( log p ) p − q d q = ( log p ) ∫ 0 1 + η p q − 2 Ψ p ( q ) + o ( 1 ) d q .
The o ( 1 ) o(1) o ( 1 ) term is uniform on the compact interval [ 0 , 1 + η ] [0,1+\eta] [ 0 , 1 + η ] , so
E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ p sup 0 ≤ q ≤ 1 + η { q − 2 Ψ p ( q ) } + o ( 1 ) . \mathbb{E}_0[\ell_p(Q)^2 1_{\{Q\le1+\eta\}}]\le p^{\sup_{0\le q\le1+\eta}\{q-2\Psi_p(q)\}+o(1)}. E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ p s u p 0 ≤ q ≤ 1 + η { q − 2 Ψ p ( q )} + o ( 1 ) .
Since ϵ p = p − β \epsilon_p=p^{-\beta} ϵ p = p − β ,
p ϵ p 2 E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ p 1 − 2 β + sup 0 ≤ q ≤ 1 + η { q − 2 Ψ p ( q ) } + o ( 1 ) = p 2 sup 0 ≤ q ≤ 1 + η E p ( q ) + o ( 1 ) ≤ p − 2 a + o ( 1 ) → 0. \begin{aligned}
p\epsilon_p^2\mathbb{E}_0[\ell_p(Q)^2 1_{\{Q\le1+\eta\}}]\le p^{1-2\beta+\sup_{0\le q\le1+\eta}\{q-2\Psi_p(q)\}+o(1)} \\
&=p^{2\sup_{0\le q\le1+\eta}E_p(q)+o(1)} \\
&\le p^{-2a+o(1)}\to0.
\end{aligned} p ϵ p 2 E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ p 1 − 2 β + s u p 0 ≤ q ≤ 1 + η { q − 2 Ψ p ( q )} + o ( 1 ) = p 2 s u p 0 ≤ q ≤ 1 + η E p ( q ) + o ( 1 ) ≤ p − 2 a + o ( 1 ) → 0.
Therefore,
ϵ p 2 E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] = o ( p − 1 ) , \epsilon_p^2\mathbb{E}_0[\ell_p(Q)^2 1_{\{Q\le1+\eta\}}]=o(p^{-1}), ϵ p 2 E 0 [ ℓ p ( Q ) 2 1 { Q ≤ 1 + η } ] = o ( p − 1 ) ,
and hence
E 0 [ L 1 ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ 1 + o ( p − 1 ) . \mathbb{E}_0[L_1(Q)^2 1_{\{Q\le1+\eta\}}]\le1+o(p^{-1}). E 0 [ L 1 ( Q ) 2 1 { Q ≤ 1 + η } ] ≤ 1 + o ( p − 1 ) .
Consequently,
E 0 [ L p 2 1 A p ] ≤ ( 1 + o ( p − 1 ) ) p = 1 + o ( 1 ) . \mathbb{E}_0[L_p^2 1_{A_p}]\le(1+o(p^{-1}))^p=1+o(1). E 0 [ L p 2 1 A p ] ≤ ( 1 + o ( p − 1 ) ) p = 1 + o ( 1 ) .
For the matching lower bound, Cauchy–Schwarz gives
E 0 [ L p 2 1 A p ] ≥ ( E 0 [ L p 1 A p ] ) 2 . \mathbb{E}_0[L_p^2 1_{A_p}]\ge\left(\mathbb{E}_0[L_p1_{A_p}]\right)^2. E 0 [ L p 2 1 A p ] ≥ ( E 0 [ L p 1 A p ] ) 2 .
By (35) , the right-hand side tends to 1. Thus
E 0 [ L p 2 1 A p ] → 1. (36) \mathbb{E}_0[L_p^2 1_{A_p}]\to1. \tag*{(36)} E 0 [ L p 2 1 A p ] → 1. (36)
Conclusion: total variation and classification
We now show that the truncated moment bounds imply total variation convergence. For any measurable event B B B ,
P 1 ( p ) ( B ) − P 0 ( p ) ( B ) = E 0 [ L p 1 B ] − P 0 ( p ) ( B ) . P_{1}^{(p)}(B)-P_{0}^{(p)}(B)=\mathbb{E}_{0}[L_{p}1_{B}]-P_{0}^{(p)}(B). P 1 ( p ) ( B ) − P 0 ( p ) ( B ) = E 0 [ L p 1 B ] − P 0 ( p ) ( B ) .
Decompose
E 0 [ L p 1 B ] = E 0 [ L p 1 A p 1 B ] + E 0 [ L p 1 A p c 1 B ] . \mathbb{E}_{0}[L_{p}1_{B}]=\mathbb{E}_{0}[L_{p}1_{A_{p}}1_{B}]+\mathbb{E}_{0}[L_{p}1_{A_{p}^{c}}1_{B}]. E 0 [ L p 1 B ] = E 0 [ L p 1 A p 1 B ] + E 0 [ L p 1 A p c 1 B ] .
Then
∣ P 1 ( p ) ( B ) − P 0 ( p ) ( B ) ∣ ≤ ∣ E 0 [ ( L p 1 A p − 1 ) 1 B ] ∣ + E 0 [ L p 1 A p c ] + P 0 ( p ) ( A p c ) . \left|P_{1}^{(p)}(B)-P_{0}^{(p)}(B)\right|\leq\left|\mathbb{E}_{0}[(L_{p}1_{A_{p}}-1)1_{B}]\right|+\mathbb{E}_{0}[L_{p}1_{A_{p}^{c}}]+P_{0}^{(p)}(A_{p}^{c}). P 1 ( p ) ( B ) − P 0 ( p ) ( B ) ≤ E 0 [( L p 1 A p − 1 ) 1 B ] + E 0 [ L p 1 A p c ] + P 0 ( p ) ( A p c ) .
The second term equals
E 0 [ L p 1 A p c ] = P 1 ( p ) ( A p c ) → 0 , \mathbb{E}_{0}[L_{p}1_{A_{p}^{c}}]=P_{1}^{(p)}(A_{p}^{c})\to0, E 0 [ L p 1 A p c ] = P 1 ( p ) ( A p c ) → 0 ,
and the third term also tends to zero. For the first term, Cauchy–Schwarz gives
∣ E 0 [ ( L p 1 A p − 1 ) 1 B ] ∣ ≤ ( E 0 [ ( L p 1 A p − 1 ) 2 ] ) 1 / 2 . \left|\mathbb{E}_{0}[(L_{p}1_{A_{p}}-1)1_{B}]\right|\leq\left(\mathbb{E}_{0}[(L_{p}1_{A_{p}}-1)^{2}]\right)^{1/2}. E 0 [( L p 1 A p − 1 ) 1 B ] ≤ ( E 0 [( L p 1 A p − 1 ) 2 ] ) 1/2 .
But
E 0 [ ( L p 1 A p − 1 ) 2 ] = E 0 [ L p 2 1 A p ] − 2 E 0 [ L p 1 A p ] + 1 \mathbb{E}_{0}[(L_{p}1_{A_{p}}-1)^{2}]=\mathbb{E}_{0}[L_{p}^{2}1_{A_{p}}]-2\mathbb{E}_{0}[L_{p}1_{A_{p}}]+1 E 0 [( L p 1 A p − 1 ) 2 ] = E 0 [ L p 2 1 A p ] − 2 E 0 [ L p 1 A p ] + 1
→ 1 − 2 + 1 = 0 , \to1-2+1=0, → 1 − 2 + 1 = 0 ,
by (35) and (36) . Hence
sup B ∣ P 1 ( p ) ( B ) − P 0 ( p ) ( B ) ∣ → 0. \sup_{B}\left|P_{1}^{(p)}(B)-P_{0}^{(p)}(B)\right|\to0. B sup P 1 ( p ) ( B ) − P 0 ( p ) ( B ) → 0.
Therefore
TV ( P 1 ( p ) , P 0 ( p ) ) → 0. \operatorname{TV}(P_{1}^{(p)},P_{0}^{(p)})\to0. TV ( P 1 ( p ) , P 0 ( p ) ) → 0.
The training-score calculation above proves indistinguishability for the training experiment. To include the test observation, augment the experiment by one independent observation Z c Z_{c} Z c from each class, conditional on the same latent means. The augmented design has class size n c + 1 n_{c}+1 n c + 1 and non-centrality
λ p + = 2 r log p ( 1 + 1 n c ) . \lambda_{p}^{+}=2r\log p\left(1+\frac{1}{n_{c}}\right). λ p + = 2 r log p ( 1 + n c 1 ) .
Because n c → ∞ n_{c}\to\infty n c → ∞ , its normalized non-centrality has the same limit r r r ; the preceding truncated-moment proof therefore gives total variation o ( 1 ) o(1) o ( 1 ) for the augmented experiment as well. Now draw Y Y Y uniformly from [ C ] [C] [ C ] , independently of the augmented observations, and evaluate h ^ ( D n , Z Y ) \hat{h}(D_{n},Z_{Y}) h ^ ( D n , Z Y ) . Under the alternative this has exactly the law of the original test pair. Under the null, Y Y Y is independent of the observed data, so the correctness probability is 1 / C 1/C 1/ C . Applying total variation to the correctness event gives, uniformly over classifiers,
P 1 { h ^ ( D n , Z Y ) = Y } ≤ 1 C + o ( 1 ) . \mathbb{P}_{1}\{\hat{h}(D_{n},Z_{Y})=Y\}\leq\frac{1}{C}+o(1). P 1 { h ^ ( D n , Z Y ) = Y } ≤ C 1 + o ( 1 ) .
A constant classifier attains 1 / C 1/C 1/ C , completing the proof of Theorem 1.
HC growth and HCT adaptivity
We analyze the HCT rule of Algorithm 1. For a threshold t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , write
TP ( t ) = ∑ j ∈ J 1 { π j ≤ t } , FP ( t ) = ∑ j ∉ J 1 { π j ≤ t } , N ( t ) = TP ( t ) + FP ( t ) . \operatorname{TP}(t)=\sum_{j\in\mathcal{J}}1\{\pi_{j}\leq t\},\qquad\operatorname{FP}(t)=\sum_{j\notin\mathcal{J}}1\{\pi_{j}\leq t\},\qquad N(t)=\operatorname{TP}(t)+\operatorname{FP}(t). TP ( t ) = j ∈ J ∑ 1 { π j ≤ t } , FP ( t ) = j ∈ / J ∑ 1 { π j ≤ t } , N ( t ) = TP ( t ) + FP ( t ) .
On the admissible set A p = { t : 1 ≤ N ( t ) ≤ ⌊ γ 0 p ⌋ } A_{p}=\{t:1\leq N(t)\leq\lfloor\gamma_{0}p\rfloor\} A p = { t : 1 ≤ N ( t ) ≤ ⌊ γ 0 p ⌋} , define
H p ( t ) = N ( t ) − p t N ( t ) ( 1 − N ( t ) / p ) . (37) H_{p}(t)=\frac{N(t)-pt}{\sqrt{N(t)(1-N(t)/p)}}. \tag*{(37)} H p ( t ) = N ( t ) ( 1 − N ( t ) / p ) N ( t ) − pt . (37)
For pointwise probability statements set H p ( t ) = 0 H_{p}(t)=0 H p ( t ) = 0 outside A p A_{p} A p . The exact F p-values are continuous, so ties have probability zero and H p ( π ( j ) ) = H C p , j H_{p}(\pi_{(j)})=HC_{p,j} H p ( π ( j ) ) = H C p , j . Between consecutive p-values the count and denominator are constant, while the numerator decreases with t t t . Thus the algorithm maximizes (37) over A p A_p A p . Write t ^ = π ( j ∗ ) \hat{t}=\pi(j^*) t ^ = π ( j ∗ ) for its chosen threshold, with deterministic tie-breaking if several scores attain the maximum.
For q ∈ ( 0 , 1 ) q \in(0,1) q ∈ ( 0 , 1 ) define
A p ( q ) = 1 − β − Ψ p ( q ) , B ( q ) = 1 − q , E p ( q ) = A p ( q ) − B ( q ) / 2 , A_p(q)=1-\beta-\Psi_p(q),\qquad B(q)=1-q,\qquad E_p(q)=A_p(q)-B(q)/2, A p ( q ) = 1 − β − Ψ p ( q ) , B ( q ) = 1 − q , E p ( q ) = A p ( q ) − B ( q ) /2 ,
and the HC growth exponent for the empirical denominator in (37)
E ~ p ( q ) = A p ( q ) − 1 2 max { A p ( q ) , B ( q ) } = min { E p ( q ) , A p ( q ) / 2 } . (38) \widetilde{E}_p(q)=A_p(q)-\frac{1}{2}\max\{A_p(q),B(q)\}=\min\{E_p(q),A_p(q)/2\}. \tag*{(38)} E p ( q ) = A p ( q ) − 2 1 max { A p ( q ) , B ( q )} = min { E p ( q ) , A p ( q ) /2 } . (38)
Here A p ( q ) A_p(q) A p ( q ) and B ( q ) B(q) B ( q ) are the exponents of the expected useful and null selection counts. The denominator in (37) uses the observed fraction N ( t ) / p N(t)/p N ( t ) / p , rather than the null probability t t t . Where E p ( q ) > 0 E_p(q)>0 E p ( q ) > 0 , its exponent is 1 2 max { A p ( q ) , B ( q ) } \frac{1}{2}\max\{A_p(q),B(q)\} 2 1 max { A p ( q ) , B ( q )} ; subtracting this from the numerator exponent A p ( q ) A_p(q) A p ( q ) gives E ~ p ( q ) \widetilde{E}_p(q) E p ( q ) . Since B ( q ) > 0 B(q)>0 B ( q ) > 0 , E ~ p ( q ) > 0 \widetilde{E}_p(q)>0 E p ( q ) > 0 if and only if E p ( q ) > 0 E_p(q)>0 E p ( q ) > 0 . Thus HC grows as a positive power of p p p for the same parameter values that define the boundary in (20) , although its growth rate and maximizing threshold can differ from those for the null denominator. The algorithm scans the ordered observed p-values; the deterministic grids below are used only to prove uniform bounds.
Theorem 8 (HC growth and HCT adaptivity). Assume the spherical homogeneous model, feature-wise independence, the calibrations of Theorem 7 , β ∈ ( 1 / 2 , 1 ) \beta\in(1/2,1) β ∈ ( 1/2 , 1 ) , and fixed γ 0 ∈ ( 0 , 1 ) \gamma_0 \in(0,1) γ 0 ∈ ( 0 , 1 ) . Then:
(a) For every fixed q ∈ ( 0 , 1 ) q \in(0,1) q ∈ ( 0 , 1 ) with E p ( q ) > 0 E_p(q)>0 E p ( q ) > 0 ,
H p ( p − q ) = p E ~ p ( q ) + o P ( 1 ) . (39) H_p(p^{-q})=p^{\widetilde{E}_p(q)+o_P(1)}. \tag*{(39)} H p ( p − q ) = p E p ( q ) + o P ( 1 ) . (39) For arbitrary fixed q ∈ ( 0 , 1 ) q \in(0,1) q ∈ ( 0 , 1 ) , its positive part satisfies
[ H p ( p − q ) ] + = O P ( p max { E ~ p ( q ) , 0 } + o ( 1 ) ) . (40) [H_p(p^{-q})]_+=O_P\left(p^{\max\{\widetilde{E}_p(q),0\}+o(1)}\right). \tag*{(40)} [ H p ( p − q ) ] + = O P ( p m a x { E p ( q ) , 0 } + o ( 1 ) ) . (40) At a nonadmissible threshold set this positive part to zero; any fixed q ∈ ( 0 , 1 ) q \in(0,1) q ∈ ( 0 , 1 ) is admissible with probability tending to one.
(b) If sup 0 < q < 1 E p ( q ) > 0 \sup_{0<q<1}E_p(q)>0 sup 0 < q < 1 E p ( q ) > 0 , there is a fixed d > 0 d>0 d > 0 such that
P { TP ( t ^ ) 2 N ( t ^ ) ≥ p d } ⟶ 1. (41) \mathbb{P}\left\{\frac{\operatorname{TP}(\hat{t})^2}{N(\hat{t})}\ge p^d\right\}\longrightarrow1. \tag*{(41)} P { N ( t ^ ) TP ( t ^ ) 2 ≥ p d } ⟶ 1. (41) In particular, after decreasing d d d if necessary, TP ( t ^ ) ≥ p d \operatorname{TP}(\hat{t})\ge p^d TP ( t ^ ) ≥ p d and TP ( t ^ ) 2 / ( FP ( t ^ ) + 1 ) ≥ p d \operatorname{TP}(\hat{t})^2/(\operatorname{FP}(\hat{t})+1)\ge p^d TP ( t ^ ) 2 / ( FP ( t ^ ) + 1 ) ≥ p d with probability tending to one.
Count lemmas
In the following two lemmas, Q p ⊂ ( 0 , 1 ) \mathcal{Q}_p\subset(0,1) Q p ⊂ ( 0 , 1 ) is any deterministic grid of polynomial cardinality. It is used for analysis, not to define HCT. Write TP q = TP ( p − q ) \operatorname{TP}_q=\operatorname{TP}(p^{-q}) TP q = TP ( p − q ) and FP q = FP ( p − q ) \operatorname{FP}_q=\operatorname{FP}(p^{-q}) FP q = FP ( p − q ) for exponent thresholds.
Lemma 9 (False positives). Assume { π j : j ∈ J c } \{\pi_j:j\in\mathcal{J}^c\} { π j : j ∈ J c } are i.i.d. Uniform[ 0 , 1 ] [0,1] [ 0 , 1 ] and the Bernoulli signal-set model of § 4 . Then, for every compact Q ⋐ ( 0 , 1 ) \mathcal{Q}\Subset(0,1) Q ⋐ ( 0 , 1 ) and every polynomial grid Q p ⊂ Q \mathcal{Q}_p\subset\mathcal{Q} Q p ⊂ Q with ∣ Q p ∣ ≤ p a |\mathcal{Q}_p|\le p^a ∣ Q p ∣ ≤ p a ,
FP q = p 1 − q ( 1 + o ( 1 ) ) \operatorname{FP}_q=p^{1-q}(1+o(1)) FP q = p 1 − q ( 1 + o ( 1 )) uniformly over q ∈ Q p q\in\mathcal{Q}_p q ∈ Q p , with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . Moreover,
FP q − p 1 − q = O P ( p ( 1 − q ) / 2 ) \operatorname{FP}_q-p^{1-q}=O_P\left(p^{(1-q)/2}\right) FP q − p 1 − q = O P ( p ( 1 − q ) /2 ) for each fixed q ∈ Q q\in\mathcal{Q} q ∈ Q .
Proof. Unconditionally, FP q \operatorname{FP}_q FP q is binomial with parameters p p p and ( 1 − ϵ p ) p − q (1-\epsilon_p)p^{-q} ( 1 − ϵ p ) p − q . Its mean differs from p 1 − q p^{1-q} p 1 − q by p 1 − β − q p^{1-\beta-q} p 1 − β − q , which is o ( p ( 1 − q ) / 2 ) o(p^{(1-q)/2}) o ( p ( 1 − q ) /2 ) since β > 1 / 2 \beta>1/2 β > 1/2 . Bernstein’s inequality gives relative concentration uniformly on the stated grid because its smallest mean is polynomial in p p p . The variance bound and the negligible mean difference give the fixed-q q q statement.
Lemma 10 (True positives). Assume the conditions of Theorem 7, feature-wise independence, and condition on a signal set of size ∣ J ∣ = p 1 − β ( 1 + o ( 1 ) ) |\mathcal{J}| = p^{1-\beta}(1+o(1)) ∣ J ∣ = p 1 − β ( 1 + o ( 1 )) , an event of probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . Then, uniformly over the deterministic grid,
E [ T P q ] = p 1 − β − Ψ p ( q ) + o ( 1 ) . \mathbb{E}[\mathrm{TP}_q] = p^{1-\beta-\Psi_p(q)+o(1)}. E [ TP q ] = p 1 − β − Ψ p ( q ) + o ( 1 ) .
Furthermore, whenever 1 − β − Ψ p ( q ) > 0 1-\beta-\Psi_p(q)>0 1 − β − Ψ p ( q ) > 0 is bounded away from zero on a subset of the grid, the corresponding counts concentrate relatively uniformly:
T P q = p 1 − β − Ψ p ( q ) + o P ( 1 ) . \mathrm{TP}_q = p^{1-\beta-\Psi_p(q)+o_P(1)}. TP q = p 1 − β − Ψ p ( q ) + o P ( 1 ) .
For all grid points, the upper bound
T P q = O P ( p max { 1 − β − Ψ p ( q ) , 0 } + o ( 1 ) ) \mathrm{TP}_q = O_P\left(p^{\max\{1-\beta-\Psi_p(q),0\}+o(1)}\right) TP q = O P ( p m a x { 1 − β − Ψ p ( q ) , 0 } + o ( 1 ) )
holds uniformly over q ∈ Q p q\in\mathcal{Q}_p q ∈ Q p .
Proof. Condition on the signal set J \mathcal{J} J . For q ∈ Q p q\in\mathcal{Q}_p q ∈ Q p , write
T P q = ∑ j ∈ J X j ( q ) , X j ( q ) : = 1 { π j ≤ p − q } . \mathrm{TP}_q=\sum_{j\in\mathcal{J}}X_j(q),\qquad X_j(q):=\mathbf{1}\{\pi_j\le p^{-q}\}. TP q = j ∈ J ∑ X j ( q ) , X j ( q ) := 1 { π j ≤ p − q } .
By feature-wise independence, for each fixed q q q the variables { X j ( q ) : j ∈ J } \{X_j(q):j\in\mathcal{J}\} { X j ( q ) : j ∈ J } are independent Bernoulli variables. By Theorem 7,
P ( X j ( q ) = 1 ) = P ( π j ≤ p − q ∣ j ∈ J ) = p − Ψ p ( q ) + o ( 1 ) \mathbb{P}(X_j(q)=1)=\mathbb{P}(\pi_j\le p^{-q}\mid j\in\mathcal{J})=p^{-\Psi_p(q)+o(1)} P ( X j ( q ) = 1 ) = P ( π j ≤ p − q ∣ j ∈ J ) = p − Ψ p ( q ) + o ( 1 )
uniformly over q ∈ Q p q\in\mathcal{Q}_p q ∈ Q p . Hence, on the event ∣ J ∣ = p 1 − β ( 1 + o ( 1 ) ) |\mathcal{J}|=p^{1-\beta}(1+o(1)) ∣ J ∣ = p 1 − β ( 1 + o ( 1 )) ,
m p ( q ) : = E [ T P q ∣ J ] = ∣ J ∣ p − Ψ p ( q ) + o ( 1 ) = p 1 − β − Ψ p ( q ) + o ( 1 ) m_p(q):=\mathbb{E}[\mathrm{TP}_q\mid\mathcal{J}]=|\mathcal{J}|p^{-\Psi_p(q)+o(1)}=p^{1-\beta-\Psi_p(q)+o(1)} m p ( q ) := E [ TP q ∣ J ] = ∣ J ∣ p − Ψ p ( q ) + o ( 1 ) = p 1 − β − Ψ p ( q ) + o ( 1 )
uniformly over q ∈ Q p q\in\mathcal{Q}_p q ∈ Q p . This proves the expectation claim.
We next prove the relative concentration statement. Let A p ⊆ Q p \mathcal{A}_p\subseteq\mathcal{Q}_p A p ⊆ Q p be a subset on which
1 − β − Ψ p ( q ) ≥ η 1-\beta-\Psi_p(q)\ge\eta 1 − β − Ψ p ( q ) ≥ η
for some fixed η > 0 \eta>0 η > 0 and all large p p p . Then, uniformly over q ∈ A p q\in\mathcal{A}_p q ∈ A p ,
m p ( q ) ≥ p η / 2 m_p(q)\ge p^{\eta/2} m p ( q ) ≥ p η /2
for all sufficiently large p p p . Bernstein’s inequality for sums of independent Bernoulli variables gives, for any fixed ϵ > 0 \epsilon>0 ϵ > 0 ,
P ( ∣ T P q − m p ( q ) ∣ ≥ ϵ m p ( q ) ∣ J ) ≤ 2 exp { − c ϵ m p ( q ) } \mathbb{P}\left(|\mathrm{TP}_q-m_p(q)|\ge\epsilon m_p(q)\mid\mathcal{J}\right)\le2\exp\{-c_\epsilon m_p(q)\} P ( ∣ TP q − m p ( q ) ∣ ≥ ϵ m p ( q ) ∣ J ) ≤ 2 exp { − c ϵ m p ( q )}
for a constant c ϵ > 0 c_\epsilon>0 c ϵ > 0 . Therefore
P ( ∃ q ∈ A p : ∣ T P q − m p ( q ) ∣ ≥ ϵ m p ( q ) ∣ J ) ≤ 2 ∣ Q p ∣ exp { − c ϵ p η / 2 } . \mathbb{P}\left(\exists q\in\mathcal{A}_p:|\mathrm{TP}_q-m_p(q)|\ge\epsilon m_p(q)\mid\mathcal{J}\right)\le2|\mathcal{Q}_p|\exp\{-c_\epsilon p^{\eta/2}\}. P ( ∃ q ∈ A p : ∣ TP q − m p ( q ) ∣ ≥ ϵ m p ( q ) ∣ J ) ≤ 2∣ Q p ∣ exp { − c ϵ p η /2 } .
Since ∣ Q p ∣ ≤ p a |\mathcal{Q}_p|\le p^a ∣ Q p ∣ ≤ p a , the right-hand side is o ( 1 ) o(1) o ( 1 ) . Hence
sup q ∈ A p ∣ T P q m p ( q ) − 1 ∣ = o P ( 1 ) . \sup_{q\in\mathcal{A}_p}\left|\frac{\mathrm{TP}_q}{m_p(q)}-1\right|=o_P(1). q ∈ A p sup m p ( q ) TP q − 1 = o P ( 1 ) .
Combining this with m p ( q ) = p 1 − β − Ψ p ( q ) + o ( 1 ) m_p(q)=p^{1-\beta-\Psi_p(q)+o(1)} m p ( q ) = p 1 − β − Ψ p ( q ) + o ( 1 ) yields
T P q = p 1 − β − Ψ p ( q ) + o P ( 1 ) \mathrm{TP}_q=p^{1-\beta-\Psi_p(q)+o_P(1)} TP q = p 1 − β − Ψ p ( q ) + o P ( 1 )
uniformly over q ∈ A p q\in\mathcal{A}_p q ∈ A p . This proves the relative concentration statement.
It remains to prove the uniform upper bound over all grid points. Again by Bernstein’s inequality, for every t > 0 t>0 t > 0 ,
P ( T P q − m p ( q ) ≥ t ∣ J ) ≤ exp ( − t 2 2 m p ( q ) + 2 t / 3 ) . \mathbb{P}(\mathrm{TP}_q-m_p(q)\ge t\mid\mathcal{J})\le\exp\left(-\frac{t^2}{2m_p(q)+2t/3}\right). P ( TP q − m p ( q ) ≥ t ∣ J ) ≤ exp ( − 2 m p ( q ) + 2 t /3 t 2 ) .
Take
t = K { m p ( q ) log p + log p } . t=K\{\sqrt{m_p(q)\log p}+\log p\}. t = K { m p ( q ) log p + log p } .
For K K K sufficiently large,
P ( T P q ≥ m p ( q ) + K { m p ( q ) log p + log p } ∣ J ) ≤ p − a − 2 . \mathbb{P}\left(\mathrm{TP}_q \ge m_p(q) + K\left\{\sqrt{m_p(q)\log p}+\log p\right\}\mathrel{\big|}\mathcal{J}\right)\le p^{-a-2}. P ( TP q ≥ m p ( q ) + K { m p ( q ) log p + log p } J ) ≤ p − a − 2 .
A union bound over ∣ Q p ∣ ≤ p a |\mathcal{Q}_p|\le p^a ∣ Q p ∣ ≤ p a therefore gives, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
T P q ≤ m p ( q ) + K m p ( q ) log p + K log p \mathrm{TP}_q\le m_p(q)+K\sqrt{m_p(q)\log p}+K\log p TP q ≤ m p ( q ) + K m p ( q ) log p + K log p
simultaneously for all q ∈ Q p q\in\mathcal{Q}_p q ∈ Q p .
Since
m p ( q ) = p 1 − β − Ψ p ( q ) + o ( 1 ) , m_p(q)=p^{1-\beta-\Psi_p(q)+o(1)}, m p ( q ) = p 1 − β − Ψ p ( q ) + o ( 1 ) ,
the preceding display implies
T P q = O P ( p max { 1 − β − Ψ p ( q ) , 0 } + o ( 1 ) ) \mathrm{TP}_q=O_{\mathbb{P}}\left(p^{\max\{1-\beta-\Psi_p(q),0\}+o(1)}\right) TP q = O P ( p m a x { 1 − β − Ψ p ( q ) , 0 } + o ( 1 ) )
uniformly over q ∈ Q p q\in\mathcal{Q}_p q ∈ Q p . Indeed, when 1 − β − Ψ p ( q ) > 0 1-\beta-\Psi_p(q)>0 1 − β − Ψ p ( q ) > 0 , the mean term dominates on the polynomial scale, while when 1 − β − Ψ p ( q ) ≤ 0 1-\beta-\Psi_p(q)\le0 1 − β − Ψ p ( q ) ≤ 0 , all three terms are at most p o ( 1 ) p^{o(1)} p o ( 1 ) . This proves the lemma. □
Lemma 11 (Auxiliary grid and uniform counts). Conditional on J \mathcal{J} J , put m J = ∣ J ∣ m_{\mathcal{J}}=|\mathcal{J}| m J = ∣ J ∣ , a p ( t ) = P ( π j ≤ t ∣ j ∈ J ) a_p(t)=\mathbb{P}(\pi_j\le t\mid j\in\mathcal{J}) a p ( t ) = P ( π j ≤ t ∣ j ∈ J ) and m T ( t ) = m J a p ( t ) m_T(t)=m_{\mathcal{J}}a_p(t) m T ( t ) = m J a p ( t ) . There is a deterministic grid T p ⊂ [ 0 , 1 ] \mathcal{T}_p\subset[0,1] T p ⊂ [ 0 , 1 ] of cardinality O ( p 4 ) O(p^4) O ( p 4 ) such that, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , each interval between successive grid points contains at most one observed p p p -value. Furthermore, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , simultaneously for every t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] ,
∣ F P ( t ) − ( p − m J ) t ∣ ≤ K { p t log p + log p } , (42) |\mathrm{FP}(t)-(p-m_{\mathcal{J}})t|\le K\left\{\sqrt{pt\log p}+\log p\right\}, \tag*{(42)} ∣ FP ( t ) − ( p − m J ) t ∣ ≤ K { pt log p + log p } , (42) ∣ T P ( t ) − m T ( t ) ∣ ≤ K { m T ( t ) log p + log p } . (43) |\mathrm{TP}(t)-m_T(t)|\le K\left\{\sqrt{m_T(t)\log p}+\log p\right\}. \tag*{(43)} ∣ TP ( t ) − m T ( t ) ∣ ≤ K { m T ( t ) log p + log p } . (43) For each fixed d > 0 d>0 d > 0 , these bounds imply m T ( t ) / T P ( t ) = 1 + o ( 1 ) m_T(t)/\mathrm{TP}(t)=1+o(1) m T ( t ) / TP ( t ) = 1 + o ( 1 ) uniformly over thresholds with T P ( t ) ≥ p d \mathrm{TP}(t)\ge p^d TP ( t ) ≥ p d .
Proof. The useful-feature F p-value distribution a p a_p a p is continuous. The function G p ( t ) = ( t + a p ( t ) ) / 2 G_p(t)=(t+a_p(t))/2 G p ( t ) = ( t + a p ( t )) /2 is therefore continuous and strictly increasing from zero to one. Set M p = ⌈ p 4 ⌉ M_p=\lceil p^4\rceil M p = ⌈ p 4 ⌉ and
u ℓ = G p − 1 ( ℓ / M p ) , 0 ≤ ℓ ≤ M p , T p = { u 0 , … , u M p } . u_\ell=G_p^{-1}(\ell/M_p),\qquad0\le\ell\le M_p,\qquad\mathcal{T}_p=\{u_0,\ldots,u_{M_p}\}. u ℓ = G p − 1 ( ℓ / M p ) , 0 ≤ ℓ ≤ M p , T p = { u 0 , … , u M p } .
Each cell ( u ℓ − 1 , u ℓ ] (u_{\ell-1},u_\ell] ( u ℓ − 1 , u ℓ ] has probability at most 2 / M p 2/M_p 2/ M p under either a null or a useful p-value distribution. Conditional on J \mathcal{J} J , two different features are independent, so the probability that their p-values share a cell is at most 2 / M p 2/M_p 2/ M p . A union bound gives
P ( some cell contains at least two p-values ∣ J ) ≤ p ( p − 1 ) / M p = o ( 1 ) . \mathbb{P}(\text{some cell contains at least two p-values}\mid\mathcal{J})\le p(p-1)/M_p=o(1). P ( some cell contains at least two p-values ∣ J ) ≤ p ( p − 1 ) / M p = o ( 1 ) .
At each deterministic grid point, apply binomial Bernstein bounds to F P \mathrm{FP} FP and T P \mathrm{TP} TP with deviation parameter K 0 log p K_0\log p K 0 log p . Taking K 0 K_0 K 0 sufficiently large makes a union bound over O ( p 4 ) O(p^4) O ( p 4 ) points valid. This proves the two displayed bounds on T p \mathcal{T}_p T p . For an arbitrary threshold, move to its lower adjacent grid point. On the no-collision event each count changes by at most one; its mean changes by at most 2 p / M p 2p/M_p 2 p / M p . Both changes are absorbed by the K log p K\log p K log p terms, proving uniformity on [ 0 , 1 ] [0,1] [ 0 , 1 ] . Finally (43) implies T P ( t ) ≤ 2 m T ( t ) + K ′ log p \mathrm{TP}(t)\le2m_T(t)+K'\log p TP ( t ) ≤ 2 m T ( t ) + K ′ log p . If T P ( t ) ≥ p d \mathrm{TP}(t)\ge p^d TP ( t ) ≥ p d , then m T ( t ) m_T(t) m T ( t ) is polynomially large, and dividing the same bound by m T ( t ) m_T(t) m T ( t ) proves relative concentration uniformly in this region. The grid depends on model distributions but is used only in the proof; the algorithm does not construct it. □
Pointwise HC growth
Fix q ∈ ( 0 , 1 ) q\in(0,1) q ∈ ( 0 , 1 ) , put t = p − q t=p^{-q} t = p − q , and condition on the high-probability event m J = p 1 − β ( 1 + o ( 1 ) ) m_{\mathcal{J}}=p^{1-\beta}(1+o(1)) m J = p 1 − β ( 1 + o ( 1 )) . The null count has mean p B ( q ) ( 1 + o ( 1 ) ) p^{B(q)}(1+o(1)) p B ( q ) ( 1 + o ( 1 )) and fluctuation O P ( p B ( q ) / 2 ) O_{\mathbb{P}}(p^{B(q)/2}) O P ( p B ( q ) /2 ) . If E p ( q ) > 0 E_p(q)>0 E p ( q ) > 0 , then A p ( q ) > B ( q ) / 2 > 0 A_p(q)>B(q)/2>0 A p ( q ) > B ( q ) /2 > 0 , so the useful count concentrates:
T P ( t ) = p A p ( q ) + o P ( 1 ) . \mathrm{TP}(t)=p^{A_p(q)+o_{\mathbb{P}}(1)}. TP ( t ) = p A p ( q ) + o P ( 1 ) .
The identity
N ( t ) − p t = T P ( t ) + { F P ( t ) − ( p − m J ) t } − m J t N(t)-pt=\mathrm{TP}(t)+\{\mathrm{FP}(t)-(p-m_{\mathcal{J}})t\}-m_{\mathcal{J}}t N ( t ) − pt = TP ( t ) + { FP ( t ) − ( p − m J ) t } − m J t
shows that the numerator has exponent A p ( q ) A_p(q) A p ( q ) . Indeed, the null fluctuation has smaller exponent, and Ψ p ( q ) < q \Psi_p(q)<q Ψ p ( q ) < q makes m J t m_Jt m J t negligible. Moreover,
N ( t ) = p max { A p ( q ) , B ( q ) } + o P ( 1 ) , N ( t ) / p → 0. N(t)=p^{\max\{A_p(q),B(q)\}+o_P(1)},\qquad N(t)/p\to0. N ( t ) = p m a x { A p ( q ) , B ( q )} + o P ( 1 ) , N ( t ) / p → 0.
Substituting in (37) proves (39) . If E p ( q ) ≤ 0 E_p(q)\le0 E p ( q ) ≤ 0 , then A p ( q ) ≤ B ( q ) / 2 < B ( q ) A_p(q)\le B(q)/2<B(q) A p ( q ) ≤ B ( q ) /2 < B ( q ) ; the null count dominates N ( t ) N(t) N ( t ) , while the positive numerator is at most p B ( q ) / 2 + o P ( 1 ) p^{B(q)/2+o_P(1)} p B ( q ) /2 + o P ( 1 ) by the count bounds. The positive part of HC is thus at most subpolynomial, proving (40) . Since B ( q ) > 0 B(q)>0 B ( q ) > 0 and A p ( q ) ≤ 1 − β < 1 A_p(q)\le1-\beta<1 A p ( q ) ≤ 1 − β < 1 , each such fixed threshold is admissible with probability tending to one.
Adaptivity of the HCT threshold
Choose a fixed q 0 ∈ ( 0 , 1 ) q_0\in(0,1) q 0 ∈ ( 0 , 1 ) with E p ( q 0 ) > 0 E_p(q_0)>0 E p ( q 0 ) > 0 , which exists above the boundary by continuity, including when the maximum over [ 0 , 1 ] [0,1] [ 0 , 1 ] is achieved at an endpoint. Part (a) gives some a > 0 a>0 a > 0 such that H p ( p − q 0 ) ≥ p a H_p(p^{-q_0})\ge p^a H p ( p − q 0 ) ≥ p a with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . Let j 0 = N ( p − q 0 ) j_0=N(p^{-q_0}) j 0 = N ( p − q 0 ) . With high probability this is an admissible rank, and π ( j 0 ) ≤ p − q 0 \pi(j_0)\le p^{-q_0} π ( j 0 ) ≤ p − q 0 . The denominator depends only on the count, so
H p ( t ^ ) ≥ H p ( π ( j 0 ) ) ≥ H p ( p − q 0 ) ≥ p a . H_p(\hat t)\ge H_p(\pi(j_0))\ge H_p(p^{-q_0})\ge p^a. H p ( t ^ ) ≥ H p ( π ( j 0 )) ≥ H p ( p − q 0 ) ≥ p a .
On the uniform event in Lemma 11, consider any admissible t t t with H p ( t ) > 0 H_p(t)>0 H p ( t ) > 0 . Then p t < N ( t ) pt<N(t) pt < N ( t ) , and dropping the nonpositive missing-null term − m J t -m_Jt − m J t gives
H p ( t ) ≤ TP ( t ) + K { p t log p + log p } N ( t ) ( 1 − N ( t ) / p ) ≤ TP ( t ) ( 1 − γ 0 ) N ( t ) + K γ 0 log p . H_p(t)\le\frac{\operatorname{TP}(t)+K\{\sqrt{pt\log p}+\log p\}}{\sqrt{N(t)(1-N(t)/p)}}
\le\frac{\operatorname{TP}(t)}{\sqrt{(1-\gamma_0)N(t)}}+K\gamma_0\log p. H p ( t ) ≤ N ( t ) ( 1 − N ( t ) / p ) TP ( t ) + K { pt log p + log p } ≤ ( 1 − γ 0 ) N ( t ) TP ( t ) + K γ 0 log p .
Applying this inequality at t ^ \hat t t ^ yields TP ( t ^ ) / N ( t ^ ) ≥ c p a \operatorname{TP}(\hat t)/\sqrt{N(\hat t)}\ge cp^a TP ( t ^ ) / N ( t ^ ) ≥ c p a with high probability. Squaring and reducing the exponent proves (41) . Finally TP ≤ N \operatorname{TP}\le N TP ≤ N and FP + 1 ≤ 2 N \operatorname{FP}+1\le2N FP + 1 ≤ 2 N imply the stated count consequences. This argument covers the entire rank scan, including thresholds below 1 / p 1/p 1/ p , without asserting that the selected exponent belongs to ( 0 , 1 ) (0,1) ( 0 , 1 ) . This proves Theorem 8.
Boundary optimization
Proposition 12 (Explicit maximizer and boundary properties). Write Δ ( β , r , s ) = max 0 ≤ q ≤ 1 E p ( q ) \Delta(\beta,r,s)=\max_{0\le q\le1}E_p(q) Δ ( β , r , s ) = max 0 ≤ q ≤ 1 E p ( q ) . For s ≥ 0 s\ge0 s ≥ 0 , let g 0 ( x ) = x g_0(x)=x g 0 ( x ) = x , x 0 ( 1 ) = 1 x_0(1)=1 x 0 ( 1 ) = 1 , and define
x 1 = x s ( 1 ) , x † = 2 r + s 2 + 4 r 2 , x ∗ = min { x 1 , x † } . x_1=x_s(1),\qquad x_\dagger=2r+\sqrt{s^2+4r^2},\qquad x_*=\min\{x_1,x_\dagger\}. x 1 = x s ( 1 ) , x † = 2 r + s 2 + 4 r 2 , x ∗ = min { x 1 , x † } . Then
Δ ( β , r , s ) = 1 2 − β + 1 2 g s ( x ∗ ) − J r , s ( x ∗ ) . (44) \Delta(\beta,r,s)=\frac{1}{2}-\beta+\frac{1}{2}g_s(x_*)-J_{r,s}(x_*). \tag*{(44)} Δ ( β , r , s ) = 2 1 − β + 2 1 g s ( x ∗ ) − J r , s ( x ∗ ) . (44) For every β ∈ ( 1 / 2 , 1 ) \beta\in(1/2,1) β ∈ ( 1/2 , 1 ) and fixed s ≥ 0 s\ge0 s ≥ 0 , Δ \Delta Δ crosses zero at a unique positive r = ξ ∗ ( β , s ) r=\xi^*(\beta,s) r = ξ ∗ ( β , s ) , with strict signs on either side. The boundary is strictly increasing in s s s and
ξ ∗ ( β , 0 ) = ρ ∗ ( β ) , lim s → 0 ξ ∗ ( β , s ) = ρ ∗ ( β ) , ξ ∗ ( β , s ) ∼ 2 s ρ ∗ ( β ) ( s → ∞ ) . \xi^*(\beta,0)=\rho^*(\beta),\qquad\lim_{s\to0}\xi^*(\beta,s)=\rho^*(\beta),\qquad\xi^*(\beta,s)\sim\sqrt{2s\rho^*(\beta)}\quad(s\to\infty). ξ ∗ ( β , 0 ) = ρ ∗ ( β ) , s → 0 lim ξ ∗ ( β , s ) = ρ ∗ ( β ) , ξ ∗ ( β , s ) ∼ 2 s ρ ∗ ( β ) ( s → ∞ ) . Proof. Substitute q = g s ( x ) q=g_s(x) q = g s ( x ) so that s ≤ x ≤ x 1 s\le x\le x_1 s ≤ x ≤ x 1 . Below s + r s+r s + r , J = 0 J=0 J = 0 and g s g_s g s is increasing. Above s + r s+r s + r , the envelope theorem in (29) , or direct differentiation of (30) , gives
d d x ( 1 2 g s ( x ) − J r , s ( x ) ) = s 2 + 4 r x − x 2 x . \frac{d}{dx}\left(\frac{1}{2}g_s(x)-J_{r,s}(x)\right)=\frac{\sqrt{s^2+4rx}-x}{2x}. d x d ( 2 1 g s ( x ) − J r , s ( x ) ) = 2 x s 2 + 4 r x − x . This derivative changes sign once, at x = x † > s + r x=x_\dagger>s+r x = x † > s + r . The same formula holds for s = 0 s=0 s = 0 above x = r x=r x = r , where x † = 4 r x_\dagger=4r x † = 4 r . This proves (44) .
For fixed s s s , as r → 0 r\to0 r → 0 the useful rate tends to the null rate and Δ → 1 / 2 − β < 0 \Delta\to1/2-\beta<0 Δ → 1/2 − β < 0 . Once s + r ≥ x 1 s+r\ge x_1 s + r ≥ x 1 , Δ = 1 − β > 0 \Delta=1-\beta>0 Δ = 1 − β > 0 . Continuity follows from the explicit formulas. At any r r r where Δ ≤ 0 \Delta\le0 Δ ≤ 0 , the optimizer lies strictly above s + r s+r s + r (otherwise x 1 ≤ s + r x_1\le s+r x 1 ≤ s + r and Δ = 1 − β \Delta=1-\beta Δ = 1 − β ). In that region, at fixed x x x , ∂ r J = − ( y − 1 ) < 0 \partial_rJ=-(y-1)<0 ∂ r J = − ( y − 1 ) < 0 . Increasing r r r thus strictly increases the optimized value until it becomes
positive; if the same x x x enters the zero-rate region, its rate has still strictly decreased. Monotonicity thereafter prevents a second crossing. This proves the existence, uniqueness and signs.
At s = 0 s=0 s = 0 , if r ≤ 1 / 4 r\le1/4 r ≤ 1/4 , the maximum is Δ = 1 / 2 − β + r \Delta=1/2-\beta+r Δ = 1/2 − β + r . If 1 / 4 < r < 1 1/4<r<1 1/4 < r < 1 , it is Δ = 1 − β − ( 1 − r ) 2 \Delta=1-\beta-(1-\sqrt{r})^2 Δ = 1 − β − ( 1 − r ) 2 ; for r ≥ 1 r\ge1 r ≥ 1 it is 1 − β 1-\beta 1 − β . Solving for its zero gives precisely the fixed-class boundary ρ ⋆ ( β ) \rho^\star(\beta) ρ ⋆ ( β ) stated in § 5.1 of the main paper.
For strict dependence on s s s , fix r , q r,q r , q in the positive-rate region and write z = x s ( q ) / s z=x_s(q)/s z = x s ( q ) / s and y = 2 x s ( q ) / ( s + s 2 + 4 r x s ( q ) ) y=2x_s(q)/(s+\sqrt{s^2+4rx_s(q)}) y = 2 x s ( q ) / ( s + s 2 + 4 r x s ( q ) ) . Then z > y > 1 z>y>1 z > y > 1 . Implicit differentiation of g s ( x s ( q ) ) = q g_s(x_s(q))=q g s ( x s ( q )) = q gives
∂ s x s ( q ) = A ( z ) , A ( u ) = log u 1 − 1 / u , A ′ ( u ) = u − 1 − log u ( u − 1 ) 2 > 0. \partial_s x_s(q)=A(z),\qquad A(u)=\frac{\log u}{1-1/u},\qquad A'(u)=\frac{u-1-\log u}{(u-1)^2}>0. ∂ s x s ( q ) = A ( z ) , A ( u ) = 1 − 1/ u log u , A ′ ( u ) = ( u − 1 ) 2 u − 1 − log u > 0.
The envelope theorem now yields
∂ s Ψ r , s ( q ) = ( 1 − 1 / y ) { A ( z ) − A ( y ) } > 0. \partial_s\Psi_{r,s}(q)=(1-1/y)\{A(z)-A(y)\}>0. ∂ s Ψ r , s ( q ) = ( 1 − 1/ y ) { A ( z ) − A ( y )} > 0.
In the zero-rate region the rate is zero; its onset g s ( s + r ) = r − s log ( 1 + r / s ) g_s(s+r)=r-s\log(1+r/s) g s ( s + r ) = r − s log ( 1 + r / s ) decreases with s s s . Thus Ψ \Psi Ψ is nondecreasing in s s s everywhere and strictly increases once positive. At a boundary point every maximizing q q q has positive rate, by the optimizer argument above. If s 2 > s 1 s_2>s_1 s 2 > s 1 , evaluating at r = ξ ⋆ ( β , s 1 ) r=\xi^\star(\beta,s_1) r = ξ ⋆ ( β , s 1 ) gives E s 2 ( q ) ≤ E s 1 ( q ) ≤ 0 E_{s_2}(q)\le E_{s_1}(q)\le0 E s 2 ( q ) ≤ E s 1 ( q ) ≤ 0 , with strict inequality at every zero of E s 1 E_{s_1} E s 1 . Compactness implies max q E s 2 ( q ) < 0 \max_q E_{s_2}(q)<0 max q E s 2 ( q ) < 0 , and hence ξ ⋆ ( β , s 2 ) > ξ ⋆ ( β , s 1 ) \xi^\star(\beta,s_2)>\xi^\star(\beta,s_1) ξ ⋆ ( β , s 2 ) > ξ ⋆ ( β , s 1 ) . The same conclusion with s 1 = 0 s_1=0 s 1 = 0 follows by continuity at zero and strict increase on positive s s s (apply it first between s 2 / 2 s_2/2 s 2 /2 and s 2 s_2 s 2 ).
As s → 0 s\to0 s → 0 , x s ( q ) → q x_s(q)\to q x s ( q ) → q uniformly on [ 0 , 1 ] [0,1] [ 0 , 1 ] : x s ( q ) − q = s + s log ( x s ( q ) / s ) x_s(q)-q=s+s\log(x_s(q)/s) x s ( q ) − q = s + s log ( x s ( q ) / s ) lies between s s s and its value at q = 1 q=1 q = 1 , which tends to zero. The explicit formula for J J J then gives uniform convergence of Ψ r , s \Psi_{r,s} Ψ r , s to ( q − r ) + 2 (\sqrt{q}-\sqrt{r})_+^2 ( q − r ) + 2 for every fixed r > 0 r>0 r > 0 . Strict signs on each side of the classical boundary bracket the roots and prove their convergence.
Finally let s → ∞ s\to\infty s → ∞ and set r = a 2 s r=a\sqrt{2s} r = a 2 s for fixed a > 0 a>0 a > 0 . Taylor expansion of g s g_s g s yields, uniformly for q ∈ [ 0 , 1 ] q\in[0,1] q ∈ [ 0 , 1 ] ,
x s ( q ) = s + 2 s q + O ( 1 ) . x_s(q)=s+\sqrt{2sq}+O(1). x s ( q ) = s + 2 s q + O ( 1 ) .
For x = x s ( q ) > s + r x=x_s(q)>s+r x = x s ( q ) > s + r , the optimizer θ \theta θ in (29) is O ( s − 1 / 2 ) O(s^{-1/2}) O ( s − 1/2 ) uniformly. Expanding at zero,
θ x − Λ ( θ ) = θ ( x − s − r ) − 1 2 ( s + 2 r ) θ 2 + O ( ( s + r ) θ 3 ) . \theta x-\Lambda(\theta)=\theta(x-s-r)-\frac{1}{2}(s+2r)\theta^2+O((s+r)\theta^3). θ x − Λ ( θ ) = θ ( x − s − r ) − 2 1 ( s + 2 r ) θ 2 + O (( s + r ) θ 3 ) .
Optimization, with the zero-rate case included, gives
Ψ a 2 s , s ( q ) = ( x s ( q ) − s − r ) + 2 2 ( s + 2 r ) + o ( 1 ) = ( q − a ) + 2 + o ( 1 ) \Psi_{a\sqrt{2s},s}(q)=\frac{(x_s(q)-s-r)_+^2}{2(s+2r)}+o(1)=(\sqrt{q}-a)_+^2+o(1) Ψ a 2 s , s ( q ) = 2 ( s + 2 r ) ( x s ( q ) − s − r ) + 2 + o ( 1 ) = ( q − a ) + 2 + o ( 1 )
uniformly on [ 0 , 1 ] [0,1] [ 0 , 1 ] . The limiting boundary functional has its unique zero at a 2 = ρ ⋆ ( β ) a^2=\rho^\star(\beta) a 2 = ρ ⋆ ( β ) , so bracketing again proves the claimed large-s s s equivalence. This is a limit of the fixed-s s s boundary, not a theorem for arbitrary joint sequences s = s p → ∞ s=s_p\to\infty s = s p → ∞ .
Proof of Theorem 2 (Misclassification rate of DP-HCT)
We prove the classification theorem under the spherical homogeneous contrast model. The proof analyzes the inner-product margin after HCT feature selection. Fix a true class c ⋆ ∈ [ C ] c^\star\in[C] c ⋆ ∈ [ C ] and a competing class c ≠ c ⋆ c\ne c^\star c = c ⋆ . For a useful feature j j j , the population contribution to the pairwise margin is
μ c ⋆ ( j ) ( μ c ⋆ ( j ) − μ c ( j ) ) = τ 2 v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) . (45) \mu_{c^\star}^{(j)}(\mu_{c^\star}^{(j)}-\mu_c^{(j)})=\tau^2v_{c^\star}^{(j)}(v_{c^\star}^{(j)}-v_c^{(j)}). \tag*{(45)} μ c ⋆ ( j ) ( μ c ⋆ ( j ) − μ c ( j ) ) = τ 2 v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) . (45)
The spherical symmetry of v ( j ) v^{(j)} v ( j ) gives positive average separation for every fixed class pair. Indeed,
E [ v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) ] = C C − 1 . (46) \mathbb{E}\left[v_{c^\star}^{(j)}(v_{c^\star}^{(j)}-v_c^{(j)})\right]=\frac{C}{C-1}. \tag*{(46)} E [ v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) ] = C − 1 C . (46)
Therefore, once HCT selects polynomially many true coordinates, the aggregate spherical contrast over the selected features produces a positive margin of order τ 2 T P \tau^2\mathrm{TP} τ 2 TP , where
T P : = ∣ J ^ ∩ J ∣ . \mathrm{TP}:=|\widehat{\mathcal{J}}\cap\mathcal{J}|. TP := ∣ J ∩ J ∣.
The rest of the proof shows that this positive population margin dominates both the training-noise terms introduced by estimating the centroids on the selected features and the variance contributed by selected null features.
Proof roadmap
Fix the true test label c ⋆ c^\star c ⋆ and a competitor c ≠ c ⋆ c \ne c^\star c = c ⋆ . The proof has seven steps.
(I.1) Pairwise reduction. Misclassification is contained in the union of the pairwise margin failures { Δ c ≤ 0 } \{\Delta_c \le0\} { Δ c ≤ 0 } .
(I.2) Conditional Gaussianity. Given the training data, latent means, and true test label, each margin Δ c \Delta_c Δ c is Gaussian with conditional mean m c ( D ) m_c(\mathcal{D}) m c ( D ) and variance v c ( D ) v_c(\mathcal{D}) v c ( D ) .
(I.3) HCT count consequences. HCT adaptivity makes T P 2 / ( T P + F P ) \mathrm{TP}^2/(\mathrm{TP}+\mathrm{FP}) TP 2 / ( TP + FP ) polynomially large. Consequently, for some fixed d > 0 d>0 d > 0 ,
T P ≥ p d , T P 2 F P + 1 ≥ p d \mathrm{TP} \ge p^d,\qquad\frac{\mathrm{TP}^2}{\mathrm{FP}+1} \ge p^d TP ≥ p d , FP + 1 TP 2 ≥ p d
with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . We do not need, and generally do not have, F P / T P → 0 \mathrm{FP}/\mathrm{TP}\to0 FP / TP → 0 .
(I.4) Overshoot control. Selected null and selected signal ANOVA statistics are O ( log p ) O(\log p) O ( log p ) uniformly. This keeps empirical selected contrasts on the rare-and-weak scale.
(I.5) Spherical pairwise diversity. For every fixed pair c ⋆ ≠ c c^\star\ne c c ⋆ = c , spherical symmetry implies positive average pairwise separation:
E [ v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) ] = C C − 1 . \mathbb{E}\left[v_{c^\star}^{(j)}\left(v_{c^\star}^{(j)}-v_c^{(j)}\right)\right]=\frac{C}{C-1}. E [ v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) ] = C − 1 C .
Since HCT selects polynomially many true positives, these pairwise separations concentrate over J ^ ∩ J \widehat{J}\cap J J ∩ J , giving an aggregate population margin of order τ 2 T P \tau^2\mathrm{TP} τ 2 TP uniformly over class pairs.
(I.6) No-sample-splitting stability. Although the same data are used for screening and centroid estimation, the selection-induced signal-noise term is bounded below by − o P ( τ 2 T P ) -o_{\mathbb{P}}(\tau^2\mathrm{TP}) − o P ( τ 2 TP ) . The reason is that ANOVA selection is radial in the projected class-mean vector and does not create an aggregate negative drift large enough to cancel the spherical signal margin.
(I.7) SNR divergence. The conditional mean is at least order τ 2 T P \tau^2\mathrm{TP} τ 2 TP , while the conditional variance is bounded by a true-signal term plus a selected-null term. The first is dominated by polynomial growth of TP; the second is dominated by T P 2 / ( F P + 1 ) → ∞ \mathrm{TP}^2/(\mathrm{FP}+1)\to\infty TP 2 / ( FP + 1 ) → ∞ .
Reduction to pairwise margins
Recall the score classifier (12), h ^ ( x ) = arg max a ∈ [ C ] V a ( x ) \widehat{h}(x)=\arg\max_{a\in[C]}V_a(x) h ( x ) = arg max a ∈ [ C ] V a ( x ) with
V a ( x ) : = ⟨ μ ^ a [ J ^ ] , x [ J ^ ] ⟩ . V_a(x):=\langle\widehat{\mu}_a[\widehat{J}],x[\widehat{J}]\rangle. V a ( x ) := ⟨ μ a [ J ] , x [ J ]⟩ .
For a test point X n + 1 X_{n+1} X n + 1 with true label c ⋆ c^\star c ⋆ , define the pairwise margin against competitor c ≠ c ⋆ c\ne c^\star c = c ⋆ by
Δ c : = V c ⋆ ( X n + 1 ) − V c ( X n + 1 ) = ∑ j ∈ J ^ ( μ ^ c ⋆ , j − μ ^ c , j ) X n + 1 , j . (47) \Delta_c:=V_{c^\star}(X_{n+1})-V_c(X_{n+1})=\sum_{j\in\widehat{J}}(\widehat{\mu}_{c^\star,j}-\widehat{\mu}_{c,j})X_{n+1,j}. \tag*{(47)} Δ c := V c ⋆ ( X n + 1 ) − V c ( X n + 1 ) = j ∈ J ∑ ( μ c ⋆ , j − μ c , j ) X n + 1 , j . (47)
Then
P { h ^ ( X n + 1 ) ≠ c ⋆ } ≤ ∑ c ≠ c ⋆ P { Δ c ≤ 0 } . (48) \mathbb{P}\{\widehat{h}(X_{n+1})\ne c^\star\}\le\sum_{c\ne c^\star}\mathbb{P}\{\Delta_c\le0\}. \tag*{(48)} P { h ( X n + 1 ) = c ⋆ } ≤ c = c ⋆ ∑ P { Δ c ≤ 0 } . (48)
We will prove a super-polynomial conditional error bound on one event that holds simultaneously for all class pairs with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . The complement of that event is counted once when removing the conditioning.
Conditional Gaussianity of pairwise margins
For this section, let D \mathcal{D} D denote the sigma-field generated by the training data, the latent signal set, all latent class means, and the fixed true test label c ⋆ c^\star c ⋆ . This enlarged conditioning is only a proof device; the classifier observes the training data and test feature vector. Define
a j ( D ) : = μ ^ c ⋆ , j − μ ^ c , j . a_j(\mathcal{D}):=\widehat{\mu}_{c^\star,j}-\widehat{\mu}_{c,j}. a j ( D ) := μ c ⋆ , j − μ c , j .
Lemma 13 (Conditional Gaussianity). Conditional on D \mathcal{D} D , for each c ≠ c ⋆ c \ne c^\star c = c ⋆ ,
Δ c ∣ D ∼ N ( m c ( D ) , v c ( D ) ) , (49) \Delta_c \mid\mathcal{D} \sim\mathcal{N}\left(m_c(\mathcal{D}),v_c(\mathcal{D})\right), \tag*{(49)} Δ c ∣ D ∼ N ( m c ( D ) , v c ( D ) ) , (49) where
m c ( D ) = ∑ j ∈ J ^ a j ( D ) μ c ⋆ ( j ) , (50) m_c(\mathcal{D})=\sum_{j\in\widehat{\mathcal{J}}}a_j(\mathcal{D})\mu_{c^\star}^{(j)}, \tag*{(50)} m c ( D ) = j ∈ J ∑ a j ( D ) μ c ⋆ ( j ) , (50) v c ( D ) = σ 2 ∑ j ∈ J ^ a j ( D ) 2 . (51) v_c(\mathcal{D})=\sigma^2\sum_{j\in\widehat{\mathcal{J}}}a_j(\mathcal{D})^2. \tag*{(51)} v c ( D ) = σ 2 j ∈ J ∑ a j ( D ) 2 . (51)
Proof. Given D \mathcal{D} D , the coefficients a j ( D ) a_j(\mathcal{D}) a j ( D ) are fixed. Write X n + 1 , j = μ c ⋆ ( j ) + ε j ⋆ X_{n+1,j}=\mu_{c^\star}^{(j)}+\varepsilon_j^\star X n + 1 , j = μ c ⋆ ( j ) + ε j ⋆ , where the test noises ε j ⋆ \varepsilon_j^\star ε j ⋆ are independent N ( 0 , σ 2 ) \mathcal{N}(0,\sigma^2) N ( 0 , σ 2 ) and independent of D \mathcal{D} D . Substitution in (47) gives a deterministic mean plus a centered Gaussian sum with variance σ 2 ∑ j a j 2 \sigma^2\sum_j a_j^2 σ 2 ∑ j a j 2 . □
By Mills’ bound, on the event m c ( D ) > 0 m_c(\mathcal{D})>0 m c ( D ) > 0 ,
P ( Δ c ≤ 0 ∣ D ) ≤ exp { − m c ( D ) 2 2 v c ( D ) } . (52) \mathbb{P}(\Delta_c\le0\mid\mathcal{D})\le\exp\left\{-\frac{m_c(\mathcal{D})^2}{2v_c(\mathcal{D})}\right\}. \tag*{(52)} P ( Δ c ≤ 0 ∣ D ) ≤ exp { − 2 v c ( D ) m c ( D ) 2 } . (52)
Thus the task is to prove m c ( D ) 2 / v c ( D ) → ∞ m_c(\mathcal{D})^2/v_c(\mathcal{D})\to\infty m c ( D ) 2 / v c ( D ) → ∞ with high probability.
Count consequences of HCT adaptivity
Let t ^ = π ( j ⋆ ) \hat{t}=\pi(j^\star) t ^ = π ( j ⋆ ) be the HCT threshold of Algorithm 1, and write
T P = ∣ J ^ ∩ J ∣ , F P = ∣ J ^ ∩ J c ∣ , N = T P + F P . \mathrm{TP}=|\widehat{\mathcal{J}}\cap\mathcal{J}|,\qquad\mathrm{FP}=|\widehat{\mathcal{J}}\cap\mathcal{J}^{c}|,\qquad N=\mathrm{TP}+\mathrm{FP}. TP = ∣ J ∩ J ∣ , FP = ∣ J ∩ J c ∣ , N = TP + FP .
Lemma 14 (Selected counts). If sup 0 < q < 1 E p ( q ) > 0 \sup_{0<q<1}E_p(q)>0 sup 0 < q < 1 E p ( q ) > 0 , there is a fixed d > 0 d>0 d > 0 such that, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
T P ≥ p d , (53) \mathrm{TP}\ge p^d, \tag*{(53)} TP ≥ p d , (53) T P 2 N ≥ p d , (54) \frac{\mathrm{TP}^2}{N}\ge p^d, \tag*{(54)} N TP 2 ≥ p d , (54) T P 2 F P + 1 ≥ p d . (55) \frac{\mathrm{TP}^2}{\mathrm{FP}+1}\ge p^d. \tag*{(55)} FP + 1 TP 2 ≥ p d . (55)
Proof. Theorem 8(b) proves the middle inequality with some positive exponent. Since T P ≤ N \mathrm{TP}\le N TP ≤ N , T P ≥ T P 2 / N \mathrm{TP}\ge\mathrm{TP}^2/N TP ≥ TP 2 / N . Also F P + 1 ≤ N + 1 ≤ 2 N \mathrm{FP}+1\le N+1\le2N FP + 1 ≤ N + 1 ≤ 2 N . These two inequalities prove the remaining conclusions after slightly decreasing the exponent to absorb constants. No restriction on a random selected exponent − log t ^ / log p -\log\hat{t}/\log p − log t ^ / log p is required. □
Overshoot control
The next lemmas say that selected empirical ANOVA contrasts remain on the log p \log p log p scale. This is not a weakness assumption; it is exactly what the rare-and-weak calibration λ j ≍ log p \lambda_j\asymp\log p λ j ≍ log p predicts.
Lemma 15 (Null overshoot). For any B > 0 B>0 B > 0 , there exists M 0 < ∞ M_0<\infty M 0 < ∞ such that
P ( max j ∈ J c T j > M 0 log p ) ≤ p − B . \mathbb{P}\left(\max_{j\in\mathcal{J}^c}T_j>M_0\log p\right)\le p^{-B}. P ( j ∈ J c max T j > M 0 log p ) ≤ p − B . Consequently, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
max j ∈ J ^ ∩ J c T j ≤ M 0 log p . \max_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}^c}T_j\le M_0\log p. j ∈ J ∩ J c max T j ≤ M 0 log p .
Proof. For j ∈ J c j \in\mathcal{J}^{c} j ∈ J c , T j ∼ χ k 2 T_j \sim\chi_k^2 T j ∼ χ k 2 . The standard Chernoff bound gives, for x > k x > k x > k ,
P ( χ k 2 ≥ x ) ≤ exp { − 1 2 [ x − k − k log ( x / k ) ] } . \mathbb{P}(\chi_k^2 \ge x) \le\exp\left\{-\frac{1}{2}\left[x-k-k\log(x/k)\right]\right\}. P ( χ k 2 ≥ x ) ≤ exp { − 2 1 [ x − k − k log ( x / k ) ] } .
Since k = O ( log p ) k = O(\log p) k = O ( log p ) in the regimes considered, taking x = M 0 log p x=M_0\log p x = M 0 log p with M 0 M_0 M 0 large enough gives probability at most p − ( B + 2 ) p^{-(B+2)} p − ( B + 2 ) . A union bound over at most p p p null coordinates proves the claim.
Lemma 16 (Signal overshoot). For any B > 0 B>0 B > 0 , there exists M 1 < ∞ M_1<\infty M 1 < ∞ such that
P ( max j ∈ J T j > M 1 log p ) ≤ p − B . \mathbb{P}\left(\max_{j\in\mathcal{J}} T_j>M_1\log p\right)\le p^{-B}. P ( j ∈ J max T j > M 1 log p ) ≤ p − B .
Proof. For j ∈ J j\in\mathcal{J} j ∈ J , T j ∼ χ k 2 ( λ j ) T_j\sim\chi_k^2(\lambda_j) T j ∼ χ k 2 ( λ j ) with k = O ( log p ) k=O(\log p) k = O ( log p ) , and under the spherical homogeneous calibration {(xref)}(11)–(17),
λ j = 2 r log p \lambda_j=2r\log p λ j = 2 r log p
exactly. A noncentral chi-squared Chernoff bound states that, for u > 0 u>0 u > 0 ,
P { χ k 2 ( λ ) ≥ k + λ + 2 ( k + 2 λ ) u + 2 u } ≤ e − u . \mathbb{P}\left\{\chi_k^2(\lambda)\ge k+\lambda+2\sqrt{(k+2\lambda)u}+2u\right\}\le e^{-u}. P { χ k 2 ( λ ) ≥ k + λ + 2 ( k + 2 λ ) u + 2 u } ≤ e − u .
Taking u = ( B + 2 ) log p u=(B+2)\log p u = ( B + 2 ) log p shows that T j ≤ M 1 log p T_j\le M_1\log p T j ≤ M 1 log p with probability at least 1 − p − ( B + 2 ) 1-p^{-(B+2)} 1 − p − ( B + 2 ) , uniformly over j ∈ J j\in\mathcal{J} j ∈ J , for M 1 M_1 M 1 large enough. Since ∣ J ∣ ≤ p |\mathcal{J}|\le p ∣ J ∣ ≤ p , a union bound proves the result.
Corollary 17 (Selected empirical contrast bound). With probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , for every selected feature j ∈ J ^ j\in\widehat{\mathcal{J}} j ∈ J and every pair a , b ∈ [ C ] a,b\in[C] a , b ∈ [ C ] ,
( μ ^ a , j − μ ^ b , j ) 2 ≤ 4 σ 2 n c M log p , (56) (\widehat{\mu}_{a,j}-\widehat{\mu}_{b,j})^2\le\frac{4\sigma^2}{n_c}M\log p, \tag*{(56)} ( μ a , j − μ b , j ) 2 ≤ n c 4 σ 2 M log p , (56)
where M : = max { M 0 , M 1 } M:=\max\{M_0,M_1\} M := max { M 0 , M 1 } .
Proof. The deterministic contrast bound
( μ ^ a , j − μ ^ b , j ) 2 ≤ 4 σ 2 n c T j (\widehat{\mu}_{a,j}-\widehat{\mu}_{b,j})^2\le\frac{4\sigma^2}{n_c}T_j ( μ a , j − μ b , j ) 2 ≤ n c 4 σ 2 T j
follows from Cauchy–Schwarz: μ ^ a , j − μ ^ b , j = ( e a − e b ) ⊤ P μ ^ ⋅ , j \widehat{\mu}_{a,j}-\widehat{\mu}_{b,j}=(e_a-e_b)^\top P\widehat{\mu}_{\cdot,j} μ a , j − μ b , j = ( e a − e b ) ⊤ P μ ⋅ , j and ∥ e a − e b ∥ 2 = 2 \|e_a-e_b\|^2=2 ∥ e a − e b ∥ 2 = 2 , while T j = ( n c / σ 2 ) ∥ P μ ^ ⋅ , j ∥ 2 T_j=(n_c/\sigma^2)\|P\widehat{\mu}_{\cdot,j}\|^2 T j = ( n c / σ 2 ) ∥ P μ ⋅ , j ∥ 2 . Combining this deterministic inequality with {(xref)}Lemmas 15 and 16 gives {(xref)}(56).
Spherical pairwise diversity
We next record the pairwise diversity properties of the spherical contrast directions. These properties are used to lower-bound the population part of the pairwise inner-product margin and to control the signal part of its conditional variance.
For c ⋆ ≠ c c^\star\ne c c ⋆ = c , define
B j ( c ⋆ , c ) : = v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) , D j ( c ⋆ , c ) : = ( v c ⋆ ( j ) − v c ( j ) ) 2 . B_j^{(c^\star,c)}:=v_{c^\star}^{(j)}(v_{c^\star}^{(j)}-v_c^{(j)}),\qquad D_j^{(c^\star,c)}:=(v_{c^\star}^{(j)}-v_c^{(j)})^2. B j ( c ⋆ , c ) := v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) , D j ( c ⋆ , c ) := ( v c ⋆ ( j ) − v c ( j ) ) 2 .
The variables B j ( c ⋆ , c ) B_j^{(c^\star,c)} B j ( c ⋆ , c ) control the population pairwise margin, whereas D j ( c ⋆ , c ) D_j^{(c^\star,c)} D j ( c ⋆ , c ) controls the signal part of the conditional variance.
Lemma 18 (Spherical pairwise diversity). Assume the spherical homogeneous contrast model {(xref)}(11)–(17). Let
T P : = ∣ J ^ ∩ J ∣ . T_P:=|\widehat{\mathcal{J}}\cap\mathcal{J}|. T P := ∣ J ∩ J ∣. On the event T P ≥ p d T_P\ge p^d T P ≥ p d for some fixed d > 0 d>0 d > 0 , for every fixed pair c ⋆ ≠ c c^\star\ne c c ⋆ = c ,
∑ j ∈ J ^ ∩ J v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) = C C − 1 T P + o P ( T P ) , \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}v_{c^\star}^{(j)}(v_{c^\star}^{(j)}-v_c^{(j)})
=\frac{C}{C-1}T_P+o_P(T_P), j ∈ J ∩ J ∑ v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) = C − 1 C T P + o P ( T P ) , and
∑ j ∈ J ^ ∩ J ( v c ⋆ ( j ) − v c ( j ) ) 2 = 2 C C − 1 T P + o P ( T P ) . \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}(v_{c^\star}^{(j)}-v_c^{(j)})^2
=\frac{2C}{C-1}T_P+o_P(T_P). j ∈ J ∩ J ∑ ( v c ⋆ ( j ) − v c ( j ) ) 2 = C − 1 2 C T P + o P ( T P ) .
In particular, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , uniformly over all c ⋆ ≠ c c^\star\ne c c ⋆ = c ,
∑ j ∈ J ^ ∩ J v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) ≥ 1 2 TP , \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}} v_{c^\star}^{(j)}\left(v_{c^\star}^{(j)}-v_c^{(j)}\right) \ge\frac{1}{2}\operatorname{TP}, j ∈ J ∩ J ∑ v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) ≥ 2 1 TP ,
and
∑ j ∈ J ^ ∩ J ( v c ⋆ ( j ) − v c ( j ) ) 2 ≤ 4 TP . \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}\left(v_{c^\star}^{(j)}-v_c^{(j)}\right)^2 \le4\operatorname{TP}. j ∈ J ∩ J ∑ ( v c ⋆ ( j ) − v c ( j ) ) 2 ≤ 4 TP .
Moreover, for every fixed c ⋆ c^\star c ⋆ ,
∑ j ∈ J ^ ∩ J ( v c ⋆ ( j ) ) 2 = TP + o P ( TP ) , \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}\left(v_{c^\star}^{(j)}\right)^2 = \operatorname{TP}+o_{\mathbb{P}}(\operatorname{TP}), j ∈ J ∩ J ∑ ( v c ⋆ ( j ) ) 2 = TP + o P ( TP ) ,
and hence, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
∑ j ∈ J ^ ∩ J ( v c ⋆ ( j ) ) 2 ≤ 2 TP \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}\left(v_{c^\star}^{(j)}\right)^2 \le2\operatorname{TP} j ∈ J ∩ J ∑ ( v c ⋆ ( j ) ) 2 ≤ 2 TP
uniformly over c ⋆ ∈ [ C ] c^\star\in[C] c ⋆ ∈ [ C ] .
Proof. Let
U ∼ Unif { u ∈ 1 ⊥ : ∥ u ∥ 2 = 1 } , v = C U . U\sim\operatorname{Unif}\left\{u\in\mathbf{1}^{\perp}:\|u\|_2=1\right\},\qquad v=\sqrt{C}U. U ∼ Unif { u ∈ 1 ⊥ : ∥ u ∥ 2 = 1 } , v = C U .
By rotational symmetry on the ( C − 1 ) (C-1) ( C − 1 ) -dimensional subspace 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ ,
E [ U U ⊤ ] = 1 C − 1 P . \mathbb{E}[UU^\top]=\frac{1}{C-1}P. E [ U U ⊤ ] = C − 1 1 P .
Therefore,
E [ v v ⊤ ] = C C − 1 P . \mathbb{E}[vv^\top]=\frac{C}{C-1}P. E [ v v ⊤ ] = C − 1 C P .
Since P a a = 1 − 1 / C P_{aa}=1-1/C P aa = 1 − 1/ C and P a b = − 1 / C P_{ab}=-1/C P ab = − 1/ C for a ≠ b a\ne b a = b , we get
E [ v a 2 ] = C C − 1 ( 1 − 1 C ) = 1 , \mathbb{E}[v_a^2]=\frac{C}{C-1}\left(1-\frac{1}{C}\right)=1, E [ v a 2 ] = C − 1 C ( 1 − C 1 ) = 1 ,
and, for a ≠ b a\ne b a = b ,
E [ v a v b ] = C C − 1 ( − 1 C ) = − 1 C − 1 . \mathbb{E}[v_av_b]=\frac{C}{C-1}\left(-\frac{1}{C}\right)=-\frac{1}{C-1}. E [ v a v b ] = C − 1 C ( − C 1 ) = − C − 1 1 .
Thus, for c ⋆ ≠ c c^\star\ne c c ⋆ = c ,
E [ v c ⋆ ( v c ⋆ − v c ) ] = E [ v c ⋆ 2 ] − E [ v c ⋆ v c ] = 1 + 1 C − 1 = C C − 1 , \mathbb{E}\left[v_{c^\star}\left(v_{c^\star}-v_c\right)\right]=\mathbb{E}[v_{c^\star}^2]-\mathbb{E}[v_{c^\star}v_c]=1+\frac{1}{C-1}=\frac{C}{C-1}, E [ v c ⋆ ( v c ⋆ − v c ) ] = E [ v c ⋆ 2 ] − E [ v c ⋆ v c ] = 1 + C − 1 1 = C − 1 C ,
and
E [ ( v c ⋆ − v c ) 2 ] = E [ v c ⋆ 2 ] + E [ v c 2 ] − 2 E [ v c ⋆ v c ] = 2 + 2 C − 1 = 2 C C − 1 . \mathbb{E}\left[\left(v_{c^\star}-v_c\right)^2\right]=\mathbb{E}[v_{c^\star}^2]+\mathbb{E}[v_c^2]-2\mathbb{E}[v_{c^\star}v_c]=2+\frac{2}{C-1}=\frac{2C}{C-1}. E [ ( v c ⋆ − v c ) 2 ] = E [ v c ⋆ 2 ] + E [ v c 2 ] − 2 E [ v c ⋆ v c ] = 2 + C − 1 2 = C − 1 2 C .
It remains to justify that these averages still concentrate after HCT selection. Conditional on j ∈ J j\in\mathcal{J} j ∈ J , the statistic used for selection is the ANOVA statistic. Under the spherical homogeneous calibration, its non-centrality is
λ j = 2 r log p \lambda_j=2r\log p λ j = 2 r log p
for every direction v ( j ) v^{(j)} v ( j ) . Consequently, the entire conditional distribution of a useful feature’s p p p -value depends on its spherical direction only through ∥ v ( j ) ∥ 2 2 = C \|v^{(j)}\|_2^2=C ∥ v ( j ) ∥ 2 2 = C , which is fixed. By independence across features, the vector of useful directions is independent of the full vector of p p p -values, conditional on the signal set. This also applies to the adaptive HCT selection, which is a measurable function of that p p p -value vector. Hence, conditional on the selected true-positive set J ^ ∩ J \widehat{\mathcal{J}}\cap\mathcal{J} J ∩ J and on its size TP \operatorname{TP} TP , the directions
{ v ( j ) : j ∈ J ^ ∩ J } \left\{v^{(j)}:j\in\widehat{\mathcal{J}}\cap\mathcal{J}\right\} { v ( j ) : j ∈ J ∩ J }
remain iid draws from the spherical law. For each fixed pair c ⋆ ≠ c c^\star\ne c c ⋆ = c , the variables
B j ( c ⋆ , c ) = v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) ) B_j^{(c^\star,c)} = v_{c^\star}^{(j)}\left(v_{c^\star}^{(j)}-v_c^{(j)}\right) B j ( c ⋆ , c ) = v c ⋆ ( j ) ( v c ⋆ ( j ) − v c ( j ) )
are iid with finite moments of all orders and mean C / ( C − 1 ) C/(C-1) C / ( C − 1 ) . Therefore, conditional on T P ≥ p d \mathrm{TP}\ge p^d TP ≥ p d ,
1 T P ∑ j ∈ J ^ ∩ J B j ( c ⋆ , c ) = C C − 1 + o P ( 1 ) . \frac{1}{\mathrm{TP}}\sum_{j\in\widehat{\mathcal J}\cap\mathcal J}B_j^{(c^\star,c)}
=\frac{C}{C-1}+o_P(1). TP 1 j ∈ J ∩ J ∑ B j ( c ⋆ , c ) = C − 1 C + o P ( 1 ) .
Similarly,
1 T P ∑ j ∈ J ^ ∩ J D j ( c ⋆ , c ) = 2 C C − 1 + o P ( 1 ) , \frac{1}{\mathrm{TP}}\sum_{j\in\widehat{\mathcal J}\cap\mathcal J}D_j^{(c^\star,c)}
=\frac{2C}{C-1}+o_P(1), TP 1 j ∈ J ∩ J ∑ D j ( c ⋆ , c ) = C − 1 2 C + o P ( 1 ) ,
and
1 T P ∑ j ∈ J ^ ∩ J ( v c ⋆ ( j ) ) 2 = 1 + o P ( 1 ) . \frac{1}{\mathrm{TP}}\sum_{j\in\widehat{\mathcal J}\cap\mathcal J}\left(v_{c^\star}^{(j)}\right)^2
=1+o_P(1). TP 1 j ∈ J ∩ J ∑ ( v c ⋆ ( j ) ) 2 = 1 + o P ( 1 ) .
The number of class pairs is at most C 2 C^2 C 2 . In the regimes considered in Theorem 2 , C = O ( log p ) C=O(\log p) C = O ( log p ) , while Lemma 14 gives that T P \mathrm{TP} TP is polynomially large with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . Each displayed summand is bounded in absolute value by 4 C 4C 4 C . Hoeffding’s inequality bounds deviations of their averages by 2 exp { − c ε T P / C 2 } 2\exp\{-c_\varepsilon\mathrm{TP}/C^2\} 2 exp { − c ε TP / C 2 } for every fixed ε > 0 \varepsilon>0 ε > 0 . A union bound over O ( C 2 ) O(C^2) O ( C 2 ) class pairs upgrades the fixed-pair convergence to uniform convergence over all c ⋆ ≠ c c^\star\ne c c ⋆ = c . The displayed high-probability bounds follow immediately.
One-sided stability of selected signal noise
The delicate point in the proof is that J ^ \widehat{\mathcal J} J is selected using the same training noise that appears in the empirical centroids. We first record a symmetrization identity that controls this dependence, and then use it to prove the one-sided stability bound.
Lemma 19 (Symmetrization). Let Z j ∣ μ ( j ) ∼ N ( 0 , ( σ 2 / n c ) I C ) Z_j\mid\mu^{(j)}\sim\mathcal N(0,(\sigma^2/n_c)I_C) Z j ∣ μ ( j ) ∼ N ( 0 , ( σ 2 / n c ) I C ) , let P = I C − C − 1 11 T P=I_C-C^{-1}11^\mathsf{T} P = I C − C − 1 1 1 T denote the orthogonal projection onto 1 ⊥ 1^\perp 1 ⊥ , and let
A j ( q ) : = { ∥ P μ ( j ) + P Z j ∥ 2 ≥ t q } A_j(q):=\left\{\left\|P\mu^{(j)}+PZ_j\right\|^2\ge t_q\right\} A j ( q ) := { P μ ( j ) + P Z j 2 ≥ t q } for a deterministic threshold t q > 0 t_q>0 t q > 0 . Then there exists a scalar b j , q ≥ 0 b_{j,q}\ge0 b j , q ≥ 0 such that
E [ P Z j 1 A j ( q ) ∣ μ ( j ) ] = b j , q P μ ( j ) . (57) \mathbb E\left[PZ_j1_{A_j(q)}\mid\mu^{(j)}\right]=b_{j,q}P\mu^{(j)}. \tag*{(57)} E [ P Z j 1 A j ( q ) ∣ μ ( j ) ] = b j , q P μ ( j ) . (57)
Proof. All expectations are conditional on μ ( j ) \mu^{(j)} μ ( j ) ; we suppress this from the notation. Write W : = P Z j W:=PZ_j W := P Z j and m : = P μ ( j ) m:=P\mu^{(j)} m := P μ ( j ) , both vectors in the subspace V : = 1 ⊥ V:=1^\perp V := 1 ⊥ . Then W W W is a centered Gaussian on V V V with covariance ( σ 2 / n c ) P (\sigma^2/n_c)P ( σ 2 / n c ) P , and A j ( q ) = { ∥ m + W ∥ 2 ≥ t q } A_j(q)=\{\|m+W\|^2\ge t_q\} A j ( q ) = { ∥ m + W ∥ 2 ≥ t q } depends on W W W only through ∥ m + W ∥ 2 \|m+W\|^2 ∥ m + W ∥ 2 .
Step 1: the conditional mean is parallel to m m m . If m = 0 m=0 m = 0 , then A j ( q ) A_j(q) A j ( q ) depends only on ∥ W ∥ 2 \|W\|^2 ∥ W ∥ 2 , so E [ W 1 A j ( q ) ] = 0 \mathbb E[W1_{A_j(q)}]=0 E [ W 1 A j ( q ) ] = 0 by symmetry of W W W , and the claim holds with b j , q = 0 b_{j,q}=0 b j , q = 0 . Assume m ≠ 0 m\ne0 m = 0 .
Let R R R be any orthogonal transformation of V V V that fixes m m m , i.e., R m = m Rm=m R m = m . Then
∥ m + R W ∥ 2 = ∥ R ( m + W ) ∥ 2 = ∥ m + W ∥ 2 , \|m+RW\|^2=\|R(m+W)\|^2=\|m+W\|^2, ∥ m + R W ∥ 2 = ∥ R ( m + W ) ∥ 2 = ∥ m + W ∥ 2 ,
so A j ( q ) A_j(q) A j ( q ) is R R R -invariant. Since the law of W W W on V V V is also R R R -invariant (rotational invariance of the Gaussian),
E [ W 1 A j ( q ) ] = E [ R W 1 A j ( q ) ] = R E [ W 1 A j ( q ) ] . \mathbb E[W1_{A_j(q)}]=\mathbb E[RW1_{A_j(q)}]=R\mathbb E[W1_{A_j(q)}]. E [ W 1 A j ( q ) ] = E [ R W 1 A j ( q ) ] = R E [ W 1 A j ( q ) ] .
Hence v : = E [ W 1 A j ( q ) ] v:=\mathbb E[W1_{A_j(q)}] v := E [ W 1 A j ( q ) ] is fixed by every orthogonal R R R on V V V with R m = m Rm=m R m = m . The stabilizer of m m m acts as the full orthogonal group on m ⊥ ∩ V m^\perp\cap V m ⊥ ∩ V , so any vector fixed by all such R R R must lie in span ( m ) \operatorname{span}(m) span ( m ) . Therefore
E [ W 1 A j ( q ) ] = b j , q m \mathbb E[W1_{A_j(q)}]=b_{j,q}m E [ W 1 A j ( q ) ] = b j , q m
for some scalar b j , q ∈ R b_{j,q}\in\mathbb R b j , q ∈ R .
Step 2: the scalar is nonnegative. Decompose W W W along m m m and its orthogonal complement in V V V :
W = X m ^ + W ⊥ , m ^ : = m ∥ m ∥ , X : = ⟨ W , m ^ ⟩ , W ⊥ ⊥ m ^ . W=X\widehat m+W_\perp,\qquad\widehat m:=\frac{m}{\|m\|},\qquad X:=\langle W,\widehat m\rangle,\qquad W_\perp\perp\widehat m. W = X m + W ⊥ , m := ∥ m ∥ m , X := ⟨ W , m ⟩ , W ⊥ ⊥ m .
Under the Gaussian law, X ∼ N ( 0 , σ ∗ 2 ) X \sim\mathcal{N}(0,\sigma_*^2) X ∼ N ( 0 , σ ∗ 2 ) with σ ∗ 2 : = σ 2 / n c \sigma_*^2 := \sigma^2/n_c σ ∗ 2 := σ 2 / n c , and X X X is independent of W ⊥ W_\perp W ⊥ . Taking the inner product of Step 1 with m ^ \hat m m ^ gives
b j , q ∥ m ∥ = E [ X 1 A j ( q ) ] , b_{j,q}\lVert m\rVert= \mathbb{E}[X1_{A_j(q)}], b j , q ∥ m ∥ = E [ X 1 A j ( q ) ] ,
so it suffices to show E [ X 1 A j ( q ) ] ≥ 0 \mathbb{E}[X1_{A_j(q)}] \ge0 E [ X 1 A j ( q ) ] ≥ 0 .
Conditional on W ⊥ W_\perp W ⊥ , the event A j ( q ) A_j(q) A j ( q ) becomes
{ ( ∥ m ∥ + X ) 2 + ∥ W ⊥ ∥ 2 ≥ t q } . \left\{\left(\lVert m\rVert+ X\right)^2+\lVert W_\perp\rVert^2 \ge t_q\right\}. { ( ∥ m ∥ + X ) 2 + ∥ W ⊥ ∥ 2 ≥ t q } .
We consider two cases.
Case (i): ∥ W ⊥ ∥ 2 ≥ t q \lVert W_\perp\rVert^2 \ge t_q ∥ W ⊥ ∥ 2 ≥ t q . The event holds for all X X X , so the conditional contribution is E [ X ] = 0 \mathbb{E}[X]=0 E [ X ] = 0 .
Case (ii): ∥ W ⊥ ∥ 2 < t q \lVert W_\perp\rVert^2 < t_q ∥ W ⊥ ∥ 2 < t q . Setting ρ : = t q − ∥ W ⊥ ∥ 2 > 0 \rho:= \sqrt{t_q-\lVert W_\perp\rVert^2}>0 ρ := t q − ∥ W ⊥ ∥ 2 > 0 , the event becomes { ∣ ∥ m ∥ + X ∣ ≥ ρ } \{\lvert\lVert m\rVert+X\rvert\ge\rho\} {∣∥ m ∥ + X ∣ ≥ ρ } , i.e.,
{ X ≤ a } ∪ { X ≥ b } , a : = − ∥ m ∥ − ρ , b : = − ∥ m ∥ + ρ . \{X\le a\}\cup\{X\ge b\},\qquad a:=-\lVert m\rVert-\rho,\quad b:=-\lVert m\rVert+\rho. { X ≤ a } ∪ { X ≥ b } , a := − ∥ m ∥ − ρ , b := − ∥ m ∥ + ρ .
Note that a + b = − 2 ∥ m ∥ ≤ 0 a+b=-2\lVert m\rVert\le0 a + b = − 2 ∥ m ∥ ≤ 0 , so ∣ a ∣ ≥ ∣ b ∣ \lvert a\rvert\ge\lvert b\rvert ∣ a ∣ ≥ ∣ b ∣ . Using the Gaussian truncation identities E [ X 1 { X ≤ a } ] = − σ ∗ 2 ϕ σ ∗ ( a ) \mathbb{E}[X1_{\{X\le a\}}]=-\sigma_*^2\phi_{\sigma_*}(a) E [ X 1 { X ≤ a } ] = − σ ∗ 2 ϕ σ ∗ ( a ) and E [ X 1 { X ≥ b } ] = σ ∗ 2 ϕ σ ∗ ( b ) \mathbb{E}[X1_{\{X\ge b\}}]=\sigma_*^2\phi_{\sigma_*}(b) E [ X 1 { X ≥ b } ] = σ ∗ 2 ϕ σ ∗ ( b ) , where ϕ σ ∗ \phi_{\sigma_*} ϕ σ ∗ denotes the N ( 0 , σ ∗ 2 ) \mathcal{N}(0,\sigma_*^2) N ( 0 , σ ∗ 2 ) density, the conditional contribution is
σ ∗ 2 ( ϕ σ ∗ ( b ) − ϕ σ ∗ ( a ) ) ≥ 0 , \sigma_*^2\bigl(\phi_{\sigma_*}(b)-\phi_{\sigma_*}(a)\bigr)\ge0, σ ∗ 2 ( ϕ σ ∗ ( b ) − ϕ σ ∗ ( a ) ) ≥ 0 ,
because ∣ b ∣ ≤ ∣ a ∣ \lvert b\rvert\le\lvert a\rvert ∣ b ∣ ≤ ∣ a ∣ and ϕ σ ∗ \phi_{\sigma_*} ϕ σ ∗ is decreasing in ∣ ⋅ ∣ \lvert\cdot\rvert ∣ ⋅ ∣ .
Both cases yield a nonnegative contribution, so integrating over W ⊥ W_\perp W ⊥ gives E [ X 1 A j ( q ) ] ≥ 0 \mathbb{E}[X1_{A_j(q)}]\ge0 E [ X 1 A j ( q ) ] ≥ 0 , hence b j , q ≥ 0 b_{j,q}\ge0 b j , q ≥ 0 .
Remark. Geometrically, conditioning on the radial event { ∥ m + W ∥ 2 ≥ t q } \{\lVert m+W\rVert^2\ge t_q\} {∥ m + W ∥ 2 ≥ t q } biases W W W along + m +m + m rather than − m -m − m : reaching the threshold on the + m +m + m side requires a smaller deviation than on the − m -m − m side, while rotational symmetry kills all components of the conditional mean orthogonal to m m m .
For exact F p-values the threshold is random, but independent of the class-mean noise. Conditional on the residual sum of squares U j U_j U j , the event { π j ≤ p − q } \{\pi_j\le p^{-q}\} { π j ≤ p − q } is
{ ∥ P μ ( j ) + P Z j ∥ 2 ≥ ( σ 2 n c ) k f k , m − 1 ( 1 − p − q ) U j / m } . \left\{\lVert P\mu^{(j)}+PZ_j\rVert^2\ge\left(\frac{\sigma^2}{n_c}\right)k f_{k,m}^{-1}(1-p^{-q})U_j/m\right\}. { ∥ P μ ( j ) + P Z j ∥ 2 ≥ ( n c σ 2 ) k f k , m − 1 ( 1 − p − q ) U j / m } .
Here f k , m − 1 f_{k,m}^{-1} f k , m − 1 denotes the central F quantile function. Apply Lemma 19 at this threshold and average over U j U_j U j . Its conclusion remains valid with a nonnegative scalar depending only on the common signal norm, q q q , and the model parameters.
Lemma 20 (One-sided selected-signal stability). For a ≠ b a\ne b a = b and t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , let
R a , b ( t ) = ∑ j ∈ J μ a ( j ) ( ε ˉ a , j − ε ˉ b , j ) 1 { π j ≤ t } , ε ˉ a , j = μ ^ a , j − μ a ( j ) . R_{a,b}(t)=\sum_{j\in\mathcal{J}}\mu_a^{(j)}(\bar\varepsilon_{a,j}-\bar\varepsilon_{b,j})1_{\{\pi_j\le t\}},\qquad\bar\varepsilon_{a,j}=\hat\mu_{a,j}-\mu_a^{(j)}. R a , b ( t ) = j ∈ J ∑ μ a ( j ) ( ε ˉ a , j − ε ˉ b , j ) 1 { π j ≤ t } , ε ˉ a , j = μ ^ a , j − μ a ( j ) . For every fixed d > 0 d>0 d > 0 , uniformly over all class pairs and all thresholds with TP ( t ) ≥ p d \operatorname{TP}(t)\ge p^d TP ( t ) ≥ p d ,
R a , b ( t ) ≥ − o P ( τ 2 TP ( t ) ) . R_{a,b}(t)\ge-o_P(\tau^2\operatorname{TP}(t)). R a , b ( t ) ≥ − o P ( τ 2 TP ( t )) . In particular, writing R c ( t ) = R c ⋆ , c ( t ) R_c(t)=R_{c^\star,c}(t) R c ( t ) = R c ⋆ , c ( t ) ,
R c ( t ^ ) ≥ − o P ( τ 2 TP ) R_c(\hat t)\ge-o_P(\tau^2\operatorname{TP}) R c ( t ^ ) ≥ − o P ( τ 2 TP ) simultaneously for all ordered class pairs.
Proof. Condition on J \mathcal{J} J ; expectations below average over both spherical directions and training observations, including residuals. For a fixed threshold t t t put
W j a , b = μ a ( j ) ( ε ˉ a , j − ε ˉ b , j ) , a p ( t ) = P ( π j ≤ t ∣ j ∈ J ) , m T ( t ) = ∣ J ∣ a p ( t ) . W_j^{a,b}=\mu_a^{(j)}(\bar\varepsilon_{a,j}-\bar\varepsilon_{b,j}),\qquad a_p(t)=\mathbb{P}(\pi_j\le t\mid j\in\mathcal{J}),\qquad m_T(t)=\lvert\mathcal{J}\rvert a_p(t). W j a , b = μ a ( j ) ( ε ˉ a , j − ε ˉ b , j ) , a p ( t ) = P ( π j ≤ t ∣ j ∈ J ) , m T ( t ) = ∣ J ∣ a p ( t ) .
The extended symmetrization identity for exact F selection gives
E [ W j a , b 1 { π j ≤ t } ∣ μ ( j ) ] = b t μ a ( j ) ( μ a ( j ) − μ b ( j ) ) , b t ≥ 0. \mathbb{E}[W_j^{a,b}1_{\{\pi_j\le t\}}\mid\mu^{(j)}]=b_t\mu_a^{(j)}(\mu_a^{(j)}-\mu_b^{(j)}),\qquad b_t\ge0. E [ W j a , b 1 { π j ≤ t } ∣ μ ( j ) ] = b t μ a ( j ) ( μ a ( j ) − μ b ( j ) ) , b t ≥ 0.
The scalar is common to all directions because their norms are equal. Averaging over the spherical direction therefore yields
E [ W j a , b 1 { π j ≤ t } ] = b t τ 2 C C − 1 ≥ 0. (58) \mathbb{E}[W_j^{a,b}1_{\{\pi_j\le t\}}]=b_t\tau^2\frac{C}{C-1}\ge0. \tag*{(58)} E [ W j a , b 1 { π j ≤ t } ] = b t τ 2 C − 1 C ≥ 0. (58)
There is no additional selection indicator outside this expectation; nonnegativity is asserted after averaging over the direction.
Truncation and selected second moments. Put L = log p L=\log p L = log p , σ ∗ 2 = σ 2 / n c \sigma_*^2=\sigma^2/n_c σ ∗ 2 = σ 2 / n c , and ξ j = P Z j / σ ∗ \xi_j=PZ_j/\sigma_* ξ j = P Z j / σ ∗ . Then ∥ ξ j ∥ 2 ∼ χ C 2 \|\xi_j\|^2\sim\chi^2_C ∥ ξ j ∥ 2 ∼ χ C 2 and σ ∗ 2 = C τ 2 / ( 2 r L ) \sigma_*^2=C\tau^2/(2rL) σ ∗ 2 = C τ 2 / ( 2 r L ) . Choose a fixed M M M large enough that B j = { ∥ ξ j ∥ 2 ≤ M L } B_j=\{\|\xi_j\|^2\le ML\} B j = { ∥ ξ j ∥ 2 ≤ M L } satisfies P ( B j c ) ≤ p − 12 \mathbb{P}(B_j^c)\le p^{-12} P ( B j c ) ≤ p − 12 . Since C = O ( L ) C=O(L) C = O ( L ) , the chi-square tail bound permits this choice uniformly over features. On B j B_j B j , for every class pair,
∣ W j a , b ∣ ≤ τ C 2 σ ∗ 2 M L ≤ K 0 τ 2 C . |W_j^{a,b}|\le\tau\sqrt{C}\sqrt{2\sigma_*^2}\sqrt{ML}\le K_0\tau^2C. ∣ W j a , b ∣ ≤ τ C 2 σ ∗ 2 M L ≤ K 0 τ 2 C .
For H ~ j ( t ) = W j a , b 1 B j 1 { π j ≤ t } \widetilde H_j(t)=W_j^{a,b}\mathbf{1}_{B_j}\mathbf{1}\{\pi_j\le t\} H j ( t ) = W j a , b 1 B j 1 { π j ≤ t } ,
E H ~ j ( t ) 2 ≤ K 0 2 τ 4 C 2 a p ( t ) . (59) \mathbb{E}\widetilde H_j(t)^2\le K_0^2\tau^4C^2a_p(t). \tag*{(59)} E H j ( t ) 2 ≤ K 0 2 τ 4 C 2 a p ( t ) . (59)
Also E ( W j a , b ) 2 ≤ 2 τ 2 C σ ∗ 2 \mathbb{E}(W_j^{a,b})^2\le2\tau^2C\sigma_*^2 E ( W j a , b ) 2 ≤ 2 τ 2 C σ ∗ 2 . Cauchy–Schwarz therefore bounds the lost first moment, uniformly in t t t , by K τ 2 C p − 6 K\tau^2Cp^{-6} K τ 2 C p − 6 (for all sufficiently large p p p ). After summing over at most p p p features this is o ( τ 2 ) o(\tau^2) o ( τ 2 ) , and P ( ⋃ j ∈ J B j c ) = o ( 1 ) \mathbb{P}(\bigcup_{j\in\mathcal{J}}B_j^c)=o(1) P ( ⋃ j ∈ J B j c ) = o ( 1 ) .
Uniform concentration over deterministic thresholds. Use the auxiliary quantile grid T p T_p T p of Lemma 11 . The truncated summands are independent across features conditional on J \mathcal{J} J . Bernstein’s inequality, the selected second-moment bound, and a union bound over O ( p 4 ) O(p^4) O ( p 4 ) grid points and O ( C 2 ) O(C^2) O ( C 2 ) class pairs give, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ,
∑ j ∈ J ( H ~ j ( t ) − E H ~ j ( t ) ) ≥ − K 1 τ 2 C { m T ( t ) L + L } \sum_{j\in\mathcal{J}}\left(\widetilde H_j(t)-\mathbb{E}\widetilde H_j(t)\right)
\ge-K_1\tau^2C\{\sqrt{m_T(t)L}+L\} j ∈ J ∑ ( H j ( t ) − E H j ( t ) ) ≥ − K 1 τ 2 C { m T ( t ) L + L }
simultaneously on the grid. The nonnegative untruncated mean in (58) , the lost-mean bound, and the event that all B j B_j B j hold imply
R a , b ( t ) ≥ − K 1 τ 2 C { m T ( t ) L + L } − o ( τ 2 ) R_{a,b}(t)\ge-K_1\tau^2C\{\sqrt{m_T(t)L}+L\}-o(\tau^2) R a , b ( t ) ≥ − K 1 τ 2 C { m T ( t ) L + L } − o ( τ 2 )
at every grid point, simultaneously for all pairs.
Extension to all thresholds and adaptive selection. On the no-collision event of Lemma 11 , moving any threshold to its lower adjacent grid point changes the sum by at most one truncated mark, whose absolute value is at most K 0 τ 2 C K_0\tau^2C K 0 τ 2 C . This is absorbed by the τ 2 C L \tau^2CL τ 2 C L remainder. Since m T m_T m T is nondecreasing, the same lower bound, with an enlarged constant, holds simultaneously for every t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . On thresholds with TP ( t ) ≥ p d \operatorname{TP}(t)\ge p^d TP ( t ) ≥ p d , that lemma also gives m T ( t ) = TP ( t ) ( 1 + o ( 1 ) ) m_T(t)=\operatorname{TP}(t)(1+o(1)) m T ( t ) = TP ( t ) ( 1 + o ( 1 )) uniformly. Dividing by τ 2 TP ( t ) \tau^2\operatorname{TP}(t) τ 2 TP ( t ) bounds the negative relative error by
O ( C L TP ( t ) + C L TP ( t ) ) + o ( 1 ) = o ( 1 ) , O\left(C\sqrt{\frac{L}{\operatorname{TP}(t)}}+\frac{CL}{\operatorname{TP}(t)}\right)+o(1)=o(1), O ( C TP ( t ) L + TP ( t ) C L ) + o ( 1 ) = o ( 1 ) ,
because C = O ( L ) C=O(L) C = O ( L ) and TP ( t ) ≥ p d \operatorname{TP}(t)\ge p^d TP ( t ) ≥ p d . Lemma 14 puts the selected threshold in this region with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) . Evaluation of the simultaneous bound at t ^ \hat t t ^ proves the result without conditioning on the random threshold as though it were fixed or independent of the training noise.
SNR divergence and conclusion
We now combine the preceding ingredients. Fix the true class c ∗ c^* c ∗ and a competitor c ≠ c ∗ c\ne c^* c = c ∗ . Recall from Lemma 13 that, conditional on the enlarged sigma-field D \mathcal{D} D , the pairwise margin Δ c \Delta_c Δ c is Gaussian with mean
m c ( D ) = ∑ j ∈ J ^ d ^ c ∗ c ( j ) μ c ∗ ( j ) , d ^ c ∗ c ( j ) : = μ ^ c ∗ , j − μ ^ c , j , m_c(\mathcal{D})=\sum_{j\in\widehat{\mathcal{J}}}\hat d_{c^*c}(j)\mu_{c^*}^{(j)},\qquad\hat d_{c^*c}(j):=\hat\mu_{c^*,j}-\hat\mu_{c,j}, m c ( D ) = j ∈ J ∑ d ^ c ∗ c ( j ) μ c ∗ ( j ) , d ^ c ∗ c ( j ) := μ ^ c ∗ , j − μ ^ c , j ,
and variance
v c ( D ) = σ 2 ∑ j ∈ J ^ d ^ c ∗ c ( j ) 2 . v_c(\mathcal{D})=\sigma^2\sum_{j\in\widehat{\mathcal{J}}}\hat d_{c^*c}(j)^2. v c ( D ) = σ 2 j ∈ J ∑ d ^ c ∗ c ( j ) 2 .
We show that
m c ( D ) 2 v c ( D ) → ∞ \frac{m_c(\mathcal{D})^2}{v_c(\mathcal{D})}\to\infty v c ( D ) m c ( D ) 2 → ∞
in probability, uniformly over c ≠ c ∗ c\ne c^* c = c ∗ . First decompose the conditional mean into its population part and its training-noise part:
m c ( D ) = ∑ j ∈ J ^ μ c ∗ ( j ) ( μ c ∗ ( j ) − μ c ( j ) ) + ∑ j ∈ J ^ μ c ∗ ( j ) ( ε ˉ c ∗ , j − ε ˉ c , j ) . m_c(\mathcal{D}) = \sum_{j\in\widehat{\mathcal{J}}} \mu_{c^*}^{(j)}\left(\mu_{c^*}^{(j)}-\mu_c^{(j)}\right)
+ \sum_{j\in\widehat{\mathcal{J}}} \mu_{c^*}^{(j)}\left(\bar{\varepsilon}_{c^*,j}-\bar{\varepsilon}_{c,j}\right). m c ( D ) = j ∈ J ∑ μ c ∗ ( j ) ( μ c ∗ ( j ) − μ c ( j ) ) + j ∈ J ∑ μ c ∗ ( j ) ( ε ˉ c ∗ , j − ε ˉ c , j ) .
Null coordinates have μ c ∗ ( j ) = 0 \mu_{c^*}^{(j)}=0 μ c ∗ ( j ) = 0 , so only selected signals contribute. Therefore
m c ( D ) = ∑ j ∈ J ^ ∩ J μ c ∗ ( j ) ( μ c ∗ ( j ) − μ c ( j ) ) + R c ( t ^ ) . m_c(\mathcal{D}) = \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}} \mu_{c^*}^{(j)}\left(\mu_{c^*}^{(j)}-\mu_c^{(j)}\right)+R_c(\hat{t}). m c ( D ) = j ∈ J ∩ J ∑ μ c ∗ ( j ) ( μ c ∗ ( j ) − μ c ( j ) ) + R c ( t ^ ) .
Using μ ( j ) = τ v ( j ) \mu^{(j)}=\tau v^{(j)} μ ( j ) = τ v ( j ) , the population term is
∑ j ∈ J ^ ∩ J μ c ∗ ( j ) ( μ c ∗ ( j ) − μ c ( j ) ) = τ 2 ∑ j ∈ J ^ ∩ J v c ∗ ( j ) ( v c ∗ ( j ) − v c ( j ) ) . \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}} \mu_{c^*}^{(j)}\left(\mu_{c^*}^{(j)}-\mu_c^{(j)}\right)
=\tau^2\sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}} v_{c^*}^{(j)}\left(v_{c^*}^{(j)}-v_c^{(j)}\right). j ∈ J ∩ J ∑ μ c ∗ ( j ) ( μ c ∗ ( j ) − μ c ( j ) ) = τ 2 j ∈ J ∩ J ∑ v c ∗ ( j ) ( v c ∗ ( j ) − v c ( j ) ) .
By Lemma 18, with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , uniformly over all c ∗ ≠ c c^*\ne c c ∗ = c ,
∑ j ∈ J ^ ∩ J v c ∗ ( j ) ( v c ∗ ( j ) − v c ( j ) ) ≥ 1 2 TP . \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}} v_{c^*}^{(j)}\left(v_{c^*}^{(j)}-v_c^{(j)}\right)\ge\frac{1}{2}\operatorname{TP}. j ∈ J ∩ J ∑ v c ∗ ( j ) ( v c ∗ ( j ) − v c ( j ) ) ≥ 2 1 TP .
By Lemma 20,
R c ( t ^ ) ≥ − o P ( τ 2 TP ) . R_c(\hat{t})\ge-o_{\mathrm{P}}(\tau^2\operatorname{TP}). R c ( t ^ ) ≥ − o P ( τ 2 TP ) .
Consequently,
m c ( D ) ≥ ( 1 2 − o P ( 1 ) ) τ 2 TP ≳ τ 2 TP , (60) m_c(\mathcal{D})\ge\left(\frac{1}{2}-o_{\mathrm{P}}(1)\right)\tau^2\operatorname{TP}\gtrsim\tau^2\operatorname{TP}, \tag*{(60)} m c ( D ) ≥ ( 2 1 − o P ( 1 ) ) τ 2 TP ≳ τ 2 TP , (60)
uniformly over c ≠ c ∗ c\ne c^* c = c ∗ .
We next bound the conditional variance. Write
d ^ c ∗ c ( j ) = ( μ c ∗ ( j ) − μ c ( j ) ) + ( ε ˉ c ∗ , j − ε ˉ c , j ) . \hat{d}_{c^*c}(j)=\left(\mu_{c^*}^{(j)}-\mu_c^{(j)}\right)+\left(\bar{\varepsilon}_{c^*,j}-\bar{\varepsilon}_{c,j}\right). d ^ c ∗ c ( j ) = ( μ c ∗ ( j ) − μ c ( j ) ) + ( ε ˉ c ∗ , j − ε ˉ c , j ) .
Using ( a + b ) 2 ≤ 2 a 2 + 2 b 2 (a+b)^2\le2a^2+2b^2 ( a + b ) 2 ≤ 2 a 2 + 2 b 2 ,
∑ j ∈ J ^ d ^ c ∗ c ( j ) 2 ≤ 2 ∑ j ∈ J ^ ( μ c ∗ ( j ) − μ c ( j ) ) 2 + 2 ∑ j ∈ J ^ ( ε ˉ c ∗ , j − ε ˉ c , j ) 2 . \sum_{j\in\widehat{\mathcal{J}}}\hat{d}_{c^*c}(j)^2\le2\sum_{j\in\widehat{\mathcal{J}}}\left(\mu_{c^*}^{(j)}-\mu_c^{(j)}\right)^2
+2\sum_{j\in\widehat{\mathcal{J}}}\left(\bar{\varepsilon}_{c^*,j}-\bar{\varepsilon}_{c,j}\right)^2. j ∈ J ∑ d ^ c ∗ c ( j ) 2 ≤ 2 j ∈ J ∑ ( μ c ∗ ( j ) − μ c ( j ) ) 2 + 2 j ∈ J ∑ ( ε ˉ c ∗ , j − ε ˉ c , j ) 2 .
For selected signals,
μ c ∗ ( j ) − μ c ( j ) = τ ( v c ∗ ( j ) − v c ( j ) ) , \mu_{c^*}^{(j)}-\mu_c^{(j)}=\tau\left(v_{c^*}^{(j)}-v_c^{(j)}\right), μ c ∗ ( j ) − μ c ( j ) = τ ( v c ∗ ( j ) − v c ( j ) ) ,
and therefore Lemma 18 gives
∑ j ∈ J ^ ∩ J ( μ c ∗ ( j ) − μ c ( j ) ) 2 = τ 2 ∑ j ∈ J ^ ∩ J ( v c ∗ ( j ) − v c ( j ) ) 2 ≤ 4 τ 2 TP \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}\left(\mu_{c^*}^{(j)}-\mu_c^{(j)}\right)^2
=\tau^2\sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}\left(v_{c^*}^{(j)}-v_c^{(j)}\right)^2\le4\tau^2\operatorname{TP} j ∈ J ∩ J ∑ ( μ c ∗ ( j ) − μ c ( j ) ) 2 = τ 2 j ∈ J ∩ J ∑ ( v c ∗ ( j ) − v c ( j ) ) 2 ≤ 4 τ 2 TP
with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) , uniformly over class pairs. For selected nulls, the population difference is zero.
It remains to control the empirical-noise part. By Corollary 17, selected empirical contrasts are on the rare-and-weak scale:
∑ j ∈ J ^ ∩ J ( ε ˉ c ∗ , j − ε ˉ c , j ) 2 = O P ( σ 2 log p n c TP ) , \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}}\left(\bar{\varepsilon}_{c^*,j}-\bar{\varepsilon}_{c,j}\right)^2
=O_{\mathrm{P}}\left(\frac{\sigma^2\log p}{n_c}\operatorname{TP}\right), j ∈ J ∩ J ∑ ( ε ˉ c ∗ , j − ε ˉ c , j ) 2 = O P ( n c σ 2 log p TP ) ,
and
∑ j ∈ J ^ ∩ J c ( ε ˉ c ∗ , j − ε ˉ c , j ) 2 = O P ( σ 2 log p n c FP ) . \sum_{j\in\widehat{\mathcal{J}}\cap\mathcal{J}_c}\left(\bar{\varepsilon}_{c^*,j}-\bar{\varepsilon}_{c,j}\right)^2
=O_{\mathrm{P}}\left(\frac{\sigma^2\log p}{n_c}\operatorname{FP}\right). j ∈ J ∩ J c ∑ ( ε ˉ c ∗ , j − ε ˉ c , j ) 2 = O P ( n c σ 2 log p FP ) .
Since
τ 2 = σ 2 n 2 r log p = σ 2 n c 2 r log p C , \tau^2 = \frac{\sigma^2}{n}2r\log p = \frac{\sigma^2}{n_c}\frac{2r\log p}{C}, τ 2 = n σ 2 2 r log p = n c σ 2 C 2 r log p ,
and C = O ( log p ) C = O(\log p) C = O ( log p ) , the selected-signal empirical-noise contribution is
O P ( σ 2 log p n c T P ) = O P ( C τ 2 T P ) . O_{\mathbb{P}}\left(\frac{\sigma^2\log p}{n_c}\mathrm{TP}\right) = O_{\mathbb{P}}(C\tau^2\mathrm{TP}). O P ( n c σ 2 log p TP ) = O P ( C τ 2 TP ) .
Absorbing the harmless C = O ( log p ) C = O(\log p) C = O ( log p ) factor into the subsequent SNR calculation, we obtain
v c ( D ) ≤ O P ( σ 2 C τ 2 T P ) + O P ( σ 4 log p n c F P ) , (61) v_c(\mathcal{D}) \le O_{\mathbb{P}}(\sigma^2 C\tau^2\mathrm{TP}) + O_{\mathbb{P}}\left(\frac{\sigma^4\log p}{n_c}\mathrm{FP}\right), \tag*{(61)} v c ( D ) ≤ O P ( σ 2 C τ 2 TP ) + O P ( n c σ 4 log p FP ) , (61)
uniformly over c ≠ c ⋆ c \ne c^\star c = c ⋆ .
Combining (60) and (61) ,
m c ( D ) v c ( D ) ≥ c τ 4 T P 2 σ 2 C τ 2 T P + ( σ 4 log p / n c ) F P \frac{m_c(\mathcal{D})}{v_c(\mathcal{D})} \ge\frac{c\tau^4\mathrm{TP}^2}{\sigma^2 C\tau^2\mathrm{TP} + (\sigma^4\log p/n_c)\mathrm{FP}} v c ( D ) m c ( D ) ≥ σ 2 C τ 2 TP + ( σ 4 log p / n c ) FP c τ 4 TP 2
for some constant c > 0 c > 0 c > 0 , with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) .
The first denominator term is negligible because
τ 4 T P 2 σ 2 C τ 2 T P = τ 2 T P σ 2 C = 2 r log p n C T P . \frac{\tau^4\mathrm{TP}^2}{\sigma^2 C\tau^2\mathrm{TP}} = \frac{\tau^2\mathrm{TP}}{\sigma^2 C} = \frac{2r\log p}{nC}\mathrm{TP}. σ 2 C τ 2 TP τ 4 TP 2 = σ 2 C τ 2 TP = n C 2 r log p TP .
Since n = p o ( 1 ) n = p^{o(1)} n = p o ( 1 ) , C = O ( log p ) C = O(\log p) C = O ( log p ) , and Lemma 14 gives T P ≥ p δ \mathrm{TP} \ge p^\delta TP ≥ p δ with probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) for some δ > 0 \delta> 0 δ > 0 , this ratio diverges.
For the selected-null denominator term, enlarge F P \mathrm{FP} FP to F P + 1 \mathrm{FP}+1 FP + 1 to avoid division by zero:
τ 4 T P 2 ( σ 4 log p / n c ) ( F P + 1 ) = ( ( σ 2 / n ) 2 r log p ) 2 T P 2 ( σ 4 log p / n c ) ( F P + 1 ) = 4 r 2 log p n C T P 2 F P + 1 . \frac{\tau^4\mathrm{TP}^2}{(\sigma^4\log p/n_c)(\mathrm{FP}+1)}
= \frac{((\sigma^2/n)2r\log p)^2\mathrm{TP}^2}{(\sigma^4\log p/n_c)(\mathrm{FP}+1)}
= \frac{4r^2\log p}{nC}\frac{\mathrm{TP}^2}{\mathrm{FP}+1}. ( σ 4 log p / n c ) ( FP + 1 ) τ 4 TP 2 = ( σ 4 log p / n c ) ( FP + 1 ) (( σ 2 / n ) 2 r log p ) 2 TP 2 = n C 4 r 2 log p FP + 1 TP 2 .
By Lemma 14,
T P 2 F P + 1 → ∞ \frac{\mathrm{TP}^2}{\mathrm{FP}+1} \to\infty FP + 1 TP 2 → ∞
polynomially, while n = p o ( 1 ) n = p^{o(1)} n = p o ( 1 ) and C = O ( log p ) C = O(\log p) C = O ( log p ) . Hence this ratio also diverges.
Therefore, for some fixed d ′ > 0 d' > 0 d ′ > 0 , there is an event G p G_p G p with P ( G p ) → 1 \mathbb{P}(G_p) \to1 P ( G p ) → 1 on which all ordered class pairs satisfy
m c ( D ) > 0 , m c ( D ) 2 v c ( D ) ≥ p d ′ . m_c(\mathcal{D}) > 0,\qquad\frac{m_c(\mathcal{D})^2}{v_c(\mathcal{D})} \ge p^{d'}. m c ( D ) > 0 , v c ( D ) m c ( D ) 2 ≥ p d ′ .
The polynomial lower bound, rather than mere divergence, follows from the selected-count exponents and n = p o ( 1 ) n = p^{o(1)} n = p o ( 1 ) . If a conditional variance is zero, the positive margin is deterministic. Otherwise conditional Gaussianity and a union bound over competitors give
P { h ^ ( X n + 1 ) ≠ c ⋆ } ≤ P ( G p c ) + ( C − 1 ) e − p d ′ / 2 = o ( 1 ) . \mathbb{P}\{\hat{h}(X_{n+1}) \ne c^\star\} \le\mathbb{P}(G_p^c) + (C-1)e^{-p^{d'}/2} = o(1). P { h ^ ( X n + 1 ) = c ⋆ } ≤ P ( G p c ) + ( C − 1 ) e − p d ′ /2 = o ( 1 ) .
The exceptional event is counted once, not once per competitor. Uniformity over the true class gives the unconditional result and proves Theorem 2 .