PaperlayerView exact revision on arXiv

Source-linked AI summary

Higher criticism for detecting sparse heterogeneous mixtures

David Donoho, Jiashun Jin

arXiv:math/0410072v1math.STstat.TH

TL;DR

The paper asks whether a small fraction of false null hypotheses can be detected, despite their subtle effect on the upper extremes. It analyzes a significance statistic in this sparse setting and reports that higher criticism separates the hypotheses wherever the likelihood ratio test does, within the detectable region.

  • Problem

    When only a small fraction of null hypotheses are false, can we reliably distinguish that case from a zero fraction, even when nonzero means have little effect on upper extremes?

    Source: §1 · p. 3, §1.1 · p. 4

  • Method

    The paper analyzes a significance statistic in the sparse-nonnull setting and derives an adaptive optimality result for it.

    Source: §1 · p. 2

  • Results

    Higher criticism asymptotically separates the hypotheses throughout the interior region where the likelihood ratio test completely separates them.

    Source: §1.2 · p. 6

  • Takeaways & Limitations

    The result does not cover the critical detection boundary, which the paper identifies as challenging future work.

    Source: §1.2 · p. 6

    The paper leaves open whether its theory describes small-sample practice and whether its motivating examples are credible deployment scenarios.

    Source: §4 · p. 19

Abstract

from arXiv · show

Higher criticism, or second-level significance testing, is a multiple-comparisons concept mentioned in passing by Tukey. It concerns a situation where there are many independent tests of significance and one is interested in rejecting the joint null hypothesis. Tukey suggested comparing the fraction of observed significances at a given \alpha-level to the expected fraction under the joint null. In fact, he suggested standardizing the difference of the two quantities and forming a z-score; the resulting z-score tests the significance of the body of significance tests. We consider a generalization, where we maximize this z-score over a range of significance levels 0<\alpha\leq\alpha_0. We are able to show that the resulting higher criticism statistic is effective at resolving a very subtle testing problem: testing whether n normal means are all zero versus the alternative that a small fraction is nonzero. The subtlety of this ``sparse normal means'' testing problem can be seen from work of Ingster and Jin, who studied such problems in great detail. In their studies, they identified an interesting range of cases where the small fraction of nonzero means is so small that the alternative hypothesis exhibits little noticeable effect on the distribution of the p-values either for the bulk of the tests or for the few most highly significant tests. In this range, when the amplitude of nonzero means is calibrated with the fraction of nonzero means, the likelihood ratio test for a precisely specified alternative would still succeed in separating the two hypotheses.

1. Introduction.

Higher criticism is studied as an adaptive test for detecting a small fraction of nonnull hypotheses among many independent tests. The paper shows it reaches the likelihood-ratio test's asymptotic detection region in its interior and examines where the evidence for sparse alternatives appears.

1.1. The model, and the asymptotic detection boundary.

  • The model has n independent tests, with a small fraction of positive nonnull means; in the hard regime, their effects are inconspicuous in both bulk p-values and upper extremes.For εn = n^-β with β ∈ (1/2, 1), the nonnulls do not noticeably affect the bulk distribution, and their means are smaller than the largest null observations.Source: §1 · p. 2, §1.1 · p. 4

1. Introduction.

  • The paper studies higher criticism for deciding whether any nonnull hypotheses are present among many tests, a problem motivated by Tukey's second-level significance testing.The introduction cites possible settings including early bioweapons detection, covert communications, and heterogeneous meta-analysis.Source: §1 · pp. 2–3

1.1. The model, and the asymptotic detection boundary.

  • The likelihood-ratio test has a detection threshold separating asymptotically detectable from undetectable cases, but its usual form requires the sparsity and effect parameters to be specified.The threshold is expressed as a function of rarity; misspecification of r and β may cause the likelihood-ratio test to fail.Source: §1.1 · p. 4

1.2. Performance of higher criticism.

  • Higher criticism has full asymptotic power throughout the interior where the likelihood-ratio test separates sparse alternatives, but the result is silent at the critical boundary.Below the detection boundary, all methods fail.Source: §1.2 · p. 6

1.3. Which part of the sample contains the information?

  • Higher criticism searches across ordered p-values for the threshold with the strongest empirical-process discrepancy.Under the intersection null, the component p-values behave like uniform order statistics.Source: §1.2 · p. 5, §1.3 · pp. 6–7
  • The most informative evidence need not lie near the nonzero mean: when r ≤ 1/4, it occurs around 2µn on the original z-scale.At that threshold, both null and alternative observations are rare, but alternative observations are relatively more frequent.Source: §1.3 · p. 8

1.4. Comparison to several multiple comparison procedures.

The section compares higher criticism with multiple-comparison and goodness-of-fit procedures, then extends it to non-Gaussian settings. The comparisons show where competing procedures lose detection power and where higher criticism reaches the optimal detection region.

1.4.1. Range/Maximum/Bonferroni.

  • Around n^1/2 nonzero means, the maximum and studentized range can be dramatically outperformed; the figure contrasts their detection boundary with HC*'s optimal boundary.The maximum focuses on observations exceeding a threshold, whereas the figure shows the HC* boundary below the maximum-family boundary where they differ.Source: §1.4.1 · pp. 9–10, Figure 1 · p. 9

1.4.2. FDR-controlling methods.

  • FDR-controlling procedures share the maximum's detection behavior: they are effective for β ∈ [3/4,1) but relatively inefficient for β < 3/4.The comparison is for the paper's measure of performance in the sparse-mixture setting.Source: §1.4.2 · p. 11

1.5. Classical methods for combining p-values.

  • Fisher's method cannot asymptotically separate the hypotheses in this setting of extreme heterogeneity.The paper distinguishes this setting from meta-analysis, where component nonnull hypotheses are homogeneous.Source: §1.5 · p. 11, §1.4.2 · p. 11

1.6. Relation to goodness-of-fit testing.

  • Goodness-of-fit procedures maximizing over fixed intervals a < p < b are dramatically inefficient because detection information lies at p-values increasingly close to zero.The section applies this criticism to Anderson–Darling and related normalized empirical-process methods.Source: §1.6 · pp. 11–12
  • The Berk–Jones BJ+ procedure has the same detection boundary as HC*, although the section states that HC* is still better.The boundary comparison concerns power tending to one above the boundary and to zero below it.Source: §1.6 · p. 12

1.7. Generalizations.

  • In a non-Gaussian covert-signal model, HC achieves the optimal detection region, which is the same as in the Gaussian case.The model uses noncentral chi-squared observations, with signal strength parameterized by δ = 2r log(n).Source: §1.7 · pp. 12–13
  • Across other non-Gaussian settings considered in the paper, higher criticism achieves the interior of the optimal detection region.The paper presents these settings as generalizations of the sparse-nonnull testing framework.Source: §1.7 · pp. 12–13

2. Main results.

The section proves the paper's main results using empirical-process results and a case analysis of the sparse normal-means problem. The analysis distinguishes regimes where higher criticism detects alternatives that the maximum misses from those where detection is available through the maximum.

2. Main results.

  • The section pauses the narrative to prove Theorems 1.1 and 1.2 before returning to the paper's narrative format.The supplied proof passages focus on the empirical-process argument for Theorem 1.1 and a two-case analysis for Theorem 1.2.Source: §2 · p. 14, §2.1 · p. 14, §2.2 · p. 15

2.1. Proof of Theorem 1.1.

  • Theorem 1.1 follows by applying known normalized empirical-process results under the null hypothesis.The proof invokes prior results on the uniform empirical process and an approximation by a Brownian bridge.Source: §2.1 · p. 14

2.2. Proof of Theorem 1.2.

  • For r > ρ*(β) with r < 1/4, the hypothesis is detectable by HC* but not by the maximum; for r ≥ 1/4, detection, if possible, is through the maximum.The proof divides the cases according to whether the signal amplitude parameter r is below or above 1/4.Source: §2.2 · p. 15

3. A refinement.

The refinement restricts higher criticism's range to reduce the influence of the smallest p-values. This adjustment thins out heavy null tails and is reported as valuable for moderate sample sizes while retaining the full interior of the detection region.

3. A refinement.

  • The restriction retains the full interior of the detection region because the information for detection is away from the extreme smallest p-values.The section says the few smallest p-values are not relevant to the detection problem.Source: §3 · pp. 16–17
  • Restricting the maximum to p-values at least 1/n thins out the heavy null tail, while the adjustment remains valuable in moderate-sized samples despite being asymptotically unnecessary.The authors report that HC* can be effective without adjustment asymptotically, but their moderate-sample experience favors the restriction.Source: §3 · pp. 16–17
  • The smallest-p-value component gives HC* heavy tails under the null, and unusually large HC* values are often driven by that component.This motivates limiting the range over which the statistic is maximized.Source: §3 · p. 17
  • For moderate n, the proposed limiting CDF exp(−2exp(−x)) approximates HC+'s distribution fairly accurately, whereas the same limiting form fits HC* poorly empirically.The paper reports this approximation based on numerical experiments.Source: §3 · p. 17

4. Simulation.

The simulation study examines HC* and HC+ at selected detectable (r,β) settings near the detection boundary. The supplied passages emphasize that required sample sizes can become enormous near that boundary and describe an approximation for efficiently simulating very large normal samples.

4. Simulation.

  • The simulations use selected detectable (r,β) pairs above but close to the detection boundary to study the proposed statistics.The described setting includes r = 0.15 log(n) scaling, approximately 2.04 for the experiment.Source: §4 · p. 18
  • The experiment compares HC* and HC+ on null samples and samples with 1,000 observations replaced by draws from N(µ,1), repeating each condition 100 times.The resulting statistic histograms are arranged by hypothesis in rows and statistic in columns.Source: §4 · p. 18, Figure 2 · p. 18
  • Near the detection boundary, required sample sizes can become enormous, with the needed size depending on how close the setting is to the boundary.The study selects detectable (r,β) pairs above but close to the boundary; Table 1 also compares EV_n(4r) with √(2 log log n).Source: §4 · p. 18, Table 1 · p. 19
  • Whether the theory describes small-sample practice and whether the motivating examples are credible deployment scenarios are left for future discussion.The paper explicitly leaves those questions to another occasion.Source: §4 · p. 19
  • For very large n, the proposed normal-sampling approximation generates only the largest-tail samples, using about εn rather than n flops, with accuracy improving as ε shrinks.The procedure simulates K from a Poisson distribution with mean nε and then draws K uniform tail values.Source: §4 · p. 19

5. Other settings.

The paper extends higher criticism beyond the Gaussian model to chi-squared and generalized Gaussian settings. In these settings, higher criticism attains the efficient detection boundary, including cases where maximum or FDR-controlling methods are less effective.

5. Other settings.

  • Higher criticism applies beyond the Gaussian model, with the chi-squared and generalized Gaussian settings providing examples.The section presents these as broader settings for the higher-criticism principle.Source: §5 · p. 19

5.1. Chi-Squared.

  • For chi-squared observations, a small fraction of groups may contain nonzero means, and decisions use sums of squares rather than the individual normals.The paper connects ν = 2 to periodograms in covert communications and ν > 2 to replicated agricultural trials across blocks.Source: §5.1 · p. 20
  • HC* separates the null and alternative throughout the interior of the chi-squared detection region, whose boundary matches the Gaussian case.The figure distinguishes detectable, undetectable, and estimable regions; in the estimable region, nonzero means can also be estimated.Source: §5.1 · pp. 20–21, Figure 3 · p. 21

5.2. Generalized Gaussian (Subbotin) distribution.

  • For γ > 1, the detection boundary depends on γ, while for γ ≤ 1 the likelihood-ratio detection boundary is expressed independently of γ.The cited boundary for γ > 1 is given piecewise in β.Source: §5.2 · pp. 22–23
  • For generalized Gaussian distributions, higher criticism has the efficient detection boundary for the considered procedure.The paper states this result for the generalized Gaussian family GNγ.Source: §5.2 · p. 23
  • For γ ≤ 1, the most informative place to look is x = µ, and the detection boundary is the limit of the γ > 1 boundaries as γ approaches 1.The paper contrasts this with γ > 1, where the most informative location differs.Source: §5.2 · pp. 24–25
  • For γ ≈ 0 and β ≈ 1/2, HC detects when r > 2β − 1 ≈ 0, whereas maximum or FDR-controlling methods require r > 1.More generally, for γ ≤ 1, higher criticism reaches the full interior detectable region while maximum or FDR methods do not.Source: §5.2 · p. 25

A.1. Proof of Theorem 1.3.

The proof of Theorem 1.3 treats settings above the detection boundary by selecting a tail threshold and using binomial-count behavior to establish the needed result.

A.1. Proof of Theorem 1.3.

  • When r > ρ+(β), the proof chooses a constant c > 0 depending only on (r,β).The passage identifies this condition as equivalent to 1 − β > (1 − √r)^2.Source: §A.1 · p. 25
  • The proof reduces Theorem 1.3 to establishing a stated intermediate result before deriving the desired conclusion.The intermediate statement is referenced as (A.11).Source: §A.1 · pp. 25–26
  • For the selected tail probabilities, q_n,c tends to zero while n q_n,c diverges, allowing application of the binomial lemma.The lemma states that if π_n tends to zero and nπ_n diverges, then the binomial count is at least one with probability tending to one.Source: §A.1 · pp. 25–26

A.2. Proof of Theorem 1.4.

The proof of Theorem 1.4 analyzes the FDR-controlling procedure using bounds on its critical value and an auxiliary lemma. It reduces the argument to a region above the detection boundary where higher criticism has full power.

A.2. Proof of Theorem 1.4.

  • The proof invokes Lemma A.3, attributed to, to obtain the desired intermediate result.The appendix states that Lemma A.3 follows directly from, Lemma 1.Source: §A.2 · pp. 26–27
  • The FDR-procedure proof considers critical values h(n,α_n) bounded by a < 1 and focuses on r between the detection boundary and the stated upper limit.The passage says attainability of the FDR-controlling procedure is as good as the maximum or Bonferroni method.Source: §A.2 · p. 27
  • The argument uses a choice of δ₀ close enough to 1 under the stated condition, then applies Lemma A.4 to conclude the desired result.The passage compares probabilities under the two hypotheses for the event involving F_{δ₀}.Source: §A.2 · pp. 27–28

A.3. Proof of Theorem 1.5.

The proof uses direct calculations under the alternative to compare the statistic’s expectation and variance with their null-scale values.

A.3. Proof of Theorem 1.5.

  • The alternative is parameterized with ε_n = n^−β and a nonzero mean μ_n.The supplied passage truncates the definition of μ_n.Source: §A.3 · p. 28
  • For 1/2 < β < 1, the proof calculates the statistic’s expectation and variance under H(n) using ε_n = n^−β.The displayed estimates are stated with relative terms O(ε_n L_n).Source: §A.3 · p. 28
  • The proof states that the conclusion follows because β > 1/2.The preceding displayed expectation and variance expressions are partially truncated in the passage.Source: §A.3 · p. 28

A.4. Proof of Theorem 1.6.

The proof analyzes BJ+ under the alternative across two overlapping cases in the region 1/2 < β < 1 and r > ρ*(β). It reports that HC* is more powerful than BJ+ in the second case.

A.4. Proof of Theorem 1.6.

  • The two cases overlap and together cover the region 1/2 < β < 1, r > ρ*(β).The proof treats r < β/3 separately from the other case.Source: §A.4 · p. 29
  • In the second case, HC* is more powerful than BJ+.Source: §A.4 · p. 30
  • BJ+ chooses the largest i for which (i/n)/p(i) ≫ 1.The passage relates this choice roughly to i ∼ n^(1−q).Source: §A.4 · p. 30
  • HC* has better performance than BJ+ when ρ*(β) < r < 1 − β, with (HC*)^2 ≈ L_n n^(2r−β+1).The passage compares this rate with 1 − (r + β)^2/(4r).Source: §A.4 · p. 30

A.5. Proof of Lemma 5.1.

The proof of Lemma 5.1 divides its analysis into cases according to ν and evaluates an integral.

A.5. Proof of Lemma 5.1.

  • The proof treats ν = 1, ν = 2, and ν ≥ 3 as separate cases.It calls the ν = 1 case obvious and then proceeds to the higher cases.Source: §A.5 · p. 31
  • For ν ≥ 3, the proof identifies θ₁ = π as the point of maximum rate of growth in the stated expression.Source: §A.5 · p. 31
  • The proof proceeds by evaluating an integral.Source: §A.5 · pp. 31–32

Related papers

Loading math/0410072v1…