We extend generalized α-investing to address the problem of online FDR control where the cost of data is not negligible. Our specific contributions are: •

a theoretical analysis of the long term asymptotic behavior of α-wealth in an α-investing procedure,

Tukey proposed the notion of α-wealth to control the family-wise error rate for a sequence of tests [26, 27]. Foster and Stine [13] proposed α-investing, an online procedure that controls the marginal FDR (mFDR) for any stopping time in the testing sequence. Aharoni and Rosset [1] introduced generalized α-investing and provided a deterministic decision rule to maximize the expected reward for the next test in the sequence. Recently, there has been much work on online FDR control in the context of A/B testing, directed acyclic graphs and quality-preserving databases [31, 20]. Javanmard and Montanari [14] first proved that generalized α-investing controls FDR, not only mFDR under an online setting with an algorithm called LORD. Ramdas et. al. [18] proposed the LORD++ to improve the existing LORD. Recent work leverages contextual information in the data to improve the statistical power while controlling FDR offline [29] and online [7]. Ramdas et. al. [19] then proposed SAFFRON, which also belongs to the α-investing framework but adaptively estimates the proportion of the true nulls. All the aforementioned methods are synchronous, which means that each test can only start once the previous test has finished. Zrnic at. al. [34] extend α-investing methods to an asynchronous setting where tests are allowed to overlap in time. These state-of-the-art online FDR control α-investing methods do not address the needs for testing when the cost of data is not negligible. So, we propose a novel α-investing method for a setting that takes into account the cost of data sample collection, the sample size choice, and prior beliefs about the probability of rejection.

Section 2 is a technical background of generalized α-investing. Section 3 contains a theoretical analysis of the long term asymptotic behavior of the α-wealth. Section 4 presents a cost-aware generalized α-investing decision rule based on the game-theoretic equalizing strategy. Section 5 presents empirical experiments that show that the cost-aware ERO decision rule improves upon existing procedures when data collection costs are nontrivial. Section 6 presents analysis of two real data sets from gene expression studies that shows cost-aware α-investing aligns with the overall objectives of the application setting. Finally, Section 7 describes limitations and future work.

A key contribution of this work is a procedure for selecting the amount of α-wealth to commit to a given hypothesis test, φ j . Aharoni and Rosset [1] leave φ j up to the investigator and provide several ways of selecting it: constant, relative, and relative-200. Given a value of φ j , the variables α j , ρ j , and ψ j are chosen such that the expected reward, E θ ( R j ) ψ j is maximized. In their simulation studies, the choice of φ j is such that under the data-generating process one is expected to see one true alternative hypothesis before α-death. This section develops a principled method of setting φ j via a strategy for a two-player zero-sum game between the investigator and nature.

Suppose that we have a zero-sum game involving two players: the investigator (Player I) and nature (Player II). The investigator has two strategies – to test or to not test a hypothesis. Nature, independent of the investigator, chooses to hide θ j ∈ H j with probability q j and θ j ∉ H j otherwise. The utility function for this game is the change in α-wealth. The payoff matrix for the game is provided in Table 1.

If the investigator chooses not to conduct the test, there is no cost ( φ j = 0) and there is no reward ( ψ j = 0) regardless of what nature has chosen. So, the change in α-wealth when not conducting a test is zero. If the investigator chooses to conduct a test, and nature has hidden θ j ∈ H j , then the payout is − φ j with probability 1 − α j , or − φ j + ψ j with probability α j . In expectation, this payout is − φ j + α j ψ j . Similarly, if the investigator chooses to conduct the test and nature has hidden θ j ∉ H j , then the expected payout is − φ j + ρ j ψ j . The mixed strategy of nature is known to be ( q j , 1 − q j ). What remains to be determined in this game are the unknowns in the payoff matrix, as well as the investigator’s strategy. We choose to set the payoffs such that the expected change in α-wealth is identical for both of the investigator’s strategies. By designing the payoff matrix conditioned on nature’s mixed strategy, such that the investigator has the same expected payoff for both pure (and any mixed) strategies, the investigator’s choice to test or not test a hypothesis has no effect (in expectation) on the ability to perform future tests. With these properties, nature is employing an equalizing strategy.

The result is the investigator is indifferent as to whether to test or not test and the expected payoff is (4.1) q j ( − φ j + α j ψ j ) + ( 1 − q j ) ( − φ j + ρ j ψ j ) = 0 . Since the expected payoff for not testing is 0, this equation ensures that the expected change in α-wealth when testing is also 0. By definition, this gives a self contained decision rule that makes α-wealth martingale, striking a balance between the two scenarios given in Theorem 1 and Theorem 2.

Theorem 3 provides a condition on the power of the test which requires a balance between the ratio of φ j and ψ j and the probability of a false positive.

Allowing φ j to be a free variable in the optimization problem leads us to an infinite number of ERO-class solutions. Selecting the maximum of this class would lead to aggressive play, and in many situations leads to betting the farm or bold play. The martingale constraint, (4.2), reduces the solution space to a single nontrivial solution and a trivial solution where φ j = ψ j = α j = 0. Furthermore, the fact that the expected reward is constrained to be zero by (4.2) means that the ERO optimization problem is a feasibility problem. Even so, we retain the objective function in the optimization problem in anticipation for the next section where we allow for variable sample sizes n j .

The investigator may additionally wish to limit the variance of their wealth process. This can be accomplished by setting an upper bound on the proportion of wealth an investigator may spend for an ante. Furthermore, the investigator may wish to lower bound the power of an individual test. In order to satisfy these conditions, the investigator will collect more samples for an individual hypothesis in order to meet their power requirement. We choose to impose a lower bound constraint on the power for this reason.

In the previous section n j was held fixed; we now consider n j as a free variable in our optimization problem. As a result, ρ j is no longer completely determined by α j and one can increase ρ j via increasing n j . In scientific applications, the investigator is also constrained by sample collection costs, and would not wish to spend excessively on a single hypothesis test. We modify the generalized α-investing decision rule, (2.6), to include a notion of dollar-wealth W $ ( j ) available for expenditure to collect data to test the j-th hypothesis (4.3) ( φ j , α j , ψ j , n j ) = I ( W α ( 0 ) , W $ ( 0 ) ) ( { R 1 , … , R j − 1 } ) , where n j is the sample size allocated for testing of the j-th hypothesis. A natural update for the dollar-wealth is (4.4) W $ ( 0 ) = B (4.5) W $ ( j ) = W $ ( j − 1 ) − c j n j , where c j is the per-sample cost for data to test the j-th hypothesis, and B is the initial dollar-wealth. Allowing the cost to vary with the hypothesis test enables one to model different experimental methods and cost inflation for long-term experimental plans.

Since n j is a free variable under the control of the investigator, we again have many solutions to the ERO problem. Furthermore, as n j increases up to the allowable expenditure of sample resources, so does the power and therefore the expected reward. Theoretically, the optimal solution allocates all the sample budget available even though the marginal increase in power and thus the expected reward, is vanishingly small for large n j . To address this issue, we modify the objective function to include a small penalty for increasing sample size,2²

We thank an anonymous reviewer for this suggestion.

The investigator’s goal is to conduct as many tests as possible while rejecting as many true alternatives as possible and maintaining control of the false discovery rate. Incorporating the methods for optimizing φ j and n j into the ERO problem yields a self-contained decision rule in the form of (4.3),

The standard ERO framework optimizes only the one-step expected return, E θ ( R j ) ψ j . But, when tests are expensive, it is logical to consider the expected return after two (or more) tests. We consider q j to be known, and extend the game theoretic framework to a finite horizon of decisions. The extensive form of the game between nature, who hides θ j in the null or alternative hypothesis region, and the investigator, who seeks to find θ j and gain the reward for doing so, is shown in Figure 2. We note that sequential two-step cost-aware ERO investing is a different problem than batch ERO investing because two-step investing accounts for the expected change in ( α , $ )-wealth after each step while batch cost-aware ERO only received the payoff at the conclusion of all of the tests in the batch.

The two-step objective function is (4.7) E ( R j ψ j + R j + 1 ψ j + 1 ) = E ( R j ) ψ j + ψ j + 1 [ P ( R j = 0 ) E ( R j + 1 | R j = 0 ) + P ( R j = 1 ) E ( R j + 1 | R j = 1 ) ] with constraints (4.6b)-(4.6i) from Problem 4.6 remaining for steps j and j + 1. Designing the game so that nature’s strategy is an equalizing strategy results in a system of equations (Appendix G) that form constraints in the ERO optimization problem. It is worth noting that such a game simplifies to the standard cost-aware ERO method defined in 4.6 when W $ > > 0. This holds since the parameters of the second test depend on the expected α-wealth available at that step. When the expected increment is 0, as set in constraint (4.6i), and when available $-wealth is not scarce, then each step is equivalent to optimization occurring on the first test. When this constraint is lifted, or when the available W $ is low, the finite horizon solution provides a different solution to the single step solution.

Table 2 compares our method, cost-aware ERO, with related state-of-the-art α-investing methods including: α-spending [27], α-investing [13], α-rewards [1], ERO-investing [1], LORD [14, 18], and SAFFRON [19]. The table is indexed by the allocation scheme (Scheme), and the reward method (Method). The allocation scheme determines the value of φ j at each step, which in many cases is left to user discretion. We implement the φ-allocation schemes proposed by Aharoni and Rosset [1]. The constant scheme simply allocates, φ j = min 1 10 W α ( 0 ) , W α ( j − 1 ) , for each test, the relative scheme allocates an amount that is proportional to the remaining α-wealth, φ j = 1 10 W α ( j − 1 ) and continues until W α ( j ) < ( 1 / 1000 ) W α ( 0 ). The relative 200 scheme follows the same proportional steps as the relative, but always performs 200 tests [1]. The results from our implementation of these methods matches or exceeds previously reported results.

ERO investing yields more true rejects than α-spending, α-investing, and both α-rewards methods. The LORD variants and SAFFRON perform the maximum number of tests while maintaining control of the mFDR. For the use scenarios considered in the LORD and SAFFRON papers (large-scale A/B testing), this is optimal — tests are nearly free and the goal is to be able to keep testing while maintaining mFDR control. The cost-aware ERO setting is different and more applicable to biological experiments where one aims to maximize a limited budget of tests to achieve as many true rejects as possible while controlling the mFDR. Increasing the sample size capacity for each test enables cost-aware ERO to achieve higher power with fewer tests than the current state-of-the-art methods with n = 1. For fair comparison, we varied n for LORD++ and include the sample size which maximized the number of true rejections. This selection was performed after running all considered sample sizes. It is important to note that the investigator would not have access to such information in a real experiment. Releasing the restriction on sample size enables cost-aware ERO to allocate an adaptive number of samples based on the prior of the null as well as the available budget. Appendix D shows the comparisons for q = 0.1 and Appendix F shows comparisons with all of the other methods set to n j = 10. Our cost-aware ERO method with n = 1 performs more tests and rejects more false null hypotheses than all competing methods at n = 1.

It is worth noting that ERO and cost-aware ERO with n j = 1 are still quite different despite the restriction of sample size. We can view the difference in performance between these two methods as the benefit of allocating φ j using our game-theoretic framework. Our decision rule incorporates our prior knowledge of the probability of the null hypothesis being true and aims to maintain α-wealth (as a martingale). The experimental set up of Aharoni and Rosset [1] implicitly leverages similar prior knowledge in the spending schemes proposed. All spending schemes proposed in Aharoni and Rosset [1] allow us to test at least one true alternative, in expectation, at which point the α-wealth should increase. This increase in α-wealth should then sustain testing until another true alternative appears. However, in the cost-aware ERO optimization problem, this information is explicitly accounted for, and helps us avoid situations described in Theorem 1 and Theorem 2. By restricting n j = 1, we have effectively limited our ability to inflate ρ j with a large sample size, and influence W α ( j ) towards being submartingale. On the other hand, nature’s equalizing strategy limits the expected payout to 0, by limiting the size of φ j , preventing the experimenter from experiencing α-death quickly, as seen in the constant spending scheme.

In our experiments, for one set of 1 , 000 potential hypothesis tests ERO investing, cost-aware, and finite-horizon cost-aware ERO all take ∼ 30 seconds on a single 2.5GHz core and 16Gb RAM. The nonlinear optimization problem was solved using CONOPT [11]. Because the solver depends on initial values and heuristics to identify an initial feasible point, infrequently the solver was not able to find a local optimal solution; in these instances, the solver was restarted 10 times and if it failed on all restarts the iteration was discarded. Out of 10 , 000 data sets at most 27 iterations were discarded (for n j = 1). Code to replicate these experiments is available at https://github.com/ThomasCook1437/cost-aware-alpha-investing.

One of the benefits of incorporating a notion of sampling cost into the hypothesis testing problem is the ability to allocate resources based on the prior probability of the null, q. We generated simulation data as previously described except the prior probability of the null hypothesis is selected at random from q j ∼ Beta ( a , b ) where a + b = 100 and with 2 , 500 independent realizations of the data. Appendix B contains pseudo-code and further implementation details. Figure 3(a-c) shows the power, mFDR, and mean number of samples per test as a function of E [ q j ]. The results show that cost-aware ERO α-investing achieves high power while maintaining control of the mFDR. A key result of this experiment is that should it not be possible to collect as many samples as the optimization problem yields, the investigator may choose to not perform the test at all and instead wait for a test (with associated prior) that does yield an optimal sample size within the budget or may choose to allow the α-wealth ante to adjust to the bound on the sample size. This often occurs for large values of q j , which we know by Theorem 2 will influence W α ( j ) towards behaving as a supermartingale. Cost-aware ERO will compensate by increasing ρ j through the sample size, n j , and will expend the W $ available, as the optimization only considers a single step. It is worth noting, that when E [ q j ] is close to 1, cost-aware ERO with n = 1, maintains power better than other methods. This can be attributed to the allocation scheme that constraint (4.6i) creates. The value of φ j is kept small so that multiple false null hypotheses are tested at an appreciable level so that α-wealth can be earned, and testing sustained. This setting is common in biological settings, where false null hypotheses can be rare.

Cost-aware ERO makes explicit the prior on the null, while the dependence on the probability of null hypotheses in the sequence is more implicit in other methods. So, an important question is, how sensitive is the method to misspecification of q j . To address this question, we consider two types of misspecification across the hypothesis sequence: variance with a correct expectation, and bias Appendix E. We find that cost-aware ERO is robust to variance in q with a correct expectation. This is likely due to the property that cost-aware ERO is relatively conservative in its allocation of ( α , $ )-wealth and the method has the opportunity to recover from losses due to misspecification. However, the cost-aware ERO is sensitive to a biased specification of q j . If the true probability of the null is 0.9 on average and q = 0.85 is used in cost-aware ERO, 273 fewer tests are performed compared to using the correct value of q. Essentially, the downward bias in the assumed q causes cost-aware ERO to be more aggressive in spending α-wealth than it should be. In practice, this effect could be mitigated, but ensuring that α-wealth spending is conservative or by giving a margin of safety to the assumed value of q j . However, a more principled solution would employ a robust optimization formulation of cost-aware ERO or to implement online-learning for the q process. While this modification is outside of the scope of this paper, it is of great interest.

To test whether extending the horizon of the reward to be maximized would enable better decisions as to ( α , $ )-wealth allocation, we varied the length of the horizon considered in the cost-aware ERO investing decision rules. In general, the optimal values returned are identical between the decision rules. This is especially visible at the beginning of the testing process. Discrepancies occur when W $ is sufficiently low such that repeatedly applying the one-step cost-aware ERO decision rule would expend all W $ prior to the final test in the finite horizon. This occurs when the finite-horizon is set to be a large number of steps or when the experiment is near the end of its funding. We also noticed that our solver exhibited less stability as the length of the horizon increased.

As seen in Figure 4, extending the horizon to include more tests results in the same allocation of samples. For E [ q ] = 0.9, which we consider most applicable to biological applications, Table 3 confirms that the solutions for different horizons are identical, with discrepancies occurring due to computational constraints.

Note that this technique optimizes the parameters of each test based on the expected wealth available at that time. The parameters set for future tests will never truly be attained. These results demonstrate that our principled ( W α , W $ ) spending strategy considering one step sufficiently captures the effect of the current test on our future tests. The martingale constraint enables us to conduct tests so that future tests remain powerful, and we do not benefit from adding additional information to our optimization problem. These results simultaneously suggest that an extended horizon may be appropriate for contexts where the optimization objective is not restricted to the expected reward or where the martingale constraint is not set for each individual test.

Gene expression data was collected to investigate the molecular determinants of prostate cancer [9]. The data set contains 50 normal samples and 52 tumor samples and each sample is a m = 6033 vector of gene expression levels. The data set has been normalized and log-transformed so that the data for each gene is roughly Gaussian. Let the empirical mean and standard deviation of the log-transformed normal samples be denoted μ ˆ j and σ ˆ j respectively and let the log-transformed tumor data be denoted x j ∈ R 52 . The goal is to test whether the tumor gene expression is increased relative to the normal samples.

We use this data set to simulate a sequential testing scenario across genes. To estimate a prior for the null hypothesis for each gene, a logistic function was fit to only the first two samples, q ˆ j = 1 − 1 + exp ( − β ( [ x j ¯ ] 1 : 2 − x 0 ) ) − 1 , where x 0 = log 10 ( 4 ) / σ and β = 2; these first two samples were then removed from the data set. The order of the genes was permuted randomly and the cost-aware decision function was computed for each gene in sequence with q ˆ j as described and θ ¯ j = log 10 ( 2 ) / σ ˆ j . We compared cost-aware ERO to ERO investing with the maximum number of samples available ( n = 50) and with a n = 3 because a typical default replication level in biological experiments is to conduct experiments in triplicate. For both procedures c j = 1 , ∀ j, and W $ [ 0 ] = 1000. Pseudo-code and implementation details for this experiment can be found in Appendix B.

Figure 5 shows the cost-aware and ERO decision rules on the prostate gene expression data set. The ERO method with n = 50 selects many tests, but rapidly expends W $ , as it does not optimize the sample size. The ERO method with n = 3 is able to test a much greater number of genes because it is limited in the amount of W $ expenditure per test. While it may appear that the ERO method with n = 3 is a much more favorable result, there are some critical concerns with this rejection sequence. First, ERO ( n = 3) fails to reject nearly all of the tests in the first 50 genes. Among those genes are many that clearly have a strong differential gene expression signature, x ¯ j shown in Figure 5. Congruent with our observations of the effect of piggybacking in ERO investing (Figure 1), had one of the early tests appeared later in the sequence, after ERO had accumulated a significant α-wealth reserve, it would have been rejected. Second, ERO ( n = 3) received a much noisier observation of the true differential gene expression signature compared to ERO ( n = 50). As can be seen in Figure 5, ERO ( n = 50) does reject many early tests that do display a 2-fold increase in gene expression in the tumor compared to the normal cells when we observe all 50 samples. ERO ( n = 3) likely fails to reject true alternative hypotheses, in part, due to the fact that it does not have access to enough samples to accurately assess the true differential expression level. Cost-aware ERO allocates, on average n j ∗ ¯ = 15.5 samples per test. This allocation strikes an balance between ERO with n = 3 and n = 50. It is provides a more accurate measurement of the differential gene expression than ERO ( n = 3), it does not expend the sample collection resources as aggressively as ERO ( n = 50). Finally, it is not as susceptible to the (random) ordering of the tests compared to ERO ( n = 3) which has the issue α-piggybacking or ERO ( n = 50) which has the issue of betting the farm in terms of sample resource wealth.

The Library of Integrated Network-Based Cellular Signatures (LINCS) NIH Common Fund program was established to provide publicly available data to study how cells respond to genetic stressors, such as perturbations by therapeutics [12]. The data considered is made up of L1000 assays of 1220 cell lines. The L1000 assay provides mRNA expression for 978 landmark genes. Differential gene expression is then calculated under a protocol known as level 5 preprocessing. Jeon et. al. [15] infer the remaining genes using a CycleGAN and make the predictions available on their lab’s webpage.3³

https://maayanlab.cloud/sigcom-lincs/#/Download

Data was prepared in a similar fashion to the prostate cancer data. Data was available for 1220 samples which experienced a 10 uM perturbation Vorinostat. Differential expression for 23 , 614 genes against controls were processed as per the L1000 Level 5 protocol. Following this protocol, we divided the values by the standard deviation for each individual gene so that the data had unit variance. Our experimental protocol utilized 100 samples to estimate q. We set q j = 1 − 1 + exp ( − β ( [ x j ¯ ] 1 : 100 − x 0 ) ) − 1 , where x 0 = 2 / σ and β = 0.6. The distribution of q j reflects our prior belief that most genes are likely to belong to the null hypothesis. Samples used for this estimation were shuffled between iterations. For both procedures c j = 1 , ∀ j, and W $ [ 0 ] = 100000. Our method was allowed n ≤ 1120 samples while the ERO used n = 1120 samples. The order of genes was randomly shuffled and the procedures were repeated 1 , 000 times to collect average statistics. One sided Gaussian tests were performed where μ 0 = 0 and μ A = 0.5. σ = 1 is assumed since data is already standardized.

Our method (CAERO) results in 797 tests with 176.89 rejections and an average sample size per test of n = 108. while ERO ( n = 1120) results in 90 tests with 32.49 rejections. The results on this data set are consistent with observations for the prostate cancer gene expression data set in that the ERO procedure expends its sample budget long before the α-wealth has been exhausted.