PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Rules for Control of False Discovery Rate and False Discovery Exceedance

Adel Javanmard, Andrea Montanari

arXiv:1603.09000v3math.STcs.LGstat.APstat.MEstat.MLstat.TH

TL;DR

Online FDR procedures must test hypotheses as they arrive, without access to future p-values, whereas batch methods such as BH require all p-values in advance. This paper analyzes generalized alpha-investing rules and establishes FDR control under stated conditions, alongside bounds for dependent p-values and false discovery exceedance. The authors caution that FDP can depart substantially from its expectation in some settings, motivating attention to exceedance control.

  • Problem

    Standard FDR procedures such as BH require all test p-values in advance, which is incompatible with online streams where decisions use only previous outcomes.

    Source: §1 · pp. 1–3

  • Method

    The paper studies generalized alpha-investing rules, whose wealth and test-level choices depend on past history, and derives FDR bounds for dependent p-values and false discovery exceedance.

    Source: §1.1 · p. 3

  • Results

    Generalized alpha-investing rules control FDR under a natural monotonicity condition, complementing earlier mFDR results.

    Source: §7 · p. 23

  • Takeaways & Limitations

    When FDP may depart substantially from its expectation, such as with few hypotheses or significant correlation, the authors identify FDX as a more meaningful metric and call for additional constraints.

    Source: §7 · p. 23

    The FDR guarantee for all generalized alpha-investing rules requires a natural monotonicity condition; the discussion also cautions about settings with few hypotheses or significant correlation.

    Source: §7 · p. 23

Abstract

from arXiv · show

Multiple hypothesis testing is a core problem in statistical inference and arises in almost every scientific field. Given a set of null hypotheses $\mathcal{H}(n) = (H_1,\dotsc, H_n)$, Benjamini and Hochberg introduced the false discovery rate (FDR), which is the expected proportion of false positives among rejected null hypotheses, and proposed a testing procedure that controls FDR below a pre-assigned significance level. Nowadays FDR is the criterion of choice for large scale multiple hypothesis testing. In this paper we consider the problem of controlling FDR in an "online manner". Concretely, we consider an ordered --possibly infinite-- sequence of null hypotheses $\mathcal{H} = (H_1,H_2,H_3,\dots )$ where, at each step $i$, the statistician must decide whether to reject hypothesis $H_i$ having access only to the previous decisions. This model was introduced by Foster and Stine. We study a class of "generalized alpha-investing" procedures and prove that any rule in this class controls online FDR, provided $p$-values corresponding to true nulls are independent from the other $p$-values. (Earlier work only established mFDR control.) Next, we obtain conditions under which generalized alpha-investing controls FDR in the presence of general $p$-values dependencies. Finally, we develop a modified set of procedures that also allow to control the false discovery exceedance (the tail of the proportion of false discoveries). Numerical simulations and analytical results indicate that online procedures do not incur a large loss in statistical power with respect to offline approaches, such as Benjamini-Hochberg.

1 Introduction

The introduction motivates online FDR control for streams of hypotheses, where decisions must use prior outcomes rather than future p-values. It introduces generalized alpha-investing contributions: FDR control under specified conditions, bounds for dependent p-values, and control of false discovery exceedance.

1 Introduction

  • At a fixed significance level α, expected false discoveries can be α(N − s), potentially exceeding the s true non-nulls.The introduction notes that BH controls FDR for large-scale testing, but requires the p-values to be aggregated and processed jointly.Source: §1 · pp. 2–3
  • Online tests must decide on each arriving hypothesis using prior decisions alone, while standard BH requires all p-values in advance.The setting can involve an unknown or potentially infinite number of hypotheses.Source: §1 · pp. 2–3

1.1 Contributions

  • Generalized alpha-investing rules use a wealth sequence that rises after rejection and falls otherwise, with pay-off and pay-out functions allowed to depend on past history.Unlike standard alpha investing, the pay-out need not be tightly determined by the testing level.Source: §1.1 · p. 3
  • Under independent p-values and a monotonicity condition, generalized alpha-investing rules control online FDR, extending earlier mFDR results [FS08].The paper also presents a general FDR upper bound for dependent p-values.Source: §1.1 · pp. 3–4
  • The paper develops bounds on false discovery exceedance because FDP can substantially exceed its expectation with significant probability, particularly when discoveries are few.It also develops statistical-power lower bounds under a mixture model with fixed arbitrary non-null fraction π1.Source: §1.1 · p. 4

1.2 Further related work

  • Online procedures can exceed adaptive BH's power when non-nulls are scarce and hypotheses are ordered with likely rejections first.The paper reports validation on synthetic and real data; it also discusses related work on online feature selection and ordered tests.Source: §1.1 · p. 4, §1.2 · p. 5

2 Generalized alpha investing

This section defines generalized alpha-investing rules as online tests whose test levels and wealth updates depend on past rejection decisions. It then gives alpha investing, alpha spending with rewards, and LORD as examples.

2 Generalized alpha investing

  • Generalized alpha investing extends earlier alpha-investing methods, and the section presents concrete subclasses for designing online procedures.Alpha investing was introduced by Foster and Stine, and alpha spending with rewards by Aharoni and Rosset.Source: §2 · p. 6, §2.2 · p. 7, §2.2.1 · p. 7

2.1 Definitions

  • A generalized alpha-investing rule chooses test levels, pay-outs, and pay-offs from past rejections, and updates its potential after each decision.A rejection occurs when p_j ≤ α_j; acceptance reduces potential by the pay-out, while rejection increases it by pay-off minus pay-out.Source: §2.1 · p. 6
  • The rule requires conditions on its pay-out and pay-off, and its potential remains non-negative; later FDR guarantees depend on b0 and w0.Monotonicity means test levels are non-decreasing as the prior rejection vector increases coordinatewise.Source: §2.1 · pp. 6–7

2.2.1 Alpha Investing

  • Alpha investing is a special case: rejected hypotheses earn a fixed b0, while accepted hypotheses reduce potential by α_j/(1 − α_j).Its test levels can be chosen subject to the constraint α_j/(1 − α_j) ≤ W(j − 1).Source: §2.2.1 · p. 7

2.2.2 Alpha Spending with Rewards

  • Alpha spending with rewards sets test levels proportional to pay-outs, α_j = ϕ_j/κ, while the penalties remain subject to the potential constraint.The cited example chooses ϕ_j = c1W(j − 1), with c1 ∈ (0, 1).Source: §2.2.2 · p. 7

2.2.3 LORD

  • LORD uses discovery times and accumulated wealth to set levels, adding b0 to wealth after discoveries and subtracting each test level otherwise.Its three versions differ in how test levels use discovery history; all are generalized alpha-investing rules, while LORD 1 and LORD 2 are monotone.Source: §2.2.3 · p. 8

3 Control of false discovery rate

The paper establishes FDR guarantees for generalized alpha-investing rules under independence and develops bounds and a modified rule for dependent p-values. The guarantees depend on rule conditions and, for the dependent-case Lord rule, a summability condition on its coefficients.

3.1 FDR control for independent test statistics

  • Monotone generalized alpha-investing rules control FDR when p-values are independent and the initial wealth and reward satisfy w0 + b0 ≤ α.The result also holds when true-null p-values are mutually independent and independent of non-null p-values.Source: §3.1 · p. 9
  • By Theorem 3.1 and Lemma 2.4, Lord 1 and Lord control FDR at level α when w0 + b0 ≤ α; Lord 3’s FDR guarantee cannot be obtained directly because it need not be monotone without further assumptions on γ.In numerical experiments, Lord 3 empirically controlled FDR.Source: §3.1 · p. 9
  • When discoveries are numerous with high probability, the stronger bound makes FDR(n) approximately no greater than b0.The paper gives many strong signals, even if they are a small fraction of the hypotheses, as one setting where this may occur.Source: §3.1 · p. 10
  • The paper introduces smoothed FDR, sFDRη(n), and gives a bound for it under Theorem 3.1’s assumptions.The supplied passage identifies the metric and the theorem’s scope but does not provide the bound’s formula.Source: §3.1 · p. 10
  • Without additional restrictions on the rule, the FDR and smoothed-FDR guarantees cannot be substantially improved in general.The paper constructs rules whose asymptotic FDR is at least b0 and whose smoothed FDR converges to b0.Source: §3.1 · p. 10

3.2 FDR control for dependent test statistics

  • For general p-value dependencies, the paper bounds FDR when each test level is a nondecreasing, weakly differentiable function of an index sequence.The upper bound uses these functions and their weak derivatives.Source: §3.2 · p. 11
  • The dependent-case theorem provides an upper bound for generalized alpha-investing rules, rather than an unconditional level-control guarantee.Its scope is general dependence, subject to the theorem’s index-based test-level conditions.Source: §3.2 · p. 11
  • A modified Lord rule controls FDR under general dependence when its coefficients satisfy the stated summability condition.It discounts accumulated capital at the last discovery according to the number of hypotheses tested so far; the original rule uses the number tested since that discovery.Source: §3.2 · p. 11

4 Statistical power

The paper studies online testing power under an independent mixture model and derives a lower bound for Lord’s average power. It also characterizes an asymptotically optimal choice of the rule’s γ sequence under a concavity condition.

4 Statistical power

  • The mixture model assumes independent hypotheses and p-values, with null p-values uniform and non-null p-values distributed according to F.The marginal p-value distribution is G(x) = π0x + π1F(x).Source: §4 · p. 12
  • Online procedures are favored when non-nulls appear early and disfavored when they appear later; random reordering offers an offline comparison under exchangeability.The authors describe the mixture model as an idealized but natural basis for comparing online and offline procedures.Source: §4 · p. 12
  • Lord’s average power is almost surely bounded below under the paper’s independent mixture model.The bound applies to all three versions of Lord.Source: §4 · p. 12
  • The lower bound is expected to be accurate when non-nulls are rare and discoveries are infrequent.It equals the power of a weaker rule that resets potential to b0 after each discovery; that rule is weaker only when multiple discoveries occur in a short interval.Source: §4 · p. 12
  • The paper chooses γ by maximizing a lower-bound surrogate A(G, γ) and characterizes the maximizing sequence’s asymptotic behavior.The stated result assumes F is concave and differentiable near zero and that γ is nonnegative, nonincreasing, and sums to one.Source: §4 · pp. 12–13
  • The concavity condition corresponds to a non-increasing density of non-null p-values near zero.The paper explains this as smaller p-values having higher density than larger ones in that neighborhood.Source: §4 · p. 13

5 Numerical simulations

The simulations compare online rules with adaptive BH and Bonferroni, examine how favorable ordering affects power, and contrast FDR with mFDR and sFDR. The results show that online rules control FDR in the simulated settings, while the benefits of ordering and alternative criteria depend on the setting.

5.1 Comparison with off-line rules

  • All tested rules controlled FDR below α = 0.05; BH and generalized alpha-investing rules used most of the allowed false discoveries, while Bonferroni was clearly too conservative.The generalized alpha-investing rules were somewhat more conservative than BH; these simulations used random non-null arrival times, unlike the adversarial arrivals allowed by Theorem 3.1.Source: §5.1 · p. 15, Figure 1 · p. 16
  • Lord appeared particularly effective for power at small π1, while standard alpha investing lost power at large π1 and could effectively stop after many discoveries.The paper links this behavior to αj approaching one when ϕj = αj/(1 − αj).Source: §5.1 · p. 15
  • For π1 = 0.2 and exponential alternatives, the generalized alpha-investing rules stayed below nominal FDR and tracked α fairly closely.For many discoveries, their FDR is closer to b0 than to α = b0 + w0.Source: §5.1 · p. 15, Figure 2 · p. 17

5.2 The effect of ordering

  • Power gains reached 20% with σ2 = 1 and 30% with σ2 = 1/2; Lord outperformed adaptive BH for π1 ≲0.15 and π1 ≲0.25, respectively.With favorable ordering, FDR also decreased significantly, while power increased only when the non-null fraction was not too large.Source: §5.2 · p. 17, Figure 3 · p. 18

5.3 FDR control versus mFDR control

  • Under independent p-values with many discoveries, mFDR and sFDR appeared stringent enough, but their power gain over FDR was somewhat marginal.Theorems 3.1 and 3.4 control FDR at w0 + b0 and sFDR at b0, respectively; both metrics allow b0 = α as a possible choice.Source: §5.3 · p. 18

6 Control of False Discovery Exceedance

FDR control bounds the expected false discovery proportion but can leave substantial variability in realized FDP; the paper develops online generalized alpha-investing rules to control its tail. It studies reducing test levels as a simple variance-reduction approach, then gives rules for controlling FDXγ.

6 Control of False Discovery Exceedance

  • FDR bounds the expected FDP, but realized FDP can be far from that expectation, especially when test statistics are correlated.The paper motivates FDX as a tail-probability measure to address this variability.Source: §6 · p. 19
  • The section frames FDXγ as control of the tail of FDP, providing stronger protection against large false-discovery proportions than FDR alone.The authors develop bounds on this tail probability.Source: §6 · p. 19
  • A bound on sup_n FDXγ(n) can still allow FDP=1/2 infinitely often with probability one in the paper’s example, motivating a more faithful online criterion.The paper notes that rare-time control alone does not preclude repeated large FDP values.Source: §6 · p. 19

6.1 The effect of reducing test levels

  • Reducing test levels lowers FDP variation by reducing the submartingale's conditional variance, but it also reduces statistical power.The effect on variance is more pronounced for alpha investing, though its complex dependence on history makes threshold selection difficult.Source: §6.1 · p. 20
  • At T=0.9, alpha investing has FDP above 0.15 with probability 0.13, although all three tested rules control FDR below 0.05.The figures show FDP histograms for alpha investing, alpha spending with rewards, and LORD at different T values.Source: §6.1 · p. 20, Figure 4 · p. 21, Figure 5 · p. 21

6.2 Rules for controlling FDXγ

  • Under a negative-dependency condition on test statistics, satisfied in particular by independent p-values, generalized alpha-investing rules meeting G1–G4 control FDXγ.The theorem requires G1 and G2 together with G3 and G4.Source: §6.2 · p. 22
  • For LORD, the potential W(n) remains positive, so its stopping criterion depends solely on inequality (41).More generally, a rule can stop future tests when inequality (41) is violated.Source: §6.2 · p. 22
  • In simulations, the LORD rule controls both FDR and FDXγ below α=0.05 for γ=0.15.The estimates use 30,000 realizations; Table 1 reports results across values of π1.Source: §6.2 · p. 22, Table 1 · p. 23

7 Discussion

The paper argues that monotone generalized alpha-investing rules control FDR and that Lord is appealing for its simple dependence on the most recent discovery. It also cautions that FDR may not adequately represent false-discovery proportions when those proportions vary substantially.

7 Discussion

  • All generalized alpha-investing rules control FDR when they satisfy a natural monotonicity condition.The paper presents this as reinforcing and complementing, which established mFDR control.Source: §7 · p. 23
  • Lord's testing levels depend only on the time of the most recent discovery, rather than the full testing history.The paper says this simplicity also helps its analysis, including bounds on statistical power under the mixture model.Source: §7 · p. 23
  • When the false discovery proportion can deviate substantially from its expectation, additional constraints on generalized alpha-investing rules may be needed to control FDX.The paper identifies a small number of hypotheses or significant correlation as settings where such deviation can occur.Source: §7 · p. 23

A FDR versus mFDR

This appendix contrasts FDR with mFDR and introduces sFDR. It notes that mFDR or sFDR control can permit larger initial wealth and potentially greater power than FDR control.

A FDR versus mFDR

  • The paper introduces sFDRη(n), a smoothed false discovery rate metric.The passage names the metric but does not provide its definition.Source: A FDR versus mFDR · p. 24
  • A simulation illustrates that controlling mFDR does not necessarily control FDR at a similar level.The appendix uses this contrast to motivate Theorem 3.1.Source: A FDR versus mFDR · p. 24
  • FDR control is bounded by b0 + w0, whereas sFDRw0/b0(n) and mFDRw0/b0(n) are bounded by b0.The appendix says targeting mFDR or sFDR permits larger w0 and may therefore yield greater power.Source: A FDR versus mFDR · p. 24

A.1 FDR and mFDR can be very different

The simulations compare FDR and mFDR for simple and alpha-investing procedures, then compare FDR-, mFDR-, and sFDR-oriented parameter choices. In the Gaussian example, the more liberal choice yields only a marginal power advantage while FDR appears to remain below its target.

A.1 FDR and mFDR can be very different

  • At t = 3, the single-step procedure has mFDR below 0.2 but FDR ≳0.6.Figure 7 reports FDR and mFDR for the single-step procedure in Example A.1.Source: Figure 7 · p. 25, §A.1 · p. 25
  • For the alpha-investing example, FDR is controlled at 0.05, yet the authors report that FDR and mFDR can still differ.The passage refers to Figure 8 for the comparison across fractions of non-null hypotheses.Source: §A.1 · p. 25, Figure 8 · p. 25
  • At π1 = 0.1, the reported mFDR is ≲0.001 while FDR is ≈0.04.The example uses this gap to illustrate that the metrics can differ substantially.Source: §A.1 · p. 26

A.2 Comparing FDR and mFDR with respect to statistical power

  • In the Gaussian comparison, mFDR-oriented parameters modestly increase power while FDR appears below the 0.05 target.The authors conclude that, with randomly arriving non-nulls and sufficiently many strong signals, mFDR control is conservative enough; the power advantage is described as somewhat marginal.Source: §A.2 · p. 26

B Proof of Lemma 2.4

The proof establishes that the three Lord variants satisfy Condition G1 and G2, then argues that Lord 1 and Lord 2 are monotone. The supplied proof passages give the conditions and conclusions but only fragments of the intermediate derivations.

B Proof of Lemma 2.4

  • For a later discovery time j > t1, the proof uses accumulated wealth W(τj) ≥ b0 because a discovery adds b0 to wealth.Source: B Proof of Lemma 2.4 · pp. 26, 28
  • The three Lord variants satisfy Conditions G1 and G2.For G2, the proof states that zero wealth makes the test levels zero and keeps later wealth at zero.Source: B Proof of Lemma 2.4 · p. 28
  • The proof establishes monotonicity for Lord 1 and Lord 2 using the ordering of discovery times and the non-increasing sequence γ.It also invokes w0 ≤ b0 and the rule for setting test levels.Source: B Proof of Lemma 2.4 · p. 28

C FDR for independent p-values (Proof of Theorem 3.1 and Theorem 3.3)

The proof sections establish FDR results for generalized alpha-investing rules, including independent-p-value bounds and a lower-bound analysis of their sharpness. The dependent-p-value proof uses a change of variables based on the uniformity of true-null p-values.

C FDR for independent p-values (Proof of Theorem 3.1 and Theorem 3.3)

D A lower bound on FDR

  • The lower-bound section states that Theorem 3.4 is optimal, while Theorem 3.1 is suboptimal by at most an additive term w0, absent a restricted subclass of rules.Source: D A lower bound on FDR · p. 30

E FDR for dependent p-values (Proof of Theorem 3.6)

F Examples of derivation of γopt

The examples derive optimal testing sequences for specified alternative distributions and describe how their p-value behavior affects the decay of γ_m. The FDX proof uses a submartingale and a stopping event to obtain a bound.

F Examples of derivation of γopt

G FDX control (Proof of Theorem 6.1)

H Proof of Theorem 4.1

The proof compares Lord's power with a simpler rule through a renewal-reward argument. The accompanying optimization proof uses a Lagrangian and properties of G to bound the optimized sequence.

H Proof of Theorem 4.1

  • Rule (78) makes a subset of Lord's discoveries, so its average power lower-bounds Lord's average power.Under the mixture model, inter-discovery intervals and rewards form an i.i.d. renewal-reward process.Source: H Proof of Theorem 4.1 · pp. 38–39
  • The renewal-reward analysis assigns expected reward π1 to each discovery and uses the strong law to obtain an almost-sure long-run average.Source: H Proof of Theorem 4.1 · p. 38

I Proof of Proposition 4.2

  • The optimization proof sets β_m=b0γ_m, derives a stationarity condition from the Lagrangian, and uses concavity of F and monotonicity of G for large-m bounds.Source: I Proof of Proposition 4.2 · p. 39

J Diabetes prediction data

The diabetes example applies online testing to patient risk alerts, where positive results can trigger interventions and false alerts matter. Using a predictive model and test-set p-values, generalized alpha-investing rules achieve FDR close to the target and power comparable to offline benchmarks.

J Diabetes prediction data

  • A positive diabetes-risk test can trigger an irreversible intervention, making the fraction of false-discovery alerts a relevant concern.Source: J Diabetes prediction data · p. 40
  • The dataset contains 9,948 de-identified patient records, split into Train1 (60%), Train2 (20%), and Test (20%) for model construction and online testing.Source: J Diabetes prediction data · p. 40
  • The logistic model is not optimized; it produces predictive scores used to form p-values, with null p-values uniform in expectation under exchangeability.Source: J Diabetes prediction data · pp. 40–41
  • Generalized alpha-investing rules control FDR close to 0.1 and have power comparable to offline benchmarks in the diabetes experiment.The reported results average over 20 random splits; Table 2 summarizes FDR and power.Source: Table 2 · p. 41, J Diabetes prediction data · p. 41

Related papers

Loading 1603.09000v3…