# power_of_ordered_hypothesis_testing__99719dfc.pdf

Power of Ordered Hypothesis Testing

Lihua Lei LIHUA.LEI@BERKELEY.EDU Department of Statistics, University of California, Berkeley

William Fithian WFITHIAN@BERKELEY.EDU Department of Statistics, University of California, Berkeley

Ordered testing procedures are multiple testing procedures that exploit a pre-specified ordering of the null hypotheses, from most to least promising. We analyze and compare the power of several recent proposals using the asymptotic framework of Li & Barber (2015). While accumulation tests including Forward Stop can be quite powerful when the ordering is very informative, they are asymptotically powerless when the ordering is weaker. By contrast, Selective Seq Step, proposed by Barber & Cand es (2015), is much less sensitive to the quality of the ordering. We compare the power of these procedures in different r egimes, concluding that Selective Seq Step dominates accumulation tests if either the ordering is weak or non-null hypotheses are sparse or weak. Motivated by our asymptotic analysis, we derive an improved version of Selective Seq Step which we call Adaptive Seq Step, analogous to Storey s improvement on the Benjamini-Hochberg procedure. We compare these methods using the GEOQuery data set analyzed by (Li & Barber, 2015) and find Adaptive Seq Step has favorable performance for both good and bad prior orderings.

1. Introduction

Since the invention of the Benjamini Hochberg (BH) procedure (Benjamini & Hochberg, 1995), control of the false discovery rate (FDR) has gained widespread adoption as a reasonable measure of error in multiple hypothesis testing problems. In a typical setup, we observe a sequence of p-values p1, . . . , pn corresponding to null hypotheses H1, . . . , Hn, then apply some procedure to reject a subset of them. If we make R total rejections (also called discov-

Proceedings of the 33 rd International Conference on Machine Learning, New York, NY, USA, 2016. JMLR: W&CP volume 48. Copyright 2016 by the author(s).

eries ) of which V are true nulls (false discoveries), then the false discovery proportion (FDP) and false discovery rate (FDR) are defined respectively as

FDP = V R 1, FDR = E FDP.

Let S = {i : Hi is rejected} and H0 = {i : Hi is true}, so that R = |S| and V = |S H0|.

We can classify testing problems into three types: batch testing, ordered testing and online testing. In batch testing, the ordering of hypotheses is irrelevant. The BH procedure and its many variants (e.g., Benjamini & Hochberg, 1997; Benjamini et al., 2006; Storey, 2002; Genovese et al., 2006) have been shown effective in this setting both in finite samples and asymptotically (Genovese & Wasserman, 2002; Storey, 2002; Storey et al., 2004; Ferreira & Zwinderman, 2006).

By contrast, in ordered testing, the ordering of hypotheses encodes prior information, typically telling us which hypotheses are most promising (i.e., most likely to be discoveries). For example, in genomic association studies, biologists could have prior knowledge about which genes are more likely to be associated with a disease of interest, and use this knowledge to concentrate statistical power on the more promising genes. Because prior information of this type is quite prevalent in scientific research, procedures that exploit it are attractive. Alternatively, the ordering may arise from the mathematical structure of the problem. For example, the co-integration test (Engle & Granger, 1987), which is widely used in macro-economics, involves testing Hj : rank(A) j where A is a coefficient matrix. Because the hypotheses are nested, it makes no sense to accept Hj and reject Hj+1. Other examples include sequential goodness-of-fit testing for the LASSO and other forward selection procedures such as Lockhart et al. (2014); Kozbur (2015); Fithian et al. (2015), which test Hk : M Mk 1 where M is the true model and Mk 1 is the model selected in (k 1)-th step. Section 2 reviews methods for ordered testing include Forward Stop (G Sell et al., 2015), Accumulation Tests (Li & Barber, 2015), Seq Step and Se-

Power of Ordered Hypothesis Testing

lective Seq Step (Barber & Cand es, 2015).

Finally, in online testing, the ordering of hypotheses does not necessarily encode prior knowledge; rather, it imposes a constraint on the selection procedure, requiring that we decide to accept or reject Hi before seeing data for later hypotheses. Online procedures include α-investing (Foster & Stine, 2008), generalized α-investing (Aharoni & Rosset, 2014), LOND and LORD (Javanmard & Montanari, 2015). We will not address the online setting here.

In Section 2 we summarize existing ordered testing procedures and propose a new procedure, Adaptive Seq Step (AS), generalizing Selective Seq Step (SS). Our motivation is analogous to Storey (2002) s improvement on the BH procedure. In Section 3, we introduce the varying coefficient two-groups (VCT) model and derive an explicit formula for asymptotic power of AS and SS under this model, comparing it to analogous results obtained by Li & Barber (2015) under similar asymptotic assumptions. Section 4 presents a detailed comparison of the asymptotic power of AS, SS, and accumulation tests (AT) under various regimes. In Section 5, we discuss selection of parameters and evaluate the finite-sample performance by simulation. In Section 6, we re-analyze the dosage response data from Li & Barber (2015), illustrating the predictions of our theory in real data. Section 7 concludes.

2. Ordered Testing and Adaptive Seq Step

Let π0 denote the fraction of null p-values. Unless otherwise stated, we assume that null p-values are independent of the non-null p-values, and are drawn i.i.d. from the uniform distribution U[0, 1].

We now summarize several batch testing and ordered testing procedures and relate them to each other. For all of the procedures discussed below, the set of discoveries is of the form S(s, k) = {i k : pi s}: all p-values below some threshold s, which arrive before some stopping index k. Similarly R(s, k), V (s, k), and FDP(s, k) denote the resulting values of V, R, and FDP if we select S(s, k).

Moreover, each method operates by defining some estimator of FDP(s, k), then maximizing the number of rejections R(s, k) = |S(s, k)| subject to a constraint that [ FDP(s, k) q, the target FDR control level. For example, the BH procedure rejects all Hi with pi ˆs BH = max{s : s q R(s, n)/n}, and may be formulated as

max s [0,1] R(s, n) s.t. [ FDPBH(s) q; (1)

[ FDPBH(s) = ns Pn i=1 I(pi s) 1 =

1 π0 EV (s, n)

R(s, n) 1 .

Benjamini & Hochberg (1995) show that FDRBH π0q. The procedure is very conservative when π0 is small be-

cause [ FDPBH(s) overestimates the true FDP. If π0 were known, we could reduce [ FDPBH(s) by a factor π0, obtaining a more liberal threshold s (and therefore more rejections) while still controlling the FDR at level q.

In most problems, π0 is unknown. Storey et al. (2004) propose an estimator based on counting the number of p-values above some fixed threshold λ (0, 1):

ˆπ0(λ) = 1 + Pn i=1 I(pi > λ) n(1 λ) = 1 + A(λ, n)

where A(λ, k) = k R(λ, k) = Pk i=1 I(pi > λ) counts pvalues exceeding the threshold. The logic is that, for high enough λ, the count A(λ, n) will exclude most non-null p-values (commonly λ = 0.5). The Storey-BH (SBH) procedure then modifies (1), solving instead

max s [0,λ] R(s, n) s.t. [ FDPSBH(s; λ) q;

[ FDPSBH(s; λ) = ˆπ0(λ) [ FDPBH(s)

= s 1 λ 1 + A(λ, n)

R(s, n) 1 ,

Storey et al. (2004) show that

FDRSBH (1 λ|H0|)q,

which can be much closer to q than π0q.

In ordered testing procedures, the choice variable is not the threshold s but rather the stopping index k. For example, Selective Seq Step (SS) (Barber & Cand es, 2015) rejects all hypotheses Hi with pi s and i ˆk SS where

ˆk SS = max k n

k : 1 + Pk i=1 I(pi > s) Pk i=1 I(pi s) 1 1 s

for a given s (0, 1). This can be reformulated as

max k {0,...,n} R(s, k) s.t. [ FDPSS(k; s) q;

[ FDPSS(k; s) = s 1 s 1 + A(s, k)

R(s, k) 1 .

The close resemblance between [ FDPSS(k; s) and [ FDPSBH(s; λ) suggests writing [ FDPSS as

[ FDPSS(k; s) = ˆπ0(s, k) [ FDPBH(s, k),

where the second argument k indicates evaluation on only the first k p-values.

If the threshold s is low, then A(s, k) may include many non-null p-values, leading to an upwardly-biased estimate of φ0. This observation motivates introducing an additional

Power of Ordered Hypothesis Testing

parameter to improve the procedure, analogous to the improvement of SBH over BH. Defining

[ FDPAS(k; s, λ) = s 1 λ 1 + A(λ, k)

R(s, k) 1 ,

we arrive at our proposal, which we call Adaptive Seq Step (AS): for some 0 s λ 1, reject all hypotheses with pi s and i ˆk AS, where

ˆk AS = max{k : [ FDPAS(k; s, λ) q}. (2)

If λ > s (say, s = 0.1 and λ = 0.5), then ˆπ0(λ; k) may be much less upwardly biased than ˆπ0(s; k), leading to a more powerful procedure. We investigate this power comparison in Sections 3 4.

The following theorem shows that AS achieves exact FDR control in finite samples.

Theorem 1. Let H0 {1, . . . , n} denote the set of nulls, and assume that {pi : i H0} are independent of {pi : i / H0}, and i.i.d. with distribution function F0 that stochatically dominates U[0, 1]. For ˆk AS defined as in (2),

FDR(ˆk AS; s, λ) = E

i H0,i ˆk AS I(pi s) P

i ˆk AS I(pi s) 1

The proof of Theorem 1 is given in Appendix A.

Another class of ordered testing procedures are accumulation tests (AT) (Li & Barber, 2015), which include Forward Stop (G Sell et al., 2015) and Seq Step (Barber & Cand es, 2015) as special cases. Accumulation tests estimate FDP via

[ FDPAT (k) = 1

for some function h 0 with R 1 0 h(x)dx = 1, and rejects all hypotheses Hi with i ˆk where

ˆk = max n k : [ FDPAT (k) q o .

Forward Stop corresponds to the case where h(x) = log(1 x) and Seq Step corresponds to the case where h(x) = CI(x > 1 1/C) for some C > 0.

In terms of our framework, accumulation tests solve

max k {0,...,n} R(1, k) s.t. [ FDPAT (k) q.

The main difference between AT and AS is that the former rejects all hypotheses before ˆk, while the latter rejects only those smaller than threshold s. This means that AT will

have full power if ˆk n, while the power of AS or SS is at most the average probability that a non-null p-value is less than s. On the other hand, unless nearly all of the early hypotheses are non-null, AT is likely to stop very early, as we will explore in Section 4.

3. Asymptotic Power Calculation

3.1. Varying Coefficient Two-group (VCT) Model

We now derive the asymptotic power of AS and SS under the following simple model:

Definition 1 (Varying Coefficient Two-groups (VCT) Model). An VCT(F0, F1; π( )) model is a sequence of independent p-values pi [0, 1] such that

pi (1 π (i/n)) F0 + π (i/n) F1

for some distinct distributions F0 and F1 and a nonnegative function π(t) : [0, 1] [0, 1]. F0 and F1 are the null and non-null distributions and π(t) is the local nonnull probability for k = nt.

For simplicity, we will take F0 to be uniform. Following Genovese et al. (2006), we also assume that F1 is strictly concave, so the density f1 of non-null p-values is strictly decreasing; in other words, smaller p-values imply stronger evidence against the null.

The cumulative non-null probability Π(t) is

The quantity Π(t) is essential to our results. It can be regarded as the average proportion of non-null hypotheses in the first nt-hypotheses since

#{i nt : i H0}

0 π(s)ds = Π(t).

Our setting is very similar to that of Li & Barber (2015) except that they impose conditions on Π(t) directly. Proposition 1 in Appendix B reveals the relation between the VCT model and the assumptions of Li & Barber (2015).

3.2. Asymptotic Power for AS and SS

Because the SS method is a special case of the AS method with λ = s, it is sufficient to analyze the general case of

Power of Ordered Hypothesis Testing

AS. Assuming a VCT model, for large n, we have

[ FDPAS( nt ) = s 1 λ 1 + A(λ, nt )

s 1 λ (1 Π(t))(1 λ) + Π(t)(1 F1(λ))

(1 Π(t))s + Π(t)F1(s)

= 1 + Π(t) 1 F1(λ)

1 + Π(t) F1(s)

s 1 FDP AS(t).

Because F1 is strictly concave, we have 1 F1(λ)

s , and FDP AS(t) is a strictly decreasing function of Π(t). Thus, in the limit, [ FDPAS(k) is determined by the fraction of non-nulls Π(t), with more non-nulls leading to a lower estimate of FDP. Setting FDP AS(t) = q and solving for Π(t), we obtain the critical non-null fraction

χAS(s, λ, q, F1) = 1 q

1 λ + q F1(s)

0 0.2 k n t* 0.4

FDP*(t) FDP(nt) Π(t)

Figure 1. Illustration of the asymptotic behavior of AS. The broken curves show population limits for the simulation of Section 4, with parameters set to λ = 0.5, s = q = γ = 0.2, µ = 2, b = 5. At t AS, Π(t) = χAS, leading to FDP AS(t) = q. The red curve shows a realization of [ FDPAS(nt) with n = 3000.

If Π(k/n) > χAS then, with high probability, we will have [ FDPAS(k) q, implying ˆk AS k. The proportion ˆk AS/n of scanned hypotheses is approximately

t AS = max{t : Π(t) χAS}, (4)

and the realized power is approximately

Pow AS = #{i ˆk : i H0, pi s}

#{i n : i H0}

= ˆk n #{i ˆk : i H0, pi s}/ˆk

#{i n : i H0}/n

F1(s) t ASΠ(t AS) Π(1) . (5)

Theorem 2 confirms our heuristic approximations.

Theorem 2. Consider a VCT model with

Π(t) is strictly decreasing and Lipschitz on [0, 1] with Π(1) > 0;

F0 is the uniform distribution on [0, 1] and f1 = F 1 is strictly decreasing on [0, 1].

Then ˆk AS/n a.s. t AS and

Pow AS a.s. F1(s) t ASΠ(t AS) Π(1) = F1(s)

R t AS 0 π(u)du R 1 0 π(u)du ,

with t AS defined as in (4).

Interpreting (4 5), we see that if Π(1) > χAS then t AS = 1 and ˆk AS = n with high probability: all pi < s are rejected and power is roughly F1(s). Conversely, if χAS > supt [0,1] Π(t) then ˆk AS = op(n) and the method is asymptotically powerless. Figure 1 illustrates an intermediate case with 0 < t AS < 1.

From Theorem 2 we see there are two ways to increase the asymptotic power: either increase s (which we can do directly), or increase t AS. To increase t AS we must decrease χAS(s, λ, q, F1), which itself is increasing in s and decreasing in λ.

Increasing λ always increases the asymptotic power. Because SS is a special case of AS, this implies that SS can always be improved by increasing λ above s, yielding a less biased estimator of the null fraction. Note, however, that taking λ 1 is not practical in finite samples: we still need large enough A(λ, k) for the estimator to be stable.

Increasing s has an ambiguous effect on the asymptotic power. A smaller s leads to a smaller χAS, and therefore a larger stopping index ˆk AS; however, it also applies a more stringent rejection threshold for hypotheses with i ˆk AS. By contrast, larger s is more liberal for i ˆk AS but tends to give smaller ˆk AS. If s is too large, χ could even exceed Π(0), leading to a total loss of power. Small s avoids this catastrophe: if lims 0 F1(s)/s = then lims 0 χAS = 0. This implies that we can always have nonzero power if we take s small enough, but the power

Power of Ordered Hypothesis Testing

can never exceed F1(s) even if ˆk AS n. Intuitively, then, using a large s is more aggressive, gambling that Π is large enough to overcome the larger value of χAS.

3.3. Asymptotic Power for AT

For AT, Li & Barber (2015) prove that

Pow AT a.s. t AT Π(t AT ) Π(1) (6)

where t AT = max{t : Π(t) χAT }, where

χAT (h, q, F1) = 1 q

and ν = Ep F1h(p). They also show that Seq Step, which uses h(x) = CI(x > 1 1/C) : C (0, 1), is most powerful among all accumulation tests with h bounded by C. Reparameterizing with λ = 1 1/C, we can write h(x) = 1 1 λI(x > λ). Then, ν = 1 F1(λ)

Comparing (8) with (3) and recalling that F1(s) > s by concavity, we see that χAS < χAT . Therefore, t AS t AT , implying that AT will tend to stop earlier than AS. Even so, AT could be more powerful due to the extra factor F1(s) in (5) which is absent from (6). If f1(x) = F 1(x), we have

R 1 0 h(p)f1(p)dp

R 1 0 h(p)dp inf x [0,1] f1(x),

where the last term equals f1(1) if F1 is strictly concave. Thus, for any choice of h (bounded or otherwise), we have χAT 1 q 1 f1(1).

4. Power Comparisons

In this section we analyze the results of Section 3 to extract further information about when each of AS, SS, and AT performs better or worse, and how and when the choice of s affects the performance of AS. There are three salient features of the VCT model to consider:

Signal density Π(1) = R 1 0 π(t)dt gives the expected total number of nulls. Note Π(1) = 1 π0.

Signal strength If the non-null p-values tend to be very small, we say the signals are strong.

Quality of the ordering If the prior information is very good then Π(t) is steep, with Π(0) = 1 in the limit of very good information; if the prior ordering is completely useless then Π(t) = Π(1) for all t.

First, note that if signals are very strong, then most of the non-null p-values are close to 1. In that case,

1 λ 0 χAS 1 q

1 + q F1(s)

even for relatively small values of λ, possibly including λ = s. As a result, λ plays a very small role in determining χAS and AS will behave similarly to SS. By contrast, if the signals are weaker, the difference is greater.

Second, if the ordering is very good, with Π(0) 1 and Π(t) correspondingly very steep, then we can afford to use a larger s for the AS procedure without worrying that χAS > Π(0) (though we still cannot allow χAS to exceed 1). By contrast, if the ordering is poor and Π(t) is very flat, then a small change in s could move χAS from below Π(1) (for which ˆk AS n) to above Π(0) (for which ˆk AS = op(n)), and so we are forced to be very cautious.

Finally, examining (7), we see that AT is highly aggressive compared to AS. Suppose q = 0.1. Then, regardless of the choice of h, AT is powerless unless at least 90% of the early hypotheses are non-null, requiring that either the signals are very dense or the ordering is very informative. In addition, the signals must be quite strong: even if Π(0) = 1, AT is asymptotically powerless unless

ν = Ep F1h(p) < q 1 = Ep F0h(p).

4.1. Numerical Results

We now illustrate the above comparisons with a numerical example. We consider the VCT model where F0 is uniform and F1 is the distribution of one-tailed p-values from a normal test. That is, p = Φ(z) = 1 Φ(z) where z N(µ, 1) and Φ is the standard normal CDF. Thus,

F1(x) = Φ( Φ 1(x) µ),

with µ determining the signal strength.

For the local non-null density, we take

π(t) = γe bt b 1 e b , γ (0, 1), b > 0.

The factor b/(1 e b) is a normalization constant guaranteeing Π(1) = R 1 0 π(t)dt = γ. Thus, γ determines the signal density, while b determines the quality of the prior ordering, with a larger b corresponding to a better ordering and b 0 corresponding to a useless ordering. b is implicitly upper-bounded by the constraint π(0) = γ b 1 e b 1; let bmax denote the maximal value.

Figure 2 shows the asymptotic power for four methods, all using q = 0.1: AS with s = q and λ = 0.5, AS with

Power of Ordered Hypothesis Testing

γ = 0.01 (Sparse) γ = 0.2 (Dense)

µ = 1 (Weak) µ = 2 (Strong)

0 25 50 75 0 1 2 3 4 b (non informative informative)

Asymptotic Power

Methods AT SS AS (s = q) AS (s = 0.1q)

Asymptotic Power Comparison

Figure 2. Asymptotic Power of AS (with s = q and s = 0.1q), SS (with s = q) and AT (with ν = 0) under four regimes: (sparse/weak) γ = 0.01, µ = 1; (sparse/strong) γ = 0.01, µ = 2; (dense/weak) γ = 0.2, µ = 1; (dense/strong) γ = 0.2, µ = 2. The x-axis measures b and a larger b corresponds to a more informative ordering.

s = 0.1q and λ = 0.5, SS with s = q, and AT. AT is not implemented with a specific h, but rather with ν = 0, giving the best possible power that any h could achieve. Four regimes are shown corresponding to two levels each of µ and γ: µ = 1 (weak signals) vs. µ = 2 (strong signals), and γ = 0.01 (sparse signals) vs. γ = 0.2 (dense signals). In each regime, we plot the asymptotic power of each method for b (0, bmax].

Unsurprisingly, all of the methods perform better with stronger, denser signals and better prior orderings, but their sensitivities to these parameters are quite different. Comparing the two AS methods, we see that smaller (less aggressive) s makes the method less sensitive to the ordering quality: its power is usually positive, but it is outperformed by AS(s = q) when the ordering is excellent. AT is even more aggressive than the other two, and is asymptotically powerless unless the ordering is excellent.

SS is dominated by AS(s = q) in all cases, as predicted, but the improvement is less dramatic when the signals are strong; in that case 1 F1(λ)

1 λ 0.05 and 1 F1(s)

are both small compared to 1 + q F1(s)

5. Selection of Parameters

5.1. Selecting λ

As explained in Section 3.2, a large λ reduces χAS and improves asymptotic power. However, in finite samples, the procedure will be unstable if λ is too close to 1. One natural suggestion is to set λ = 0.5, analogous to Storey s suggestion for the Storey-BH procedure (Storey et al., 2004).

5.2. Selecting s

As discussed in Section 3.2, s has an ambiguous effect on the asymptotic power. The oracle choice s , which maximizes asymptotic power, is unknown in practice and depends on knowing parameters like Π(t) and F1(x). Although we could plug in estimators of the parameters b and µ, or simply choose the value of s giving us the largest power on our data, the validity of such procedures would not be guaranteed by our results here.

In our view s > q is intuitively unappealing because it would mean using a more liberal rejection cutoff than unadjusted marginal testing. We suggest s = q as a heuristic, moderately aggressive default. This will give non-zero power as long as

1 q > 1 Π(0)

(9) can be easily derived from (3) and (4), provided λ is close to 1 such that 1 F1(λ)

1 λ 0, and is not too stringent. For example, if q = 0.1, F1(0.1) 0.5, then (9) holds provided Π(0) > 0.64. That is, if the non-nulls have reasonably strong signal and most of the early p-values are non-null, then s = q is small enough. If we do not find these values of F1(0.1) and Π(0) plausible, we can repeat this reasoning for smaller values of s until we arrive at assumptions we do find plausible.

5.3. Finite Sample Performance

Now we evaluate the finite sample performances of the above two heuristics for λ and s. Figure 3 displays the distribution of realized power for AS using λ = 0.5 vs. λ = 0.95, and s = q vs. s = s . We set q = 0.1, γ = 0.2, µ = 2, b = 3.65, in which case Π(0) = 0.75, Π(1) = 0.2. Each panel shows power for n = 100, 500, 1000, and 10, 000. For each setting we simulate 500 realizations of the fraction of all non-nulls that the method discovers. It is clear that large λ is less stable especially when n is small.

We see from Figure 3 that the performance of λ = 0.5 is more stable than that of λ = 0.95. On the other hand, the choice s = q has a comparable power to the oracle approach. This justifies the simple choice s = q as a moderately aggressive default choice for fairly strong signals and

Power of Ordered Hypothesis Testing

s = s* s = q

λ = 0.5 λ = 0.95

100 500 1000 10000 100 500 1000 10000 Sample Size

Figure 3. Finite-sample power using s {s , q} and λ {0.5, 0.95}. Red dashed line corresponds to the asymptotic power.

a good prior ordering; note however that if the signals were much weaker or the ordering much worse, s = q could be powerless.

6. Data Example: Dosage Response Data

Li & Barber (2015) analyzed the performance of several ordered testing methods using the GEOquery data of Davis & Meltzer (2007). In this section we reproduce and extend their analysis, adding the SS and AS methods as competitors. Where possible we have re-used the R code provided by Li & Barber (2015) at their website.

The GEOquery data consist of gene expression measurements at 4 different dosage levels of an estrogen treatment for breast cancer, plus control (no dose). At each of the 5 dosage levels, the gene expression of n = 22, 283 genes is measured in 5 trials. The problem is to test whether each gene is differentially expressed in the lowest dosage versus the control condition, while using data from other dosage levels to obtain a prior ordering on the genes.

For each gene, Li & Barber (2015) carry out a t-test comparing expression under the highest dose versus the expression under the lowest dose and control, pooled together. Let e Ti denote the t-statistic and pi the p-value for gene i using the high-dose data. Next, they compute one-sided permutation p-values pi comparing lowest dose to control, using the sign of e Ti to determine which side. Finally, they order the p-values p1, . . . , pn according to the ordering of p1, . . . , pn and apply an ordered testing procedure. For a more detailed explanation of the experiment, see Li & Barber (2015).

The top panel of Figure 4 reproduces Figure 6 of Li & Barber (2015) (with different axis limits), but including the SS

and AS procedures analyzed here as competing methods. Both the Hinge Exp and AS methods perform quite well compared to the other methods, with SS coming in third place. In light of the foregoing theory, we can conclude that the high-dose data are doing an excellent job discriminating between null and non-null hypotheses for example, the Hinge Exp method rejects the first 600 hypotheses at the q = 0.1 level, essentially implying that at least 540 of the first 600 genes in the ordering are truly non-null. The BH and Storey-BH methods, which are performed without any regard to the (highly informative) ordering, are unable to make any rejections.

For the lower panel of Figure 4, we repeat the same analysis, but with one change: instead of comparing with the highest dose to obtain e Ti, we instead compare with the second-lowest dose. This has the affect of attenuating the signal strength of e Ti, and thereby deteriorating the quality of the prior ordering. With a weaker ordering, all of the AT methods suffer major losses in power, so that the AS method is the clear winner, with SS in second place. As before, the BH and Storey methods have no power. This panel confirms the message of our theoretical analysis that AS and SS are more robust to weaker orderings.

Ordered with High Dose Data

Target FDR level q

# of discoveries

0.05 0.10 0.20

0 500 1000 1500 2000 2500

AT (Seq Step, C=2) AT (Hinge Exp, C=2) AT (Forward Stop) SS (s=q) AS (s=q,lam=0.5) BH Storey

Ordered with Medium Dose Data

Target FDR level q

# of discoveries

0.05 0.10 0.20

0 500 1000 1500 2000 2500

AT (Seq Step, C=2) AT (Hinge Exp, C=2) AT (Forward Stop) SS (s=q) AS (s=q,lam=0.5) BH Storey

Figure 4. Power of AS, SS, and several AT methods on the dosage response data analyzed by Li & Barber (2015).

Power of Ordered Hypothesis Testing

7. Conclusions and Future Directions

We have proposed Adaptive Seq Step (AS), which extends Selective Seq Step (SS) and improves on it in a manner analogous to Storey s improvement on the BH procedure. We have shown it controls FDR exactly in finite samples and analyzed its asymptotic power in detail, using the varying coefficient two-groups (VCT) model as a benchmark for comparing ordered testing procedures. For VCT models, we show that AS dominates SS asymptotically and outperforms AT except possibly in regimes with very good hypothesis ordering and very strong signals. Note that perfect ordering of hypotheses is implicit in the mathematical structure of many problems such as sequential goodness-of-fit testing; as a result AT could still be a suitable choice for these. Although we have proposed the heuristic s = q for selecting s, it would be interesting to investigate whether there is a good way to estimate a good s from the data.

A natural extension of AS is to allow s and λ to be different across the hypotheses. Intuitively, for those which have a higher chance to be non-null, we could use a more liberal threshold. Once the conditions for exact FDR control are established, we can derive the optimal s-sequence and λsequence under the asymptotic framework. We leave this as future work.

Another interesting direction is to compare AS and AT with BH-type methods. Genovese & Wasserman (2002) has obtained the explicit formula for the power of BH procedure and it is not hard to obtain it in our more framework. The comparison should reveal more similarities and differences between these two genres.

Finally, AS is a natural fit for the multiple knockoffs extension of the knockoffs procedure suggested at the end of Barber & Cand es (2015). Because the original knockoff procedure only produces 1-bit p-values, AS and SS are essentially equivalent, with s = λ = 0.5 the most natural settings of those parameters. However, a multipleknockoff procedure could yield p-values lying in { i k+1 : i = 1, 2, . . . , k + 1} by using k knockoffs for each predictor variable. It would be interesting to see whether using the AS instead of SS procedure would give a meaningful improvement.

Acknowledgments

We thank the anonymous reviewers for their helpful comments, which greatly improved this work.

Aharoni, Ehud and Rosset, Saharon. Generalized αinvesting: definitions, optimality results and application

to public databases. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(4):771 794, 2014.

Barber, Rina Foygel and Cand es, Emmanuel J. Controlling the false discovery rate via knockoffs. The Annals of Statistics, 43(5):2055 2085, 2015.

Benjamini, Yoav and Hochberg, Yosef. Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal Statistical Society. Series B (Methodological), pp. 289 300, 1995.

Benjamini, Yoav and Hochberg, Yosef. Multiple hypotheses testing with weights. Scandinavian Journal of Statistics, 24(3):407 418, 1997.

Benjamini, Yoav, Krieger, Abba M, and Yekutieli, Daniel. Adaptive linear step-up procedures that control the false discovery rate. Biometrika, 93(3):491 507, 2006.

Davis, Sean and Meltzer, Paul S. Geoquery: a bridge between the gene expression omnibus (geo) and bioconductor. Bioinformatics, 23(14):1846 1847, 2007.

Engle, Robert F and Granger, Clive WJ. Co-integration and error correction: representation, estimation, and testing. Econometrica: journal of the Econometric Society, pp. 251 276, 1987.

Ferreira, JA and Zwinderman, AH. On the benjamini hochberg method. The Annals of Statistics, 34(4):1827 1849, 2006.

Fithian, William, Taylor, Jonathan, Tibshirani, Robert, and Tibshirani, Ryan. Selective sequential model selection. ar Xiv preprint ar Xiv:1512.02565, 2015.

Foster, Dean P and Stine, Robert A. α-investing: a procedure for sequential control of expected false discoveries. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(2):429 444, 2008.

Genovese, Christopher R. and Wasserman, Larry. Operating characteristics and extensions of the false discovery rate procedure. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 64(3):499 517, 2002.

Genovese, Christopher R., Roeder, Kathryn, and Wasserman, Larry. False discovery control with p-value weighting. Biometrika, 93(3):509 524, 2006.

G Sell, Max Grazier, Wager, Stefan, Chouldechova, Alexandra, and Tibshirani, Robert. Sequential selection procedures and false discovery rate control. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2015.

Power of Ordered Hypothesis Testing

Javanmard, Adel and Montanari, Andrea. On online control of false discovery rate. ar Xiv preprint ar Xiv:1502.06197, 2015.

Kozbur, Damian. Testing-based forward model selection. ar Xiv preprint ar Xiv:1512.02666, 2015.

Li, Ang and Barber, Rina Foygel. Accumulation tests for fdr control in ordered hypothesis testing. ar Xiv preprint ar Xiv:1505.07352, 2015.

Lockhart, Richard, Taylor, Jonathan, Tibshirani, Ryan J, and Tibshirani, Robert. A significance test for the lasso. Annals of statistics, 42(2):413, 2014.

Storey, John D. A direct approach to false discovery rates. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 64(3):479 498, 2002.

Storey, John D, Taylor, Jonathan E, and Siegmund, David. Strong control, conservative point estimation and simultaneous conservative consistency of false discovery rates: a unified approach. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 66(1): 187 205, 2004.